Dissecting a Bitcoin Script
In the book Programming Bitcoin by Jimmy Song at the end of Chapter 6 we are presented with the following Bitcoin script as part of an exercise.
What is the following supposed to do?
OP_2DUP, OP_EQUAL, OP_NOT, OP_VERIFY, OP_SHA1, OP_SWAP, OP_SHA1, OP_EQUALLet’s take a step back. What are we looking at?
It’s a bunch of operation codes. Opcodes. They specify the operation to be performed. They are what makes up Bitcoins Smart Contract Programming language.
Wait. Smart Contracts in Bitcoin? Isn’t that what Ethereum was created for?
In a sense yes. In Ethereum we could be more expressive. For example by using loops. Whether the added expressiveness is helpful would depend on who we ask.
Bitcoin offers a way of programming Smart Contracts using the stack based Bitcoin Script. No loops. We will get to what stack-based is supposed to be now.
We take a look at the script again
OP_2DUP, OP_EQUAL, OP_NOT, OP_VERIFY, OP_SHA1, OP_SWAP, OP_SHA1, OP_EQUALWhen ordering the the opcodes. They will be applied in the listed order. OP_2DUP first.
The stack is currently empty. All we have is the script.
We can find out what the Opcodes are doing in the Bitcoin Wiki for Script.
OP_2DUP is on top. It will be applied first. It will duplicate the top two stack items.
OP_2DUP tells us we need to have two items on the stack.
Let’s take the numbers 1 and 1 and play through what will happen when evaluating the script. We put the two numbers on the stack. They are the input to our script.
After applying OP_2DUP we are left with.
The two items on top of the stack were duplicated. OP_2DUP was applied.
On to OP_EQUAL. It returns a 1 if the inputs are equal. Else a 0. OP_EQUAL is applied and of course 1 is equal to 1. Thus we are left with a 1.
OP_NOT flips the input if its a 1 or a 0. A 0 would become a 1 and a 1 would become a 0. If the input is anything other than 1 or 0 the output is a 0.
When applying OP_NOT it will flip the top value. It becomes a 0 (false). Because the input is 1 (true).
OP_VERIFY pops the top stack value and mark the transaction as invalid if is not 1. Because it is a 0 the transaction will be invalid. Evaluation stops.
Of course we want the script to continue to learn what it does.
For it to continue we need to have a 1 on the stack when OP_VERIFY is applied. To have a 1 on the stack the previous OP_NOT needs to flip a 0 to 1. The 0 would have to be the output of OP_EQUAL. Meaning the two inputs can’t be equal.
Because we used the same inputs, two 1, we destined the transaction to fail from the start.
Let’s go for another evaluation. Using two different inputs. 1 and 2.
After we apply OP_2DUP. Duplicating the top two values.
Now OP_EQUAL. 1 and 2 are not equal. The 0 (false) is put on the stack.
We apply OP_NOT. The Input (0) is flipped to 1
In our last go we have stopped at that point because the top value was a 0. We apply OP_VERIFY. Since the top value is 1 everything is fine and the 1 on top gets removed (popped).
OP_SHA1 hashes the input using SHA-1. A cryptographic hash function. The input 1 is hashed and we have
OP_SWAP swaps the two top items on the stack and we are left with.
While OP_SHA1 hashes the 2
We can already guess these two hashes are not equal. OP_EQUAL returns a 0. The final result is 0 (false). The script execution was a failure.
So how do we get here with two hashes that are equal?
The hash of 1 is always the same. We can’t use the same inputs as we learned when we used 1 and 1.
But we need to have two different values on the stack in the beginning to not end up with an invalid transaction.
Different values lead to different hashes. Or don’t they? If two different values would end up with the same hash we have a hash collision.
The script above was used to offer a reward, or the ability to spend, for someone who can produce different values that lead to the same hash. Usually the ability to spend requires us to prove ownership of the private key.
It was set up by Peter Todd in 2013. The reward of 2.48 BTC was claimed in 2017 after the first SHA-1 hash collision was found by researchers.
If we check the transaction details we see the inputs used were
255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017f46dc93a6b67e013b029aaa1db2560b45ca67d688c7f84b8c4c791fe02b3df614f86db1690901c56b45c1530afedfb76038e972722fe7ad728f0e4904e046c230570fe9d41398abe12ef5bc942be33542a4802d98b5d70f2a332ec37fac3514e74ddc0f2cc1a874cd0c78305a21566461309789606bd0bf3f98cda8044629a1and
255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017346dc9166b67e118f029ab621b2560ff9ca67cca8c7f85ba84c79030c2b3de218f86db3a90901d5df45c14f26fedfb3dc38e96ac22fe7bd728f0e45bce046d23c570feb141398bb552ef5a0a82be331fea48037b8b5d71f0e332edf93ac3500eb4ddc0decc1a864790c782c76215660dd309791d06bd0af3f98cda4bc4629b1The different parts are marked bold.
In the shattered.io paper the identical prefix and the colliding message blocks from above can be found on page 3 and 4.
Does this matter for Bitcoin? Not really. OP_SHA1 is an opcode that is barely used. Bitcoin itself depends on SHA-256.
Hopefully the article has shown how we can use a Bitcoin Script for more than “just” proving we are in control of the private keys allowing us to spend.
