Zero-Knowledge Puzzles

  • paying to a public key on an elliptic curve different from the curve secp256k1 used in Bitcoin today
  • paying to a group of public keys, which can be spent if one knows any of the private key, without revealing which one.

∑ Protocols

A ∑-protocol is a zero knowledge protocol for proving knowledge of values in some relation without disclosing the values themselves. For instance, one proves knowledge of discrete logarithm, i.e., given gand y, prove knowledge of xin gˣ = ywithout revealing x. It consists of three steps between Peggy the prover and Victor the verifier, called commitment, challenge and response, as shown below (the name ∑ comes from the shape).

Figure 1: ∑ Protocol
  1. Peggy computes a commitment A using a random number a. She shares A with Victor, but doesn’t reveal a.
  2. Victor generates a random number e as challenge and shares it with Peggy.
  3. Peggy uses a and e to compute an answer z and sends back to Victor.
Figure 2: ∑ protocol to prove knowledge of x under 𝜑

The Fiat-Shamir Heuristic

The ∑ protocol above requires interaction between Peggy and Victor. We can use the standard Fiat–Shamir heuristic technique to remove the interaction. The basic idea is to emulate Victor’s challenge e using a cryptographic hash function H like sha256. By hashing Y and A, specific to a protocol execution, e can be regarded as random². The new ∑ protocol to prove knowledge of x becomes:

Figure 3: Non-interactive ∑ protocol to prove knowledge of x under 𝜑

Examples of ZK Puzzles

We apply non-interactive ∑ protocols to Bitcoin, where 𝜑(x) = x * G and G is the generator point.

Pay to a Generic Public Key (P2GPK)

We replace signature with proof (e, z), use the ∑ protocol. It is a generalization of the standard Pay to Public Key (P2PK) puzzle. The following code implements the verifier, using our elliptic curve library.

Contract P2GPK
  • It can use curve with higher security, such as secp521r1, than the hardcoded curve secp256k1. This can be desirable if a large amount of bitcoins is controlled by a single key for decades. This also means Bitcoin can upgrade to more secure signature scheme without breaking changes, by implementing it using existing opcodes³.
  • It can reuse compatible keys from elsewhere. For example, PGP supports elliptic curve keys and bitcoins can be sent to PGP keys, even if they are based other curves.

Composition

We have only applied ∑ protocols to a single puzzle, so far. ∑ protocols are modular and can be composed together by using, for example, logical conjunction/AND and disjunction/OR. We can thus construct more advanced puzzles such as:

  • Pay to Group Privately (P2GP): anyone of a group of key owners can spend the funds, without disclosing which one redeemed, using proof from OR composition. This is a generalization of 1-of-n multisig, but more private. For example, Peggy proves she knows the private key of public key Y or Z, i.e., she knows x such that
  • Pay to Threshold Group Privately (P2TGP): any m of n members in a group can collectively redeem the UTXO without revealing which m members, using proof from AND and OR composition. This generalizes P2GP and m-of-n multisig. For example, a 2-of-3 ZK puzzle requires

Acknowledgements

This is a collaboration with nChain on whitepaper 1617: Zero-knowledge Puzzles by Dr. Enrique Larraia.

--

--

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
sCrypt

sCrypt

sCrypt (https://scrypt.io) is a company with a mission to provide integrated on-chain smart contracting solutions on Bitcoin SV