Gamble Channels: Fast Verifiable Off-Chain Gambling

Gambling on a blockchain has one big UI problem: it's too slow. If you have to wait for the next block, it's boring.

SatoshiDice fixed that by using Bitcoin's UTXO model. You sent a transaction to the SatoshiDice address, and if you won it sent back a transaction that gave you your winnings. That was safe for SatoshiDice to do, since the payout transaction wasn't valid without your bet transaction. You got instant results.

SatoshiDice wasn't perfect. It was a centralized service, you had to trust it to generate fair random numbers (though you could check its historical win rate), it had a house edge, and every bet had to go on the blockchain. Despite all this it was hugely popular for a while.

But what if we could fix those problems? Instant gambling, between any two people, with verifiable fairness and no house edge at all? What if we could do all our bets off-chain until we're ready to cash out?

The solution is state channels. They're like the payment channels I described in the Lightning post, but track arbitrary state.

Signatures

Just like with payment channels, we sign data offline, like this:

web3.eth.sign(address, dataToSign);

A solidity contract can verify a signature like this:

address signer = ecrecover(sha3(data), v, r, s);

In a simple payment channel, we just keep sending the recipient signed data with a transfer amount, with a slightly bigger total each time, with a contract that only allows a single redemption. The recipient gets the most money by sending the latest one to the contract.

We did pretty much the same thing with the duplex channels in our Lightning implementation, and with blind auctions.

But for a game, we can't rely on users having a built-in economic incentive to submit the most recent transaction. Instead, we'll need to increment a nonce with each step of gameplay. Each player only accepts transactions that properly increment the nonce. When closing the channel, the contract accepts the submitted state with the highest nonce; either player can submit, and the other player has an opportunity to submit a state with a higher nonce.

Using a nonce gets a little tricky in a duplex payment channel, where each party can send transactions at any time. But in a game, we can enforce a particular sequence of moves. For a basic gamble channel, we'll have the two players simply take turns.

State

Since the players take turns, we have a simple way to handle arbitrary state. Just have each player sign a statement which includes:

  • The current state, including the current nonce n

  • The other player's signature over the previous state, including the nonce n-1.

Players don't sign without a valid transition. A player closing the channel can submit his own signed statement, and the signed statement he most recently received from his opponent; the contract can verify that both players agreed on the n-1 state, and that the transition from n-1 to n was a valid transition.

Random Numbers

Random numbers are famously tricky for Ethereum gambling contracts. If all our bets were on-chain we could use block hashes to get our random numbers. We'd be vulnerable to miner manipulation, but it'd work ok if our bets were small. Another option is BTCRelay, which pulls random numbers from Bitcoin block headers, but those show up only every ten minutes or so. Or we could trust a random source from Oraclize, but those can be manipulated too; a miner could just get lots of random numbers from them and discard the ones he doesn't like.

But here's the trick that makes Gamble Channels possible:

When two players start a game, each generates a chain of, say, 10,000 sha3 hashes. Each is the hash of the previous hash, all the way back to an initial random number.

Players initiate the game by sending each other the final hash in their chains.

They place their bets, then send the preimage of the current hash. Each player verifies that the preimage hashes to the current hash. The two preimages are XOR'd together, and there's your random number.

If a player runs out of hashes, the channel has to close. But a chain of 10,000 hashes takes less than a second to make, only 320K to store, and at 2 seconds per round is good for over five hours of play.

A Basic Gamble Channel

The game is simple: each generated random number pays Alice if it's below the median, and Bob if it's above the median. Players start by generating a random number and a sequence of hashes on top, depositing funds, and agreeing on a standard bet size.

Here's a rough draft of the contract. This version only handles two players; every new game will have to start by publishing a new contract. This isn't tested or audited and may well have security issues.

//Balances in bets can go negative
//They are deltas on the player's actual balance
//This lets players easily top up their ether balance by sending ether to contract
//Players can't withdraw ether until the channel is finalized
//Client code is responsible for ending betting if opponent runs out of funds

contract GambleChannel {
    bool public Finalized;
    bool public Adjusted;
    uint public ClosingBlock;
    uint public FinalNonce;
    bool public FinalBettor;
    uint public Betsize;
    mapping(bool => address) public players;
    mapping(address => uint) public deposits;
    mapping(address => int) public deltas;

    struct Bet { 
        uint256 Priorhash; 
        uint256 Currhash; 
        bool Bettor; 
        int Balance0; 
        int Balance1; 
        uint Nonce; 
        uint8 v; 
        bytes32 r; 
        bytes32 s;
    }

    modifier deposit() {
        if (players[true] != msg.sender && 
            players[false] != msg.sender) throw;
        deposits[msg.sender] += msg.value;
        _
    }

    function() deposit { }

    event ChannelClosed();

    function GambleChannel (address player2, uint betsize) deposit {
        if (msg.sender == player2) throw; //would cause all bets to invalidate
        players[true] = msg.sender;
        players[false] = player2;
        Betsize = betsize;
        Finalized = false;
        Adjusted = false;
    }

    function checksig(Bet b) private returns(bool) {
        bytes32 hash = sha3(b.Priorhash, b.Currhash, b.Currplayer, b.Balance0, b.Balance1, b.Nonce);
        player = players[b.Currplayer];
        return player == ecrecover(hash, b.v, b.r, b.s);
    }

    function checkpair(Bet curr, Bet prior) private returns(bool) {
        //sigs must be valid
        if (!checksig(curr)) return false;
        if (!checksig(prior)) return false;

        //bettors must alternate
        if (curr.Bettor == prior.Bettor) return false;

        //bettor's hash must be preimage of his previous hash 
        if (curr.Currhash != sha256(prior.Priorhash)) return false;

        //bettor must correctly report opponent's latest hash
        if (curr.Priorhash != prior.Currhash) return false;

        //bettor must increment nonce
        if (curr.Nonce != prior.Nonce + 1) return false;

        //balances must be adjusted properly
        uint spin = curr.Currhash ^ curr.Priorhash; //xor
        bool winner = (spin > ~0 / 2);

        int trueChange = -Betsize;
        int falseChange = Betsize;
        if (winner) {
            trueChange = Betsize;
            falseChange = -Betsize;
        }
        if (curr.Balance0 != prior.Balance0 + falsechange) return false;
        if (curr.Balance1 != prior.Balance1 + truechange) return false;

        //passed all checks
        return true;
    }

    function setFinal(Bet bet) private {
        address player0 = players[false];
        address player1 = players[true];
        deltas[player0] = bet.Balance0; 
        deltas[player1] = bet.Balance1;
        finalNonce = bet.Nonce;
        finalBettor = bet.Bettor;
        closingBlock = block.number + 1 hour;
        if (!finalized) finalized = true;
    }

    function finalize(Bet currentBet, Bet priorBet) deposit {
        if (!checkpair(currentBet, priorBet)) throw;
        if (!finalized || currentBet.Nonce > finalNonce) setFinal(currentBet);
    }

    function claim() deposit {
        if (channelClosed()) {
            if (!Adjusted) {
                //assume people always quit on a losing bet
                //so award one more bet to finalBettor
                if (finalBettor) {
                    deltas[true] += Betsize;
                    deltas[false] -= Betsize;
                } else {
                    deltas[true] -= Betsize;
                    deltas[false] += Betsize;
                }
                Adjusted = true;
            }
            uint256 amount = deposits[msg.sender] + deltas[msg.sender];
            if (amount > 0) {
                deposits[msg.sender] = 0;
                deltas[msg.sender] = 0;
                if (!msg.sender.call.value(amount)()) throw;
            }
        }
    }

    function channelClosed() private returns(bool) {
        return finalized && block.number > closingBlock ;
    }
}

Next Steps

Instead of making a new contract for every game, it might be nice to have a single contract hosting lots of games. Of course that means we have to make sure that a hacker can't withdraw ether from games other than his own!

Just flipping a coin might get boring after a while. More complex games might be more fun. Dice games, roulette, or blackjack are all possibilities. For blackjack, eliminate card counting by just pretending we have an infinite number of decks, so the odds of any particular card coming up don't vary depending on what's already turned up. (Casinos already try to approximate this by using at least six decks.)

Poker is a hard problem. It's difficult to deal a card secretly to Alice, and make sure Bob doesn't get the same card without revealing to Bob that Alice has it. The wikipedia entry on mental poker has more information. But we could manage other games with hidden information.