06 - R-Puzzles

R-Puzzles are a means by which the ephemeral key used in the calculation of an elliptic curve signature can be applied to a locking function. R-Puzzles provide additional capabilities to users of the Bitcoin protocol by allowing parties to provide the ephemeral keys to third parties to access specific outputs on the blockchain so that valid signatures can be created.

To achieve this, the R-Puzzle script breaks down a signature in Bitcoin's modified DER format and extracts the R-value, before evaluating it against a value stored in the output script. The Bitcoin DER format is as follows:

Data Item	Example data / notes
Sequence Identifier	0x30
Length of Sequence	0x44 (Variable length, max value 0x46)
Integer Identifier	0x02
Byte-length of r	0x20 (Variable length, max value 0x21)
r	e9d34347e597e8b335745c6f8353580f4cbdb4bcde2794ef7aab915d996642 (Must not be negative)
Integer identifier	0x02
Byte-length of s	0x20 (Variable length, max value 0x21)
s	4f2ccb52c7243c55bde34934bd55efbdac21c74a20bb7b438d1b6de3311f (Low signature coordinate only)
Sighash type	0x41 (SIGHASH_ALL | SIGHASH_FORKID)

An R-Puzzle script is defined as follows:

OP_3 OP_SPLIT OP_NIP OP_1 OP_SPLIT OP_SWAP OP_SPLIT OP_DROP <r-value> OP_EQUAL

Pay to R-Puzzle Hash

This script does not include a signature evaluation so a further extension combines a signature check and hash function into a script called Pay to R-Puzzle Hash (P2RPH).

A P2RPH script is defined as follows:

OP_OVER OP_3 OP_SPLIT OP_NIP OP_1 OP_SPLIT OP_SWAP OP_SPLIT OP_DROP OP_HASH160 <r_hash> OP_EQUALVERIFY OP_CHECKSIG

To spend an output that is locked with a P2RPH script, the following solution is provided:

<signature> <public_key>

The validation engine will evaluate the full script as follows:

<signature> <public_key> OP_OVER OP_3 OP_SPLIT OP_NIP OP_1 OP_SPLIT OP_SWAP OP_SPLIT OP_DROP OP_HASH160 <r_hash> OP_EQUALVERIFY OP_CHECKSIG

A breakdown of the script evaluation process is shown below:

Stack	Script	Description
Empty.	<sig> <pubKey> | | OP_OVER OP_3 OP_SPLIT OP_NIP OP_1 OP_SPLIT OP_SWAP OP_SPLIT OP_DROP OP_HASH160 <r_hash> OP_EQUALVERIFY OP_CHECKSIG	scriptSig and scriptPubKey are combined.
<sig> <pubKey>	OP_OVER OP_3 OP_SPLIT OP_NIP OP_1 OP_SPLIT OP_SWAP OP_SPLIT OP_DROP OP_HASH160 <r_hash> OP_EQUALVERIFY OP_CHECKSIG	Signature and public key are added to the stack
<sig> <pubKey> <sig>	OP_3 OP_SPLIT OP_NIP OP_1 OP_SPLIT OP_SWAP OP_SPLIT OP_DROP OP_HASH160 <r_hash> OP_EQUALVERIFY OP_CHECKSIG	Signature is copied to top of stack.
<sig> <pubKey> <sig> 3	OP_SPLIT OP_NIP OP_1 OP_SPLIT OP_SWAP OP_SPLIT OP_DROP OP_HASH160 <r_hash> OP_EQUALVERIFY OP_CHECKSIG	Constant value '3' is added to top of stack.
<sig> <pubKey> <sig_l3> <sig_r>	OP_NIP OP_1 OP_SPLIT OP_SWAP OP_SPLIT OP_DROP OP_HASH160 <r_hash> OP_EQUALVERIFY OP_CHECKSIG	First 3 bytes of DER encoded signature are split from remainder
<sig> <pubKey> <sig_r>	OP_1 OP_SPLIT OP_SWAP OP_SPLIT OP_DROP OP_HASH160 <r_hash> OP_EQUALVERIFY OP_CHECKSIG	First 3 bytes of DER encoded signature are removed from stack
<sig> <pubKey> <sig_r> 1	OP_SPLIT OP_SWAP OP_SPLIT OP_DROP OP_HASH160 <r_hash> OP_EQUALVERIFY OP_CHECKSIG	Constant value '1' is added to stack
<sig> <pubKey> <r_len> <sig_r>	OP_SWAP OP_SPLIT OP_DROP OP_HASH160 <r_hash> OP_EQUALVERIFY OP_CHECKSIG	The length of r is split from the signature remainder
<sig> <pubKey> <sig_r> <r_len>	OP_SPLIT OP_DROP OP_HASH160 <r_hash> OP_EQUALVERIFY OP_CHECKSIG	Length of r is moved to top of stack
<sig> <pubKey> <r> <sig_r>	OP_DROP OP_HASH160 <r_hash> OP_EQUALVERIFY OP_CHECKSIG	r value is split from signature remainder
<sig> <pubKey> <r>	OP_HASH160 <r_hash> OP_EQUALVERIFY OP_CHECKSIG	Signature remainder is dropped from stack
<sig> <pubKey> <hash160_r>	<r_hash> OP_EQUALVERIFY OP_CHECKSIG	r value is hashed using OP_HASH160
<sig> <pubKey> <hash160_r> <r_hash>	OP_EQUALVERIFY OP_CHECKSIG	Expected r-hash is added to the stack
<sig> <pubKey>	OP_CHECKSIG	Expected r-hash is tested for equality against generated r-hash
true	Empty.	The signature is checked against the public key

As shown above, the spending party must supply a valid signature generated from the public key also provided. Because we don't check the public key, this signature can be generated with any valid public key. The script copies the signature to the top of the stack before extracting the length of the r component, and using this length value to extract r itself. Once r has been separated from the signature, it is hashed and checked against an expected value before the signature is checked for validity against the public key provided. A wallet using R-Puzzles must keep a list of k-values which it needs to sign R-Puzzle inputs. These are mathematically identical to ECDSA public keys.

R-Puzzles can form a useful component of other second layer functionality and can be incorporated into more elaborate scripts for added functionality.