| Safe Haskell | Safe-Inferred |
|---|---|
| Language | GHC2021 |
Plutus.MerkleTree
Contents
Description
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.
Constructors
| MerkleEmpty | |
| MerkleNode Hash MerkleTree MerkleTree | |
| MerkleLeaf Hash BuiltinByteString |
Instances
| Show MerkleTree Source # | |
Defined in Plutus.MerkleTree | |
| Eq MerkleTree Source # | |
Defined in Plutus.MerkleTree Methods (==) :: MerkleTree -> MerkleTree -> Bool Source # (/=) :: MerkleTree -> MerkleTree -> Bool Source # | |
| Eq MerkleTree Source # | |
Defined in Plutus.MerkleTree Methods (==) :: 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.
>>>toList (fromList xs) == xsTrue
rootHash :: MerkleTree -> Hash Source #
Obtain the root hash of a MerkleTree. In particular we have:
>>>(mt == mt') == (rootHash mt == rootHash mt')True
null :: MerkleTree -> Bool Source #
Return true if the MerkleTree is empty.
>>>null mt == (size mt == 0)True
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.
Constructors
| Hash BuiltinByteString |
Instances
| Show Hash Source # | |
| Eq Hash Source # | |
| Eq Hash Source # | |
Defined in Plutus.MerkleTree | |
| FromData Hash Source # | |
Defined in Plutus.MerkleTree Methods fromBuiltinData :: BuiltinData -> Maybe Hash | |
| ToData Hash Source # | |
Defined in Plutus.MerkleTree Methods toBuiltinData :: Hash -> BuiltinData | |
| UnsafeFromData Hash Source # | |
Defined in Plutus.MerkleTree Methods unsafeFromBuiltinData :: BuiltinData -> Hash | |