Scribd
Upload
55 views17 pages

Blockchain Hashing and Data Structures

This document discusses hash pointers and data structures that use hash pointers to provide tamper resistance. It explains that hash pointers can verify that data has not been modified by comparing the hash to the stored hash pointer. Structures like linked lists and Merkle trees are discussed as examples where replacing regular pointers with hash pointers results in tamper-resistant versions of the structures. The Merkle tree structure is particularly important for Bitcoin as it allows efficient verification of all transactions in a block.

Uploaded by

begat651
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
55 views17 pages

Blockchain Hashing and Data Structures

This document discusses hash pointers and data structures that use hash pointers to provide tamper resistance. It explains that hash pointers can verify that data has not been modified by comparing the hash to the stored hash pointer. Structures like linked lists and Merkle trees are discussed as examples where replacing regular pointers with hash pointers results in tamper-resistant versions of the structures. The Merkle tree structure is particularly important for Bitcoin as it allows efficient verification of all transactions in a block.

Uploaded by

begat651
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 17

BLOCKCHAIN

Hashing in depth

Pr. TMIMI Mehdi

Inspired from Web3 Foundation course


Discuss :
• Hash pointers Main goal
• Some Data Structures for blockchain

inspired from Web3 Foundation course


Hash Pointer

Hash Pointer

Cryptographic
Pointer to some hash of that data
object or data set or representation
of that object

inspired from Web3 Foundation course


Regular pointers can tell you
where data is located.

Why use ?
Hash pointers tell
you that, plus let you verify that
it has not been modified.
inspired from Web3 Foundation course
Hash Pointer

SHA-256 of 'Allah is the greatest' matches the hash pointer => All is well

NB: If there is no match between the hashes => the data has been accidentally or
maliciously modified, or it may just be data corruption

inspired from Web3 Foundation course


Many Data structures which use
pointers/references can have their
pointers/references replaced with hash
pointers.
Data structures
with hash
pointers
This makes them tamper-resistant versions
of the 'classic' data structures

inspired from Web3 Foundation course


Linked List
with Hash
Pointers Head of the list

If we replace those pointers


with hash pointers => a
basic blockchain
NB: adding the data is
always on the head of the
list

inspired from Web3 Foundation course


Temper-resistant
Head of the list

=> Hash pointer of previous


data in the node includes
both its data and the hash
of the preceding node.

inspired from Web3 Foundation course


Temper-resistant
Head of the list

- Strikethrough = modified
data
- Green = valid hash pointer
- Red = invalid hash pointer

inspired from Web3 Foundation course


Merkle root
Binary Tree with
Hash Pointers

Merkle Tree:
- It's a binary tree.
- Replace pointers with hash
pointers.
- Store data only in the
leaves (it is not quite represented
in the figure)

inspired from Web3 Foundation course


Example:

Example: using a hash function


that only will return a 256 bits
hash value

inspired from Web3 Foundation course


Memberships

Proving and Disproving


membership in O(log n) time.
=> this requires sorted Merkle
tree.
=> more efficient (less
complexity) than searching in
linked list

inspired from Web3 Foundation course


• Good access time.
Why Merkle • Can just store Merkle root to verify the entire tree.
Tree • Verify membership/ non-membership for sorted
Merkle trees in O(log n) times

inspired from Web3 Foundation course


• The Merkle root in a block is the Merkle root of all
transactions in that block.
Bitcoin & Merkle • Allows mining to be approximately equally
Tree difficult no matter how many transactions are
included. => incentivize miners to add
more transactions, so they get transaction fees.

inspired from Web3 Foundation course


Example
inspired from Web3 Foundation course
• Data Structures without explicit pointers: like
Where can't we Arrays.
use Hash Pointers • Data structures which can includes cycles => there
is no starting points for hashes

inspired from Web3 Foundation course


BLOCKCHAIN
Hashing in depth

Pr. TMIMI Mehdi

Inspired from Web3 Foundation course

You might also like