Seed: how biased can it be?

filecoin-project / research

Home for Filecoin Research

Other

74 stars 10 forks source link

Seed: how biased can it be? #34

Closed ZenGround0 closed 4 years ago

ZenGround0 commented 5 years ago

How "bad" would it be if we could bias the on-chain random seed by one bit, for example by having two private forks and choosing which one to release?

As noted by @nicola the answer depends on what we use the seed for. A few likely users I know about are:

EC leader election
PoSts
PoRep Seal??

bvohaska commented 5 years ago

@ZenGround0: Let's talk about this at the research retreat. This issue has come up a few times and I'd like to formalize our discussion.

sternhenri commented 5 years ago

Successful output: what the seed is used for in the system (which black box) and what model of manipulability each can handle (set a bit vs not -- ie choosing between two forks).

So per cryptographic primitive, what randomness do they need.

nicola commented 5 years ago

To move forward on this one:

Do proofs (@nicola) need randomness from the chain?
Does consensus need randomness from the chain? (@sternhenri can you update on your needs on this?)

sternhenri commented 5 years ago

On consensus, yes we do. Specifically having the randomness "tied" to the chain (through ticket-chain being stapled to blocks) allows us to ensure ticket creation and election proofs are not reusable across chains. This is useful to preventing long range attacks (posterior corruption) and helps mitigate Nothing at Stake.

Happy to help evaluate alternatives, but it does have a purpose for us atm.

sternhenri commented 5 years ago

I'll add that we could do without it (esp if it allows us to make stronger claims about unbiasability of the seed), but it's not costless.

nicola commented 4 years ago

old issue, closing