The hard way - Bitcoin: Transaction
This is Part 2 of 'The hard way - Bitcoin' series and I will start with 'the easy way' section first because even this gets a bit complex, then will continue with the hard stuff, crafting a Bitcoin transaction from scratch using basic math and cryptography.
A. The easy way
Create private key, public key and address
We are going to generate private key, public key and Bitcoin testnet address to be used in this article.
shell> bx seed # generate seed
27634686aa8838acaa68e27aea6c072534394ce411cb7d75
shell> echo 27634686aa8838acaa68e27aea6c072534394ce411cb7d75 | bx ec-new # generate private key
79020296790075fc8e36835e045c513df8b20d3b3b9dbff4d043be84ae488f8d
shell> echo 79020296790075fc8e36835e045c513df8b20d3b3b9dbff4d043be84ae488f8d | bx ec-to-public # generate public key
03996c918f74f0a6f1aeed99ebd81ab8eed8df99bc96fc082b20839259d332bad1
shell> echo 03996c918f74f0a6f1aeed99ebd81ab8eed8df99bc96fc082b20839259d332bad1 | bx ec-to-address # generate address
n1C8nsmi4sc4hMBGgVZrnhxeFtk1sTbMZ4
Previous transaction to be spent
In Bitcoin we have this concept called UTXO (Unspent Transaction Output) which is the unspent output of a previous transaction.
shell> bx fetch-tx d30de2a476060e08f4761ad99993ea1f7387bfcb3385f0d604a36a04676cdf93
transaction
{
hash d30de2a476060e08f4761ad99993ea1f7387bfcb3385f0d604a36a04676cdf93
inputs
{
input
{
address_hash 10924d4f0aefd6dc652ce1fe906694eba4dfc8ae
previous_output
{
hash 264d0f5be4ebdd1102e23c4b440955b04b291c654323bdd33cd51d8989e3d54f
index 1
}
script "[30450221009553c91c4aaf5ab137d5ed77cbc94a2c0511461f0de51b83fc2f00202f6a6beb022029a691221e1f664fa268524565d44f9e8a5387c5c091ec55f98ad12705720e7201] [02a46fc215bb6899814dc5bd026d815017784a2c4ceb78e7befdab1d5dfd51ef1a]"
sequence 4294967294
}
}
lock_time 1384777
outputs
{
output
{
address_hash de69e4fc748732103653236dcc31c79e87422925
script "dup hash160 [de69e4fc748732103653236dcc31c79e87422925] equalverify checksig"
value 3625875580
}
output
{
address_hash d7d35ff2ed9cbc95e689338af8cd1db133be6a4a
script "dup hash160 [d7d35ff2ed9cbc95e689338af8cd1db133be6a4a] equalverify checksig"
value 65000000
}
}
version 2
}
Create transaction
Create transaction with two parameters: input (previous transaction hash and previous transaction output index) and output (receiving address and amount to send in Satoshi).
shell> bx tx-encode -i d30de2a476060e08f4761ad99993ea1f7387bfcb3385f0d604a36a04676cdf93:1 -o 2NFrxEjw5v2i7L8pm9dWjWSFpDRXmj8dBTn:64000000
010000000193df6c67046aa304d6f08533cbbf87731fea9399d91a76f4080e0676a4e20dd30100000000ffffffff010090d0030000000017a914f81498040e79014455a5e8f7bd39bce5428121d38700000000
Sign transaction
Sign the input to be spent using private key and lock script.
shell> bx input-sign 79020296790075fc8e36835e045c513df8b20d3b3b9dbff4d043be84ae488f8d "dup hash160 [d7d35ff2ed9cbc95e689338af8cd1db133be6a4a] equalverify checksig" 010000000193df6c67046aa304d6f08533cbbf87731fea9399d91a76f4080e0676a4e20dd30100000000ffffffff010090d0030000000017a914f81498040e79014455a5e8f7bd39bce5428121d38700000000
3045022100b290086350a59ce28dd80cc89eac80eac097c20a50ed8c4f35b1ecbed789b65c02200129f4c34a9b05705d4f5e55acff0ce44b5565ab4a8c7faa4a74cf5e1367451101
Create unlock script using signed endorsement and the public key then set it as transaction's input.
shell> bx input-set "[3045022100b290086350a59ce28dd80cc89eac80eac097c20a50ed8c4f35b1ecbed789b65c02200129f4c34a9b05705d4f5e55acff0ce44b5565ab4a8c7faa4a74cf5e1367451101] [03996c918f74f0a6f1aeed99ebd81ab8eed8df99bc96fc082b20839259d332bad1]" 010000000193df6c67046aa304d6f08533cbbf87731fea9399d91a76f4080e0676a4e20dd30100000000ffffffff010090d0030000000017a914f81498040e79014455a5e8f7bd39bce5428121d38700000000
010000000193df6c67046aa304d6f08533cbbf87731fea9399d91a76f4080e0676a4e20dd3010000006b483045022100b290086350a59ce28dd80cc89eac80eac097c20a50ed8c4f35b1ecbed789b65c02200129f4c34a9b05705d4f5e55acff0ce44b5565ab4a8c7faa4a74cf5e13674511012103996c918f74f0a6f1aeed99ebd81ab8eed8df99bc96fc082b20839259d332bad1ffffffff010090d0030000000017a914f81498040e79014455a5e8f7bd39bce5428121d38700000000
Validate transaction
Validate input with public key, lock script and signed endorsement.
shell> bx input-validate 03996c918f74f0a6f1aeed99ebd81ab8eed8df99bc96fc082b20839259d332bad1 "dup hash160 [d7d35ff2ed9cbc95e689338af8cd1db133be6a4a] equalverify checksig" 3045022100b290086350a59ce28dd80cc89eac80eac097c20a50ed8c4f35b1ecbed789b65c02200129f4c34a9b05705d4f5e55acff0ce44b5565ab4a8c7faa4a74cf5e1367451101 010000000193df6c67046aa304d6f08533cbbf87731fea9399d91a76f4080e0676a4e20dd3010000006b483045022100b290086350a59ce28dd80cc89eac80eac097c20a50ed8c4f35b1ecbed789b65c02200129f4c34a9b05705d4f5e55acff0ce44b5565ab4a8c7faa4a74cf5e13674511012103996c918f74f0a6f1aeed99ebd81ab8eed8df99bc96fc082b20839259d332bad1ffffffff010090d0030000000017a914f81498040e79014455a5e8f7bd39bce5428121d38700000000
The endorsement is valid.
Validate encoded transaction as a whole.
shell> bx validate-tx 010000000193df6c67046aa304d6f08533cbbf87731fea9399d91a76f4080e0676a4e20dd3010000006b483045022100b290086350a59ce28dd80cc89eac80eac097c20a50ed8c4f35b1ecbed789b65c02200129f4c34a9b05705d4f5e55acff0ce44b5565ab4a8c7faa4a74cf5e13674511012103996c918f74f0a6f1aeed99ebd81ab8eed8df99bc96fc082b20839259d332bad1ffffffff010090d0030000000017a914f81498040e79014455a5e8f7bd39bce5428121d38700000000
The transaction is valid.
Broadcast transaction
Broadcast the transaction to network.
bx send-tx 010000000193df6c67046aa304d6f08533cbbf87731fea9399d91a76f4080e0676a4e20dd3010000006b483045022100b290086350a59ce28dd80cc89eac80eac097c20a50ed8c4f35b1ecbed789b65c02200129f4c34a9b05705d4f5e55acff0ce44b5565ab4a8c7faa4a74cf5e13674511012103996c918f74f0a6f1aeed99ebd81ab8eed8df99bc96fc082b20839259d332bad1ffffffff010090d0030000000017a914f81498040e79014455a5e8f7bd39bce5428121d38700000000
Sent transaction.
Check address and transaction history.
shell> bx fetch-history n1C8nsmi4sc4hMBGgVZrnhxeFtk1sTbMZ4
transfers
{
transfer
{
received
{
hash d30de2a476060e08f4761ad99993ea1f7387bfcb3385f0d604a36a04676cdf93
height 1384780
index 1
}
spent
{
hash fb8c52b201eb474ea3b2cb1f482cf4f774f710c711267818fbdd4763a5ca38b9
height 1384802
index 0
}
value 65000000
}
}
B. The hard way
Now lets get down to real business and craft our own transaction starting with a few utility methods that we are going to use along the way.
Two methods to convert big numbers to bytes string and vice-versa, padding with 0x00 to satisfy the required length if any.
def bytes_to_bignum(bytes_string)
bytes_string.bytes.reduce { |n, b| (n << 8) + b }
end
def bignum_to_bytes(n, length=nil)
a = []
while n > 0
a << (n & 0xFF)
n >>= 8
end
a.fill 0x00, a.length, length - a.length if length
a.reverse.pack('C*')
end
Base58 encoding / decoding methods, Bitcoin address decoding to Hash160 (hashing twice with sha256 then ripe160) and build Bitcoin script based on destination address that can be Pay-to-PublicKey-Hash or Pay-to-Script-hash.
def bitcoin_base58_encode(ripe160_hash)
alphabet = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
value = ripe160_hash.to_i 16
output = ''
while value > 0
remainder = value % 58
value /= 58
output += alphabet[remainder]
end
output += alphabet[0] * [ripe160_hash].pack('H*').bytes.find_index{|b| b != 0}
output.reverse
end
def bitcoin_base58_decode(address)
alphabet = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
int_val = 0
address.reverse.chars.each_with_index do |char, index|
char_index = alphabet.index(char)
int_val += char_index * 58**index
end
bignum_to_bytes(int_val, 25).unpack('H*').first
end
def bitcoin_address_decode(address)
wrap_encode = bitcoin_base58_decode address
wrap_encode[2, 40]
end
def bitcoin_script(address)
hash160 = bitcoin_address_decode address
if address.start_with? '2'
"OP_HASH160 #{hash160} OP_EQUAL"
else
"OP_DUP OP_HASH160 #{hash160} OP_EQUALVERIFY OP_CHECKSIG"
end
end
Multiple utility methods to transform different data types into hex string.
class Struct
OPCODES = {
'OP_DUP' => 0x76,
'OP_HASH160' => 0xA9,
'OP_EQUAL' => 0x87,
'OP_EQUALVERIFY' => 0x88,
'OP_CHECKSIG' => 0xAC
}.freeze
def opcode(token)
raise "opcode #{token} not found" unless OPCODES.include?(token)
OPCODES[token].to_s 16
end
def data(token)
bin_size = hex_size token
byte_to_hex(bin_size) + token
end
def hex_size(hex)
[hex].pack('H*').size
end
def to_hex(binary_bytes)
binary_bytes.unpack('H*').first
end
def hash_to_hex(value)
to_hex [value].pack('H*').reverse
end
def int_to_hex(value)
to_hex [value].pack('V')
end
def byte_to_hex(value)
to_hex [value].pack('C')
end
def long_to_hex(value)
to_hex [value].pack('Q<')
end
def script_to_hex(script_string)
script_string.split.map { |token| token.start_with?('OP') ? opcode(token) : data(token) }.join
end
def sha256(hex)
Digest::SHA256.hexdigest([hex].pack('H*'))
end
end
Now, lets check the previous transaction that we want to spend.
shell> bx fetch-transaction ea8a64e122304637e8da016836e9afd59fc1179dfa15affc40d63b34e7db0cec
transaction
{
hash ea8a64e122304637e8da016836e9afd59fc1179dfa15affc40d63b34e7db0cec
inputs
{
input
{
address_hash d7d35ff2ed9cbc95e689338af8cd1db133be6a4a
previous_output
{
hash 6b22d8a69432774ebbc00566755ff8da241be83c1b364ca177e241e23a0e111c
index 0
}
script "[3045022100e4c449be7643140b9a62635afe8f99406311372f6ad4215d19a6d0b0ea306c7902203c6966502dba43b86d34d9252adb7632632bce1cf83ed721b5a1ac00e9e0f48a01] [03996c918f74f0a6f1aeed99ebd81ab8eed8df99bc96fc082b20839259d332bad1]"
sequence 4294967295
}
}
lock_time 0
outputs
{
output
{
address_hash ad99d5964d9180d501c8863f4bcd7b04f0766787
script "dup hash160 [ad99d5964d9180d501c8863f4bcd7b04f0766787] equalverify checksig"
value 1000000
}
output
{
address_hash d7d35ff2ed9cbc95e689338af8cd1db133be6a4a
script "dup hash160 [d7d35ff2ed9cbc95e689338af8cd1db133be6a4a] equalverify checksig"
value 23990000
}
}
version 1
}
Build transaction input from previous UTXO (Unspent Transaction Output): value, tx hash and output index.
Input = Struct.new :value, :tx_hash, :index, :unlock_script, :sequence do
def initialize(value, tx_hash, index, unlock_script: '', sequence: 0xfffffffff)
super value, tx_hash, index, unlock_script, sequence
end
def serialize
script_hex = script_to_hex(unlock_script)
hash_to_hex(tx_hash) + int_to_hex(index) +
byte_to_hex(hex_size(script_hex)) + script_hex + int_to_hex(sequence)
end
end
input = Input.new 23_990_000, 'ea8a64e122304637e8da016836e9afd59fc1179dfa15affc40d63b34e7db0cec', 1
Build transaction output with output value and lock script.
Output = Struct.new :value, :lock_script do
def serialize
script_hex = script_to_hex(lock_script)
long_to_hex(value) + byte_to_hex(hex_size(script_hex)) + script_hex
end
end
output_script = bitcoin_script '2N959B4qEPkce8jbzQC7EQaS6uaEBB9YTgQ'
output = Output.new 1_000_000, output_script
Build the second output which is the 'change' transaction.
change_value = input.value - output.value - 10_000
change_script = bitcoin_script 'n1C8nsmi4sc4hMBGgVZrnhxeFtk1sTbMZ4'
change = Output.new change_value, change_script
Before creating the actual transction lets introduce a few elliptic curve methods methods and parameters that we all know and love already.
EC_Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
EC_Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
EC_p = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1
EC_n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
def extended_euclidean_algorithm(a, b)
s, old_s = 0, 1
t, old_t = 1, 0
r, old_r = b, a
while r != 0
quotient = old_r / r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
old_t, t = t, old_t - quotient * t
end
[old_r, old_s, old_t]
end
def inverse(n, p)
gcd, x, y = extended_euclidean_algorithm(n, p)
(n * x + p * y) % p == gcd || raise('invalid gcd')
gcd == 1 || raise('no multiplicative inverse')
x % p
end
def ec_double(px, py, pn)
i_2y = inverse(2 * py, pn)
slope = (3 * px**2 * i_2y) % pn
x = (slope**2 - 2 * px) % pn
y = (slope*(px - x) - py) % pn
[x, y]
end
def ec_add(ax, ay, bx, by, pn)
return [ax, ay] if bx == 0 && by == 0
return [bx, by] if ax == 0 && ay == 0
return ec_double(ax, ay, pn) if ax == bx && ay == by
i_bax = inverse(ax - bx, pn)
slope = ((ay - by) * i_bax) % pn
x = (slope**2 - ax - bx) % pn
y = (slope*(ax - x) - ay) % pn
[x, y]
end
def ec_multiply(m, px, py, pn)
nx, ny = px, py
qx, qy = 0, 0
while m > 0
qx, qy = ec_add qx, qy, nx, ny, pn if m&1 == 1
nx, ny = ec_double nx, ny, pn
m >>= 1
end
[qx, qy]
end
And these are the core methods of Elliptic Curve Digital Signature Algorithm (ECDSA), the sign/verify methods with DER signature encoding.
def ecdsa_sign(private_key, digest, temp_key = nil)
temp_key ||= 1 + SecureRandom.random_number(EC_n - 1)
rx, _ry = ec_multiply(temp_key, EC_Gx, EC_Gy, EC_p)
r = rx % EC_n
r > 0 || raise('r is zero, try again new temp key')
i_tk = inverse temp_key, EC_n
m = bytes_to_bignum digest
s = (i_tk * (m + r * private_key)) % EC_n
s > 0 || raise('s is zero, try again new temp key')
[r, s]
end
def ecdsa_verify?(px, py, digest, signature)
r, s = signature
i_s = inverse s, EC_n
m = bytes_to_bignum digest
u1 = i_s * m % EC_n
u2 = i_s * r % EC_n
u1Gx, u1Gy = ec_multiply u1, EC_Gx, EC_Gy, EC_p
u2Px, u2Py = ec_multiply u2, px, py, EC_p
rx, _ry = ec_add u1Gx, u1Gy, u2Px, u2Py, EC_p
r == rx
end
Der = Struct.new :der, :length, :ri, :rl, :r, :si, :sl, :s, :sighash_type do
def initialize(der: 0x30, length: 0x45, ri: 0x02, rl: 0x21, r: nil, si: 0x02, sl: 0x20, s: nil, sighash_type: 0x01)
super der, length, ri, rl, r, si, sl, s, sighash_type
end
def serialize
byte_to_hex(der) + byte_to_hex(length) +
byte_to_hex(ri) + byte_to_hex(rl) + to_hex(bignum_to_bytes(r, 33)) +
byte_to_hex(si) + byte_to_hex(sl) + to_hex(bignum_to_bytes(s, 32)) +
byte_to_hex(sighash_type)
end
def self.parse(signature)
fields = *[signature].pack('H*').unpack('CCCCH66CCH64C')
Der.new r: fields[4], s: fields[7], sighash_type: fields[8]
end
end
We are getting there, build Bitcoin transaction passing in the input and the two outputs.
Transaction = Struct.new :version, :inputs, :outputs, :locktime do
def serialize
inputs_hex = inputs.map(&:serialize).join
outputs_hex = outputs.map(&:serialize).join
int_to_hex(version) + byte_to_hex(inputs.size) + inputs_hex +
byte_to_hex(outputs.size) + outputs_hex + int_to_hex(locktime)
end
def hash
hash_to_hex sha256(sha256(serialize))
end
def signature_hash(lock_script = nil, sighash_type = 0x1)
inputs.first.unlock_script = lock_script if lock_script
hash = sha256(sha256(serialize + int_to_hex(sighash_type)))
[hash].pack('H*')
end
def sign(private_key, public_key, lock_script, sighash_type = 0x01)
bytes_string = signature_hash lock_script, sighash_type
r, s = ecdsa_sign private_key, bytes_string
der = Der.new r: r, s: s
inputs.first.unlock_script = "#{der.serialize} #{public_key}"
serialize
end
end
transaction = Transaction.new 1, [input], [output, change], 0
Finally, to sign the transaction we need 3 things: private key, public key and the lock script of previous UTXO to spend.
private_key = 0x79020296790075fc8e36835e045c513df8b20d3b3b9dbff4d043be84ae488f8d
public_key = '03996c918f74f0a6f1aeed99ebd81ab8eed8df99bc96fc082b20839259d332bad1'
lock_script = bitcoin_script 'n1C8nsmi4sc4hMBGgVZrnhxeFtk1sTbMZ4'
tx_hex = transaction.sign private_key, public_key, lock_script
puts "TX hash: #{transaction.hash}"
puts "TX hex: #{tx_hex}"
And VOILA! take the returned transaction hex and decode/validate it:
shell> bx tx-decode 0100000001ec0cdbe7343bd640fcaf15fa9d17c19fd5afe9366801dae837463022e1648aea010000006b483045022100c1c85b5865f64f8f18c54f028a50942cd21cbda9c4a5f9296132defe51017c640220304793e361e71b3bae812923ca4aa5481a2fead05a73583ad5d930e7229f562f012103996c918f74f0a6f1aeed99ebd81ab8eed8df99bc96fc082b20839259d332bad1ffffffff0240420f000000000017a914ad99d5964d9180d501c8863f4bcd7b04f076678787a0a55e01000000001976a914d7d35ff2ed9cbc95e689338af8cd1db133be6a4a88ac00000000
transaction
{
hash c218dc394fef23ab9652ed6fd49539aa5dfb4f0153127b5c433032918948e60b
inputs
{
input
{
address_hash d7d35ff2ed9cbc95e689338af8cd1db133be6a4a
previous_output
{
hash ea8a64e122304637e8da016836e9afd59fc1179dfa15affc40d63b34e7db0cec
index 1
}
script "[3045022100c1c85b5865f64f8f18c54f028a50942cd21cbda9c4a5f9296132defe51017c640220304793e361e71b3bae812923ca4aa5481a2fead05a73583ad5d930e7229f562f01] [03996c918f74f0a6f1aeed99ebd81ab8eed8df99bc96fc082b20839259d332bad1]"
sequence 4294967295
}
}
lock_time 0
outputs
{
output
{
address_hash ad99d5964d9180d501c8863f4bcd7b04f0766787
script "hash160 [ad99d5964d9180d501c8863f4bcd7b04f0766787] equal"
value 1000000
}
output
{
address_hash d7d35ff2ed9cbc95e689338af8cd1db133be6a4a
script "dup hash160 [d7d35ff2ed9cbc95e689338af8cd1db133be6a4a] equalverify checksig"
value 22980000
}
}
version 1
}
then submit it to Bitcoin testnet network via:
- Broadcast TX
- or using
bitcoin-clicommand line tool
shell> bitcoin-cli -testnet sendrawtransaction 0100000001ec0cdbe7343bd640fcaf15fa9d17c19fd5afe9366801dae837463022e1648aea010000006b483045022100c1c85b5865f64f8f18c54f028a50942cd21cbda9c4a5f9296132defe51017c640220304793e361e71b3bae812923ca4aa5481a2fead05a73583ad5d930e7229f562f012103996c918f74f0a6f1aeed99ebd81ab8eed8df99bc96fc082b20839259d332bad1ffffffff0240420f000000000017a914ad99d5964d9180d501c8863f4bcd7b04f076678787a0a55e01000000001976a914d7d35ff2ed9cbc95e689338af8cd1db133be6a4a88ac00000000
C. Conclusions
Creating transaction is a bit more difficult than generating a Bitcoin address that we saw in Part 1 but it is all possible once you understand the basics of Bitcoin like UTXOs, script and transactions.
D. References
Here are the most important references but feel free to get in touch for more information.
The very end.