Merkle tree
Overview
A Merkle tree (or hash tree) is a (normally perfect binary) tree in which all nodes are labelled with a hash.
There is a data block attached to each leaf, and the hash label is the hash of the data.
For other nodes, the hash label is the hash of the concatenation of its child hashes.
Merkle trees allow efficient and secure verification of the contents of large data structures
In Bitcoin, each block contains a Merkle tree of all included transactions.
If there is an odd number of transactions or of nodes on a higher level, the last hash is duplicated.
A Simplified Payment Node (SPN) does not save all transaction, but only the Merkle root, the hash labelling the Merkle tree root.
A full node can prove to an SPN that a given transaction is in the block by providing a Merkle path.
https://gyazo.com/6698c0397f494d118a21d99b4df1e9a1
If one want to verify H(Y[i=2]), then the Merkle path is auth[0], auth[1], auth[2]
Code
Implementation of Merkle tree
code:core.hs
import Data.Binary (Binary, encode)
import Data.ByteString.Lazy (append)
import Data.List.NonEmpty
import Merkle.Hash
data MerkleTree a =
Leaf Hash a
| Node Int Hash (MerkleTree a) (MerkleTree a)
| Partial Int Hash (MerkleTree a)
deriving Show
height :: MerkleTree a -> Int
height (Leaf _ _) = 0
height (Node n _ _ _) = n
height (Partial n _ _) = n
treeHash :: MerkleTree a -> Hash
treeHash (Leaf h _) = h
treeHash (Node _ h _ _ ) = h
treeHash (Partial _ h _) = h
leaf :: Binary a => a -> MerkleTree a
leaf a = Leaf (hash $ encode a) a
node :: MerkleTree a -> MerkleTree a -> MerkleTree a
node l r =
let n = 1 + max (height l) (height r)
h = hash $ hashToByteString (treeHash l) append hashToByteString (treeHash r)
in Node n h l r
partial :: MerkleTree a -> MerkleTree a
partial l =
let n = 1 + height l
bs = hashToByteString $ treeHash l
h = hash $ bs append bs
in Partial n h l
construct :: Binary a => NonEmpty a -> MerkleTree a
construct = go . fmap leaf
where
go :: NonEmpty (MerkleTree a) -> MerkleTree a
go (t :| []) = t
go (l :| r : ts) = go $ node l r :| step ts
step [] = []
step (l : r : ts) = node l r : step ts
code:path.hs
module Merkle.Path
( MerklePath (..)
, merklePath
, checkPath
) where
import Data.Binary (Binary, encode)
import Data.ByteString.Lazy (append)
import Data.List (foldl')
import Merkle.Core
import Merkle.Hash
deriving Show
merklePath :: MerkleTree a -> Int -> Maybe (MerklePath a)
merklePath (Leaf _ a) i
| i == 0 = Just $ MerklePath a []
| otherwise = Nothing
merklePath (Node n _ l r) i
| i < 2^(n-1) = do
MerklePath a ps <- merklePath l i
return $ MerklePath a $ Right (treeHash r) : ps
| otherwise = do
MerklePath a ps <- merklePath r (i - 2^(n-1))
return $ MerklePath a $ Left (treeHash l) : ps
merklePath (Partial n _ l) i
| i < 2^(n-1) = do
MerklePath a ps <- merklePath l i
return $ MerklePath a $ Right (treeHash l) : ps
| otherwise = Nothing
checkPath :: Binary a => MerklePath a -> Hash
checkPath (MerklePath a ps) = go $ reverse ps
where
go = foldl' f $ hash $ encode a
f :: Hash -> Either Hash Hash -> Hash
f h (Left l) = hash $ hashToByteString l append hashToByteString h
f h (Right r) = hash $ hashToByteString h append hashToByteString r