# Nethermind - Proof optimization checklist
This is a mirror document to apply the same optimizations I wrote in a [document](https://hackmd.io/@jsign/vkt-proofs-implementation-notes) related to Geth libraries.

## Proof generation
- Multiproof
- [[**Done**](https://github.com/NethermindEth/bandersnatch-sharp/pull/52)] 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)]
- [[**Done**](https://github.com/NethermindEth/bandersnatch-sharp/pull/53)] 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
- [**Pending**] 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)]
- [[**Done**](https://github.com/NethermindEth/bandersnatch-sharp/pull/54)] 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.
- [[**Done**](https://github.com/NethermindEth/bandersnatch-sharp/pull/55)] 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)]