Zero-knowledge puzzles

Getting your Trinity Audio player ready...

This post was first published on Medium.

Upgrade Bitcoin’s Elliptic Curve without a fork and more

A standard payment transaction can be regarded as a public key puzzle. Anyone can spend if he knows the corresponding private key of a given address/public key. Different from a hash puzzle where the preimage is revealed when spending, the solution of a public key puzzle, the private key, is never revealed. This is achieved using digital signatures, a form of zero-knowledge proof: one proves the knowledge of a private key without disclosing it.

We generalize the proof of knowledge of a private key using standard zero-knowledge proof techniques. Consequently, we can construct arbitrary complex puzzles, called zero-knowledge (ZK) puzzles, as spending conditions. Some use cases include:

• 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).

As an example, Peggy wants to convince Victor she know x in Y = 𝜑(x) without revealing x, in which 𝜑 is a function¹. Both parties receive Y as an input.

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.

Victor accepts that Peggy knows x if the equation holds, which can be checked based on public information A, Y, z and e.

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:

There is only one step: Peggy sends Victor the proof (e, z). Victor derives A using the equation in Figure 2 and checks if e == H(Y || A) holds.

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 is the same verification as in Figure 3, except that we also add sighash preimage in H, just like what bitcoin signing currently does. Otherwise, an attacker can change the transaction and redirect the coins to his address, since the proof is publicly known in the unlocking script, i.e., arguments to function unlock() above. H is instantiated to SHA256 at Line 17.

P2GPK enjoys several benefits over built-in signature checking.

• 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

x * G == Y || x * G == Z

• 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

x * G == X && y* G == Y || x * G == X && z * G == Z || y * G == Y && z * G == Z

Acknowledgements

This is an implementation of nChain whitepaper 1617.

***

NOTES:

[1] 𝜑 has to be a one-way group homomorphism, such as discrete log.

[2] Assume H is a random oracle.

[3] Hash function such as sha256 and ripemd160 can be upgraded similarly.

Watch: CoinGeek New York presentation, Smart Contracts & Computation on Bitcoin