3
$\begingroup$

I'm studying simple examples to understand how ZK-Snarks work.

Following this great introduction, I'm trying to elaborate a generator function giving a prover and verifier keys:

pk, vk = G (C, lambda)

that would work on the simple case

C (x, w) { return (sha256 (w) == x); }

i.e. how to build a zero knowledge proof scheme for the simple use case:

I know a string s whose hash is x. I can prove it to you, without revealing s.

How to actually build a zk proof algorithm for this simple use case? (following the article's notations, how to get proving/verifying keys and functions, given a lambda "waste" that will be discarded after generation?)

$\endgroup$
2
$\begingroup$

This section from the paper Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture is what you want. See the following image. NIZK for von Neumann I will describe the very high-level idea below. ZKSNARK that libsnark and ZCash use is based on the Knowledge of Exponent assumption. Basically, the exponent used in the elliptic curve cryptography is just the "toxic waste" that you mentioned. Denote $G$ as the group generator of the curve used, $G*t, G*t^2, \ldots$ ($t$ is part of the so-called private coin and this series will continue until the evaluation of some polynomial like $H(t))$ is covered. You may wonder what $H(t)$ is. A brief answer is that we have transformed the NP statement (the preimage of SHA256 is a witness to the NP statement due to the property of the one-way function) to the arithmetic circuit consisting of additive and multiplicative gates (just assume no boolean comparison here), then to the polynomial $A(t)*B(t)-C(t)=H(t)*Z(t)$. This polynomial equation holds ($H(t)$ exists particularly) $iff$ the proving procedures are correctly executed. Put it more simply, if the circuit contains $N$ gates (constraints), then we need a polynomial representation of order $N$. Again why this weird equation? Assume the underlying computation takes $T$ steps, this gives us lower bound $T\log(T)$ on proving time thanks to the deep connection between polynomials and the $\text{Fast Fourier Transformation (FFT)}$. Before this method, the proving time is at least $T^2$ (inner product and outer product are used, thus the square). On the other hand, we can further reduce the polynomial equation to the $\text{ECC}$ bilinear pairing problem. We need this one last transformation because it allows the verification steps to be very efficient. The proof is constantly 128 bytes (3 pairings) and the verification is always around 3-5 ms. So now we can also answer where this "trusted setup" concept comes from. It is import no one has a trapdoor to the setup procedures, i.e., no one has access to the "toxic waste". Typically, multi-party computation is applied so that if at least one party is honest, the setup is a trusted one. Another thing you mentioned is $pk$ and $vk$. As you can see, $pk$ is a proving template that uses homomorphic encryption for the verifier to check the knowledge commitments of polynomials $A(x)$, $B(x)$ and $C(x)$ and whether they use the same coefficients. And $vk$ is just used in the pairing.

If you want to know more details, a great start would be the explanation by Vitalik Buterin. It is not hard to understand this one. Here is another somehow more formal explanation by Christian Reitwießner. Also, for more academic teaching resources, this lecture series covers the general topic of verifiable computation, interactive arguments system, ZKSNARK with pre-preprocessing, ZK system front-end transformation and much more.

$\endgroup$
  • $\begingroup$ Wellcome here. Please learn to use $LaTeX$. I've updated your answer. Please check it. $\endgroup$ – kelalaka Nov 12 '18 at 15:43
0
$\begingroup$

In libsnark, prover and verifier keys are generated with

r1cs_ppzksnark_generator< proof_system >(constraints).

https://github.com/vadym-f/Sudoku_solvability_proof/

To generate the keys, circuit must be defined first. For sha256, just pick the proper "gadget".

Full "algorithm" is generate keys, produce a proof, verify it. You will need to learn some math and jargon, so 2013/879 could be great if you can follow it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.