zkSNARKs and proof systems are a super interesting piece of technology. But, like any young technology, there is a lack of articles and best practices. Most of them are simplified explanations of zkSNARKs technology, or highly-specialized articles and studies, that are difficult to understand until you've tried working with them hands-on. The goal of this set of articles is to fill this gap between common and highly-professional knowledge, allowing you to start from "Hello, world" and sequentially move to your first circuits, prepare your own codebase, and deal with the common problems in zkSNARKs development.
First, read the simple basics here
if you haven't done so already. You should understand something like:
- "I have some private data that, when processed by this algorithm, gives this public output"
- "I know such input signal(s) that, when processed by the circuit, gives this output signal(s)"
- "I can provide a proof, constructed from valid signals that proves I know a solution for the constraints system of equations"
In short, I have a "circuit" - similar to an electronic circuit in real life that takes some input signals, pushes them through different logical and arithmetical gates, and generates some output signals. I take some input signals, and perform the computation over the circuit, generating a "witness": a set of all signals, valid for this circuit. Then, using this "witness", I calculate a much shorter proof.I present this proof and the public part of inputs-outputs to the verifier. The verifier takes public values and proof and verifies them together against the circuit verification data (verification key).
It is important to note that verification for different proof systems requires a "setup" when a verification key for the current circuit is generated. This verification key, allows anyone with this verification key to check proofs for any valid combination of inputs-outputs (where part of them can be kept private).
This is the "ARK" (Arguments of Knowledge) part of "Succinct Non-interactive Arguments of Knowledge" (SNARKs).
"N" means "Non-Interactive" - another property of SNARKS. It means that proofs can be sent to the verifier without any previous interactions - no "challenge-response" protocols, no pseudorandom "nonces", "salts", "challenge" values (we see them everywhere in Web2, while for blockchains absence of additional transactions is a critical property). All public inputs-outputs-proof are sent in one transaction. It's a super important property for using SNARKs in scaling solutions.
What about "S" (Succinct)? In some cases, verification of the proof can be many times faster than the calculation of the witness and the proof. A client can perform a super-heavy computation, processing thousands of user transactions for example, performing a computation with complexity O(N), and generate one, constant-size single proof, that all state changes were performed correctly, according to the state transition function. Verification in some proof systems takes O(1)! You can prove O(N) computation steps using an O(1), constant-size, constant-verification-time proof. It's super "Succinct".
Aaaand, "zk"(zero-knowledge)? "zk" part is written with small letters because in proof systems we control by ourselves, whether our "provable" function provides zero-knowledge or not. All proving logic works absolutely similarly, whether the provided signals are private or public. We receive "zk" property "for free" by designing our circuit function so that private inputs cannot be calculated from public signals. If we prove that we know a
, such as c <== a * b
, then if a
are public, anyone can compute b
, and this circuit is not "zk". But if we calculate some c <== hash(a)
, then a
can be kept private. Many cryptographic operations are built on one-way functions
, and we can make some inputs private, making it impossible to reconstruct them from public data (such as the private key from the public key or the hash preimage from the hash itself).