More efficient state representation

[abacabadabacaba]

THIS IS A DRAFT, MORE INFO WILL BE ADDED LATER

See also: #4413.

Problem description

The data structure that is currently used to represent blockchain state, a variant of Merkle-Patricia Trie (MPT), is not very efficient. We want this structure to have the following properties:

1. Simplicity: we don't want to make the protocol too complex.
2. Processing efficiency: accessing the state when processing transactions and receipts should be reasonably fast.
3. Fee structure: state-accessing operations should have predictable gas fees.
4. Proof efficiency: it should be possible to construct a reasonably small proof that the state includes specific key-value pairs, or that it doesn't include specific keys, or that applying specific updates results in a specific root hash. This is needed for challenges.
5. Split and join operations: these operation make it possible to reshard more efficiently.

MPT satisfies (1) to some extent, but not too well: node structure and algorithms are not very simple. There are possible simplifications (like merging extension nodes and branch nodes) which can improve this, but MPT has other, more fundamental problems.

For (2), the efficiently depends to a large extend on the depth on the tree. While the depth of MPT is usually small, it is possible for an adversary to make it as large as twice the length of the key in bytes, which is not good. If the keys are hashed, the impact of this attack is limited, but resharding becomes more difficult. Thus, (2) is not satisfied.

For (3), currently the gas fee for accessing a key depends on the number of nodes on its path, which in turn depends on the other keys as well. This makes the fee structure non-transparent for developers. Thus, (3) is not satisfied.

For (4), the worst proof size should be considered. For MPT, the worst case is when the path consists entirely of branch nodes, and each of them has a maximum number of children (16). In this case, each node will take at least 16×32=512 bytes just for the hashes (every second node can have one more hash if there is a key ending in that node). With a maximum of two nodes for each byte of the key, a proof for a single 50-byte key can take at least 50 KiB just for the intermediate nodes! Clearly, (4) is not satisfied.

MPT does satisfy (5) (if the keys are not hashes, see (2)).

Overall, MPT satisfies only two of the desired properties out of five, which is not enough.

Proposed solution: AVL tree

To solve these problems, I propose to represent the state as a variant of AVL tree. Here are some of the differences from MPT:

• The depth of an AVL tree is bounded by a logarithm of the number of entries, so it is much more difficult to create very deep trees.
• Because the tree is binary, a proof only requires one hash for each level.
• Unlike MPT, an AVL tree can have multiple different ways (with different tree structures) to represent the same set of key-value pairs. With MPT, root hash is a function of the set of key-value pairs. With AVL trees, the exact tree structure is part of the state.
• Adding or removing entries from an AVL tree may result in rotations, which may sometimes touch nodes which are not on the path from the root to the entry. Still, the total number of nodes touched is bounded by a logarithm of the total number of entries.

In the most common version of AVL trees, every node contains an entry. For our use case, this is suboptimal: if every node contains a key-value pair, then to prove the existence of some node it is necessary to provide keys and values for all nodes on the path from that node to the root. Even if those keys and values are hashed, the size of the proof is still much larger compared to the case where only leaf nodes contain entries. So, only leaf nodes contain entries, and internal nodes only include the hashes of their children.

Each internal node should also include its tilt (the difference between the heights of its subtrees). Because its absolute value cannot exceed one, there are only three possible values: left (left subtree is higher), right and center. This information is merkelized (that is, it contributes to the hash of the node) because it is needed to prove that the rotations are performed correctly. In addition to these values, each internal node is associated with a boundary key, which is the highest key in the left subtree. This is used by lookup algorithm to find an entry by its key. This value is not merkelized, instead, a different approach is used to prove that a lookup was performed correctly.

Simplified implementation

use std::iter::once;

// Types used in the tree, and basic operations on them
// ====================================================

// In this implementation, the items are key-value pairs. Keys must be ordered.
#[derive(PartialEq, PartialOrd)]
pub struct K(String);
pub struct V(String);

// Hashes must be comparable but need not be ordered.
#[derive(Copy, Clone, PartialEq)]
pub struct Hash(usize);

// The tree consists of nodes. Only leaf nodes contain keys and values, and each internal node must have two children.
// Empty/missing nodes are not permitted.
pub enum Node {
    Leaf { key: K, value: V },
    Internal { left: Hash, right: Hash, tilt: Tilt },
}
use Node::*;

// Because nodes cannot be empty, there is a special case for a completely empty tree.
pub enum Tree {
    Empty,
    NonEmpty(Node),
}

// Each internal node stores the difference between the heights of its child subtrees, which must not exceed one by
// absolute value. Left means that the left subtree is higher, Right means that the right is higher, Center means that
// the heights are equal.
#[derive(Copy, Clone, PartialEq)]
pub enum Tilt {
    Left,
    Center,
    Right,
}
use Tilt::{Center as TCenter, Left as TLeft, Right as TRight};

// There should be a procedure to compute the hashes of nodes.

pub fn hash_leaf_node(_k: &K, _v: &V) -> Hash {
    unimplemented!()
}

pub fn hash_internal_node(_left: Hash, _right: Hash, _tilt: Tilt) -> Hash {
    unimplemented!()
}

pub fn hash_node(node: &Node) -> Hash {
    match node {
        Leaf { key, value } => hash_leaf_node(key, value),
        &Internal { left, right, tilt } => hash_internal_node(left, right, tilt),
    }
}

// The hash of a tree is the same as the hash of its root node, or a special value if the tree is empty.
// This special value must not be used as a hash of a node's child.

pub const EMPTY_TREE_HASH: Hash = Hash(usize::MAX);

pub fn hash_tree(tree: &Tree) -> Hash {
    match tree {
        Tree::Empty => EMPTY_TREE_HASH,
        Tree::NonEmpty(node) => hash_node(node),
    }
}

// Chunk producers have the entire state, so they can look up nodes and trees by hash.

pub fn lookup_by_hash_node(_hash: Hash) -> Node {
    unimplemented!();
}

// This is used if a node is guaranteed to be an internal node.
fn lookup_by_hash_internal_node(hash: Hash) -> (Hash, Hash, Tilt) {
    match lookup_by_hash_node(hash) {
        Internal { left, right, tilt } => (left, right, tilt),
        Leaf { .. } => unreachable!(),
    }
}

pub fn lookup_by_hash_tree(hash: Hash) -> Tree {
    if hash == EMPTY_TREE_HASH {
        Tree::Empty
    } else {
        Tree::NonEmpty(lookup_by_hash_node(hash))
    }
}

// They also keep track of the boundary key (the highest key in the left subtree) of each internal node.

pub fn boundary_key(_node: &Node) -> K {
    unimplemented!();
}

// Common types and operations used in the proofs
// ==============================================

// This is the result of verification operations, essentially a bool.
pub type VerifyResult = Result<(), ()>;

fn verify(cond: bool) -> VerifyResult {
    if cond {
        Ok(())
    } else {
        Err(())
    }
}

// Directions appear in nearly every proof.

#[derive(Copy, Clone, PartialEq)]
pub enum Direction {
    Left,
    Right,
}
use Direction::{Left as DLeft, Right as DRight};

// These functions are used to avoid duplicating a lot of code for different directions.
impl Direction {
    fn choose<T>(self, left: T, right: T) -> T {
        match self {
            DLeft => left,
            DRight => right,
        }
    }

    fn swap<T>(self, this: T, other: T) -> (T, T) {
        match self {
            DLeft => (this, other),
            DRight => (other, this),
        }
    }

    fn is_left(self) -> bool {
        self.choose(true, false)
    }

    fn opp(self) -> Self {
        self.choose(DRight, DLeft)
    }

    // A common operation is to derive a tilt from a direction, or to match a tilt with a direction.

    fn same_tilt(self) -> Tilt {
        self.choose(TLeft, TRight)
    }

    fn opposite_tilt(self) -> Tilt {
        self.choose(TRight, TLeft)
    }
}

#[derive(Copy, Clone, PartialEq)]
pub enum MatchedTilt {
    Same,
    Center,
    Opposite,
}
use MatchedTilt::{Center as MCenter, Opposite, Same};

impl MatchedTilt {
    fn choose<T>(self, same: T, center: T, opposite: T) -> T {
        match self {
            Same => same,
            MCenter => center,
            Opposite => opposite,
        }
    }
}

fn match_tilt(t: Tilt, d: Direction) -> MatchedTilt {
    match t {
        TLeft => d.choose(Same, Opposite),
        TCenter => MCenter,
        TRight => d.choose(Opposite, Same),
    }
}

// Path proofs are used to show that some node is a descendant of another node.
// For each node on the path, a proof provides the direction, the hash of that node's sibling, and a tilt.
// The order is from the leaf towards the root.

pub type PathProof = Vec<(Direction, Hash, Tilt)>;

// This applies a single path proof element.
fn apply_step(this: Hash, other: Hash, direction: Direction, tilt: Tilt) -> Hash {
    let (l, r) = direction.swap(this, other);
    hash_internal_node(l, r, tilt)
}

// This applies a sequence of them.
fn apply_path(hash: Hash, path: impl IntoIterator<Item = (Direction, Hash, Tilt)>) -> Hash {
    path.into_iter().fold(hash, |h, (d, s, t)| apply_step(h, s, d, t))
}

// A special case if all elements have the same direction.
fn apply_path_samedir(dir: Direction, hash: Hash, path: &[(Hash, Tilt)]) -> Hash {
    apply_path(hash, with_samedir(dir, path))
}

fn with_samedir(dir: Direction, path: &[(Hash, Tilt)]) -> impl Iterator<Item = (Direction, Hash, Tilt)> + '_ {
    path.iter().map(move |&(s, t)| (dir, s, t))
}

// To prove a failed lookup, it is necessary to provide the adjacent items and the corresponding proofs.
// However, either or both of the adjacent items may not exist.
pub enum FailureProof {
    // Empty tree
    Empty,
    // All items are either greater or less than the key.
    Side(Direction, K, V, Vec<(Hash, Tilt)>),
    // There are items on both sides of the key.
    Middle {
        // Left adjacent item and the path to the join node
        left: (K, V, Vec<(Hash, Tilt)>),
        // Right adjacent item and the path to the join node
        right: (K, V, Vec<(Hash, Tilt)>),
        // The tilt of the join node
        join_tilt: Tilt,
        // The path from the join node to the root
        common: Vec<(Direction, Hash, Tilt)>,
    },
}

fn verify_failure(tree: Hash, key: &K, proof: &FailureProof) -> VerifyResult {
    // When verifying a failure proof, there are three cases:
    // 1. None of the two adjacent items exists. In this case, the tree must be empty.
    // 2. Only one of the adjacent items exists, which must be the first or the last in the tree.
    // 3. Both of the adjacent items exist, and they must be adjacent.
    match proof {
        FailureProof::Empty => verify(tree == EMPTY_TREE_HASH),
        FailureProof::Side(dir, k, v, path) => {
            verify(if dir.is_left() { k < key } else { k > key })?;
            verify(tree == apply_path_samedir(dir.opp(), hash_leaf_node(k, v), path))
        }
        FailureProof::Middle { left: (lk, lv, lp), right: (rk, rv, rp), join_tilt, common } => {
            verify(lk < key && rk > key)?;
            verify(
                tree == apply_path(
                    hash_internal_node(
                        apply_path_samedir(DRight, hash_leaf_node(lk, lv), lp),
                        apply_path_samedir(DLeft, hash_leaf_node(rk, rv), rp),
                        *join_tilt,
                    ),
                    common.iter().copied(),
                ),
            )
        }
    }
}

// Lookup operation
// ================

// Lookup operation either finds a value that corresponds to the given key, or shows that none exists.

pub enum LookupProof {
    Success(PathProof),
    Failure(FailureProof),
}

pub fn lookup(tree: Hash, key: &K) -> (Option<V>, LookupProof) {
    // Empty tree is a special case.
    if tree == EMPTY_TREE_HASH {
        (None, LookupProof::Failure(FailureProof::Empty))
    } else {
        let (k, v, trace) = lookdown(tree, key);
        if &k == key {
            (Some(v), LookupProof::Success(trace.iter().rev().map(|&(d, _, s, t)| (d, s, t)).collect()))
        } else {
            let dir = if &k < key { DLeft } else { DRight };
            (None, LookupProof::Failure(make_failure_proof(k, v, trace, dir).0))
        }
    }
}

// Verification simply uses the functions defined above.
pub fn verify_lookup(tree: Hash, key: &K, value: Option<&V>, proof: &LookupProof) -> VerifyResult {
    match (value, proof) {
        (Some(v), LookupProof::Success(p)) => verify(tree == apply_path(hash_leaf_node(key, v), p.iter().copied())),
        (None, LookupProof::Failure(p)) => verify_failure(tree, key, p),
        _ => Err(()),
    }
}

// This function performs the first phase of the lookup: it walks down the tree to find the node with a matching key if
// there is one, or one of the adjacent nodes otherwise.
fn lookdown(tree: Hash, key: &K) -> (K, V, Vec<(Direction, Hash, Hash, Tilt)>) {
    // Walk down the tree, while collecting some information on the way.
    let mut node_hash = tree;
    // Each element stores a direction, current child's hash, sibling's hash and a tilt.
    let mut trace = Vec::new();
    loop {
        match lookup_by_hash_node(node_hash) {
            // Unlike the regular AVL trees, these trees don't have any key-value pairs in the internal nodes.
            // So, always go down to one of the children.
            ref node @ Node::Internal { left, right, tilt } => {
                let k = boundary_key(node);
                // k is the highest key in the left subtree, so need to use <=.
                let d = if key <= &k { DLeft } else { DRight };
                let (c, s) = d.swap(left, right);
                trace.push((d, c, s, tilt));
                node_hash = c;
            }
            Node::Leaf { key, value } => {
                return (key, value, trace);
            }
        }
    }
}

// Given one of the nodes adjacent to a key, finds another one (if any) and builds a failure proof. If dir is Left, the
// passed node is left adjacent, otherwise it is right adjacent. Also returns the hashes of the joining node's children.
fn make_failure_proof(
    key: K,
    value: V,
    trace: Vec<(Direction, Hash, Hash, Tilt)>,
    dir: Direction,
) -> (FailureProof, Option<(Hash, Hash)>) {
    // First, remove any elements in the end of the trace, whose direction is opposite to dir.
    let mut i = trace.len();
    let mut proof = Vec::new();
    while i > 0 && trace[i - 1].0 == dir.opp() {
        i -= 1;
        proof.push((trace[i].2, trace[i].3));
    }
    // If no elements remain, there is no adjacent item on the other side.
    if i == 0 {
        (FailureProof::Side(dir, key, value, proof), None)
    } else {
        i -= 1;
        let mut proof2 = Vec::new();
        let mut node_hash = trace[i].2;
        let (k, v) = loop {
            match lookup_by_hash_node(node_hash) {
                // In an internal node, descend in the direction dir.
                Node::Internal { left, right, tilt } => {
                    let (c, s) = dir.swap(left, right);
                    proof2.push((s, tilt));
                    node_hash = c;
                }
                Node::Leaf { key, value } => break (key, value),
            }
        };
        // After reaching a leaf, assemble the whole proof: reverse the current segment and add a common suffix from the
        // existing proof.
        proof2.reverse();
        let ((kl, vl, pl), (kr, vr, pr)) = dir.swap((key, value, proof), (k, v, proof2));
        (
            FailureProof::Middle {
                left: (kl, vl, pl),
                right: (kr, vr, pr),
                join_tilt: trace[i].3,
                common: trace[..i].iter().rev().map(|&(d, _, s, t)| (d, s, t)).collect(),
            },
            Some(dir.swap(trace[i].1, trace[i].2)),
        )
    }
}

// Set operation
// =============

// Set operation adds an item with a given key and value or updates an existing item.
// Returns the previous value (if any), the proof, and the new tree hash.

pub fn set(tree: Hash, key: &K, value: &V) -> (Option<V>, LookupProof, Hash) {
    let (v, proof) = lookup(tree, key);
    let new_tree = finish_set(&proof, key, value);
    (v, proof, new_tree)
}

pub fn verify_set(
    tree: Hash,
    key: &K,
    value: &V,
    old_value: Option<&V>,
    proof: &LookupProof,
    new_tree: Hash,
) -> VerifyResult {
    verify_lookup(tree, key, old_value, proof)?;
    verify(new_tree == finish_set(proof, key, value))?;
    Ok(())
}

// It happens that the proof returned by lookup is enough to complete the set operation without using lookup_by_hash.
fn finish_set(proof: &LookupProof, key: &K, value: &V) -> Hash {
    match proof {
        // Proof of successful lookup can just be applied to a modified leaf node,
        LookupProof::Success(p) => apply_path(hash_leaf_node(key, value), p.iter().copied()),
        // If a lookup failed, a new leaf node is inserted next to a node that holds one of the adjacent items.
        // This code prefers the left adjacent item, but uses the right if the left doesn't exist.
        // It is also possible that the tree is empty, so it is replaced with a single leaf node.
        LookupProof::Failure(fp) => match fp {
            FailureProof::Empty => hash_leaf_node(key, value),
            FailureProof::Side(dir, k, v, p) => {
                let (l, r) = dir.swap(hash_leaf_node(k, v), hash_leaf_node(key, value));
                finish_insert(InsertState::Center(l, r), with_samedir(dir.opp(), p)).0
            }
            FailureProof::Middle { left, right, join_tilt, common } => {
                finish_insert(
                    InsertState::Center(hash_leaf_node(&left.0, &left.1), hash_leaf_node(key, value)),
                    with_samedir(DRight, &left.2)
                        .chain(once((
                            DLeft,
                            apply_path_samedir(DLeft, hash_leaf_node(&right.0, &right.1), &right.2),
                            *join_tilt,
                        )))
                        .chain(common.iter().copied()),
                )
                .0
            }
        },
    }
}

// Insert state represents the current subtree. The root node must be an internal node.
// If the root node's tilt is Center, only the child's hashes are stored.
// Otherwise, the tilt must be Left or Right, in which case the corresponding child must be an internal node, so that
// child's child hashes and tilt are stored.
enum InsertState {
    // Order: left child, right child.
    Center(Hash, Hash),
    // Order: if the direction is Left, from left to right, otherwise from right to left.
    Tilted(Direction, Hash, Hash, Tilt, Hash),
}

impl InsertState {
    // Converts the state into a single internal node (represented as a tuple of fields).
    fn collapse(self) -> (Hash, Hash, Tilt) {
        match self {
            Self::Center(l, r) => (l, r, TCenter),
            Self::Tilted(d, h11, h12, t, h2) => {
                let (l1, r1) = d.swap(h11, h12);
                let (l2, r2) = d.swap(hash_internal_node(l1, r1, t), h2);
                (l2, r2, d.same_tilt())
            }
        }
    }

    fn hash(self) -> Hash {
        let (l, r, t) = self.collapse();
        hash_internal_node(l, r, t)
    }
}

// Assumes that a node is replaced by different node whose height is one higher than that of the original.
// Modifies the tree accordingly. Returns the new root hash and a boolean indicating whether the height of the entire
// tree increased.
fn finish_insert(mut state: InsertState, mut proof: impl Iterator<Item = (Direction, Hash, Tilt)>) -> (Hash, bool) {
    // Invariant: the current node's height is one more than that of the original node.
    // As a result, tilts need to be adjusted, and rotations may need to be performed.
    for (d, s, t) in proof.by_ref() {
        state = match match_tilt(t, d) {
            // The easiest case: the current node's height was smaller than that of its sibling.
            // After the insertion, its height becomes the same, and the parent's height doesn't change.
            Opposite => {
                return (apply_path(apply_step(state.hash(), s, d, TCenter), proof), false);
            }
            // Medium case: the current node's height was the same as that of its sibling.
            // The parent's height increases, but no rotation is necessary.
            MCenter => {
                let (l, r, t) = state.collapse();
                let (h1, h2) = d.swap(l, r);
                InsertState::Tilted(d, h1, h2, t, s)
            }
            // Difficult case: the current node's height was already greater than that of the sibling, so after it is
            // increased even more, the parent node becomes overtilted.
            // There are two possible kinds of rotations, depending on the heights of different subtrees.
            Same => {
                match state {
                    // Single rotation (option 1)
                    InsertState::Center(l, r) => {
                        let (h1, h2) = d.swap(l, r);
                        InsertState::Tilted(d.opp(), s, h2, d.same_tilt(), h1)
                    }
                    InsertState::Tilted(d2, h11, h12, t, h2) => {
                        let (rh11, rh12, rt1, rh21, rh22, rt2) = if d2 == d {
                            // Single rotation (option 2)
                            (h11, h12, t, h2, s, TCenter)
                        } else {
                            // Double rotation
                            let (t2, t3) = match match_tilt(t, d) {
                                Same => (TCenter, d.opposite_tilt()),
                                MCenter => (TCenter, TCenter),
                                Opposite => (d.same_tilt(), TCenter),
                            };
                            (h2, h12, t2, h11, s, t3)
                        };
                        let rh1 = apply_step(rh11, rh12, d, rt1);
                        let rh2 = apply_step(rh21, rh22, d, rt2);
                        let rh = apply_step(rh1, rh2, d, TCenter);
                        return (apply_path(rh, proof), false);
                    }
                }
            }
        };
    }
    // This is reached if the height of the entire tree is increased as a result of the insertion.
    (state.hash(), true)
}

// Delete operation
// ================

// Delete operation removes the item with a given key, if any.
// The proof is more complex, as it is necessary to include the hashes of some descendants of the sibling nodes.

#[derive(Copy, Clone)]
pub enum DeleteProofElement {
    Simple(Direction, Hash, Tilt),               // No rotation
    Complex(Direction, Hash, Hash, Tilt),        // Single rotation
    Complex2(Direction, Hash, Hash, Tilt, Hash), // Double rotation
}

pub enum DeleteProof {
    Success(Vec<DeleteProofElement>),
    Failure(FailureProof),
}

// Returns the old value, a proof, and the new tree hash.

pub fn delete(tree: Hash, key: &K) -> (Option<V>, DeleteProof, Hash) {
    let (value, proof) = lookup(tree, key);
    let (proof, new_tree) = match proof {
        LookupProof::Success(p) => {
            // same_height: if true, the new node has the same height as the old one, otherwise the height of the new
            // node is one less than that of the old one.
            let mut same_height = false;
            // First element is handled differently.
            let mut first_elem = true;
            let proof: Vec<_> = p
                .into_iter()
                .map(|(d, s, t)| {
                    // Same height: no tilt adjustment or rotation, so simple proof elements.
                    // First element: an internal node is replaced by one of its children, no extra data is necessary.
                    // t is not opposite to d: no rotation is necessary.
                    if same_height || first_elem || t != d.opposite_tilt() {
                        if !first_elem && t == TCenter {
                            same_height = true;
                        }
                        first_elem = false;
                        DeleteProofElement::Simple(d, s, t)
                    } else {
                        let (l, r, t) = lookup_by_hash_internal_node(s);
                        let (h1, h2) = d.swap(l, r);
                        if t != d.same_tilt() {
                            // Single rotation. t == TCenter corresponds to option 1.
                            if t == TCenter {
                                same_height = true;
                            }
                            DeleteProofElement::Complex(d, h1, h2, t)
                        } else {
                            // Double rotation
                            let (l, r, t) = lookup_by_hash_internal_node(h1);
                            let (h11, h12) = d.swap(l, r);
                            DeleteProofElement::Complex2(d, h11, h12, t, h2)
                        }
                    }
                })
                .collect();
            let new_tree = finish_delete(key, value.as_ref().unwrap(), &proof).unwrap().1;
            (DeleteProof::Success(proof), new_tree)
        }
        LookupProof::Failure(p) => (DeleteProof::Failure(p), tree),
    };
    (value, proof, new_tree)
}

pub fn verify_delete(tree: Hash, key: &K, old_value: Option<&V>, proof: &DeleteProof, new_tree: Hash) -> VerifyResult {
    match (old_value, proof) {
        (Some(v), DeleteProof::Success(p)) => {
            let (expect_tree, expect_new_tree) = finish_delete(key, v, p).ok_or(())?;
            verify(tree == expect_tree && new_tree == expect_new_tree)
        }
        (None, DeleteProof::Failure(p)) => {
            verify_failure(tree, key, p)?;
            verify(new_tree == tree)
        }
        _ => Err(()),
    }
}

fn finish_delete(key: &K, value: &V, proof: &[DeleteProofElement]) -> Option<(Hash, Hash)> {
    let mut old_hash = hash_leaf_node(key, value);
    // If the proof is empty, the only remaining node was removed.
    if proof.is_empty() {
        Some((old_hash, EMPTY_TREE_HASH))
    } else {
        // The first element must be Simple.
        let (d, s, t) = if let DeleteProofElement::Simple(d, s, t) = proof[0] {
            (d, s, t)
        } else {
            return None;
        };
        old_hash = apply_step(old_hash, s, d, t);
        // new_hash is initialized with the sibling hash of the removed node.
        let mut new_hash = s;
        // Initially, the heights of the old_hash subtree and the new_hash subtree differ by one.
        let mut same_height = false;
        for p in &proof[1..] {
            match *p {
                // No rotation, but the tilt may be adjusted.
                DeleteProofElement::Simple(d, s, t) => {
                    let t2 = if same_height {
                        t
                    } else {
                        match match_tilt(t, d) {
                            Same => TCenter,
                            MCenter => {
                                same_height = true;
                                d.opposite_tilt()
                            }
                            // If not same_height and t == d.opposite_tilt(), a different proof element must be used.
                            Opposite => return None,
                        }
                    };
                    old_hash = apply_step(old_hash, s, d, t);
                    new_hash = apply_step(new_hash, s, d, t2);
                }
                // Single rotation
                DeleteProofElement::Complex(d, h1, h2, t) => {
                    if same_height {
                        return None;
                    }
                    let (t2, t3) = match match_tilt(t, d) {
                        // If t == d.same_tilt(), double rotation must be used.
                        Same => return None,
                        MCenter => {
                            same_height = true;
                            (d.opposite_tilt(), d.same_tilt())
                        }
                        Opposite => (TCenter, TCenter),
                    };
                    old_hash = apply_step(old_hash, apply_step(h1, h2, d, t), d, d.opposite_tilt());
                    new_hash = apply_step(apply_step(new_hash, h1, d, t2), h2, d, t3);
                }
                // Double rotation
                DeleteProofElement::Complex2(d, h11, h12, t, h2) => {
                    if same_height {
                        return None;
                    }
                    let (t2, t3) = match match_tilt(t, d) {
                        Same => (TCenter, d.opposite_tilt()),
                        MCenter => (TCenter, TCenter),
                        Opposite => (d.same_tilt(), TCenter),
                    };
                    old_hash = apply_step(
                        old_hash,
                        apply_step(apply_step(h11, h12, d, t), h2, d, d.same_tilt()),
                        d,
                        d.opposite_tilt(),
                    );
                    new_hash = apply_step(apply_step(new_hash, h11, d, t2), apply_step(h12, h2, d, t3), d, TCenter);
                }
            }
        }
        Some((old_hash, new_hash))
    }
}

// Split operation
// ===============

// Split operation separates a tree into two: one with the items whose keys are less than a given key, and the other
// with the remaining items.

pub enum SplitProof {
    Empty,
    Side(Direction, K, V, Vec<(Hash, Tilt)>),
    Middle {
        left: (K, V, Vec<(Hash, Tilt)>),
        right: (K, V, Vec<(Hash, Tilt)>),
        join_tilt: Tilt,
        // Here, some paths into sibling subtrees are included.
        common: Vec<(Direction, Hash, Vec<(Hash, Tilt)>, Tilt)>,
    },
}

pub fn split(tree: Hash, key: &K) -> (Hash, Hash, SplitProof) {
    if tree == EMPTY_TREE_HASH {
        (EMPTY_TREE_HASH, EMPTY_TREE_HASH, SplitProof::Empty)
    } else {
        let (k, v, trace) = lookdown(tree, key);
        let dir = if &k < key { DLeft } else { DRight };
        match make_failure_proof(k, v, trace, dir) {
            (FailureProof::Side(dir, k, v, p), None) => {
                let (l, r) = dir.swap(tree, EMPTY_TREE_HASH);
                (l, r, SplitProof::Side(dir, k, v, p))
            }
            (FailureProof::Middle { left, right, join_tilt, common }, Some((mut left_hash, mut right_hash))) => {
                // Here, the code is keeping track of the hash and the height of the left and the right tree, as well as
                // the height of the old (common) tree.
                let mut left_h = path_height_samedir(DRight, &left.2);
                let mut right_h = path_height_samedir(DLeft, &right.2);
                let mut common_h = left_h.max(right_h) + 1;
                let new_common = common
                    .into_iter()
                    .map(|(dir, mut s, t)| {
                        // The height of the sibling tree can be determined from the height of the current (common) tree
                        // and the tilt of the current node.
                        let sh_orig = match_tilt(t, dir).choose(common_h - 1, common_h, common_h + 1);
                        common_h += if t == dir.opposite_tilt() { 2 } else { 1 };
                        let ((this, this_h), (other, other_h)) = dir.swap((left_hash, left_h), (right_hash, right_h));
                        // Now going to merge `other` into `s`.
                        assert!(other_h <= sh_orig + 1);
                        let mut sp = Vec::new();
                        let (new_other, new_other_h) = if sh_orig > other_h + 1 {
                            let mut sh = sh_orig;
                            let mut extra = false;
                            loop {
                                let (left, right, tilt) = lookup_by_hash_internal_node(s);
                                let (this, other) = dir.swap(left, right);
                                sp.push((other, tilt));
                                s = this;
                                sh -= if tilt == dir.opposite_tilt() { 2 } else { 1 };
                                if sh <= other_h + 1 {
                                    // One extra element may be necessary for a double rotation.
                                    if sh == other_h + 1 && sp[sp.len() - 1].1 == dir.same_tilt() {
                                        extra = true;
                                    } else {
                                        break;
                                    }
                                }
                            }
                            sp.reverse();
                            finish_subjoin(dir, other, other_h, s, sh, sh_orig, &sp, extra)
                        } else {
                            apply_step_with_heights(dir, other, other_h, s, sh_orig)
                        };
                        let ((new_left_hash, new_left_h), (new_right_hash, new_right_h)) =
                            dir.swap((this, this_h), (new_other, new_other_h));
                        left_hash = new_left_hash;
                        left_h = new_left_h;
                        right_hash = new_right_hash;
                        right_h = new_right_h;
                        (dir, s, sp, t)
                    })
                    .collect();
                (left_hash, right_hash, SplitProof::Middle { left, right, join_tilt, common: new_common })
            }
            _ => unreachable!(),
        }
    }
}

pub fn verify_split(tree: Hash, key: &K, proof: &SplitProof, new_left: Hash, new_right: Hash) -> VerifyResult {
    let (expected_tree, expected_left, expected_right) = match proof {
        SplitProof::Empty => (EMPTY_TREE_HASH, EMPTY_TREE_HASH, EMPTY_TREE_HASH),
        SplitProof::Side(dir, k, v, path) => {
            verify(if dir.is_left() { k < key } else { k > key })?;
            let tree = apply_path_samedir(dir.opp(), hash_leaf_node(k, v), path);
            let (left, right) = dir.swap(tree, EMPTY_TREE_HASH);
            (tree, left, right)
        }
        SplitProof::Middle { left, right, join_tilt, common } => {
            let (mut left_hash, mut left_h) = {
                let (k, v, p) = left;
                (apply_path_samedir(DRight, hash_leaf_node(k, v), p), path_height_samedir(DRight, p))
            };
            let (mut right_hash, mut right_h) = {
                let (k, v, p) = right;
                (apply_path_samedir(DLeft, hash_leaf_node(k, v), p), path_height_samedir(DLeft, p))
            };
            let mut common_hash = hash_internal_node(left_hash, right_hash, *join_tilt);
            let mut common_h = left_h.max(right_h) + 1;
            for &(dir, s, ref sp, t) in common {
                let sh_orig = match_tilt(t, dir).choose(common_h - 1, common_h, common_h + 1);
                common_hash = apply_step(common_hash, apply_path_samedir(dir, s, sp), dir, t);
                common_h += if t == dir.opposite_tilt() { 2 } else { 1 };
                let ((this, this_h), (other, other_h)) = dir.swap((left_hash, left_h), (right_hash, right_h));
                // Now going to merge `other` into `s`.
                assert!(other_h <= sh_orig + 1);
                let (new_other, new_other_h) = if sh_orig > other_h + 1 {
                    let mut sh = sh_orig;
                    let mut i = sp.len();
                    let mut extra = false;
                    loop {
                        verify(i > 0)?;
                        i -= 1;
                        sh -= if sp[i].1 == dir.opposite_tilt() { 2 } else { 1 };
                        if sh <= other_h + 1 {
                            if sh == other_h + 1 && sp[i].1 == dir.same_tilt() {
                                extra = true;
                            } else {
                                break;
                            }
                        }
                    }
                    verify(i == 0)?;
                    finish_subjoin(dir, other, other_h, s, sh, sh_orig, sp, extra)
                } else {
                    verify(sp.is_empty())?;
                    apply_step_with_heights(dir, other, other_h, s, sh_orig)
                };
                let ((new_left_hash, new_left_h), (new_right_hash, new_right_h)) =
                    dir.swap((this, this_h), (new_other, new_other_h));
                left_hash = new_left_hash;
                left_h = new_left_h;
                right_hash = new_right_hash;
                right_h = new_right_h;
            }
            (common_hash, left_hash, right_hash)
        }
    };
    verify(tree == expected_tree && new_left == expected_left && new_right == expected_right)
}

// Applies a join subproof, whose length must be correct.
fn finish_subjoin(
    dir: Direction,
    this: Hash,
    this_h: usize,
    s: Hash,
    sh: usize,
    sh_orig: usize,
    sp: &[(Hash, Tilt)],
    extra: bool,
) -> (Hash, usize) {
    let (hash, grow) = if extra {
        finish_insert(InsertState::Tilted(dir.opp(), sp[0].0, s, sp[0].1, this), with_samedir(dir, &sp[1..]))
    } else if sh == this_h + 1 {
        if sp[0].1 == TCenter {
            finish_insert(InsertState::Tilted(dir, this, s, dir.opposite_tilt(), sp[0].0), with_samedir(dir, &sp[1..]))
        } else {
            assert!(sp[0].1 == dir.opposite_tilt());
            (
                apply_path_samedir(
                    dir,
                    apply_step(apply_step(this, s, dir, dir.opposite_tilt()), sp[0].0, dir, TCenter),
                    &sp[1..],
                ),
                false,
            )
        }
    } else {
        assert!(sh == this_h && sp[0].1 == dir.opposite_tilt());
        (apply_path_samedir(dir, apply_step(apply_step(this, s, dir, TCenter), sp[0].0, dir, TCenter), &sp[1..]), false)
    };
    (hash, sh_orig + if grow { 1 } else { 0 })
}

fn path_height_samedir(dir: Direction, path: &[(Hash, Tilt)]) -> usize {
    let ot = dir.opposite_tilt();
    path.iter().map(|&(_, t)| if t == ot { 2 } else { 1 }).sum()
}

fn apply_step_with_heights(
    dir: Direction,
    this: Hash,
    this_height: usize,
    other: Hash,
    other_height: usize,
) -> (Hash, usize) {
    let ((l, lh), (r, rh)) = dir.swap((this, this_height), (other, other_height));
    (
        hash_internal_node(
            l,
            r,
            if lh > rh {
                TLeft
            } else if rh > lh {
                TRight
            } else {
                TCenter
            },
        ),
        lh.max(rh) + 1,
    )
}

// Join operation
// ==============

// Join operation merges two trees into one, concatenating their sequences of items. A necessary condition for that is
// that if both trees are not empty, the largest key in the first tree must be strictly less than the smallest key in
// the second tree.

pub type JoinProof = Option<(K, V, Vec<(Hash, Tilt)>, K, V, Vec<(Hash, Tilt)>)>;

pub fn join(left: Hash, right: Hash) -> (Hash, JoinProof) {
    if left == EMPTY_TREE_HASH {
        (right, None)
    } else if right == EMPTY_TREE_HASH {
        (left, None)
    } else {
        let mut left_cur = left;
        let mut left_hashes = Vec::new();
        left_hashes.push(left);
        let mut left_proof = Vec::new();
        let (left_key, left_value) = loop {
            match lookup_by_hash_node(left_cur) {
                Node::Internal { left, right, tilt } => {
                    left_hashes.push(right);
                    left_proof.push((left, tilt));
                    left_cur = right;
                }
                Node::Leaf { key, value } => {
                    break (key, value);
                }
            }
        };
        left_proof.reverse();
        let mut right_cur = right;
        let mut right_hashes = Vec::new();
        right_hashes.push(right);
        let mut right_proof = Vec::new();
        let (right_key, right_value) = loop {
            match lookup_by_hash_node(right_cur) {
                Node::Internal { left, right, tilt } => {
                    right_hashes.push(left);
                    right_proof.push((right, tilt));
                    right_cur = left;
                }
                Node::Leaf { key, value } => {
                    break (key, value);
                }
            }
        };
        right_proof.reverse();
        (
            finish_join(
                &left_proof,
                |i| left_hashes[left_hashes.len() - i - 1],
                &right_proof,
                |i| right_hashes[right_hashes.len() - i - 1],
            ),
            Some((left_key, left_value, left_proof, right_key, right_value, right_proof)),
        )
    }
}

pub fn verify_join(left: Hash, right: Hash, proof: &JoinProof, new_tree: Hash) -> VerifyResult {
    let expected = match proof {
        None => {
            if left == EMPTY_TREE_HASH {
                right
            } else if right == EMPTY_TREE_HASH {
                left
            } else {
                return Err(());
            }
        }
        Some((kl, vl, pl, kr, vr, pr)) => {
            verify(left == apply_path(hash_leaf_node(kl, vl), with_samedir(DRight, pl)))?;
            verify(right == apply_path(hash_leaf_node(kr, vr), with_samedir(DLeft, pr)))?;
            finish_join(
                pl,
                |i| apply_path(hash_leaf_node(kl, vl), with_samedir(DRight, &pl[..i])),
                pr,
                |i| apply_path(hash_leaf_node(kr, vr), with_samedir(DLeft, &pr[..i])),
            )
        }
    };
    verify(new_tree == expected)
}

fn finish_join(
    left_proof: &Vec<(Hash, Tilt)>,
    left_hash: impl FnOnce(usize) -> Hash,
    right_proof: &Vec<(Hash, Tilt)>,
    right_hash: impl FnOnce(usize) -> Hash,
) -> Hash {
    let mut left_height = path_height_samedir(DRight, left_proof);
    let mut right_height = path_height_samedir(DLeft, right_proof);
    if left_height > right_height + 1 {
        let mut i = left_proof.len();
        while left_height > right_height + 1 {
            i -= 1;
            left_height -= if left_proof[i].1 == TLeft { 2 } else { 1 };
        }
        let right = right_hash(right_proof.len());
        finish_insert(
            if left_height == right_height {
                InsertState::Center(left_hash(i), right)
            } else {
                assert!(left_height == right_height + 1);
                let (l, t) = left_proof[i - 1];
                InsertState::Tilted(DLeft, l, left_hash(i - 1), t, right)
            },
            with_samedir(DRight, &left_proof[i..]),
        )
        .0
    } else if right_height > left_height + 1 {
        let mut i = right_proof.len();
        while right_height > left_height + 1 {
            i -= 1;
            right_height -= if right_proof[i].1 == TRight { 2 } else { 1 };
        }
        let left = left_hash(left_proof.len());
        finish_insert(
            if right_height == left_height {
                InsertState::Center(left, right_hash(i))
            } else {
                assert!(right_height == left_height + 1);
                let (r, t) = right_proof[i - 1];
                InsertState::Tilted(DRight, r, right_hash(i - 1), t, left)
            },
            with_samedir(DLeft, &right_proof[i..]),
        )
        .0
    } else {
        apply_step_with_heights(
            DLeft,
            left_hash(left_proof.len()),
            left_height,
            right_hash(right_proof.len()),
            right_height,
        )
        .0
    }
}

[Longarithm]

@abacabadabacaba Thank you for the detailed explanation!

While the depth of MPT is usually small, it is possible for an adversary to make it as large as twice the length of the key in bytes, which is not good.

By "make it as large as twice" do you mean the attack where for key abcde we add keys for each prefix like aX, abX, abcX, etc.?

[abacabadabacaba]

Yes. In fact, because in MPT the keys are represented by sequences of half-bytes, an attacker can add a key for each prefix in half-bytes. For abcde, this may be 0, b, a0, aa, ab0, aba, etc. In the worst case, the path for the key abcde will consist of 11 nodes (10 branch nodes and one leaf node).

[mm-near]

This is a very nice idea @abacabadabacaba - especially the AVL guarantees in the worst case scenario.

One thing that you didn't cover here (but you mentioned it during VC) - is how to optimise disk reads (if we do one read per 'level', we might end up being far slower than MPT - that has less levels).

For (5) - split and join - what kind of splits are you thinking about? the ones related to dynamic sharding?

Also - did you think about how the migration from MPT could look like? (I wonder how long would it take to move the current MPT-based storage into AVL - and whether we should do it in one go - that is during one epoch or do we have to stretch it for longer)

What are the next steps with this idea? should we implement it and run some performance comparison with the current MPT ?

[abacabadabacaba]

Optimizing low level details such as disk reads is a subject of a different discussion: #4326. It currently doesn't address the optimization that you are talking about, though. The rough idea is to store nodes in "clusters", where each cluster holds a node and its descendants up to a certain depth, and the children of the nodes in a cluster which are themselves not in that cluster will be roots of other clusters. The depth cannot be the same everywhere, though, because of the rotations.

Another important optimization is to keep the current state in a "flat" format, where the state keys are also the keys in the low-level storage, so that the reads don't need to traverse the tree at all. With this optimization, it will only be necessary to traverse the tree when updating the state, but this can be efficiently parallelized because the entire set of changes is known in advance.

Also, it is possible that sometimes an MPT will have more levels than an AVL tree even in non-adversarial scenarios. Even though each branch node in an MPT can have up to 16 children, in practice many of them have fewer, and the choice of keys (which contain human-readable strings such as account IDs) may result in a suboptimal tree structure.

Regarding the splits: yes, they are for resharding (dynamic or not).

The migration can happen similarly to how we are currently migrating to multiple shards: nodes are building a version of the state in the new format in parallel, and then they start including a new state root in the chunks.

The next step after writing the entire description will be to write a specification. We can write some prototype implementations as well, but we should implement optimized low level storage (#4326) before the real implementation. We want it anyway, so it doesn't make much sense to measure the performance using the current low level storage.

[abacabadabacaba]

One note about using AVL trees for the state: Cosmos tried to do it and then they switched away from it. Relevant discussions: cosmos/cosmos-sdk#7100 and cosmos/cosmos-sdk#8297. In those discussions, I couldn't find any fundamental reasons which would make AVL trees unsuitable (or poorly suitable) for our purposes. So far, I don't think that their experience is a reason for us to not pursue the approach of using AVL trees for the state.

[ilblackdragon]

I'm curious what are other alternatives that were considered and how AVL tree would compare to them?
E.g.

• Urkel: https://github.com/handshake-org/urkel
• Sparse Merkle Tree: https://github.com/celestiaorg/smt
• Binary merkle tree with read/write optimizations @SkidanovAlex or trie https://eips.ethereum.org/EIPS/eip-3102

Separately would we change layout of the contract data vs account data as part of this change? e.g. currently contract data is stored with prefix of account. That indeed makes hashed keys complex to reshard but there are ways to address this by changing layouts.

[abacabadabacaba]

Urkel tree is similar to an MPT, but is radix-2 instead of radix-16. This makes the proofs smaller, but the maximum depth even greater. They work around this problem by using hashes as keys, but this is still susceptible to key grinding attacks, so AVL tree's guaranteed maximum depth is significantly less.

The implementation of Urkel tree also includes its own low-level storage, which is more efficient than RocksDB, but the choice of low-level storage is orthogonal to the choice of tree structure.

Sparse Merkle Tree: also a radix-2 tree, but instead of compressing every node with a single child, they only compress nodes with a single descendant leaf. This makes them even more susceptible to key grinding.

EIP-3102: also similar to an Urkel tree. Most of the alternatives are very similar, even if they come by different names. The only alternatives that are substantially different are those based on self-balancing trees (such as AVL trees) and Verkle trees, but Verkle trees rely on trusted setup (and much more complex cryptography) and so we don't want to use them.

AFAIU, @SkidanovAlex's optimizations can be used with any tree structure, as they belong to the low-level storage.

[pmnoxx]

@abacabadabacaba I think it would be a good idea to write list of mathematical properties the structure you propose has.

Algorithm properties:

• reversible - by doing operations add/remove in reverse, can you get the same structure back

From my experience with debugging issues with Redis, MySQL, LevelDB'. The database design is heavily influenced by the technical limitations. If all storage was as fast as memory, their designs would have been much easier. Redis` for example, if all it did was to provide data structures, and not care at all about data preservation, would be just a single in-memory library. Anyway, I'm curious on how the following implementation details are solved:

implementation properties:

• disk optimized - is it optimized for disk read/writes. Typically, disk read/writes operate on blocks of size 4kb. Any read less than that, will occur penalty, of writing full 4kb data.
• corruption free - will any panic in the program cause corruption of the database, how do you handle error recovery. power goes down, etc.
• atomic - disk writes larger than 4kb, are not atomic, writing larger keys, and if the process gets killed, may cause database corruption
• grow-able - how are you going to manage the data on disk, resizes, etc.

[abacabadabacaba]

AVL tree is not reversible: there may be multiple valid tree structures representing the same data. Adding an item and then removing it may result in a different structure.

The other properties that you mention are provided by the low-level storage. You may look at #4326 for a current proposal, and post any questions there.

[pmnoxx]

@abacabadabacaba Anyway, I think that AVL tree is a valid solution. We should try to make a prototype, even not fully implemented, but enough to judge performance. To see, whenever that solution is good enough performance wise. I would be happy to help you with that. Share, any useful suggestions, etc.

[zeech3]

@abacabadabacaba Calculate the merkle root hash on the AVL tree, whether it will be different according to the put order of keys?

E.g [1,2,3,4,5] and [1.3.4.5.2], the merkle root hash of this two AVL tree will be same?

[yihuang]

@abacabadabacaba Calculate the merkle root hash on the AVL tree, whether it will be different according to the put order of keys?

E.g [1,2,3,4,5] and [1.3.4.5.2], the merkle root hash of this two AVL tree will be same?

it won't be the same, in cosmos-sdk, the writes are buffered and sorted before commit into iavl tree, so there's a canonical order of modifications to the tree.