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.
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 (a) non native arithmetics or (b) two different proofs
- “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.
- Number of leaves to open on the sector: 3000 !
- 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 !
1-proof bls12-381 Plonk w/ Anemoi
20M constraints (plonk)
x10 impr. over Poseidon-8
Separate Proofs w/ Blake2 w/ 377
47M (381) + 64M (377 - 40s)
Separate proofs w/ Blake2 w/ 377 w/ Anemoi
47M (381) + 40M(377)
Curve Agnostic w/ Blake2
22.5M w/ 100 proofs
Curve Agnostic w/ SHA256
36M w/ 100 proofs
Direct Translation w/ Poseidon
26M w/ 1k proofs
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.