This post was first published on Medium.
We have created a simulation of the Monty Hall problem on bitcoin. If you know the correct answer to a probability puzzle, you are compensated with monetary rewards in addition to showing off your mathematical skills than you would otherwise get. It runs completely on chain.
monty hall problem
The Monty Hall problem is a probability puzzle named after Monty Hall, who was the original host of the TV show Let’s Make a Deal. This is a famous counter-intuitive statistics puzzle that has a solution so absurd, most people refuse to believe it is being shown to be true. It works as follows:
Let’s say you’re on a game show, and you’re given a choice of three doors: Behind one door is a car; behind others, goats. You choose a door, say number 1, and the host, who knows what is behind the door, opens another door, say number 3, which contains a goat. Then he tells you, “Do you want to pick door number 2?” Is it to your advantage to change your preferences?
From Wikipedia, the free encyclopedia
Surprisingly, the odds are not 50-50. If you switch doors, you win 2/3 times! There are many articles/videos explaining the maths which we are not going to cover here. Some good examples are listed below.
width = “562” height = “315” frameborder = “0” allowedscreen = “allowed fullscreen”>
placement prospects 
Possible scenarios of stay vs switch
cryptographic doors
To emulate Monty Hall in Bitcoin, we need a way to hide the car/goat such that 1) the player cannot see what is behind each door; 2) The host cannot move the car/goat once the game has started. A commitment plan is a standard primitive for achieving both. We use a bit 1 to represent a car, and a bit 0 a goat. As always, we also generate a nonce for the bit, to prevent brute-force attacks.
execution
We have implemented the Monty Hall problem in a bitcoin smart contract using ScriptTS, a TypeScript DSL. Before the start of the game, both the player and the host lock up the same amount of bitcoins in the following contract¹. After the contract is in force, the game proceeds in the following phases:
The player chooses a door, say door 0, of course in the hope of the car. The host opens one door with a goat in the other two doors. The player decides whether he sticks to door 0 (the original guess) or remains closed. Switches on the door The host reveals the result: if the player picks the door with the car, he takes all the bitcoins in the contract; otherwise the host takes them.
monty hall contract
On line 25, the host sets the position of the car. He “opens” a door by forking the SHA256 commit. At the start of every public method, we ensure that the correct steps are followed sequentially. Line 51 uses the stateful contract technique.
If the game is repeated many times, a player who always chooses to stay will win about 1/3 of the time, whereas if he always switches he can improve his winning chances to 2/3.
What if the host cheats?
There are two possible ways the host can cheat:
(1) If the player correctly chooses the car in step 4, it refuses to open the door;
(2) He keeps three goats behind the doors and no car.
To prevent (1), we can use a timed commitment scheme, in which the host forfeits his deposit if he does not open a commitment before the deadline.
(2) can be stopped in the same way. The host eventually has to open all three doors and loses his deposit if they all open for the goats. Or he can explain to the player that there is exactly one car behind the doors, using the Zero Knowledge Proof, without revealing which door it is behind.
Comment:
[1] For ease of demonstration we ignore transaction fees, which can be easily incorporated into the contract, for example, using ANYONECANPAY.
See: Smart Contracts and Computation on BSV
width = “562” height = “315” frameborder = “0” allowedscreen = “allowed fullscreen”>
New to bitcoin? Check out CoinGeek’s Bitcoin for Beginners section, the ultimate resource guide for learning more about bitcoin – as originally envisioned by Satoshi Nakamoto – and blockchain.
