NOTE: This is a draft in progress, so that I can get some feedback from early reviewers. It is not yet ready for learning.
Bitcoin Scripts don't actually have to depend on the knowledge of a secret key. They can instead be puzzles of any sort.
Our first real Script, from §7.2: Running a Bitcoin Script was an alegbraic puzzle. That Bitcoin Script, OP_ADD 99 OP_EQUAL, could have been alternatively described as x + y = 99.
This sort of Script doesn't have a lot of applicability in the real world, as it's too easy to claim the funds. But, a puzzle-solving contest giving out Bitcoin dust might offer it as a fun entertainment.
More notably, creating alegebraic puzzles gives you a nice understanding of how the arithmetic functions in Bitcoin Script work.
Bitcoin Script has a number of opcodes that were disabled to maintain the security of the system. One of the is OP_MUL, which would have allowed multiplication ... but is instead disabled.
So, how would you write an algebraic function like 3x + 7 = 13?
The most obvious answer is to OP_DUP the number input from the locking script twice. Then you can push the 7 and keep adding until you get your total. The full locking script would look like this: OP_DUP OP_DUP 7 OP_ADD OP_ADD OP_ADD 13 OP_EQUAL.
Here's how it would run if executed with the correct unlocking script of 2:
Script: 2 OP_DUP OP_DUP 7 OP_ADD OP_ADD OP_ADD 13 OP_EQUAL
Stack: [ ]
Script: OP_DUP OP_DUP 7 OP_ADD OP_ADD OP_ADD 13 OP_EQUAL
Stack: [ 2 ]
Script: OP_DUP 7 OP_ADD OP_ADD OP_ADD 13 OP_EQUAL
Running: 2 OP_DUP
Stack: [ 2 2 ]
Script: 7 OP_ADD OP_ADD OP_ADD 13 OP_EQUAL
Running: 2 OP_DUP
Stack: [ 2 2 2 ]
Script: OP_ADD OP_ADD OP_ADD 13 OP_EQUAL
Stack: [ 2 2 2 7 ]
Script: OP_ADD OP_ADD 13 OP_EQUAL
Running: 2 7 OP_ADD
Stack: [ 2 2 9 ]
Script: OP_ADD 13 OP_EQUAL
Running: 2 9 OP_ADD
Stack: [ 2 11 ]
Script: 13 OP_EQUAL
Running: 2 11 OP_ADD
Stack: [ 13 ]
Script: OP_EQUAL
Stack: [ 13 13 ]
Script:
Running: 13 13 OP_EQUAL
Stack: [ True ]
See also the WebBTC Debug Execution of this script.
What if you wanted to instead write an equation system, such as x + y = 3, y + z = 5, and x + z = 4? A bit of algebra tells you that the answers come out to x = 1, y = 2, and z = 3. But, how do you script it?
Most obviously, after the redeemer inputs the three numbers, we're going to need two copies of each numbers, since each number goes into two different equations. OP_3DUP takes care of that and results in x y z x y z being on the stack. Popping off two items at a time will give us y z, z x, and x y. Voila! That's our three equations, so we just need to add them up and test them in the right order! Here's the full script: OP_3DUP OP_ADD 5 OP_EQUALVERIFY OP_ADD 4 OP_EQUALVERIFY OP_ADD 3 OP_EQUAL.
Here's how it runs with the correct unlocking script of 1 2 3:
Script: 1 2 3 OP_3DUP OP_ADD 5 OP_EQUALVERIFY OP_ADD 4 OP_EQUALVERIFY OP_ADD 3 OP_EQUAL
Stack: [ ]
Script: OP_3DUP OP_ADD 5 OP_EQUALVERIFY OP_ADD 4 OP_EQUALVERIFY OP_ADD 3 OP_EQUAL
Stack: [ 1 2 3 ]
Script: OP_ADD 5 OP_EQUALVERIFY OP_ADD 4 OP_EQUALVERIFY OP_ADD 3 OP_EQUAL
Running: 1 2 3 OP_3DUP
Stack: [ 1 2 3 1 2 3 ]
Script: 5 OP_EQUALVERIFY OP_ADD 4 OP_EQUALVERIFY OP_ADD 3 OP_EQUAL
Running: 2 3 OP_ADD
Stack: [ 1 2 3 1 5 ]
Script: OP_EQUALVERIFY OP_ADD 4 OP_EQUALVERIFY OP_ADD 3 OP_EQUAL
Stack: [ 1 2 3 1 5 5 ]
Script: OP_ADD 4 OP_EQUALVERIFY OP_ADD 3 OP_EQUAL
Running: 5 5 OP_EQUALVERIFY
Stack: [ 1 2 3 1 ] — Does Not Exit
Script: 4 OP_EQUALVERIFY OP_ADD 3 OP_EQUAL
Running: 3 1 OP_ADD
Stack: [ 1 2 4 ]
Script: OP_EQUALVERIFY OP_ADD 3 OP_EQUAL
Stack: [ 1 2 4 4 ]
Script: OP_ADD 3 OP_EQUAL
Running: 4 4 OP_EQUALVERIFY
Stack: [ 1 2 ] — Does Not Exit
Script: 3 OP_EQUAL
Running: 1 2 OP_ADD
Stack: [ 3 ]
Script: OP_EQUAL
Stack: [ 3 3 ]
Script:
Running: 3 3 OP_EQUAL
Stack: [ True ]
See also the WebBTC Debug Execution of this script.
WARNING The WebBTC Debugger was used not just to offer another visualization of these scripts, but to also double-check the results. Sure enough, we got this one wrong the first time, testing the equations in the wrong order. That's how easy it is to make a financially fatal mistake in a Bitcoin Script, and that's why every script must be tested.
Though puzzle scripts are trivial, they can actually have real-world usefulness if you want to crowdsource a computation. You simply create a script that requires the answer to the computation and you send funds to the P2SH address as a reward. It'll stay there until someone comes up with the answer.
For example, Peter Todd offered rewards for solving equations that demonstrate collisions for standard cryptographic algorithms. Here was his script for confirming a SHA1 collision: OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_SHA1 OP_SWAP OP_SHA1 OP_EQUAL. It requires two inputs, which will be the two numbers that collide.
Here's how it runs with correct answers.
First, we fill in our stack:
Script: <numA> <numB> OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_SHA1 OP_SWAP OP_SHA1 OP_EQUAL
Stack: [ ]
Script: OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_SHA1 OP_SWAP OP_SHA1 OP_EQUAL
Stack: [ <numA> <numB> ]
Script: OP_EQUAL OP_NOT OP_VERIFY OP_SHA1 OP_SWAP OP_SHA1 OP_EQUAL
Running: <numA> <numB> OP_2DUP
Stack: [ <numA> <numB> <numA> <numB> ]
Then, we make sure the two numbers aren't equal, exiting if they are:
Script: OP_NOT OP_VERIFY OP_SHA1 OP_SWAP OP_SHA1 OP_EQUAL
Running: <numA> <numB> OP_EQUAL
Stack: [ <numA> <numB> False ]
Script: OP_VERIFY OP_SHA1 OP_SWAP OP_SHA1 OP_EQUAL
Running: False OP_NOT
Stack: [ <numA> <numB> True ]
Script: OP_SHA1 OP_SWAP OP_SHA1 OP_EQUAL
Running: True OP_VERIFY
Stack: [ <numA> <numB> ] — Does Not Exit
We now create two SHAs:
Script: OP_SWAP OP_SHA1 OP_EQUAL
Running: <numB> OP_SHA1
Stack: [ <numA> <hashB> ]
Script: OP_SHA1 OP_EQUAL
Running: <numA> <hashB> OP_SWAP
Stack: [ <hashB> <numA> ]
Script: OP_EQUAL
Running: <numA> OP_SHA1
Stack: [ <hashB> <hashA> ]
Script:
Running: <hashB> <hashA> OP_EQUAL
Stack: [ True ]
This is a nice script because it shows careful use of logic (with the OP_NOT and the OP_VERIFY) and good use of stack functions (with the OP_SWAP). It's all around a great example of a real-world function. And it is very real-world. When SHA-1 was broken, 2.48 BTC were quickly liberated from the address, with a total value of almost $3,000.
See also the WebBTC Debug Execution, with the correct answers.
Peter Todd's other bounties remain unclaimed at the time of this writing. They're all written in the same manner as the SHA-1 example above.
Puzzle scripts are great to further examine Bitcoin Scripting, but you'll only see them in real-world use if they're holding small amounts of funds or if they're intended for redemption by very skilled users. There's a reason for this: they aren't secure.
Here's where the security falls down:
First, anyone can redeem them without knowing much of a secret. They do have to have the redeemScript, which offers some protection, but once they do, that's probably the only secret that's necessary — unless your puzzle is really tough, such as a computational puzzle.
Second, the actual redemption isn't secure. Normally, a Bitcoin transction is protected by the signature. Because the signature covers the transaction, no one on the network can rewrite that transaction to instead send to their address without invalidating the signature (and thus the transaction). That isn't true with a transactions whose inputs are just numbers. Anyone could grab the transaction and rewrite it to allow them to steal the funds. If they can get their transaction into a block before yours, they win, and you don't get the puzzle money. There are solutions for this, but they involve mining the block yourself or having a trusted pool mine it, and neither of those options is rational for an average Bitcoin user.
Yet, Peter Todd's cryptographic bounties prove that puzzle scripts do have some real-world application.
Puzzles scripts are a great introduction to more realistic and complex Bitcoin Scripts. They demonstrate the power of the mathematical and stack functions in Bitcoin Script and how they can be carefully combined to create questions that require very specific answers. However, their real-world usage is also limited by the security issues inherent in non-signed Bitcoin transactions.
What is the power of puzzle script? Despite their limitations, puzzles scripts have been used in the real world as the prizes for computational bounties. Anyone who can figure out a complex puzzle, whose solution presumably has some real-world impact, can win the bounty. Whether they get to actually keep it is another question.
Continue "Designing Real Bitcoin Scripts" with §11.2: Writing Complex Multisig Scripts.