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.
It doesn't depend on what kind of computation, so it has nothing to do with the type, 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.
It's restricted to 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 very different from cryptography (and P vs NP), which relate the verifiability of something (such as factorisation or hash output or formal theorem correctness) to a problem requiring exponentially larger time and/or space which, if the parameters are suitable, can't be feasibly computed by any physically reaslisable computer.
(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.)
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.)