Verkle Trie of Ethereum

Polynomial

Coefficient representation

$$f(x) = x^3 - 2x + 1$$

Point-values representation

• (0,1), (1,0), (2,5), (3,22)

Point-values to coefficients

• How many points do we need?
  if $d$ is the degree of the polynomial, then $d+1$ points are needed.
• How to find the coefficients?
  • (method 1) solve the linear equation in $d+1$ variables
  • (method 2) use Lagrange interpolation
    

Reed-Solomon code: Let $d+1$ points be the stored data, and add other $n$ points as the parity data.

Schwartz-Zippel lemma

• For random $x_0$, if I can give the correct evaluation $f(x_0)$, then I know entire information of $f(x)$ (e.g. the all coefficients).

Polynomial Commitment

• Vector to point-value $$(v_0, v_1, \dots, v_n) \rightarrow (0, v_0), (1, v_1), \dots, (n, v_n)$$
• Point-value to $n$ degree polynomial $f(x)$
• Provide the polynomial commitment $C(f(x))$
• Provide a proof $\pi$ for a point $(z, y)$ where $ y = f(z)$

KZG Commitment

• KZG commitment is a kind of implementation of polynomial commitment.

• Knowledge -> Point-values -> Coefficients -> Commitment -> Open & Prove & Verify
                           FFT             MSM(Multi-Scalar Multiplication)
                                            ^
                                            |
                                      Trusted Setup
  

  • trusted setup:

    • generate a random secret key $s$ (must no one knows) and select a curve and a base point $G$ of it
    • generate a set of public points $G, sG, s^2G, \dots, s^nG$ (only generated once and are known to everyone)

  • commitment:

    • dervive a polynomial $f(x)=a_0 + a_1x + \dots + a_nx^n$ from the point-values
    • dervive the commitment $C = f(s)G = a_0G + a_1sG + \dots + a_ns^nG$

  • open:

    • randomly select a point $(z, y)$ where $y = f(z)$

  • prove:

    • construct a polynomial $f(x)-y = (x-z)q(x) \Rightarrow q(x) = \frac{f(x)-y}{x-z}$
    • derive the proof $\pi = q(s)G = b_0G + b_1sG + \dots + b_{n-1}s^{n-1}G$

  • verify:

    • given $G$, $sG$, $C$, $\pi$ and $(z, y)$, check if $$ e(C-yG, G) = e(sG-zG, \pi)$$
    • why?
      • given $e(aG, bG)=e(G, G)^{ab}$ according to the Bilinear Pairing
      • it’s easy to know that $ f(s)-y = (s-z)q(s) $
      • then $e(G, G)^{f(s)-y} = e(G, G)^{(s-z)q(s)} \Rightarrow$
      • $e((f(s)-y)G, G) = e((s-z)G, q(s)G) \Rightarrow$
      • $ e(C-yG, G) = e(sG-zG, \pi)$

Notice that $C-yG = (s-z)\pi$. But to calculate $s$ is extremely hard according to the ECDLP (Elliptic Curve Discrete Logarithm Problem).

Verkle Trie

• Graph

  

• How to calculate KZG root:

  • KZG commitment for inner node B
    • derive point-values $(0, 4444)$, $(1, 1213)$ according to the leaf nodes
    • derive polynomial: $f(x) = 4444 -3231x$
    • derive commitment: $C_B = f(s)G = 4444G - 3231sG$
  • KZG commitment for inner node A and root
    • derive point-values $(0, 1354)$, $(1, C_B)$, $(2, 6666)$
    • similar to $C_B$, $C_A$ and $C_{root}$ can be derived

• How to calculate the opening proof:

  • let’s say the path is root -> node A -> node B -> 4444
  • calculate the opening proof along the path: $\pi_{A}$, $\pi_{B}$ and $\pi_{4444}$
  • the proof data includes: $(0, 4444)$, $\pi_{4444}$, $(1, C_B)$, $\pi_{B}$, $(0, C_A)$, $\pi_{A}$ and $C_{root}$