Pay to R Puzzle Hash

Ty Everett ([e-mail])

Abstract

The R-puzzle technique is a powerful cryptographic tool that can be used to create Bitcoin output scripts that can be unlocked by anyone who is able to solve for a value k, without revealing k to the world. The technique relies on the fact that in an ECDSA digital signature, the R component is computed by multiplying a generator point on the elliptic curve with this k-value. By constructing a Bitcoin output script that requires knowledge of this value, it is possible to create puzzles that can be solved by anyone who is able to compute the correct value for k. The R-puzzle technique is flexible and can be used for a variety of applications, including those that benefit when the solver does not reveal their solution to the world, only proving knowledge of it. R-puzzles also provide a way to create Bitcoin output scripts that can be unlocked without requiring knowledge of a specific private key, while still maintaining a high level of security and cryptographic strength. By serializing short-hand script templates in a standard way, implementers can maintain ecosystem-wide compatibility.

Motivation

The creation of puzzles that can be unlocked by anyone who is able to solve a complex problem has become increasingly popular in recent years, particularly in the field of distributed computing. However, it is important to ensure that these puzzles are designed in such a way that they maintain a high level of security and cryptographic strength, while still allowing anyone to solve them without revealing any sensitive information.

To achieve this, it is valuable to create a script template that enables the solver to prove knowledge over a value, k, without revealing the k-value to the world. This provides a way to create puzzles that are secure and difficult to solve, while still allowing anyone to claim the solution and the associated rewards. In addition, it is desirable to employ a script template that does not require the creator of the puzzle to know which key will be used by the solver in claiming the solution, at the time the puzzle was created. Finally, there is also a need to standardize the way these scripts are expressed and exchanged between users of the Bitcoin network, to enable greater cross-compatibility and wider adoption.

Specification

We specify the following Bitcoin script template for R-puzzles:

.unlock
  <ECDSA sig>              # This is the first stack element and represents the ECDSA digital signature provided by the 
                           # solver. It must have an R component that, when hashed with SHA256 and then RIPEMD160, 
                           # produces the same value as the <hash> specified in the locking script. The S component can 
                           # be computed using any key of the solver's choosing.
  <key>                    # This is the second stack element and represents the private key that was used to compute the S component of the 
                           # signature. It can be any key of the solver's choosing, as long as it produces a valid S component for the signature that 
                           # was provided as the first stack element.

.lock
  OVER                     # Duplicates the second stack element (the signature) so that it can be used later in the script. Now the stack has 
                           # three elements, <signature> <key> <signature> and we can work with the top <signature> without bothering the bottom one.
  3 SPLIT                  #
  NIP                      #
  TRUE SPLIT               # This section of the script picks out the R-value from the signature.
  SWAP                     #
  SPLIT                    #
  DROP                     # 
  HASH160                  # Here, we hash the R-value with SHA256 and then again with RIPEMD160 (the combined operation is HASH160).
  <hash> EQUALVERIFY       # The hash we calculated in the previous step is compared with <hash> and if they are not equal then the script fails.
  CHECKSIG                 # Finally, the ECDSA signature is checked.

We specify that the same private key and k-value must NEVER EVER be used, and that steps MUST be taken to prevent the same private key and k-value from ever being used to sign different messages in ECDSA. Failure to follow this provision will result in leakage of private keys and k-values.

Serialization Format (Base58)

We specify that the P2RPH output script is serialized using Base58 encoding. The serialized format is as follows:

[Version Bytes][RPuzzleHash][Checksum]

Where:

• [Version Bytes] is a prefix that identifies the network and the script type. The value of the version byte is 0x0e00 for the mainnet and 0x1c00 for the testnet.

• [PubKeyHash] is a 20-byte RIPEMD160 hash of the SHA256 hash of the R-value.

• [Checksum] is a 4-byte checksum computed using the first four bytes of the double-SHA256 hash of the serialized script.

Examples

P2RPH Bitcoin addresses for mainnet always start with an R because the [Version Bytes] we selected are 0x0e00. On testnet, they will always start with lowercase r because the [Version Bytes] are 0x1c00.

Mainnet example P2RPH address: RsQphNVccTzET8zwMNESLmTeJ4cJYxyc9cx

Testnet example P2RPH address: rjQPANNiecDK1a6jedyCsQ6UND4SnK6rJNe

How it Works

The locking script is the script that is attached to the Bitcoin output that is being locked with the R-puzzle. When a Bitcoin transaction is created that spends this output, the unlocking script must provide the correct input to satisfy this locking script.

The locking script essentially creates a puzzle that can only be unlocked by providing an ECDSA digital signature that satisfies certain conditions. Specifically, the signature must have an R component that, when hashed with SHA256 and then RIPEMD160, produces the same value as the <hash> specified in the script. The S component of the signature can be computed using any key of the solver's choosing.

The unlocking script essentially satisfies the conditions set out by the locking script by providing a valid ECDSA digital signature with an R component that matches the hash specified in the locking script, and an S component that is computed using the solver's chosen private key.

The locking and unlocking scripts for the R-puzzle comprise a powerful and flexible tool for creating puzzles that can be solved by anyone who is able to compute the correct value for the k parameter used in the ECDSA digital signature. By using this technique, it is possible to create Bitcoin outputs that can be unlocked by anyone who is able to solve the puzzle, without requiring knowledge of a specific private key.

Security Considerations

It is crucial to emphasize the importance of never using the same private key and k-value for different messages in ECDSA. Doing so can compromise the security of the digital signatures and result in the leakage of private keys and k-values, which can lead to the loss of funds or assets associated with those signatures.

Therefore, it is essential to take steps to ensure that private keys and k-values are never reused. One way to achieve this is by using a secure random number generator to generate new values for each signature. It is also important to store private keys securely and to use secure communication channels when transmitting them.

To further emphasize the importance of this provision, it is advisable to include clear warnings and instructions in any documentation or educational material related to the R-puzzle technique. This will help ensure that users understand the potential risks of reusing private keys and k-values and take the necessary precautions to prevent such incidents from occurring.

Implementations

The first-known implementation for R-puzzles was created by Dean Little.