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 zeroknowledge proof: one proves the knowledge of a private key without disclosing it.
We generalize the proof of knowledge of a private key using standard zeroknowledge proof techniques. Consequently, we can construct arbitrary complex puzzles, called zeroknowledge (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.
 Peggy computes a commitment A using a random number a. She shares A with Victor, but doesn’t reveal a.
 Victor generates a random number e as challenge and shares it with Peggy.
 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 FiatShamir 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 noninteractive ∑ 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.
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 builtin 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 1ofn 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 mofn multisig. For example, a 2of3 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 oneway 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