This semester, I've been taking a course on Bitcoin and Cryptocurrencies, offered by Princeton's Center for Information Technology Policy, and co-taught by Arvind Narayanan and Joseph Bonneau (with help from Ed Felten and Andrew Miller).
Inspired by the course, I spent some time this semester on a Bitcoin Script-to-JavaScript compiler and a real-time playground for the browser: the Script Playground. It's a great way to familiarize yourself with the semantics of and philosophies behind Bitcoin Script.
The ES6 source is available on GitHub; you can also download the interpreter as the bitcoin-script package on npm.
In this post, I'll explain some of the core principles and functionality behind Script before introducing the Script Playground and a few examples.
(If you have a good handle on Script, feel free to skip ahead.)
Script is a simple stack-based programming language used by Bitcoin to validate transactions.
Script programs are processed left-to-right, with each operation modifying a global stack. On termination, the script is either considered valid (indicated by the presence of a 1 on top of the stack) or invalid (anything else).
As an example, this script pushes a 0 onto the stack, increments it, and terminates. As 0 + 1 = 1 is on top of the stack, this script will run successfully:
OP_0 OP_1ADDPretty simple.
Script is used to verify that the spender of some Bitcoins actually owns them. In other words, scripts validate transactions.
Each Bitcoin transaction requires two scripts: ScriptPubKey and ScriptSig. The former is included as part of the transaction when it is broadcast to the network and typically encodes the destination address D of the Bitcoins involved. The latter is provided when those Bitcoins are spent in the future by the owner of address D and typically provides some evidence that the owner actually owns that address (i.e., by signing a message with its private key).
To validate the spending of Bitcoins, miners concatenate the ScriptSig and ScriptPubKey. If the concatenated program is valid, the transaction is valid, and vice-versa. For this reason, these scripts are sometimes referred to as the "unlocking" and "locking" scripts, respectively, as the ScriptPubKey is provided to lock some Bitcoins to an address, and the ScriptSig, to unlock them in the future.
Script is purposefully not Turing-complete. It contains no loops (it's only form of control flow is through if-else statements) and the instruction set is limited to the bare necessities: stack manipulation, arithmetic, cryptography, and little else.
This simplicity is a feature, not a flaw.
As scripts are used to validate transactions, miners across the network have to execute them in bulk to compose and validate blocks. If the Script language allowed for intense computation, miners would be disincentivized from validating transactions because of the costs of computing.
At the very least, these miners would be incurring an unnecessary cost, as Script's simplicity is sufficient for covering most of what we want to do in transaction validation. This cost would make mining less attractive, and as the attractivity of mining is crucial to maintaining a high hash rate across the network (and thus securing the network), this simplicity is a good thing.
In practice, Bitcoin scripts typically take one of a handful of forms, e.g.:
In fact, miners will reject transactions that veer from the list of standard Script formats. In Bitcoin jargon, these are referred to as "non-standard transactions".
Script is an interesting facet of Bitcoin.
First, the language is intentionally simple, which makes you wonder just how far you can push it.
Second, Script is a good mechanism for reinforcing the principles behind Bitcoin. For example, Script's limited instruction set reinforces an understanding of miner incentives, while its multi-signature support demonstrates interesting use-cases for Bitcoin.
For these reasons, I wanted to make it possible to play with Script in the most accessible of settings: the browser. The finished product is available here, with the source free to view on GitHub. You can also download it as the bitcoin-script package from npm.
My implementation of Script covers all of the enabled opcodes listed on the Bitcoin Wiki, apart from the reserved words, altstack commands, pseudo-words, and OP_CODESEPARATOR. In particular, it's worth noting that my implementation allows for the use of disabled commands, like OP_MUL, by passing in true as the second argument to any of the exported functions. (The Script Playground has this behavior enabled by default.)
However, it differs from Bitcoin's implementation in a few ways:
OP_PUSHDATA commands and instead pushes any hex-formatted data to the stack (e.g., 0x05 or fde5a). Further, this hex data can be of arbitrary length.OP_CHECKMULTISIG does not pop an extra, arbitrary value off the stack (as this is considered a bug and would only serve to confuse new users).Each of these changes was made so as to make this implementation easier to use and understand.
In addition to the Script implementation itself, the Playground also includes:
The Script playground compiles Script programs down to JavaScript using Jison, a JavaScript parser generator, with the grammar defined here. The implementation is built to run in Node, and is transpiled for use in the browser with Browserify.
The live editor itself is based on my friend Joel Burget's react-live-editor, which is in-turn based on CodeMirror for real-time updates and editing.
Because my implementation is built for Node, it's really easy to play around with Script using all the expressive power of JavaScript.
As an example, consider a ScriptPubKey that is only unlocked if the redeemer provides a three-digit prime number. We can programmatically generate the ScriptPubKey in JavaScript and then evaluate some ScriptSig candidates, all within the same module.
As Script's division and remainder operators are disabled in Bitcoin, the best we can do (whilst remaining in the realm of enabled operators) is generate all the set of prime numbers in [100, 999] and evaluate whether the ScriptSig is in that set. Since the ScriptPubKey is public, we won't want to include the actual primes; instead, we'll include the hash of each prime and evaluate the hash of the ScriptSig for equality.
The final evaluation function looks like this:
var unlock = require("./index.tsx").unlock;
var sha256 = require("../crypto.js").sha256;
function isPrime(scriptSig) {
// Find primes in [100, 999]
var minValue = 100;
var maxValue = 999;
var primes = getPrimes(maxValue);
// Check for equality of hashes
var scriptPubKey = "";
for (var i = 0; i < primes.length; i++) {
var commands = ["OP_DUP", "OP_SHA256", sha256(primes[i]), "OP_EQUAL"];
// Keep a running OR tally of whether we've hit a match
if (scriptPubKey) {
commands.push("OP_ROT");
commands.push("OP_BOOLOR");
}
commands.push("OP_SWAP");
scriptPubKey += commands.join(" ") + " ";
}
// Verify that the value is in [100, 999]
var hexBase = 16;
var conclusion = [
"0x" + minValue.toString(hexBase),
"0x" + maxValue.toString(hexBase),
"OP_WITHIN",
"OP_BOOLAND",
"OP_VERIFY",
];
scriptPubKey += conclusion.join(" ");
// Concatenate and run (scriptSig, scriptPubKey)
return unlock(scriptSig, scriptPubKey);
}
It's fun to test the limits of Script's expressiveness.
Unfortunately, this example isn't very useful. In the real world, the goal of such a script would be to incentivize individuals to find large primes: in return for their effort, they could unlock the script and claim some Bitcoin (this is in the realm of a useful proof-of-work system).
But by computing all the primes in advance, we defeat the purpose, as all the work is being done twice: once by the individual that issues the challenge, and once by the individual that solves it.
What commands would it take, then, to write a ScriptPubKey that doesn't need to precompute primes?
A test for divisability would be sufficient and, indeed, this is possible with the OP_MOD command. OP_MOD is disabled in the Bitcoin Script spec, but can be enabled in my implementation by switching a flag.
Here's the revised code which is much more useful, as the burden of producing a prime number is placed on the unlocker:
var { sha256 } = require("../src/crypto.js");
var { unlock } = require("../src/index.js");
/*
* This function only unlocks if the user supplies a three-digit prime number.
*/
function isPrime(scriptSig) {
var minValue = 100;
var maxValue = 999;
var scriptPubKey = "";
for (var i = 2; i < Math.sqrt(maxValue); i++) {
var commands = [
"OP_DUP",
i,
"OP_MOD",
"OP_0",
"OP_EQUAL",
"OP_IF",
"OP_RETURN",
"OP_ENDIF",
];
scriptPubKey += commands.join(" ") + " ";
}
// Verify that the value is in [100, 999]
var hexBase = 16;
var conclusion = [
"0x" + minValue.toString(base),
"0x" + maxValue.toString(base),
"OP_WITHIN",
"OP_VERIFY",
];
scriptPubKey += conclusion.join(" ");
return unlock(scriptSig, scriptPubKey, /* enableDisabled */ true);
}
I'd encourage you to play around with your own scripts in the playground and see what you can come up with. Alternatively, you can download the bitcoin-script package from npm.
Thanks to Shubhro Saha for his feedback on a draft of this post.
2014-12-16