For context see: Open problem: ideal vector commitment
Compressed introduction / recap
Kate commitments
A Kate commitment is a technique for committing to a polynomial P, where one starts with a trusted setup string consisting of elliptic curve points G, G * s, G * s^2 … G * s^{n-1} for some never-published secret s, and commits to P(x) = \sum_{i=0}^{n-1} c_ix^i by computing G * P(s) = \sum_{i=0}^{n-1} c_i * (G * s^i), a linear combination of elements of the trusted setup string. We’ll use [P] as shorthand for G * P(s), including eg. G = [1], G * s^i = [x^i].
Witnesses: Q = P // (X - w^i)
Kate commitments can be used as a replacement for Merkle trees: to commit to a piece of data D = \{D[0] ... D[n-1]\}, you interpolate the polynomial P(x) that satisfies P(1) = D[0], P(\omega) = D[1] … P(\omega^{n-1}) = D[n-1] and more generally P(\omega^i) = D[i], where \omega is an “order-n root of unity”, that is \omega^n = 1. The “Merkle root” is just the commitment [P]. A Merkle branch is a Kate commitment of the quotient Q_i = P // (x - \omega^i), where // is the “rounded division” operator, eg. (3x + 4) // x = 3, c // x = 0 for any constant c, x^2 // (x - k) = (x + k) (see if you can figure out why)… Note that unlike with integers, polynomial rounded division is a linear operator, that is (A + B) // C = A // C + B // C and (A * z) // C = (A // C) * z for any constant z.
Checking witnesses: pairing check e(Q, X - w^i) ?= e(P-z, 1)
To use a witness Q_i to prove that P(\omega^i) = z, compute the pairing check: e(Q_i, [X - \omega^i]) \overset{?}{=} e(P - z, [1]). If the check passes, then Q_i * (X - \omega^i) actually equals P - z, implying that P - z is zero at \omega^i (as otherwise it could not be expressed as a product of X - \omega^i and something else), implying that P(\omega^i) = z.
Properties
Kate commitments have some powerful advantages:
- A witness is O(1) sized, as opposed to Merkle witnesses, which are O(\log(n)) sized, where n is the number of items in the tree
- You can combine many witnesses together: given Q_{i_1} … Q_{i_k}, you can take a linear combination of these values to generate Q_{\{i_1 ... i_k\}} = P // ((X - i_1) * ... * (X - i_k)), which you can then verify as a single fixed-size witness for all the values z_1 ... z_k at those points.
So you can prove any number of values in a tree with a single point. However, compared to Merkle trees they have a big disadvantage: updating Kate witnesses is expensive. With a Merkle tree, if in every block you need to read 1000 accounts and update 1000 accounts, you only need to update \approx 1000 * \log(n) hashes in the tree to generate the Merkle branches for the 1000 accounts in the next block. With a Kate commitment, you would need to fully recompute every witness (or if you don’t recompute, computing a witness from scratch takes O(n) time, where n is once again the total size of the state, eg. \approx 2^{29} for current ethereum).
This post proposes a technique that improves on this.
Our new technique
Client-side split: P’ = P + D, compute witnesses separately and recombine at the end
Let P be the current state; assume we have already precomputed witnesses [P // (X - \omega^i)] for all i \in \{0 ... n-1\}. Now, suppose in a block we get k writes to the state, so there is a new state P' with k modifications (ie. P'(\omega^i) \ne P(\omega^i) at k positions). We do the following. Client-side, represent P' = P + D, where |D| = k (we’ll use |D| to mean “the number of \omega^i coordinates where D is nonzero”).
Let Z_{i_1 ... i_k} represent the degree-k polynomial that’s zero at \{\omega^{i_1} ... \omega^{i_k}\}, ie. (X - \omega^{i_1}) * ... * (X - \omega^{i_k}). As mentioned above, we can make a “multi-witness” that proves P(\omega^{i_j}) = z_j for all pairs in some list \{(i_1, z_1) ... (i_k, z_k)\} simultaneously, and that witness just is [P // Z_{\{i_1 ... i_k\}}].
How to compute witness for D in O(|D|) time
Rounded polynomial division is linear, so a witness [P' // Z_{\{i_1 ... i_k\}}] equals [P // Z_{\{i_1 ... i_k\}}] + [D // Z_{\{i_1 ... i_k\}}]. We already have all [P // (X - \omega^{i_j})] values and as mentioned above we can use a linear combination of those to construct [P // Z_{\{i_1 ... i_k\}}], so we just need to worry about D // Z_{\{i_1 ... i_k\}}. If we look at D // Z_{\{i_1 ... i_k\}} in evaluation form (that is, in terms of its evaluations at \omega^i positions), we can see that it can only be nonzero at (i) positions where D itself is nonzero, and (ii) positions in \{i_1 ... i_k\}. Hence, we can compute it as a |D| + k sized linear combination of [L_i] elements (where L_i = \frac{X^n - 1}{(X - \omega^i) * \prod_{j \ne i}(\omega^j - \omega^ii)}) equals 1 at \omega^i and zero at other powers of \omega^i); to determine the coefficients of this linear combination we need only solve some linear systems of equations (see https://notes.ethereum.org/AALpIfEzRWWExA5EVzLjOA for more efficient ways of doing this including removing the need for even superlinear field arithmetic).
Putting it all together
Let us summarize so far. Suppose in each block, there are k state modifications. After d blocks, P' = P + D, where |D| = k * d. The time needed to generate a witness for the next block is |D| = k * d (note: this is one witness for all accesses in that block).
At any point, we can “refresh” the scheme by setting P \leftarrow P' and D \leftarrow 0 and recomputing all P // (X - \omega^i) values; this takes O(n \log n) effort (a total of 3 n \log n EC operations using this technique: https://github.com/khovratovich/Kate/blob/master/Kate_amortized.pdf). If we recompute P every t blocks, then the total cost over those t blocks will be 3n \log n + \sum_{d=1}^t k * d \approx 3n \log n+ k * \frac{t^2}{2}. The amortized per-block cost is c = \frac{3n \log n}{t} + \frac{k * t}{2}, minimized at t = \sqrt{\frac{6*n \log n}{k}}, c = \sqrt{6k n \log n} (ie. \sqrt{6k n \log n} elliptic curve operations per block).
Realistically, n \approx 2^{30} and k \approx 2^{10} so this would still require 2^{24} elliptic curve operations per block, slightly outside the range of feasibility, but nevertheless this is a considerable step forward.