zk-SNARKs on Bitcoin

Previously, we have proved one knows some mathematical secret using zero knowledge proof (ZKP), without revealing the secret itself. The secret knowledge include:

While useful in their specific applications, these ZKPs cannot be applied to arbitrary mathematical functions. Overcoming these limitations, a zk-SNARK (zero-knowledge Succinct Non-interactive ARguments of Knowledge) is a protocol designed to generate a ZKP for any mathematical function. The generated proof is “succinct” and “non-interactive”: a proof is only a few hundred bytes and can be verified in constant time and within a few milliseconds, without needing to ask additional questions of the prover. Together, these properties make zk-SNARK especially suitable for blockchains, where on-chain storage and computation can be expensive and senders often go offline after sending a transaction. Anonymous cryptocurrency Zcash and the smart-contract platform Ethereum are among its notable early adopters, among others.

zk-SNARK

A zk-SNARK consists of the following three algorithms: G ,P, andV.

Key Generation

A key generator G takes a secret parameter λ and a function C, and produces a proving key pk and a verification key vk. Both keys are made public.

Key Generator

C is a boolean function (also called a program or circuit) that takes two inputs: a public input x and a private input w (aka, witness). For example, C can be a function that checks if w is the sha256 preimage of the digest x.

C(x, w) = sha256(w) == x

Prover

The prover P takes as input the proving key pk, a public input x and a private witness w to produce a proof that the prover knows a witness w that makes C(x, w) evaluates to true.

Prover

Verifier

The verifier V takes verification key vk, the proof, and the public input x and accepts the proof only if it is produced with the knowledge of witness w¹.

Verifier

Implementation

When zk-SNARKs are used in blockchains, both the key and proof generation are executed off-chain. Only the general verification algorithm is run inside a smart contract on chain.

There are multiple schemes of zk-SNARKs in the literature. We implement the most widely used scheme Groth16 due to its small proof size and fast verification.

Verifier in Groth16: page 18

The full code is listed below, based on our elliptic curve arithmetic and pairing libraries.

Contract ZKSNARK

It is worth noting that the proof size (Line 23–27) and the number of pairings (Line 43–44) are constant, regardless of how complex the function C being proved is.

Summary

zk-SNARK is a powerful primitive for blockchain privacy and scalability. Today we only showed what zk-SNARK is and how to implement it on Bitcoin. We will explore how to use it in the near future. Why and how it works internally, which is quite math heavy, is beyond the scope of this single article. There are many excellent tutorials such as this series and this paper.

[1] There is an exception. Anyone knows the secret parameter λ used in the generator can generate fake yet valid proof without knowledge of witness. That is why it is called toxic waste. It must be discarded after the trusted setup phase.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store