Showerthoughts: Trustless Multiparty Pseudorandom Numbers

Let’s say that Kenny and Hector are planning a bank heist and they need to decide amongst themselves who is the robber and who is the driver (à la Shut Up and Dance from Black Mirror). Surely most people would prefer to be the driver in this situation and so with no better way to choose, the fair thing to do would be flip a coin. If it’s heads, then Kenny is the robber, otherwise Hector is.

Let’s suppose that Kenny and Hector are in different cities, and are planning the heist ahead of time. A physical coin flip won’t do; they will need to generate a random number between themselves to decide who is the robber and who is the driver. The obvious way to do this is to have a third party generate the random number. Something like Cointossr might do the trick.

But, to make things more interesting from a game-theoretical perspective, we’ll assume that Kenny doesn’t trust Hector, Hector doesn’t trust Kenny and neither of them trust any third party. We need a way to generate random numbers over the internet that is completely trustless.

Have a think about it!

Solution One

Random numbers generated by computers are completely deterministic and emergent from an initial value called a seed. The seed completely determines all random numbers that follow. If somebody can ‘force’ the seed, then they can force any random number from the generator.

By having Hector and Kenny both contribute a portion to the seed, we (partially) eliminate this concern. For example, before the random number generator is used, Hector and Kenny both think of a random string and ‘commit’ to it. The seed is the XOR of these two strings (bitwise).

The problem with this is that one party has to reveal their commitment first. Let’s suppose Kenny reveals his commitment string first. This gives Hector time to generate a new commitment which, when XORed with Kenny’s, generates a favourable random number.

This option is fine if commitments are sent simultaneously, but computer networks are subject to latency. What one party may describe as ‘network latency’ may actually be cheating. They could be using the time to generate a seed which generates numbers that suit them better.

Solution Two

We use the same principles as before, but we commit to our random strings properly using a cryptographic commitment scheme. Here are the steps:

  1. Both Hector and Kenny generate commitments (any string – anything goes) on their local machines.
  2. Using a secure cryptographic hash function (SHA256 in this post), they hash their commitments.
  3. They send their hashed commitments to one another.
  4. Once the hashed commitments have been received, they send their unhashed commitments to one another.
  5. Each party then verifies that the unhashed commitment, when hashed, equals the hashed commitment.
  6. The random number is generated by taking both of the unhashed commitments, XORing them together then using this as the seed material for a PRNG. Alternatively, we could just use the bitwise XOR as the random number itself, but we’ll assume we want to generate a sequence of random numbers for completeness.

By establishing a seed that cannot be manipulated by any single party, we have a way to generate fair pseudorandom numbers over the internet without having to trust anyone.

Why does this work?

Cryptographic hash functions have two important properties:

  • It’s infeasible to generate a message from its hash except by guessing.
  • A small change to a message should change the hash value so extensively that the new hash value appears uncorrelated with the old hash value – this is called the avalanche effect.
  • It’s infeasible to find two different messages with the same hash value.

Hashing the commitment keeps it hidden from others until it is needed later. Commitment schemes are designed so that a party cannot change their statement after they have committed to it: that is, commitment schemes are binding. Before the random number is generated, no single party is aware of any of the constituent seed material and therefore cannot force the random number process. It is about as fair as you can get. The numbers that are generated with this scheme are trustlessly random.

More Than Two Parties

It’s trivial to extend this to work with N parties. Like before, everyone commits to a personal secret. Once everybody has made their commitment, the secrets are revealed. The seed material is the bitwise XOR of the revealed secrets.

Additional Considerations

There are a few additional considerations we might want to take into account.

  • Once all of the personal secrets are revealed, which order do we XOR them together in? Answer: it doesn’t matter. XOR is commutative, so order isn’t a concern.
  • What happens if one (or more) party is uncooperative and doesn’t abide by the rules of the cryptographic commitment scheme (e.g. they reveal a secret that doesn’t match their hash)? Answer: we ignore their commitment when finding the seed. If we do this we still generate a sensible seed using everyone else’s commitments. However, the uncooperative party now has to trust that the other parties aren’t plotting against them.

    Why? Suppose there are 3 parties: A, B, and C. Let’s say A and B are working against C. They can coordinate two secrets between themselves which, in the event that C is uncooperative, generates a seed which favours them. If C cooperates, any planning between A and B is void since C’s secret will be included as part of the seed. It is therefore in C’s best interest to cooperate, otherwise they are trusting the other parties to play fairly too. This scheme incentivises all parties to play fairly.

This is a Lot of Effort for Random Numbers…

Yep, it is. But random numbers are important in many situations. For example, take the Golem Project’s Nanopayment Scheme, which uses a probabilistic payment scheme to reward users for contributing their computing power. In this context we must assume that there is no trust between any parties. There needs to be a trustless, decentralised way to establish who won the lottery. This kind of scheme could be useful in situations like this.

(as a side note, the Golem Project doesn’t use this kind of scheme to determine who wins the lottery. They use the hash of a block header instead, which is probably equally as good if not better)

Written on December 23, 2017