Zero-Knowledge Puzzles

Upgrade Bitcoin’s Elliptic Curve Without a Fork and More

This is the third installment of our collaboration with nChain. We would like to give special thanks to Dr Enrique Larraia for authoring the whitepaper this article is based on and helping guide the implementation.

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:

∑ 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

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.

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

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 𝜑

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.

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:

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

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

Acknowledgements

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

[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.

--

--

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 (https://scrypt.io) is a company with a mission to provide integrated on-chain smart contracting solutions on Bitcoin SV