HackMD
    • Options
    • Versions and GitHub Sync
    • Transfer ownership
    • Delete this note
    • Template
    • Save as template
    • Insert from template
    • Export
    • Dropbox
    • Google Drive
    • Gist
    • Import
    • Dropbox
    • Google Drive
    • Gist
    • Clipboard
    • Download
    • Markdown
    • HTML
    • Raw HTML
    • ODF (Beta)
    • PDF (Beta)
    • Sharing Link copied
    • /edit
    • View mode
      • Edit mode
      • View mode
      • Book mode
      • Slide mode
      Edit mode View mode Book mode Slide mode
    • Note Permission
    • Read
      • Owners
      • Signed-in users
      • Everyone
      Owners Signed-in users Everyone
    • Write
      • Owners
      • Signed-in users
      • Everyone
      Owners Signed-in users Everyone
    • More (Comment, Invitee)
    • Publishing
      Everyone on the web can find and read all notes of this public team.
      After the note is published, everyone on the web can find and read this note.
      See all published notes on profile page.
    • Commenting Enable
      Disabled Forbidden Owners Signed-in users Everyone
    • Permission
      • Forbidden
      • Owners
      • Signed-in users
      • Everyone
    • Invitee
    • No invitee
Menu Sharing Help
Menu
Options
Versions and GitHub Sync Transfer ownership Delete this note
Export
Dropbox Google Drive Gist
Import
Dropbox Google Drive Gist Clipboard
Download
Markdown HTML Raw HTML ODF (Beta) PDF (Beta)
Back
Sharing
Sharing Link copied
/edit
View mode
  • Edit mode
  • View mode
  • Book mode
  • Slide mode
Edit mode View mode Book mode Slide mode
Note Permission
Read
Owners
  • Owners
  • Signed-in users
  • Everyone
Owners Signed-in users Everyone
Write
Owners
  • Owners
  • Signed-in users
  • Everyone
Owners Signed-in users Everyone
More (Comment, Invitee)
Publishing
Everyone on the web can find and read all notes of this public team.
After the note is published, everyone on the web can find and read this note.
See all published notes on profile page.
More (Comment, Invitee)
Commenting Enable
Disabled Forbidden Owners Signed-in users Everyone
Permission
Owners
  • Forbidden
  • Owners
  • Signed-in users
  • Everyone
Invitee
No invitee
   Published      
   owned this note    owned this note
   Linked with GitHub
  • Any changes
    Be notified of any changes
  • Mention me
    Be notified of mention me
# Verkle multiproofs using random evaluation Problem: In a verkle tree of width $d$, we want to provide all the intermediate KZG ("Kate") proofs as efficiently as possible. We need to provide all intermediate commitments, there is no way around that in Verkle trees, but we only need a single KZG proof in the optimal case. There are efficient multiverification techniques for KZG if all proofs are given to the verifier, but we want to do with just a small constant number of proofs. For the notation used here, please check my post on [KZG commitments](https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html). Please see [here](https://notes.ethereum.org/_N1mutVERDKtqGIEYc-Flw) for an introduction to (KZG-based) verkle tries. ## Connection to verkle tries Quick recap: looking at this verkle trie: [![verkle trie](https://yuml.me/ethereum/a162eb37.svg)](https://yuml.me/ethereum/a162eb37.svg) In order to prove the leaf value `0101 0111 1010 1111 -> 1213` we have to give the commitment to `Node A` and `Node B` (both marked in cyan), as well as the following KZG proofs: * Proof that the root (hash of key and value) of the node `0101 0111 1010 1111 -> 1213` is the evaluation of the commitment of `Inner node B` at the index `1010` * Proof that the root of `Inner node B` (hash of the KZG commitment) is the evaluation of the commitment of `Inner node A` at the index `0111` * Proof that the root of `Inner node A` (hash of the KZG commitment) is the evaluation of the `Root` commitment at the index `0101` Each of these commitments, let's call them $C_0$ (`Inner node B`), $C_1$ (`Inner node A`) and $C_2$ (`Root`) is to a polynomial function $f_i(X)$. What we are really saying by the claim that the commitment $C_i$ evaluates to some $y_i$ at index $z_i$ is that *the function committed to* by $C_i$, i.e. $f_i(X)$, evaluates to $y_i$ at $z_i$, i.e. $f_i(z_i) = y_i$. So what we need to prove is * $f_0(\omega^{0b1010}) = H(0101\ 0111\ 1010\ 1111, 1213)$ (hash of key and value), where $C_0 = [f_0(s)]_1$, i.e. $C_0$ is the commitment to $f_0(X)$ * $f_1(\omega^{0b0111}) = H(C_0)$, where $C_1 = [f_1(s)]_1$ * $f_2(\omega^{0b0101}) = H(C_1)$, where $C_2 = [f_2(s)]_1$ Note that we replaced the index with $z_i = \omega^{\text{the index}}$, where $\omega$ is a $d$-th root of unity which makes many operations more efficient in practice (we will explain below why). $H$ stands for a collision-resistant hash function, for example `sha256`. If we have a node deeper inside the trie (more inner nodes on the path), there will be more proofs to provide. Also, if we do a multiproof, where we provide the proof for multiple key/value pairs at the same time, the list of proofs will be even longer. Overall, we can end up with hundreds or thousands of evaluations of the form $f_i(z_i) = y_i$ to prove, where we have the commitments $C_i = [f_i(s)]_1$ (these are part of the verkle proof as well). ## Relation to prove The central part of a verkle multiproof (a verkle proof that proves many leaves at the same time) is to prove the following relation: Given $m$ KZG commitments $C_0 = [f_0(s)]_1, \ldots, C_{m-1}=[f_{m-1}(s)]_1$, prove evaluations $$ f_0(z_0)=y_0 \\ \vdots\\ f_{m-1}(z_{m-1})=y_{m-1} $$ where $z_i \in \{\omega^0, \ldots, \omega^{d-1}\}$, and $\omega$ is a $d$-th root of unity. ## Proof 1. Let $r \leftarrow H(C_0, \ldots, C_{m-1}, y_0, \ldots, y_{m-1}, z_0, \ldots, z_{m-1})$ ($H$ is a hash function) The prover computes $$ g(X) = r^0 \frac{f_0(X) - y_0}{X-z_0} + r^1 \frac{f_1(X) - y_1}{X-z_1} + \ldots +r^{m-1} \frac{f_{m-1}(X) - y_{m-1}}{X-z_{m-1}} $$ If we can prove that $g(X)$ is actually a polynomial (and not a rational function), then it means that all the quotients are exact divisions, and thus the proof is complete. This is because it is a random linear combination of the quotients: if we just added the quotient, it could be that two of them just "cancel out" their remainders to give a polynomial. But because $r$ is chosen after all the inputs are fixed (see [Fiat-Shamir heuristic](https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic)), it is computationally impossible for the prover to find inputs such that two of the remainders cancel. Everything else revolves around proving that $g(X)$ is a polynomial (and not a rational function) with minimal effort for the prover and verifier. Note that any function that we can commit to via a KZG commitment is a polynomial. So the prover computes and sends the commitment $D = [g(s)]_1$. Now we only need to convince the verifier that $D$ is, indeed, a commitment to the function $g(X)$. This is what the following steps are about. 2. We will prove the correctness of $D$ by (1) evaluating it at a completely random point $t$ and (2) helping the verifier check that the evaluation is indeed $g(t)$. Let $t \leftarrow H(r, D)$. We will evaluate $g(t)$ and help the verifier evaluate the equation $$ g(t) = \sum_{i=0}^{m-1}r^i \frac{f_i(t) - y_i}{t-z_i} $$ with the help of the prover. Note that we can split this up into two sums $$ g(t) = \underbrace{\sum_{i=0}^{m-1} r^i \frac{f_i(t)}{t-z_i}}_{g_1(t)} - \underbrace{\sum_{i=0}^{m-1} r^i \frac{y_i}{t-z_i}}_{g_2(t)} $$ The second sum term $g_2(t)$ is completely known to the verifier and can be computed using a small number of field operations. The first term can be computed by giving an opening to the commitment $$ E = \sum_{i=0}^{m-1} \frac{r^i}{t-z_i} C_i $$ at $t$. Note that the commitment $E$ itself can be computed by the verifier using a multiexponentiation (this will be the main part of the verifier work), because they have all the necessary inputs. The prover computes $$ h(X) = \sum_{i=0}^{m-1} r^i \frac{f_i(X)}{t-z_i} $$ which satisfies $E = [h(s)]_1$. 3. The prover computes the polynomial evaluations $y=h(t)$ and $w=g(t)$, as well as two KZG proofs $\pi=[(h(s) - y)/(s-t)]_1$ and $\rho = [(g(s) - w)/(s-t)]_1$. The proof consists of $D$, $y$, $\pi$, and $\rho$ ## Verification The verifier starts by computing $r$ and $t$. As we have seen above, the verifier can compute the commitment $E$ (using one multiexponentiation) and the field element $g_2(t)$ Then the verifier computes $$ w = y - g_2(t) $$ The verifier checks the two Kate opening proofs $$ e(E - [y]_1,[1]_2) = e(\pi, [s-t]_2) $$ and $$ e(D - [w]_1,[1]_2) = e(\rho, [s-t]_2) $$ which prove that (1) that $g_1(t)=y$ and (2) whichever function the prover committed to using $D$ evaluates to $w$ at $t$. This means that the verifier now knows that the commitment $D$, opened at a completely random point (that the prover didn't know when they committed to it), has exactly the value of $g(t)$ which the verifier computed with the help of a prover. According to the [Schwartz-Zippel lemma](https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma) this is extremely unlikely (read: impossible in practice, like finding a hash collision), unless $D$ is actually a commitment to $g(X)$; thus, $g(X)$ must be a polynomial and the proof is complete. ## Modification to save one group element Since both KZG proofs above are at the same point, we can aggretage them to save one group element and one pairing. Compute $$ q = H(E, D, y, w) $$ and define $\sigma = \pi + q \rho$. Then the full proof can be checked by verifying $$ e(E - [y]_1 + q(D - [w]_1),[1]_2) = e(\sigma, [s-t]_2) $$ The proof thus consists of only $D$, $y$ and $\sigma$ (128 bytes for BLS12_381). # Optimization: Do everything in evaluation form This section is to explain various optimizations which make all of the above easy to compute, it is not essential for understanding the correctness of the proof (but it is for making an efficient implementation). The great advantage of the above version of KZG multiproofs, compared to many others, is that very large parts of the prover and verifier work only need to be done in the field. In addition, all these operations can be done on the evaluation form of the polynomial (or in maths terms: in the "Lagrange basis"). What that means and how it is used is explained below. ## Evaluation form Usually, we see a polynomial as a sequence of coefficients $c_0, c_1, \ldots$ defining a polynomial function $f(X) = \sum_i c_i X^i$. Here we define another way to look at polynomials: the so-called "evaluation form". Given $d$ points $(\omega^0, y_0), \ldots, (\omega^{d-1}, y_{d-1})$, there is always a unique polynomial $f$ of degree $<d$ that assumes all these points, i.e. $f(\omega^i) = y_i$ for all $0 \leq i < d$. Conversely, given a polynomial, we can easily compute the evaluations at the $d$ roots of unity. We thus have a one-to-one correspondence of $$ \{\text{all polynomials of degree }<d\} \leftrightarrow \{\text{vectors of length $d$, seen as evaluations of a polynomial at $\omega^i$}\} $$ This can be seen as a "change of basis": On the left, the basis is "the coefficients of the polynomial", whereas on the right, it's "the evaluations of the polynomial on the $\omega^i$". Often, the evaluation form is more natural: For example, when we want to use KZG as a vector commitment, we will commit to a vector $(y_0, \ldots, y_{d-1})$ by committing to a function that is defined by $f(\omega^i) = y_i$. But there are more advantages to the evaluation form: Some operations, such as multiplying two polynomials or dividing them (if the division is exact) are much more efficient in evaluation form. In fact, all the operations in the KZG multiproof above can be done very efficiently in evaluation form, and in practice we never even compute the polynomials in coefficient form when we do this! ## Lagrange polynomials Let's define the Lagrange polynomials $$ \ell_i(X) = \prod_{j \not= i} \frac{X - \omega^j}{\omega^i - \omega^j} $$ For any $x \in {\omega^0, \ldots, \omega^{d-1}}$, $$ \ell_i(x) = \begin{cases} 1 & \text{if $x=\omega^i$}\\ 0 & \text{otherwise} \end{cases} $$ so the Lagrange polynomials can be seen as the "unit vectors" for polynomials in evaluation form. Using these, we can explicitly translate from the evaluation form to the coefficient form: say we're given $(y_0, \ldots, y_{d-1})$ as a polynomial in evaluation form, then the polynomial is $$ f(X) = \sum_{i=0}^{d-1} y_i \ell_i(X) $$ Polynomials in evaluation form are sometimes called "Polynomials in Lagrange basis" because of this. For KZG commitments, we can use another trick: Recall that the $G_1$ setup for KZG to commit to polynomials of degree $<k$ consists of $[s^i]_1, 0\leq i < d$. From these, we can compute $[\ell_i(s)]_1, 0\leq i < d$. Then we can simply compute a polynomial commitment like this: $$ [f(s)]_1 = \sum_{i=0}^{d-1} y_i [\ell_i(s)]_1 $$ There is no need to compute the polynomial in coefficient form to compute its KZG commitment. ## FFT to change between evaluation and coefficient form The Discrete Fourier Transform $u=\mathrm{DFT}(v)$ of a vector $v$ is defined by $$ u_i = \sum_{j=0}^{d-1} v_j \omega^{ij} $$ Note that if we define the polynomial $f(X) = \sum_{j=0}^{k-1} v_j X^j$, then $u_i = f(\omega^i)$, i.e. the DFT computes the values of $f(X)$ on the domain $\omega^i, 0 \leq i < d$. This is why in practice, we will almost always use this particular domain (the roots of unity) because then we can use the DFT to compute the evaluation form from the coefficient form. The inverse, the Inverse Discrete Fourier Transform $v_i = \mathrm{DFT}^{-1}(u_i)$, is given by $$ v_i = \frac{1}{d}\sum_{j=0}^{d-1} u_j \omega^{-ij} $$ Similar to how the DFT computes the evaluations of a polynomial in coefficient form, the inverse DFT computes the coefficients of a polynomial from its evaluations. To summarize: $$ \text{coefficient form} \overset{\mathrm{DFT}}{\underset{\mathrm{DFT}^{-1}}\rightleftarrows} \text{evaluation form} $$ The "Fast Fourier Transform" is a fast algorithm, that can compute the DFT or inverse DFT in only $\frac{d}{2} \log d$ multiplications. A direct implementation of the sum above would take $d^2$ multiplications. This speedup is huge and makes the FFT such a powerful tool. In strict usage, DFT is the generic name for the operation, whereas FFT is an algorithm to implement it (similar to sorting being an operation, whereas quicksort is one possible algorithm to implement that operation). However, colloquially, people very often just speak of FFT even when they mean the operation as well as the algorithm. ## Multiplying and dividing polynomials Let's say we have to polynomials $f(X)$ and $g(X)$ such that the sum of the degrees is less than $k$. Then the product $h(X) = f(X) \cdot g(X)$ is a polynomial of degree less than $k$. If we have the evaluations $f_i = f(\omega^i)$ and $g_i = g(\omega^i)$, then we can easily compute the evaluations of the product: $$ h_i = h(\omega^i) = f(\omega^i) g(\omega^i) = f_i g_i $$ This only needs $d$ multiplications, whereas multiplying in coefficient form needs $O(d^2)$ multiplications. So multiplying two polynomials is much easier in evaluation form. Now lets assume that $g(X)$ divides $f(X)$ exactly, i.e. there is a polynomial $q(X)$ such that $f(X) = g(X) \cdot q(X)$. Then we can find this quotient $q(X)$ in evaluation form $$ q_i = q(\omega^i) = f(\omega^i) / g(\omega^i) = f_i / g_i $$ using only $d$ divisions. Again, using long division, this would be a much more difficult task taking $O(d^2)$ operations in coefficient form. We can use this trick to compute openings for Kate commitments in evaluation form, where we need to compute a polynomial quotient. So we'll use this trick to compute the proofs $\pi$ and $\rho$ above. ## Dividing when one of the points is zero There is only one problem: What if one of the $g_i$ is zero, i.e. $g(X)$ is zero somewhere on our evaluation domain? Note by definition this can only happen if $f_i$ is also zero, otherwise $g(X)$ cannot divide $f(X)$. But if both are zero, then we are left with $q_i = 0/0$ and can't directly compute it in evaluation form. But do we have to go back to coefficient form and use long division? It turns out that there's a trick to avoid this, at least in the case that we care about: Often, $g(X) = X-\omega^m$ is a linear factor. We want to compute $$ q(X) = \frac{f(X)}{g(X)} = \frac{f(X)}{X-\omega^m} = \sum_{i=0}^{d-1} f_i \frac{\ell_i(X)}{X-\omega^m} $$ Now, we introduce the polynomial $A(X) = X^d - 1$. The roots of the polynomial are actually the roots of unity $\omega^i$ because $A(\omega^i) = \omega^{id} - 1 = 1 - 1 = 0$. So we can also write $A(X)$ in another form as $$ A(X) = x^d - 1 = \prod_{i = 0} ^ {d-1} (X-\omega^i) $$ The [formal derivative](https://en.wikipedia.org/wiki/Formal_derivative) of $A$ is given by $$ A'(X) = d x^{d-1} = \sum_{j=0}^{d-1} \prod_{i \not= j}(X-\omega^i) $$ We will need $A'(\omega^i)$, which is easy to compute: $$ A'(\omega^i) = d (\omega^i)^{d-1}= d \omega^{-i} $$ This polynomial is extremely useful because we can write the Lagrange polynomials as $$ \ell_i(X) = \frac{1}{A'(\omega^i)}\frac{A(X)}{X-\omega^i} = \frac{1}{d\omega^{-i}}\frac{A(X)}{X-\omega^i} = \frac{\omega^{i}}{d}\frac{A(X)}{X-\omega^i} $$ so $$ \frac{\ell_i(X)}{X-\omega^m} = \frac{\omega^{i}}{d}\frac{A(X)}{(X-\omega^i)(X-\omega^m)} = \frac{\omega^{i}}{\omega^m}\frac{\ell_m(X)}{X - \omega^i} $$ Now, let's go back to the equation for $q(X)$. The one problem we have if we want to get this in evaluation form is the point $q(\omega^m)$ where we encounter a division by zero; all the other points are easy to compute. But now we can replace $$ q(X) = \sum_{i=0}^{d-1} f_i \frac{\ell_i(X)}{X-\omega^m} = \sum_{i=0}^{d-1} f_i \frac{\omega^{i}}{\omega^m}\frac{\ell_m(X)}{X - \omega^i} $$ Because $\ell_m(\omega^m)=1$, this lets us compute $$ q_m = q(\omega^m) = \sum_{i=0}^{d-1} f_i \frac{\omega^{i}}{\omega^{m}}\frac{1}{\omega^m - \omega^i} = \sum_{i=0}^{k-1} f_i \frac{\omega^{i-m}}{\omega^m - \omega^i} $$ For all $j \not= m$, we can compute directly $$ q_j = q(\omega^j) = \sum_{i=0}^{d-1} f_i \frac{\ell_i(\omega^j)}{\omega^j-\omega^m} = \frac{f_j}{\omega^j-\omega^m} $$ This allows us to efficiently allow all $q_j$ in evaluation form for all $j$, including $j=m$. This trick is necessary to compute $q(X)$ in evaluation form. ## Evaluating a polynomial in evaluation form on a point outside the domain Now there is one thing that we can do with a polynomial in coefficient form, that does not appear to be easily feasible in evaluation form: We can evaluate it at any point. Yes, in evaluation form, we do have the values at the $\omega^i$, so we can evaluate $f(\omega^i)$ by just taking an item from the vector; but surely, to evaluate $f$ at a point $z$ *outside* the domain, we have to first convert to coefficient form? It turns out, it is not necessary. To the rescue comes the so-called barycentric formula. Here is how to derive it using Lagrange interpolation: $$ f(z) = \sum_{i=0}^{d-1} f_i \ell_i(z) = \sum_{i=0}^{d-1} f_i \frac{\omega^i}{d}\frac{A(z)}{z-\omega^i} = \frac{A(z)}{d}\sum_{i=0}^{d-1} f_i \frac{\omega^i}{z-\omega^i}= \frac{z^d-1}{d}\sum_{i=0}^{d-1} f_i \frac{\omega^i}{z-\omega^i} $$ The last part can be computed in just $O(d)$ steps, which makes this formula very useful, for example for computing $g(t)$ and $h(t)$ without transforming into coefficient form.

Import from clipboard

Advanced permission required

Your current role can only read. Ask the system administrator to acquire write and comment permission.

This team is disabled

Sorry, this team is disabled. You can't edit this note.

This note is locked

Sorry, only owner can edit this note.

Reach the limit

Sorry, you've reached the max length this note can be.
Please reduce the content or divide it to more notes, thank you!

Import from Gist

Import from Snippet

or

Export to Snippet

Are you sure?

Do you really want to delete this note?
All users will lost their connection.

Create a note from template

Create a note from template

Oops...
This template is not available.
All
  • All
  • Team
No template found.

Create a template

Delete template

Do you really want to delete this template?

This page need refresh

You have an incompatible client version.
Refresh to update.
New version available!
See releases notes here
Refresh to enjoy new features.
Your user state has changed.
Refresh to load new user state.

Sign in

Sign in via SAML

or

Sign in via GitHub

Help

Documents

Tutorials
YAML Metadata
Slide Example
Book Example

Cheatsheet

Example Syntax
Header # Header
  • Unordered List
- Unordered List
  1. Ordered List
1. Ordered List
  • Todo List
- [ ] Todo List
Blockquote
> Blockquote
Bold font **Bold font**
Italics font *Italics font*
Strikethrough ~~Strikethrough~~
19th 19^th^
H2O H~2~O
Inserted text ++Inserted text++
Marked text ==Marked text==
Link [link text](https:// "title")
Image ![image alt](https:// "title")
Code `Code`
var i = 0;
```javascript
var i = 0;
```
:smile: :smile:
Externals {%youtube youtube_id %}
LaTeX $L^aT_eX$

This is a alert area.

:::info
This is a alert area.
:::

Versions and GitHub Sync

Versions and GitHub Sync

Sign in to link this note to GitHub Learn more
This note is not linked with GitHub Learn more
 
Add badge Pull Push GitHub Link Settings

Version named by    

More Less
  • Edit
  • Delete

Note content is identical to the latest version.
Compare with
    Choose a version
    No search result
    Version not found

Feedback

Submission failed, please try again

Thanks for your support.

On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?

Please give us some advice and help us improve HackMD.

 

Thanks for your feedback

Remove version name

Do you want to remove this version name and description?

Transfer ownership

Transfer to
    Warning: is a public team. If you transfer note to this team, everyone on the web can find and read this note.

      Link with GitHub

      Please authorize HackMD on GitHub

      Please sign in to GitHub and install the HackMD app on your GitHub repo. Learn more

       Sign in to GitHub

      HackMD links with GitHub through a GitHub App. You can choose which repo to install our App.

      Push the note to GitHub Push to GitHub Pull a file from GitHub

       Authorize again
       

      Choose which file to push to

      Select repo
      Refresh Authorize more repos
      Select branch
      Select file
      Select branch
      Choose version(s) to push
      • Save a new version and push
      • Choose from existing versions

      Pull from GitHub

       
      File from GitHub
      File from HackMD

      GitHub Link Settings

      File linked

      Linked by
      File path
      Last synced branch

      Danger Zone

      Unlink
      You will no longer receive notification when GitHub file changes after unlink.

      Syncing

      Push failed

      Push successfully