# Verkle Trees - Proof creation/verification notes
*Update (2023-11-28): this document was created ~2023-05 -- all the ideas are still relevant. I've also worked on a parallelized version in the Go library that you might also find interesting [here](https://github.com/crate-crypto/go-ipa/pull/63).*

This document contains notes about implementation optimizations for Verkle Tree proof generation and verification.

Some of these optimizations are present [in the spec implementation](https://github.com/crate-crypto/verkle-trie-ref), while others aren't since the spec code is meant to optimize to be understandable. We list them here and provide links to the reference implementation and other documents with explanations (if available).

## Proof generation
- Preprocessing
- Collecting polynomials in eval form involves doing `toFr` at each relevant internal node to prove, which means doing inversions.
- [x] Optimization: If you're collecting polynomials of relevant internal nodes recursively, at least batch inverses per node (i.e.: between 1 and 256 Point->Fr transformations per internal node). Do the same on leaf nodes.
- Idea: Note there's no dependency between levels so that you can batch everything in a single batch.
- Idea: The EL pipeline might already serialized the tree. Try caching the already calculating Frs and avoid redoing work altogether. (Might consume extra memory).
- Multiproof
- [x] Fiat-Shamir: We start by adding all `Cs` to the transcript. This requires serializing the points. Probably, you store them in projective form in memory, normalize them (i.e: to affine) in batch mode (i.e: Montgometry trick for $Z$ coordinate). [[go-ipa](https://github.com/crate-crypto/go-ipa/pull/46/files#diff-15732f9d80d142e52a9de146c6be3c65b99fa8c81c28540dcb6d8e2061ce6002R35)]
- [X] Aggregate all polynomials by evaluation domain before starting with any heavy work. This avoids repeated heavy work when you're aggregating many openings (which is usually the case). [[go-ipa](https://github.com/crate-crypto/go-ipa/pull/48)]
- When calculating $g(x)$, we have to do polynomial division on the domain
- [x] Rewrite $q_m$ in terms of $q_j$. [[spec code](https://github.com/crate-crypto/verkle-trie-ref/blob/master/multiproof/quotient.py#L20-L21), [explanation](https://hackmd.io/mJeCRcawTRqr9BooVpHv5g#1-Rewrite-q_m-in-terms-of-q_j)]
- [x] Removing field inversions in $q_j$ [[spec code](https://github.com/crate-crypto/verkle-trie-ref/blob/master/multiproof/quotient.py#L9), [explanation](https://hackmd.io/mJeCRcawTRqr9BooVpHv5g#2-Removing-field-inversions-in-q_j)]
- [x] Leverage precomputed terms when calculating $\frac{A'(x_m)}{A'(x_i)}$ [[spec code](https://github.com/crate-crypto/verkle-trie-ref/blob/master/multiproof/quotient.py#L21), [explanation](https://hackmd.io/mJeCRcawTRqr9BooVpHv5g#3-Precompute-fracAx_mAx_i)].
- [x] When calculating $g_1(x)$, do batch inversion for $\frac{1}{t-z_i}$ terms.
- Inner product argument
- When evaluating outside of the domain step $f(z)= A(z)\sum_{i=0}^{d-1}\frac{f_i}{A'(x_i)(z-x_i)}$:
- [x] Remember that we already have precomputed $\frac{1}{A'(x)}$, use it directly. [[spec code](https://github.com/crate-crypto/verkle-trie-ref/blob/master/polynomial/precomputed_weights.py#L76)]
- [x] We have many $\frac{1}{z-x_i}$, batch those inverse calculations. [[spec code](https://github.com/crate-crypto/verkle-trie-ref/blob/master/polynomial/precomputed_weights.py#L73)]

## Proof verification
- Proof deserialization
- [X] Make sure you use Tonelli-Shanks with precomputed tables [not in spec code, [original impl in Gottfried repo](https://github.com/GottfriedHerold/Bandersnatch/blob/f665f90b64892b9c4c89cff3219e70456bb431e5/bandersnatch/fieldElements/field_element_square_root.go), [port in go-ipa with gnark](https://github.com/crate-crypto/go-ipa/pull/38), [explanation](https://ihagopian.com/posts/tonelli-shanks-with-precomputed-dlog-tables), [perf impact results](https://hackmd.io/@jsign/Bandersnatch-optimized-sqrt-notes)]
- Multiproof
- To calculate $g_2(t)$ (and $E$):
- [x] You'll need $\frac{r^i}{t-z_i}$ terms, batch the denominator inverses [[go-ipa](https://github.com/crate-crypto/go-ipa/pull/42/files)]
- [x] As mentioned for the prover, remember to aggregate polynomials by evaluation point first which will save some work down the road. [[go-ipa](https://github.com/crate-crypto/go-ipa/pull/49)]
- [X] Note that calculating `E` is a MSM. Consider using a MSM algorithm, and not the naive sum of scalar multiplications [[go-ipa](https://github.com/crate-crypto/go-ipa/pull/43/files)].
- Inner product argument
- [X] When evaluating outside the domain step, use the same optimizations mentioned for the prover.
- [X] Only compute basis changes at the end [not in spec code, [EIP code](https://github.com/ethereum/research/blob/master/verkle_trie_eip/ipa_utils.py#L82-L93), [Dankrad's blog post](https://dankradfeist.de/ethereum/2021/07/27/inner-product-arguments.html), [my handwritten "explanation" of folding trick](https://hackmd.io/_uploads/rybHSG343.png), [go-ipa](https://github.com/crate-crypto/go-ipa/pull/41)]
- [X] Do batch inversion for the needed challenges for the basis changes. [[go-ipa](https://github.com/crate-crypto/go-ipa/pull/40/files)]

## Impact

As an example of what kind of speedup you can get from an implementation that can be missing some of these benchmarks, here's some results on `go-ipa`:
- [Benchmark results before some important optimizations](https://gist.github.com/jsign/3ea6d6d23ee691472c48f45732d31799)
- [Benchmark results after all optimizations](https://gist.github.com/jsign/f79f87af09ad3a14f0bfcfc5ba4e8c3e)

As an example, for 16.000 random polynomial openings:

For 16000 polynomials:
        Proving:
                Proof serialization duration: (0.11ms -> 0.11ms)
                Proof creation duration: (664ms -> 271ms [2.45x speedup])
                ...
        Verification:
                Proof deserialization duration: 0.11ms
                Total duration: (1166ms -> 38ms [30x speedup]
                ...

Legend: `(BEFOREms -> AFTERms, [SPEEDUPx])`

The optimized implementation still is single-threaded-ish, and doesn't require extra memory (e.g: precomputed tables).

## Closing
Do you know any other missing trick? [Ping me](https://t.me/ignaciohagopian)!