Safe Haskell | Safe-Inferred |
---|---|

Language | GHC2021 |

A purely functional implementation of MerkleTrees that is suitable for
usage on-chain. Note however that the construction of `MerkleTree`

and
membership proofs are still expected to happen *off-chain* while only the
proof verification should be done on-chain.

Note that this module is meant to used as a qualified import, for example:

import qualified Plutus.MerkleTree as MT

## Synopsis

- data MerkleTree
- = MerkleEmpty
- | MerkleNode Hash MerkleTree MerkleTree
- | MerkleLeaf Hash BuiltinByteString

- fromList :: [BuiltinByteString] -> MerkleTree
- toList :: MerkleTree -> [BuiltinByteString]
- rootHash :: MerkleTree -> Hash
- null :: MerkleTree -> Bool
- size :: MerkleTree -> Integer
- type Proof = [Either Hash Hash]
- mkProof :: BuiltinByteString -> MerkleTree -> Maybe Proof
- member :: BuiltinByteString -> Hash -> Proof -> Bool
- newtype Hash = Hash BuiltinByteString
- hash :: BuiltinByteString -> Hash
- combineHash :: Hash -> Hash -> Hash

# MerkleTree

data MerkleTree Source #

A MerkleTree representation, suitable for on-chain manipulation.
Construction of the merkle tree shouldn't be done by hand, but via
`fromList`

.

MerkleEmpty | |

MerkleNode Hash MerkleTree MerkleTree | |

MerkleLeaf Hash BuiltinByteString |

#### Instances

Show MerkleTree Source # | |

Defined in Plutus.MerkleTree | |

Eq MerkleTree Source # | |

Defined in Plutus.MerkleTree (==) :: MerkleTree -> MerkleTree -> Bool Source # (/=) :: MerkleTree -> MerkleTree -> Bool Source # | |

Eq MerkleTree Source # | |

Defined in Plutus.MerkleTree (==) :: MerkleTree -> MerkleTree -> Bool |

fromList :: [BuiltinByteString] -> MerkleTree Source #

Construct a `MerkleTree`

from a list of serialized data as
`BuiltinByteString`

.

Note that, while this operation is doable on-chain, it is expensive and preferably done off-chain.

toList :: MerkleTree -> [BuiltinByteString] Source #

Deconstruct a `MerkleTree`

back to a list of elements.

`>>>`

True`toList (fromList xs) == xs`

rootHash :: MerkleTree -> Hash Source #

Obtain the root hash of a `MerkleTree`

. In particular we have:

`>>>`

True`(mt == mt') == (rootHash mt == rootHash mt')`

null :: MerkleTree -> Bool Source #

Return true if the `MerkleTree`

is empty.

`>>>`

True`null mt == (size mt == 0)`

size :: MerkleTree -> Integer Source #

Total numbers of leaves in the tree.

# Proof

mkProof :: BuiltinByteString -> MerkleTree -> Maybe Proof Source #

Construct a membership `Proof`

from an element and a `MerkleTree`

. Returns
`Nothing`

if the element isn't a member of the tree to begin with.

member :: BuiltinByteString -> Hash -> Proof -> Bool Source #

Check whether a element is part of a `MerkleTree`

using only its root hash
and a `Proof`

. The proof is guaranteed to be in log(n) of the size of the
tree, which is why we are interested in such data-structure in the first
place.

# Hash

A type for representing hash digests.

Hash BuiltinByteString |

#### Instances

Show Hash Source # | |

Eq Hash Source # | |

Eq Hash Source # | |

Defined in Plutus.MerkleTree | |

FromData Hash Source # | |

Defined in Plutus.MerkleTree fromBuiltinData :: BuiltinData -> Maybe Hash | |

ToData Hash Source # | |

Defined in Plutus.MerkleTree toBuiltinData :: Hash -> BuiltinData | |

UnsafeFromData Hash Source # | |

Defined in Plutus.MerkleTree unsafeFromBuiltinData :: BuiltinData -> Hash |