Goal
Goal is to have another commR directly translated to another curve/proof system.
There are two main approaches in this document:
- Prove in one proof the two different trees using non native arithmetic
- Each proof verify the hash of all leaves using a curve agnostic hash function
- Each proof then do the MT inclusion proof their own way
- Prove in two proofs , each one on each curve, using a binding commitment.
- Goal
- Two Separate Proofs
- 2-proof: BLS12-381 and 377 w/ sha256
- 2-proof: BLS12-381 and 377 w/ blake2
- 2-proof BLS12-381 and 377 w/ Anemoi R1CS
- One Proof solutions
- 1-proof BLS12-381 with Jive/Anemoi on TurboPlonk
- 1-proof BLS12-381 w/ Anemoi R1CS
- 1-proof: BLS12-381 move to Rescue hash
- 1-proofs: Poseidon non native for 381 on 377 field
- ⛔ Option 1: one proof
- 🆗Option 2: Multiple proofs
- 🆗Option 3: Using Uniformity of Testudo
Two Separate Proofs
TLDR:
- One proof that proves on bls12-381 the 3k leaves
- Another proof on another curve that proves the same 3k leaves
- Both proof hash all the leaves at the beginning and compare expected output to make sure these are the same
2-proof: BLS12-381 and 377 w/ sha256
Total Cost: 120M w/ 381 + 120M w/ 377
Too Costly !
Cost of 1 sha256 2-arity: 40k
Cost of 3000 sha256: 120 000 000 (chain)2-proof: BLS12-381 and 377 w/ blake2
Total Cost: 47M w/ 381 + 64M w/ 377
Blake2 used as the hash for the leaves verification. → That means only 1500 evaluations because of the way blake2 works when optimizing the chaining
h' = blake_compression(h, msg) <- msg can be 2 elementsCost for BLS12-381 side
Cost 1 blake2 2-arity: 20k
Commitment to leaves verification: Cost of 1500 blake2: 20k * 1.5k = 30M
Cost of 1 Poseidon 8-arity: 565
Cost of 1 MT path verification: 5650
Cost of 3000 path verification: ~17M
Cost for BLS12-381: 60M + 17M = 47 MCost for BLS12-377 side
Twice as much hashes for input verification = 30M
Twice as much MT path inclusion = 17M * 2 = 34M
Total cost: 64M3mn on current testudo - 40s on batch one
2-proof BLS12-381 and 377 w/ Anemoi R1CS
In this case, Anemoi hash function provides exceptional 95 constraints in R1CS for 2-1 inputs !!
Cost for bls12377 goes down to 40M
Cost of leaves verification = 1.5k * 20k = 30M (blake2)
Cost of ONE MT path inclusion proof (8-arity): 162 * 10 = 1620
Cost of all MT path proofs (x2 because 377) = 1620 * 3000 * 2 = 9.7M
Total cost: 40MOne Proof solutions
TLDR:
- One proof that opens the leaves in current sector MT tree
- Same proof that proves them using another hash function / commitment
1-proof BLS12-381 with Jive/Anemoi on TurboPlonk
TLDR: less than 20M constraints !
Gives a x10 reduction for hashing !
1 8-ary hash constraints = 51
Cost of 1 MT path verification = 510 constraints
COst of 3k path verification = 1.5M constraints
TOTAL COST = 17M + 1.5M = 19M1-proof BLS12-381 w/ Anemoi R1CS
TLDR: 23M , single proof & no more blake2
Cost of ONE MT path inclusion proof (8-arity): 200 * 10 = 2000
Cost of all MT path proofs w/ Anemoi = 2000 * 3000 = 6M
Cost of all MT path proofs w/ Poseidon8 = 17M
Total cost: 23M1-proof: BLS12-381 move to Rescue hash
Based on Jellyfish - Hyperplonk implementation
—> Not worth it (current 16.8M vs 18.7M hypothetically)
Cost of 3-arity Rescue hash on BLS12-381: 331 constraints (plonk)
Number of layers = math.log(2**30,3) = 19
Cost of proving MT path proofs: 331 * 19 * 3000 = 18.7M constraints
Cost of regular Poseidon 8-arity: 565 * 10 * 3000 = 16.8M
NOT WORTH IT1-proofs: Poseidon non native for 381 on 377 field
We want to evaluate the cost of evaluating poseidon non natively on bls12-381 if the proof system uses bls12-377.
The reason of looking at 377 is because Testudo achieves its best tradeoffs and performance on this curve and thus it could bolster the adoption of Testudo as the foundation for a new proof system.
NNA Field Add : 544 constraints
NNA Field Mul : 1221 constraintsWhich gives a total number of constraints for Poseidon to
5850*544+5652*1221 = 10 083 492 5850 * 985 + 5652 * 1872 = 1634279427 constraints only for adding and 127 for mul !
One Poseidon hash evaluation: 5850*27 + 5652*127 = 876024
One MT path = 8.7M
Full 3k evaluations = 26.1B !| Framework | NNA Field | Constraint Field | Operation | Constraints | Notes | nop |
|---|---|---|---|---|---|---|
arkworks | BLS12-381 | BLS12-377 | ADD | 544 | ||
arkworks | BLS12-381 | BLS12-377 | MUL | 1221 | ||
Gnark | BLS12-381 | BLS12-377 | ADD | 985 | ||
Gnark | BLS12-381 | BLS12-377 | MUL | 1872 | ||
gnark/develop | BLS12-381 | BLS12-377 | ADD | 27 | for 10k ADD amortization (x10k for full result) | |
gnark/develop | BLS12-381 | BLS12-377 | MUL | 127 | For 10k MUL amortization |
⛔ Option 1: one proof
From the current estimated cost, it would require only for the part proving the current commR non natively:
876 000 * 30 000 = 26 280 000 000 constraints🆗Option 2: Multiple proofs
Instead of proving all at once, we can actually either
- Create multiple smaller proofs and aggregate them via the natural aggregation mechanism of the new proof system (snarkpack or sangria or else)
- Create smaller proofs incrementally submitting them to the chain until we have reached a high confidence (i.e. we proved 3k inclusion proofs)
For example, with snarkpack, we can easily aggregate 8k proofs. That would mean each indivual proofs is only about 3 285 000 constraints (for the non native part only).
Improvements to Snarkpack can be made to further reduce the cost of onchain verification.
🆗Option 3: Using Uniformity of Testudo
Cost of 1 NNA Hash = 876k
Number of Hash to do for 1 MT path verification = 10
Total cost of one MT Path verification = 8.76M-> The “fast path” of Testudo is only 8.76M.