Permalink
Switch branches/tags
Nothing to show
Find file Copy path
238919d Jan 29, 2017
1 contributor

Users who have contributed to this file

27 lines (19 sloc) 5.55 KB

The Signidice Algorithm

This algorithm is suitable for those Ethereum-based games, where outcome of every round for the player depends only on the RNG and (optionally) the number, chosen by the player, but not on the action of other players. E.g. it may be suitable for roulette, slots, etc., but not for those games, where outcome depends on the other players or just their number, as may be the case in lotteries. For example, a game of roulette could be modeled as a number of rounds where a single player plays against the casino. In this case, a pseudorandom number could be generated with the following algorithm.

  1. Casino generates a new pair of private/public keys (PrivKey and PubKey) for some deterministic signing algorithm (e.g.RSA).
  2. Casino creates a smart contract, which contains the public key (PubKey), maximal number of participants, and the Ether bounty. (Optionally: casino changes PubKey of the existing smart contract).
  3. Player chooses the number to bet on (B), and a random number (R) in certain format (e.g. 20 bytes). The player might even specify the range of numbers B, if the rules of the game allow it (odd vs. even, etc.).
  4. Player sends a transaction (TX) containing the Ether bet, along with the data: B and R.
  5. The contract checks validity and format of the numbers B and R. Invalid TX is rejected.
  6. Additionally, the contract checks if the number R has already been used by this player in previous rounds, in which case TX is rejected. (This step is necessary if the contract is reused for multiple rounds of the game).
  7. The contract concatenates the random number R with the public address (A) of the player's Ether account, from which TX was sent: V = A + R. The resulting value V is stored in the contract. The size of V is always the same: size(V) = size(A) + size(R). At this point the outcome of the round (win or lose) becomes deterministic.
  8. Casino must sign the resulting value V with its PrivKey, thus producing the digital signature S = sign(PrivKey, V), and send the corresponding TX, containing S.
  9. The contract recovers the actual public key (K) from the digital signature S, and verifies that it is equal to the previously published PubKey (K == PubKey). If APK does not match PubKey, or if casino fails to perform step 8 within a predefined time frame, it is tantamount to cheating. In this case the contract sends the bounty to the player along with the original bet, and the contract is closed via suicide. (In case of multiplayer game, the bounty is shared between all players).
  10. The contract uses S as a seed for the predefined PRNG algorithm (e.g. SHA-3 based), which produces the lucky number (L), e.g. between 0 and 36.
  11. If B corresponds to L, the player wins, otherwise casino wins. The contract sends the bet to the winner.
  12. Now casino may close the contract and recover the bounty, or initiate a new round of the game. Alternatively, the contract might be programmed to automatically proceed to the next round, unless the casino closes it.

After casino has chosen the PrivKey, its actions become deterministic. The player can not predict the result of digital signature, and therefore his choice of the random number R can influence the outcome only in the same way as rolling the dice in the real life (hence the name of this algorithm). Thus, neither of the participants can manipulate the outcome in any meaningful way.

The bounty that casino commits to the contract must be high enough to compensate the players for any possible opportunity loss. The time slot must be long enough to accommodate for any kind of network disruption. Although it gives the casino opportunity to postpone the outcome, it has no incentive to do so, since the outcome is still deterministic. Postponing without a valid reason will only result in reputational loss, whereas no financial gain is possible. If the casino wants to maintain good reputation, it might even intercept the player's TX before the next Ether block is mined, immediately calculate the outcome of the game, and reward the player in case he wins, even before the step 7 occurs (before corresponding TX is incorporated into the next mined block). Instant gratification will also help to prevent the reputational loss in case of long delay (e.g. due to the network disruption). It might also allow the player to start a new round without waiting for the next block to be mined.

The same smart contract can be reused multiple times, provided that the player never chooses the same number R twice (otherwise he can predict the outcome). Hence, the necessity of the step 5 -- the contract should reject any TX, where the same player uses the same number R in the same contract twice. Alternatively, the casino can regularly change the pair of PrivKey/PubKey, publishing the PubKey before every new round. But it requires an additional TX, resulting in unnecessary delays and increasing TX costs.

Nothing should prevent multiple players from using the same smart contract simultaneously. Different players even choose the numbers N, previously used by other players: V will be unique, since A is unique. The number of possible participants will only be limited by the bounty the casino is willing to commit.

The game of roulette in online casino was used purely as an example. The Signidice algorithm can be used in any case, where transactions occur between the two participants. In this case the Signidice is better than RANDAO: the players neither have to trust the oracles (in case of external oracle use), nor can disrupt the next round of the game by refusing to reveal the committed number (in case of players being the oracles).