Rolling commit-reveal: an idea for 'randomness' in force-move games

force-move
1

One of the challenges when writing a state channel game is simulating random events, such as a dice roll. This post presents a (new?) idea for tackling this problem. Before introducing this idea we will look at two existing approaches: commit-reveal, and hash-onions

Commit-reveal

One way of doing generating randomness is to add a commit-reveal process, taking two rounds of states:

  1. In the first round, every player i commits to a number rnd_i, by concatenating hash(rnd_i, salt_i) to the state.
  2. In the second round, the players reveal rnd_i and salt_i, and construct rnd = sum_i(rnd_i)

This has the property that if any one player generates their number rnd_i randomly, then the result will also be random. The downside of this approach is that it adds two rounds of state channel states for each game move where randomness is required.

Hash-onions

The hash-onion approach requires a privileged player, e.g. player A, to provide the randomness for the channel. Before play starts, player A commits to a value rnd_0. This value is constructed by applying a hash function n times to a secret random seed, known only to A.

The channel maintains a rnd_source, which is initially set to rnd_0. When randomness is required, player A ‘unpeels a layer of the onion’, revealing an r such that hash(r) = rnd_source, and then setting rnd_source = r.

This is a bit more efficient that commit reveal: randomness can only be revealed on player A’s turn, but that only takes one round of states, instead of two. It has the downside that player A knows all of the random values in advance.

The hash-onion approach is used by FunFair for their state channel casino games.

New idea: rolling commit-reveal

In rolling commit reveal, each player begins by generating a random number rnd_i_0, and committing to this number by adding cmt_i_0 = hash(rnd_i_0, salt_i_0) to the state. On each turn players reveal their previous random number and commit to their next:

  1. At round j, player i reveals rnd_i_j and salt_i_j such that cmt_i_j = hash(rnd_i_j, salt_i_j).
  2. This entropy is added to a randomness accumulator rnd, e.g. by adding, or by bitwise or etc.
  3. rnd is used for any randomness required on i’s turn
  4. Player i then generates rnd_i_(j+1) and adds the commitment to the state

This has the property that if any player is honest, and generates a random number, then each player will have a random number on their next turn. It has the advantage that no extra rounds of states are required to generate randomness.

There is some collusion possible, but it might still be an acceptable trade-off. For example, in a channel with 1 honest player, and (n-1) colluding dishonest players, at the point straight after the honest player’s turn the dishonest players can accurately predict the values of rnd up until the honest player’s next turn. It’s possible that this could allow them to collude so that one of their members win the game before the honest player’s next turn, for example. It might be that this is ok in real-world games though, which tend not to work well in the case where all the players collude against another anyhow.

2 Likes