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.)
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-...
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.
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.)
Is this also how IPFS works?
Blockchain as such has nothing to do with the costs of a node and incentives to run one
Blockchains are built under the assumption that everyone is selfish and untrustworthy. Which is a decent assumption when building a crypto currency, but that doesn't mean that every system has to run like that.
Typically on a tracker you’re given a currency (although not as sound as some e-coins) and can use that to influence your upload or download statistics, which in turn affect your ratio. Some trackers might employ rules where your user class has to have a certain ratio, or else you’ll lose privileges like certain forums or even the ability to download at all. (The trackers are private and can control which peers you can see)
I see some similarity here to the world of private torrent trackers. You want a Linux ISO, I want a Linux ISO, we're all working towards the same goal. So we're already incentivized to cooperate, without getting money involved. And trackers also have things like minimum seeding ratios to keep people honest. In the case of AI, you and I both want to generate images, so we're also working towards the same goal, so let's help each other out so both of our workloads finish faster. Maybe idealistic, but I think it could work.
A distributed consensus mechanism would segment the decisions amongst nodes, not poll for a unanimous response.
"Massively redundantly replicated"