Zero-knowledge proof systems are governed by witness data, which we feed as inputs to an arithmetic circuit. Most data, as the name of the schemes imply, remains secret. However, for the NP-statements we are proving to be useful, we must also include public witness data. For instance, we may want to prove we know the pre-image of a hash function by only revealing the image, and arithmetizing the hash function itself.
Arguably the most popular zero-knowledge proof system to date is Groth16. The main reason for its popularity is the incredible succinctness of its proofs, and cheap verification on blockchain systems like Ethereum. Let us focus on the case of Ethereum Groth16 proof verification. While the scheme is generally quite gas efficient, if the public witness data of a circuit is large, costs escalate more or less linearly with the number of public inputs to the circuit. This blog post explains the inner workings of Groth16 quite well.
Suppose we instantiate the Groth16 scheme over the BLS12-381 curve, which is supported in Ethereum under EIP-2537. The estimated gas usage of verifying a single proof can be defined as:
Gas(n) = 168,100 + 12(n+1) * D_{n+1}
Where D_k is defined by the following discount factors:
| Condition | D_k |
|---|---|
k = 1 | 1000 |
k = 2 | 949 |
k = 3 | 848 |
k = 4 | 797 |
k = 5 | 764 |
k = 6 | 750 |
k = 7 | 738 |
... | … |
1 < k <= 128 | T_k |
k > 128 | 519 |
And:
n: Number of variable public inputs.168,100: Gas cost for a 4-pair BLS12-381 pairing check.12: Simplified coefficient for G1 MSM gas cost.D_k: G1 MSM discount factor for k elements.T_k: integer from the EIP-2537 G1 discount table.For a proof with 37 public inputs, the gas usage is 448540, whereas for a proof with 2 public inputs, the gas usage is 198628. This represents more than double the amount of gas required to verify a proof with 37 public inputs, versus 2 public inputs. The reason why we instantiated the gas function with these specific values will become apparent soon.
Ethereum block times aren’t necessarily the fastest. To speed up block production, an architecture known as Plasma can be employed, where Merkle tree updates pertaining to the state of another blockchain are verified on Ethereum. The other blockchain is called a Layer 2 (L2), while Ethereum is called a Layer 1 (L1).
Assuming the hash function chosen for the Merkle tree is efficient to compute on Ethereum (i.e., Solidity), Plasma is incredibly gas efficient, and allows processing many updates in a batch, improving throughput of L1 operations.
Suppose the Merkle tree contained commitments to secret data witnessed in a zero-knowledge proof. On Ethereum, we wish to verify proofs that validate the commitments, then append their data to a Merkle tree.
Neither Keccak256, Blake2b, nor Sha256 (all hash functions that contain pre-compiles on Ethereum) can be efficiently computed in an arithmetic circuit (without generating many constraints). One of the cheapest hash functions to compute on Ethereum to date, that is simultaneously cheap to compute on an arithmetic circuit, is Poseidon2. Even then, a single instance of the Poseidon2 compress function can cost around 14-15k gas. Given that we must compute many hashes to incrementally update a Merkle tree, gas usage escalates quite quickly. If instead of computing a Merkle tree update, we offload that procedure to a zkSNARK, by proving the correct update of the tree, we can potentially save on gas. Let’s call this architecture zkPlasma, since Merkle tree updates are verified by a zkSNARK.
In spite of zkPlasma presenting a compelling architecture for an L2, there is a massive scalability challenge: the large number of public inputs to the proof. Recall our gas estimates for 37 public inputs. Imagine they represent the following:
Our estimate for 37 public inputs is 448540 gas. At 14k gas per Poseidon2 compress function, and for a 32 level tree, we would be spending 448k gas to hash up the tree. To scale zkPlasma, we need to find a compromise between cheap Ethereum verification and cheap zkSNARK proving.
There is a surprisingly simple solution to fix the dilemma presented in the previous section. In the arithmetic circuit, we can commit to the original public inputs and compress them in two steps.
The first step involves computing a Fiat-Shamir transcript of all the public
inputs (with domain separation). This step is done inside the arithmetic
circuit. Either Poseidon or Poseidon2 can act as a random oracle, and they are
efficient to compute in an arithmetic circuit, so they may be used as our
transcript hash function. From the transcript of all (original) public inputs,
we squeeze out a challenge point z. The second step involves treating the
(original) public inputs as the coefficients of a polynomial P, then
evaluating y = P(z). This step is done in the arithmetic circuit, and repeated
in Solidity, while verifying the proof.
The new public inputs of the circuit become z and y. Recall that for 2
public inputs, Groth16 (over BLS12-381) proof verification costs roughly 198628
gas. In Solidity, z is passed verbatim, and y is recomputed from the
original public inputs. The computation of y is efficient, because it only
depends on 37 calls to addmod and mulmod (via Horner’s method).
z is bound to the original inputs, because of the Fiat-Shamir transcript we
compute from them. Moreover, because it is exposed as a public input, provers
cannot cheat, and alter the public inputs of a proof.
The likelihood of finding a collision for y is equivalent to happening to find
a value of z that is a root of P, which is negligible, given the size of the
scalar field of BLS12-381. A more in-depth explanation is given by the
Schwartz–Zippel
lemma.