Welcome back!
A lot of progress was made since last time. I've implemented Merkle proofs, and in fact revamped the whole Merkle tree implementation — my initial attempt having turned rather unfit in retrospect. I explain all of this and much, much more in the README file of the patricia package. Look for the section on tree layouts for the explanation of why my initial design wasn't ideal.
I finally got to move towards the implementation of Verkle trees proper. There I've faced the most significant challenges I've encountered so far in the apprenticeship.
The difficulty with Verkle is not in the tree proper, but in implementing the vector commitment scheme. The scheme is described in this amazing blogpost by Dankrad Feist. This other post mostly explains how multiple proofs can be aggregated, though I haven't gotten this far — it also has some relevant information for the basic scheme. There is also this paper that gives a more formal treatment. Unfortunately, I've just stumbled onto it, so I haven't been able to go over it yet.
At first, I also relied a lot on this document titled "From Zero (Knowledge) to Bulletproofs", however I found Dankrad's posts easier to follow. To be fair, one difference is that the Verkle tree scheme's hiding properties are not as stringent as the real bulletproof scheme. For instance, two commitments to the same tree will be the same — a desirable property in the context of Verkle tree, but not in the general zero-knowledge context.
My first big difficulty actually arose before finding Dankrad's blogpost (which unlocked the answer). I understood how to write a vector commitment, but couldn't figure out how I could open such a commitment at a particular position, i.e. prove the value at a particular index without revealing all the values.
It turns out the key is to use the vector commitment to evaluate a polynomial at a value that corresponds to the index we want to reveal. Wow, what?
I won't get too deep into the math here, but essentialy we treat the vector as the coefficients of a polynomial. The inner product of this vector by another vector reprensenting the value of terms without the coefficients (i.e. (1, x, x^2, xˆ3, ...) , but where x is not an abstract variable but a concrete number) is the evaluation of the polynomial at x.
If we use the vector as the coefficients of the polynomial, computing this weird polynomial doesn't really tell us anything. What we'd like is that evaluating the polynomial with x = 1 gives us the item at index 1 of the vector.
Fortunately, this can be achieved by using a Lagrange interpolation polynomial. The formulas are given at the bottom of Dankrad's article. I won't claim to understand the math deeply, but Lagrange interpolation deals with the fact that a set of N points uniquely defines a polynomial of degree N. In our case, the points are ((0, v0), (1, v1), (2, v2), ...) where the v0 is the value of the vector at index 0, etc.
So now we can evaluate the polynomial at index i and get the ith item of the vector, right?
(And remember that evaluating the polynomial at i = computing the inner product of the vector to a vector of Lagrange basis polynomial, evaluated at i.)
Well, almooost. Instead of using iwe are going to use w^i for i in [0, 255] where w is a d-th root of unity of the finite field p of the curve used in our scheme. d is the size of our vectors (and so also the width of the Verkle tree). Why do we do this? It turns out that computing the Lagrange basis polynomials is much simpler when the value is a root of unity.
(Lagrange polynomials almost make sense to me. This root of unity stuff? I know the definition, but otherwise, no clue.)
This is where I run in another issue. See, the scheme is meant to be used with Bandersnatch, a new curve developped by Ethereum Foundation researchers. One important characteristic of Bandersnatch is that the size p of its finite field is such that (p - 1) % 256 == 0 where 256 is the proposed Verkle tree width (i.e. the d value mentionned before). The finite field only admits 256 256th root of unity (which we need to compute our polynomial!) if this condition holds.
But alas, Bandersnatch being new, there doesn't seem to be any Java implementation around. I was prototyping the scheme using Seckp256k1, the curve that Ethereum uses for signing transactions, but alas, it's field size does not satisfy the condition.
So I guess I need to actually implement the curve? Stay tuned for the next update to see how I did!
To cap it off, once we gain the ability to evaluated the polynomial at w^i to get the ith vector item, what the prover can do is send a commitment to the vector, and then later zero-knowledge proofs that the inner product of that vector to the Lagrange basis polynomials is the ith vector element. Most of Dankrad's article is actually dedicated to explaining this proof ("the inner product argument") and how it can be compressed to become logarithmic in the size of the vector (and don't forget that after, we can aggregate many such proofs with very little overhead).