Goal
We want to move a sector from one proof and specific curve to another proof system and/or curve. This would allow us to rely on the effort from the ecosystem to push for better and better SNARKs and enables faster development of new features on Filecoin.
Technically: The SP should be able to prove that he has two sectors, one encoded with former curve A and the new one encoded with new curve B that encodes the same data. To do this, we ask him to reveal randomly X positions on both sectors (his commR) and verify that the leaf, the actual encoded data, is the same on both.
Strategies
These are the potential strategies currently being worked on:
- Direct translation: Translate directly from the Poseidon hashing in one curve to the poseidon hashing in another curve using non native arithmetics.
- “Curve agnostic hash”: Take the commR in Poseidon, make a translation proof on sha256 / blake2 etc. Then any curve / proof system can directly translate from this hash function to the “snark friendly hash function” they want to use for this proof system.
- New Vector Commitment: Changing proof system and curves also allows us to change vector commitment at the same time ! Depending on which VC we use the translation cost may be acceptable !
Pros: A SP can directly take advantage of another proof system, no need for change on current proof system
Cons: costly + translation is only useful for one other proof system/curve, not for all
Pros: Once translation is done for a “curve agnostic” hash function, then it can be re-used for multiple proofs system → multitude of proof systems/curve available at once
Cons: extra cost for SP that needs to do this intermediate step, “2 proofs” instead of 1 per sector now.
Challenges:
- Bit Sizes: challenge is to embed the data inside another scalar field of the other curve. We need 255 bits however the major curves out there are 252 or 254 bits !
- Non Native / Common inputs: We need to make sure the same data are input to both proof system , there needs to be a “link” between the two !
Overview
Constraint Costs | Using SnarkPack | ||
Separate Proofs w/ Blake2 w/ 377 | 47M (381) + 64M (377 - 40s) | ||
Direct Translation w/ Poseidon | 26 B | 26M w/ 1k proofs | |
Curve Agnostic w/ SHA256 | 3.6 B | 36M w/ 100 proofs | |
Curve Agnostic w/ Blake2 | 2.25 B | 22.5M w/ 100 proofs | |
Separate proofs w/ Blake2 w/ 377 w/ Anemoi | 47M (381) + 40M(377) |
Ongoing exploration code repository
Cost of Poseidon hashing in Filecoin
Using Poseidon Natively:
8-arity Hash = 565 constraints
Detailling all additions / multiplications:
The following describes the number of field additions and multiplications one needs to do to evaluate a poseidon with 8 arity without optimizations.
Field additions = 5850
Field multiplications = 5652
First general formula
// "Width" (or "capacity").
t = arity + 1
// Number of full and partial rounds.
rf, fp = lookup round numbers for `t` in table:
https://github.com/lurk-lab/neptune/blob/master/parameters/round_numbers.txt
// Total number of rounds.
r = rf + rp
// The number of field operations required to an sbox: x^5 = (x^2)^2 * x.
muls_per_sbox = 3
// Number of sbox field multiplications per full/partial round.
sbox_muls_per_rf = t * muls_per_sbox
sbox_muls_per_rp = muls_per_sbox
// Number of field additions per round for adding round constants into `state`.
rc_adds_per_round = t
// Number of field operations per matrix-vector multiplication (of MDS matrix with `state` vector).
mds_adds_per_round = t^2
mds_muls_per_round = t^2
// Total number of field operation:
total_adds = r * (rc_adds_per_round + mds_adds_per_round)
total_muls = r * mds_muls_per_round + rf * sbox_muls_per_rf + rp * sbox_muls_per_rp
Then applied to Filecoin’s case
t = arity + 1 = 9
rf, rp = 8, 57
r = rf + rp = 65
sbox_muls_per_rf = 3 * t = 27
sbox_muls_per_rp = 3
rc_adds_per_round = t = 9
mds_mixing_adds_per_round, mds_mixing_muls_per_round = t^2 = 81
total_adds = 65 * (9 + 81) = 5850
total_muls = 65 * 81 + 8 * 27 + 57 * 3 = 5652
Cost of translation proof
One needs to realize on the order of 3000 merkle tree inclusion proofs on both curves.
Each inclusion proof on the current Filecoin system (curve and setting) is about 10 * 8-arity Poseidon hashes.
In total, we can say a translation proof requires at least evaluating 30k 8-arity Poseidon hashes + the cost of 3000 “inclusion proof” on the other proof system.
Milestones and roadmap
Name | Status | Quarter | DRI | Date | OKR | 🎒 Team backlog ㊙️ |
---|---|---|---|---|---|---|
Not started | 2023Q3 | Alex North | ||||
Not started | ||||||
Not started | ||||||
Not started | ||||||
Not started | ||||||
Not started | ||||||
Not started | ||||||
Not started | ||||||
Not started | ||||||
Not started | ||||||
Not started | ||||||
Not started | ||||||
Not started | ||||||
Not started | ||||||
Not started | 2023Q4 | August 1, 2023 → December 29, 2023 | ||||
Not started | 2023Q2 | June 5, 2023 → June 16, 2023 | ||||
🔵 | 2023Q3 | October 1, 2022 → June 19, 2023 | ||||
🔵 | 2023Q3 | Alex North | ||||
🔵 | ||||||
🔵 | ||||||
🔵 | ||||||
🔵 | ||||||
🔵 | ||||||
🔵 | ||||||
🔵 | 2023Q4 | |||||
🔵 | 2023Q4 | |||||
🔵 | 2023Q3 | |||||
🔵 | 2023Q3 | |||||
🔵 | 2023Q3 | Alex North | ||||
🔵 | 2023Q3 | June 12, 2023 → July 25, 2023 | ||||
🔵 | 2023Q2 | May 15, 2023 → June 6, 2023 | ||||
🔵 | 2023Q2 | May 29, 2023 → June 17, 2023 | ||||
🔵 | 2023Q3 | May 15, 2023 → June 29, 2023 | ||||
🔵 | 2023Q3 | May 15, 2023 → June 29, 2023 | ||||
🔵 | 2023Q2 | March 15, 2023 → June 15, 2023 | ||||
🔵 | 2023Q3 | Alex North | ||||
🔵 | 2023Q3 | Alex North | ||||
🟡 | 2023Q4 | Alex North | ||||
🟡 | 2023Q2 | Alex North | ||||
🟡 | 2023Q4 | May 8, 2023 → October 31, 2023 | ||||
🟣 | 2022Q3 | |||||
🟣 | 2023Q3 | May 1, 2023 → June 30, 2023 | ||||
✅ | 2023Q1 | February 20, 2023 → February 24, 2023 | ||||
✅ | 2023Q2 | |||||
✅ | 2023Q1 | February 27, 2023 → March 10, 2023 | ||||
✅ | 2023Q1 | February 20, 2023 → February 24, 2023 | ||||
✅ | ||||||
✅ | 2022Q4 | March 19, 2023 → March 19, 2023 | ||||
✅ | 2023Q2 | February 12, 2023 → March 24, 2023 | ||||
✅ | 2023Q1 | February 12, 2023 → March 17, 2023 | ||||
✅ | 2022Q4 | |||||
✅ | 2023Q1 | Alex North | ||||
✅ | 2023Q2 | |||||
✅ | 2023Q1 | March 31, 2023 → April 7, 2023 | ||||
✅ | 2023Q1 | February 10, 2023 | ||||
✅ | 2023Q2 | March 24, 2023 → June 30, 2023 | ||||
✅ | 2022Q4 | October 1, 2022 → December 22, 2022 | ||||
✅ | 2023Q1 | March 20, 2023 → April 1, 2023 | ||||
✅ | 2023Q2 | May 1, 2023 → June 12, 2023 | ||||
✅ | 2023Q2 | April 3, 2023 → May 1, 2023 | ||||
✅ | 2023Q2 | February 1, 2023 → May 22, 2023 | ||||
✅ | 2023Q2 | Alex North | ||||
✅ | 2023Q2 | Alex North | ||||
✅ | 2023Q3 | March 20, 2023 → June 30, 2023 | ||||
✅ | 2023Q2 | Deleted User | May 8, 2023 → June 9, 2023 | |||
✅ | 2023Q2 | Deleted User | May 2, 2023 → June 2, 2023 | |||
✅ | 2023Q2 | Deleted User | May 29, 2023 → June 5, 2023 | |||
✅ | 2023Q2 | May 29, 2023 → June 2, 2023 | ||||
✅ | 2023Q2 | Alex North | ||||
✅ | 2023Q2 | Alex North | April 12, 2023 → May 20, 2023 | |||
✅ | 2023Q2 | April 10, 2023 → May 1, 2023 | ||||
✅ | 2023Q2 | May 8, 2023 → June 30, 2023 | ||||
✅ | 2023Q2 | April 3, 2023 | ||||
✅ | 2023Q2 | |||||
✅ | 2023Q2 | April 10, 2023 → June 19, 2023 | ||||
✅ | 2023Q1 | January 10, 2023 → March 15, 2023 | ||||
✅ | 2023Q1 | Alex North | ||||
✅ | 2023Q2 | March 31, 2023 | ||||
✅ | 2023Q1 | Alex North | ||||
✅ | 2023Q1 | Alex North | ||||
✅ | 2023Q1 | Alex North | May 17, 2023 → May 24, 2023 | |||
✅ | 2023Q2 | |||||
✅ | 2023Q2 | |||||
✅ | 2023Q2 | February 27, 2023 → March 10, 2023 | ||||
✅ | 2023Q2 | February 27, 2023 → March 10, 2023 | ||||
✅ | February 27, 2023 → March 3, 2023 | |||||
✅ | 2023Q2 | Alex North | March 19, 2023 → May 31, 2023 | |||
✅ | 2023Q1 | February 20, 2023 → February 24, 2023 | ||||
✅ | 2023Q1 | |||||
✅ | 2023Q1 | February 13, 2023 → February 17, 2023 | ||||
✅ | 2023Q2 | |||||
✅ | 2023Q1 | Alex North | March 27, 2023 → April 28, 2023 | |||
✅ | 2023Q2 | March 24, 2023 → March 31, 2023 | ||||
✅ | February 13, 2023 → February 24, 2023 | |||||
🔴 | 2023Q1 | |||||
🔴 | 2023Q2 | |||||
🔴 | 2023Q1 | |||||
🔴 | 2023Q2 | Alex North | March 17, 2023 → June 30, 2023 | |||
🔴 | 2023Q2 | |||||
🔴 | 2023Q2 |
Name | Status | Quarter | DRI | Date | OKR | 🎒 Team backlog ㊙️ |
---|---|---|---|---|---|---|
Not started | ||||||
Not started | ||||||
🔵 | 2023Q3 | April 1, 2023 → June 30, 2023 | ||||
🔵 | 2023Q3 | March 1, 2023 → September 30, 2023 | ||||
🔵 | 2023Q3 | April 17, 2023 → May 26, 2023 | ||||
🔵 | 2023Q3 | September 4, 2023 → October 3, 2023 | ||||
🔵 | 2023Q3 | June 1, 2023 → October 31, 2023 | ||||
🔵 | 2023Q3 | April 1, 2023 → October 31, 2023 | ||||
🔵 | ||||||
🔵 | 2023Q3 | |||||
🔵 | 2023Q2 | Deleted User | May 30, 2023 → July 31, 2023 | |||
🔵 | 2023Q3 | May 15, 2023 → July 31, 2023 | ||||
🔵 | 2023Q3 | July 23, 2023 → October 15, 2023 | ||||
🟡 | September 25, 2023 → October 5, 2023 | |||||
✅ | 2022Q4 | Deleted User | ||||
✅ | 2022Q4 | Deleted User | ||||
✅ | 2022Q4 | Deleted User | ||||
✅ | 2023Q1 | Deleted User | ||||
✅ | 2023Q2 | Deleted User | March 1, 2023 → June 19, 2023 | |||
✅ | 2023Q1 | February 28, 2023 | ||||
✅ | 2023Q1 | February 28, 2023 | ||||
✅ | 2023Q2 | Deleted User | February 28, 2023 | |||
✅ | 2022Q4 | |||||
✅ | 2022Q4 | |||||
✅ | 2022Q3 | |||||
✅ | 2023Q2 | May 8, 2023 → May 26, 2023 | ||||
✅ | 2023Q2 | Deleted User | ||||
✅ | 2023Q1 | Deleted User | ||||
✅ | 2022Q2 | |||||
✅ | 2022Q2 | |||||
✅ | 2022Q3 | |||||
✅ | 2023Q1 | Deleted User | February 27, 2023 → March 27, 2023 | |||
✅ | 2023Q3 | Deleted User | June 5, 2023 → July 21, 2023 | |||
✅ | 2023Q2 | Deleted User | June 5, 2023 → July 6, 2023 | |||
✅ | 2023Q2 | June 14, 2023 → July 6, 2023 | ||||
✅ | 2023Q2 | May 22, 2023 → August 4, 2023 | ||||
✅ | 2023Q2 | May 29, 2023 → June 7, 2023 | ||||
✅ | 2023Q2 | Deleted User | April 24, 2023 → May 10, 2023 | |||
✅ | 2023Q2 | Deleted User | April 24, 2023 → May 10, 2023 | |||
✅ | 2023Q2 | Deleted User | March 27, 2023 → May 31, 2023 | |||
✅ | 2023Q2 | Deleted User | March 26, 2023 → April 7, 2023 | |||
✅ | 2022Q3 | |||||
✅ | 2023Q1 | February 24, 2023 | ||||
✅ | 2023Q2 | Deleted User | ||||
🔴 | 2023Q1 | Deleted User | ||||
🔴 | 2023Q2 | Deleted User | ||||
🔴 | 2023Q3 | Deleted User | ||||
🔴 | 2023Q2 | Deleted User | ||||
🔴 | 2023Q2 | Deleted User | ||||
🔴 | 2023Q3 | Deleted User | ||||
🔴 | 2023Q4 | August 31, 2023 | ||||
🔴 | 2023Q4 | September 30, 2023 | ||||
🔴 | May 31, 2023 | |||||
🔴 | May 31, 2023 | |||||
🔴 | June 30, 2023 | |||||
🔴 | 2023Q1 | March 31, 2023 | ||||
🔴 | 2023Q1 | March 31, 2023 | ||||
🔴 | 2023Q2 | April 30, 2023 | ||||
🔴 | 2023Q2 | June 30, 2023 | ||||
🔴 | 2023Q2 | May 31, 2023 | ||||
🔴 | 2023Q2 | Deleted User | March 31, 2023 | |||
🔴 | 2023Q1 | January 31, 2023 | ||||
🔴 | 2023Q2 | |||||
🔴 | 2023Q4 | |||||
🔴 | 2023Q4 | |||||
🔴 | 2023Q4 | |||||
🔴 | 2022Q4 | |||||
🔴 | 2022Q4 | |||||
🔴 | 2023Q1 | |||||
🔴 | 2023Q2 | |||||
🔴 | 2023Q4 | |||||
🔴 | 2023Q4 | |||||
🔴 | 2022Q4 | |||||
🔴 | 2023Q2 | Deleted User | March 24, 2023 → May 30, 2023 | |||
🔴 | Deleted User | |||||
🔴 | 2023Q3 | May 20, 2023 → June 30, 2023 | ||||
🔴 | 2023Q2 | Deleted User | ||||
🔴 | 2022Q3 | |||||
🔴 | 2023Q2 | |||||
🔴 | 2023Q1 | March 13, 2023 → March 13, 2023 | ||||
🔴 | 2023Q1 | February 17, 2023 |
Name | Status | Quarter | DRI | Date | OKR | 🎒 Team backlog ㊙️ |
---|---|---|---|---|---|---|
Not started | 2023Q2 | Deleted User | ||||
Not started | 2023Q2 | Deleted User | ||||
Not started | ||||||
Not started | 2023Q2 | Deleted User | ||||
Not started | 2023Q2 | Deleted User | ||||
Not started | 2023Q2 | Deleted User | ||||
Not started | 2023Q2 | Deleted User | ||||
Not started | 2023Q2 | Deleted User | ||||
🔵 | 2023Q2 | Jonathan Easterman | ||||
🔵 | 2023Q2 | Deleted User | ||||
🔵 | 2023Q1 | Deleted User | February 28, 2023 → February 28, 2023 | |||
🔵 | 2023Q1 | Deleted User | ||||
🔵 | 2023Q1 | Deleted User | ||||
🔵 | 2023Q1 | Jonathan Easterman | ||||
🟡 | 2023Q2 | Deleted User | ||||
🟡 | 2023Q2 | Deleted User | ||||
✅ | 2022Q3 | Deleted User | ||||
✅ | 2022Q4 | Deleted User | ||||
✅ | 2023Q1 | Deleted User | ||||
✅ | 2023Q1 | Deleted User | ||||
✅ | 2022Q4 | |||||
✅ | 2022Q4 | Deleted User | ||||
✅ | 2023Q1 | Deleted User | ||||
✅ | 2023Q1 | Deleted User | February 15, 2023 → February 15, 2023 | |||
✅ | 2023Q1 | Jonathan Easterman | ||||
✅ | 2023Q1 | Deleted User | ||||
✅ | ||||||
✅ | ||||||
✅ | ||||||
✅ | ||||||
✅ | ||||||
✅ | 2023Q1 | Deleted User | ||||
✅ | ||||||
✅ | 2023Q2 | Deleted User | ||||
🔴 | 2022Q4 | Deleted User | ||||
🔴 | 2023Q2 | Deleted User |