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 constraintsDetailling 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_rpThen 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 = 5652Cost 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
‣
📖 Research Enablers
‣
🔮 Protocol Opportunities
| Name | Status | Quarter | DRI | Date | OKR | 🎒 Team backlog ㊙️ |
|---|---|---|---|---|---|---|
Planning session to understand timeline | Not started | 2023Q1 |  | |||
Model the qap pricing and characterise where Filecoin consensus security comes from; | ⚪️ | 2023Q2 |  | May 8, 2023 → June 10, 2023 | ||
Design & analysis for consensus changes for interop | Not started | 2023Q3 | Alex North | |||
Storage fees | Not started | 2023Q3 | Alex North | |||
New miner APIs for onboarding (w/ Free CommD) | Not started | 2023Q3 | Alex North | |||
Report about consensus security | Not started | 2023Q2 | | May 28, 2023 → June 10, 2023 | ||
Documentation | Not started | 2023Q2 | | |||
Deploy PoRep safety mechanism to Filecoin | Not started | 2023Q2 | Alex North | |||
🔵 | 2023Q2 | | ||||
🔵 | 2023Q2 | | October 1, 2022 → June 19, 2023 | |||
🔵 | 2023Q2 | | March 24, 2023 → June 30, 2023 | |||
Pledge Collateral Shortfall | 🔵 | 2023Q2 | Alex North | March 17, 2023 → June 30, 2023 | ||
(security) Filecoin Protocol Review | 🔵 | 2023Q2 | | March 6, 2023 → June 10, 2023 | ||
🔵 | 2023Q2 |  | March 20, 2023 → June 12, 2023 | |||
Report about model and findings | 🔵 | 2023Q2 | | May 1, 2023 → June 12, 2023 | ||
Data on-boarding pipeline | 🔵 | 2023Q2 | | February 1, 2023 → June 14, 2023 | ||
Identify opportunities | 🔵 | 2023Q1 | | February 1, 2023 → March 31, 2023 | ||
Enabling programmable storage applications | 🔵 | 2023Q2 | Alex North | |||
🔵 | 2023Q3 | | May 15, 2023 → June 29, 2023 | |||
DagHouse integration | 🔵 | 2023Q2 | | March 15, 2023 → June 15, 2023 | ||
(ex)Estuary integration | 🔵 | 2023Q2 | | May 29, 2023 → June 2, 2023 | ||
Data collateral without the built-in market | 🔵 | 2023Q2 | Alex North | |||
Technical Report - “Proof of Useful Space in Filecoin” | 🔵 | 2023Q2 | | June 25, 2023 | ||
Scaling FIL+ VC Allocation | 🔵 | 2023Q3 | nikkolasg g | |||
🔵 | 2023Q4 | | May 8, 2023 → October 31, 2023 | |||
Synthetic PoRep is ready to be deployed | 🔵 | 2023Q2 | | May 8, 2023 → June 30, 2023 | ||
Publish FIP-0047 replacement | 🔵 | 2023Q2 | | April 10, 2023 → June 19, 2023 | ||
FRC merged (waiting on Kaitlyn to assign number and merge) | 🔵 | | February 27, 2023 → March 3, 2023 | |||
🟡 | 2023Q4 | Alex North | ||||
Background research on consensus/snapshot/finality options | 🟡 | 2023Q2 | Alex North | |||
Create the FIP for SnapDeal v2 | 🟡 | 2023Q2 | | April 2, 2023 | ||
Implement it (MVP) | ✅ | 2023Q1 | | February 20, 2023 → February 24, 2023 | ||
Integration with existing libraries | ✅ | 2023Q2 | | |||
User Friendly API | ✅ | 2023Q1 | | February 27, 2023 → March 10, 2023 | ||
First prototype for inclusion proofs during computation of CommP | ✅ | 2023Q1 | | February 20, 2023 → February 24, 2023 | ||
Kuba will complete the two sections (security and design reasoning) | ✅ | | ||||
Commitment Scheme format agreement | ✅ | 2022Q4 | | March 19, 2023 → March 19, 2023 | ||
Software for generation of data segments inclusion proof | ✅ | 2023Q2 | | February 12, 2023 → March 24, 2023 | ||
Support for verifying data segment inclusion proofs on-chain | ✅ | 2023Q1 | | February 12, 2023 → March 17, 2023 | ||
Built-in actors API for user-programmed actors | ✅ | 2022Q4 | | |||
(security) Short term fix for Cron | ✅ | 2023Q1 | Alex North | |||
FIP for Synthetic PoRep | ✅ | 2023Q1 | | March 31, 2023 → April 7, 2023 | ||
Draft ideas to make SnapDeal cheaper | ✅ | 2023Q1 | | February 10, 2023 | ||
FIP-0047 and code are ready | ✅ | 2022Q4 | | October 1, 2022 → December 22, 2022 | ||
Create the model for cost/profit to compare CC sector upgrade with deal sector strategy | ✅ | 2023Q1 | | March 20, 2023 → April 1, 2023 | ||
Gather initial feedback about the design for deals larger than sectors | ✅ | 2023Q2 | | April 3, 2023 → May 1, 2023 | ||
✅ | 2023Q2 | | ||||
Publish specs for public discussion | ✅ | 2023Q2 | Alex North | April 12, 2023 → May 20, 2023 | ||
Implement the model | ✅ | 2023Q2 | | April 10, 2023 → May 1, 2023 | ||
Obtain cost estimation for the different solutions | ✅ | 2023Q2 | | April 3, 2023 | ||
Figure out design to avoid FIP-0047 after all | ✅ | 2023Q1 | | January 10, 2023 → March 15, 2023 | ||
Code | ✅ | 2023Q1 | Alex North | |||
Gather initial feedback from SPs | ✅ | 2023Q2 | | March 31, 2023 | ||
✅ | 2023Q2 | | March 20, 2023 → April 15, 2023 | |||
✅ | 2023Q2 | | March 6, 2023 → March 31, 2023 | |||
Short-term FIP is shipped | ✅ | 2023Q1 | Alex North | |||
Short-term FIP is in the public | ✅ | 2023Q1 | Alex North | |||
Gather initial feedback from SP | ✅ | 2023Q1 | Alex North | May 17, 2023 → May 24, 2023 | ||
Resolve int overflow TODOs | ✅ | 2023Q2 | | |||
Export Format | ✅ | 2023Q2 | | |||
Storage Format | ✅ | 2023Q2 | | February 27, 2023 → March 10, 2023 | ||
Testing | ✅ | 2023Q2 | | February 27, 2023 → March 10, 2023 | ||
Find parameters and alternative proposals and sync with CEL | ✅ | 2023Q2 | Alex North | March 19, 2023 → May 31, 2023 | ||
Generate test vectors for solidity implementation | ✅ | 2023Q1 | | February 20, 2023 → February 24, 2023 | ||
Lib and docs | ✅ | 2023Q1 | ||||
Decoder for boost | ✅ | 2023Q1 | | February 13, 2023 → February 17, 2023 | ||
Negative tests and test vectors | ✅ | 2023Q2 | | |||
Draft a new concrete proposal w/ analysis of impact | ✅ | 2023Q1 | Alex North | March 27, 2023 → April 28, 2023 | ||
Synthetic PoRep shipping effort | ✅ | 2023Q2 | | March 24, 2023 → March 31, 2023 | ||
FRC is reviewed and approved (continuing with minor edits and chasing people) | ✅ | | February 13, 2023 → February 24, 2023 | |||
Data Prepapers API Standard | 🔴 | 2023Q1 | | |||
SubPieceCID Registry smart contract with Merkle trees verification | 🔴 | 2023Q2 | | |||
FIP for Deal Pre-activation (based on ad-hoc collateral) | 🔴 | 2023Q2 | | |||
Repeatedly updatable storage ("Re-snap") | 🔴 | 2023Q2 | | |||
🔴 | 2023Q2 | | March 31, 2023 | |||
(advising) 🍝 FilFil: PeSto and Filecoin Archive | 🔴 | 2023Q2 | | March 31, 2023 |
‣
🏗️ Product Builders