Activity 17

The Peruvian Coin Flip—Secret Codes for Fair Choices

Age group: Older elementary and up.

What you should know already: You should be able to count and know odd and even numbers. It helps to understand the words "and" and "or." You'll get more out of this activity if you already know binary numbers (numbers made of just 0s and 1s), the idea of parity (whether a number of things is odd or even), and how a "one-way" math trick works (something easy to do one way, but very hard to undo).

Time: About 30 minutes.

Group size: Works for one person or a whole class.

What this activity is about:

• Logic with "and" and "or"
• Functions (math rules that turn an input into an output)
• Solving puzzles

Summary

This activity shows a clever way to solve a tricky problem: how can two people who don't fully trust each other—and who can only talk by phone—flip a coin fairly?

Some new words you'll learn: distributed coin-tossing, computer security, secret codes (cryptography), a set of coded rules (protocol), and-gate, or-gate, and a circuit made of gates.

What you'll need

Each group needs:

• A copy of the worksheet on page 183
• About two dozen small buttons or counters in two different colors

The Story

Two soccer teams—one from Lima and one from Cuzco—need to decide who gets to play at home for the championship game. Normally, they'd just flip a coin. But the cities are far apart, and Alicia (from Lima) and Benito (from Cuzco) can't meet in person just to flip a coin.

Could they do it over the phone instead? Alicia could flip the coin while Benito guesses heads or tails. But there's a problem: if Benito guesses heads, Alicia could just say "Sorry, it was tails!"—and Benito would never know if she was telling the truth. Even if Alicia is usually honest, this is an important game, and the temptation to cheat is strong. And even if she were truthful, would Benito believe her if he lost?

Here's what they decide to do instead. Together, they build a special "circuit" made of and-gates and or-gates (explained below). They could even do this over the phone, though it might take a while! While building the circuit, both Alicia and Benito want to make sure it's tricky enough that the other person can't cheat. Once it's built, everyone can see the design—it's not a secret.

How Gates Work

The rules for and-gates and or-gates are simple. Each gate takes two inputs and gives one output (see Figure 17.1). Each input is either a 0 (meaning "false") or a 1 (meaning "true").

• An and-gate only outputs a 1 (true) if both inputs are 1. Otherwise, it outputs a 0.
• An or-gate outputs a 1 (true) if either input is 1 (or if both are). It only outputs a 0 if both inputs are 0.

For example, in Figure 17.1, the and-gate has a 1 and a 0 going in, so its output is 0. The or-gate has the same inputs (0 and 1), but its output is 1.

You can connect the output of one gate to the input of another gate, making more complicated circuits. In Figure 17.2 (left side), two or-gates feed into a third or-gate. This means if any of the four starting inputs is a 1, the final output will be a 1. In the right-hand circuit, the outputs from two and-gates feed into two more gates below, so this circuit has two separate output values.

For the Peruvian coin flip, we need an even bigger circuit. The one on the worksheet (page 183) has six inputs and six outputs. Figure 17.3 shows an example of how it works with one set of input numbers.

How to Flip the Coin Using the Circuit

Here's how Alicia and Benito use this circuit to make a fair coin flip:

1. Alicia picks six numbers (each a 0 or 1) as her secret input. She keeps this secret.
2. She runs these six numbers through the circuit and sends Benito the six numbers that come out (the output).
3. Benito looks at the output and tries to guess something about Alicia's secret input: whether it has an odd or even number of 1s in it. This is called guessing the parity.
4. If the circuit is complicated enough, Benito can't figure out the answer for sure—so his guess is basically random. (He could even flip a real coin to help him guess!)
5. If Benito guesses correctly, he wins, and the game will be played in Cuzco. If he guesses wrong, Alicia wins, and the game will be played in Lima.
6. After Benito guesses, Alicia reveals her secret input. Benito checks that it really does produce the output she sent him.

Try It Yourself

1. Split into small groups. Give each group the circuit and some counters. Explain the story above. It might help to imagine a real team captain arranging this coin flip with a rival school. Pick a color code—for example, red counters mean 0, and blue counters mean 1. Write this down at the top of your worksheet so you don't forget.

1. Set up the inputs. Show how to use counters to represent Alicia's six secret numbers on the input spots. Then go over the and-gate and or-gate rules (they're summarized at the bottom of the worksheet—you might want to color them in).

1. Work through the circuit. Carefully place counters at each step to figure out the final output. This takes patience! (Table 17.1, which shouldn't be shown to the kids, lists every possible input and its matching output, just in case you get stuck.)

1. Play the game. Have each group pick one person to be Alicia and one to be Benito (or split into two teams). Alicia picks a random six-digit input, works out the output, and tells Benito the output. Benito guesses whether Alicia's input had an odd or even number of 1s. You'll notice that Benito's guess is pretty much a random shot in the dark. Then Alicia reveals her actual input. Benito wins if he guessed the parity correctly. He can also check that Alicia didn't switch her input by making sure it produces the output she originally gave him.

That's it—the coin flip is complete!

Can Someone Cheat?

Could Benito cheat? Yes—if, given the output, he could figure out exactly what input made it. That's why it's important for Alicia that the circuit works like a "one-way" function (like the one in Activity 14): easy to calculate going forward, but very hard to reverse.

Could Alicia cheat? Yes—if she could find two different inputs (one with even parity, one with odd) that both give the same output. Then no matter what Benito guesses, she could claim whichever input makes him wrong! That's why Benito wants to make sure the circuit doesn't let many different inputs produce the same output.

Looking at the Example Circuit

1. Try to find ways to cheat. Look at the first line of Table 17.1. You'll see that several different inputs give the same output, 010010—for example, 000001, 000011, and 000101. This means if Alicia gets this output, she could pick input 000001 if Benito guesses "even," or 000011 if he guesses "odd." She can cheat!

However, this circuit isn't perfect for Benito either. If the output happens to be 011000, checking the table shows there's only one possible input that could have made it: 100010. If Alicia happens to get this exact output, Benito could guess "even parity" and be guaranteed to win!

A real computer system would use many more digits, so there would be far too many possible inputs to check by hand (every extra digit doubles the number of possibilities).

1. Design your own circuit! Have groups try building their own version of this game's circuit. Can they design one that makes it easy for Alicia to cheat? Can they design one that makes it easy for Benito to cheat? The circuit doesn't have to have six inputs—it could have more or fewer, and even a different number of inputs than outputs.

More Ideas to Explore

1. One tricky part of this whole idea is that Alicia and Benito have to work together to build a circuit they both trust. That might be fun for a game, but it would be a hassle to do for real—especially over the phone! Luckily, there's a simpler way: Alicia and Benito can each build their own circuit separately, and show everyone how their circuits work. Then Alicia runs her secret input through both circuits. She compares the two outputs digit by digit—wherever the digits match, she writes a 1; wherever they don't match, she writes a 0. This combined result becomes the final output. With this method, neither person can cheat unless the other person also built a cheat-friendly circuit—because if even one of the two circuits is a strong one-way function, the combined circuit will be too!

The next two ideas aren't about coin flips or secret codes exactly—they're about circuits made of and-gates and or-gates in general. These ideas are important building blocks of both computer circuits and logic itself. This kind of logic is called Boolean algebra, named after the mathematician George Boole (1815–1864).

1. You may have noticed that if all six inputs are 0, the output is always all 0s. Likewise, if all six inputs are 1, the output is always all 1s. (Sometimes other inputs can also create these same outputs—for example, in our sample circuit, the input 000010 also gives all zeros, and 110111 also gives all ones.) This always happens with circuits built only from and-gates and or-gates. But if you add a not-gate—a gate that takes just one input and flips it (turning a 0 into a 1, or a 1 into a 0)—you can build circuits that don't have this pattern.

1. Two other useful gates are and-not and or-not. These work like and-gates and or-gates, but with a not-gate added at the end. For example, "a and-not b" means "not (a and b)."