Lecture 04: Hash Pointers and Data Structures
Lecture 04
Hash Pointers and Data
Structures
Lecture 04: Hash Pointers and Data Structures
hash pointer is:
* pointer to where some info is stored, and
* (cryptographic) hash of the info
if we have a hash pointer, we can
* ask to get the info back, and
* verify that it hasn’t changed
Lecture 04: Hash Pointers and Data Structures
H( )
(data) will draw hash
pointers like this
Lecture 04: Hash Pointers and Data Structures
key idea:
build data structures with hash pointers
Lecture 04: Hash Pointers and Data Structures
linked list with hash pointers = “block chain”
H( )
prev: H( ) prev: H( ) prev: H( )
data data data
use case: tamper-evident log
Lecture 04: Hash Pointers and Data Structures
linked list with hash pointers = “block chain”
each block not only tells us where the value of the
previous block was, but it also contains a digest of that
value that allows us to verify that the value hasn’t
changed.
Lecture 04: Hash Pointers and Data Structures
detecting tampering
use case: tamper-evident log
• An attacker wants to tamper with one block of the chain, let’s say,
block 1.
• The attacker changed the content of block 1, because of “collision
free” property of the hash function, he is not able to find another
data which has the same hash with the old one. So now the hash
of this modified block is also changed.
Lecture 04: Hash Pointers and Data Structures
detecting tampering
use case: tamper-evident log
• To avoid others noticing the inconsistency, he also needs to
change the hash pointer of that block in the next block, which is
block 2.
• Now the content of block 2 is changed, so to make this story
consistent, the hash pointer in block3 must be changed.
• Finally, the attacker goes to the hash pointer to the last block of
the blockchain, which is a roadblock for him, because we keep
and remember that hash pointer.
Lecture 04: Hash Pointers and Data Structures
binary tree with hash pointers = “Merkle tree”
H( )
H( )
H( ) H( )
H( ) H( )
H( ) H( ) H( ) H( )
H( ) H( ) H( ) H( )
(data) (data) (data) (data) (data) (data) (data) (data)
Lecture 04: Hash Pointers and Data Structures
binary tree with hash pointers = “Merkle
tree”
• 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, providing a
very efficient process to verify whether a transaction is
included in a block.
• The merkle tree is constructed bottom-up. In the
following example, we start with four transactions, A, B,
C, and D, which form the leaves of the merkle tree, as
shown in the Figure.
• The transactions are not stored in the merkle tree;
rather, their data is hashed and the resulting hash is
stored in each leaf node as HA, HB, HC, and HD:
HA = SHA256(SHA256(Transaction A))
Lecture 04: Hash Pointers and Data Structures
binary tree with hash pointers = “Merkle tree”
Lecture 04: Hash Pointers and Data Structures
• Because the merkle tree is a binary tree, it needs an
even number of leaf nodes. If there is an odd number of
transactions to summarize, the last transaction hash will
be duplicated to create an even number of leaf nodes,
also known as a balanced tree.
Lecture 04: Hash Pointers and Data Structures
Why they are used?
• They serve many purposes,
○ They can be used to verify membership in O(log n)
time/space
○ Membership of transaction in a block !!
○ We can use something called a “Merkle proof” to
show that some content is part of this tree. For
example, let’s prove that A is part of the above tree.
All we need to do is provide each of A’s siblings on
the way up, recompute the tree, and make sure
everything matches.
Lecture 04: Hash Pointers and Data Structures
Example
• Is transaction K part of the tree?
Lecture 04: Hash Pointers and Data Structures
Where they are used?
Lecture 04: Hash Pointers and Data Structures
Where they are used?
• A light client may need fewer details.
• Can verify membership in O(log n) time/space
Lecture 04: Hash Pointers and Data Structures
Simplified Payment
Verification
• It should be possible to verify that a certain
transaction has happened
• The node thus needs to access the blockchain
and may need a full local copy
• This is a lot to do!! Is it possible to verify bitcoin
payments without running a full network node?
Lecture 04: Hash Pointers and Data Structures
Transaction verification
• What is needed to verify that a transaction has
happened?
○ It must be included in a block which must be
in the longest chain (not orphan)
○ The block must have valid chain of previous
blocks back to the genesis block
• How to do that on a regular node?
Lecture 04: Hash Pointers and Data Structures
Merkle Trees in Bitcoin
Lecture 04: Hash Pointers and Data Structures
Simplified Transaction
Verification
• How merkle trees can help?
○ The size of block header is small as
they only contain merkle root.
○ For a block header size of 80 bytes
(like Bitcoin) it requires blockheight * 80
bytes. At height 530361 it requires 40
Megabytes.
Lecture 04: Hash Pointers and Data Structures
Simplified Transaction
Verification
• How merkle trees can help for verifying
transaction inclusion in a block?
○ We do not need to have all the hashes.
○ The merkle proof will always consist of one
hash for every step up the tree.
○ A block of 16 transactions would require 4
hashes
○ For 1000 transactions – 10 hashes. Average
is more than 2500 transaction these days!
Lecture 04: Hash Pointers and Data Structures
Do not distribute ...
• These slides are not always prepared by me.
• Most of the content comes from the reference book
– Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction
– Arvind Narayanan, Joseph Bonneau,
– Edward Felten, Andrew Miller, Steven Goldfeder
