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
One way of doing generating randomness is to add a commit-reveal process, taking two rounds of states:
- In the first round, every player
icommits to a number
rnd_i, by concatenating
hash(rnd_i, salt_i)to the state.
- In the second round, the players reveal
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.
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:
- At round j, player i reveals
cmt_i_j = hash(rnd_i_j, salt_i_j).
- This entropy is added to a randomness accumulator
rnd, e.g. by adding, or by bitwise or etc.
rndis used for any randomness required on i’s turn
- 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.