This article first appeared on Medium.
Previously, we proved that one knows a mathematical secret using zero-knowledge proof (ZKP), without revealing the secret itself. Secret knowledge includes:
Although useful in their specific applications, these ZKPs cannot be applied to arbitrary mathematical functions. Overcoming these limitations, a zk-SNARK (zero knowledge Sconcise NOTover-interactive ARscrubs Kknowledge) is a protocol designed to generate a ZKP for any mathematical function. The proof generated is “succinct” and “non-interactive”: a proof is only a few hundred bytes long and can be checked in constant time and in a few milliseconds, without having to ask the prover additional questions. Together, these properties make zk-SNARK particularly suitable for blockchains, where on-chain storage and computation can be expensive and senders often disconnect after sending a transaction. Anonymous cryptocurrency Zcash and smart contract platform Ethereum are among its notable early adopters, among others.
A zk-SNARK consists of the following three algorithms: g ,P andV.
Generator (circuit C, λ is ☣️):
(pk, vk) = G(λ, C)
Prove (x pub inp, w sec inp):
π = P(pk, x, w)
V(vk, x, π) == (∃ w st C(x,w))
— Christian Lundkvist (@ChrisLundkvist) November 19, 2016
A key generator g takes a secret parameter λ and a function VSand produces a proof key pack and a verification key vk. Both keys are made public.
VS is a Boolean function (also called program or circuit) that takes two inputs: a public input X and a private entrance w (alias, witness). For instance, VS can be a function that checks if w is the sha256 preimage of the summary X.
C(x, w) = sha256(w) == x
The prover P takes as input the proof key packa public contribution X and a private witness w produce evidence that the prover knows a witness w which does C(x,w) evaluate to true.
The verifier V take the verification key vkevidence and public input X and accepts evidence only if produced with the knowledge of the witness w¹.
When zk-SNARKs are used in blockchains, key and proof generation is performed off-chain. Only the general verification algorithm is executed inside an on-chain smart contract.
There are several zk-SNARK schemes in the literature. We implement the most widely used Groth16 scheme due to its small proof size and fast verification.
The full code is listed below, based on our elliptic curve arithmetic and matching libraries.
Note that the proof size (Line 23–27) and the number of matches (Line 43–44) are constant, regardless of the complexity of the function. VS to be proven is.
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 see 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 great tutorials such as this series and this article.
 There is one exception. Anyone knows that the secret parameter λ used in the generator can generate a false but valid proof without the knowledge of a witness. This is why we talk about toxic waste. It must be deleted after the secure configuration phase.
Watch: Presentation of the BSV Global Blockchain Convention, Smart Contracts and Computation on BSV
New to Bitcoin? Discover CoinGeek bitcoin for beginners section, the ultimate resource guide to learn about bitcoin – as originally envisioned by Satoshi Nakamoto – and blockchain.