Large Scale Secure Sortition Part 3: What exactly did Cleve show was impossible? And what possibilities are left?

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.

5 Responses

  1. […] first details a method for how a specific cryptographic tool can be used to allow voting from home. The second explains the broad outlines of what approaches can work by looking at the paper that kicked off the […]

    Like

  2. Matthew,

    Thanks for the careful explanation. Could you describe the algorithm that can be used if we are willing to make the majority-honest assumption?

    Like

  3. Thank you Yorem :).

    The details of the system are moderately complicated (undergraduate CS or Math students should be able really get it after a day or two of work). If you want all the details, these two videos explain the math well–although they do throw around a fair bit of jargon.


    I’ll do my best to explain how it works at a high level.

    There is a tool (made out of several smaller tools) called verifiable secret sharing. This tool allows a group of people to do the following.

    1: A “Dealer” can take some value and split it up into a bunch of “shares” which they can hand out to the rest of the participants.
    2: If a majority of the participants are behaving honestly then the group can take those shares and combine them to get the original value back.
    3: No dishonest minority can change or delete the value during the reconstruction.

    However a dishonest majority including a dishonest Dealer can change or delete the value during reconstruction.

    We could use this tool by first having every participant takes a turn playing as the Dealer and handing out shares of their random submission. Then once every participant has sent out their shares (thereby effectively commiting to their submission) the group reconstructs everyone’s submissions. As long as a majority of participants behave honestly then we get back everyone’s original random submissions. No one can change the values during reconstruction after having seen another players submission. We can then add-divide-remainder them and get our final result.

    This method actually has two addition downsides that I didn’t mention in the above article because I felt that majority rule was already disqualifying. These are that 1) this system assumes that peer to peer messages are secure (which can be made true but will require additional complexity) and 2) This system requires every participant to send several messages to every other participant. If you have more than a few dozen people then expecting people to do that by hand is ridiculous.

    So the process (for any large selection) would have to be done by computers communicating with other computers. This leaves open the possibility of them being hacked, spoofed, or otherwise messed with.

    The only thing I like about this method is that the math involved is super interesting but could still probably be taught at a high school level (if you took a semester to teach it all). On every other front it is really disappointing.

    Liked by 1 person

  4. Thanks for the explanation and for the references, Matthew.

    To me it seems that any procedure that requires secret communication is on very shaky ground. I think we should aim for a procedure where all actions are either completely private (done by a single person) or completely public (visible to everybody and documented).

    Like

  5. You are super welcome.

    I really agree. Those are really good benchmarks to aim for that the other systems meet.

    Technically even for this one we could have the whole communication be auditable afterwards by having it be done in the open but be under public/private key encryption and then having everyone reveal their private keys at the end. But that’s another level of complexity that everyone has to trust is mathematically sound. Like I said: this option has really cool math, but on every other front it’s pretty awful.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: