Luca @Kubuxu @Luca @ @Nicola
- Problem space
- Non Interactive PoRep: Merging PreCommit and ProveCommit in a unique step via Fiat Shamir Transformation
- Why do we currently need interactive PoRep?
- Ideas
- (1) Rational Fiat Shamir
- (2) 80 bits of Security + Proofs Aggregation via SnarkPack
- (3) Synthetic PoRep: Commit to non interactive challenges and verify a subset of them to grant ⁍ soundness
- Interactive Challenge Verification
Problem space
Mining Experience: with the current interactive PoRep protocol (PreCommit + ProveCommit) SPs need to keep a buffer of 10 layers between PreCommit and ProveCommit. Here we aim to remove this need. We identify two different directions:
- Make PoRep non-interactive: this would remove the need to submit PreCommit and would allow to have a unique message for proving new sectors (only ProveCommit would be needed). Moreover, the removal of PreCommit would also remove the need for keeping around 11 layers for the window of time that starts at PreCommit and lasts until PreCommit.
- Make PoRep Synthetic: Non interactively generate challenges for 80 bits of security, commit to them, and later on, interactively, show a subset of them keeping around vanilla proofs only (aka: merkle tree paths), in order to get soundness without need of keeping the whole graph.
Non Interactive PoRep: Merging PreCommit and ProveCommit in a unique step via Fiat Shamir Transformation
The aim of this line of work is to get rid of the need of both pre-commit and prove-commit merging the two steps into a unique one.
Having such an improvement is important (at least) under two different points of view
- Mining Experience: adding sectors to the network results in a lighter process
- Exponential Network Growth: having a non-interactive PoRep mechanism would be beneficial for network onboarding.
Why do we currently need interactive PoRep?
Currently, PoRep phase has 10 bits of security. This means that a malicious adversary can cheat a PoRep on a sector with probability lower or equal than .
This is due to the fact that proving PoRep in a Snark is expensive: achieving 10 bits of security translates in 10 snarks proofs per PoRep per sector, which at the moments needs go onchain. We could get around onchain footprint using SnarkPack but we would still have a considerable proving overhead.
In practice, 10 bits of security are not enough to use Fiat-Shamir heuristic and make PoRep non interactive. Indeed, roughly speaking a non interactive PoRep would work as follows:
- SP computes a Replica R
- SP uses CommR to locally generate a seed via an hash function
- SP uses the seed to compute challenges over which he has to produce a proof that is posted onchain
Since the challenge generation procedure is done locally, a malicious miner could cheat trying different seeds (and so grinding on different sets of challenges) until he finds a set of challenges he can answer.
Having 10 bits of security means that, on expectation, a cheating adversary could misbehave during PoRep generation (for example by introducing more incorrect labels than he is allowed to) and find such a set of challenges in (~1000) attempts.
Note that this is particularly bad in our case since
- PoRep is a one time process: once the adversary passes that step, he could cheat on that sector for its whole lifetime
- With attempt we do not (unfortunately) mean sealing attempts. Indeed, a miner could try different seeds by simply modifying R (by flipping a simple bit, hoping not to be challenged there) and so modifying CommR and the corresponding seed.
The theoretical recommendation for using Fiat-Shamir heuristic is at least 80 bits of security (or even 128), which translates to 8x the number of challenges we have today per PoRep (1408 per layer instead of the current 176), resulting in 8x the number of snarks per PoRep. These numbers are impractical at the moment given the current snarks due to proving overhead.
Ideas
(1) Rational Fiat Shamir
One way to possibly overcome the need of 80 bits of security could be to rely on rationality: we could find a tradeoff between minimal cost of the number of attempts the adversary is required to perform in order to cheat with probability 1 (on expectation) and the reward they are earning during the sector lifetime. Ideally, is the two amounts are close (or equal) not cheating would not be a rational strategy for the miner.
On this front, the good thing is that we already use a rational model for WindowPoSt. Moreover, properly modeling such an idea for the FIat Shamir Heuristic could potentially be an interesting research result (in the framework of the so-called rational proofs).
On the other hand, this analysis would require significant effort, and there are uncertainties (for instance, costs are in $ while rewards are in FIL, which make the comparison not straightforward without making any price prediction/setting some lower bound on the value of FIL).
For all these reasons, at the moment this is not the main option
(2) 80 bits of Security + Proofs Aggregation via SnarkPack
We could stick to the theoretical requirements for Fiat- Shamir Heuristic and heavily use SnarkPack in order to aggregate proofs. This would give us a reduced onchain footprint with a logarithmic overhead for the verification, which is acceptable. Nevertheless, proving overhead would be still considerable (8x what we have today)
(3) Synthetic PoRep: Commit to non interactive challenges and verify a subset of them to grant soundness
Synthetic PoRep aims mitigate the need of keeping around a whole graph between PreCommit and ProveCommit by relying on a first non interactive step of challenge generation combined with an interactive step of partial challenge check.
Even if this approach is keeping some interaction, it improves the current state of things under multiple points of view:
- Mining Experience: adding sectors to the network results in a lighter process than today, even if less light as the full non-interactive Fiat Shamir proposal
- Exponential Network Growth: both Neutron proposal and Stateless Mining really profit by having a lighter PoRep mechanism.
- Small changes in current circuits: it seems we could keep them almost the same as today
Interactive Challenge Verification
The biggest benefit of NI PoRep comes from non-interactive challenge generation, its biggest drawback comes from how numerous these challenges have to be to perform non-interactive verification.
Proposed below protocol reintroduces interactivity to the PoRep protocol but keeps challenge generation non-interactive.
This allows us to keep the benefit of miners being able to discard layers data (12x sector size) before interacting with the chain, while at the same time not increasing the GPU cost of sealing, which is significantly increased in NI Fiat Shamir PoRep. The drawback in comparison to fully NI PoRep is that the interactive step still exists on chain but it is not worse in comparison to today.
The protocol works as follows:
- After computing the replica, the miner computes N vanilla proofs based on N non-interactive challenges (using fiat-shamir). When vanilla proofs are computed, the miner is free to remove layers data for the sector.
- When the miner is ready to onboard the sector as part of an aggregate or supersector, he commits to CommR and waits a delay to reveal randomness which will choose V challenges out of N to be verified.
- After the randomness is revealed, the miner submits SNARK proofs for V challenges.
The number of verified challenges, V, can be much lower than the overall number of challenges, N, as the miner has to cheat C challenges, which ends up being the majority of N challenges, such that when selecting V challenges at random, only cheated challenges are selected.
The details of the Synthetic PoRep Protocol Description can be found in here. Moreover, a discussion can be found on Github here