[Cryptography] What is the current state of useful code for zk-snarks?
cherry
cherry at cpal.pw
Wed Mar 9 21:19:27 EST 2022
To be actually useful, a zk-snark system needs to be a compiler, that
compiles a program written in what Starkware calls R1CS, and other
people are calling script, and generates two programs, a prover and a
verifier.
The prover operates on two blobs, the public blob and private blob, and
produces a boolean result, true or false, pass or fail, and a proof that
it did so.
The proof is approximately constant size, regardless of how much
computation is required and regardless of how large the private blob
was, but takes a very long time.
The verifier operates on the public blob and the proof, takes a short
and approximately constant time to do so, regardless of how big the
computation was, and regardless of how big the private data was and
determines, with 2^(126) likelihood of error, what result the prover got.
But at present I get the impression that neither script nor R1CS have
any real existence, though I have seen a script language that operates
on a stack, and, though it has no variables, can dupe any item on the
stack to the top of the stack. It seems to have only been ever used to
generate one prover and one verifier, because actually creating the
prover and verifier still required some coding by hand. Also lacked
certain control structures.
At present, people seem to be writing the prover and the verifier by
hand, a very difficult operation with a very high likelihood of bugs.
The prover and the verifier do very simple tasks like proving the
encoded inputs to a transaction are greater than or equal to the encoded
outputs and that no numeric underflow or overflow occurred.
Another problem is that we would really like the public data to be the
root hash of a merkle tree, and no one seems to have a script language
that contains a useful hash function Stackware is built out of hash
functions, but last time I looked, you could not call a hash function
from R1CS.
We need a script language that can not merely add and subtract, but can
also do hashes and elliptic point operations. zk-stark systems are
built out of hashes and elliptic point operations, but it seems to be
uphill trying to generate proofs that prove something about the results
of hashes and elliptic point operations, making very difficult to
produce a proof that a pile of proofs in the pre-image of a merkle tree
have been verified. I suspect that a prover might take a very very long
time to produce such a proof.
More information about the cryptography
mailing list