Hello everyone, welcome to NTT Summit. My name is Ilan Komargodski, and I will talk about, SPARKs: Succinct Parallelizable Arguments of Knowledge. This talk is based on a joint work with; Naomi Eiphraim, Cody Freitag and Rafael Pass. Let me start by telling you what Succinct Arguments are. A Succinct Argument is a special type of interactive protocol between a Proof, Prover and the Verifier, who share some instance ‘x’, which is allegedly in some language ‘L’. The goal of the protocol is for the prover, to convince the verifier that ‘x’ is indeed in the language. For completeness, the guarantee is that, if ‘x’ is indeed in the language, the verifier will in the end of the protocol indeed be convinced. On the other hand, for Soundness we require, that if ‘x’ is not in the language, then no matter what the prover does, as long as it is bounded to run in polynomial time, the verifier will not be convinced.

There is a stronger notion of soundness, called an argument of knowledge, which says that the only way for the prover to convince the verifier is by knowing some witness. There is a mathematical way to formalize this notion, but I will not get into it. For efficiency, and what makes this protocol succinct, is that we require the verifiers, running time and communication complexity between the prover and the verifier, to be both mangled by some polylogarithmic function in ‘T’, where ‘T’ is the time to verify the NP statement. In terms of the prover’s running time, we’re not required anything except that it’s sampling normality. The goal of this work is to improve this polynomial overhead of the prover. To explain why this is an important task, let me give you a motivating example, which is just the concept of Delegation of Computation.

So considering some small device like a laptop, or a smartphone that wishes to perform some complicated computation, which it cannot do, since it is a weak device, it wishes to delegate the computation to some service or cloud to perform the computation for it. Since the small device does not fully trust the service, it may want to ask the service to also issue a proof for correctness of the computation. And the problem is that if the proof takes much more time than just performing the computation, it’s not clear that this is something that will be useful in practice. Think of an overhead which is square of the time it takes to perform the computation, this will become very quickly a very big number or very large delay for generating the proof.

We are not the first study this problem, it has been studied for several decades. And at least from a theoretical point of view, the problem is almost solved or essentially solved. We have constructions of argument systems is the great overhand just for the logarithmic, multiplicative overhead. This is obtained by combining efficient PCPs, together with Killian’s argument system. There’s huge open problem in Complexity Theory of constructing PCPs with constant overhead, mainly running just in linear time in the running time of just running the computation. But we argue that even if we had such a PCP, and the constant was great, let’s say it was just 2, this will already be too much. Because if you delegate the computation, to take some months to complete, then waiting another month, just for the proof might not be so reasonable.

There is a solution in the literature for this problem, using what we call a Parallelizable PCP, [unintelligible] show that there is a PCB construction that has the following very useful property. Once you perform the computation itself, without the proof, just the computation and write down the computation tableau, then there is a way to generate every symbol of the PCP in just only logarithmic time. So this means that you can in parallel, after computing the function itself, you can in parallel, compute the whole PCP in just polylogarithmic time. This gives us a great argument system with just ‘T’ plus polylog ‘T’ parallel time instead of ‘T’ times polylog ‘T’ time. But for this, we need about ‘T’ processors, which is prohibitively large.

This is where SPARKs come in. We introduced the notion or the paradigm of computing the proof in parallel to the computation not after the computation is done. Slightly more formally what a SPARK is. It’s just a succinct argument of knowledge. Like what we said before with the verifiers and communication aggressively being small. But now we also require approver, which is super efficient, namely it can be parallelizable, and it has to finish the proof together with the computation in time ‘T’ plus polylog ‘T’, which is essentially the best you can hope for. And we want the Prover to do so, only with polylogarithmic number of processors.

You can also extend the definition, to handling computations which are to begin with parallelizable. But I will not touch upon this in this talk, you can see the paper for details. We have two main results. The first main result is a construction of an interactive SPARK. It’s just four rounds, and it assumes only collision-resistant hash functions. The second result is a non-interactive SPARK. This result also assumes collision-resistant hash functions, and in addition, the existence of any SNARK and namely Succinct Non-interactive Argument of Knowledge, that does not have to be a super-efficient in terms of proof or anything.

Slightly more generally, the two theorems follow from a combined framework, which takes essentially any argument to knowledge and turns it into a SPARK by assuming all collision-resistant hash functions. And maybe the motto behind the construction could be viewed as a trade-off between computation time and processors. We instantiate theorem one using Killian’s protocol, which is an argument of knowledge, which is a foreground argument of knowledge. And we instantiate Theorem 2 using a SNARK, which is an argument of knowledge just by definition.

Let me tell you what are the main ideas underlying our construction. Before telling you the ideas, let me make some simplifying assumptions. The first assumption, I will only be talking about the non-interactive regime. The second assumption is that I’m going to assume a SNARK, which is a non-interactive succinct argument to knowledge. And then we’ll assume the Snark is super efficient. So it will consume total time 2T for a computation that takes time ‘T’. So almost what we want, but just not yet, not yet there. I will assume that the computation that we want to perform is sequential. And additionally, I will assume that the computation has no space, or it has very low space. So think about the sequential computation, which doesn’t have a lot of space, or even zero for the for the time being. I will later discuss how to simplify. How to remove the simplifying assumptions.

So the starting idea is based on two works of Boneh Allan Dobligenter, from a couple of years ago. And here’s how it works. So remember, we want to perform a ‘T’ time computation, generate a proof, and we need to finish roughly by time ‘T’. So the idea is to run half of the computation, which is what we can afford, because it will have a SNARK, that can generate a proof in additional ‘T’ two steps. So we can run half of the computation and prove that half of the computation all in time ‘T’. And the idea is that now we can recursively compute and prove the rest of the computation in parallel. Here’s how it looks like. So you run half of the computation, started the proof, and then you run a quarter of the remaining, half of the remaining computation, which is a quarter of the original one and prove it in parallel again, we take another eighth of the computation, which is one half of what’s left, and so on and so forth. As you can see, eventually we’ll finish the whole computation. And you only need something like logarithmically many parallel processors. And the communication complexity and verifiers runtime only grow by a logarithmic factor. So this is the main idea.

Let’s go back to the Simplifying Assumptions we had. So the first one was that, I’m only going to talk about the non-interactive regime. You have to believe me, that the same ideas extend to the interactive case, which is a little bit more messy with notation, but the ideas extend. So I will not talk about it anymore. The second assumption I had, was that I have a super-efficient SNARK. So it had overhead 2 ‘T’ for ‘T’ time computation.

Again, you have to believe me that if you work out the math, then the ideas extend to start with quasi-linear overhead, namely, SNARKS that work in time ‘T’ times polylog ‘T’. And then the result extends to any SNARK, because of a result, because of a previous work will be translated to show that a SNARK with a proof that runs in polynomial time can be generically translated into a SNARK, where the proof runs in quasi-linear, which is quasi-linear overhead. So this gives our results from any SNARK. Not only from pretty efficient SNARKs. The last bullet was about the fact that, we’re dealing with only with sequential RAM computations. And again, you have to believe me that the ideas can be extended to PRAMs.

And the last assumption, which is the focus of this work, is how to get rid of the small space assumption. This is what I’m going to be talking about next. So let’s see what goes wrong if the computation has space. Remember what we did in a couple of slides ago. The construction wants to perform half of the computation, prove it, and then half of the remaining computation, prove it and so on. And if you write down the statement that each of these proofs proves, it’s something like, ‘ a machine ‘M’ or the input ‘x’ executed for some number of steps, starting from some state ended at some other state.’ And if you notice, the statement itself, depends on the space of the computation.

And therefore, if the space of the computation is non-trivial, the statements are large, and therefore the communication will be large. And therefore the verifier will have to be run with time proportional to the space, and so on. So we don’t even get a succinct argument if we do it natively. Here’s a solution for this problem. You can say, well, you don’t have to include the space, in the whole space in the statement, you can include only a digest of the space, think about some hash function of the space. So indeed, you can modify the statement to not include a space but only a digest. And now the statement will be a little bit more complicated, it will be that there exists some initial state and n state such that their hash is consistent with the digest in the statement, and if you run the machine ‘M’ for ‘K’ state, and for ‘K’ steps, starting from the initial space, you end up with the final space.

So this is great, it indeed solves the communication complexity problem and the verifier complexity problem. But notice that from the prover side, we didn’t actually do anything, because we just pushed the complexity into the witness. So, the provers running time is still very large, with this solution.

Our final solution in the very high level, is to compress the witness. So instead of using the whole space as the witness, we will be using the computation itself, the computation that we ran as the witness. So now, the statement will be of the same form. So it will still consist of two digests and a machine. But now the witness will be not the whole state, but it will be the case steps that we performed. Namely, it will be that there exists case steps that I performed, such that if I run the machine ‘M’, on this case steps, and I started with a digest, Dig start and I apply these ‘k’ steps on the digest, I will end up with a final digest. In order to implement this, we need some sort of an updatable digest. This is not so hard to obtain, because you can just use something like a Merkle tree, it’s not hard to see that you can update locations in the Merkle tree quite efficiently. But the problem is that we need to compute those updates, not only we need to be able to update the hash or digest, we should also be able to compute the updates in parallel to the computation.

And To this end, we introduce a variant of Merkle trees, and show how to perform all of those updates level by level in the in the Merkel tree in a pipeline fashion. So namely, we push the updates of the digest into the Merkel tree, one after the other without waiting for the previous ones to end. And here we’re using the tree structure of Merkle trees. So that’s all I’m going to say about the protocol, I’m just going to end with showing you how the final protocol looks like. We run ‘k’ steps of computation, some ‘k’-1 steps of computation, and we compute the ‘K’ updates for those ‘k’ steps in parallel with computation. So every time we run a step of computation, we also have a start and update of our digest.

And once we finish computing all the updates, we can start running a proof, of using those updates as witness. And we recursively continue in this way. As a conclusion, this results with a SPARK, mainly a succinct argument system, with the provers running time ‘T’ polylog ‘T’ and no times, and all we need is something like, polylogarithmic number of processors. I would like to mention that this is a theoretical result, and by no means should be taken as a practical thing that should be implemented. But I think that it is important to work on it and there is a lot of interesting questions on how to make this really practical and useful. So with that, I’m going to end, and thank you so much for inviting me and enjoy the Summit.