| Copyright | Copyright © 2019 Kadena LLC. |
|---|---|
| License | MIT |
| Maintainer | Lars Kuhtz <lars@kadena.io> |
| Stability | experimental |
| Safe Haskell | None |
| Language | Haskell2010 |
Data.MerkleLog
Description
Merkle Logs are a append-only data structure. The tree layout in this implementation of Merkle trees is based on the description of Merkle trees in RFC 6962. With this tree layout extending a Merkle tree requires chaining a logarithmic number of nodes at the end of the tree. Unlike RFC 6962 the Merkle trees in this module support the creation of unbalanced MerkleTrees by nesting sub-trees as leafs of Merkle trees. Also, unlike RFC 6962 this module generates fully self-contained inclusion proofs that don't rely on the client being aware of the balancing of the Merkle Tree that was used to generate the proof.
The API requires the usage of type applications which can be enabled with the following pragma.
{-# LANGUAGE TypeApplications #-}
Example
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE OverloadedStrings #-}
import qualified Data.ByteString as B
import Crypto.Hash.Algorithms (SHA512t_256)
inputs = ["a", "b", "c"] :: [B.ByteString]
-- create tree
t = merkleTree @SHA512t_256 inputs
-- create inclusion proof
p = either (error . show) id $ merkleProof 1 (inputs !! 1) t
-- verify proof
runMerkleProof p == merkleRoot t
TODO
- implement extension of trees (possibly by linking memory chunks of maximal full trees) (how important is this?)
- implement consistency proofs
- document encodings and hash format
- describe tree layout
Synopsis
- data MerkleTree a
- merkleTree :: forall a b. HasCallStack => HashAlgorithm a => ByteArrayAccess b => [MerkleNodeType a b] -> MerkleTree a
- encodeMerkleTree :: ByteArray b => MerkleTree a -> b
- decodeMerkleTree :: forall a b m. MonadThrow m => HashAlgorithm a => ByteArrayAccess b => b -> m (MerkleTree a)
- data MerkleRoot a
- merkleRoot :: forall a. HashAlgorithm a => MerkleTree a -> MerkleRoot a
- encodeMerkleRoot :: ByteArray b => MerkleRoot a -> b
- decodeMerkleRoot :: MonadThrow m => HashAlgorithm a => ByteArrayAccess b => b -> m (MerkleRoot a)
- data MerkleNodeType a b
- = TreeNode (MerkleRoot a)
- | InputNode b
- data MerkleProof a = MerkleProof {
- _merkleProofSubject :: !(MerkleProofSubject a)
- _merkleProofObject :: !(MerkleProofObject a)
- newtype MerkleProofSubject a = MerkleProofSubject {}
- data MerkleProofObject a
- encodeMerkleProofObject :: ByteArray b => MerkleProofObject a -> b
- decodeMerkleProofObject :: forall a b m. MonadThrow m => HashAlgorithm a => ByteArrayAccess b => b -> m (MerkleProofObject a)
- merkleProof :: forall a m. MonadThrow m => HashAlgorithm a => MerkleNodeType a ByteString -> Int -> MerkleTree a -> m (MerkleProof a)
- merkleProof_ :: forall a m. MonadThrow m => HashAlgorithm a => MerkleNodeType a ByteString -> NonEmpty (Int, MerkleTree a) -> m (MerkleProof a)
- runMerkleProof :: forall a. HashAlgorithm a => MerkleProof a -> MerkleRoot a
- newtype Expected a = Expected a
- newtype Actual a = Actual a
- data MerkleTreeException
- = EncodingSizeException Text (Expected Int) (Actual Int)
- | EncodingSizeConstraintException Text (Expected Text) (Actual Int)
- | IndexOutOfBoundsException Text (Expected (Int, Int)) (Actual Int)
- | InputNotInTreeException Text Int ByteString
- | MerkleRootNotInTreeException Text Int ByteString
- | InvalidProofObjectException Text
- textMessage :: MerkleTreeException -> Text
- isEmpty :: forall a. HashAlgorithm a => MerkleTree a -> Bool
- emptyMerkleTree :: forall a. HashAlgorithm a => MerkleTree a
- size :: forall a. HashAlgorithm a => MerkleTree a -> Int
- leafCount :: HashAlgorithm a => MerkleTree a -> Int
- data MerkleHash a
- getHash :: HashAlgorithm a => MerkleTree a -> Int -> MerkleHash a
- merkleLeaf :: forall a b. HashAlgorithm a => ByteArrayAccess b => b -> MerkleHash a
- merkleNode :: forall a. HashAlgorithm a => MerkleHash a -> MerkleHash a -> MerkleRoot a
Merkle Tree
data MerkleTree a Source #
Binary Merkle Tree.
A Merkle Tree is only an index. It doesn't store any data but only hashes of the data that is referenced in the tree.
Instances
| Eq (MerkleTree a) Source # | |
Defined in Data.MerkleLog | |
| Show (MerkleTree a) Source # | |
Defined in Data.MerkleLog Methods showsPrec :: Int -> MerkleTree a -> ShowS # show :: MerkleTree a -> String # showList :: [MerkleTree a] -> ShowS # | |
| Generic (MerkleTree a) Source # | |
Defined in Data.MerkleLog Associated Types type Rep (MerkleTree a) :: Type -> Type # | |
| NFData (MerkleTree a) Source # | |
Defined in Data.MerkleLog Methods rnf :: MerkleTree a -> () # | |
| ByteArrayAccess (MerkleTree a) Source # | |
Defined in Data.MerkleLog Methods length :: MerkleTree a -> Int # withByteArray :: MerkleTree a -> (Ptr p -> IO a0) -> IO a0 # copyByteArrayToPtr :: MerkleTree a -> Ptr p -> IO () # | |
| type Rep (MerkleTree a) Source # | |
Defined in Data.MerkleLog type Rep (MerkleTree a) = D1 (MetaData "MerkleTree" "Data.MerkleLog" "merkle-log-0.1.0.0-4JJg1LvWubF6HYXmsOGsa9" True) (C1 (MetaCons "MerkleTree" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Bytes))) | |
merkleTree :: forall a b. HasCallStack => HashAlgorithm a => ByteArrayAccess b => [MerkleNodeType a b] -> MerkleTree a Source #
Merkle Tree as described in RFC 6962, but with a configurable hash function and support for nested Merkle trees.
The Merkle tree for the empty input log is the hash of the empty string.
TODO: The length of the list is forced before the algorithm starts processing the items. Either demand a strict structure (e.g. vector or array) or allocate tree memory dynamically while traversing the log structure.
encodeMerkleTree :: ByteArray b => MerkleTree a -> b Source #
Binary encoding of a Merkle tree.
decodeMerkleTree :: forall a b m. MonadThrow m => HashAlgorithm a => ByteArrayAccess b => b -> m (MerkleTree a) Source #
Decode are Merkle tree from a binary representation.
Merkle Root
data MerkleRoot a Source #
The root of a Merkle tree.
Instances
merkleRoot :: forall a. HashAlgorithm a => MerkleTree a -> MerkleRoot a Source #
Get the root of Merkle tree.
encodeMerkleRoot :: ByteArray b => MerkleRoot a -> b Source #
Encode a Merkle tree root into binary format.
decodeMerkleRoot :: MonadThrow m => HashAlgorithm a => ByteArrayAccess b => b -> m (MerkleRoot a) Source #
Decode a Merkle tree root from a binary representation.
Merkle Proofs
data MerkleNodeType a b Source #
The Type of leafs nodes in a Merkle tree. A node is either an input value or a root of another nested Merkle tree.
Constructors
| TreeNode (MerkleRoot a) | |
| InputNode b |
Instances
data MerkleProof a Source #
Merkle Inclusion Proof. In RFC 6962 this is called an audit proof. The proof in this module are not compatible with RFC 6962. They support proving inclusion of subtrees and proof for unbalanced trees of unknown size.
The proof is self-contained. It is independent of the concrete implementation of the Merkle tree. This type works with any binary Merkle tree type and doesn't make any assumptions about the balancing of the tree.
The proof includes the subject of the proof (for which inclusion is proven) as a plaintext bytestring. The proof does not include the root hash of the Merkle tree, because the proof is only meaningful if the root is available from a trusted source. Including it into the proof would thus be redundant or even misleading.
A more compact encoding would use the first bit of each hash to encode the side, but that would require to alter the hash computation. We also could pack the sides into a bit array. However, the total number of bytes for the sides will be most likely less than two hashes, so the overhead is small and doesn't justify more clever encodings.
Constructors
| MerkleProof | |
Fields
| |
Instances
newtype MerkleProofSubject a Source #
The subject for which inclusion is proven.
Constructors
| MerkleProofSubject | |
Fields | |
Instances
data MerkleProofObject a Source #
Opaque proof object.
Instances
encodeMerkleProofObject :: ByteArray b => MerkleProofObject a -> b Source #
Encode a Merkle proof object into binary format.
This copies the bytes of the underlying byte array. The encoded object
doesn't reference the MerkleProofObject
decodeMerkleProofObject :: forall a b m. MonadThrow m => HashAlgorithm a => ByteArrayAccess b => b -> m (MerkleProofObject a) Source #
Encode a Merkle proof object from a binary representation.
This copies the original bytes and doesn't keep a reference to the input bytes.
merkleProof :: forall a m. MonadThrow m => HashAlgorithm a => MerkleNodeType a ByteString -> Int -> MerkleTree a -> m (MerkleProof a) Source #
Construct a self-contained Merkle inclusion proof.
Arguments
| :: MonadThrow m | |
| => HashAlgorithm a | |
| => MerkleNodeType a ByteString | The proof subject |
| -> NonEmpty (Int, MerkleTree a) | The proof components |
| -> m (MerkleProof a) |
Construct a Merkle proof for a proof subject in a nested sub-tree.
FIXME: make this function more efficient by implementing it more directly.
runMerkleProof :: forall a. HashAlgorithm a => MerkleProof a -> MerkleRoot a Source #
Execute an inclusion proof. The result of the execution is a Merkle root that must be compared to the trusted root of the Merkle tree.
Exceptions
An expected value.
Constructors
| Expected a |
Instances
| Eq a => Eq (Expected a) Source # | |
| Ord a => Ord (Expected a) Source # | |
| Show a => Show (Expected a) Source # | |
| Generic (Expected a) Source # | |
| NFData a => NFData (Expected a) Source # | |
Defined in Data.MerkleLog | |
| type Rep (Expected a) Source # | |
Defined in Data.MerkleLog | |
An actual value.
Constructors
| Actual a |
data MerkleTreeException Source #
Exceptions that are thrown by functions in Data.MerkleLog. All functions that throw exceptions can be called as pure functions in `Either SomeException`.
Constructors
Instances
textMessage :: MerkleTreeException -> Text Source #
Display MerkleTreeException values as text messages.
Internal
isEmpty :: forall a. HashAlgorithm a => MerkleTree a -> Bool Source #
Test a Merkle tree is the tree of the empty log.
emptyMerkleTree :: forall a. HashAlgorithm a => MerkleTree a Source #
The Merkle tree of the empty log. RFC 6962 specifies that this is the hash of the empty string.
size :: forall a. HashAlgorithm a => MerkleTree a -> Int Source #
The number of nodes (including leafs) in a Merkle tree.
leafCount :: HashAlgorithm a => MerkleTree a -> Int Source #
Get the number of leafs in a Merkle tree.
data MerkleHash a Source #
Internal type to represent hash values.
Instances
getHash :: HashAlgorithm a => MerkleTree a -> Int -> MerkleHash a Source #
Get the hash of a node in the Merkle tree.
merkleLeaf :: forall a b. HashAlgorithm a => ByteArrayAccess b => b -> MerkleHash a Source #
Compute hash for a leaf node in a Merkle tree.
merkleNode :: forall a. HashAlgorithm a => MerkleHash a -> MerkleHash a -> MerkleRoot a Source #
Compute hash for an inner node of a Merkle tree.