Finally after the delay in last week due to circumstances, this week was caught up with collaborating with the Nimbus team, @zahary & other EPF participants who want to create a Verkle Tree library in Nim. The library will be used in the Nimbus client, and will be open source. So if I try to sum up this week : -

  • Had a meeting with @zahary & the Nimbus team regarding the workflow and specing out the library.
  • Collaborated with other EPF participants interested in Verkle Tree & Nim, to draft a project proposal. Find the proposal here.
  • Exploring the Constantine library, using which we will be building the verkle tree library.
  • Undestanding the IPA+Pederson scheme, which will be used for commitments in Verkle Tree. ( Working on it as more clarity is needed )

Learnings

Starting of the week the meeting was delayed thus I started exploring the nim-eth-verkle repository in the github. The repository had few commits and they were using KZG Commitments from the EF github made for the EIP-4337, so was confused, yet also learnt that & it was quite interesting.

The KZG Polynomial Commitments is built on pairing based cyrptography, and it needed a trusted setup. The first method which is the $keygen(\lambda , \mathbb F) \rightarrow gp$

  • $\lambda$ is the security parameter or the randomness
  • sample random $\tau \in \mathbb F_p$
  • then $gp = (g, g^\tau, g^{\tau^2}, . . . , g^{\tau^d})$
  • delete $\tau$ ( The trusted setup )

Next comes the commitment menthod $commit(gp, f\in \mathbb F) \rightarrow comm_f$. This generates a commitment to the polynomial $f(x)$. The commitment generation is done by

  • consider $f(x)=f_0 + f_1x + f_2x^2 + . . . . + f_dx^d$
  • then $comm_f = g^{f(\tau)}$
\[g^{f(\tau)} = g^{f_0 + f_1\tau + f_2\tau^2 + . . . . + f_d\tau^d} = (g)^{f_0}.(g^{\tau})^{f_1}.(g^{\tau^2})^{f_2}. . .(g^{\tau^d})^{f_d}\]

Here the $g^{\tau^i}$ are the powers of the generator $g$ raised to the powers of $\tau$ which is the random number generated in the $keygen$ method. The $f_i$ are the coefficients of the polynomial $f(x)$.

Next comes the evalution method, which opens the polynomial at a point $u$, given by the verfier. The $eval(gp, f, u)\rightarrow v, \pi$ method is used to open the polynomial at the point $u$, this is done by

  • $f(x) - f(u) = (x-u)q(x)$, as $u$ is a root of the polynomial $f(x) - f(u)$
  • compute $q(x)$, and $\pi = g^{q(\tau)}$, using the $gp$ from the $keygen$ method

Then comes the verfication method, which is used to verify the polynomial at the point $u$ using the commitment $comm_f$ and the proof $\pi$. This is where the pairing based cryptography comes into play, as $\mathbb G$ is a cryptographic group and the Computational Diffe-Hellman(CDH) Assumtion holds, and we need pairing. The verification is done by the following

  • the idea is to check the equation at point $\tau$, i.e. :
\[g^{f(\tau) - f(u)} = g^{(\tau - u)q(\tau)}\]
  • from the previous computation we already know the following
    • $comm_f = g^{f(\tau)}$
    • $\pi = g^{q(\tau)}$
    • $v = f(u)$
  • so the challenge is to know $g^{\tau - u}$ & $g^{q(\tau)}$
  • this is done using bilinear-pairing $e : \mathbb G \times \mathbb G \rightarrow \mathbb G_T$. And if the proover is honest then the following holds true
\[e(\frac{comm_f}{g^v} , g) = e(g^{\tau - u}, \pi) \\ e(g, g)^{f(\tau) - f(u)} = e(g, g)^{(\tau - u)q(\tau)}\]

Now the KZG Polynomial Commitments have been replaced by IPA+Pedersen scheme, which is more efficient and secure. So I started exploring the IPA+Pedersen scheme, and it was quite interesting. I am still working on it, as I need more clarity on it. But I do understand IPA & Pedersen commitment seperately, I need to understand how they are combined mathematically.

The Pedersen Commitment is a hash based commitment scheme, which is used to commit to a value $x \in \mathbb Z_p$. We can understand this scheme simply.
Let us consider a cryptographic group

\[G = \{1, g, g^2, \dots g^{q-1}\}; \: q=|G|,\: \text{assume} \: q \: \text{is prime} \\ \text{where} \: g^i . g^j = g^{(i+j \: mod \: q)}\]

Now we can fix $g, h \in G$, let $R = \{ 0, 1, \dots q-1\}$, for $m,r \in R$. And now we can define our pedersen hash function as

\[H(m, r) = g^m . h^r \in G\]

Since $G$ is a cryptogtaphic group, i.e. the Computational Diffe-Hellman(CDH) Assumtion holds, and we can conclude that the Pedersen hash function is collision resistant. Now we can use this hash function to commit to a value $x$, and also verify the commitment.

\[commit(m\in R, r \leftarrow R) = H(m, r) = g^m . h^r \\ verify(m, comm, r) : \text{accept if} \: comm = H(m, r)\]

This seems rather simple and what we are used to it, but the properties that comes with this commitment schemes makes it special. It is know as the homomorphic property. This property states that if we have two commitments $comm_1 = H(m_1 \in R, r_1 \leftarrow R)$ & $comm_2 = H(m_2 \in R, r_2 \leftarrow R)$, then we can compute the commitment of the sum of the values

\[comm_1 \times comm_2 = g^{m_1 + m_2} . h^{r_1 + r_2} \\ = commit(m_1+m_2, r_1+r_2)\]

This makes possible such that anyone can sum the commited values and also verify. This is the homomorphic property of the Pedersen Commitment. This is the reason why it is used in the IPA+Pedersen scheme.

What is IPA?
It is very literal, it is the Inner Product Argument. Bulletproofs use IPA, and a few others, a trick that allows a prover to convince a verifier of the correctness of an “inner product”. An inner product is the component by component product of two vectors:

\[\vec{a}.\vec{b} = a_0b_0 + a_1b_1 + \dots + a_{n-1}b_{n-1} \\ \text{where} \: \vec{a} = (a_0, a_1, \dots, a_{n-1}) \: \text{and} \: \vec{b} = (b_0, b_1, \dots, b_{n-1})\]

One interesting case is where we set the vector $\vec{b}$ to be the power of some number $z$, i.e. $\vec{b}=(1, z, z^2, \dots ,z^{n-1})$, then the inner product becomes the evaluation of the polynomial at $z$.

\[f(X) = \sum_{i=1}^{n-1} a_i X^i\]

Findings

After the initial talk with @zahary, the meeting happened with other EPF participants along with the Nimbus team including @mamy and @daniel. The meeting was very informative and I got to know about the current state of the project, after discussion KZG was stripped of and the standard implementation would be followed upon now. The standard implementation is the IPA+Pedersen scheme, which is more efficient and secure built over the Banderwagon Curve. I am still working on it, as I need more clarity on it, I need to understand how they are combined mathematically.

A basic spec was drafted out for the development, the major finding was the Constantine library built by @mamy which consists of all the cryptographic primitives natively in Nim, it’s fuzzed and also optimized ( even faster than rust crates ). So what we need to do

  • the BLS12_381 curve is already there, and also the Bandersnatch Curve, we need to build the Banderwagon Curve, and make the PR to the Constantine library, so that it can be used.
  • the IPA needs to be implemented
  • the Pedersen Commitment needs to be implemented
  • optimize the Langrange Interpolation ( maybe, not sure )
  • then the IPA+Pedersen scheme needs to be implemented, using both of the above
  • spec out the Verkle Tree interface, from either EF or other client implementations ( would be very helpful for future clients during their implementation & transition )