Bitcoin Script Puzzles

Bitcoin scripts can be puzzles of any sort and they don't actually have to depend on the knowledge of a secret key. Complex scripts are replaced by shorter fingerprints in the transaction output, which allows for smaller transaction and less fees.

Scripts can be hashed and encoded as a bitcoin address, hence the term Pay to Script Hash, and sending money to it is the same as sending to a public key hash address.

P2SH shifts the transaction fee cost of a long script from the sender to the recipient, who has to include a large redeem script in the input to spend the UTXO. Doing so, P2SH also alleviate blockchain data storage since the redeem script is not kept in the UTXO-set database.

Finally, P2SH shifts the burden in data storage for the long script from the present time (locking of funds) to a future
time (spending of funds).

However puzzles that doesn't require a signature are insecure.
When a transaction is not signed, an attacker can rewrite it to instead send the value to his address.

Except for hard computational puzzles, if we have the redeemScript, we can find the unlocking script.

Algebra Puzzle - Legacy P2SH

To follow along this tutorial and enter the commands step-by-step

  • Type node in a terminal after cd into ./code for a Javascript prompt
  • Open the Bitcoin Core GUI console or use bitcoin-cli for the Bitcoin Core commands
  • Use bx aka Libbitcoin-explorer as a handy complement

Let's create a simple maths puzzle with a legacy P2SH transaction.

Creating and Funding the P2SH

Import libraries, test wallets and set the network

const bitcoin = require('bitcoinjs-lib')
const { alice } = require('./wallets.json')
const network = bitcoin.networks.regtest

Create the script and generate its address.

const redeemScript = bitcoin.script.compile([
  bitcoin.opcodes.OP_ADD,
  bitcoin.opcodes.OP_5,
  bitcoin.opcodes.OP_EQUAL])
  
console.log('redeemScript  ', redeemScript.toString('hex'))

You can decode the script in Bitcoin Core CLI.

$ decodescript 935587

The p2sh method will generate an object that contains the P2SH address.

const p2sh = bitcoin.payments.p2sh({redeem: {output: redeemScript, network}, network})
console.log('p2sh.address  ', p2sh.address)

Let's fund this address with 1 BTC. This is the reward for whoever as the solution to the locking script.

$ sendtoaddress 2N7WfHK1ftrTdhWej8rnFNR7guhvhfGWwFR 1

We can note that anyone can create this script and generate the corresponding address, it will always result in the same
address.

Get the output index so that we have the outpoint (txid / vout).

Find the output index (or vout) under details > vout.

$ gettransaction "txid"

Preparing the spending transaction

Now let's prepare the spending transaction by setting input and output.

Alice_0 wants to send the funds to her P2WPKH address.

const keyPairAlice0 = bitcoin.ECPair.fromWIF(alice[0].wif, network)
const p2wpkhAlice0 = bitcoin.payments.p2wpkh({pubkey: keyPairAlice0.publicKey, network})

Create a BitcoinJS transaction builder object.

const txb = new bitcoin.TransactionBuilder(network)

Create the input by referencing the outpoint of our P2SH funding transaction.

txb.addInput('TX_ID', TX_VOUT)

Create the output, leaving 100 000 satoshis as mining fees.

txb.addOutput(p2wpkhAlice0.address, 999e5)

Prepare the transaction.

const tx = txb.buildIncomplete()

Creating the unlocking script

Now we can update the transaction with the unlocking script, providing a solution to the maths problem.

We provide 02 and 03 as an answer, plus the redeem script.

const InputScriptP2SH = bitcoin.script.compile([bitcoin.opcodes.OP_2, bitcoin.opcodes.OP_3, p2sh.redeem.output])
tx.setInputScript(0, InputScriptP2SH)

We don't need to sign this transaction since the redeem script doesn't ask for a signature.

Get the raw hex serialization.

No build step here as we have already called buildIncomplete

console.log('tx.toHex()  ', tx.toHex())

Inspect the raw transaction with Bitcoin Core CLI, check that everything is correct.

$ decoderawtransaction "hexstring"

Broadcasting the transaction

It's time to broadcast the transaction via Bitcoin Core CLI.

$ sendrawtransaction "hexstring"

Inspect the transaction.

$ getrawtransaction "txid" true

Observations

We can decrypt the unlocking script in Bitcoin Core CLI with decodescript.
You will notice that it is the concatenation of the corresponding hex value of the specified opcodes, OP_2, OP_3 and
the redeem script OP_ADD OP_5 OP_EQUAL.

Be aware that the hex script is the serialized version, which precede the redeem script by its byte length.
In order to decode the script we need to remove this byte length.

$ decodescript 5253935587

Algebra Puzzle - Native Segwit P2WSH

To follow along this tutorial and enter the commands step-by-step

  • Type node in a terminal after cd into ./code for a Javascript prompt
  • Open the Bitcoin Core GUI console or use bitcoin-cli for the Bitcoin Core commands
  • Use bx aka Libbitcoin-explorer as a handy complement

Read more about P2WSH in BIP141 - Segregated Witness

Let's create a simple maths puzzle with a native Segwit P2WSH transaction.

Creating and Funding the P2WSH

Import libraries, test wallets and set the network

const bitcoin = require('bitcoinjs-lib')
const { alice } = require('./wallets.json')
const network = bitcoin.networks.regtest

Create the witness script and generate its address.

In a P2WSH context, a redeem script is called a witness script.

const witnessScript = bitcoin.script.compile([
  bitcoin.opcodes.OP_ADD,
  bitcoin.opcodes.OP_5,
  bitcoin.opcodes.OP_EQUAL])

The output of our funding transaction will have a locking script composed of <00 version byte> + <32-bytes hash witness program>.
SHA256 of the witnessScript must match the 32-byte witness program.

witnessScript.toString('hex')
// '935587'
bitcoin.crypto.sha256(Buffer.from('935587', 'hex')).toString('hex')
// '0afd85470f76425c9f81a91d37f9ee8ac0289d479a091af64787e0930eef3b5a'

You can decode the script in Bitcoin Core CLI.

$ decodescript 935587

The p2wsh method will generate an object that contains the P2WSH address.

const p2wsh = bitcoin.payments.p2wsh({redeem: {output: witnessScript, network}, network})
console.log('p2wsh.address  ', p2wsh.address)

Send 1 BTC to this P2WSH address, which is the reward for whoever as the solution to the locking script.

$ sendtoaddress bcrt1qpt7c23c0wep9e8up4ywn070w3tqz3828ngy34aj8slsfxrh08ddq2d2pyu 1

We can note that anyone can create this script and generate the corresponding address, it will always result in the same
address.

Get the output index so that we have the outpoint (txid / vout).

Find the output index (or vout) under details > vout.

$ gettransaction "txid"

Preparing the spending transaction

Now let's prepare the spending transaction by setting input and output.

Alice_0 wants to send the funds to her P2WPKH address.

const keyPairAlice0 = bitcoin.ECPair.fromWIF(alice[0].wif, network)
const p2wpkhAlice0 = bitcoin.payments.p2wpkh({pubkey: keyPairAlice0.publicKey, network})

Create a BitcoinJS transaction builder object.

const txb = new bitcoin.TransactionBuilder(network)

Create the input by referencing the outpoint of our P2SH funding transaction.

txb.addInput('TX_ID', TX_VOUT)

Create the output, leaving 100 000 satoshis as mining fees.

txb.addOutput(p2wpkhAlice0.address, 999e5)

Prepare the transaction.

const tx = txb.buildIncomplete()

Creating the witness

Now we can update the transaction with the witness, providing a solution to the maths problem plus the problem itself.

We provide 02 and 03 as an answer, plus the witness script.

Note that we are pushing the integer values, not the corresponding opcode values.

const witness = [Buffer.from('02','hex'), Buffer.from('03','hex'), p2wsh.redeem.output]
tx.setWitness(0, witness)

We don't need to sign this transaction since the witness script doesn't ask for a signature.

Get the raw hex serialization.

No build step here as we have already called buildIncomplete

console.log('tx.toHex()  ', tx.toHex())

Inspect the raw transaction with Bitcoin Core CLI, check that everything is correct.

$ decoderawtransaction "hexstring"

Broadcasting the transaction

It's time to broadcast the transaction via Bitcoin Core CLI.

$ sendrawtransaction "hexstring"

Inspect the transaction.

$ getrawtransaction "txid" true

Observations

In the vin section, we note that the scriptSig field is empty, and that our solution data and witness script are located
in the witness txinwitness field.

The SHA256 hash of the witness script, last item in txinwitness, is compared against the 32-byte hash located in the P2WSH UTXO we are
spending.

The script is then executed with the remaining data from the witness txinwitness field.

Algebra Puzzle - Embedded Segwit P2SH-P2WSH

To follow along this tutorial and enter the commands step-by-step

  • Type node in a terminal after cd into ./code for a Javascript prompt
  • Open the Bitcoin Core GUI console or use bitcoin-cli for the Bitcoin Core commands
  • Use bx aka Libbitcoin-explorer as a handy complement

Read more about in P2WSH nested in BIP16 P2SH

Let's create a simple maths puzzle with an embedded Segwit P2SH-P2WSH transaction.

Creating and Funding the P2SH-P2WSH

Import libraries, test wallets and set the network

const bitcoin = require('bitcoinjs-lib')
const { alice } = require('./wallets.json')
const network = bitcoin.networks.regtest

Create the witness script and generate its address.

const witnessScript = bitcoin.script.compile([
  bitcoin.opcodes.OP_ADD,
  bitcoin.opcodes.OP_5,
  bitcoin.opcodes.OP_EQUAL])
  
console.log('witnessScript  ', witnessScript.toString('hex'))

You can decode the script in Bitcoin Core CLI.

$ decodescript 935587

Put the p2wsh object into the p2sh redeem parameter.

const p2wsh = bitcoin.payments.p2wsh({redeem: {output: witnessScript, network}, network})
const p2sh = bitcoin.payments.p2sh({redeem: p2wsh, network: network})
console.log('p2sh.address:  ', p2sh.address)

Send 1 BTC to this P2SH-P2WSH address, which is the reward for whoever as the solution to the locking script.

$ sendtoaddress 2MwnRrQxKhCdr8e3vbL7ymhtzQFYPTx9xww 1

We can note that anyone can create this script and generate the corresponding address, it will always result in the same
address.

Generate one block so that we can spend the UTXO.

$ generate 1

Get the output index so that we have the outpoint (txid / vout).

Find the output index (or vout) under details > vout.

$ gettransaction "txid"

Preparing the spending transaction

Now let's prepare the spending transaction by setting input and output.

Alice_0 wants to send the funds to her P2WPKH address.

const keyPairAlice0 = bitcoin.ECPair.fromWIF(alice[0].wif, network)
const p2wpkhAlice0 = bitcoin.payments.p2wpkh({pubkey: keyPairAlice0.publicKey, network})

Create a BitcoinJS transaction builder object.

const txb = new bitcoin.TransactionBuilder(network)

Create the input by referencing the outpoint of our P2SH funding transaction.

txb.addInput('TX_ID', TX_VOUT)

Create the output, leaving 100 000 satoshis as mining fees.

txb.addOutput(p2wpkhAlice0.address, 999e5)

Prepare the transaction.

const tx = txb.buildIncomplete()

Creating the witness

Now we can update the transaction with the version byte 0 and the witness program that will be placed in the scriptSig
field, and the witness composed of the solution to our maths problem (witness stack) and the maths problem itself (witness script).

When we are spending from a P2WSH UTXO the witness script hash is produced automatically.
However, when we are spending from a P2SH UTXO (our P2SH-P2WSH is a regular P2SH UTXO), we need to place the witness
script hash ourselves in the scriptSig, preceded by a 0 version byte so that the interpreter recognizes that it actually
is a witness program.
If the version byte is 0 and the witness program is 32 bytes it is interpreted as a P2WSH program.

Create the input script.

Serialized version byte + witness program: <0 <32-byte-hash>>

const scriptSig = bitcoin.script.compile([p2wsh.output])
tx.setInputScript(0, scriptSig)

The only item in scriptSig <0 <32-byte-hash>> is hashed with HASH160, compared against the 20-byte-hash in the locking
script of the P2SH UTXO we are spending, and interpreted as 0 <32-byte-hash>.

HASH160 of the scriptSig asm version, without pushbytes(22).

bitcoin.crypto.hash160(scriptSig.slice(1)).toString('hex')
// '31c74d4132ecfdb577695cd23be18346f048cb24'

We create the witness stack, providing 02 and 03 as an answer, plus the witness script.

Note that we are pushing the integer values, not the corresponding opcode values.

const witness = [Buffer.from('02','hex'), Buffer.from('03','hex'), p2wsh.redeem.output]
tx.setWitness(0, witness)

We don't need to sign this transaction since the witness script doesn't ask for a signature.

Get the raw hex serialization.

No build step here as we have already called buildIncomplete

console.log('tx.toHex()  ', tx.toHex())

Inspect the raw transaction with Bitcoin Core CLI, check that everything is correct.

$ decoderawtransaction "hexstring"

Broadcasting the transaction

It's time to broadcast the transaction via Bitcoin Core CLI.

$ sendrawtransaction "hexstring"

Inspect the transaction.

$ getrawtransaction "txid" true

Observations

In the vin section, we note that the scriptSig contains a 0 version byte and a witness program, which is the SHA256
32-bytes hash of the witness script.

ScriptSig (asm version) is hashed with HASH160 and compared against the 20-byte-hash in the locking script of the UTXO
we are spending.

bitcoin.crypto.hash160(Buffer.from('00200afd85470f76425c9f81a91d37f9ee8ac0289d479a091af64787e0930eef3b5a', 'hex')).toString('hex')
// '31c74d4132ecfdb577695cd23be18346f048cb24'

ScriptSig is then interpreted as a P2WSH and triggers the execution of the witness script.

Computational Puzzle: SHA-1 Collision

To follow along this tutorial and enter the commands step-by-step

  • Type node in a terminal after cd into ./code for a Javascript prompt
  • Open the Bitcoin Core GUI console or use bitcoin-cli for the Bitcoin Core commands
  • Use bx aka Libbitcoin-explorer as a handy complement

On September 13, 2013, Peter Todd, a renowned Bitcoin Core developer, announced a bounty on BitcoinTalk forum. As he explain himself,
"rewards at P2SH addresses are available for anyone able to demonstrate collision attacks against a variety of cryptographic algorithms.
You collect your bounty by demonstrating two messages that are not equal in value, yet result in the same digest when hashed.
These messages are used in a scriptSig, which satisfies the scriptPubKey storing the bountied funds, allowing you to
move them to a scriptPubKey (Bitcoin address) of your choice".

On the February 23, 2017, someone successfully claimed the SHA-1 hash collision bounty of 2.48 BTC, with this transaction
8d31992805518fd62daa3bdd2a5c4fd2cd3054c9b3dca1d78055e9528cff6adc

To read more about Bitcoin computational puzzles and Peter Todd bounties

Let's recreate the Peter Todd bounty for SHA-1 hash collision.

Creating and Funding the P2SH

Import libraries, test wallets and set the network

const bitcoin = require('bitcoinjs-lib')
const { alice } = require('./wallets.json')
const network = bitcoin.networks.regtest

Create the script and generate its address.

const redeemScript = bitcoin.script.compile([
  bitcoin.opcodes.OP_2DUP,
  bitcoin.opcodes.OP_EQUAL,
  bitcoin.opcodes.OP_NOT,
  bitcoin.opcodes.OP_VERIFY,
  bitcoin.opcodes.OP_SHA1,
  bitcoin.opcodes.OP_SWAP,
  bitcoin.opcodes.OP_SHA1,
  bitcoin.opcodes.OP_EQUAL])
  
console.log('redeemScript  ', redeemScript.toString('hex'))

You can decode the redeem script in Bitcoin Core CLI.

$ decodescript 6e879169a77ca787

The p2sh method will generate an object that contains the P2SH address.

const p2sh = bitcoin.payments.p2sh({redeem: {output: redeemScript, network}, network})

Let's fund this address with 1 BTC. This is the reward for whoever as the solution to the locking script.

$ sendtoaddress 2MyJKxYR2zNZZsZ39SgkCXWCfQtXKhnWSWq 1

Get the output index so that we have the outpoint (txid / vout).

Find the output index (or vout) under details > vout.

$ gettransaction "txid"

Preparing the spending transaction

Now let's prepare the spending transaction by setting input and output.

Alice_0 wants to send the funds to her P2WPKH address.

const keyPairAlice0 = bitcoin.ECPair.fromWIF(alice[0].wif, network)
const p2wpkhAlice0 = bitcoin.payments.p2wpkh({pubkey: keyPairAlice0.publicKey, network})

Create a BitcoinJS transaction builder object.

const txb = new bitcoin.TransactionBuilder(network)

Create the input by referencing the outpoint of our P2SH funding transaction.
Create the output, leaving 100 000 satoshis as mining fees.

txb.addInput('TX_ID', TX_VOUT)
txb.addOutput(p2wpkhAlice0.address, 999e5)

Prepare the transaction.

const tx = txb.buildIncomplete()

Creating the unlocking script

Now we can update the transaction with the unlocking script, providing a solution to the SHA-1 bounty.

Here are the two values that have been used to claim the Peter Todd bounty.

const value_1 = '255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017f46dc93a6b67e013b029aaa1db2560b45ca67d688c7f84b8c4c791fe02b3df614f86db1690901c56b45c1530afedfb76038e972722fe7ad728f0e4904e046c230570fe9d41398abe12ef5bc942be33542a4802d98b5d70f2a332ec37fac3514e74ddc0f2cc1a874cd0c78305a21566461309789606bd0bf3f98cda8044629a1'
const value_2 = '255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017346dc9166b67e118f029ab621b2560ff9ca67cca8c7f85ba84c79030c2b3de218f86db3a90901d5df45c14f26fedfb3dc38e96ac22fe7bd728f0e45bce046d23c570feb141398bb552ef5a0a82be331fea48037b8b5d71f0e332edf93ac3500eb4ddc0decc1a864790c782c76215660dd309791d06bd0af3f98cda4bc4629b1'

We provide the two values above as the answer, plus the redeem script.

const InputScriptP2SH = bitcoin.script.compile([
  Buffer.from(value_1, 'hex'),
  Buffer.from(value_2, 'hex'), 
  p2sh.redeem.output
])
tx.setInputScript(0, InputScriptP2SH)

In order to push data we should use OP_PUSHDATA
Here, regarding the length of the values, we should use OP_PUSHDATA2, followed by two bytes that contain the number of
bytes to be pushed onto the stack in little endian order.
Fortunately, BitcoinJS is taking care of that for us.
If you inspect InputScriptP2SH, you will see that the values are preceded by 4d4001.
4d is the OP_PUSHDATA2 opcode

We don't need to sign this transaction since the redeem script doesn't ask for a signature.

Get the raw hex serialization.

No build step here as we have already called buildIncomplete

console.log('tx.toHex()  ', tx.toHex())

Inspect the raw transaction with Bitcoin Core CLI, check that everything is correct.

$ decoderawtransaction "hexstring"

Broadcasting the transaction

It's time to broadcast the transaction via Bitcoin Core CLI.

$ sendrawtransaction "hexstring"

Inspect the transaction.

$ getrawtransaction "txid" true

Observations

Check the hash collision

bitcoin.crypto.sha1(Buffer.from(value_1, 'hex')).toString('hex')
bitcoin.crypto.sha1(Buffer.from(value_2, 'hex')).toString('hex')

Both returns the same hash, f92d74e3874587aaf443d1db961d4e26dde13e9c.

Peter Todd's other bounties (SHA256, RIPEMD160, RIPEMD160-SHA256, SHA256-SHA256) remain unclaimed at the time of this writing. They're all written in the same manner as the SHA-1 example above.