# Goal

Goal is to have another commR directly translated to another curve/proof system.

There are two main approaches in this document:

- Prove in
the two different trees using non native arithmetic**one proof** - 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
, each one on each curve, using a binding commitment.**two proofs**

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

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

**⛔**

**Using arkworks 3.0:**

**10M constraints for one Poseidon evaluation**```
NNA Field Add : 544 constraints
NNA Field Mul : 1221 constraints
```

Which gives a total number of constraints for Poseidon to

`5850*544+5652*1221 = 10 083 492 `

**⛔**

**Using gnark 0.8:**

**16.2M constraints**`5850 * 985 + 5652 * 1872 = 16342794`

**Using gnark/develop:**😐

**876k constraints MAX - it will go down !**

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