9
$\begingroup$

Is there a way to generate a random number with given restrictions:

  • It will be used in a decentralised network with a big number of peers (no central authority to generate it)
  • Its generation should not rely on any third-party service (for example, going to a specific website)
  • Its generation is triggered by a semi-random data being sent through the network, and it should relate to the data
  • The computer sending the data should not have an advantage in determining the random number (for example, computing some number that would have a really high chance of becoming the seeked number)

I was thinking of using a random number like that to counter a 51% attack against the Bitcoin network. The main problem there is that an attacker with a lot of computation power can compute a couple "blocks" in advance and only release them to counter "blocks" generated by legitimate users. I figured a way to counter that would be by requiring generation of some random number that couldn't be pre-computed in advance, but only when a block is sent through the network. Required use of that number would then invalidate blocks that are precomputed beforehand, preventing the attack.

So, is there a way to generate a random number like that described above?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
6
$\begingroup$

A service that provides such numbers is called a random beacon.

Since everyone has to agree on what a beacon's value is and peers may not have a complete view of the network, it is very difficult to construct a universally verifiable value using only internal network data. Since data only becomes canonical when it is included in a block (a block that is accepted by everyone else), I'm not sure what else could be used.

If you relax the internal-only constraint and allow external beacons, you will hopefully be able to use NIST's beacon service. You can also construct values with financial data however this only works when markets are open.

Improve this answer
$\endgroup$
0
9
$\begingroup$

The classic way to do this is to have all parties commit to individual random values by publishing a secure hash of a suitably random-nonce-padded number. Once the commitments have been distributed, the parties open the commitments by publishing the nonce and the number. The numbers are combined in some previously agreed suitable fashion such as adding them modulo some number or xoring them together. As long as your value was included then you are confident that the result is random. If the numbers used are large enough, the nonce is not required.

Improve this answer
$\endgroup$
3
$\begingroup$

This is a well-known problem from the secure multi-party computation literature, known as the coin-tossing problem. Several people want to get together and jointly generate an unbiased coin toss, where the security property is that no one can influence the bias of the coin.

The problem is impossible if adversaries are allowed to be computationally unbounded. The simplest protocol in the computationally bounded setting is the following (I'll describe it for generating a single bit -- it generalizes naturally for generating multiple bits):

  1. Party $i$ publishes a commitment to a secret randomly chosen bit $b_i$.

  2. After everyone has posted their commitment, everyone opens their commitments. The final coin is taken to be $b_1 \oplus \cdots \oplus b_n$.

As long as one person generates their $b_i$ honestly, the outcome is an unbiased coin. This follows from the hiding and binding properties of the commitment scheme.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Actually, your protocol is vulnerable to a classic attack. Suppose there are two parties, Alice and Bob, and Bob goes last. Then, Bob can ensure the final bit will be 0 as follows. Bob can copy Alice's commitment, then copy Alice's opening of the commitment, which ensures that $b_1=b_2$ and thus the final coin is always 0. To fix this, you could compute the final coin as $H(b_1,\dots,b_n)$, or use other standard fixes. $\endgroup$
    – D.W.
    Sep 7, 2012 at 8:24

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.