# How to use KZG commitments in proofs With EIP-4844, a new object enters the scene in Ethereum: The additional calldata will be committed to using a KZG commitment $$C = [f(s)]_1$$ where $f$ is a function that evaluates to the committed data at certain points (a 4096th root of unity), $s$ is the KZG trusted setup secret, and $[x]_1=x g_1$ is a shorthand notation for elements of $G_1$. The function $f$ is defined as the interpolation polynomial $$f(\omega^i) = d_i$$ where $\omega^{4096}=1$ is a root of unity of order 4096, and $d_i$ define the data points. (Alternatively, applications can forget about the $d_i$ and simply see the polynomial itself as the input). Data transactions in Ethereum will only get the KZG commitment $C$ as an input, and will not have any way of accessing the data directly. The only access provided will be a precompile that verifies an evaluation, i.e. given $C, x$ and $y$, verifies that $f(x) = y$. Optimistic rollups tend to use multiple rounds nowadays, and thus can always resolve any fraud claim to an ultimate disagreement over a single point of $f(x)$. However, how can ZKRollups do the same? For schemes that naturally work over KZG commitments, for example PLONK using BLS12_381, it is easy. However, many applications will choose different prover schemes and more importantly, other elliptic curves with different group orders and thus other fields. Computing a KZG commitment inside the proof would be very expensive (4096 BLS12_381 operations). How can we reduce this cost? ## The trick The original trick is well known; Given two polynomial commitments $C_1$ and $C_2$ over the same field (but not the same scheme, e.g. they could be KZG and FRI, or both KZG but with different trusted setup), there is an efficient way to prove that they are equivalent, i.e. commit to the same function $f(x)$: 1. Let $x=\mathrm{hash}(C_1, C_2)$ 2. Compute $y = f(x)$ 3. Generate proof $\pi_1$, that proves $y = f(x)$ with respect to $C_1$ 4. Generate proof $\pi_2$, that proves $y = f(x)$ with respect to $C_2$ The prover sends $C_1, C_2, y, \pi_1, \pi_2$. The verifier accepts if $y = f(\mathrm{hash}(C_1, C_2))$ and the proofs $\pi_1$ and $\pi_2$ verify. The correctness of this scheme follows from the Schwarz-Zippel Lemma if the field is large enough (i.e. 256 bits for 128 bit security) (This technique was summarized by Vitalik here: https://ethresear.ch/t/easy-proof-of-equivalence-between-multiple-polynomial-commitment-schemes-to-the-same-data/8188) ## ZKPs over non-aligned fields The trick we just saw only works if $C_1$ and $C_2$ are polynomial commitments over the same field. But most prover systems will work over different fields. So in this form it is not that helpful. However, all is not lost. Here are two methods which should work to create an efficient scheme to introduce data committed by KZG commitments into a proof ### Method 1: Use a Merkle tree A Merkle tree with the leaves $d_0, \ldots, d_{4095}$ is actually a polynomial commitment. To evaluate at a point, the prover simply gives the points $d_0, \ldots, d_{4095}$ to the verifier. The verifier can reconstruct $f(x)$ from these points and check that $f(x)=y$. The downside of this is the huge proof size, but in our case this is actually fine: This proof is just a witness to the proof, and we want the circuit to have access to the data $d_0, \ldots, d_{4095}$. What remains is the cost of evaluating this. Using the [barycentric formula](https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html#evaluating-a-polynomial-in-evaluation-form-on-a-point-outside-the-domain) this can be done using 4096 multiplications and 4096 divisions. **Total cost** The full cost of introducing the data into the circuit is (1) the Merkle tree computation, requiring 4095 hashes and (2) 8192 non-aligned field operations (multiplications and divisions). Cost of non-aligned field operations have gone down a lot since the introduction of schemes like Plookup. ### Method 2: Use "Fiat inputs" A "fiat input" is a name I am trying to establish for this construction: Let $e_0, \ldots, e_{k-1}$ be field elements, which we commit to using a "suitable" commitment scheme; suitable means that it is in some form compatible with the prover scheme. Let the commitment be $E$. Saying that $e_0, \ldots, e_{k-1}$ is a "fiat input" to the circuit means that the field elements $e_0, \ldots, e_{k-1}$ are available as input wires, as well as one extra wire that contains $E$ (This could be the commitment cut off to be contained in a field element). Below I will demonstrate that it is easy to add "Fiat inputs" to PLONK using KZG commitment, by adding only a small amount of work to the verifier. In particular, the amount of work is constant and not proportional to $k$. I believe that this construction can be generalized to almost any prover scheme, but it does certainly require a modification of the scheme. But first let's see what we can do if we have a "Fiat input": Let's add the data $d_i$ as a Fiat input. If the proof field is larger than the BLS field, we can simply set $e_i = d_i$ and leave some leading zeros. If it is smaller, we might need several $e$ field elements to encode one $d$ BLS element. Now we can set $C_2 = E$ and execute the polynomial commitment equivalence proof over $C_1$ and $C_2$ **Total cost** Inside the circuit, we now only have to evaluate the polynomial, i.e. 8192 non-aligned field operations. No hashes are necessary (except for a single one for computing the random point $x$). This method has a big advantage if hashes are expensive inside the circuit. This will mostly be the case if for security reasons, no arithmetic hash functions should be used; if arithmetic hash functions can be used, the hashing cost is probably similar to the evaluation cost and the advantage of this technique not worth the complication #### Constructing a Fiat input in PLONK In order to show that Fiat inputs with the above properties can be constructed, I will show how to modify the [PLONK](https://eprint.iacr.org/2019/953.pdf) protocol to add a Fiat input. This is best described as a small modification to the PLONK protocol (specifically the KZG-based PLONK protocol), so please read this section alongside the PLONK paper. We want to add a Fiat input $\mathbb e = e_0, \ldots, e_{k-1}$ to the circuit. This means we want to make the inputs $e_0, \ldots, e_{k-1}$ as well as a representation of $E$ available to the circuit, which we are going to call $\mathrm{map\_to\_field}(E)$. Note that PLONK reserves $\ell$ public inputs in a circuit. We will abuse the first $k+1$ of the public inputs for the Fiat inputs. This works as follows: To the prover, we add the following steps: 1. The prover commits to the Fiat inputs using the KZG commitment for the function $\mathrm{FI}(X) = \sum_{i=0}^{k-1} e_i L_i(X)$, which is $E=[\mathrm{FI}(s)]_1$. 2. As part of the proof, the prover adds $E$ as well as a KZG proof $\pi$ that shows that $FI(X)$ is zero in the domain except in $i=0,\ldots,k-1$. To the verifier, we add the following steps: 1. Verify the proof $\pi$ that $FI(X)$ is zero in the domain except in $i=0,\ldots,-1$. 2. When computing the public inputs, we need to add the Fiat inputs that we have "abused". For this purpose, the public input polynomial will become $\mathrm PI(X) = - FI(X) - \mathrm{map\_to\_field}(E) L_k(X) - \sum_{i=k+1}^{\ell -1} x_i L_i(X)$. In fact the verifier does not know this polynomial, but they can compute the commitment $[\mathrm{FI}(s)]_1 = - E - [- \mathrm{map\_to\_field}(E) L_k(S) - \sum_{i=k+1}^{\ell -1} x_i L_i(s)]_1$ which is enough to complete the proof verification. This is enough to add Fiat inputs to PLONK; in fact something very similar to this idea should work for any scheme that uses additively homomorphic commitments. Things get a bit more difficult without additive homomorphic commitments, however there are still ways to get Fiat inputs at least as long as the commitments are