Private key puzzles

This post was first published on Medium.

We introduce a new type of Bitcoin smart contracts called private key puzzles, which can only be solved by providing the corresponding private key of a given public key.

In previous contracts, only the possession of a private key needs to be proved in the form of digital signatures. The private key is not exposed and kept confidential. In contrast, the private key itself is disclosed in a private key puzzle.

This can be used, for example, when Alice wants to pay Bob to watch a movie online. Bob can encrypt the movie with an ephemeral public key. Alice can get the corresponding private key if Bob redeems her payment locked in a private key puzzle, after which she can decrypt the movie.

Nonce Reuse Attack on ECDSA

To generate signatures, ECDSA takes a private key d, a random number k (called nonce), and the hash of a message h. r is the x-coordinate of the point k * G, where G is the generator.

The signature is the pair (r, s).

Problems arise when the same private key is used to sign different messages with the same nonce k. We will have two signatures (r, s1) and (r, s2). r is the same since k is the same.

We can recover the nonce with:

We can recover the private key with:

Sony PlayStation 3 is hacked by exploring this vulnerability. For this reason, it is crucial to select different k for different signatures.

Private Key Puzzles

We turn the vulnerability on its head and use it to expose a private key indirectly. We intentionally demand two valid signatures over two different messages signed using the same private key and nonce, as shown below.

Contract PrivateKeyPuzzle

We validate two signatures are for the same public key and thus private key, at Line 11 and 14. Function extraRFromSig() at Line 5 allows us to retrieve r from a signature, DER-encoded as below.

Line 17 ensures the same r and thus k is used in two signatures.

The message signed is called a sighash preimage. Note that we insert an OP_CODESEPARATOR at Line 13 to ensure two messages signed are different, since they have distinct scriptCode (part 5 of a sighash preimage).

There are other ways to ensure signed messages are different. For instance, we can use different sighash flags (part 10 of a sighash preimage) when signing.

Contract PrivateKeyPuzzle

sig1 uses NONE and excludes transaction outputs from message signed, while sig2 includes it and is thus different.

Alternative Implementations

There are other ways to force disclosing of a private key:

1. Directly use elliptic curve point multiplication to verify public key equals d * G
2. Use the OP_PUSH_TX technique to verify the private and public key are a pair.

Private key puzzles are much more compact and efficient than them.

Acknowledgements

This article adapts idea from the paper Bitcoin private key locked transactions.

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