popcornpaws / fde

Atomic BlockChain Data Exchange with Fairness

FDE protocols allow a server and a client to exchange KZG-committed data securely and fairly. The server holds all the data, while the client only knows a KZG (polynomial commitment) to the data. For more details on the protocol, refer to our research paper. This protocol is useful for Ethereum in a post EIP-4844 world. In particular, blocks will contain blob data (KZG commitments) that commit to rollup data. The block header only contains KZG commitments, while full nodes store the entire data. It is reasonable to assume that an efficient market will emerge for downloading rollup data from full nodes. This work creates protocols that allow full nodes to exchange the committed data for money in an atomic and fair manner.

Title: Atomic BlockChain Data Exchange with Fairness

Authors: Ertem Nusret Tas, Valeria Nikolaenko, István A. Seres, Márk Melczer, Yinuo Zhang, Mahimna Kelkar, Joseph Bonneau.

Currently available at the following link:

• IACR eprint link.

Quickstart

The protocols in the paper are implemented in the Rust programming language, relying heavily on cryptographic libraries from arkworks. The source code is found in src. Respective smart contracts were implemented in Solidity and they are found in contracts.

Installing, building, and running tests

First, you must install rustup by following the steps outlined here.

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

Clone the repository and jump into the cloned directory

git clone https://github.com/PopcornPaws/fde.git
cd fde

• build: cargo build --release (the release flag is optional)
• test: cargo test --release (the release flag is optional)
• benchmark: cargo bench

Contracts

Requires Foundry.

Install: forge install

Build: forge build

Differential tests: forge test --match-test testRef --ffi

Other tests: forge test --no-match-test testRef

Implemented BDE protocols

Below is a short introduction to the implementation of the protocols in the paper. IMPORTANT This is an unaudited, proof-of-concept implementation used mainly for benchmarking and exploring practical feasibility and limitations. Do not use this code in a production environment.

ElGamal encryption-based

This version of the protocol uses exponential ElGamal encryption for generating the ciphertexts. Plaintext data is represented by scalar field elements of the BLS12-381 curve. Since exponential ElGamal relies on a brute-force approach to decrypt the ciphertexts, we needed to ensure that the encrypted scalar field elements are split up into multiple u32 shards that are easier to decrypt than a single 256-bit scalar. Thus we needed an additional encryption proof whose goal is to prove that the plaintext shards are indeed in the range of 0..u32::MAX and we also needed to ensure that the plaintext shards can be used to reconstruct the original 256 bit scalar. For this, we used simple DLEQ proofs. For the range proofs, we used a slightly modified version of this implementation, that is based on the work of Boneh-Fisch-Gabizon-Williamson with further details discussed in this blogpost.

Paillier encryption-based

This version of the protocol uses the Paillier encryption scheme to encrypt the plaintext data. It utilizes the num-bigint crate for proof generation due to working in an RSA group instead of an elliptic curve. Computations are, therefore, slightly less performant than working with arkworks libraries, but we gain a lot in the decryption phase where there is no need to split up the original plaintext, generate range proofs, and use a brute-force approach for decryption.

On-chain components of our protocols

Our protocols apply smart contracts to achieve atomicity and fairness. Have a look at our implemented FDE smart contracts.

Benchmarks

We provide benchmarks in this folder.

Contributing

We welcome any contributions. Feel free to open new issues or resolve existing ones.

Disclaimer

The code is being provided as is. No guarantee, representation or warranty is being made, express or implied, as to the safety or correctness of the code. The code has not been audited and as such there can be no assurance it will work as intended, and users may experience delays, failures, errors, omissions or loss of transmitted information. THE CODE CONTAINED HEREIN IS FURNISHED AS IS, WHERE IS, WITH ALL FAULTS AND WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING ANY WARRANTY OF MERCHANTABILITY, NON- INFRINGEMENT OR FITNESS FOR ANY PARTICULAR PURPOSE. Further, use of any of the smart contracts may be restricted or prohibited under applicable law, including securities laws, and it is therefore strongly advised for you to contact a reputable attorney in any jurisdiction where these smart contracts may be accessible for any questions or concerns with respect thereto. Further, no information provided in this repo should be construed as investment advice or legal advice for any particular facts or circumstances, and is not meant to replace competent counsel. The authors are not liable for any use of the foregoing, and users should proceed with caution and use at their own risk.

fde's Issues

Exponential ElGamal decryption optimizations

Currently, the verifier naively brute forces the exponential ElGamal ciphertext to recover the underlying plaintext. This has a linear complexity. We could either (depending on the application and the assumptions about the clients computational/storage complexity):

1. Use lookup tables to read off the plaintext as it was done in this paper. Some of the lookup tables here have MB, even GB size, which might be intolerable in certain applications. So caution is required here.
2. Use Shank's Baby step Giant step algorithm or Pollard's rho algorithm to recover the plaintext, i.e., the discrete logarithm of g^m, where m is the message. This would have square root complexity in the size of the range.

Paillier subset opening fixes

Implement the final Paillier subset-opening protocol, which is currently not supported.

Import Ethereum's KZG common reference string for compatibility

We use the following unsafe, completely insecure, common reference string for our proof of concept implementation.

fde/src/commit/kzg.rs

Lines 18 to 28 in 8759afa

	pub fn unsafe_setup(tau: C::ScalarField, range: usize) -> Self {
	let mut g1 = Vec::new();
	let mut g2 = Vec::new();
	let mut exponent = C::ScalarField::one();
	for _ in 1..=range {
	g1.push((<C::G1Affine as AffineRepr>::generator() * exponent).into_affine());
	g2.push((<C::G2Affine as AffineRepr>::generator() * exponent).into_affine());
	exponent *= tau;
	}
	Self { g1, g2 }
	}

For applications that want to be compatible with Ethereum, it will be necessary to use the common reference string of the KZG commitment created in 2023 during a large-scale KZG ceremony by the Ethereum Foundation.

add readme

Extensive benchmarks

Description

Add benchmarks (where applicable) for

• total prover time
• total verifier time
• subprotocols
  • kzg proof gen/verify
  • elgamal encryption/decryption - brute force
  • paillier encryption/decryption

Refactor and improve code readability

Description

Before adding extensive benchmarks, the code should be refactored.

• clean up Paillier
• add a common interface for the proofs if possible
• add comments
• #11
• #13

Create informative Readme

DO it! :)

Batching range proofs and other range proof-related optimizations

Currently, range proofs are not batched, and verifier does a linear number of pairings. This could be improved if using Construction 2. in this paper whereby the verifier does linear work but only in G1! Most likely, concretely, this will be quite an improvement.

Range proofs and split encryption should be connected cryptographically

Description

The current implementation (used only for benchmarking) doesn't check whether the encrypted "split" ciphers and the range proofs on the respective "split" scalar values are connected. In other words we have the following:

• the original data point $p\in\mathbb{F}$ represented as a scalar
• the "split" data points $p_i\in\mathbb{F}$ that are in a brute-forceable range (e.g. $2^{32}$)
  • $p = \sum p_i\cdot 2^{32\cdot i}$
• the "split" ciphertexts using exponential Elgamal encryption
  • $ct_i = (g^y, g^{p_i}h^y)$, where $g\in\mathbb{G}$ is a generator, $h = g^r$ with $r\overset{\textdollar}{\leftarrow}\mathbb{F}$
    -range proofs are generated on each $p_i$ to ensure they are within the brute-forceable range $2^{32}$

However, $p_i$ in the ciphertext $ct_i$ is currently not enforced in the verification process to be equal to the number we generated the range proof on. Thus, a malicious prover can split the original data point in such way that the "split" scalars are not in the brute-forceable range and generate range proofs on different scalars in the brute-forceable range.

Solution

We could somehow check the commitments of the range proofs against the ciphertexts, since they might both contain the element $g^{p_i}$.

• ciphertext: $g^{p_i}h^y$
• KZG commitment of polynomial $f(x)$: $g^f(tau) = g^{p_i}$ if we choose $f(x) = p_i$ as a constant polynomial, which is sufficient, according to this blogpost

Problem --- the implementation taken from here doesn't seem to use the constant polynomial for the secret number, so more thought should be given to how this can be implemented.

Smart contract notes

Goal

The goal of this issue is to start a conversation about the smart contract structure and design choices. We want to make payments atomic, i.e. the number of messages between the client and the server should be minimal. Thus, if possible, we want to implement something better than a traditional escrow contract where the buyer locks tokens and the seller can only access these tokens if the conditions programmed into the smart contract are met.

In our case, the buyer is the client who pays the server for the decryption key of some encrypted data. The server is the seller who should only receive payment if they provide valid encrypted data to the client. Furthermore, upon receiving the payment, the server must send the valid decryption key for the encrypted data.

We can see that the above scenario takes multiple steps (transactions) and requires the client to trust the server. Thus, by making the above scenario atomic, we could eliminate the trust factor.

Adaptor signatures

Adaptor signatures, in theory, could be used to make the outlined scenario atomic. The process would look like this:

• client signs a transaction that would transfer funds from their address to the server's address
  • however, due to the properties of adaptor signatures, this signature would not be accepted as valid by the blockchain, i.e. it cannot be executed until the adaptor (server) adapts it
• server checks the incomplete transaction signature validity and adapts (signs) it if the contents are valid
• server submits the adapted signature to the network, which transfers a given amount of tokens from the client to the server
• client queries the submitted transaction event and extracts the decryption key from the adapted signature

Note, that all steps above can be executed offline, except for the step where the server submits the transaction on chain, making the whole process atomic from the network's perspective.

Concerns/questions

However, my main concern about this is that nothing enforces the client to sign the transaction with a wallet that indeed holds enough funds for the transaction to succeed. I.e. if the client's signer wallet is empty, the submitted transaction will fail because there's not enough funds to transfer to the server's address.

Another concern of mine---although it might just be that I don't fully understand adaptor signatures yet---is that funds can only be transferred from the client's address if the client is the transaction signer. But in case of an adapted signature, the ultimate signer will be the server, thus they cannot just send a transaction that transfers funds from another address to their address. The client just "pre-signs" the transaction, thus, from the network's perspective, it will be the server who sends the adapted, valid transaction that attempts to transfer funds from the client's address.

Possible solution

Thus, it might not be possible to reduce the whole protocol to a single transaction. I see the following solution

• user locks some funds into our smart contract to ensure it can be transferred from the contract to the server
• a pre-signature is saved next to the user's locked funds that was signed by the user (this way, it can be ensured that the server submits an adapted signature of the intended pre-signature, not some random (but still valid) signature.
• server queries the pre-signature and the locked funds and verifies that the pre-signature was generated on a transaction that would withdraw the locked amount from the smart contract to the server's address
• server adapts the locked pre-signature and submits the adapted signature
• client, who is subscribed to the smart contract events, sees the submitted adapted signature, and they extract the decryption key from it

The only problem I currently see with this solution is that the server may malfunction/etc. and never submit a transaction, meaning that the client's funds are locked forever. Thus, we should provide the option for the user to withdraw their locked funds after a week or something. If the client could withdraw their funds at any time, they could withdraw it at a point where the server's transaction has already been submitted, meaning that the client gets back their funds and the server's transaction will fail. However, the adapted signature of the failed transaction will still be visible and the client gets the decryption key without payment to the server.

Thus, there should be at least three callable functions in this contract:

• lockFunds(client_address, server_address, amount, pre-signature)
• withdrawFundsClient(client_address, server_address) - here's an example to check expiration using block.timestamp
• withdrawFundsServer(server_address, client-address, adapted-signature) - the provided adapted signature should be checked against the stored pre-signature submitted by the client

Not sure about the state yet, but we should store the locked amounts and pre-signatures in a map that has the concatenated server_address and client_address as key?

Let me know @seresistvanandras what you think.

Backlog

• application of Merlin transcript
• what should be hashed into the challenge in order to maintain soundness but also efficiency (BLS, generator, etc)?
  • client-related data in hash? Replayablitiy vs server efficiency (reusability)
• optimize range proofs
  • batch multiple openings with respect to different polynomials
  • Efficient polynomial commitment schemes for multiple polynomials