Before my first day as a Blockchain architect for the banking industry in Sydney, I visited a bar. It happened to be on ANZAC day — the Australia National day of remembrance. I watched, beer in hand, folks playing two-up. When I finally decided to join in, the sun went down, and the two-up gambling in bars had to stop, as it is the local legal requirement. I was inspired to look for a way to play the game after dusk, or even more excitingly, over bitcoin.
It’s a simple game, people toss two coins at a time, and bet which sides will be up. I must declare, despite the terrible die-hard reputation of Chinese gamblers, what inspired me to study how to toss bitcoins is pure curiosity, not the mere rancour of not being able to try a hand at dusk! It turned out that tossing a bitcoin is not straightforward at all, not to mention tossing two of them at once, but it was a joyful adventure and mentally stimulating to find out how. The research in coin-tossing methods is an age-old one, and the solution on bitcoin was finally pieced together by a group of cryptographers in the University of Warsaw†. I write this blog in an attempt to bring this intellectual pleasure to a wider audience. My dear readers, grab a coffee and sit comfortably before continuing! This adventure is going to test your knowledge of how bitcoin works, challenge your presumptions and excite the senses! The Difficulty of Source of Randomness The amazing invention of bitcoin has a programming language behind it, with every unspent bitcoin locked by a piece of software program. For every attempt to spend a piece of money, typically by using a key, a program that makes up that piece of money is executed that requires the sender to prove that he or she has the key. If the proof evaluates to “True”, the money is moved to a new address. The program that dictates the flow of money has a proper name called “smart-contract”. It looks like regular software program and is executed on the computers of the miners. In bitcoin, it is a part of each individual pieces of money, serving as a lock to the very money, setting the condition how it can be spent, thus I find “locking script” an appropriate name. In other systems, like Ethereum, “smart-contract” is not written on money, but is a separate entity, which money goes into and comes out of. Typically, this piece of “locking script” does only one thing: given a signature, it checks whether or not the signature matches the imprint of the money’s owner’s key. There are more complicated locking scripts, such as multi-sig, where the program requires multiple signatures at once (often two out of three) to unlock the fund. To demonstrate this, let’s imagine a group of three accountants and a safe that can be opened only when at least two of the accountants are presents. A multi-sig locking script would enable them to do so. Let’s consider the case of tossing a bitcoin from a minimum design: The combined wage from Alice and Bob is locked together with such a locking script, that it can only be unlocked by an input and a signature. If the input is 0, which means coin falls head-up, Alice can unlock the fund providing her signature; if the input is 1, which means coin falls tail-up, Bob can unlock the fund providing his signature. However, this design has one problem: who gives the input, be it 0 or 1? bitcoin’sdesign requires transaction accuracy, and a bitcoin locking script leaves no space for randomness. The lock itself cannot generate an input representing the side of a coin. Since we have only two parties here, Alice and Bob, the input must be determined by them. If Alice can provide the input solely, she can lie about it to her advantage, and the same goes for Bob; the input must, therefore, come from both of them. Manuel Blum, a famous cryptologist and 1995 Turing Award winner, invented a simple way to solve the problem: Let Alice say a number to Bob, and Bob say a number to Alice. Let us add the two numbers, if it turns out to be even, we say the coin falls head-up; if it is an odd number, we say the coin falls tail-up. Since Alice doesn’t know Bob’s number, she cannot produce a number to her advantage. Equally, Bob doesn’t know Alice’s number, and can do nothing to increase his odds. Here is the program code for the locking script, described in plain English: Name: the locking script on the wager. Input Alice’s number, and make sure that it really is from Alice by requiring Alice to sign it. Input Bob’s number, and make sure that it really is from Bob, by requiring Bob to sign it. Check the sum of A and B. If they add up to an odd number, unlock the fund to anyone who can prove Alice’s signature, which effectively means Alice only. Otherwise, unlock the fund to anyone who can prove Bob’s signature. The Difficulty of Preventing Lying But this method begets a problem: who will say the number first? Let’s remember that a bitcoin locking script can’t talk secretly. If Alices bet on an odd number, and she says 35, Bob could (and would likely) change his mind and simply say 1, as the sum would be an even number of 36, and Bob could obtain the money. There has to be a way to prevent either side from changing their minds when they learn of the other party’s number And it turns out that there is a common solution: hash. Let’s recall hash: for any fixed given data, its hash is a fixed large number. It has 2 properties: First, the smallest change in the data itself will completely change the hash. Secondly, knowing the hash does not reveal the data. A true cryptologist will point out that for the latter, the hash needs to be salted, which is beyond this introductory discussion. (See Cryptograph Commit [wikipedia] for further information.) Our coin tossing process becomes a bit more complicated with hashing. First, Alice and Bob must exchange the hash of their numbers. Then, both of them will send the wager to an address locked by the following locking script: Name: the locking script on the wager. Input Alice’s number, check that its hash matches what Alice told Bob before. This makes sure that Alice didn’t change his number. Input Bob’s number. [ditto] Check the sum of A and B. If it is an odd number, unlock the fund to anyone who can provide Alice’s signature, which effectively means Alice only. Otherwise, unlock the fund to anyone who can provide Bob’s signature. Now, neither Alice nor Bob will be able to make up a different number when they learned the opponent’s, since the slightest change in the data will result in a completely different hash, and the fund will remain locked. The Difficulty In Preventing Loser From Quitting What if Bob, having learned of Alice’s number, and knowing that he is the loser, decide to quit suddenly? Remember that the locking script requires Bob’s number to match the hash he provided earlier. If Bob doesn’t show up and supply the number, this contract will be locked for eternality. There is no such a shortage of dead locks on Blockchain. Blockchain is made of locks, on which there are more dead locks than what you can find on Pont des Arts (Paris)! It is estimated that 5% of the bitcoins in existence are forever locked. Bob may think that if he can’t win the money, he will not let Alice get it. What I can’t have, no one can. The cryptographers in University of Warsaw has invented another solution to the problem, which involves 3 locks, and accordingly, 3 pieces of money. They are: Alice’s ante, Bob’s ante, Alice and Bob’s wager. First, Alice and Bob exchange hashes of their number, but not reveal the number at that stage. Then, Alice can require Bob to prepare the ante, with the following locking script: Name: the locking script on Bob’s ante Input a number, check that its hash is equal to Bob’s hash. If so, Unlock the fund to anyone who can prove that he has Bob’s key (i.e. Bob himself). Then, Bob requires Alice to prepare an ante, with a locking script just like that one. So far, both people have depsited ante, and both can reclaim them back by providing their number to the locking script. Now we have two locks. The third lock will be exactly what we have seen, which checks the sum of Alice’s and Bob’s number and distribute the wage. If Bob decide to quit, he will want to have his deposit back, and the only way to redeem his deposit is to reveal his number to the locking script on his deposit. As scandalous as bitcoin’s Blockchain famously be, once it is revealed to the locking script, it is revealed to the world. Alice learns the number — the only missing key to unlock the fund — and takes her reward. The Difficulty of Making Sure The Game Has An End Now, Bob in this case is surprisingly sneaky. He decided that he doesn’t want his deposit back — until the moment he needs it. Since he has quite a few bitcoinsin his pocket, the time he is desperately needing this deposit could be a few years away, and in the meanwhile, Alice has to wait for her reward. Perhaps anticipating such need, bitcoin’s programmable lock not only contains programs, it also have a timer. The simplest way to explain the use of a timer is perhaps by a will. Suppose an old man wishes to leave a big purse of bitcoins to his son, but does not want him to touch it until he is 35 years old, lest he be spoiled in his younger days, he can set the timer to that particular transaction which moves his funds, keep the seed of the key in his head, and die in peace, without revealing the key to his son and without needing to trust a third party to execute the will. bitcoin’s amazing capacity to lock events in its Blockchain timeline provides the guarantee that the funds can’t be touched before that time, unless the old man, who possesses the key, changes his mind and write a new will with it. In practice, we rarely see such a telltale use of the timer. Most timers on the bitcoin locks are set to the near future: minutes, hours or a few days away. They serve short term purpose. There are a lot short-term cases such as paying security deposit for a payment channel, much like paying a hotel reservation. In this article we focus on its use to deposit wage. So before we toss a bitcoin, we wish to let each party pay an ante, and we wish that the ante can expire. When it expires, the money goes to the adversary, and not redeemable by the original owner. bitcoin’s time lock only serve to make a transaction possible after a certain time, not to make it impossible after certain time — if it is the latter, we wouldn’t be able to make a rule to force something happen after expiration. When the ante expires, we will need a promise, a transaction to transfer the ante to the adversary. Certainly, this promise has to be given to the adversary ahead of the game, and it needs to have a time lock described above. To allow such a promise, our ante money will look different: If Bob decides not to reveal his losing number, the timer will be triggered and within a stipulated time that is reasonable, Alices gets her reward. [to be continued] Name: the locking script on Bob’s ante Input a number, check that its hash is equal to Bob’s hash. If so, unlock the fund to anyone who can prove that he has Bob’s key (i.e. Bob himself). Otherwise, unlock the fund to anyone who can provide both Bob’s and Alice’s signature. (Think: will this be Bob or Alice?) And the promise. Bob sends the promise to Alice, which is a transaction that uses the ante and sends it to Alice, after a certain time — let’s say one day. Bob signs it, and sends it to Alice. Alice signs it too, and now it is a valid promise. There are now only two ways to get the ante:
- Provide the correct number, then Bob can get it.
- Provide both Alice and Bob’s signature, then Alice can get it. Upon this Alice can prepare her ante too, and send her promise to Bob. At this moment, either can bail out without losing any money, by simply revealing their number, and there is no harm to do so, since the game hasn’t started. When each party prepared the ante and acquired the others time locked promise, they can start the game, by both party sending their wager, which uses the aforementioned wager locking script. This way, if the loser chooses not to reveal his number, forever, then his ante goes to the adversary, making him lose two, instead of one, bitcoin! Any rational player wouldn’t do this! The Difficulty In Money Efficiency The introduction of ante has two implications: First, if the loser, against his own financial interest, decide to let his ante money go, then the wager will still be locked forever. This may not be a problem, since getting a bitcoin out of circulation benefits every other bitcoinholder, same way like burning a country’s money (illegal in some countries) deals a profit to every other fellow countrymen. The computer memory to store this lost bitcoin may be a neglectable cost. Second, for one to play a hand of coin tossing, he actually needs two coins! This means the players who have only one coin left will not be able to play. This is a problem. Is there a solution to the problems? Yes there is. Despite that we are so close to the final solution, it is grander than what I can’t fit in a blog post like this, thanks to additional required background knowledge. But since we are doing a blog post here, I’ll be doing just enough by pointing out the academic work which includes that solution. The paper is “Secure Multiparty Computation on bitcoin” — as usual, the title doesn’t give any clue to a layman on what it is about. It was published on April 2016 edition of Communications of the ACM. † The cryptographers are: Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, Łukasz Mazurek Slides (Chinese) can be downloaded here: How To Toss a bitcoin WeiWu Zhang — Biosnap: Weiwu Zhang is an encryption and distributed computing technology expert. He is a Blockchain architect and an open-source advocate involved in a broad range of projects from FinTech solutions to IoT. Weiwu has a wealth of experience serving enterprises from governmental and financial institutions to innovative startups. He is often speaking in international conferences on topics such as digital identity, security and disruptive data sharing technologies.