3 ms·

That's changing. The high replication to verify untrusted peers is decreasing and there's a realistic prospect of it going away due to gradual adoption and deve

That's changing. The high replication to verify untrusted peers is decreasing and there's a realistic prospect of it going away due to gradual adoption and development of new zk-proof techniques. In zk proofs-of-computation-result, different nodes can perform different intensive parts of a calculation and send the results along with proofs that those are the correct results. Other nodes can accept the results and verify the proofs with remarkable efficiency, then use those partial results for further calculations. To me it still feels counterintuitive and almost magical that any large, arbitrary computation result can be easily verified without repeating the computation, without the verifier needing much memory or data. For cryptocurrency blockchains this allows smart-contract (computational) transactions to be accepted with only one node having to execute the code, everyone else just efficiently verifies the proof to accept the state change. As proofs can be aggregated, this scales well: it isn't necessary for every node to run all the verifications, either. For big, distributed calculations like the article's, the whole calculation can progress using those partial results without having to rely on trust and reputation, and everyone can have high confidence that the final result is what it should be, not undermined by subterfuge or subtly inaccurate contributions. This is an offshoot of zero-knowledge proofs, as ironically zero-knowledge is not required for these types of applications. Just the efficient verifiability part. (Fwiw, I am working on large, scalable zk-proofs-of-computation in my spare time, in optimised software and with hardware accelaration, if anyone is interested in discussing this stuff.)

vlovich123 4y ago
> To me it still feels counterintuitive and almost magical that any large, arbitrary computation result can be easily verified without repeating the computation, without the verifier needing much memory or data. Why counterintuitive? That’s kind of all of cryptography and most of computer science. Take factoring into primes (which has been done for forever): it’s really time consuming and expensive to determine what the prime factors for a number are, particularly if it’s a big number and you know it only has two. That’s because division is very very difficult and time consuming. Multiplication on the other hand is super cheap so once you tell me the prime factors, I can confirm much more quickly whether or not they’re factors. In computer science, one of the earliest identified computation classes is NP complete which has this property. Eg traveling salesman and knapsack packing problem are examples. It can be insanely difficult to find a path that exists between two cities in a graph under some cost. But if you give me a solution I can easily confirm whether it meets the criteria (global optimality testing is itself NP complete but if you give me a set of solutions you can verify which one is the cheapest). I’m not claiming that factorization is NP btw. There are complexity classes beyond NP that share this property. https://cstheory.stackexchange.com/questions/159/is-integer-factorization-an-np-complete-problem https://cstheory.stackexchange.com/questions/159/is-integer-... Anyway. ZK proofs themselves are super surprising and not intuitive but not because verification is fast but because verification reveals nothing to the verifier about the solution. That’s the mind blowing result.
- jlokier 4y ago
  It's really different from the cryptography you're describing, although they do have the theory of NP in common. Mathematical cryptography depends on the assumed hardness of just a very few problems, notably factorisation of numbers with two or more large factors, and discrete logarithm in some groups. The particular problems are very specific. What I find remarkable is that zk-proof-of-computation works for any kind of computation. On the face of it, it might seem that some computations would resist being compressible that way, but no, it works with anything that can be run on any real computer. It doesn't depend on what kind of computation, so it has nothing to do with which program, how it's written, the complexity class (linear time, P, NP-complete, superexponential etc), or even on the size of the problem. It doesn't even depend on how much memory the problem requires. You can have a computation that requires terabytes or exabytes of RAM to compute, and the world's largest supercomputer running for a decade: The proof that the output is correct, no matter how much complexity went into calculating it, is still small and fast to verify. But you still have to do the computation somewhere to get the proof. That's why it's called "argument of knowledge", because the entity constructing the proof must have access to ("knowledge of") the computation. So it's still about feasible computations. Usual zk-proof-of-computation can't be used to prove things larger than there's a computer able to compute. That boundary is different from cryptography (and P vs NP), which is more about verifiability of problems requiring exponentially larger time and/or space to solve if you don't have the secrets, so if the parameters are suitable, these are about infeasible computations by any physically realisable computer. The connection is that that zk-proofs-of-computation are about making proofs of feasible computations, while ensuring it's infeasible to compute a false proof, or to find the secret inputs if there are any (there don't have to be). (By the way, you may be thinking of discrete logarithm not division. Division is not difficult. In finite fields such as used in cryptography, division can be computed by constant exponention using Fermat's Little Theorom, and exponentiation takes logarithmic time in the size of the field using a repeated squaring method. Division is slower than multiplication, but not prohibitively so; it's used in elliptic curve operations. The hardness of factorising certain numbers is for a different reason than division.)

vlovich123 4y ago

> To me it still feels counterintuitive and almost magical that any large, arbitrary computation result can be easily verified without repeating the computation, without the verifier needing much memory or data. Why counterintuitive? That’s kind of all of cryptography and most of computer science. Take factoring into primes (which has been done for forever): it’s really time consuming and expensive to determine what the prime factors for a number are, particularly if it’s a big number and you know it only has two. That’s because division is very very difficult and time consuming. Multiplication on the other hand is super cheap so once you tell me the prime factors, I can confirm much more quickly whether or not they’re factors. In computer science, one of the earliest identified computation classes is NP complete which has this property. Eg traveling salesman and knapsack packing problem are examples. It can be insanely difficult to find a path that exists between two cities in a graph under some cost. But if you give me a solution I can easily confirm whether it meets the criteria (global optimality testing is itself NP complete but if you give me a set of solutions you can verify which one is the cheapest). I’m not claiming that factorization is NP btw. There are complexity classes beyond NP that share this property. https://cstheory.stackexchange.com/questions/159/is-integer-factorization-an-np-complete-problem https://cstheory.stackexchange.com/questions/159/is-integer-... Anyway. ZK proofs themselves are super surprising and not intuitive but not because verification is fast but because verification reveals nothing to the verifier about the solution. That’s the mind blowing result.

jlokier 4y ago
It's really different from the cryptography you're describing, although they do have the theory of NP in common. Mathematical cryptography depends on the assumed hardness of just a very few problems, notably factorisation of numbers with two or more large factors, and discrete logarithm in some groups. The particular problems are very specific. What I find remarkable is that zk-proof-of-computation works for any kind of computation. On the face of it, it might seem that some computations would resist being compressible that way, but no, it works with anything that can be run on any real computer. It doesn't depend on what kind of computation, so it has nothing to do with which program, how it's written, the complexity class (linear time, P, NP-complete, superexponential etc), or even on the size of the problem. It doesn't even depend on how much memory the problem requires. You can have a computation that requires terabytes or exabytes of RAM to compute, and the world's largest supercomputer running for a decade: The proof that the output is correct, no matter how much complexity went into calculating it, is still small and fast to verify. But you still have to do the computation somewhere to get the proof. That's why it's called "argument of knowledge", because the entity constructing the proof must have access to ("knowledge of") the computation. So it's still about feasible computations. Usual zk-proof-of-computation can't be used to prove things larger than there's a computer able to compute. That boundary is different from cryptography (and P vs NP), which is more about verifiability of problems requiring exponentially larger time and/or space to solve if you don't have the secrets, so if the parameters are suitable, these are about infeasible computations by any physically realisable computer. The connection is that that zk-proofs-of-computation are about making proofs of feasible computations, while ensuring it's infeasible to compute a false proof, or to find the secret inputs if there are any (there don't have to be). (By the way, you may be thinking of discrete logarithm not division. Division is not difficult. In finite fields such as used in cryptography, division can be computed by constant exponention using Fermat's Little Theorom, and exponentiation takes logarithmic time in the size of the field using a repeated squaring method. Division is slower than multiplication, but not prohibitively so; it's used in elliptic curve operations. The hardness of factorising certain numbers is for a different reason than division.)