Full transcript
0:00The billionth digit of pi is 1. I know
0:05because I just ran a program on my
0:07computer that computed [music] it,
0:08taking about 30 minutes. But how do you
0:11know I'm not just faking it? [music] I
0:13can show you the code. It's a well-known
0:15fast pi computing algorithm. If you
0:17wanted, you could run the code yourself
0:19and check the result against mine. But
0:22this would take just as long as it took
0:23me. Moreover, if all of you were to do
0:26this, it would be tons more computation,
0:28all just for a lack of trust. But what
0:31if instead of just saying the answer, I
0:34also gave just a tiny bit of extra data
0:36that could somehow fully convince you
0:38without repeating the computation.
0:42This sounds paradoxical. I mean, suppose
0:45I claimed to have calculated many, many
0:47digits of pi by hand. This could take
0:50days and hundreds of sheets of paper.
0:53But imagine if there was something I
0:55could write on just one sheet of paper
0:57that could somehow fully convince you
0:59all those piles of calculations are
1:00correct.
1:02Incredibly, not only is this possible,
1:05but the calculation having to do with
1:07digits of pi is irrelevant. For any
1:10calculation, you can convince someone
1:12it's correct with only [music] a tiny
1:14proof, often taking just milliseconds to
1:17check. Now you may be familiar with the
1:20concept that checking the answer to a
1:22problem may be much easier than solving
1:24the problem from scratch. For example,
1:26solving this sudoku puzzle might take a
1:28while. Whereas the solution itself is
1:31very quick to check. But what if instead
1:33of a normal 9x9 sudoku, I wanted to
1:36prove I solved a 1 millionx 1 million
1:38sudoku.
1:40Even though checking such a solution
1:42would be much faster than finding it,
1:44the solution itself would still be
1:46massive. just reading it would still
1:48take forever.
1:50Amazingly though, using the techniques
1:52from this video, it would be possible
1:54for me to convince you that I've solved
1:55the puzzle with an even shorter proof
1:58than the solution to the puzzle.
2:01This idea is called a succinct argument.
2:04And while Sudoku is a toy example, many
2:06practical problems essentially act like
2:09huge Sudoku puzzles. So succinct
2:11arguments are incredibly useful in the
2:13real world. Most notably in
2:15cryptocurrency whose fundamental
2:17mechanism called blockchain requires
2:19decentralized nodes to independently
2:22verify that batches of transactions
2:23update millions of account balances
2:25correctly in a fraction of a second.
2:28Now there are many different kinds of
2:30succinct arguments that are used in
2:31practice, but for this video we'll build
2:33up one of the most basic forms. what's
2:35known as an interactive succinct
2:37argument that achieves succinctness of
2:39communication, which basically means
2:41there are going to be two parties
2:43communicating back and forth with each
2:44other. And what we end up designing is
2:46going to allow for that communication to
2:49only contain a small amount of data
2:51overall. So with that, let's meet our
2:53two characters for the video, the prover
2:56and the verifier. The prover wants to
2:59convince the verifier of the output to a
3:01certain program. Meaning the prover
3:03shows the verifier the code for some
3:05program f and an input x and they want
3:08to prove that the output is y. To be
3:12clear, they're not proving that the code
3:13is bug-free or that it really computes
3:15digits of pi, check sudoku puzzles,
3:17validates crypto transactions, or
3:19anything else. This is an important yet
3:21entirely different consideration, and
3:23it's why I told you earlier that the
3:24implementation of my pi computing
3:26program is a well-known algorithm that
3:28you can verify independently if you'd
3:30like. For our purposes, the prover is
3:32only proving one thing, that the agreed
3:35upon program was executed correctly,
3:37step by step, according to its
3:38instructions.
3:40The easiest way to do this is for the
3:42prover to simply send the verifier a
3:45full execution trace of their program.
3:47Basically, a giant spreadsheet logging
3:50each successive state of the variables,
3:52memory, and current line of code being
3:54run from start to finish. The verifier
3:56can then just make sure all of those
3:58steps are correct. But this would be
4:00just like checking the hundreds of
4:02sheets of paper to compute digits of pi
4:04by hand. It would take just as long as
4:06rerunning the entire computation.
4:09Remember, our goal is for the prover to
4:11somehow only need to send the verifier a
4:14much shorter message than the entire
4:16proof. So instead of asking the prover
4:18for the whole execution trace, what if
4:20the verifier requests just say a
4:22thousand or so random pairs of adjacent
4:25steps? then they can just check that the
4:27state of the program between each pair
4:29of steps they asked for changes
4:31properly. If the verifier finds a
4:34mistake, they'll reject the proof. But
4:36otherwise, the idea is that those
4:38thousand spot checks give the verifier
4:41some degree of confidence that the
4:42entire proof is correct. This is the
4:45main framework for a succinct argument.
4:47Although, as is, there are two key
4:49problems. Number one, unfortunately, the
4:52proofer can cheat. You see, there's
4:55nothing forcing the prover to send the
4:57actual requested steps from their
4:58original proof. As it is, every time the
5:01verifier asks to see one of those steps,
5:04there's nothing stopping the prover from
5:06choosing how to answer the question
5:08dynamically based on which step was
5:10asked for. This means the prover can
5:13always just make up a locally quote
5:15unquote correct step that may have
5:17nothing to do with their original proof,
5:19but that passes the verifier's test. So,
5:22if the verifier asks for step 17, but
5:25step 17 is incorrect, well, it's no
5:27problem at all. Just replace it with 1 +
5:301 equals 2 or something. And if that
5:32causes later steps to be flawed, well,
5:34they can switch things up again for the
5:36next question. And they can do this for
5:38every single query from the verifier,
5:40always choosing what to answer based on
5:42the question asked. Instead, we'd really
5:45like for the prover to have to commit to
5:47one execution trace and for them to be
5:50forced to answer all of the verifiers
5:52questions using that trace.
5:55So, that's problem number one. And
5:57problem number two is well, even if the
5:59prover doesn't cheat and those thousand
6:02spot checks all pass, the verifier
6:04unfortunately still can't trust the
6:06entire proof. Suppose the execution
6:09trace has a million steps and exactly
6:12one of them is incorrect. [music]
6:14What's the chance of catching the
6:16mistake with 1,000 random samples? Well,
6:19the probability of not catching the
6:21mistake on any given try is 9999,999
6:25over a million. So, the probability of
6:28not catching the mistake in 1,000 tries
6:30is that raised to the power of a,000,
6:33which is more than 99.9%.
6:35Meaning, if there's just a single error
6:37out of a million steps, you're almost
6:40guaranteed to not catch it.
6:43Amazingly though, there is a way to
6:44solve both of these problems, and their
6:47solutions make use of some of the most
6:49fascinating tools in computer science.
6:51Cryptographic commitments and the PCP
6:54theorem.
6:56Let's start with problem number one. A
6:59cryptographic commitment is basically a
7:01way of forcing the prover to lock up
7:03their work inside a mathematical vault
7:05of sorts so that they can't mess with it
7:07once the verifier starts asking
7:09questions.
7:11To do this in practice, you need
7:13something called a cryptographic hash
7:15function, which you should think of as a
7:17digital scrambling machine. You feed it
7:19some data and it outputs a seemingly
7:22completely random string.
7:25I say seemingly random because strictly
7:27speaking it's deterministic. Applying it
7:30to the same input multiple times always
7:32yields the same garbled output. But it's
7:35random in the sense that if the input
7:37contains even just the tiniest error,
7:39the result will be completely different.
7:43Moreover, it's practically infeasible to
7:46reverse engineer what the input was just
7:49by looking at the output. Along the same
7:51lines, it's also practically infeasible
7:54to find two different inputs that get
7:56hashed to the same output. And there's
7:58also no restriction on the size of the
8:00input. You could input a really short
8:02string or a really long string, and they
8:04all get scrambled to what appears to be
8:06a uniformly random output of a fixed
8:09length. There's no reliable way to
8:11control what the output is going to look
8:13like. Keep that in mind for later.
8:16Using hash functions as a tool, our goal
8:19is now to force the proofer to commit to
8:21their proof so that they can't cheat and
8:23change it once the verifier wants to
8:25take a look. Here's how we can do that.
8:28Suppose we are the proofer. Let's
8:31imagine each row of our proof, some
8:33execution trace of a program we ran as a
8:35box, lining them all up in a row.
8:38Now, using some hash function we've
8:40agreed upon in advance with the
8:42verifier, we're going to combine each
8:44pair of neighboring boxes and hash them.
8:47And we repeat this for the next level
8:49up, the level after that, and so on
8:51until there's just one final hash at the
8:53top. What we've made here is called a
8:56Merkel tree, and it has some pretty nice
8:58properties.
9:00Notice if we now alter the data in one
9:02of these boxes, remember the result of a
9:04hash totally changes when you mess with
9:06the input even just a little. Meaning
9:08this hash would be completely different
9:11and therefore so would this one etc. all
9:14the way up to the root because that hash
9:17value at the root is sensitive to
9:18changes throughout the entire tree. This
9:21is what we'll send to the verifier to
9:23make sure they know we can't cheat. So
9:26how exactly does the verifier checkout
9:28work?
9:29Well, like before, they'll ask to see a
9:31bunch of random steps from the proof,
9:33meaning a bunch of random boxes at the
9:35base of our tree. Say the verifier asks
9:38for step number seven. As the prover,
9:41we'll send step number seven to the
9:42verifier so the verifier can check it.
9:45But to prove we didn't cheat and just
9:47fake our answer for step seven, we also
9:49send them the values of these boxes from
9:52the tree. This is called the Merkel path
9:55for box number seven. And the reason why
9:58it's useful is because the verifier now
10:00has all the information they need to
10:02reconstruct the root of the tree. They
10:05can take what we sent them for step
10:07number seven, hash it with this box of
10:09the Merkel path, and then hash that with
10:12this box from the Merkel path, etc., all
10:14the way up to the root.
10:17They then just need to compare the root
10:19value they got to the commitment we sent
10:21them previously.
10:23If we had cheated and changed step
10:26seven, it would have totally changed the
10:28value of the root like we were talking
10:30about earlier. And because of the
10:32unpredictability of hash functions, not
10:35even we as the prover can feasibly
10:37modify the rest of the tree to fix this.
10:39So once the verifier starts the
10:41inspection, we as a prover can't
10:44sneakily switch the answers around
10:45because we're bound to our commitment.
10:48Of course, besides step seven, the
10:51verifier will ask for many, many more at
10:53random, and we'll send all of those
10:55along with the Merkel path to each one.
10:57Then the verifier can check them all for
10:59correctness and check all the Merkel
11:01paths to make sure we didn't cheat.
11:04Crucially, the amount of data we need to
11:06send to the verifier to achieve this is
11:08drastically less than that of the full
11:10execution trace. Each Merkel path
11:13includes one box per level of the tree,
11:15excluding the root level. And since each
11:18level of the tree has half the size of
11:20the level below it, there are about log
11:22base 2 of n levels where n is the size
11:25of the proof. So with say a,000 queries,
11:28you only need to send about a,000 log
11:30base 2 of n hashes, which is much much
11:33less data than n, the original proof
11:35size.
11:38We've successfully solved problem number
11:40one. The prover is now forced to send
11:42the true requested steps to the verifier
11:45and it only takes a tiny amount of data.
11:48And so if you imagine this all as a game
11:50where the prover tries to trick the
11:52verifier into believing a faulty proof,
11:54we've just achieved something big. The
11:57prover can no longer cheat at this game.
12:00They can't adaptively choose their
12:02answers based on the verifier's
12:03requested steps anymore because they're
12:06forced to commit to one execution trace
12:09and answer every requested step using
12:11the data from that commitment.
12:13Unfortunately, as it is, the prover
12:15doesn't even have to cheat to win this
12:17game. The odds are already rigged in
12:20their favor. Remember problem number two
12:22from earlier? The probability that the
12:25verifier actually catches a mistake is
12:27tiny. As we calculated before, it's only
12:30about a tenth of a percent with a
12:32thousand random samples if there's just
12:34one incorrect step out of a million.
12:36Now, the verifier could just check more
12:39steps, [music] like 10 or 100,000 to
12:41boost the success rate. But then the
12:43prover would have to send 10 or 100
12:45times more data, approaching or even
12:47exceeding the full size of their proof,
12:50which would defeat the whole purpose of
12:51this video. The problem is that a single
12:54mistake is like a needle in a hay stack.
12:56[music] is just too hard to catch. Which
12:59begs the question, what if we could
13:00somehow rewrite the proofer's proof so
13:03that even a tiny mistake becomes
13:05impossible to hide?
13:08Incredibly, there is a way to do this
13:10and it comes from one of the most
13:12fascinating results in computer science,
13:14the probabilistically checkable proofs
13:16theorem or PCP theorem. Now, proving the
13:19PCP theorem is very complicated and
13:22could have an entire series of videos
13:24dedicated to it, but what it's saying is
13:26on its own really interesting. And for
13:28this video, we'll see how you can use
13:30the theorem to take what we were
13:32designing earlier from a fun theoretical
13:34thought experiment to something actually
13:36useful. There are many equivalent ways
13:39of stating the theorem, but one common
13:41one that I think illustrates it really
13:42well has to do with coloring graphs. And
13:45I want to quickly flag that this next
13:47section might seem completely unrelated
13:49at the moment, but just hang on. We'll
13:51see how this all ties into the rest of
13:53the video in just a few minutes.
13:56A graph is a network formed by nodes and
13:59edges, which connect pairs of nodes. Say
14:02we wanted to color each node either red,
14:05yellow, or blue such that every edge
14:07connects nodes of different colors. So,
14:10for example, this coloring would not be
14:12valid because this edge connects two
14:15blue nodes. We'll call that edge a bad
14:18edge since it violated the rule. If we
14:21change the colors though, there are no
14:23bad edges. Every edge connects nodes of
14:26different colors. And so, we'd say this
14:28assignment of colors for the nodes is a
14:30three coloring of the graph since we
14:32were able to color the graph using three
14:34colors without any conflicts. But some
14:36graphs are not three colorable. For
14:39example, in this graph, you can color
14:41the outer nodes red, yellow, and blue,
14:44but there's no color for that node in
14:45the middle that leaves no bad edges.
14:50Now, back to the prover and the
14:51verifier. Remember, the prover's goal is
14:54to convince the verifier of the output
14:56to a certain program. And the PCP
14:58theorem gives a standardized efficient
15:01procedure that both the prover and
15:02verifier can use to translate any such
15:05computational claim into a graph that
15:07has two properties.
15:09Number one, if the program does indeed
15:12have the claimed output, then the graph
15:14is three colorable and an execution
15:17trace for the program can easily be
15:19converted into the three coloring.
15:22And number two is that if the program
15:24does not have the claimed output, then
15:26any attempt to color the graph with
15:28three colors will cause at least about
15:315% of the edges to be bad. Remember this
15:34triangle-shaped graph we saw earlier
15:36that was impossible to color with three
15:38colors. You can imagine the process here
15:40might turn a false statement into a
15:42complex network that has not just one of
15:45these non-reecolorable constructions,
15:47but tens or hundreds of them, polluting
15:49a sizable chunk of the edges.
15:53Okay, that's a lot to take in. And how
15:55does this graph even help us with
15:56checking proofs anyway? Well, remember
15:59what we were doing earlier? Before the
16:02prover had committed to their proof
16:04using a Merkel tree, and the verifier
16:06was checking a bunch of random steps
16:08within the proof for mistakes. The
16:11analogous thing to do here is to have
16:13the prover commit to their coloring of
16:15this big graph representing their proof.
16:17meaning they'll essentially line up all
16:19the nodes in a row and make a Merkel
16:21tree out of the data from the color
16:23assignments.
16:24The verifier will check a bunch of
16:26random edges in the graph looking for
16:28bad edges. Because a correct proof
16:32always turns into a valid three
16:33coloring, it means the verifier should
16:36reject the proof if they find any bad
16:38edges.
16:40Okay, that's great and all, but how does
16:42this actually solve the problem we had
16:43before? that there could be just one
16:45tiny mistake in a gigantic proof.
16:49Well, if you look closely at the PCP
16:51theorem, it's telling you that any
16:53flawed proof is going to cause not just
16:55one, but at least around 5% of the total
16:58number of edges to be bad edges. Even
17:01though that 5% may not seem like a lot,
17:04with enough tries, the verifier will
17:06almost certainly hit one of them. It's
17:09like throwing darts at a pie chart where
17:115% of the area is shaded in. Sure,
17:14you're unlikely to hit that region
17:15within the first few tries, but throw
17:17enough darts and you're essentially
17:19guaranteed to hit it eventually. To back
17:22that up with numbers, in the case where
17:24the proof is indeed faulty, we know the
17:26probability of not catching a bad edge
17:28on any given try is at most 95% or 0.95.
17:33So using the same example number as
17:35before of a thousand tries, the
17:38probability that none of them would
17:39catch a bad edge is 0.95 to the power of
17:43a,000.
17:44Subtracting that from one, we find that
17:46you can be about 99.9999999999995%
17:52sure this is going to work. In short,
17:55the reason this is so much better than
17:57what we had before is that there used to
17:59be nothing guaranteeing a faulty proof
18:01would have more than a single mistake.
18:03But in the PCP theorem, the number of
18:05mistakes in any faulty proof grows with
18:08the size of the proof. Because that 5%
18:12is a constant fraction of the edges, it
18:14now doesn't even matter whether there
18:16are a million edges or 100 million. If
18:18you choose a thousand of them at random,
18:21the chances of catching a mistake are as
18:23good as certain.
18:25Using the power of cryptography and the
18:27PCP theorem, we just created a scheme by
18:30which a prover can convince a verifier
18:32of any computational claim to an
18:34arbitrarily high degree of confidence
18:36just by sending a handful of hash values
18:39which in practice usually only ends up
18:41being just a few kilob even for
18:43ginormous computations.
18:46To wrap things up, let's lay out the
18:48full scheme we design from start to
18:50finish. The prover begins by sharing
18:53their computational claim with the
18:54verifier. They then both translate that
18:57claim into its corresponding graph via
19:00the PCP theorem. The prover will now
19:03translate the execution trace of their
19:05program into its corresponding coloring
19:07of the graph. Then they'll commit to
19:10those color assignments with a Merkel
19:11tree, sending the root of the tree to
19:13the verifier. At this point, the
19:16verifier will choose a bunch of random
19:18edges from the graph and ask for the
19:20colors on the nodes they connect,
19:22looking for bad edges. For each edge,
19:25the prover sends that pair of colors and
19:28the Merkel path to those two nodes. And
19:30the verifier checks that the two colors
19:32are different and that the Merkel paths
19:34they receive correctly reconstruct the
19:37previously committed root value. When
19:40repeated on enough random edges, this
19:42will give the verifier an arbitrarily
19:44high degree of confidence that the proof
19:46is correct. That's the full process.
19:50Now, the astute among you may realize
19:51that there's still one more catch here.
19:53In our current scheme, we've achieved
19:55succinctness of communication, meaning
19:57the prover can get away with sending a
20:00small amount of information compared to
20:02their original proof size. This is
20:04already very useful on its own because
20:06communication is a highly valuable
20:08resource in the real world. It takes
20:10time to send terabytes of data over the
20:12internet. But what about the verifier?
20:15How much work do they have to do on
20:17their end to actually check what the
20:18proofer sent? The way we've been
20:21thinking about things, they have to
20:22generate this graph that's about as big
20:24as the original proof size because they
20:26have to know which nodes are even
20:28connected so that they can query edges
20:30to check the colors. And creating that
20:32graph takes an amount of work. Well,
20:34proportional to the size of that proof.
20:37You have to generate all that data.
20:39However, many implementations of
20:41succinct arguments in practice also
20:43achieve succinctness of verification.
20:45Meaning the verifier 2 can get away with
20:48doing much much less work locally to
20:50verify the proof, avoiding the need to
20:52fully generate this big graph. [music]
20:55This might sound weird at first, but
20:57remember this big graph is created from
20:59the code of some program. And everything
21:02we're doing here is already under the
21:04assumption that the code or the
21:05description of a program is very short,
21:08much shorter than the potential size of
21:10its execution trace or the proof of the
21:12output to that program. Meaning in
21:14theory, there should also be a way to
21:16get a short version of the description
21:18for or the code if you will for this
21:21graph representing the program. To
21:24actually achieve this, there are [music]
21:25a bunch of fancy mathematical details
21:27that we won't get into, but I just
21:28wanted to highlight that it is possible
21:30and it means the verifier has a way of
21:32generating their queries about the edges
21:34of the big [music] graph implicitly
21:36without having to produce so much data.
21:38And this is often what's done in
21:40practice.
21:42So yeah, that's pretty much it. And this
21:45isn't merely a theoretical curiosity.
21:47Systems based on ideas from this video
21:49are actively being used to scale the
21:51future of the internet. Blockchains are
21:54already using succinct arguments to
21:56validate crypto transactions. And for
21:58instance, Ethereum plans to even more
22:00widely implement this technology into
22:02their primary network over the next few
22:04years.
22:06If you think about it, this is all
22:08possible because we've changed our
22:09definition of a proof. Normally, proofs
22:12are something you just read line by
22:13line, but allowing for interactivity
22:16between parties, cryptography, and
22:18probabilistic checking opens a whole new
22:21realm of possibilities. Using related
22:23ideas from this video, proofs can even
22:25be made zero knowledge, meaning a prover
22:28can convince you something is true
22:30without revealing any details of the
22:32proof itself or non-interactive, [music]
22:35eliminating the need for back and forth
22:37communication between the prover and
22:38verifier altogether. But that's it for
22:41this video though. I want to extend a
22:43big thanks to Bar Elon University and
22:45the European Research Council for
22:47providing funding for this project and
22:49to professors Alessandro Kza and Elon
22:52Yogv for taking the time to help me
22:54understand these concepts and for their
22:56editorial oversight. If you're
22:58interested in having your research
22:59featured on Purplemind, reach out to me
23:01at my email in the description below. Of
23:04course, a huge thanks to my Patreon
23:05supporters. And as always, thanks so
23:07much to you for watching. I hope you
23:09enjoyed and learned something, and I'll
23:11see you next time.