## Expand description

This module implements `JellyfishMerkleTree`

backed by storage module. The tree itself doesn’t
persist anything, but realizes the logic of R/W only. The write path will produce all the
intermediate results in a batch for storage layer to commit and the read path will return
results directly. The public APIs are only `new`

, `put_value_sets`

, `put_value_set`

and
`get_with_proof`

. After each put with a `value_set`

based on a known version, the tree will
return a new root hash with a `TreeUpdateBatch`

containing all the new nodes and indices of
stale nodes.

A Jellyfish Merkle Tree itself logically is a 256-bit sparse Merkle tree with an optimization that any subtree containing 0 or 1 leaf node will be replaced by that leaf node or a placeholder node with default hash value. With this optimization we can save CPU by avoiding hashing on many sparse levels in the tree. Physically, the tree is structurally similar to the modified Patricia Merkle tree of Ethereum but with some modifications. A standard Jellyfish Merkle tree will look like the following figure:

```
.──────────────────────.
_.─────' `──────.
_.──' `───.
_.─' `──.
_.─' `──.
,' `.
,─' '─.
,' `.
,' `.
╱ ╲
╱ ╲
╱ ╲
╱ ╲
; :
; :
; :
│ │
+──────────────────────────────────────────────────────────────────────────────────────────────+
.''. .''. .''. .''. .''. .''. .''. .''. .''. .''. .''. .''. .''. .''. .''. .''.
/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \
+----++----++----++----++----++----++----++----++----++----++----++----++----++----++----++----+
( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( (
) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )
( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( (
) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )
( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( (
) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )
( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( (
) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )
( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( (
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
■: the [`Value`] type this tree stores.
```

A Jellyfish Merkle Tree consists of `InternalNode`

and `LeafNode`

. `InternalNode`

is like
branch node in ethereum patricia merkle with 16 children to represent a 4-level binary tree and
`LeafNode`

is similar to that in patricia merkle too. In the above figure, each `bell`

in the
jellyfish is an `InternalNode`

while each tentacle is a `LeafNode`

. It is noted that
Jellyfish merkle doesn’t have a counterpart for `extension`

node of ethereum patricia merkle.

## Modules

A mock, in-memory tree store useful for testing.

Merkle proof types.

This module implements the functionality to restore a
`JellyfishMerkleTree`

from small chunks of
key/value pairs.

Contains types used to bridge a `JellyfishMerkleTree`

to the backing storage recording the tree’s internal data.

## Structs

The `JellyfishMerkleStream`

implementation.

The Jellyfish Merkle tree data structure. See `crate`

for description.

A hashed key used to index a `JellyfishMerkleTree`

.

An error that occurs when the state root for a requested version is missing (e.g., because it was pruned).

A root of a `JellyfishMerkleTree`

.

A wrapper around a `JellyfishMerkleTree`

that buffers pending writes to the
tree, and overlays the effect of those writes on the tree state for reading.

## Functions

## Type Definitions

An owned value stored in the `JellyfishMerkleTree`

.

Specifies a particular version of the `JellyfishMerkleTree`

state.