[crypto] Verkle tree commitments

[irakliyk]

Currently, the only commitment scheme supported by Winterfell is Merkle trees. We should investigate adding an additional commitment scheme: Verkle tree.

By using Verkle trees we could reduce proof sizes significantly (by like a factor of 6x - 8x) while giving up only post-quantum security. The big question is how would it affect proof generation time (e.g. how long it would take to construct a Verkle tree with 1M nodes?). Also, for performance and other reasons, we should probably use IPA-based Verkle trees (as opposed to KZG-based ones).

If the performance is acceptable, we should add Verkle tree commitments as one of dynamically configurable parameters - e.g. commitment_scheme with the type looking something like this:

pub enum CommitmentScheme {
    MerkleTree,
    VerkleTree,
}

Some references on Verkle trees:

• Verkle trees by Vitalik Buterin
• PCS multiproofs using random evaluation by Dankrad Feist
• rust-verkle by Kev Aundray

[Pratyush]

I'd expect IPA-based Verkle trees to have worse proving times and larger proof size than KZG10-based ones. The only benefit is avoiding a trusted setup.

To achieve faster proving while still compressing proof sizes, you could also consider a hybrid of Merkle and Verkle trees.

[kchalkias]

I'm working on this, there will soon be updates re KZG10 PolyCommitment trees with a reusable minimal trusted setup CRS consisting of 1024-8192 powers of tau elements. That will allow browser and mobile participation to the trusted setup and then it could be used elsewhere too (not only as a Winterfell mode).