Reduce PoRep verification time by reducing graph parents generation cost

[kaitlin-beegle]

Migrated from #102; originally authored by @nicola

--

Facts:

• According to preliminary calculations, about half of the time spent in verifying a PoRep proof goes into generating the correct indices of the parents of the challenged nodes (from now challenged parents)
• Challenged parents are currently independent per proof and they depend on the randomness at the height of PreCommit.

Potential proposals that could evolve into a FIP:

• Proposal 1: Add cache to verification:
  • Full nodes must keep in cache the full graph in order to generate parents efficiently by reading memory (~1GiB)
  • Pro:
    • No major change, only gas cost adjustments and requirement of graph cache
    • It will improve today's proofs (no requirement on SnarkPack)
  • Cons:
    • Large memory/storage requirement for full node (note that they are already storing a very large state, so likely not too bad afterall)
• Proposal 2: Generate parents once for aggregated precommits (SnarkPack only)
  • Given a ProveCommitAggregate, for all sectors precommitted at the same epoch, only generate the parents once (since they will share the same randomness). In this way, it will be more rational for miners to reduce their gas cost by PreCommittAggregate and then ProveCommitAggregate their proofs
  • Pros:
    • No mem requirement as in 1
  • Cons:
    • Miners need to time things right to minimize costs
    • Only works with SnarkPack
    • Miners may PreCommit across epochs, so we may not realize the full 50% gas reduction
• Proposal 3: Same randomness for all precommits in a window
  • Instead of randomness being assigned per pre-commit, only generate randomness every X blocks, every precommitted before X will use randomness at X. This means that for all sectors precommitted at position X, they will all have the same randomness, hence parents only need to be calculated once every X for all miners.
  • Pros:
    • No mem requirement as in 1
    • Can realize 50% gas reduction
    • Should work also without SnarkPack

There may be other solutions that we did not consider. Let us know what are your thoughts on the three proposals.

Once this gets more solidified we can turn it into an FIP proposal.