Summary

After exploring a lot of different topics and areas in which I can contribute to. Finally I have decided that I will be working on the Verkle Tree implementation. I have started reading the mathematical intricasies this week, and will be starting the implementation as soon as I have a clear mathematical understanding of working with the mathematical libraries.

A lot of cryptographic primitives are available in rust, but as I decided to implement it in Nim or Java, this week I will be exploring the cryptographic libraries available in Nim. Also need to talk with Zahary (Mentor) about the implementation details and the design of the Verkle Tree.

Learnings

For learning about the verkle trees, I found this paper very helpfull, they have kept a very simple language and explained the concepts very well, also from a implementation point of view.

While studying all these along with Nim I realized that since not a lot of cryptographic libraries are there for Nim, I will have to implement the cryptographic primitives myself. So I started reading about the cryptographic primitives and how they are implemented in Rust.

In Verkle Tree implementation there are different commitments that we can use. A commitment is a public value that is bound with the original message (computation binding) provided by a committer who will not reveal the message (hiding). The committer needs to open this commitment and send the message to the verifier to verify the correspondence between the commitment and the message. A PC can be regarded as a commitment to a certain polynomial P, and the committer can prove that the value of the polynomial at a certain point z satisfies P(z) = a through a proof without revealing the polynomial P. There are multiple schemes to implement PC:

  1. KZG10 Commitment: based on pairing group
  2. IPA Commitment: based on discrete log group
  3. FRI Commitment: based on hash function
  4. DARKS Commitment: based on unknown order group

I am further diving deep into the mathematical intricasies of these commitments, specially IPA and KZG, as these two are the most popular ones. Also while studing about these, I found that FRI Commitments are post quantum secure, but couldn’t understand, why it’s not used and implemented in any previous verkle trees.

A few of the primitives I brushed upon was Discrete Log Assumption, the basis of the Diffie Hellman Key Exchange, which states that a multiplicative group $ G $ with generator as $ g $, it is hard to find $ x $ such that

\[\text{given} \: y \in G, g^x = y \\ \textrm{for example : } 3^x = 4 ~ mod ~ 7\]

In the above example we realize that the only way to find $ x $ is by brute force, which is not feasible for large numbers, thus making it hard to find $ x $.
Now is extended and comes the compuational Diffie Hellman Assumption, which states

\[\text{Given a group :} \: G, \text{with generator :} \: g, \\ g, g^x, g^y \in G, \\ \text{it is hard to find :} \: g^{xy} \: \text{given} \: g^x \: \text{and} \: g^y\]

Also I read about the Bilinear Pairing, which is a function $ e : G \times G \rightarrow G_T $, where $ G $, and $ G_T $ are cyclic groups of prime order $ p $, and $ e $ is a bilinear map and $ g $ is the generator

\[\text{Pairing : } \: e(P^a, Q^b) = e(P, Q)^{ab} \\ \text{example}\rightarrow e(g^x, g^y) = e(g, g)^{xy} = e(g^{xy}, g)\]

Thus given $ g^x $ and $ g^y $, a paring can check that some element $ h = g^{xy} $, without revealing $ x $ or $ y $. Examples of pairing is the BLS Signature, which is used in Ethereum 2.0.

In polynomial commitments we have to prove that a polynomial $ P(x) $ of degree $ d $ is equal to $ a $ at a point $ x $, without revealing the polynomial $ P(x) $, and the point $ x $.
Let us choose a family of polynomial $ ~ \mathbb{F} ~ $, and the proover have a polynomial $ f(x) \in \mathbb{F} $, then the following happens in the polynomial commitment scheme.

\[\text{Prover : } \rightarrow commit(f) = comm_f \rightarrow \text{Verifier} \\ \text{Verifier : } \rightarrow u \rightarrow \text{Prover} \\ \text{Prover : } \rightarrow v, proof:\pi \rightarrow \text{Verifier} \\ \text{Verifier : } \rightarrow accept/reject\]

Thus there are 4 definations in a polynomial commitment scheme:

  1. Keygen : $ (\lambda, \mathbb F) \rightarrow gp $
  2. Commit : $ (gp, f) \rightarrow comm_f $
  3. Prove : $ (gp, f, u) \rightarrow u, proof:\pi $
  4. Verify : $ (gp, comm_f, u, v, \pi) \rightarrow accept/reject $

Next Week

Next week I will be diving deep into the mathematical intricasies of the polynomial commitments, learn more about IPA, FRI, etc. A lot of things yet to find out, also to decide on should we go ahead with IPA or use some other commitment schemes, etc Also I will be discussing the design of the Verkle Tree with the mentors.
Further I would look out for any existing implementation of the polynomial commitments in Nim, or even if there is any half completed works. Will also be working on drafting the project proposal.