R-Puzzles

An R-Puzzle is a new type of script that allows for the spending party to sign the input UTXO using any valid Bitcoin keypair. This can be used to sign Metanet node addresses or addresses that hold tokens, or be randomly generated.

k

In an R-puzzle, a knowledge proof of a value called 'k' is used to allow coins to be spent. 'k' is from the same mathematical set as Bitcoin Private Keys and must be known to the spender and used to generate 'r', which is the x-coordinate of k multiplied by the Generator point. 'r' is extracted from the signature used in the transaction and tested against a hash stored in the ScriptPubKey. k-chains can be managed using the same deterministic techniques as Bitcoin keychains.

Generating an ECDSA signature involves a few steps.

Inputs to the signature:

1. k value 'k'
2. keypair 'P1' = 'S1' · G
3. Message 'm'

Method:

1. Calculate R = k · G
2. Define r = x-coordinate of R
3. Calculate s = k^-1(H(m) + S₁ * r)mod n

Signature is (r, s) plus 5 bytes of formatting and a SIGHASH type

Signature Structure

Data Structure	Length	Data (hex)
Sequence Identifier	1	30
Length of Sequence	1	46
Integer Identifier	1	02
Byte-length of r	1	21
Needed when left(r, 1) > 7f	1	00 NOTE: This byte is not always needed
r	32	e9d34347e597e8b335745c6f8353580f4cbdb4bcde2794ef7aab915d996642
Integer identifier	1	02
Byte-length of s	1	21
Needed when left(s, 1) > 7f	1	00
s		df2ccb52c7243c55bde34934bd55efbdac21c74a20bb7b438d1b6de3311f
Sighash type	1	01

When serialised the signature looks like this:

3046022100e9d34347e597e8b335745c6f8353580f4cbdb4bcde2794ef7aab915d996642022100df2ccb52c7243c55bde34934bd55efbdac21c74a20bb7b438d1b6de3311f01

Extracting r

The following piece of script pulls r out of the signature string by extracting first the length of R which is the 4th byte of the packet, and then using it to split r from the signature.

OP_3 OP_SPLIT OP_NIP OP_1 OP_SPLIT OP_SWAP OP_SPLIT OP_DROP

Stack	Script	Description
<sig>	OP_3 OP_SPLIT OP_NIP OP_1 OP_SPLIT OP_SWAP OP_SPLIT OP_DROP	scriptSig is loaded, signature on the stack
<3 bytes> <sig'>	OP_NIP OP_1 OP_SPLIT OP_SWAP OP_SPLIT OP_DROP	First 3 bytes of signature are split
<sig'>	OP_1 OP_SPLIT OP_SWAP OP_SPLIT OP_DROP	3 byte data item is removed
<r Length> <sig">	OP_SWAP OP_SPLIT OP_DROP	1 byte containing r length is split from sig'
<sig"> <r Length>	OP_SPLIT OP_DROP	r Length parameter is moved to top of stack
<r> <sig'">	OP_DROP	r is split from sig"
<r>		sig'"== is dropped from stack, leaving r

P2RPH

Packaging this subscript into the following gives a Pay to R-Puzzle Hash script: OP_OVER OP_3 OP_SPLIT OP_NIP OP_1 OP_SPLIT OP_SWAP OP_SPLIT OP_DROP OP_HASH160 <Hash(r)> OP_EQUALVERIFY OP_CHECKSIG

Security Considerations

Since the R-Puzzle method has been published, concerns have arisen around possible issues with using them improperly.

Leaking Private Keys

If two signatures are published using the same k then anyone who knows the value of k can derive the secret key used to create the signatures.

Solution To mitigate this issue, ensure that the same k value and private key are never used to create more than one signature.

Signature Forgeability

There is a second flaw which can be exploited by a miner or malicious party who is trying to claim funds by malleating a transaction to change the outputs. The malicious party can modify the transaction to send the funds to themselves while using the same signature that the spender uses in the transaction. The exploit malleates the private key such that the modified transaction hash still produces the same when the ECDSA signature is calculated.

Solution A possible solution is to include another signature <sig'> in the unlocking script and apply it to a different message using modified sighash flags. <sig'> must also use a different value of r so as not to leak the private key.

This solution would propose the following input solution:

<sig'> <pubkey> <sig_r>

R-Puzzle Use Cases

• Delegation of authority
• Tokens
• Multi-signature schemes (with advanced scripting)