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 proposes a backup protocol to compliment the one in the previous article that can be used without requiring people to gather in person. However it is so mathematically complicated that only CS and Math PhDs are likely to ever understand the proof of why it’s secure. Given that the goal of using these systems is to generate trust, I cannot recommend this as a primary option, though I can recommend it as a fallback during times (like extreme weather events or pandemics) where gathering large numbers of people is difficult.

Non-Malleable¹ Time Lock Puzzles are cryptographic tools that allow you to hide information inside a computational puzzle. Once hidden, the information can only be accessed after the puzzle is solved. Making a time lock puzzle is kind of like turning a QR code into a jigsaw puzzle. If you give the puzzle to someone they’ll only be able to scan it after they’ve completed/solved the puzzle. The main difference is that Jigsaw puzzles can be solved in many different ways by doing the “this piece connects to this piece” steps in any order. Time Lock Puzzles can only be solved in 2 ways.

The first (called opening) is fast but requires a special key that is created alongside the puzzle and known only by its creator. The second (called forced opening) takes much longer and requires you to do a specific list of computations in a specific order. These computations have to be done sequentially (you only know what step 2 is after you finish step 1) so throwing hundreds of computers² at the problem isn’t any better than using just one. When you create the puzzle you get to decide exactly how many steps it’ll take to solve the puzzle (by choosing how many “puzzle pieces” there are). And since we know about how quickly modern computers can do these steps, we can accurately estimate how long the puzzle will take to solve.

We can take advantage of this to construct a system where participants have to submit their puzzle before they’ve had enough time to solve others’ puzzles. This achieves the same effect as a simultaneous reveal. 

If Luka and Hugo want to use time lock puzzles to conduct a coin flip here’s how they would go about it:

1. They hide their submissions in time lock puzzles made to take 2 hours of work to force open.
2. Hugo sends Luka Hugo’s puzzle.
3. If Luka sends a puzzle back within 20 minutes³ both Hugo and Luka can force open their opposite’s puzzle and then combine the submissions.
4. If Luka doesn’t send back a puzzle in those 20 minutes Hugo just flips a coin. 

If Luka doesn’t have a computer that is 6 times as fast as the modern standard he’ll have to choose whether (and what) to reply before knowing what Hugo’s submission was. This means that having that crazy fast computer is the only way to cheat⁴.

To scale this up to a large selection we have every submitter send in their puzzles (that can only be solved after 24 hours) over the course of a 4 hour period. As puzzles arrive they are posted publicly. After the “polls” close, we have an hour during which submitters are asked to send in their “keys” which can be used to quickly solve their submitters’ puzzles. After that hour we start force opening all the puzzles which we didn’t receive keys for. After 24 hours of this, all the puzzles will be solved and we can extract every submitter’s submission. Then we use the same add-divide-remainder procedure to get the final answer. Like in the previous article as long as one submitter submitted randomness this final answer is random.

This system has three major advantages. First, it allows people to participate in collectively generating randomness from the comfort of their own homes. Second, every participant gets to contribute directly to the final randomness instead of contributing indirectly through the tiered system laid out in the previous article. Third, anyone can audit the process. Once a puzzle has been opened it’s easy to tell that the solution is correct. And since all the puzzles and solutions were posted publicly anyone can go through and check that each pair matches, that the list of puzzles didn’t change after the submission window closed, and that the solutions combine to get the final listed result.

But it has a major disadvantage that means I cannot propose it as our first choice for a collective randomness generating system. The math involved is fiendishly complex. Really understanding what Non-Malleable Time Lock Puzzles are, how they work, and why they are secure requires years of study. The proof of security uses tools from circuit complexity, number theory, cutting edge cryptography, and much more. Maybe someday people will build a mathematical tool that works similarly enough to Non-Malleable Time Lock Puzzles but is much simpler to build and explain. But until then the only people who can personally trust that they work are the handful of Math and CS PhDs who have taken the right classes and read the right papers. Everyone else has to just trust us. That doesn’t seem very democratic. And more importantly that doesn’t build trust in the system. 

I can recommend it as a backup system for times when gathering large numbers of people is difficult, but I cannot recommend it as the backbone of a sortition system. For most people it would get its trustworthiness from experts saying it worked. But they would always have a nagging fear that it didn’t.

Footnotes:

1: In this article I do not explain why our Time Lock Puzzles need to be “Non-Malleable” or even what Non-Malleable means. The shortest possible explanation is that if they aren’t Non-Malleable then it might be possible for Luka to vote in such a way that it deletes Hugo’s vote. Giving a deeper but still accessible explanation would have taken a few pages at minimum. And really explaining it would require math that is rarely taught in even PhD level cryptography courses.

2: Or a supercomputer, modern supercomputers are just thousands of normal computers working together.

3: The exact ratio of forcing time to submission window is arbitrary. I like 6:1 but that is just a personal choice. I am not an expert on computer chips, and that’s probably the right kind of person to determine what the best ratio would be.

4: There are actually two other options for cheating but these are both even more implausible than a secret super fast computer. The first is to randomly guess the correct answer by brute force guess-and-check. But it is easy to set up the time lock puzzles such that even if we used every existing computer for the next hundred years the odds of guessing the correct answer are one in a million. The other option is to use a large scale quantum computer, which can (from a certain point of view) do the entire brute force guess and check in just a few calculations. However we are decades away from having quantum computers large enough and reliable enough to do that calculation. And by the time those become available some cryptographer will likely have come up with a way to create post-quantum Non-Malleable Time Lock Puzzles. Though I’m sure that method will involve even nastier math.

Filed under: Sortition |