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.
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:
- k value 'k'
- keypair 'P1' = 'S1' · G
- Message 'm'
- Calculate R = k · G
- Define r = x-coordinate of R
- Calculate s = k-1(H(m) + S1 * r)mod n
Signature is <r, s> plus 5 bytes of formatting and a SIGHASH type
|Data Structure||Length||Data (hex)|
|Length of Sequence||1||46|
|Byte-length of r||1||21|
|Needed when left(r, 1) > 7f||1||00 NOTE: This byte is not always needed|
|Byte-length of s||1||21|
|Needed when left(s, 1) > 7f||1||00|
When serialised the signature looks like this:
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
|<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|
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
Protecting 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.
To mitigate this issue, ensure that the same k value and private key are never used to create more than one signature.
Given an R-puzzle signature <r, s>, a public key P, and a message m, a forger can create a different message m', and calculate a new public key P' such that:
P' = P + [ r -1 [ H(m) - H(m') ] ] · G
Then signature <r, s> is a valid signature on message m' with respect to the public key P'. Note that, the forger does not know and does not need to know the private key corresponding to P' in this forgery.
When implementing R-puzzle, it is important to take this into account.
One way to mitigate this is to require another signature to prove that the signer knows the private key corresponding to the public key used in the R-puzzle. That is, two signatures in the unlocking script, <r, s> and <r', s'>, and one public key P. It is important to have r not equal r' for the first security consideration. Both signatures should be valid subject to the same public key P.
This solution would propose the following input solution:
<sig'> <pubkey> <sigr>
which spends outputs with the following script:
OP_DUP OP_3 OP_SPLIT OP_NIP OP_1 OP_SPLIT OP_SWAP OP_SPLIT OP_DROP OP_HASH160 <rhash> OP_EQUALVERIFY OP_OVER OP_CHECKSIGVERIFY OP_CHECKSIG
R-Puzzle Use Cases
- Delegation of authority
- Multi-signature schemes (with advanced scripting)