Equality by lot

This article assumes you’ve read my previous article “Large Scale Secure Sortition Part 1: Generating Randomness Collectively with In-Person Gatherings”. In particular it assumes a familiarity with the add-divide-remainder procedure for combining individual submissions to get a final random result.

This article explains the mathematical structure that makes collectively generating randomness difficult and introduces the four major approaches that can lead to systems that work. To do this we’ll go through a version of Cleve’s 1986 impossibility proof and call out the four major assumptions he makes as he makes them. Then we’ll explain how reversing each of those assumptions leads to a working method of collectively generating randomness and talk about its pros and cons.

In the world of CS theory the process of collectively generating randomness is called “multiparty coin flipping” and the seminal paper that kicked off the field was Cleve’s 1986 impossibility result. The paper proves that “it is impossible to have perfectly fair multiparty coin flipping unless a majority of those helping to ‘flip the coin’ are behaving honestly.” But if you keep digging you start finding papers that claim to have methods for fair multiparty coin flipping when just a single person is behaving honestly. Cleve’s proof was correct, but it made some specific assumptions about how those trying to flip the coin were able to structure their communications and what they wanted out of the process. Multiparty coin flipping is only possible if you take at least one of those assumptions and assume the opposite.

The first assumption is that at least half of the participants are dishonest (when we reverse this assumption later we assume that less than half of the participants are dishonest). Cleve is very upfront about this assumption and it is a good one to keep when thinking about designing sortition systems.

I’ll call out the other assumptions as the proof makes them. Let’s dive in.

The Proof

Imagine that Luka and Hugo instead of flipping a collective coin in person have to do it over text. The basic rules are the same: they both flip a coin, Hugo wins if they are both the same(heads heads or tails tails), Luka wins if they are different(heads tails or tails heads). If they both just send the results of their coin flip there’s a big problem. If Hugo sends his result (heads) first, Luka has the opportunity to lie about his (it actually came up heads, but he can say tails) and win unfairly. Or vice versa. Maybe they can agree to both send their result at exactly 12:00, but because online messages can take several seconds to arrive Luka might not be able to tell the difference between a message actually sent at 12:00 and one held back a moment and changed. If we are defining a formal way of collectively generating randomness online we have to assume that they trade off talking (Luka talks, then Hugo talks, then Luka talks). There’s no way to ensure any desired overlap. (This is the proof’s second assumption, and it’s a good one for online communication).

So they can’t just send the results of their coin flips, but maybe there’s some other way they can flip a coin over text. Maybe we can come up with a dynamic script: a structured series of texts that Luka and Hugo trade off sending that allows them to carry out a coin flip. We would want this script/system to have two properties. #1: if neither of them cheat the result should be heads half the time and tails the other half, and #2: even if one person cheats the other person should be able to finish the script and still end up with heads half the time and tails the other half. What Cleve proved is that this is impossible. There are no scripts with both of these properties. Here’s why:

Let’s imagine that scripts like this did exist, well then there must be a shortest script. Shortest in this case meaning the one with the fewest times Hugo and Luka switch who’s sending messages. Let’s imagine Luka and Hugo use that shortest script. Let’s zoom in on the moment before the last message is sent in a “reading of the script” in which no one has cheated yet. Let’s assume the script says that it’ll be a message from Hugo to Luka. And further, let’s assume that (unlike in the previous example) Hugo wants the result to be heads while Luka wants the result to be random. Because Hugo isn’t going to hear anything more from Luka before the “coin lands”, he has all the information he needs to know how the coin should land (this is the proof’s third assumption: that Hugo having all the information he needs to figure out how the coin should land is the same as him knowing how the coin should land). All that’s left for him to do–if he’s behaving honestly–is to send a message to Luka with the last bits of information Luka needs to also know how the coin should land.

However if Hugo can see that being honest will result in tails then he has a sneaky option. He can choose not to send his final text. If Hugo doesn’t send the text, Luka is left with a conundrum. One option would be to say “Luka can just flip a coin on his own and go with that” but that’s not actually fair. In the 50% of the time where the coin was about to come up heads he’d have sent his final text. And now in the 50% of the time where they were about to flip tails Luka will end up flipping heads 50% of the time as well. This means Luka will end up with heads 75% of the time. That’s clearly not fair. So Luka can’t just flip a coin. He has to guess what the result would have been if Hugo had sent the final message (the proof’s fourth and final assumption is that Luka actually did want the result to be random, if he did have a preference at this point he could just “guess” his preferred result). 

Unfortunately Luka will sometimes guess wrong. If he always guessed right that would mean he had all the information he needed and then Hugo wouldn’t have needed to send his final text. But we said that the script they were using was the shortest possible working script. If Hugo didn’t need to send the last message then there is a shorter script where he doesn’t. This means that there is no shortest script with both properties and that means that there are no scripts with both properties at all.

The Assumptions

Cleve’s first assumption was that at least half of the participants are dishonest and willing to stop texting if they think they aren’t going to get their way. When a majority of them are honest there is a method for doing coin flipping using a tool called “Verifiable Secret Sharing”. However this assumption is a really good one to keep when we are thinking about developing sortition systems. The systems that assume a majority is honest can be completely taken over by a majority trying to subvert them. This reintroduces an element of majority rule into a sortition environment where it doesn’t belong.

The second assumption was that participants cannot communicate simultaneously. This is a natural assumption if you are communicating online. And this is why my proposed system from the first article in this series cannot be moved online. At the end of the day networks just aren’t reliable or consistent enough for them to successfully make the transition work. If a single honest party is enough to ensure full randomness, then the last message must be able to change the final answer to any option. But that means the last submitter can have full control if they are able to see all the other submissions. This makes trying to achieve a simultaneously reveal online just too much of a risk.

The third assumption was having all the information Hugo needed to know the final answer was the same thing as knowing the final answer. That doesn’t necessarily follow. If I hand you a QR code broken up into puzzle pieces you have all the information that you need to scan the QR code, but doing so is going to take you some time. What that bit in the proof assumes is that Hugo can take all that time he needs to process the information he has, solve any puzzles he needs to solve, and Luka won’t notice. If it would take Hugo 2 hours to solve the puzzle Luka’s hidden his submission in and Luka only gives him an hour to get back to him, then Hugo can’t bias the coin flip. Because at the end of the hour Hugo has to decide whether to reply or not without knowing what the final answer will be. If he chooses not to reply Luka’s coin flip is 50/50 heads or tails as before. But if he chooses to reply it’s still 50/50 heads or tails. When we reverse the underlying assumption that Luka will let Hugo take all the time he needs, we end up with the proposed method in the second article of this series.

The fourth and final assumption was that Luka wanted the result to be random instead of wanting the result to go his way. If instead we assume that even honest participants have preferences then we are in the realm of “Game Theoretic Multiparty Coin Flipping” or “Leader Election”. These areas look promising and have methods that work. The main problem with using the tools from these areas is that they seem to allow something like vote buying. In these systems participants may be able to sacrifice their chance at winning by giving it to another participant. That seems like a very dangerous thing to have in our systems. That said, this is one of the most interesting areas of currently active multiparty coin flipping research and I may at some point post a follow up if there are results from that area that we can use.

Cleve’s result is foundational, important, and a little disappointing. We would love to be able to have a group of people send texts or emails or web packets to each other and have all honest participants come to a shared agreement on a final fair outcome. Cleve shows us that it is impossible to do this unless we make certain assumptions (assumptions which his proof assumes the opposite of). 

If we assume that people are able to reveal their messages simultaneously then we are able to make a fair and secure system, in the real world this seems only possible in person. If we assume that a majority of participants behave honestly we are able to make a fair and secure system, though this seems like a foolish assumption and one not in the spirit of sortition. If we insist on time limits for the communication we can create a fair and secure system, but as of today the only mathematical tools that can achieve this are too complex to be our first choice for building trust. And if we assume that every participant wants to win and has no other preference besides that we can construct fair and secure systems, but this doesn’t account for participants who would rather someone else win.

It’s possible that there are some other assumptions baked into the proof that haven’t been yet noticed. But for now if we want to collectively generate randomness we have to reverse one (or more) of these four. So we’re going to have to come to terms with at least one of these sets of pros and cons.

Filed under: Academia, Proposals, Sortition |