Has a bug in proof generation which made proof invalid
Has a bug in proof verification which accepted those proof
Was lacking test coverage to highlight those bugs
Multiproofs were incorrect due to 1 and 2
This refactoring may fix 1 and 2, however at the moment only if run in AddressSanitizer. If not for some reason verification fails.
Hence this refactoring improves structure and lay out groundwork for addressing the bugs once and for all but does not improve or degrade compared to past implementation.
The files constantine/ethereum_verkle_primitives.nim and constantine/ethereum_verkle_trees.nim have been deleted and replaced by constantine/ethereum_verkle_ipa.nim
The final public API for Eth Verkle IPA still needs to be implemented. It will be similar to the KZG one and will expose only what's necessary and not Constantine's internals.
However before that #396 must be fixed
Highlight of changes:
reimplemented eth-verkle-ipa:
Structures like array[N, Field] which are 256x32 bytes = 8kB are now on heap.
No more seq usage or Nim allocs to ensure no exceptions and no need to call NimMain when using Constantine as a library
exported short names like Bytes/EC_P / EC_P_Aff cause confusion if library is used for many purposes, for example BN254, BLS12-381 and Banderwagon curves and should be private to a module or left to the caller.
Use opening challenges sparsity in multiproof to minimize memory allocation.
Thorough documentation of the protocol
ipa_verify should be significantly faster than before as a MSM is used instead of ~10 individual scalar mul. The change of basis computation is also linear in domain size instead of being ½ n log₂ n.
Use of affine coordinates where it make senses and avoiding redundant affine transformation (for example ingesting in a transcript requires affine)
Avoid several copies and intermediate values.
Transcripts now have a cryptographic sponge with duplex construction API:
Specified the order of arguments for Constantine and change KZG to follow spec. This only affects internal KZG backend. The Ethereum-flavored KZG follows c-kzg-4844 order of arguments, hence no impact on C/Go/Rust.
common getQuotientPoly between KZG and IPA
MSM benchmarks now compare to vartime scalar mul as well
This PR is a followup to #392. Unfortunately this PR has become the biggest PR ever and a part 3 is needed.
An important background to this PR is https://github.com/mratsim/constantine/issues/396.
The previous IPA implementation:
This refactoring may fix 1 and 2, however at the moment only if run in AddressSanitizer. If not for some reason verification fails. Hence this refactoring improves structure and lay out groundwork for addressing the bugs once and for all but does not improve or degrade compared to past implementation.
The files
constantine/ethereum_verkle_primitives.nimandconstantine/ethereum_verkle_trees.nimhave been deleted and replaced byconstantine/ethereum_verkle_ipa.nimThe final public API for Eth Verkle IPA still needs to be implemented. It will be similar to the KZG one and will expose only what's necessary and not Constantine's internals.
However before that #396 must be fixed
Highlight of changes:
array[N, Field]which are 256x32 bytes = 8kB are now on heap.Bytes/EC_P/EC_P_Affcause confusion if library is used for many purposes, for example BN254, BLS12-381 and Banderwagon curves and should be private to a module or left to the caller.ipa_verifyshould be significantly faster than before as a MSM is used instead of ~10 individual scalar mul. The change of basis computation is also linear in domain size instead of being ½ n log₂ n.