search

dbosk / crocus

Securely and privately verifiable protests
Other
0 stars 0 forks source link

TS: What do we mean by "difficult to guess before time t"? #129

Open dbosk opened 5 years ago

dbosk commented 5 years ago

How difficult is that?

dbosk commented 5 years ago

The probability of guessing it correctly should be exponential in the security parameter, \lambda.

dbosk commented 5 years ago

Even if the adversary can control all the inputs, it will be difficult. If it wasn't, anyone could mine cryptocurrencies easily.

The adversary knows the "strength" of the network, so if the hash values are adapted to that (e.g. k leading zeroes as in Bitcoin), then the difficulty of prediction should be at least 2^{n-k}. Where n = p(\lambda), where p is a polynomial.

In that sense, as the strength of the network increases, the difficulty of guessing decreases.

How does this work with proof-of-stake? It should be 2^n, if it's an n-bit hash, but I must look into it.

sbuc commented 5 years ago

Isn't this a general blockchain problem? Do we need to address this?

dbosk commented 5 years ago

Well, we still need to capture this formally, for when we state our assumption. Our current phrasing is very informal, it doesn't do any attempt at quantifying the difficulty of predicting the value.