The Monty Hall Problem on Bitcoin: Put your money where your mouth is

Getting your Trinity Audio player ready...

This post was first published on Medium.

We have built a Monty Hall Problem simulation on Bitcoin. If you know the right answer to the probability puzzle, you are compensated with monetary rewards, besides showing off your mathematical skills as you only gain otherwise. It runs entirely on chain trustlessly.

The Monty Hall Problem

The Monty Hall problem is a probability puzzle named after Monty Hall, the original host of the TV show Let’s Make a Deal. It’s a famous counter-intuitive statistics puzzle that has a solution that is so absurd, most people refuse to believe even being shown it’s true. It works as follows:

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say №1, and the host, who knows what’s behind the doors, opens another door, say №3, which has a goat. He then says to you, “Do you want to pick door № 2?” Is it to your advantage to switch your choice?

Surprisingly, the odds aren’t 50–50. If you switch doors, you’ll win 2/3 of the time! There are many articles/videos explaining the math, which we do not dive into here. Some good examples are listed below.

Cryptographic doors

To simulate 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 car/goat after the game starts. A commitment scheme is a standard primitive for achieving both. We use a single bit 1 to represent a car, and bit 0 a goat. As usual, we also prepend a nonce to the bit, to prevent brute-force attacks.

Implementation

We have implemented the Monty Hall problem in Bitcoin smart contract using scryptTS, a TypeScript DSL. Before the game starts, both the player and the host lock equal amount of bitcoins into the following contract¹. After the contract is deployed, the game proceeds in the following steps:

1. The player picks a door, say door 0, hoping for the car of course
2. The host opens a door with a goat in the other two doors
3. The player decides if he sticks with door 0 (original guess) or switches to the remaining unopened door
4. The host reveals the result: if the player picks the door with the car, he takes all bitcoins in the contract; otherwise the host takes them.

Monty Hall contract

At Line 25, the host commits the car’s position. He “opens” a door by opening the SHA256 commitment. At the beginning of every public method, we ensure the right steps are followed sequentially. Line 51 uses the stateful contract technique.

If the game is repeated many times, a player chooses to always stay would win about 1/3 of the time, while he could improve his winning odds to 2/3 if he always switches.

What if the host cheats?

There are two possible ways the host can cheat:

(1) he refuses to open the door if the player rightly picks the car in step 4;
(2) he places three goats behind doors and there is no car.
To prevent (1), we can use a timed commitment scheme, in which the host forfeits his deposit if he does not open the commitment before a deadline.
(2) can be prevented similarly. The host has to open all three doors eventually and he loses his deposit if they all open to goats. Or he could convince the player there is exactly one car behind the doors using Zero Knowledge Proof, without disclosing which door it is behind.

NOTE:
[1] We ignore transaction fees for ease of exposition, which can be easily accounted for in the contract, e.g., by using ANYONECANPAY.

Watch: Smart Contracts and Computation on BSV