[Consensus] Random Seed sampling

[sternhenri]

Currently evaluated strategies:

• (current) VRF+VDF(Post) against current min ticket from parent set
• Sample from k blocks back (constant lookback)
• Sample from k blocks back but variable lookback: use seed for n block epoch

Strategy

Short term

• Get together to write attacks to EC ([Consensus Attack] Exponential Forking #18, added headstart simulation #57)
• Attempt formal evaluation of entropy in tickets (given EC construction)
• Meet in person in December Research Weeks

Mid/long-term

• Involve outside researchers (could be Snow White authors (Rafael Pass, Phil Daian)) about this

---

Other notes:

• https://github.com/filecoin-project/research/issues/18
• https://github.com/filecoin-project/aq/issues/98 (but about PoST tickets)
• Read "Formal Barriers"
• Read how Algorand proves their on-chain randomness: Algorand uses the ticket chain to extract randomness (or extract a future honest user), page 55 chapter 5.9 shows how to do this

---

Why do we need randomness?

• Elect leaders
• Seed for the proof of spacetime (this is where we get PoSt challenges from!)
  • Taking the seed from chain ensures that a VDF speedup won't compromise security since the network still has to wait for the "re-seeding" from chain
  • Can we avoid taking challenges from chain for PoSt? Technically yes (MPC? All absed on VDF?), practically, it's difficult.

Decision tree (so far):

• Can we use the chain as a Randomness Beacon?
  • if yes:
    • Construction 1: just use the ticket chain (like algorand!)
  • if not:
    • Run MPC at every round:
      • Construction 2: Run a slow MPC -> VDF+RANDAO (similar to justice)
      • Construction 3: Run a fast MPC -> Deterministic Threshold Signatures (like DFinity) at every round (also useful for SSLE)
    • Current leader runs VDF:
      • Construction 4: leader submits a ticket, miners run VDF for T blocks to find their secret leader election seed

More in this presentation on randomness

[sternhenri]

@whyrusleeping @nicola @ZenGround0 How are we feeling about this one? Is it still a major area of open questions, I must admit I feel like I've answered a lot of my own questions here.

I also think we can close filecoin-project/research#98.

Major Qs for me come from filecoin-project/research#34, which I take to be blocked on @nicola (for lack of context on my part)