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 elements

Cost 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 M

Cost for BLS12-377 side

Twice as much hashes for input verification = 30M
Twice as much MT path inclusion = 17M * 2 = 34M
Total cost: 64M

3mn 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: 40M

One 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 !

Embed GitHub

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 = 19M

1-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: 23M

1-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 IT

1-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.

⛔ 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

1. Create multiple smaller proofs and aggregate them via the natural aggregation mechanism of the new proof system (snarkpack or sangria or else)
2. 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.

https://blog.celer.network/2023/03/01/the-pantheon-of-zero-knowledge-proof-development-frameworks/