Crypto.Hash.CompactSparseMerkleTree

Compact Sparse Merkle Trees

The CompactSparseMerkleTree i alg a type represents a merkle tree of size i containing elements of type a authenticated with a secure cryptographic hash function alg. This allows for the novel generation and verification of memory efficient cryptographic zero-knowledge proofs of inclusion and exclusion of elements in the tree. Most operations require that a be an instance of the ByteArrayAccess class and alg be an instance of the HashAlgorithm class.

This module is intended to be imported qualified:

 import Crypto.Hash.CompactSparseMerkleTree (CSMT)
 import qualified Crypto.Hash.CompactSparseMerkleTree as CSMT

Warning

The size of the tree obviously cannot exceed the size of the image of the hash algorithm 2^(8 * hashDigestSize alg). The word length of the hash digest for the algorithm must not exceed maxBound :: Int. Violation of these limits are not detected and a breach implies undefined behaviour.

Implementation

The implementation of CompactSparseMerkleTree is based on compact sparse merkle trees as described by:

• Faraz Haider. "Compact sparse merkle trees.", Cryptology ePrint Archive, October 2018, https://eprint.iacr.org/2018/955.

Asymptotic bounds for the average case time complexity are given with the assumption that the supplied hash function acts as a random oracle under the random oracle model and that the compact sparse merkle tree is valid. In practice, the probability that the observed complexity differs from the average case is vanishingly small.

Additionally, this implementation enforces domain separation for the inputs to the hash algorithm alg to provide the proofs with resistance to second preimage attacks. Inputs to hashes for leaf and parent nodes are prefixed with the bytes 0x00 and 0x01 respectively before applying the hash algorithm.

CompactSparseMerkleTree Type

type CSMT = CompactSparseMerkleTree

A compact sparse merkle tree of size i with values a authenticated over the algorithm alg.

data CompactSparseMerkleTree (i :: Size) alg a where

A compact sparse merkle tree of size i with values a authenticated over the algorithm alg.

Constructors

Nil :: CSMT 'Empty alg a

The empty tree.

Leaf

A leaf node.

Fields

• :: { digest :: Digest alg

  The hash digest of the data element.

•    , value :: a

  The data value.

•    } -> CSMT 'NonEmpty alg a

Parent

A parent node.

Fields

• :: { left :: CSMT 'NonEmpty alg a

  The left non-empty subtree.

•    , digest :: Digest alg

  The hash digest of the data element.

•    , maxDigest :: Digest alg

  The maximum digest in the tree.

•    , right :: CSMT 'NonEmpty alg a

  The right non-empty subtree.

•    } -> CSMT 'NonEmpty alg a

Instances

Foldable (CSMT i alg)

Defined in Crypto.Hash.CompactSparseMerkleTree

Methods

fold :: Monoid m => CSMT i alg m -> m

foldMap :: Monoid m => (a -> m) -> CSMT i alg a -> m

foldMap' :: Monoid m => (a -> m) -> CSMT i alg a -> m

foldr :: (a -> b -> b) -> b -> CSMT i alg a -> b

foldr' :: (a -> b -> b) -> b -> CSMT i alg a -> b

foldl :: (b -> a -> b) -> b -> CSMT i alg a -> b

foldl' :: (b -> a -> b) -> b -> CSMT i alg a -> b

foldr1 :: (a -> a -> a) -> CSMT i alg a -> a

foldl1 :: (a -> a -> a) -> CSMT i alg a -> a

toList :: CSMT i alg a -> [a]

null :: CSMT i alg a -> Bool

length :: CSMT i alg a -> Int

elem :: Eq a => a -> CSMT i alg a -> Bool

maximum :: Ord a => CSMT i alg a -> a

minimum :: Ord a => CSMT i alg a -> a

sum :: Num a => CSMT i alg a -> a

product :: Num a => CSMT i alg a -> a

Eq1 (CSMT i alg)

Defined in Crypto.Hash.CompactSparseMerkleTree

Methods

liftEq :: (a -> b -> Bool) -> CSMT i alg a -> CSMT i alg b -> Bool

Ord1 (CSMT i alg)

Defined in Crypto.Hash.CompactSparseMerkleTree

Methods

liftCompare :: (a -> b -> Ordering) -> CSMT i alg a -> CSMT i alg b -> Ordering

Eq a => Eq (CSMT i alg a)

Defined in Crypto.Hash.CompactSparseMerkleTree

Methods

(==) :: CSMT i alg a -> CSMT i alg a -> Bool

(/=) :: CSMT i alg a -> CSMT i alg a -> Bool

Ord a => Ord (CSMT i alg a)

Defined in Crypto.Hash.CompactSparseMerkleTree

Methods

compare :: CSMT i alg a -> CSMT i alg a -> Ordering

(<) :: CSMT i alg a -> CSMT i alg a -> Bool

(<=) :: CSMT i alg a -> CSMT i alg a -> Bool

(>) :: CSMT i alg a -> CSMT i alg a -> Bool

(>=) :: CSMT i alg a -> CSMT i alg a -> Bool

max :: CSMT i alg a -> CSMT i alg a -> CSMT i alg a

min :: CSMT i alg a -> CSMT i alg a -> CSMT i alg a

Show a => Show (CSMT i alg a)

Defined in Crypto.Hash.CompactSparseMerkleTree

Methods

showsPrec :: Int -> CSMT i alg a -> ShowS

show :: CSMT i alg a -> String

showList :: [CSMT i alg a] -> ShowS

data Size

The size of a compact sparse merkle tree.

Constructors

Empty

The empty tree

NonEmpty

A non-empty tree

Construction

empty :: CSMT 'Empty alg a

The empty tree.

Worst case Θ(1).

singleton :: (ByteArrayAccess a, HashAlgorithm alg) => a -> CSMT 'NonEmpty alg a

Create a singleton tree.

Worst case Θ(1).

fromList :: (ByteArrayAccess a, HashAlgorithm alg) => NonEmpty a -> CSMT 'NonEmpty alg a

Create a tree from a list of elements.

Average case Θ(n*log n), Worst case Θ(n²) where n is the size of the tree.

Insertion

insert :: (ByteArrayAccess a, HashAlgorithm alg) => a -> CSMT i alg a -> CSMT 'NonEmpty alg a

Insert an element in a tree. If the tree already contains an element whose hash is equal to the given value, it is replaced with the new value.

Average case Θ(log n), Worst case Θ(n) where n is the size of the tree.

Deletion

delete :: (ByteArrayAccess a, HashAlgorithm alg) => a -> CSMT i alg a -> (forall j. CSMT j alg a -> b) -> b

Delete an element from a tree if such an element exists.

Average case Θ(log n), Worst case Θ(n) where n is the size of the tree.

Query

lookup :: Digest alg -> CSMT i alg a -> Maybe a

Lookup the value with the digest in the map.

Average case Θ(log n), Worst case Θ(n) where n is the size of the tree.

member :: (ByteArrayAccess a, HashAlgorithm alg) => a -> CSMT i alg a -> Bool

Is the element in the tree?

Average case Θ(log n), Worst case Θ(n) where n is the size of the tree.

notMember :: (ByteArrayAccess a, HashAlgorithm alg) => a -> CSMT i alg a -> Bool

Is the element not in the tree?

Average case Θ(log n), Worst case Θ(n) where n is the size of the tree.

Min/Max

minimumDigest :: CSMT 'NonEmpty alg a -> Digest alg

The minimum digest in the tree.

Average case Θ(log n), Worst case Θ(n) where n is the size of the tree.

maximumDigest :: CSMT 'NonEmpty alg a -> Digest alg

The maximum digest in the tree.

Worst case Θ(1).

Proofs

data MembershipProof alg

A membership proof over a hash algorithm alg.

Constructors

forall p. MembershipProof (Proof Direction p alg)

Instances

Show (MembershipProof alg)

Defined in Crypto.Hash.CompactSparseMerkleTree

Methods

showsPrec :: Int -> MembershipProof alg -> ShowS

show :: MembershipProof alg -> String

showList :: [MembershipProof alg] -> ShowS

data Proof d (p :: ProofType) alg where

A proof of p with direction d over a hash algorithm alg.

Constructors

InclusionProof

A proof of inclusion.

Fields

• :: { includedDigest :: Digest alg

  A digest of an included element.

•    , rootPath :: [(Digest alg, d)]

  A list of sibling digests from the root to the included element with the directions from their parents.

•    } -> Proof d 'Inclusion alg

ExclusionProof

A proof of exclusion.

Fields

• :: { excludedDigest :: Digest alg

  The digest of an excluded element.

•    , immediatePredecessor :: Maybe (Proof () 'Inclusion alg)

  A uni-directional inclusion proof from the left of the immediate predecessor to the included element, if one exists.

•    , immediateSuccessor :: Maybe (Proof () 'Inclusion alg)

  A uni-directional inclusion proof from the right of the immediate successor to the included element, if one exists.

•    , commonRootPath :: [(Digest alg, d)]

  A list of sibling digests from the root to the first common sibling of the immediate predecessor and successors with the directions from their parents.

•    } -> Proof d 'Exclusion alg

Instances

Show d => Show (Proof d alg p)

Defined in Crypto.Hash.CompactSparseMerkleTree

Methods

showsPrec :: Int -> Proof d alg p -> ShowS

show :: Proof d alg p -> String

showList :: [Proof d alg p] -> ShowS

data Direction

A direction of a node from its parent.

Constructors

L

A left node

R

A right node

Instances

Eq Direction

Defined in Crypto.Hash.CompactSparseMerkleTree

Methods

(==) :: Direction -> Direction -> Bool

(/=) :: Direction -> Direction -> Bool

Show Direction

Defined in Crypto.Hash.CompactSparseMerkleTree

Methods

showsPrec :: Int -> Direction -> ShowS

show :: Direction -> String

showList :: [Direction] -> ShowS

data ProofType

A type of proof

Constructors

Inclusion

A proof that an element is in a tree.

Exclusion

A proof that an element is not in a tree.

isInclusionProof :: MembershipProof alg -> Bool

Is this an inclusion proof?

Worst case Θ(1).

isExclusionProof :: MembershipProof alg -> Bool

Is this an exclusion proof?

Worst case Θ(1).

Proof construction

membershipProof :: (ByteArrayAccess a, HashAlgorithm alg) => a -> CSMT i alg a -> MembershipProof alg

Construct a membership proof of inclusion if the given element is in the tree, or a proof of exclusion if the element is not in the tree.

Average case Θ(log n), Worst case Θ(n) where n is the size of the tree. The constructed membership proof has equivalent space complexity.

Proof verification

data MerkleRoot alg

A merkle root of a tree.

Constructors

EmptyMerkleRoot

A merkle root of an empty tree.

MerkleRoot (Digest alg)

A merkle root of a non-empty tree.

Instances

Eq (MerkleRoot alg)

Defined in Crypto.Hash.CompactSparseMerkleTree

Methods

(==) :: MerkleRoot alg -> MerkleRoot alg -> Bool

(/=) :: MerkleRoot alg -> MerkleRoot alg -> Bool

Show (MerkleRoot alg)

Defined in Crypto.Hash.CompactSparseMerkleTree

Methods

showsPrec :: Int -> MerkleRoot alg -> ShowS

show :: MerkleRoot alg -> String

showList :: [MerkleRoot alg] -> ShowS

merkleRoot :: CSMT i alg a -> MerkleRoot alg

The merkle root of a tree.

Worst case Θ(1).

validProof :: HashAlgorithm alg => MerkleRoot alg -> MembershipProof alg -> Bool

Validate a membership proof against a merkle root.

Worst case Θ(d) where d is the number of hash digests in the membership proof.

validInclusionProof :: HashAlgorithm alg => MerkleRoot alg -> Proof Direction 'Inclusion alg -> Bool

Validate an inclusion proof against a merkle root.

Worst case Θ(d) where d is the number of hash digests in the inclusion proof.

validExclusionProof :: HashAlgorithm alg => MerkleRoot alg -> Proof Direction 'Exclusion alg -> Bool

Validate an exclusion proof against a merkle root.

Worst case Θ(d) where d is the number of hash digests in the exclusion proof.

valid :: (ByteArrayAccess a, HashAlgorithm alg) => CSMT i alg a -> Bool

Validate a tree against the properties of a compact sparse merkle tree. Namely that:

• the maximum leaf digests for all subtrees are valid
• the leaf hash digests are valid
• and all leafs lie on its minimum distance path from the root.

All exported functions maintain these properties.

Average case Θ(n*log n), Worst case Θ(n²) where n is the size of the tree.

Debugging

depth :: (Num n, Ord n) => CSMT i alg a -> n

The depth of a tree.

Average case Θ(n), Worst case Θ(n) where n is the size of the tree.

toTree :: CSMT i alg a -> Maybe (Tree (DataNode alg a))

Convert a tree to a rose tree with non-recursive nodes as elements. Used for debugging purposes.

Average case Θ(n), Worst case Θ(n) where n is the size of the tree.

drawTree :: Show a => CSMT i alg a -> String

2-dimensional ASCII drawing of the tree. Used for debugging purposes.

Average case Θ(n²), Worst case Θ(n²) where n is the size of the tree.