Let's Play A Round Of Chess - On The BCH Blockchain!
2018-11-30Everybody loves playing chess! Alright, not everybody does, but I do, even if I'm not really good at it. And if you don't like chess, but are still interested in on-chain games, or on-chain whatever, this post is definitely something for you.
The good thing about chess is that it's rules are deterministic, so no need to throw dice or do some cryptographically secure pseudo-random number generator magic. So if Kasparov were to challenge Anand for a round of chess, they might trust some third party (referee) or even each other to enforce/follow the rules, but if they are anonymous people on the internet playing for not insignificant amounts of money, it would be good if the rules of the games didn't require a trusted third party.
That's where Bitcoin Cash comes in. It's designed to not need a trusted third party, just miner incentives. In a recent upgrade, Bitcoin Cash gained support for OP_CHECKDATASIG and OP_CHECKDATASIGVERIFY, and this allows some pretty nifty spending constraints to be enforced, as has been outlined here. After I read it, I was immediately intrigued by the simplicity and possibilities it offers. I encourage y'all to have a look at it, so that my post will make more sense. I will outline the important stuff below, anyway.
The basic idea (shamelessly copied from that article) is to gain access to the transaction that's spending an output, like so.:
contract Constraint(Ripemd160 pkh) { challenge spend(PubKey pk, Sig sig, bin preimage) { verify hash160(pk) == pkh; verify checkSig(sig, pk); verify checkDataSig(sig, preimage, pk); } }
We verify that exactly the same signature verifies both the transaction itself and the "preimage". This by itself doesn't do anything useful (it really just wastes space on the blockchain), but if we e.g. want to ensure that some contract on this coin should be fulfilled for it's whole life, we can add additional stuff. The preimage consists of the following, according to the spec:
- nVersion: Version of the transaction
- hashPrevouts: Double SHA256 of the serialization of all input outpoints (if not ANYONECANPAY)
- hashSequence: Like hashPrevouts, but for the sequence number for the input
- outpoint: Transaction hash + output index of the input this (output) script will receive as input
- scriptCode of the input: This (output) script itself!
- value of the output spent by this input: Amount the input provides for this transaction
- nSequence of the input: Sequence number of the input
- hashOutputs: Double SHA256 of all output amounts paired with their output scripts of this transaction (if not SINGLE or NONE)
- nLocktime of the tx: Locktime of this transaction
- sighash type of the signature: Contains the fork id, and if this signature is ANYONECANPAY, ALL, SINGLE and/or NONE.
Forever looping transaction
Using scriptCode and hashOutputs, we can do some interesting stuff. Lets assume we have some function that decomposes our preimage into the above components (would be done with many OP_SPLITs, but that gives me a headache, so I assume it would give you one, too, and I don't want to inflict unnecessary pain to you). So how about this contract?
contract ForeverTheSame() { challenge spend(PubKey pk, Sig sig, bin preimageSerialized) { verify checkSig(sig, pk); verify checkDataSig(sig, preimageSerialized, pk); Preimage preimage = decomposePreimage(preimageSerialized); verify hash256(preimage.value . preimage.scriptCode) == preimage.hashOutputs; } }
Let's look at the verify line:
verify hash256(preimage.value . preimage.scriptCode) == preimage.hashOutputs;
This constrains the spending transaction to have the exact same output as the input transaction's output. That way, this transaction output can only ever be spent by a transaction that has exactly the script above as output. We're also enforcing that the same amount has to be sent each time. How useless! And fun. This would be the equivalent of the following while loop in Python:
while True: pass # do nothing, just spin till terminated or heat death
Note that I removed the verify hash160(pk) == pkh; line, so, actually, any signer could create a valid signature. Anyone could keep the loop spinning! But no one could terminate it...
If we were to change the verify line to:
verify hash256(num2bin(bin2num(preimage.value) - 100) . preimage.scriptCode) == preimage.hashOutputs;
This would require the spending transaction to spend 100 less than it did in the input. If we started with 1000 Satoshis for our initial output, we could loop for 10 times (if there was no dust limit). Our Python equivalent would be the following:
for satoshis in range(1000, 0, -100): # go from 1000 down in 100 steps pass # we could do something useful here, but we chose to do nothing instead
Again, anyone could keep the loop spinning, until all satoshis have been siphoned away.
Wait a minute! Oddly enough, it looks like we are able to do loops in Bitcoin after all! I didn't intend this before starting to write this post, but it seems like we've just accidentally proved Script to be Turing complete (at least when we're allowed to do multiple transactions, and let's be generous, please).
Chess
Now back to chess. If we were to implement a game in Python, we'd write something like the following:
board = [['R', 'N', 'B', 'K', 'Q', 'B', 'N', 'R'], ['P', 'P', 'P', 'P', 'P', 'P', 'P', 'P'], [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '], [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '], [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '], [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '], ['p', 'p', 'p', 'p', 'p', 'p', 'p', 'p'], ['r', 'n', 'b', 'k', 'q', 'b', 'n', 'r']] # ^-- also other stuffs, such as "can still do castling" and "can do en passant" etc. while True: white_move = input('White move: ') if white_move == 'surrender': send(1000, blacks_address) break board = apply_move(board, white_move) if white_has_won(board): send(1000, whites_address) break if is_stalemate(board): send(500, whites_address) send(500, blacks_address) break black_move = input('Black move: ') if black_move == 'surrender': send(1000, whites_address) break board = apply_move(board, black_move) if black_has_won(board): send(1000, blacks_address) break if is_stalemate(board): send(500, whites_address) send(500, blacks_address) break
That's quite a bit! The really juicy parts, of course, are apply_move, white_has_won, black_has_won and is_stalemate, but we'll leave those out, because they are way too juicy right now. Also, I've left out the part where both agree on a draw.
Let's try to do the while/if/break part first:
while True: white_move = input('White move: ') if white_move == 'surrender': send(1000, blacks_address) break
contract LoopAndBreak(Ripemd160 pkh, bin hashSend1000ToBlack) { challenge spend(PubKey pk, Sig sig, bin preimageSerialized, bin whiteMove) { verify hash160(pk) == pkh; // <-- need to ensure this is actually our white player! verify checkSig(sig, pk); verify checkDataSig(sig, preimageSerialized, pk); Preimage preimage = decomposePreimage(preimageSerialized); if (whiteMove == 0x73757272656e646572) { // 'surrender' encoded verify (hashSend1000ToBlack == preimage.hashOutputs); } else { verify (hash256(preimage.value . preimage.scriptCode) == preimage.hashOutputs); } } }
Let's look at that in detail.
if (whiteMove == 0x73757272656e646572) { // 'surrender' encoded
This checks if white's move is 'surrender'. If yes, we continue with this:
verify (hashSend1000ToBlack == preimage.hashOutputs);
We get a script that sends 1000 Satoshis to black as template input into the contract, now we verify that this script is the actual output script.
After that comes our already familiar
verify (hash256(preimage.value . preimage.scriptCode) == preimage.hashOutputs);.
This ensures that the loop keeps spinning otherwise.
What do we have now? A very skewed game. White has two options: First, make a move (any move, at least that's that!) and continue. Second, surrender and lose 1000 Satoshis. Sounds like a game where the only winning move is not to play, at least for white.
The next line is:
board = apply_move(board, white_move)
This innocuous looking line is actually quite a challenge to do on Bitcoin, but we'll try anyway. Or exactly because of that.
For that, we need to encode the board in the transactions' OP_RETURN part.
contract LoopAndApplyMove(Ripemd160 pkh, bin hashSend1000ToBlack) { challenge spend(PubKey pk, Sig sig, bin preimageSerialized, bin whiteMove, bin previousTxBefore, // <-- previous transaction part 1 bin board, // <-- current board (as part 2 of the previous transaction) bin previousTxAfter, // <-- previous transaction part 3 bin previousTxOutpointIndex) { // <-- previous transaction output index (<-- useful comment) verify hash160(pk) == pkh; verify checkSig(sig, pk); verify checkDataSig(sig, preimageSerialized, pk); Preimage preimage = decomposePreimage(preimageSerialized); verify hash256(previousTxBefore . board . previousTxAfter) . previousTxOutpointIndex == preimage.outpoint; // ^-- verify the given board is actually the one in the previous transaction if (whiteMove == 0x73757272656e646572) { // 'surrender' encoded verify hashSend1000ToBlack == preimage.hashOutputs; } else { bin newBoard = applyMove(board, whiteMove); // <-- apply the move to the board verify hash256(preimage.value . preimage.scriptCode . 0x0000000000000000 . newBoard) == preimage.hashOutputs; // ^-- verify the new board is part of the OP_RETURN part of the next transaction } } }
Phew! That's quite a mouthful. Let's go through it.
verify hash256(previousTxBefore . board . previousTxAfter) . previousTxOutpointIndex == preimage.outpoint;
As you can see in the challenge parameter list, there are five new parameters. The last 4 are all needed to access the previous transaction, that is the one this transaction spends an output of. When we concat previousTxBefore, board and previousTxAfter, we get back exactly the bytes of that transaction. By the naming, you should already be able to tell which one of those is our board.
So, hash256(previousTxBefore . board . previousTxAfter) gives the transaction hash. Concat this with previousTxOutpointIndex to get a so called outpoint. We check that this outpoint matches this transaction input's outpoint!
bin newBoard = applyMove(board, whiteMove); // <-- apply the move to the board
This assumes we have a function applyMove which takes a serialized board and returns a new board which has the move applied. This function is really juicy, since it must also ensure the move is valid, encode/decode the board and move etc. Maybe we'll come to that later.
verify hash256(preimage.value . preimage.scriptCode . 0x0000000000000000 . newBoard) == preimage.hashOutputs;
Ouch, so many zeros! (8, in bytes, to be precise). This now enforces an additional output compared to the contract we had above: An output that spends 0 Satoshis and has newBoard as output script. This output script, of course, should be an OP_RETURN transaction, otherwise the transaction would be rejected by the network.
The next part in Python is the following:
if white_has_won(board): send(1000, whites_address) break
Let's add that to our contract! Again, we'll assume there's a function whiteHasWon that checks if, given a board, white has won. That means if whether black's king is in checkmate.
contract LoopAndCheckWin(Ripemd160 pkh, bin hashSend1000ToWhite, bin hashSend1000ToBlack) { challenge spend(PubKey pk, Sig sig, bin preimageSerialized, bin whiteMove, bin previousTxBefore, bin board, bin previousTxAfter, bin previousTxOutpointIndex) { verify hash160(pk) == pkh; verify checkSig(sig, pk); verify checkDataSig(sig, preimageSerialized, pk); Preimage preimage = decomposePreimage(preimageSerialized); verify hash256(previousTxBefore . board . previousTxAfter) . previousTxOutpointIndex == preimage.outpoint; if (whiteMove == 0x73757272656e646572) { // 'surrender' encoded verify hashSend1000ToBlack == preimage.hashOutputs; } else { bin newBoard = applyMove(board, whiteMove); if (whiteHasWon(newBoard)) { // <-- check if whiteHasWon verify hashSend1000ToWhite == preimage.hashOutputs; // ^-- if yes, must send to white } else { verify hash256(preimage.value . preimage.scriptCode . 0x0000000000000000 . newBoard) == preimage.hashOutputs; } } } }
That's a small change, this time.
if (whiteHasWon(newBoard)) { // <-- check if whiteHasWon verify hashSend1000ToWhite == preimage.hashOutputs; // <-- if yes, must send to white }
This if block ensures that white get's his money once he's won the game. Note, we could actually leave that out and not place any rules on the output, since it's white that has won! I just placed it here for a better understanding. This contract is already complicated enough. Also, it gets relevant at the end again, so bear with me.
Sir, it seems like we're in a stalemate
Now the next part should be trivial, right? Just the same as before with different output!
if is_stalemate(board): send(500, whites_address) send(500, blacks_address) break
Well... yes and no. See, it's really difficult to check for a checkmate, because you have to go through all possible moves the king can do, and check for each of those moves if one of the possible moves of a piece can capture the king from that place and... Well, it's just not pretty. And doing it in Script would certainly exceed a lot of limits put on scripts (such as the 200 opcode limit, which we'd probably violate anyway).
Therefore, we'll check for checkmate in a simpler, more crude but accurate fashion: Whether the king has been captured. "Ugh!", I hear people say, "How ugly!". "Shut up", I reply. This is not a challenge for aestetics. And if you have to capture the king in order to win your 1000 Satoshis, you'd quickly disregard all sorts of aestetics in Bitcoin Script. Mmh Satoshis.
So, now that we know how we'd implement whiteHasWon (i.e., by checking if there's no black king anymore), there's a problem with the stalemate. A stalemate is exactly like a normal (non-captury) checkmate, only that the king is not in check and no other move is possible. However, this time, we have the same problem as with whiteHasWon: it's really hard to check if there are no moves left for the king (and any other piece) anymore!
We solve this in the following way: If there's a stalemate, both players just agree it's a stalemate and split the money.
Huh? That's supposed to work? After all, we've gone through all of that by doing exactly not that: The rules are in the script, not some agreement between players enforced by honor and loss of face alone.
However, we have to look it from the view of game theory (at least that very small part I get). If white is in stalemate, then the only valid move (according to our "king-captury" rules) would be to lose the king and thus the Satoshis, so he wouldn't do that. Black can't do a move either, because it's white turn. This means neither white nor black can get any of the 1000 Satoshis, except if they agree to a draw and split the money.
Also, we need a way for players to agree on a draw anyways, so that's covered in the same stroke.
"Show me some code!", you yell impatiently after such a long passage, and I reply calmly:
contract LoopAndAllowDraw(Ripemd160 pkhWhite, Ripemd160 pkhBlack, bin hashSend1000ToWhite, bin hashSend1000ToBlack, bin hashSendDraw) { challenge spend(PubKey pkWhite, Sig sigWhite, PubKey pkBlack, Sig sigBlack, bin preimageSerialized, bin whiteMove, bin previousTxBefore, bin board, bin previousTxAfter, bin previousTxOutpointIndex) { verify hash160(pkWhite) == pkhWhite; verify hash160(pkBlack) == pkhBlack; verify checkSig(sigWhite, pkWhite); Preimage preimage = decomposePreimage(preimageSerialized); if (checkSig(sigBlack, pkBlack)) { // <-- check if black has also signed verify hashSendDraw == preimage.hashOutputs; } else { verify checkDataSig(sigWhite, preimageSerialized, pkWhite); verify hash256(previousTxBefore . board . previousTxAfter) . previousTxOutpointIndex == preimage.outpoint; if (whiteMove == 0x73757272656e646572) { // 'surrender' encoded verify hashSend1000ToBlack == preimage.hashOutputs; } else { bin newBoard = applyMove(board, whiteMove); if (whiteHasWon(newBoard)) { verify hashSend1000ToWhite == preimage.hashOutputs; } else { verify hash256(preimage.value . preimage.scriptCode . 0x0000000000000000 . newBoard) == preimage.hashOutputs; } } } } }
Now, what about black? Well, we'll just encode which player's turn it is in the board, and add a challenge for black. Each challenge then also has to verify that it's the current player's turn.
A word on incentives
As you might have thought, there's one problem: If black knows he has lost, there's no reason for him to make a move, leaving the 1000 Satoshis forever locked on the blockchain, impossible to be claimed by white. Now, you'd think we could just add a lock time for white to spend the money after x amount of time has passed, but then our trick with the stalemate doesn't work anymore. Also, noone would have an incentive to ever accept a draw (as the last mover could just wait until the time has run out and claim all the money).
Therefore, we'll just change hashSend1000ToWhite to also send some money to black, and vice versa for hashSend1000ToBlack. That way, the person with the losing position would rather surrender (or play until the end) and get a small compensation, than lose all of his money. This compensation should be large enough to overcome the inconvenience of surrendering and hurt feelings, but shouldn't be too high to spoil the fun of winning 1000 Satoshis for the winner.
And that's it.
I hope I was able to convey my idea in an understandable way and hope you've enjoyed it! Tell me if you want to see the part which elaborates on applyMove and whiteHasWon/blackHasWon.