# Programmable Zero Knowledge Proofs Using zk-SNARKs: Part 1

## Prove Knowledge of a Private Key Without Signatures

In theory, a zero-knowledge proof (ZKP) can be constructed for any mathematical problem¹, without revealing this solution. In practice, developing a ZKP for a problem often requires the invention of a whole new cryptographic algorithm. It has no standard recipe and requires extensive and in-depth knowledge of cryptography. For example, ZK puzzle involves ∑-protocols and ZK key-statement proof Pedersen commitments and Fiat-Shamir heuristic.

zk-SNARKs standardize ZKP generation for arbitrary problems. One only needs to express the original problem to be proven in ZK format, such as domain-specific language (DSL) Circom or Zokrates. All the rest is handled by the generic zk-SNARK framework, hiding all the complexities of the underlying cryptography.

Prior to zk-SNARKs, constructing ZKP for a new problem is akin to building a new ASIC whenever a new ZKP application needs to be devised. zk-SNARKs allow building the new ZKP by simply programming a general-purpose “ZK CPU”. The former requires one to be a cryptographer, while the latter only requires one to be a programmer, greatly lowering the barrier to entry of ZKPs.

To demonstrate the power of this paradigm shift, we use it to construct the most popular ZKP: knowledge of the private key for a given public key, aka, discrete logarithm.

# ZKP of Knowledge of a Private Key

To transfer bitcoins locked to a public key/address, an owner has to show he knows the corresponding private key. But he cannot simply disclose it, otherwise bitcoins can be stolen. This is done with a digital signature, a form of ZKP². We show an alternative way to achieve the same using zk-SNARK.

In bitcoin, a public key ** Q** is simply the private key

**multiplies the generator**

*d***.**

*G*The following Circom code implements scalar multiplication over Bitcoin’s elliptic curve secp256k1. We can easily use it prove ** Q** is the public key of

**:**

*d*- Set the input scalar at Line 3 to
: note it is*d**private*and thus remains confidential - Set the input point at Line 4 to
*G* - Set the output at Line 6 to
.*Q*

We use the standard double-and-add algorithm, for ease of exposition. A more efficient algorithm can be found here. The main loop occurs from Line 33 to Line 65. We use ** Secp256k1AddUnequal** at Line 42 for point addition, and

**at Line 43 for point doubling. We keep doubling at Line 355–358 in each iteration. We also add if the current bit is set.**

*Secp256k1Double*Once we have the Circom code, we can use our generic zk-SNARK library to prove knowledge of a private key, while keeping it secret. We have demonstrated the knowledge without a digital signature!

Stay tuned for more examples of ZKPs leveraging the programmability of zk-SNARKs.

# Acknowledgements

This article is inspired by this excellent write up.

[1] In fact, ZKP can be constructed for any NP problem.

[2] We use ZK loosely here.