Verkle Trie Library in Noir

This is a PoC (Proof of Contept) implementation of the Verkle Tries.

WIP

Currently in repository is realized cryptography spec necessary for Verkle Tries, however it is not tested and requires further adjustments prior to utilization.

Of such, several optimizations may be made like GLV-endomorphism for faster scalar multiplication and precomputed MSM.

Additionally, it is required to examine field arithmetics, considering Noir backed curve.

Considering that Verkle Tries are made on top of Banderwagon subgroup of the Bandersnatch curve with scalar field being equal to BLS12_381, we shall use latter in the underlaying proving system - also due to the fact that for now we don't have emulation functionality.

Installation

[dependencies]
ipa_multipoint = { tag = "main", git = "https://github.com/distributed-lab/noir-verkle", directory = "crates/ipa-multipoint"}

Packages

IPA-multipoint package is split into six primary crates:

• crs - Common Reference String.
• ecc - Banderwagon prime order subgroup of the Bandersnatch.
• ipa - Inner product argument.
• multipoint - Multipoint proofs.
• polynomial - Barycentric interpolation.
• transcript - Fiat-Shamir protocol.

Reference

Articles

1. Verkle Trees by John Kuzmaul
2. Barycentric Lagrange Interpolation
3. Bandersnatch: a fast elliptic curve built over the BLS12-381 scalar field
4. GLV Decomposition for Multi-Scalar Multiplication (MSM)
5. Understanding The Wagon - From Bandersnatch to Banderwagon
6. Bandersnatch Implementation Notes
7. Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials, 2.2
8. Faster batch forgery identification
9. Inner Product Arguments
10. Proofs for Inner Pairing Products and Applications
11. Weak Fiat-Shamir Attacks on Modern Proof Systems
12. PCS multiproofs using random evaluation
13. Multipoint opening argument

Implementations

• go-verkle
• go-ipa
• rust-verkle
• verkle-trie-ref

License

This project is licensed under the MIT License. See the LICENSE file for details.