Intuition on KZG Aggregation
KZG is a polynomial commitment scheme widely used in the field of cryptography. It allows a prover to commit to a polynomial, and later on open a particular point on the polynomial which can be verified by a verifier through the commitment. I’ve previously written a more detailed intuition here.
Some use cases of KZG include constructing zero knowledge proofs. When a prover would like to selectively disclose a statement without revealing all the properties, the prover will encode the statement as a polynomial and commit it. The prover can then have the options to only reveal selected points on the polynomial. Other than that, the recent Ethereum Dencun upgrade introduces protodanksharding which offers a new blob-carrying transaction type. This type of transaction normally carries large data blob (for e.g. rollups transaction data), however only the KZG commitment of the data blob is accessible on Ethereum’s execution layer. A polynomial commitment is used rather than a hash commitment as it offers more flexibility to prove only specific part. For example, if a user would like to prove that its transaction is part of the commitment, it will only need to open the polynomial at that particular point as opposed to needing to get all transactions data to reconstruct the hash commitment.
Ethereum also has plans to update the data structure used for storage from merkle patricia trie (MPT) to verkle trie. Merkle trees are hash-based, which means that a merkle proof of a storage slot will need to provide all corresponding sibling nodes (that share the same parent nodes) in order to prove an element in the tree. For verkle trie, the proof of a storage slot just needs to provide the path to the slot. We can think that each level of the tree is represented by a polynomial, so we will need to generate a KZG proof per level that proves the intermediate node in that level. The proofs have constant size. The good news is that KZG also supports a multiproof scheme which allows aggregating these proofs into a single proof, thereby further reducing proof size.
There are various variants of KZG aggregation, where in this article I’ll try to explain 1) the simplest form of multiproofs, and 2) aggregating individual KZG proofs. Let’s start with the first one.
Multiproofs
Recall that constructing a proof for a single point is to provide the quotient, where the numerator is the polynomial subtract the evaluated point, and the denominator is the root of that point. For a multiproof, we will use all the points that we want to open and form a Lagrange polynomial using that. The resulting proof is still a quotient, except that we are substituting the evaluated point with the Lagrange polynomial, and the denominator is now the product of the roots of all the points that we want to open (known as zero polynomial). Below is an example implementation.
As you can see, the resulting proof is still a constant size proof which the same size as proving one single point, so it is really bytes efficient! Verification of the proof is similar using bilinear pairing, where the verifier will also need to compute the Lagrange interpolation and the zero polynomial.
Aggregating Individual Proofs
Other than constructing a multiproof, individual KZG proofs can also be aggregated to a single proof. This is useful when each proof is generated by a different participant, in which case they wouldn’t be able to coordinate and generate a multiproof.
Some use cases for KZG proof aggregation is being able to parallelize the generation of KZG proofs between different threads or machines, and aggregate them later on. This would be useful as generating a multiproof causes proof generation time to be longer when there are more points to be opened. Other than that, there has also been research around stateless blockchains, which means that rather than the blockchain nodes needing to store the full state, they only store a commitment of the state (this can help address some state growth issues). Each user of the blockchain each stores their own corresponding states, which they can generate a proof to the commitment to show that their balance is correct. Aggregation will be useful in this case as different users generate their own proofs to show that their account balances are correct when making transactions.
To aggregate proofs, we first obtain a polynomial which is a product of the roots of unity for the points that we want to prove. We then evaluate the first derivative of the polynomial at points w^i, where i is the index of the point in the vector. Each of this evaluation is multiplied by the individual proofs, and we sum them together to obtain the aggregated proof. Below is an example implementation.
The idea is that a proof is a commitment to the quotient polynomial as mentioned in the multiproof section, and by replacing the denominator of the quotient polynomial with its partial fraction decomposition, we were able to express the quotient polynomial as a linear combination of all its individual quotient polynomial, and thus aggregatable.
That’s it for today! I have kept this fairly high level, mostly just for intuition, but if you are interested in the full maths, I’ve also done an implementation here. Drop your questions if any!