Analyze how secure is the randomness extracted from EC

[bvohaska]

@nicola: Let's define what we mean by "secure". I think what we need to determine is (1) what are we using the randomness for? (2) Does entropy actually matter? If so, how much is enough? (3) How are we going to extract that randomness.

The following is for context and comes from conversations with @nicola, @Stebalien, et. al.

---

Let's consider the case where we are going to use a random seed for our PoST proof. In this case,

• (1) is clear - we want a random seed to kick-off a fair proof ^1,2
• (2) Since the randomness is only used to prevent an attacker from simulating a proof (and possibly gain an unfair power advantage), we don't actually care that the randomness has "a lot" of entropy. We only need the randomness to have enough unpredictability to ensure that generating T proofs is not realistic. Where T is the number of proofs needed to ensure that a miner has generated enough proofs to ensure the proof is valid with probability p. We also want to ensure that the prover can't perform a randomness influence attack ³.
• (3) If there are valid block forks, we will need to consider this when choosing where in the EC or at what epoch randomness will be taken. If we do not account for this, miners will have different/invalid sources of randomness since this is a distributed system.

I would propose that in this case, we define "secure" to be a set of conditions FSC (FIL security conditions) such that the conditions contain at least (1) definition for fairness w.r.t. the consumer of randomness i.e. how will we determine that a particular function is fair given that it will consume randomness r; (2) a definition for relative entropy i.e. w.r.t. (1) what is our effective entropy and how hard would it be to simulate the function in (1); (3) a list of assumptions and dependencies for functions consuming randomness r.

References:

1: Challenge Sampling Discussion 2: SSLE - Overview & Definitions 3: An attacker gains an advantage by influencing the random seed that will be used by provers to generate a proof. For example, let the randomness come from the first listed miner in a block: H(miner_name). If a prover colludes with a block leader, they could choose the first miner in a deterministic way known only to themselves and possibly gain a power advantage.

[lucaniz]

Hi all, don't know if it helps but there was this paper that was formalizing usage of Bitcoin blockchain as a source of publicly verifiable randomness. Feel free to ignore the pointer if I completely missed the point. https://eprint.iacr.org/2015/1015.pdf

If we need any explanation we can ask Steven Goldfeder.

[nicola]

• Algorand uses the ticket chain to extract randomness (or extract a future honest user), page 55 chapter 5.9 shows how to do this (Algorand)
• Snowwhite is a similar model to us, I can't recall their paper now, but they must be doing something in a similar fashion.

[bvohaska]

@lucaniz: It might be a good exercise to write out how each of these methods exact random and the assumptions they make. (1) Might make a good survey paper (2) This would help us evaluate exactly what we need for our system to work and evaluate protocol correctness and security.

I'd also note that we can get randomness from any MPC scheme we choose to use in SSLE (if that's the route we go). It would be verifyably fair assuming our MPC scheme is fair. It would also be verifiable secure under the MPC model. This would make general evaluation of our protocol easier.

[nicola]

See https://github.com/filecoin-project/research/issues/38