Off-chain Window PoSt verification

[anorth]

Problem

Window PoSt messages are necessary for ongoing maintenance of storage power. Verifying the submitted proofs is expensive and when the gas base fee rises (due to congestion) these messages become expensive. In bad cases, for small miners with mostly-empty partitions, this cost can exceed their expected reward from maintaining power. We need to ensure that these messages are cheap for miners, even when specifying a very high gas fee cap.

Note the framing of the problem here assumes congestion. There is a separate and just-as-pressing problem of reducing congestion. But even if we make great improvements there, congestion will happen sometimes in the future for different reasons (E.g. massive popularity! Deals! DeFi!) and we'll need Window PoSt to remain cheap and effective.

This is an alternative to the Fast Track for Window PoSt and related proposals.

Proposed solution

Don't verify most Window PoSt proofs "on chain". Assume they are valid, and implement a challenge mechanism for external parties to dispute an invalid proof, verifying on-chain only at that point.

Outline

• Change the SubmitWindowPoSt method to store the proof bytes (or a hash) in per-deadline chain state instead of verifying the proof. The method still checks that the proof is expected, records skipped faults, etc. Optimistically update state assuming the proof is valid, including marking recovered sectors and gaining power for new/recovered sectors.
• During end-of-deadline cron, snapshot the partition state relevant for proof verification (the active/faulty sector sets and proofs themselves)
• The proofs and snapshots remains in chain state until the next occurrence of the deadline (~24h)
• At any point in that challenge window, a challenger can force the on-chain validation of a proof. If the proof fails validation, all of the sectors in the partitions included in that proof are marked faulty, penalised, and the miner loses power for them.

With this mechanism, the vast majority of Window PoSt proofs would never be validated on chain. The network cost of maintaining storage would be effectively constant, rather than linear in storage as it is today (at sufficient scale it would revert to linear for the work of submitting the proofs, but over that timeframe expect to develop other aggregation techniques).

Discussion

This issue is intended for discussion. There are a number of details to work out before drafting a FIP.

Impact

The proof verification syscall accounts for 88% of SubmitWindowPoSt's gas cost, and loading the thousands of SectorOnChainInfo that form public inputs for the bulk of the remainder. Both of these are avoided for valid proofs, and the cost paid by a challenger rather than the miner. So the gas cost reduction will be in the range of 10-20x (maybe more for full partitions).

Rather than every node on the network validating every proof, we instead need that at least one node verifies every proof.

Note that a similar technique could be applied to ProveCommit proof verifications too, but that's a bit trickier and out of scope for this proposal.

Incentives

This proposal does not include a reward for a successful challenge, though one could be added.

• If there were a reward, it would still not be rational for a party to verify proofs with the aim of winning the reward unless that party were also a significant block producer. Any public submission of a challenge message would be censored and stolen by a block producer, taking the reward for themselves.
  • But parties may rationally verify proofs for other reasons
• Block producers are incentivised to detect fraudulent proofs in order to reduce the power share of other miners
  • But not proofs from below-consensus-power-threshold miners
• Off-chain verification with no reward lends itself to miner cooperation, dividing the verification work for mutual efficiency and benefit
  • For any individual miner, the expected gain in power share might not justify the cost of verifying all proofs, but would justify doing some of the work given assurance that others would do disjoint parts of it.
  • For below-consensus-threshold miners, a cooperative of deal clients could collaborate to check all their proofs (the likely cost of this is ~ operation of a single consumer machine).
• It may be prudent to introduce a reward covering the network transaction (gas) fee for a successful challenge, lest high gas prices exceed the expected value of increased power share
• Protocol Labs, at least, may be considered sufficiently incentivised to run hardware to verify all proofs long into the future, regardless of any direct reward. This proposal assumes the continued existence of some organisations or cooperatives with similar broad network security incentive (the Filecoin Foundation? Institutional investors?).
• An honest block producer is always incentivised to include a successful challenge message, if one is transmitted to them, since it will increase their power share.

Verification mechanics

Off-chain verification lends itself to continued technical improvements without the need for protocol upgrades.

• We can immediately apply batch verification techniques to verify 10s of Window PoSt proofs together, from different miners, for a ~5x speedup, on the assumption that most proofs are valid.
• Future improvements in verification speed can be used immediately without the need to adjust gas costs
• Verification systems can store sector information (sealed CIDs) in any appropriate database, not limited to hash-linked structures.

Risks

Some risks to consider and satisfy ourselves about.

• The obvious attack of this mechanism would be cabal of large miners who refuse to include challenges of each other's storage.
  • A first consideration suggests that such a cabal would have to have at least 1/3 of power in order to be effective (at which point other attacks are possible), but this needs analysis.
• A large miner could spam bad proofs to try to overwhelm the chain with the subsequent verification cost.
  • We'd have to pick penalties/limits to avoid this.
  • Each partition can only be used once in this way before a valid proof is needed to restore its power.
  • A the moment, we have chain bandwidth to handle challenging every proof, and if we greatly reduce congestion, headroom here will increase by >= 10x
  • Future proof aggregation techniques may support submitting a challenge for multiple proofs with sub-linear verification cost.
• How does this affect chain weight? At the moment, it's very difficult to increase chain weight by excluding a message but this makes it easier.

Implementation notes

The miner state update required for a successful challenge will be very similar to the state change currently implemented during the deadline cron when a "missed PoSt" is detected. Snapshotting the partition state is expected to be cheap since we can content-address state that already exists in the state tree.

Since submitting a proof will no longer involve loading all the sector information, we can probably increase the number of partitions that may be batched into a single submission (currently, and somewhat arbitrarily, set to 4).

Open questions

A bunch of details to be worked out include:

• What is the expected reward for a block producer of detecting a fraudulent proof?
• What is the appropriate penalty rate for bad proofs?
• Do we need to reward gas?

[anorth]

@Stebalien and I are spiking on concrete implementation of this to narrow the uncertainty and focus analysis.

[jbenet]

I think this is a great idea. I think most/all SNARK verification that we do could be moved to a slashing model.

[jbenet]

Re: censoring

• It may be time to implement a commit-then-execute message exec.
• Using any VDF (maybe even simple DFs): let key K be the result of running a VDF for T epochs. we can encrypt transactions under K, submit them, and have them decrypted & executed on chain afterward by miners.
• https://gist.github.com/jbenet/9f8dc458271b1781c1e347053e9fc2cb

[nicola]

Note: this should be merged only if our reporting dispute code is ready.

[anorth]

Shipped as FIP-0010!