[Consensus] Random Seed sampling - Githubissues

filecoin-project / consensus

Filecoin consensus work

Other

42 stars 5 forks source link

[Consensus] Random Seed sampling #24

Closed sternhenri closed 5 years ago

sternhenri commented 5 years ago

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

[x] Get together to write attacks to EC (#18, #57)
[ ] Attempt formal evaluation of entropy in tickets (given EC construction)
[x] 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 commented 5 years ago

@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 https://github.com/filecoin-project/research/issues/98.

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