Re:Petals: Run 100B+ language models at home bit-torrent style
by jlokier on Monday January 02, 2023 @08:37PM
(#34226419)
It's really different from the cryptography you're describing, although they do have the theory of NP in common. What I find remarkable is that proofs work for any kind of computation. On the face of it, it might seem that some kinds of computations would resist being compressible that way, but no.
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.)
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.)