Low-level Bitcoin

comment

Exploring Bitcoin can yield interesting surprises. The block chain already contains various gems hidden inside transactions — tributes, illegal data, even pictures and a patch fixing bug in a Bitcoin client.

This article shows how to implement a simple parser for blocks and transactions in JavaScript, how to execute scripts embedded in transactions and how the signatures are created and validated. These tools are used to visualize Bitcoin contracts.

The implementation uses several ES6 features not yet enabled by default in Chrome (version 36). It is necessary to enable Experimental JavaScript at chrome://flags/#enable-javascript-harmony.

Firefox (version 31) supports generators as well as Promises.

Encoders

Simple utility methods to convert bytes into the hex-encoded strings or to and from little-endian numbers.

var hex = {
    decode: function(text) {
        return text.match(/.{2}/g).map(function(byte) {
            return parseInt(byte, 16);
        });
    },
    encode: function(bytes) {
        var result = [];
        for (var i = 0, hex; i < bytes.length; i++) {
            hex = bytes[i].toString(16);
            if (hex.length < 2) {
                hex = '0' + hex;
            }
            result.push(hex);
        }
        return result.join('');
    }
};

var littleEndian = {
    decode: function(bytes) {
        return bytes.reduce(function(previous, current, index) {
            return previous + current * Math.pow(256, index);
        }, 0);
    },
    encode: function(number, count) {
        var rawBytes = [];
        for (var i = 0; i < count; i++) {
            rawBytes[i] = number & 0xff;
            number = Math.floor(number / 256);
        }
        return rawBytes;
    }
};

Bitcoin addresses are encoded using the base-58 encoding as it offers human-friendly output. The implementation below uses a big integer library.

var base58 = {
    _codes: '123456789ABCDEFGHJKLMNPQRSTUVWXYZ' +
        'abcdefghijkmnopqrstuvwxyz',
    _58: new BigInteger('58'),
    encode: function(bytes) {
        var number = new BigInteger(bytes);

        var output = [];

        while (number.compareTo(BigInteger.ZERO) > 0) {
            var result = number.divideAndRemainder(this._58);
            number = result[0];
            var remainder = result[1];
            output.push(this._codes.charAt(remainder));
        }

        // preserve leading zeros
        for (var i = 0; i < bytes.length; i++) {
            if (bytes[i] !== 0) {
                break;
            }
            output.push(this._codes[0]);
        }
        return output.reverse().join('');
    },
    decode: function(string) {
        var result = BigInteger.ZERO;
        var output = [], code, power;
        for (var i = 0; i < string.length; i++) {
            code = this._codes.indexOf(string.charAt(i));

            // preserve leading zeros
            if (result.equals(BigInteger.ZERO) && code === 0) {
                output.push(0);
            }
            power = this._58.pow(string.length - i - 1);
            code = new BigInteger('' + code);
            result = result.add(code.multiply(power));
        }
        output.push.apply(output, result.toByteArrayUnsigned());
        return output;
    }
};

Reading primitives

Low-level Bitcoin structures are parsed from the byte arrays using ArraySource wrapper. This adapter wraps the byte array exposing the readByte method that returns the next byte each time it is invoked.

function ArraySource(rawBytes, index) {
    this.rawBytes = rawBytes;
    this.index = index || 0;
}

ArraySource.prototype = {
    readByte: function() {
        if (!this.hasMoreBytes()) {
            throw new Error('Cannot read past the end of the array.');
        }
        return this.rawBytes[this.index++];
    },
    hasMoreBytes: function() {
        return this.index < this.rawBytes.length;
    },
    getPosition: function() {
        return this.index;
    }
};

The source object is passed to the Stream that returns a higher-level abstraction based on the readByte. For example reading variable length integers can consume 1, 3, 5 or 9 bytes depending on the value of the first byte. Strings (for example scripts) are encoded as a variable length integer (the array length) followed by the byte array itself.

The readByte method delegates to the readByte method of the source. All the others use generators.

function Stream(source) {
    this.source = source;
}

Stream.prototype = {
    readByte: function() {
        return this.source.readByte();
    },
    readBytes: function*(num) {
        var bytes = [];
        for (var i = 0; i < num; i++) {
            bytes.push(yield this.readByte());
        }
        return bytes;
    },
    readInt: function*(num) {
        var bytes = yield this.readBytes(num);
        return littleEndian.decode(bytes);
    },
    readVarInt: function*() {
        var num = yield this.readByte();
        if (num < 0xfd) {
            return num;
        } else if (num === 0xfd) {
            return this.readInt(2);
        } else if (num === 0xfe) {
            return this.readInt(4);
        } else {
            return this.readInt(8);
        }
    },
    readString: function*() {
        var length = yield this.readVarInt();
        return this.readBytes(length);
    },
    readHexBytes: function*(num) {
        var bytes = yield this.readBytes(num);
        return hex.encode(bytes.reverse());
    },
    hasMoreBytes: function() {
        return this.source.hasMoreBytes();
    },
    getPosition: function() {
        return this.source.getPosition();
    }
};

Parsing transactions and blocks

Reading transactions algorithm uses a Stream object to create the Transaction object from simple primitives.

function Transaction(version, inputs, outputs, lockTime) {
    this.version = version || 1;
    this.inputs = inputs || [];
    this.outputs = outputs || [];
    this.lockTime = lockTime || 0;
}

Transaction.parse = function*(stream) {
    var transaction = new Transaction();
    transaction.version = yield stream.readInt(4);

    var txInNum = yield stream.readVarInt();
    for (var i = 0; i < txInNum; i++) {
        transaction.inputs.push({
            previousTxHash: yield stream.readHexBytes(32),
            previousTxOutIndex: yield stream.readInt(4),
            script: Script.readScript(yield stream.readString()),
            sequenceNo: yield stream.readHexBytes(4)
        });
    }

    var txOutNum = yield stream.readVarInt();
    for (var i = 0; i < txOutNum; i++) {
        transaction.outputs.push({
            value: yield stream.readInt(8),
            script: Script.readScript(yield stream.readString())
        });
    }

    transaction.lockTime = yield stream.readInt(4);

    return transaction;
};

Parsing blocks is similar to parsing transactions. Before a block is read though the Block.parse method looks for the block magic number. It is important to look for the magic number first as blocks can be separated by a region of zero bytes of unknown size.

function Block() {
}

Block.parse = function*(stream) {

    var findMagicNumber = function*(stream, octet) {
        while (octet !== 0xf9) {
            octet = yield stream.readByte();
        }
        octet = yield stream.readByte();
        if (octet !== 0xbe) {
            return findMagicNumber(stream, octet);
        }
        octet = yield stream.readByte();
        if (octet !== 0xb4) {
            return findMagicNumber(stream, octet);
        }
        octet = yield stream.readByte();
        if (octet !== 0xd9) {
            return findMagicNumber(stream, octet);
        }
    };

    yield findMagicNumber(stream);

    var block = new Block();

    block.length = yield stream.readInt(4);
    block.version = yield stream.readInt(4);
    block.previousBlockHash = hex.encode(yield stream.readBytes(32));
    block.merkleRoot = hex.encode(yield stream.readBytes(32));
    block.timeStamp = new Date((yield stream.readInt(4)) * 1000);
    block.target = yield stream.readInt(4);
    block.nonce = yield stream.readInt(4);
    block.transactions = [];

    var transactionCount = yield stream.readVarInt();
    for (var i = 0; i < transactionCount; i++) {
        block.transactions.push(yield Transaction.parse(stream));
    }

    return block;
};

Reading data from files

The FileSource implements the same interface as the ArraySource but instead of returning a byte directly in readByte method it returns a Promise object that will resolve to the byte being read. Instead of reading bytes from an array it uses the FileReader API to read bytes from the disk. One ArraySource object is used internally as a buffer for efficiency.

function FileSource(file, index, chunkSize) {
    if (!file) {
        throw new Error('Argument file not defined.');
    }
    this.file = file;
    this.index = index || 0;
    this.chunkSize = chunkSize || (1024 * 1024);
    this.buffer = new ArraySource([]);
    this.reader = new FileReader();
}

FileSource.prototype = {
    readByte: function() {
        if (this.buffer.hasMoreBytes()) {
            return Promise.resolve(this.buffer.readByte());
        }
        if (!this.hasMoreBytes()) {
            var err = Error('Cannot read past the end of file.');
            return Promise.reject(err);
        }
        var _this = this;
        return this._readBytes().then(function(rawBytes) {
            _this.buffer = new ArraySource(rawBytes);
            return _this.readByte();
        });
    },
    hasMoreBytes: function() {
        return this.index < this.file.size;
    },
    getPosition: function() {
        return this.index - this.chunkSize + this.buffer.getPosition();
    },
    _readBytes: function() {
        return new Promise(function(resolve, reject) {
            this.reader.onload = function(e) {
                var bytes = new Uint8Array(e.target.result);
                resolve(bytes);
            };
            this.reader.onerror = reject;
            var index = this.index;
            var blob = this.file.slice(index, index + this.chunkSize);
            this.reader.readAsArrayBuffer(blob);
            this.index += this.chunkSize;
        }.bind(this));
    }
};

Strange transactions

This code categorizes transactions according to the script type in outputs and prints any strange scripts that are found in the block chain. The vast majority of output scripts are standard pay-to-pubkey-hash scripts.

function getOutputScriptType(script) {
    if (script.length === 2 && script[1] === 'OP_CHECKSIG') {
        return 'pubkey';
    } else if (script.length === 5 &&
            script[0] === 'OP_DUP' &&
            script[1] === 'OP_HASH160' &&
            script[3] === 'OP_EQUALVERIFY' &&
            script[4] === 'OP_CHECKSIG') {
        return 'pubkeyhash';
    } else if (script[0] === 'OP_1' &&
            script[script.length - 1] === 'OP_CHECKMULTISIG') {
        return 'onemultisig';
    } else if (script[0] === 'OP_2' &&
            script[3] == 'OP_2' &&
            script[script.length - 1] === 'OP_CHECKMULTISIG') {
        return 'twomultisig';
    } else if (script.length === 3 &&
            script[0] === 'OP_HASH160' &&
            script[2] === 'OP_EQUAL') {
        return 'hash';
    } else if (script[0] === 'OP_RETURN') {
        return 'destroy';
    } else {
        return 'unknown';
    }
}

var findStrangeTransactions = function*(stream) {
    var block = yield Block.parse(stream);
    var strange = block.transactions.filter(function(transaction) {
        return transaction.outputs.some(function(output) {
            return getOutputScriptType(output.script) === 'unknown';
        });
    });
    var stats = block.transactions.reduce(function(stats, tx) {
        tx.outputs.forEach(function(output) {
            var type = getOutputScriptType(output.script);
            if (type in stats) {
                stats[type]++;
            } else {
                stats[type] = 1;
            }
        });
        return stats;
    }, {});
    var generation = block.transactions[0];
    // decode messages in input scripts
    var decoded = [];
    generation.inputs[0].script.forEach(function(instr) {
        if (instr.length > 20) {
            decoded.push(hex.decode(instr).map(function(char) {
                return String.fromCharCode(char);
            }).join(''));
        }
    });
    generation.inputs[0].decodedScript = decoded;
    return {
        block: block,
        generation: block.transactions[0],
        outputStatistics: stats,
        strangeTransactions: strange
    };
};

Block files are named blk*.dat and are located in:

  • C:\Users\YourUserName\Appdata\Roaming\Bitcoin\blocks — Windows Vista and 7,
  • ~/.bitcoin/blocks — Linux,
  • ~/Library/Application Support/Bitcoin/blocks — Mac.
var input = document.createElement('input');
input.type = 'file';
input.onchange = function() {
    window.stream = new Stream(new FileSource(input.files[0]));
};
input.click();

This method parses a block in the loaded stream and reports simple statistics.

Parse the first block from file blk00000.dat to read the message embedded in input script by Satoshi Nakamoto.

Try parsing 10 blocks from the file blk00092.dat to find transactions with strange outputs.

async(findStrangeTransactions(window.stream)).then(function(obj) {
    delete obj.block.transactions;
    if (obj.generation.inputs[0].script.length > 10) {
        obj.generation.inputs[0].script = '[truncated]';
    }
    output.textContent = JSON.stringify(obj, null, 2);
}, console.error.bind(console));
// Load block and parse it

Script

Bitcoin Script is a simple stack-based programming language used in transaction inputs and outputs to move funds.

Script is a pure (side-effect free) function so that each evaluation yields the same result. There are branching instructions (OP_IF, OP_ELSE) but no loops. Script contains special cryptography functions and operators for pushing constant byte vectors (e.g. signatures and public keys) onto the stack.

Parsing script

The readScript method takes an array of bytes and returns an array of symbolic opcodes (e.g. OP_EQUALVERIFY). The writeScript does the reverse — takes an array of symbolic names and returns an array of bytes.

Not all opcodes are parsed by this code. Only a limited subset used in Bitcoin contracts article is supported.

var Script = (function() {
    var opcodes = {
        0x00: 'FALSE',

        // Operators 0x00-0x4b push next _opcode_ bytes on the stack
        // e.g. 0x02 pushes next 2 bytes as a one two byte vector item

        // Operators 0x51-0x60 push number (opcode — 0x50) on the stack
        // e.g. 0x52 pushes number 2 as a byte vector

        // Flow control
        0x63: 'IF',
        0x67: 'ELSE',
        0x68: 'ENDIF',
        0x69: 'VERIFY',

        // Stack
        0x76: 'DUP',
        0x77: 'NIP',
        0x7a: 'ROLL',
        0x7b: 'ROT',
        0x7c: 'SWAP',
        0x7d: 'TUCK',

        // Splice
        0x82: 'SIZE',

        // Bitwise logic
        0x87: 'EQUAL',
        0x88: 'EQUALVERIFY',

        // Arithmetic
        0x93: 'ADD',
        0x94: 'SUB',
        0x9a: 'BOOLAND',
        0x9b: 'BOOLOR',
        0xa0: 'GREATERTHAN',
        0xa5: 'WITHIN',

        // Crypto
        0xa8: 'SHA256',
        0xa9: 'HASH160',
        0xac: 'CHECKSIG',
        0xad: 'CHECKSIGVERIFY',
        0xae: 'CHECKMULTISIG'
    };

    var readScript = function*(stream) {
        var instructions = [];
        while (stream.hasMoreBytes()) {
            var opcode = yield stream.readByte();
            if (opcode === 0x00) {
                instructions.push('OP_FALSE');
            } else if (opcode <= 0x4b) {
                var bytes = yield stream.readBytes(opcode);
                instructions.push(hex.encode(bytes));
            } else if (opcode >= 0x51 && opcode <= 0x60) {
                var num = opcode - 0x50;
                instructions.push('OP_' + num);
            } else if (opcode in opcodes) {
                instructions.push('OP_' + opcodes[opcode]);
            } else {
                throw new Error('Unknown opcode: ' + opcode);
            }
        }
        return instructions;
    };

    function writeScript(instructions) {
        var bytes = [];
        instructions.forEach(function(opcode) {
            var num = opcode.match(/^OP_([1-9]|1[0-6])$/);
            if (num) {
                bytes.push(parseInt(num[1], 10) + 0x50);
                return;
            } else if (opcode.match(/^([a-f0-9][a-f0-9])+$/g)) {
                bytes.push(opcode.length / 2);
                bytes.push.apply(bytes, hex.decode(opcode));
                return;
            } else {
                for (var code in opcodes) {
                    if (opcode === ('OP_' + opcodes[code])) {
                        bytes.push(parseInt(code, 10));
                        return;
                    }
                }
            }
            throw new Error('Unknown opcode: ' + opcode);
        });
        return bytes;
    }

    return {
        readScript: function(script) {
            try {
                var stream = new Stream(new ArraySource(script));
                return sync(readScript(stream));
            } catch (e) {
                console.warn('Cannot parse script: ' + e, script);
                return script;
            }
        },
        writeScript: writeScript
    };

}());

Operators

The execution of operators relies on the stack structure passed as a first parameter. Several more sophisticated functions like OP_CHECKSIG and OP_IF use the context object (second parameter) to check signatures embedded in scripts or control the script execution.

var operators = {
    OP_DUP: function(stack) {
        var value = stack.pop();
        stack.push(value);
        stack.push(value);
    },
    OP_SHA256: function(stack) {
        var value = stack.pop();
        stack.push(digest.sha256(value));
    },
    OP_HASH160: function(stack) {
        var value = stack.pop();
        stack.push(digest.ripemd160(digest.sha256(value)));
    },
    OP_EQUAL: function(stack) {
        var value1 = stack.pop();
        var value2 = stack.pop();
        if (value1.length !== value2.length) {
            stack.pushBoolean(false);
            return;
        }
        for (var i = 0; i < value1.length; i++) {
            if (value1[i] !== value2[i]) {
                stack.pushBoolean(false);
                return;
            }
        }
        stack.pushBoolean(true);
    },
    OP_VERIFY: function(stack) {
        var value = stack.popBoolean();
        if (!value) {
            stack.pushBoolean(value);
            throw new Error('Verify error.');
        }
    },
    OP_EQUALVERIFY: function(stack) {
        this.OP_EQUAL(stack);
        this.OP_VERIFY(stack);
    },
    OP_CHECKSIG: function(stack, context) {
        var pubKey = stack.pop();
        var signature = stack.pop();
        var valid = context.checkSignature(signature, pubKey);
        stack.pushBoolean(valid);
    },
    OP_CHECKSIGVERIFY: function(stack, context) {
        this.OP_CHECKSIG(stack, context);
        this.OP_VERIFY(stack);
    },
    OP_CHECKMULTISIG: function(stack, context) {
        var pubKeysCount = stack.popNumber();
        var pubKeys = [];
        for (var i = 0; i < pubKeysCount; i++) {
            pubKeys.push(stack.pop());
        }
        var sigsCount = stack.popNumber();
        var signatures = [];
        for (var i = 0; i < sigsCount; i++) {
            signatures.push(stack.pop());
        }
        stack.pop(); // dummy value
        var valid = signatures.every(function(signature) {
            return pubKeys.some(function(pubKey) {
                return context.checkSignature(signature, pubKey);
            });
        });
        stack.pushBoolean(valid);
    },
    OP_FALSE: function(stack) {
        stack.pushBoolean(false);
    },
    OP_SIZE: function(stack) {
        var element = stack.pop();
        stack.push(element);
        stack.push([element.length]);
    },
    OP_WITHIN: function(stack) {
        var max = stack.popNumber();
        var min = stack.popNumber();
        var element = stack.popNumber();
        stack.pushBoolean(min <= element && element < max);
    },
    OP_GREATERTHAN: function(stack) {
        var first = stack.popNumber();
        var second = stack.popNumber();
        stack.pushBoolean(second > first);
    },
    OP_ADD: function(stack) {
        var first = stack.popNumber();
        var second = stack.popNumber();
        stack.pushNumber(first + second);
    },
    OP_SUB: function(stack) {
        var first = stack.popNumber();
        var second = stack.popNumber();
        stack.pushNumber(second - first);
    },
    OP_SWAP: function(stack) {
        var value1 = stack.pop();
        var value2 = stack.pop();
        stack.push(value1);
        stack.push(value2);
    },
    OP_TUCK: function(stack) {
        var value1 = stack.pop();
        var value2 = stack.pop();
        stack.push(value1);
        stack.push(value2);
        stack.push(value1);
    },
    OP_ROT: function(stack) {
        var value1 = stack.pop();
        var value2 = stack.pop();
        var value3 = stack.pop();
        stack.push(value2);
        stack.push(value1);
        stack.push(value3);
    },
    OP_ROLL: function(stack) {
        var n = stack.popNumber();
        var value = stack.splice(stack.length - n - 1, 1);
        // splice returns an array with one element
        stack.push(value[0]);
    },
    OP_BOOLAND: function(stack) {
        var value1 = stack.popBoolean();
        var value2 = stack.popBoolean();
        stack.pushBoolean(value1 && value2);
    },
    OP_BOOLOR: function(stack) {
        var value1 = stack.popBoolean();
        var value2 = stack.popBoolean();
        stack.pushBoolean(value1 || value2);
    },
    OP_NIP: function(stack) {
        var value1 = stack.pop();
        var value2 = stack.pop();
        stack.push(value1);
    },
    OP_IF: function(stack, context) {
        var execute = context.canExecute() && stack.popBoolean();
        context.pushExecute(execute);
    },
    OP_ELSE: function(stack, context) {
        context.flipExecute();
    },
    OP_ENDIF: function(stack, context) {
        context.popExecute();
    }
};

Interpreter

All stack items are byte arrays. Arithmetic operators treat them as little-endian encoded numbers. Boolean operators treat all representations of zero as false (e.g. empty array) and everything else as true. The StackWrapper provides convenience methods to push or pop stack items as numbers or booleans.

A script is considered valid if its execution leaves a truthy item at the top of the stack and nothing triggers a failure (e.g. OP_VERIFY).

var StackWrapper = (function() {

    function StackWrapper(stack) {
        this.stack = stack;
    }

    StackWrapper.prototype = {
        push: function(value) {
            this.stack.push(value);
            this.length = this.stack.length;
        },
        pop: function() {
            this.length = this.stack.length - 1;
            return this.stack.pop();
        },
        splice: function(index, count) {
            this.length = this.stack.length - count;
            return this.stack.splice(index, count);
        },
        pushNumber: function(number) {
            this.push(littleEndian.encode(number, 1));
        },
        pushBoolean: function(boolean) {
            this.push(booleanToNumber(boolean));
        },
        popNumber: function() {
            return littleEndian.decode(this.pop());
        },
        popBoolean: function() {
            return numberToBoolean(this.pop());
        }
    };

    var FALSE = [], TRUE = [1];

    function numberToBoolean(value) {
        if (value.length === 0) {
            return false;
        } else {
            for (var i = 0; i < value.length; i++) {
                if (value[i] !== 0) {
                    if (i === value.length - 1 && value[i] === 0x80) {
                        return false;
                    }
                    return true;
                }
            }
            return false;
        }
    }

    function booleanToNumber(value) {
        return value ? TRUE : FALSE;
    }

    return StackWrapper;

}());

function createInterpreter(stack, checkSignature) {
    var executes = [];

    var context = {
        pushExecute: function(execute) {
            executes.push(execute);
        },
        flipExecute: function(execute) {
            executes.push(!executes.pop());
        },
        popExecute: function() {
            executes.pop();
        },
        canExecute: function() {
            return executes.every(function(execute) {
                return !!execute;
            });
        },
        checkSignature: checkSignature
    };

    stack = new StackWrapper(stack);

    function isConditional(instruction) {
        return instruction === 'OP_IF' || instruction === 'OP_ELSE' ||
            instruction === 'OP_ENDIF';
    }

    return function(instruction) {
        if (isConditional(instruction) || context.canExecute()) {
            var num = instruction.match(/^OP_([1-9]|1[0-6])$/);
            if (num) {
                stack.pushNumber(parseInt(num[1], 10));
            } else if (instruction.match(/^([a-f0-9][a-f0-9])+$/)) {
                stack.push(hex.decode(instruction));
            } else if (instruction in operators) {
                operators[instruction](stack, context);
            } else {
                throw new Error('Not implemented: ' + instruction);
            }
            return true;
        }
        return false;
    };
}

Signatures

There is one special category of operators — sigops — operators that check signatures. They are expensive and there is a limit of sigops that each block can contain (currently 20 000) to prevent Denial of Service attacks. OP_CHECKSIG or OP_CHECKSIGVERIFY instructions count as 1 and each OP_CHECKMULTISIG or OP_CHECKMULTISIGVERIFY instruction counts as number of public keys to verify (if operator before the sigop is from range OP_1 to OP_16) or 20 otherwise.

OP_CHECKSIG checks if a signature for a given transaction input is valid. It takes two arguments from the stack — a public key and a signature. This operator also relies on the current transaction state, input that contains the signature and the referenced output’s script (called subscript).

Signature hash type

The signature hash flags indicate which parts of the transaction are signed. The last byte of the signature indicates which hash type was used to construct the signature.

There are three procedures of calculating transaction’s hash:

  1. ALL — the default, indicates that everything in the transaction is signed (except for the input scripts),
  2. NONE — nothing in the transaction is signed (transaction can be modified without breaking the signature),
  3. SINGLE — only the output with the same index as the current input is signed.

Each of these can also be combined with the ANYONECANPAY flag that enables merging transaction inputs.

Only the default procedure is implemented below with the ANYONECANPAY extension.

function SigHashType(value, procedure) {
    this.value = value;
    this.procedure = procedure;
}

SigHashType.prototype.apply = function(tx, inputIndex, subscript) {
    var transaction = tx.clone();
    transaction.inputs.forEach(function(input) {
        input.script = [];
    });
    transaction.inputs[inputIndex].script = subscript;
    this.procedure(transaction, inputIndex, subscript);
    return transaction;
};

SigHashType.prototype.withAnyoneCanPay = function() {
    return new SigHash(this.value | SigHash.ANYONECANPAY);
};

SigHashType.ALL = new SigHashType(1, function() {
    // default procedure
});

SigHashType.NONE = new SigHashType(2, function() {
    throw new Error('Not implemented.');
});

SigHashType.SINGLE = new SigHashType(3, function() {
    throw new Error('Not implemented.');
});

function SigHash(value) {
    var type = (value & ~SigHash.ANYONECANPAY);
    for (var item in SigHashType) {
        if (SigHashType[item].value === type) {
            this.type = SigHashType[item];
            break;
        }
    }
    this.isAnyoneCanPay = !!(value & SigHash.ANYONECANPAY);
    this.value = value;
}

SigHash.ANYONECANPAY = 0x80;

SigHash.prototype.apply = function(tx, inputIndex, subscript) {
    var transaction = this.type.apply(tx, inputIndex, subscript);
    if (this.isAnyoneCanPay) {
        // leave only one input — the spending one
        transaction.inputs = [transaction.inputs[inputIndex]];
    }
    return transaction;
};

Serializing transactions

The ArraySink provides a simple interface that writes Bitcoin primitives into an array of bytes.

function ArraySink(rawBytes) {
    this.rawBytes = rawBytes;
}

ArraySink.prototype = {
    writeByte: function(byte) {
        this.rawBytes.push(byte);
    },
    writeBytes: function(bytes) {
        Array.prototype.push.apply(this.rawBytes, bytes);
    },
    writeInt: function(number, count) {
        this.writeBytes(littleEndian.encode(number, count));
    },
    writeVarInt: function(num) {
        if (num < 0xfd) {
            this.writeByte(num);
        } else if (num <= 0xffff) {
            this.writeByte(0xfd);
            this.writeBytes(littleEndian.encode(num, 2));
        } else {
            throw new Error('Not implemented.');
        }
    },
    writeString: function(bytes) {
        this.writeVarInt(bytes.length);
        this.writeBytes(bytes);
    },
    writeHexBytes: function(text) {
        this.writeBytes(hex.decode(text).reverse())
    }
};

ArraySink object is passed to the serialization method. After the serializeInto call the array passed to ArraySink will be filled with bytes representing the current transaction.

Transaction.prototype.serializeInto = function(stream) {
    stream.writeInt(this.version, 4);

    stream.writeVarInt(this.inputs.length);
    for (var i = 0, input; input = this.inputs[i]; i++) {
        stream.writeHexBytes(input.previousTxHash);
        stream.writeInt(input.previousTxOutIndex, 4);
        stream.writeString(Script.writeScript(input.script));
        stream.writeHexBytes(input.sequenceNo);
    }

    stream.writeVarInt(this.outputs.length);
    for (var i = 0, output; output = this.outputs[i]; i++) {
        stream.writeInt(output.value, 8);
        stream.writeString(Script.writeScript(output.script));
    }

    stream.writeInt(this.lockTime, 4);
};

Transaction.prototype.clone = function() {
    var copy = JSON.parse(JSON.stringify(this));
    return new Transaction(copy.version, copy.inputs, copy.outputs, copy.lockTime);
};

The serialized form of the transaction is used to calculate the transaction hash for signing or checking signatures.

Checking signatures algorithm first calculates the transaction hash using the signature hash type and then verifies the given signature with a provided public key.

Signature verification and hash signing is implemented using the ecdsa library.

function hashTransaction(tx, spendingInputIndex, subscript, sigHash) {

    // transform transaction according to SIGHASH procedure
    var transaction = sigHash.apply(tx, spendingInputIndex, subscript);

    // serialize transaction
    var bytes = [], sink = new ArraySink(bytes);
    transaction.serializeInto(sink);

    // append sighash value
    sink.writeInt(sigHash.value, 4);

    return digest.sha256(digest.sha256(bytes));
}

function checkSignature(previousTx, newTx, inputIndex,
        signature, pubKey) {

    var spendingInput = newTx.inputs[inputIndex];
    var output = previousTx.outputs[spendingInput.previousTxOutIndex];
    var subscript = output.script;

    // last byte of signature is hash type
    var hashType = new SigHash(signature[signature.length - 1]);

    var hash = hashTransaction(newTx, inputIndex, subscript, hashType);

    try {
        return ecdsa.verify(hash, signature, pubKey);
    } catch (e) {
        console.warn('Signature verification failed', e);
        return false;
    }
}

A similar algorithm is used when signing a transaction but instead of verifying an existing signature a private key is used to sign the transaction’s hash.

function signTransaction(previousTx, newTx, inputIndex, sigHash,
        privateKey) {

    var spendingInput = newTx.inputs[inputIndex];
    var output = previousTx.outputs[spendingInput.previousTxOutIndex];
    var subscript = output.script;

    var hash = hashTransaction(newTx, inputIndex, subscript, sigHash);

    return ecdsa.sign(hash, privateKey).concat(sigHash.value);
}

Creating new transaction

The private key is an array of 32 random bytes. The public key is created by multiplying private key by the elliptic curve parameter.

This example signs one of the pledges in a Kickstarter campaign.

var privateKey = new Uint8Array(32);

window.crypto.getRandomValues(privateKey);

log('Private key', hex.encode(privateKey));

var publicKey = ecdsa.getPublicKey(privateKey);

log('Public key', hex.encode(publicKey));

var bytes = hex.decode('01000000011f5e7131923054920104e5080983572c6e29366d0c7f95548398e7a1c80dfa23500000006b4830450221009ce31d9d621c4ef2a753cb238d8bbb4b02edaf17cea98d95945011b84448bd39022010c699f51a8d1399748ce57b3db3ccd7a076872fd564492df96b1c7ff5ad57e5012103a72a9fc1615f45b461534c0a035ea4ea228f86c11f52dbfa6997f1483dbcc21bffffffff0188130000000000001976a914da8df9cc99e719562b52c209ebea7e28b8b3c60b88ac00000000');

var txid = hex.encode(digest.sha256(digest.sha256(bytes)).reverse());

var stream = new Stream(new ArraySource(bytes));

var previous = sync(Transaction.parse(stream));

var current = new Transaction();

var inputIndex = 0;

var spendingInput = {
    previousTxHash: txid,
    previousTxOutIndex: 0,
    script: [], // script is empty for now
    sequenceNo: 'ffffffff'
};

current.inputs[inputIndex] = spendingInput;

current.outputs.push({
    value: 15000,
    script: [
        'OP_DUP',
        'OP_HASH160',
        '54000657e2b8ebed5b1a1565b17aec63583ddc66',
        'OP_EQUALVERIFY',
        'OP_CHECKSIG'
    ]
});

var signature = signTransaction(previous, current, inputIndex,
    SigHashType.ALL.withAnyoneCanPay(), privateKey);

log('Signature', hex.encode(signature));

var valid = checkSignature(previous, current, inputIndex,
    signature, publicKey);

log('Signature valid?', valid);

// finalize transaction by adding signature and publicKey

spendingInput.script.push(hex.encode(signature));
spendingInput.script.push(hex.encode(publicKey));

log('Complete transaction', JSON.stringify(current, null, 2));

var bytes = [];
current.serializeInto(new ArraySink(bytes));

log('Serialized transaction', hex.encode(bytes));

    Serialized transaction can be sent to the Bitcoin network using Bitcoin Core’s sendrawtransaction command.

    Locked transactions

    Transactions can be made non-final. That prohibits miners from adding transaction to the block chain until specified time or block height.

    Transaction.prototype.isFinal = function(blockHeight, currentTimeMs) {
        var LOCKTIME_THRESHOLD = 500000000;
        if (this.lockTime === 0) {
            return true;
        }
        var threshold;
        if (this.lockTime < LOCKTIME_THRESHOLD) {
            threshold = blockHeight;
        } else {
            threshold = currentTimeMs / 1000;
        }
        if (this.lockTime < threshold) {
            return true;
        }
        function isInputFinal(input) {
            return input.sequenceNo === 'ffffffff' /* UINT_MAX */;
        }
        if (this.inputs.every(isInputFinal)) {
            return true;
        }
        return false;
    };

    Transaction below is the last, fine (pay deposit) transaction from the Multilottery scenario:

    var tx = new Transaction();
    
    tx.inputs.push({
        previousTxHash: '7ae5760af2105a5ba54a914f188686e2743ead50cd690afb7e609f7b99e0ae31',
        previousTxOutIndex: 0,
        script: [
            '3045022100a27c9532f4eb90240f598aa4c3ad43bc604fb4464688dad8113a943212d6638f022035ff6f215a4a432590d987f9c8ea839678506904a97643e8e99371b991b9438001',
            '3046022100b9d333b096a2a19bf6aa142aa429e7feb4d400b7af82bed4f5eca3ea7b7e83ec02210082d5be5da0a523c9c6e86ecf48f16cfbe3b32def49c92ce376cc87aa7467608601',
            '00'
        ],
        sequenceNo: '00000000'
    });
    
    tx.outputs.push({
        value: 45000,
        script: [
            'OP_DUP',
            'OP_HASH160',
            '62a2486468040e8a1a1f91d8949ac4dc838a0ed2',
            'OP_EQUALVERIFY',
            'OP_CHECKSIG'
        ]
    });
    
    tx.lockTime = 1384457550;
    
    log('Is final now?', tx.isFinal(310280, Date.now()));
    
    var dateInPast = new Date('2013-11-14T15:32:30.000Z');
    
    log('Was final ' + dateInPast + '?', tx.isFinal(310280, dateInPast))
    

      Brain wallet

      Because private keys are arrays of random bytes it is possible to use a passphrase to generate a private key and derive the public key from it.

      The advantage of this method is that the private key does not need to be stored on a hard drive and can be always retrieved from memory.

      The main disadvantage is the fact that the security of the key is directly proportional to the complexity of the chosen passphrase. Using the address generated from this sample private key will likely result in bitcoins being stolen.

      function getAddressFromPublicKey(publicKey) {
          var hash = digest.ripemd160(digest.sha256(publicKey));
      
          hash.unshift(0x00); // version byte, 0x00 for the main network
      
          var checksum = digest.sha256(digest.sha256(hash)).slice(0, 4);
      
          return base58.encode(hash.concat(checksum));
      }
      var passphrase = 'correct horse battery staple';
      
      var passbytes = passphrase.split('').map(function(letter) {
          return letter.charCodeAt(0);
      });
      
      var privateKey = digest.sha256(passbytes);
      
      log('Private key', hex.encode(privateKey));
      
      var publicKey = ecdsa.getPublicKey(privateKey);
      
      log('Public key', hex.encode(publicKey));
      
      log('Address', getAddressFromPublicKey(publicKey));

        Vanity addresses

        A vanity address is an address that starts with the given string (for example 1CuriozN3rhL9CupMZei7VKtnPjiTXQreT starts with 1Curio). As base58 encoding supports only limited subset of ASCII characters not all symbols can be used and the address for the main network will always have to start with the number 1.

        var startWith = '1C';
        
        var privateKey = new Uint8Array(32), start = performance.now();
        var publicKey, address;
        
        do {
            window.crypto.getRandomValues(privateKey);
        
            publicKey = ecdsa.getPublicKey(privateKey);
        
            address = getAddressFromPublicKey(publicKey);
        
        } while (address.indexOf(startWith) !== 0);
        
        log('Looking for key took (ms)', performance.now() - start);
        
        log('Private key', hex.encode(privateKey));
        
        log('Public key', hex.encode(publicKey));
        
        log('Address', address);

          Generating the vanity address in JavaScript with starting string longer than two characters will be slow. Using Vanitygen command line utility is a preferred method of generating long vanity addresses.

          Comments

          cancel

          Revisions

          1. Initial version.
          2. Add Brain wallet and Vanity addresses sections.