6
$\begingroup$

There are a lot of miners trying to calculate the next valid SHA-256 hash using random strings, so can I consider that generated hashes have good randomness? How can I prove it?

For example, use the bitcoin hash as a entropy or seed to generate random numbers. How would you solve this problem? What algorithm would you use to generate random numbers with the bitcoin hash as a input seed? but the algorithm should be secure and have a good entropy

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ They don't have to try random strings. Any input is as likely as every other input to create a SHA-256 output with a desired prefix. A miner can try to win Bitcoin's high-carbon-footprint lottery using only inputs that were a multiple of 5, for example, or only inputs that end with the ASCII bytes for the string "cat". They would find a winning input in the same expected number of tries, even though they aren't using random inputs, because SHA-2 behaves somewhat like a random oracle. So they could bias the result and succeed with a probability equal to them first winning the Bitcoin race. $\endgroup$
    – Future Security
    Commented Jun 22, 2019 at 0:46
  • $\begingroup$ @FutureSecurity I suppose each miner use a different strategy to get the right hash, otherwise everyone would be calculating the same hashes and it would always win the fastest. So if we have a group of people that uses strategies and another group that uses random strings (I pretty sure this group exists, specially if you can't rival with the most powerful), we can consider the next hash is completely random and unpredictable. $\endgroup$
    – Serginho
    Commented Jun 22, 2019 at 11:48
  • $\begingroup$ I've not looked into details of mining hardware and this is over-simplified, but I've read that miners basically pick a random r to start with; then each subsequent hash uses ++r. Everyone can use this one strategy without miners repeating work that's already failed for someone else. If you ignore the fact that a miner might not have hardware that's designed for this, the initial r can be rounded to a multiple of 5 and ++r can be replaced with r += 5. That wouldn't effect the probability of success or required number of hashes. Nor does it have the redundant mining issue. $\endgroup$
    – Future Security
    Commented Jun 22, 2019 at 15:40
  • $\begingroup$ (Using a counter is actually slightly cheaper and faster than using a new random number every time. Again, with no negative side effects. Real mining hardware might use some other form of "counting", eg. using a hardware LFSR, to save a little more energy. This is also very theoretical. Someone succeeding in biasing results has to win the mining race, which probably wouldn't be likely or worth the expense. At least while bitcoin is popular.) $\endgroup$
    – Future Security
    Commented Jun 22, 2019 at 15:53
  • 1
    $\begingroup$ @JonHutton Hex is just a representation of a hash output. The output itself is binary. $\endgroup$
    – forest
    Commented Jun 23, 2019 at 3:15

1 Answer 1

Reset to default
5
$\begingroup$

As Bonneau et al. showed a Bitcoin block header has high min-entropy, approximately 68 bits. So, in theory you could extract randomness for your protocol or application from Bitcoin block headers, but bear in mind that blockchain's entropy is malleable as shown by Pierrot et al.

For example, if you run a lottery whose randomness is extracted from the Bitcoin blockchain, a miner could interfere with this randomness by withholding blocks whose entropy is not profitable for her. She might want to do this, if she is participating in the lottery and the prize of the lottery is larger than the block reward.

To deter such an attack you might want to use verifiable delay functions(VDF). VDFs make impossible to learn the randomness derived from the block before some time-out (say 1 hour), since it requires sequential work to compute, therefore massive parallelization does not help here. Furthermore once the output of the VDF function is calculated it is easy to verify the computation given a small proof. By applying VDFs even the miner does not know the output of the VDF before the time-out. Therefore there would be no more financial incentive for the miner not to publish her block, since she would forfeit her block reward.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.