BLOCKCHAIN TRANSACTIONS

AND ALGORITHMS
An Introduction
BITCOIN TRANSACTION DETAILS
(PART 1)
A good step-by-step tutorial on bitcoin core client (bitcoin-cli aka bitc) can be found
here:
[Link]
Transactions
• Everything in Bitcoin is designed around the handling of transactions, ensuring that
transactions can be:
• Created
• Propagated
• Validated
• Irreversible
• Bitcoin does not use a traditional accounting ledger with a “current balance”
• A transaction’s ID is a hash of the transaction itself
Transactions at 5,000 Feet
• A transaction is a transfer of Bitcoin value broadcast over the network and collected
into blocks.
• A transaction usually references one or more previous transaction outputs as new
transaction inputs and dedicates all input Bitcoin values to new outputs.
• Transactions are actually not encrypted, so it is possible to browse and view every
transaction ever collected into a block.
• Once transactions are buried under enough confirmations, they can be
considered irreversible.
• Standard transaction outputs nominate addresses, and the redemption of any future
inputs requires a relevant signature.
• All transactions are visible in the block chain and can also be viewed with a hex editor.
• Blockchain browsers such as blockchain explorer ([Link]
and Block Explorer for Testnet ([Link] are useful sites for
looking into blocks and transactions
An Analogy
• A parent earns $20 dollars in a golf match,
which he’d been paid by his golf partner
• He decides to give each of his two kids their
allowance for the week
• He hands his daughter $10 of the $20
• He hands his son $10 of the $20
• Dad has no more money in his wallet
• In this transaction, Dad took the $20 he
had won at the golf course, and divided it
up into two $10 dollar bills, and handed
each kid a $10 dollar bill.
• In this, $20 came in, and $20 went out
(some say vanished), it’s just different
people on the receiving end of the
transaction
Transactional Activities Charlie’s dad wins a $20
payout at the golf course...

Txn Divides the

n-1
payout into two
In Out equal parts...

XX $20

Txn n
Kids now can
spend their
In Out money
$20
$10 $10

Dad takes that

$20 payout won at
the golf course...
Bitcoin Transactions
Charlie’s dad wins a 20 BTC
payout at the golf course...

Txn
Dad divides the
n-1
payout into two
In Out
equal parts...
XX 20
btc btc
Txn n
Kids now can
each spend their
In Out 10 bitcoins
20
btc 10 10
btc btc

Dad takes that 20

BTC won at the
golf course...
Bitcoin Transactions - Inputs
• Alice pays Bob 10 BTC and pays Giselle 10 BTC as well

Txn n-1

In Out
XX 20 Txn Bob & Giselle
[0] n
btc btc

In Out
20
btc 10 10
btc btc

Alice’s Private
Key
1af8374bf1241cc4
generates... 69982e69db1c3263
07afccc989d720df
48babeca51dc4c10
Alice’s Public Key Alice’s Digital
H( ) 0584abf1241cc469
Signature as
Hash of
previous
[0] 982e69db1c326307
afc9d720dabeca51
Owner of 20 BTC

Transaction Index dc4c10bfc56f7bf0

Transaction Outputs
• For reference, if you stop by a 7-Eleven to buy a $.50 pack of chewing gum (with sales
tax at 10%), and you hand the teller a $2.00 bill, you will expect two things in return,
right?
• Your chewing gum you just bought
• $1.45 in change ($2.00 - $0.50 for the gum - $0.05 tax)
• Great News! Bitcoin works the same way!
• What this means is that all outputs are discrete and indivisible units of bitcoin, and
each and every output can only be consumed (spent) in its entirety
• Think about it. You would expect the teller
at the 7-Eleven to react rather oddly if you
handed her something that looked like this:
• You can no more spend partial outputs
than you can spend half a two-dollar bill.
Bitcoin Transactions - Outputs
• Alice pays Bob 10 BTC and pays Giselle 10 BTC as well Bob’s Private Key

Txn n-1
1348eff8a7436eda
837f6238778bb5s7 10
fds77790734abab4 btc 10
In Out 87aacce8767bc230 btc

@ @
XX 20 Txn Bob & Giselle
[0] n
1a8b
fed...
14b4
f91...
btc btc
In Out
Out generates...
10 PayTo:
20 btc Address1a8bfed...
btc
Out
10 PayTo:
btc Address14b4f91...
generates...

Giselle’s Private
Key
1b1c326a4bf1241c
Alice’s Public Key Alice’s Digital c469982e69dbabec
H( ) 0584abf1241cc469
Signature as a51dc4c307afccc9
f83789d7201dc879
Hash of
previous
[0] 982e69db1c326307
afc9d720dabeca51
Owner of 20 BTC

Transaction Index dc4c10bfc56f7bf0

 Transactions Between Alice, Bob and Giselle

Gee, thanks
Alice Alice Bob Bob for the
$1.3MM,
receives spends receives spends Bob!

Txn n Txn n+1

20 BTC In Out In
10 BTC 10 BTC
divides

From 20 10 To From
10
her golf btc btc Bob
As the world turns...
So does the passage of time... Alice btc Out 20 BTC
20 To
buddies
btc
Giselle Giselle

aggregates
Out In receives
10 BTC 10 BTC
10 To From 10
btc Bob Alice btc
 Transactions Between Alice, Bob and Giselle
Header
... Header Header Header Header
MerkleRoot MerkleRoot MerkleRoot HABCD MerkleRoot

A Chain of Blocks Containing Transactions

Alice’s Private Key

Txn n-1 Txn 3495a4fab0ff587f6050a22035e12253b250d088413dbd30b1cb44365b87bd86

In Out In Out
20 10 PayTo:
btc [0] 10 PayTo: Address
Index btc 1ab837f5edf... btc Address1a8bfed...
A Smorgasbord of Algorithms Relevant for Bitcoin
• Sorting
• Bubble, Selection, Insertion, Merge
• Data Structures
• Stacks
• Queues
• Trees
• Lists
• Searching
• Sequential
• Binary
• Breadth First, Depth First
• Graphs & Trees
• Binary Trees
• Priority Queues
• Binary Heaps
• Strings & Greedy Algorithms
• Nondeterministic Finite Automatons, etc.
REVIEW OF TREES
Binary Trees
Binary Search Tree
Trees are used in Bitcoin’s Merkle Tree algorithm
Tree Algorithms root

• You can think of a tree as a special kind of graph, A

edge edge
specifically, an acyclic connected graph.
• Vocabulary B C
leaf edge parent edge
• The first node of a tree is the root node child child

• Any node that is connected to a subsequent node D E

parent leaf
is a parent node of the subsequent node, and the child

subsequent node is the parent node’s child F

edge parent edge
• Nodes are linked together by edges child child

• The final node in a given path is known as a leaf G H

leaf leaf
node, which is a node without any child nodes

Nodes edge
Tree Algorithms Depth

root
• Path: sequence of edges, each edge starts with 0
A
the node where the previous edge ends edge edge

• Length of path: number of edges from α to β

B C 1
• Height of a node: length of longest path from leaf edge parent edge

the node to a leaf child child

D E 2
• Height of tree: height of root to farthest leaf parent leaf
child
• Depth (or level) of a node: length of a given
F 3
path from root to the node edge parent edge
child child
• Depth of tree: maximum depth of any leaf
G H 4
leaf leaf

• Height of Tree: 4
• Height of Node B: 0
• Height of Node C: 3
• Height of Node D: 2
• Length of Path A-C-D-F-G: 4
Tree Algorithms
• Vocabulary
• Binary tree: a tree in which each node has at most two children.

• Complete binary tree (AKA Balanced Binary Tree): tree in which all child leaves are on
the same level and each non-leaf node has exactly zero, one or two children (if a node has
only one child, it must be a left child, i.e. no node can have a right child without also
having a left child).
Tree Traversal
• We have a few options for traversal: Depth-First Search (DFS) and Breadth-First Search
(BFS).
• A Depth-First Search is an algorithm for traversing or searching tree data structures
where one starts at the root and explores as far as possible along each branch before
backtracking.
• There are three types of DFS: pre-order, in-order, and post-order
• Pre-order Traversal:
1. Print the value of the node.
2. Go to the left child and print it if, and only if, it has a left child.
3. Go to the right child and print it if, and only if, it has a right child. 1

• Depth-First pre-order Search (DFS) yields the path: 1,2,3,4,5,6,7

• A walk in which each parent node is traversed 2 5

before its children is called a pre-order walk

3 4 6 7
 Tree Traversal
• Now that we are familiar with this traversal algorithm, we will discuss two additional
types of DFS: in-order, and post-order.
1

2 5

3 4 6 7

In-Order Traversal Post-Order Traversal

The result of the in-order algorithm is 3–2–4–1–6–5–7 The result of the post-order algorithm is 3–4–2–6–7–5–1
Steps: Steps:
1. Go to the left child and print it if, and only if, it has a left child. 1. Go to the left child and print it if, and only if, it has a left child.
2. Print the node’s value 2. Go to the right child and print it if, and only if, it has a right child.
3. Go to the right child and print it if, and only if, it has a right child. 3. Print the node’s value

A Traversal that is a walk in which a node's left subtree, then the A Traversal that is a walk in which the children are traversed before
node itself, and finally its right subtree are traversed is called an in- their respective parents are traversed is called a post-
order traversal. order traversal.
Binary Search Tree
• A Binary Tree is a tree whose outdegree is bounded by 2 (note a tree with an outdegree of
1 is known as a list)
• A Binary Search Tree is one where all of its “left” descendants (all elements in its left-
hand branch) are smaller in value than the value of the node itself, and all of its “right”
descendants (all elements in its right-hand branch) are larger in value than the value of
the node itself
• Stated formally, a Binary Search Tree is a binary tree that has the following property:
Let x be a node in a binary search tree. If y is a node in the left subtree of x,
then key[y] ≤ key[x]. If y is a node in the right subtree of x, then key[x] ≤ key[y]
Which of the following are valid Binary Search Trees?
Binary Search Tree
• Build a Binary Search Tree with the following list of numbers: 40, 60, 30, 80, 20, 50,
35, 45, 37, 90, 10, 25, 34, 70, 55:
• A Binary Search Tree may be sorted in-order in this way:
(1) If T is empty, return;
(2) Else, do:
(1) Call second-visit-traversal-of left(T)
(2) Process Node at root of T
(3) Call second-visit-traversal-of right(T)
(4) return
Tree Algorithms
• Build a Binary Search Tree with the following list of numbers: 40, 60, 30, 80, 20, 50,
35, 45, 37, 90, 10, 25, 34, 70, 55:
(1) If T is empty, return;
(2) Else, do:
(1) Call second-visit-traversal-of left(T)
(2) Process Node at root of T
(3) Call second-visit-traversal-of right(T)
(4) return
Binary Search Tree Example
• python3 [Link]/lecture.4/trees/[Link]
HASH POINTERS
 Blockchains Use Hash Pointers
• A hash pointer is a pointer to some information stored together with a cryptographic
hash of that information.
• We can use hash pointers in any pointer-based data structure as long as the data
structure is an acyclic graph
• Like a regular pointer, a hash pointer is a way to find the information, but a hash
pointer also gives us a way to verify that the information pointed to has not changed
• We can use hash pointers to build all kinds of data structures. Intuitively, we can take a
familiar data structure that uses pointers such as a linked list or a binary search tree and
implement it with hash pointers, instead of pointers as we normally would. Very Important:
we can create a
“hash of a
hash”…
H( ) H( ) H( )
Data Data Data 0584abf1241cc
(Same size (Same size (Same size 469982e69db1c
every time) every time) every time) 326307afc9d72
0dabeca51dc4c
10bfc56f7bf0
MERKLE TREES
A balanced binary tree of hash pointers
Merkle Trees
• Each block in the bitcoin blockchain contains a summary hash of all the transactions in
the block, using a merkle tree.
• A merkle tree, which is basically a balanced binary hash tree, is a data structure used for
efficiently summarizing and verifying the integrity of large sets of data.
• Merkle trees are binary trees containing cryptographic hash pointers to other data.
• Merkle trees are used in bitcoin to summarize all the transactions in a block, producing
an overall digital fingerprint of the entire set of transactions in the block, providing a very
efficient process to verify whether a transaction is included in a block.
• A Merkle tree is constructed by recursively hashing pairs of hashes until there is only
one resulting hash, called the root hash, or merkle root.

a hash of two (concatenated) hashes…

 Merkle Trees
• To prove that an item is in the tree, you only need to produce log2(N) 32-byte hashes,
and this will constitute an authentication path or merkle path
• A Merkle Tree can hold many items efficiently and securely: Remember, by our
properties, we know that if we rehash this tree all the way up to the root, if our re-hash
matches the root, we can confirm that nothing in the data hashed has changed.
Merkle Root

HABCD
Hash(HAB + HCD )

These are merely “hashes

of hashes”… HAB HCD
Hash(HC + HD )
Branches in the middle
Hash(HA + HB )

This is the data HA HB HC HD

Leaf Data at the bottom
we are hashing… Hash(Data A) Hash(Data B) Hash(Data C) Hash(Data D)
Merkle Trees are Generally Balanced
• When N data elements mod 2 != 0, the last (dangling) element is simply repeated (as in
a balanced B-Tree) (DAG Merkle Trees may be unbalanced...not for bitcoin...)
 Merkle Tree Membership
• To prove that an item is in the tree, you only need to produce log2(N) 32-byte hashes,
and this will constitute an authentication path or merkle path
• Suppose we want to show that Data Item HK is in the merkle tree below, what minimal
set of actual data items would we need to be given in order to most efficiently validate
(prove) that?

These
are
merely
“hashes
of
hashes”
…

Data to
Be hashed…
 Merkle Trees
• To prove that an item is in the tree, you only need to produce log2(N) 32-byte hashes, and this
will constitute an authentication path or merkle path
• Suppose we want to show that Data Item K is in the merkle tree below, what actual data items
would we need to provide in order to validate that?
• This becomes important when we later talk about validating transactions and bloom filters

We would need to
We don’t need to
provide the following
provide these
four hashes:
hashes, as we can
HL
calculate these
HIJ
hashes from what
HMNOP
we are given...
HABCDEFGH
BLOCKCHAINS –
PUTTING IT ALL TOGETHER
“Once we have eaten our cryptographic vegetables...”—Ed Felton, Princeton
 A Blockchain
• A blockchain is simply a linked list linked by hash pointers instead of regular pointers
• Its purpose is to link data together in such a way that each subsequent block contains a
pointer to a previous block and a cryptographic hash of that data
• The result is a tamper-proof list where any change anywhere along the links will
immediately be noticeable

Prev: H(n) Prev: H(4) Prev: H(3) Prev: H(2)

H( )
... Data4 Data3 Data2 Data1

{Height = 999} {Height = 1000} {Height = 1001} {Height = 1002}

Timed Growth of Blockchain

 A Blockchain
• If someone subsequently tampers with the data, say Data3 in the purple block at height
1000, the subsequent block’s hash pointer (at height 1001) will no longer validate
• As soon as someone goes through the process of chain validation, they will come to the
green block, grab the purple hash pointer, and navigate to its previous block, and rehash
data Data3 and discover the fingerprint mismatch
• The hash pointers can be followed all the way back to the genesis block, the original
block at block height 0

X H( )
Prev: H(n) Prev: H(4) Prev: H(3) Prev: H(2)

... Data4 Data3 Data2 Data1

{Height = 999} {Height = 1000} {Height = 1001} {Height = 1002}

Timed Growth of Blockkchain

MERKLE TREES OF
TRANSACTIONS
Bitcoin Block Structure
• Each block contains three things related to transactions:
• A count of the transactions in the block
• The Merkle Root of the transactions in the block
• A list of the transactions in the block

First block in the The Chain Tip is

chain is the the last block in
Genesis Block the chain

Header Header
Header Header Header Header Header Header
MerkleRoot MerkleRoot MerkleRoot MerkleRoot HABCD MerkleRoot MerkleRoot MerkleRoot

Merkle Root
Merkle Trees of Transactions
• Transactions are represented in blocks with their
MerkleRoot, and the MerkleRoot is in the Block Header
• This is the key to the kingdom: it brands all transactions
in that block as inviolable going forward, as it is trivial to

Timed Growth of Blockchain

verify the merkle root is correct from the transaction
hashes, Q.E.D. Merkle Root
$ bitc getblockhash 0
000000000933ea01ad0ee984209779baaec3ced90fa3f408719526f8d77f4943
$ bitc getblock 000000000933ea01ad0ee984209779baaec3ced90fa3f408719526f8d77f4943
{
"hash": "000000000933ea01ad0ee984209779baaec3ced90fa3f408719526f8d77f4943",
...
The Genesis Block
"merkleroot": "4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b",
"tx": [ (notice: no previousblockhash)
"4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b"
],
...
"nextblockhash": "00000000b873e79784647a6c82962c70d228557d24a747ea4d1b8bbe878e1206"
}

$ bitc getblockhash 1
00000000b873e79784647a6c82962c70d228557d24a747ea4d1b8bbe878e1206
$ bitc getblock 00000000b873e79784647a6c82962c70d228557d24a747ea4d1b8bbe878e1206
{
"hash": "00000000b873e79784647a6c82962c70d228557d24a747ea4d1b8bbe878e1206",
...
"merkleroot": "f0315ffc38709d70ad5647e22048358dd3745f3ce3874223c80a7c92fab0c8ba", Merkle Hashes are
"tx": [

],
"f0315ffc38709d70ad5647e22048358dd3745f3ce3874223c80a7c92fab0c8ba"
single SHA-256 hashes
...
"previousblockhash": "000000000933ea01ad0ee984209779baaec3ced90fa3f408719526f8d77f4943",
"nextblockhash": "000000006c02c8ea6e4ff69651f7fcde348fb9d557a06e6957b65552002a7820"
}

$ bitc getblockhash 2
000000006c02c8ea6e4ff69651f7fcde348fb9d557a06e6957b65552002a7820
$ bitc getblock 000000006c02c8ea6e4ff69651f7fcde348fb9d557a06e6957b65552002a7820
{
"hash": "000000006c02c8ea6e4ff69651f7fcde348fb9d557a06e6957b65552002a7820",
...
"merkleroot": "20222eb90f5895556926c112bb5aa0df4ab5abc3107e21a6950aec3b2e3541e2",
"tx": [
"20222eb90f5895556926c112bb5aa0df4ab5abc3107e21a6950aec3b2e3541e2"
...
"previousblockhash": "00000000b873e79784647a6c82962c70d228557d24a747ea4d1b8bbe878e1206",
"nextblockhash": "000000008b896e272758da5297bcd98fdc6d97c9b765ecec401e286dc1fdbe10"
}
Merkle Root Revisited
$ bitc getblock 000000000000004fbc510b95ba2366576879aad7f018b20bf8532267182cb7d1
{
"hash": "000000000000004fbc510b95ba2366576879aad7f018b20bf8532267182cb7d1",
...
"height": 1324789,
...
"merkleroot": "a259dffe797877b1542f563e8a70c127c788245f7d8a88af05fda7f0d5290fef",
"tx": [
"b5f60977102f95a9ed855b61acec86e2e434248b38c5f263ccf708a302832f3c",
"e6922d44c520c52dca2cd5300784af55944c11839684e5c1671d9b330f871f55",
"a72ef0e0240fb592dd1d6ec3d1ab24890def0870f5c44d478f1feb1f87701e43",
"51ef089bd2fc330cd02ee9d5a3cb5532ed48d8668ed78a92b84c8da97922975a",
"ae22ea6889a5712eb2e13736ce4586afd310295c6ddbbc2b56b1305441017a70",
"cfce9664889e17fa006cfa23dd82852a999f9a748478cf325e3791241dd27a50",
"4db4ac98aa68d75dc3602f8f3b06157ac93485268df220cc6dc4aa39f6f9d7a9",
"a0337aef8e3739e6b705c51202a9d58addc375e2830e3429727a461052279d46",
"0dc7b3bf9b1a98859d694146a0acd5a988d4184ab9c048ea91d8be7fd1cd84e6",
"72e15234eb42c9f4b650dec5727205dacbbcb039e8c22034b00bf805192abec7",
"dca4db368d5241219a0f5f8c744c42293b9bc4959b99e4ed43abc075c284b78c",
"a5e67793f9193a7b9192e4c3e7cd27268ef354b0513a9cd595c04778d3fa3eef",
"4d53b64a343589f9b76643c80eacdd632cc50fcec6ece4dd7d3c0c65dba1d0f9",
"3495a4fab0ff587f6050a22035e12253b250d088413dbd30b1cb44365b87bd86" Build the tree
],
...
"previousblockhash": "000000000000004950205cca66572178be57a990f58b9a6741ad683a36c9a46e",
"nextblockhash": "0000000000000037d75561c013e8b7ab882dc1f0f226dc060f0c42fefff80ebc"
}

[Link]
The Merklelizer Test
$ bitc getblock 000000000000004fbc510b95ba2366576879aad7f018b20bf8532267182cb7d1
{
"hash": "000000000000004fbc510b95ba2366576879aad7f018b20bf8532267182cb7d1",
...
"height": 1324789,
...
"merkleroot": "a259dffe797877b1542f563e8a70c127c788245f7d8a88af05fda7f0d5290fef",
"tx": [
"b5f60977102f95a9ed855b61acec86e2e434248b38c5f263ccf708a302832f3c",
"e6922d44c520c52dca2cd5300784af55944c11839684e5c1671d9b330f871f55",
"a72ef0e0240fb592dd1d6ec3d1ab24890def0870f5c44d478f1feb1f87701e43",
"51ef089bd2fc330cd02ee9d5a3cb5532ed48d8668ed78a92b84c8da97922975a",
"ae22ea6889a5712eb2e13736ce4586afd310295c6ddbbc2b56b1305441017a70",
"cfce9664889e17fa006cfa23dd82852a999f9a748478cf325e3791241dd27a50",
"4db4ac98aa68d75dc3602f8f3b06157ac93485268df220cc6dc4aa39f6f9d7a9",
"a0337aef8e3739e6b705c51202a9d58addc375e2830e3429727a461052279d46",
"0dc7b3bf9b1a98859d694146a0acd5a988d4184ab9c048ea91d8be7fd1cd84e6",
"72e15234eb42c9f4b650dec5727205dacbbcb039e8c22034b00bf805192abec7",
"dca4db368d5241219a0f5f8c744c42293b9bc4959b99e4ed43abc075c284b78c", The Merkleizer™
"a5e67793f9193a7b9192e4c3e7cd27268ef354b0513a9cd595c04778d3fa3eef",
"4d53b64a343589f9b76643c80eacdd632cc50fcec6ece4dd7d3c0c65dba1d0f9",
"3495a4fab0ff587f6050a22035e12253b250d088413dbd30b1cb44365b87bd86"
],
...
"previousblockhash": "000000000000004950205cca66572178be57a990f58b9a6741ad683a36c9a46e",
"nextblockhash": "0000000000000037d75561c013e8b7ab882dc1f0f226dc060f0c42fefff80ebc"
}
 The MerklelizerTM
$ bitc getblock 000000000000004fbc510b95ba2366576879aad7f018b20bf8532267182cb7d1
{
"hash": "000000000000004fbc510b95ba2366576879aad7f018b20bf8532267182cb7d1",
...
"height": 1324789,
...
"merkleroot": "a259dffe797877b1542f563e8a70c127c788245f7d8a88af05fda7f0d5290fef",
"tx": [
"b5f60977102f95a9ed855b61acec86e2e434248b38c5f263ccf708a302832f3c",
"e6922d44c520c52dca2cd5300784af55944c11839684e5c1671d9b330f871f55",
"a72ef0e0240fb592dd1d6ec3d1ab24890def0870f5c44d478f1feb1f87701e43",
"51ef089bd2fc330cd02ee9d5a3cb5532ed48d8668ed78a92b84c8da97922975a",
"ae22ea6889a5712eb2e13736ce4586afd310295c6ddbbc2b56b1305441017a70", The Merkleizer™
"cfce9664889e17fa006cfa23dd82852a999f9a748478cf325e3791241dd27a50",
"4db4ac98aa68d75dc3602f8f3b06157ac93485268df220cc6dc4aa39f6f9d7a9",
"a0337aef8e3739e6b705c51202a9d58addc375e2830e3429727a461052279d46",
"0dc7b3bf9b1a98859d694146a0acd5a988d4184ab9c048ea91d8be7fd1cd84e6",
"72e15234eb42c9f4b650dec5727205dacbbcb039e8c22034b00bf805192abec7",
"dca4db368d5241219a0f5f8c744c42293b9bc4959b99e4ed43abc075c284b78c",
"a5e67793f9193a7b9192e4c3e7cd27268ef354b0513a9cd595c04778d3fa3eef",
"4d53b64a343589f9b76643c80eacdd632cc50fcec6ece4dd7d3c0c65dba1d0f9",
"3495a4fab0ff587f6050a22035e12253b250d088413dbd30b1cb44365b87bd86"
],
...
"previousblockhash": "000000000000004950205cca66572178be57a990f58b9a6741ad683a36c9a46e",
"nextblockhash": "0000000000000037d75561c013e8b7ab882dc1f0f226dc060f0c42fefff80ebc"
}
$ $tail –[Link]/lecture.3/merklebuilder/[Link]
python [Link]
$ a259dffe797877b1542f563e8a70c127c788245f7d8a88af05fda7f0d5290fef
python3 [Link]/lecture.4/merklebuilder/[Link]
$ ruby [Link]/lecture.3/merklebuilder/[Link]
a259dffe797877b1542f563e8a70c127c788245f7d8a88af05fda7f0d5290fef
a259dffe797877b1542f563e8a70c127c788245f7d8a88af05fda7f0d5290fef
$ ruby [Link]/lecture.4/merklebuilder/[Link]
a259dffe797877b1542f563e8a70c127c788245f7d8a88af05fda7f0d5290fef
b5f60977102f95a9ed855b61acec86e2e434248b38c5f263ccf708a302832f3c fbde8de832fc532e8749ef8b6d7f4095ab51363a5176b4d68fee565ce6ec404a
e6922d44c520c52dca2cd5300784af55944c11839684e5c1671d9b330f871f55 dfc9d9c65c81b84d964a489673d3aa55a104fb8310cb2f012edf9e85a0e2a331
a72ef0e0240fb592dd1d6ec3d1ab24890def0870f5c44d478f1feb1f87701e43 519192022964a43a8f6083ca8a9db00d67240b6bc27527b98e161cbf61f61b55
Hashes to...
51ef089bd2fc330cd02ee9d5a3cb5532ed48d8668ed78a92b84c8da97922975a 932e4b5b88444f9001279f3e6b9f8c9144b30194a47723f6ffe46e2c83433d20
ae22ea6889a5712eb2e13736ce4586afd310295c6ddbbc2b56b1305441017a70 56b79f789eb27436f176b9beea918d1d1538f6b7b4706fa33f499def2c7d4abf
cfce9664889e17fa006cfa23dd82852a999f9a748478cf325e3791241dd27a50 2bbd8846e4e8684a762b9cd7e4f66d62c6215e7b465de17c5b468ffcfeff5c14
Hashes to...
4db4ac98aa68d75dc3602f8f3b06157ac93485268df220cc6dc4aa39f6f9d7a9 Duplicate so 0413829417c3cc2db9c9890eb940b039afa6def6def9ec52e697b409eac5b414
a0337aef8e3739e6b705c51202a9d58addc375e2830e3429727a461052279d46 8%2=0 0413829417c3cc2db9c9890eb940b039afa6def6def9ec52e697b409eac5b414
0dc7b3bf9b1a98859d694146a0acd5a988d4184ab9c048ea91d8be7fd1cd84e6
72e15234eb42c9f4b650dec5727205dacbbcb039e8c22034b00bf805192abec7
14064970f7b3947cc046c094b4d0104f71d74fd74f6838734d201544cf47fff2
dca4db368d5241219a0f5f8c744c42293b9bc4959b99e4ed43abc075c284b78c
d2a927244dbb224cbcbe555a6670da39f5ed24296459723d5fe81ae17fd9279e
a5e67793f9193a7b9192e4c3e7cd27268ef354b0513a9cd595c04778d3fa3eef
7358ff53b3eaf7d249f725e9d5e999831eb9a787fafcc81a59697a3f68d4ea2e
4d53b64a343589f9b76643c80eacdd632cc50fcec6ece4dd7d3c0c65dba1d0f9
b6fae0b24b87c574c4732e507ff5ba5ff03c42a15c8b7da6a5b644e03efae9c1
3495a4fab0ff587f6050a22035e12253b250d088413dbd30b1cb44365b87bd86

Merkle Root Hashes to...

How SWEET! 14 % 2 = 0 a259dffe797877b1542f563e8a70c127c788245f7d8a88af05fda7f0d5290fef

7abfa52b7d99720b90bb50ee94a194ecf5de19c0095cd8e814443ad307f9245c65
fdb577a662d866e4f00a821684e9b0ea0c54299b6c7ce323dfcdffc4f79128

Hashes to...

python3 [Link]
ruby [Link]
52b7...5fdb 7abf...9128
java PrintMerkleizer
Merkle (C++)

b6fa...e9c1 7358...ea2e d2a9...279e 1406...fff2

0413...b414 Duplicate & 2bbd...5c14 56b7...4abf 932e...3d20 5191...1b55 dfc9...a331 fbde...404a

Self-hash

3495...bd86 4d53...d0f9 a5e6...3eef dca4...b78c 72e1...bec7 0dc7...84e6 a033...9d46 4db4...d7a9 cfce...7a50 ae22...7a70 51ef...975a a72e...1e43 e692...1f55 b5f6...2f3c
 Hashes to...
b5f60977102f95a9ed855b61acec86e2e434248b38c5f263ccf708a302832f3c fbde8de832fc532e8749ef8b6d7f4095ab51363a5176b4d68fee565ce6ec404a
e6922d44c520c52dca2cd5300784af55944c11839684e5c1671d9b330f871f55 dfc9d9c65c81b84d964a489673d3aa55a104fb8310cb2f012edf9e85a0e2a331
a72ef0e0240fb592dd1d6ec3d1ab24890def0870f5c44d478f1feb1f87701e43 519192022964a43a8f6083ca8a9db00d67240b6bc27527b98e161cbf61f61b55
51ef089bd2fc330cd02ee9d5a3cb5532ed48d8668ed78a92b84c8da97922975a 932e4b5b88444f9001279f3e6b9f8c9144b30194a47723f6ffe46e2c83433d20
ae22ea6889a5712eb2e13736ce4586afd310295c6ddbbc2b56b1305441017a70
56b79f789eb27436f176b9beea918d1d1538f6b7b4706fa33f499def2c7d4abf
cfce9664889e17fa006cfa23dd82852a999f9a748478cf325e3791241dd27a50
4db4ac98aa68d75dc3602f8f3b06157ac93485268df220cc6dc4aa39f6f9d7a9 2bbd8846e4e8684a762b9cd7e4f66d62c6215e7b465de17c5b468ffcfeff5c14
Hashes to...
a0337aef8e3739e6b705c51202a9d58addc375e2830e3429727a461052279d46 Duplicate so 0413829417c3cc2db9c9890eb940b039afa6def6def9ec52e697b409eac5b414
0dc7b3bf9b1a98859d694146a0acd5a988d4184ab9c048ea91d8be7fd1cd84e6 8%2=0 0413829417c3cc2db9c9890eb940b039afa6def6def9ec52e697b409eac5b414
72e15234eb42c9f4b650dec5727205dacbbcb039e8c22034b00bf805192abec7
dca4db368d5241219a0f5f8c744c42293b9bc4959b99e4ed43abc075c284b78c
a5e67793f9193a7b9192e4c3e7cd27268ef354b0513a9cd595c04778d3fa3eef 14064970f7b3947cc046c094b4d0104f71d74fd74f6838734d201544cf47fff2
4d53b64a343589f9b76643c80eacdd632cc50fcec6ece4dd7d3c0c65dba1d0f9 d2a927244dbb224cbcbe555a6670da39f5ed24296459723d5fe81ae17fd9279e
3495a4fab0ff587f6050a22035e12253b250d088413dbd30b1cb44365b87bd86 7358ff53b3eaf7d249f725e9d5e999831eb9a787fafcc81a59697a3f68d4ea2e
b6fae0b24b87c574c4732e507ff5ba5ff03c42a15c8b7da6a5b644e03efae9c1
Hashes to...
Merkle Root

Need How SWEET! 14 % 2 = 0 a259dffe797877b1542f563e8a70c127c788245f7d8a88af05fda7f0d5290fef

7abfa577a662d866e4f00a821684e9b0ea0c54299b6c7ce323dfcdffc4f79128
Hash 52b7d99720b90bb50ee94a194ecf5de19c0095cd8e814443ad307f9245c65fdb

Can Hashes to...

Calculate
Hash
52b7...5fdb
Validating Transactions in a Tree 7abf...9128
Hash to
Prove

b6fa...e9c1 7358...ea2e d2a9...279e 1406...fff2

0413...b414 Duplicate & 2bbd...5c14 56b7...4abf 932e...3d20 5191...1b55 dfc9...a331 fbde...404a

Self-hash

3495...bd86 4d53...d0f9 a5e6...3eef dca4...b78c 72e1...bec7 0dc7...84e6 a033...9d46 4db4...d7a9 cfce...7a50 ae22...7a70 51ef...975a a72e...1e43 e692...1f55 b5f6...2f3c
One Caveat: Host and Network Byte Ordering
• Different computer architectures store numbers differently:
• Little Endian architectures (like VAX, Intel) store the least significant byte first
• This means that within a (2-byte) word, the least significant byte is stored first, that
is, at the lowest byte address
• Big Endian architectures (like Sun Sparc, Motorola 68000, Apple PowerPC, and TCP
networks) store the most significant byte first
• This means that within a (2-byte) word, the most significant byte is stored first, that
is, at the lowest byte address
• This means that little-endian machines will need to convert IP addresses and port
numbers into big-endian form in order to communicate successfully
• Note that big-endian architectures don’t actually have to do anything, because they
already meet the specification
• Big Endian and Little Endian are terms taken from Jonathan Swift’s Gulliver’s Travels...
echo 12345678 | grep -o .. | tail –r | echo $(tr -d '\n')
• [Link]/lecture.4/byteorder/[Link] & [Link] (requires qemu + ppc image)
Why This Matters
• Bitcoin uses network byte order, or big-endian byte order, for internal
processing...mostly...
• Hashes are defined by the standards as being big-endian, and crypto libraries deal with
them in that form, and hashes are transmitted in big-endian
• Bitcoin displays hashes in little-endian because Bitcoin considers hashes to be little-
endian integers instead of strings
• Bitcoin stores transaction ids as big-endian
What’s To Be Done About It?
• Several C/C++ functions are provided to allow you to easily convert between host and network
byte ordering (of integers), and they are:
• To translate 32-bit numbers (i.e. IP addresses):
• unsigned long htonl(unsigned long hostlong);
• unsigned long ntohl(unsigned long netlong);
• To translate 16-bit numbers (i.e. Port numbers):
• unsigned short htons(unsigned short hostshort);
• unsigned short ntohs(unsigned short netshort);
• Python: hexlify and unhexlify, codecs encode/decode, etc.
• Ruby: reverse() and pack('H*’) and unpack('H*’), etc.
• Java folks may find this interesting: [Link]
integer-and-then-to-string-conversion-in-java
• In converting bitcoin data, you have to work on bytes, you can’t just reverse hexadecimal ASCII
strings of characters...
BLOCKS AND MORE BLOCKS
The Blockchain in Action
A Blockchain
• A blockchain is a list of blocks where each block references the previous block in the chain.
• Each block has an implicit height that indicates how far it is from the first block in the chain,
called the Genesis Block
• The Chain Tip is at the other end of the chain and is the current height of the blockchain
• Each block stores a list of transactions
• Blocks are averaging a little less than 1MB in size
• As of 1/1/2025, there have been over 870,000 total blocks mined on the bitcoin blockchain
Block Header

TX TX TX TX

First block in the The Chain Tip is

chain is the the last block in
Genesis Block the chain

{Height = 0} {Height = 1} {Height = 2} {Height = 3} {Height = 4} {Height = 5} {Height = 6} {Height = 7}

The Genesis Block
• The first block in the Bitcoin blockchain was mined (formally added to the blockchain) on
January 3, 2009, at 6:15 PM, UTC
• If you navigate back to the first block in the Bitcoin blockchain, you’ll arrive at the Genesis
Block, which has a height of 0
• The Genesis Block is actually hard-coded into the bitcoin core software in the file
[Link] (currently, it was in [Link] in the original source)
• Every node that joins the Bitcoin network (running bitcoind) knows the genesis block’s hash
and structure, its time of creation, and the single transaction it contains
• See it here: [Link] (enter block “0”)

0000000000000000
0000000000000000
0000000000000000
0000000000000000
4a5e1e4baab89f3a
32518a88c31bc87f
618f76673e2cc77a
b2127b7afdeda33b
2009-01-03 [Link]
1 N
2083236893
This was run
against Mainnet
...FYI

Txn
50 BTC “The Times 03/Jan/2009
4a5e1e4baab89f3a Chancellor on brink of
32518a88c31bc87f
618f76673e2cc77a
b2127b7afdeda33b
second bailout for banks”
The Genesis Block
• The first block in the Bitcoin blockchain was “mined” (formally added to the blockchain) on
January 3, 2009, as block 0
• In the Coinbase transaction, the input field (which can be virtually anything) contains a
reference to the London Times front page from January 3, 2009 (the Coinbase transaction
begins with “546865…”)
• This did two things simultaneously:
• It etched in the blockchain the date of the first mined transaction
• It served as a bit of a slam on a Central bank’s regulating of the money supply

0000000000000000
0000000000000000
0000000000000000
0000000000000000
4a5e1e4baab89f3a
32518a88c31bc87f
618f76673e2cc77a
b2127b7afdeda33b
2009-01-03 [Link]
1 N
2083236893

Txn
50 BTC “The Times 03/Jan/2009
4a5e1e4baab89f3a Chancellor on brink of
32518a88c31bc87f
618f76673e2cc77a
b2127b7afdeda33b
second bailout for banks”
Mainnet Block 1 Details
$ bitc-MAINNET getblockheader $(bitc-MAINNET getblockhash 1)
{
"hash": "00000000839a8e6886ab5951d76f411475428afc90947ee320161bbf18eb6048",
"confirmations": 529906,
"height": 1,
"version": 1,
"versionHex": "00000001",
"merkleroot":
"0e3e2357e806b6cdb1f70b54c3a3a17b6714ee1f0e68bebb44a74b1efd512098",
"time": 1231469665,
"mediantime": 1231469665,
"nonce": 2573394689,
... The previousblockhash of the second block points
"nTx": 1, to Block 0, the Genesis Block
"previousblockhash":
"000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f",
"nextblockhash":
"000000006a625f06636b8bb6ac7b960a8d03705d1ace08b1a19da3fdcc99ddbd"
}
Mainnet Block 0 Details
$ bitc-MAINNET getblockheader $(bitc-MAINNET getblockhash 0)
{
"hash": "000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f",
"confirmations": 530185,
"height": 0,
"version": 1,
"versionHex": "00000001",
"merkleroot":
"4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b",
"time": 1231006505,
"mediantime": 1231006505,
"nonce": 2083236893,
... The previousblockhash of the Genesis Block is MIA
"nTx": 1,
"nextblockhash":
"00000000839a8e6886ab5951d76f411475428afc90947ee320161bbf18eb6048"
}
Block Structure
Size in Bytes Header Field Description
4 Block Size The size of the block, in bytes, following this field
80 Block Header Metadata about this block
1-9 (variable) Transaction Counter How many transactions are in this block
Variable Transactions The actual transactions recorded in this block

Block Header

TX TX TX TX

First block in the The Chain Tip is

chain is the the last block in
Genesis Block the chain

{Height = 0} {Height = 1} {Height = 2} {Height = 3} {Height = 4} {Height = 5} {Height = 6} {Height = 7}

The Block Header
Size in Bytes Header Field Description
4 Version A version number to track software/protocol upgrades
32 Previous Block Hash A reference to the hash of the previous (parent) block in the chain
32 Merkle Root The hash of the root of the Merkle Tree of this block’s transactions
4 Timestamp The approximate creation time of this block (seconds from Unix Epoch)
4 Difficulty Target The Proof-of-Work algorithm difficulty target for this block
4 Nonce The counter used for the Proof-of-Work algorithm

Block Header

TX TX TX TX

First block in the The Chain Tip is

chain is the the last block in
Genesis Block the chain

{Height = 0} {Height = 1} {Height = 2} {Height = 3} {Height = 4} {Height = 5} {Height = 6} {Height = 7}

Block Referencing
• A block can be referenced in two ways:
• By referencing the block hash or by referencing the block height
• Each block that is added on top of a given block is one position higher in the
chain
• It is possible that at any given time (such as a fork competition), two blocks might
temporarily have the same height, but this discrepancy will eventually be resolved by
the system in time
• Note that neither the block’s hash nor its height is actually stored in the block,
software and sites such as [Link] calculate it for our convenience
• The genesis block’s timestamp is 2009-01-03 [Link]
• It can be viewed via [Link]:
[Link]
Block-Block Linkage
• The Block Header contains important information about the block, including:
• The Previous Block’s Header Hash
• The Merkle Root Hash
• The Timestamp for the block
• The Target Value Later!
• The Nonce
• Each block contains a double SHA-256 hash of the previous block’s header, and this becomes the
current block’s Header ID, more accurately the block header hash
• Signing the header block hash pointer effectively signs the entire block structure...
Double SHA-256 Hash

Previous Block’s Header

Target
Timestamp Nonce
Miner’s
Digital
Signature
 Block Header Detail
• The Block Header contains important metadata about the block, including:
• Linkage to the previous block
• The Merkle Root
• Mining Information

Field Description Size

Version A version number to track protocol upgrades 4 bytes
Previous Block Hash A reference to the hash of the previous block’s header 32 bytes
A hash of the root of the Merkle tree of this block’s
Merkle Root 32 bytes
transactions
The approximate creation time of this block (in seconds from
Timestamp 4 bytes
Unix Epoch January 1, 1970)
Mining!

Difficulty Target The Proof-of-Work algorithm difficulty target for this block 4 bytes
The number used by the Proof-of-Work algorithm that
Nonce 4 bytes
successfully solved this block’s mining puzzle
The Blockchain in More Detail
• The Block Header

Double
SHA-
256
Hash
Blocks in the blockchain
Block Root Hash of all the
creation Reference to Previous Block Transactions in this block
time

Block First Txn in Block Block Block

block is always a
height height height height
Coinbase Txn
5096 (Later!) 5097 5098 5099

Timed Growth of Blockchain

Block Header Details
$ bitc getblockheader
{
"hash" : "hash", (string) the block hash (same as provided)
"confirmations": (numeric) The number of confirmations, or -1 if the block is not
on the main chain
"height": (numeric) The block height or index
"version": (numeric) The block version
"versionHex": (string) The block version formatted in hexadecimal
"merkleroot": (string) The merkle root
"time": (numeric) The block time in seconds since epoch (Jan 1 1970 GMT)
"mediantime": (numeric) The median block time in seconds since epoch (1/1/70)
"nonce": (numeric) The nonce
"bits": (string) The bits
"difficulty" (numeric) The difficulty
"chainwork": (string) Expected number of hashes required to produce the
current chain (in hex)
"previousblockhash": (string) The hash of the previous block
"nextblockhash": (string) The hash of the next block
}
Mainnet Block 2 Details
$ bitc-MAINNET getblockheader $(bitc-MAINNET getblockhash 2)
{
"hash": "000000006a625f06636b8bb6ac7b960a8d03705d1ace08b1a19da3fdcc99ddbd",
"confirmations": 530623,
"height": 2,
"version": 1,
"versionHex": "00000001",
"merkleroot": "9b0fc92260312ce44e74ef369f5c66bbb85848f2eddd5a7a1cde251e54ccfdd5",
"time": 1231469744,
"mediantime": 1231469665,
"nonce": 1639830024,
"bits": "1d00ffff",
"difficulty": 1,
"chainwork": "0000000000000000000000000000000000000000000000000000000300030003",
"previousblockhash": "00000000839a8e6886ab5951d76f411475428afc90947ee320161bbf18eb6048",
"nextblockhash": "0000000082b5015589a3fdf2d4baff403e6f0be035a5d9742c1cae6295464449"
}
• Example:
[Link]
• Example: [Link]/lecture.4/[Link]/[Link] (Review Code! and use python version 3.6.15)
Testnet Block 1324789 Details
$ bitc getblockheader $(bitc getblockhash 1324789)
{
"hash": "000000000000004fbc510b95ba2366576879aad7f018b20bf8532267182cb7d1",
"confirmations": 163249,
"height": 1324789,
"version": 536870912,
"versionHex": "20000000",
"merkleroot": "a259dffe797877b1542f563e8a70c127c788245f7d8a88af05fda7f0d5290fef",
"time": 1528549673,
"mediantime": 1528547887,
"nonce": 4119827990,
"bits": "195aec00",
"difficulty": 47237276.6179756,
"chainwork": "00000000000000000000000000000000000000000000004adceab492086ed03c",
"previousblockhash":
"000000000000004950205cca66572178be57a990f58b9a6741ad683a36c9a46e",
"nextblockhash": "0000000000000037d75561c013e8b7ab882dc1f0f226dc060f0c42fefff80ebc"
}
• Example: [Link]
• Example: [Link]/lecture.4/[Link]/[Link]