This article first appeared on Medium.

Prove knowledge of a private key without signatures

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

zk-SNARKs standardize ZKP generation for arbitrary problems. Simply express the original problem to be proved in ZK format, such as Circom Domain Specific Language (DSL) or Zokrates. Everything else is handled by the generic zk-SNARK framework, hiding all the complexities of the underlying cryptography.

Prior to zk-SNARKs, building ZKP for a new problem was akin to building a new ASIC every time a new ZKP application needs to be designed. zk-SNARKs allow the new ZKP to be built 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, which significantly lowers the barrier to ZKP entry.

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, i.e. the discrete logarithm.

ZKP knowledge of a private key

To transfer bitcoins locked to a public key/address, an owner must show knowledge of the corresponding private key. But he can’t just disclose it, otherwise the bitcoins can be stolen. This is done with a digital signature, a form of ZKP². We show another way to achieve the same result using zk-SNARK.

In Bitcoin, a public key Q is just the private key D multiply generator g.

Equation: Q because the private key d multiplies the generator G

The following Circom code implements scalar multiplication on Bitcoin’s secp256k1 elliptic curve. We can easily use it to prove Q is the public key of D:

  • Set the input scalar at line 3 to D: note that it is private and therefore remain confidential
  • Set the line 4 in point to g
  • Set the line 6 output to Q.

Scalar point multiplication. Credit: 0xPARC/circom-ecdsa

We use the standard double-addition algorithm, to facilitate exposure. A more efficient algorithm can be found here. The main loop goes from line 33 to line 65. We use Secp256k1AddUnequal on line 42 for adding dots, and Secp256k1Double at line 43 to double the points. We continue to double at line 355–358 with each iteration. We also add if the current bit is set.

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 knowledge without a digital signature!

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

Thanks

This article is inspired by this excellent writing.

***

REMARKS:

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

[2] We use ZK freely here.

New to Bitcoin? Discover CoinGeek bitcoin for beginners section, the ultimate resource guide to learn more about Bitcoin – as originally envisioned by Satoshi Nakamoto – and blockchain.