This paper provides a comprehensive overview of Merkle trees and their numerous extensions, which are fundamental data structures for ensuring data integrity and authenticity. Beginning with the foundational principles of k-ary Merkle trees, including their construction, membership proof generation, and verification processes, the article systematically explores a wide range of advanced variants. Key extensions such as Sparse Merkle Trees (SMT), Indexed Merkle Trees (IMT), Verkle Trees (VT), and Radix Merkle Trees (RMT) are detailed, alongside specialized implementations like the Merkle Patricia Trie (MPT) and Jellyfish Merkle Tree (JMT). The survey also investigates various optimization techniques aimed at improving storage efficiency, reducing membership proof size, and modifying the underlying logic. The paper concludes with a comparative analysis of these structures, evaluating their algorithmic complexities, trade-offs, and suitability for different applications, thereby serving as a guide for selecting the optimal Merkle-based construction for specific use cases like blockchain, cloud storage, and digital signatures.
A Merkle tree was first proposed in [
One can aggregate the quorum of public keys into one root value with the ability to prove
the membership of the particular public key later [
One can check whether a blockchain transaction is included in the block or not [
One can confirm the authenticity and the integrity of outsourced data or data block without
the local copy of data files [
Users can be identified and verified on the IoT in the blockchain network 8[
One can check whether the data is properly stored in a cloud drive [
0009-0006-3648-9057 (V. Dubinin); 0009-0004-3588-8617 (Y. Panasenko); 0009-0004-9373-0519 (S. Volynets);
0000-0003-4051-1190 (V. Zhebka); 0009-0006-1781-4109 (D. Nishchemenko)
For the most of the mentioned usages, security is necessary. The tree’s digest computation function
must be irreversible and collision-resistant to make the forging of a tree node by the owner or
third-party adversary improbable, preventing money and/or privacy loss [
This paper aims to give a comprehensive overview of existing constructions of a Merkle tree and its modifications for different usages.
2.1. Trees The structure of a Merkle tree is based on the structure of a regular tree, so it is better to start with general definitions and properties of a tree to feel confident before going to a Merkle tree.
Definition 2.1 (Graph). A graph G is a tuple G = (V, E), where V is a set whose elements are called nodes, and E = V × V is a set of pairs (v1, v2) of nodes, whose elements are called edges. The graph G is unordered, if all the edges have no direction, i.e. the existence of edge (v1, v2) implies the existence of edge (v2, v1), otherwise, the graph G is called an ordered graph. For the node, v1 the directed edge (v1, v2) is called the outgoing edge, and for a node v2, the edge is called the ingoing edge. The graph has an order annotated as |G|, which is the number of nodes in a graph, i.e. |G| = |V|. For the node v in an undirected tree, the order of the node v is a number of edges (v, u), where u ∈ V. If the tree is ordered, then the order of a node is a number of all edges (v, u) and (w, v), where u, w ∈ V.
Definition 2.2 (Tree). A tree T is a connected and acyclic graph, i.e. there is an undirected path between any pair of vertices and there is no non-empty path from any node to itself without repeated edges. The leaf in a tree is a node with only one edge, i.e. node of order 1.
Definition 2.3 (Perfect k-ary tree). A perfect k-ary tree is a tree of some height h with kh leaves, with non-leaf nodes, which have exactly k child nodes each.
If we have an ordered graph G, we can define the source node v as a node with only outgoing edges, and the sink node as a node with only ingoing nodes. For a directed tree T, a sink node is a leaf node, and the source node is a root node. There exists only one root in a directed tree. The height of the tree T is the maximum length of a path, i.e. the maximum number of edges, from the root to any leaf.
The next thing worth mentioning is that there is a hierarchy, sometimes described in levels. We will say that the root is located on the 0-th level. Then, we have inner nodes and at the end of each branch, we have leaves. If the tree is perfect, then leaves are located on the last layer. One can use definitions of the parent node and child node to describe hierarchical relationships between two adjacent nodes u and v. Let the node u be located on a n-th level. If the node v is located on level (n + 1), then the node v is a child node of u and u is a parent node of v. It is well known that the root has no parents, and leaves have no children.
A Merkle tree is constructed from data digests. These digests must be small enough to be stored efficiently while also providing security for the tree's construction. Cryptographic hash functions are excellent candidates for this purpose.
Definition 2.4 (Cryptographic Hash Function). For a function to be considered a cryptographic hash function H : 0 , 1∗ →0 , 1 n , it must satisfy three fundamental security properties that are critical to the integrity of data structures such as Merkle trees.
Preimage Resistance: This property guarantees that the function is one-sided. For any given hash output y, it must be computationally infeasible to find any input messagex' for which H(x′) = y.
Second-Preimage Resistance: For a given input value x, it must be computationally infeasible to find another, different input value x' where x≠ x ′ that generates the same hash, i.e. H(x) = H(x′).
Collision Resistance: This is the strongest property that makes it computationally infeasible to find any pair of distinct inputs x and x' that result in an identical hash output H(x) = = H(x′).
In the context of Merkle trees, collision resistance is of paramount importance [
The hash function can be applied for any string. However, to compute the hash of a set of strings si, i= 1 , k we compute the hash of the concatenation of that strings, i.e. hash = H(s1||s2||...|| sk) or simply hash = H(s1, s2, ..., sk) or even hash = H(si| i= 1 , k). It is important not to forget that the order of concatenation affects the final result.
Hash functions aren't the only method for computing digests. An alternative approach involves
using vector commitment schemes [
Hiding: The commitment should not reveal any information about the message it contains. Specifically, an observer should not be able to distinguish whether a commitment was created for a message m or a different message m', where m≠ m′.
Binding: The commitment mechanism must prevent the sender (S) from changing her mind about the committed message m after the fact.
More precisely, the binding property requires an efficiently verifiable opening procedure. This allows anyone to quickly check that the opened message is the one S originally committed to. Thus, a commitment scheme typically involves two phases:
Commit Phase: A sender (S) creates a commitment (C) for a message (m) using a specific algorithm.
Decommit Phase: The sender (S) reveals m and “convinces” a receiver (R) that C is the valid commitment to m.
A single commitment can be created for a vector m that contains several messages. Then, during the decommit phase, S can open just one element of the vector m at a time. A commitment scheme is considered non-interactive if each phase requires only a single message from S to R.
In general, the structure of the Merkle tree (sometimes named the Merkle hash tree) is similar to an
ordinary tree. Authors and researchers define a Merkle tree differently. That is why the definition
of the Merkle tree varies from article to article. Moreover, some Merkle tree definitions were
different enough to have separate names.
Here, we define a simple and general Merkle tree using [
Definition 3.1 (k-ary Merkle tree). An k-ary Merkle tree T = ⟨V, E⟩ is a construction that has leaf nodes, internal nodes and a root, which are as follows: 1. Leaf nodes contain the direct hash value of data blocks. 2. Internal nodes contain concatenation of k hash values of its k children. 3. Root node is an internal node that has no parents.
The k-ary Merkle tree T = ⟨V, E⟩ is a tree with the next properties: 1. It is a rooted tree. 2. All the leaves are located on the same level. 3. Each inner node has exactly k children. 4. Duplicated vertices are allowed to meet restrictions. 5. The set of children nodes is ordered set, so digest can be calculated correctly.
Fig. 1 provides an example of a perfect binary Merkle tree. In contrast, Fig. 2 displays a nonperfect Merkle tree, illustrating how duplicated nodes are used to calculate the final root hash. In the Figs. 1 and 2, we can see the main idea of the Merkle tree. Let’s assume that we compute the digest in a root. Because the digest in the root node depends on all the digest in leaves, any slightest change in any leaf digest changes the digest in a root. So, if we have the digest in a root, then we can check if any change is done. One can use it to prove that the element is in a tree, i.e. there is a leaf node with the element digest in it.
Here is an example of proving data block 2 membership for the tree in Fig. 1. As the hash of the searched data block is stored in node 2, we can give the proof consisting of two hash values: h1= H(D 1) from node 1 and h6 = H(h3||h4) from node 6. To check the proof, we first calculate the hash in node 2 as h2 = H(D 2) using data D 2 that we know. It is also an option to store the hash h2 and not have the data D 2. Then we calculate h5 = H(h1||h2), the hash value of the concatenation of node 1 and node 2 hashes, which gives us the hash of node 5, and then calculate h7 = H(h5||h6), the hash of the concatenation of node 5 and node 6, which provides us with the hash value in a root. To decide if the data is in the tree, we compare the computed hash in the root node h7 with the real hash in the root hroot (hroot is the hash we computed previously or get from the trusted source). If the computed hash in the root matches the real hash in the root, i.e. h7 = hroot, the hash of the data is in the tree, otherwise, it is not. However, with negligible probability, it can match without the data inclusion, and the verification procedure will give a false positive result.
If a malicious Prover wants to prove data block 2 inclusion if it is not in the tree, then the Prover must find such hashes of block 1 and block 6, that H(H(h1||h2)||h6) = hroot. So the Prover needs to find a preimage ofhroot or H(h1||h2) of the hash function H, but we assumed before that the H is preimage-resistant. Another way for a malicious Prover to forge the node is to find a second preimage D 2 ′ for D 2, such that H(D 2 ′) = H(D 2). Then the Prover can claim that the data D 2 ′ is in the tree, however it is not. The malicious creator of a Merkle tree can forge the node from the start by searching any collision D 2 ′ and D 2 ′ ′ with the same hash, and then claim different statements: the data D 2 ′ is in a tree and the data D 2 ′ ′ is in a tree. Such manipulation of an adversary is a reason of using the cryptographic hash functions that have appropriate security properties.
The Binary Merkle Tree (BMT) is one of the most commonly used structures among k-ary
Merkle trees. There are other named k-ary trees. For example, Ethereum’s blockchain utilizes a
Patricia-Merkle tree with up to 16 child nodes [
The node of a Merkle tree contains references to its children and the digest. The main part of a Merkle tree that we need to remember is the hash in the root. However, sometimes it’s also important to store hashes of leaves. If the memory isn’t strictly limited, and it is possible to store all the nodes, it might be reasonable to append other fields. For example, nodes can have an additional field parent, which is undefined for the root node. For even more convenience, every node can have a boolean flag that states whether the node is the left child. For the root, the flag is undefined. Those fields can aid in constructing algorithms to make them more readable and fast. In our approach, we assume that all the fields are present unless otherwise specified.
Using notation in [
Author of [
Algorithm (alg. 1) is a pseudocode that creates a k-ary Merkle tree from an array of values. It will store the whole tree in the memory. It uses an additional function pad_list(nodes, k) which, for the given set of nodes with cardinality divisible by k, returns the given set of nodes, or else, returns the given set with a duplicated last node at the end to make the cardinality of the set divisible by k. If k= 2, function pad_list(nodes, 2), ensures that the set nodes cardinality is even. It isn’t necessary to duplicate all the node’s descendants in the pad list function. We need a divisible by k amount of hashes, so we can duplicate only a hash instead of a node.
The most resource-consuming operation in the tree creation is hashing. For a perfect binary tree with n leaves to compute the first layer of nodes, we will compute n hashes, for the next n , and so on.
Therefore, the time complexity of Merkle tree creation is For the perfect k-ary Merkle tree, the claim is similar.
T ( n) ≈ n+ n + n2 + ...+ 2log(n)< 2 n
2 2 T ( n) ≈ n+ n + n2 + ...+ klog k(n)< 2 n k k (1) (2) Algorithm (alg. 1) is inefficient in terms of memory complexity. To be precise, it stores n leaf nodes, which contain one hash each, and O(n) inner nodes, which contain one hash and k + 1 pointers. It is useful to know that the height of an k-ary Merkle tree is logk(n). For a binary Merkle tree, the height is log2(n). It is quite obvious that trees with a bigger arity are shorter and have fewer nodes. Unfortunately, it doesn’t affect the algorithms a lot. The main effects are implementational.
Appending of a new element, i.e. appending of a leaf, can be accomplished by a complete rebuild of the tree. Then, the complexity of appending a new element to the tree equals a new tree creation. In other words, complexity is O(n) hashing. However, there is a solution to the problem. We can mark duplicated nodes. If we have a marked leaf, swap it with the new element. If we have a duplicated inner node, we must swap it with a new node with the new leaf in its descendants; that is more complicated. If the tree is full and no duplicate nodes are left, then we increase the tree’s height by changing the root. The root becomes an internal node. In theory, the appending of a new element leads to the recalculation of the root. The appended element affects only one node on each level, so it should require O(logk(n)) hashing operations.
As was said before, it is possible to create a proof of element membership for the Merkle tree. There are different ways to prove data inclusion. The first is through some equality verification (let’s name it “verifiable proof”), and the second is through the direct search of the element in the memory (let’s name it “searching proof”).
The first type of proof that was already mentioned (“verifiable proof”) is a membership proof,
which is a set of pairs of hash (hashes) and direction ({(hi, di)|i= 1 , k}). It might be helpful to
append node parameters or other information to the proof to see what we are proving in more
detail. For example, it is possible to append a version of a tree to the proof [
The “verifiable proof” is a membership proof for one data block. However, if we combine several
proofs for some nodes, we will get proof of membership for a set of nodes named ranged existence.
In [
Authors of [
Algorithm (alg. 2) is a pseudocode for “verifiable membership proof” generation for a binary Merkle tree. Firstly, it searches for the required element by searching over the set of leaves, which, unfortunately, is unsorted. The search requires O(n) comparison operations. When the node is found, the algorithm (alg. 2) searches for the corresponding hash values in O(log2(n)) operations to generate membership proof. Because all hash values are already calculated, the last complexity is also evaluated in comparison operations. In a binary Merkle tree, a membership proof (per Algorithm 2) consists of a set of pairs. Each pair contains a hash value and a positional indicator specifying whether the hash should be concatenated from the left or right. Consequently, the size of such a proof is on the order of O(log2(n)). For a k-ary Merkle tree, proof construction methodologies differ, primarily in the structure of the proof elements. Consider a verifier who, at a given step, holds a hash hi and needs to compute its parent hash, defined ash = H(h1, h2, ..., hi, ..., hk). The proof must supply all sibling hashes of hi.
One efficient approach is to structure the proof element as a pair of concatenated strings: A left-side string: l = h1||h2||...||hi−1 A right-side string: r = hi+1||hi+2||...||hk
In this model, if hi is the first element (i=1), the left string l is empty. Likewise, if hi is the last element (i=k), the right string r is empty. To proceed, the verifier computes the parent hash using the received elements as H(l||hi||r).
The other way is to represent the step of the proof like a whole set of additional hashes and an id of position, where the hash from the previous step must be concatenated. The first strategy requires less space because there is no id in it, and has less complexity to verify because we don’t have to find appropriate places to put the hashes. However, both strategies have the same time complexity. The size of the proof for k-ary Merkle tree is O((m − 1)logm(n)). Algorithm (alg. 3) shows the second approach for an k-ary Merkle tree membership proof cration.
Algorithms (alg. 4), (alg. 5) that checks membership proof uses hashing operation. For the k-ary tree, algorithms will perform (k − 1) logk(n) hashing operations. So the complexity of verification of membership proof is O((k − 1) logk(n)), where n is the number of elements in the tree.
As previously established, numerous definitions and variations of Merkle trees exist. Merkle trees and their extensions can be categorized based on several key characteristics:
The tree structure is not necessarily binary. It can be designed as a generic k-ary tree, where each internal node has at most k child nodes. Implementations such as binary (k=2) or 16-ary (k=16) trees are common.
The tree's topology may be perfect or imperfect, as well as balanced or unbalanced, depending on the specific application and construction algorithm.
The overall structure can be either static (constant) or adaptive, dynamically changing in response to data modifications.
The digest function itself can be customized. This includes variations in its input parameters or the computational logic used to produce the hash output.
The tree may incorporate specialized node types beyond the standard leaf and internal nodes to support extended features.
The fundamental tree can be augmented with additional data substructures to provide enhanced functionality.
A Sparse Merkle Tree (SMT) [
Remark. Sometimes (like in [
To create an empty k-ary sparse Merkle tree of height h, one can use pseudocode (alg. 6), where the input size must be equal to kh, where k, h ∈ N, k ⩾ 2. If we are using SHA-256, We can have sizes 2256 (k = 2, h = 256), 4128 (k = 4, h = 128), etc.
Appending a new leaf here means changing the existing leaf hash because the structure has already been created, and updating the tree. The algorithm for appending a new element is much simpler than the one for a binary Merkle tree because we know where the new node must be, and there is no need to rebuild the entire tree or find an empty place. To find a leaf algorithm, use O(1) operations. To update the tree, we need to update the leaf, the changed leaf’s parent and its parent, and so on. If we use pointer parent in all the nodes, then it is a trivial task. If we save all the nodes using the mentioned notation, then, if we change leaf, we N ij know that its parent node is node N ji− 1 (or in other words children of a node N ij is node N kji++1a , a= 0 , k − 1).
[ k ]
The algorithm of membership proof generation for sparse Merkle tree is similar to (alg. 3) for kary Merkle tree proof generation. The only difference is the search of a node. The size of the membership proof is also the same as for a k-ary tree, i.e. O((k − 1) logk(n)). Verification of the membership proof has no change compared to (alg. 4). However, if the hash of a leaf is computed as H(id||data), then it is reasonable to attach the id of a node to the proof and use the right hash value for the proof verification at the beginning.
For a sparse Merkle tree, there is also a method of proving element exclusion. The check of the exclusion is the same algorithm as the check of inclusion because if the element exists, we know the id of the leaf where the hash of the data must be located. Therefore, if the algorithm (alg. 4), for the SMT proof, returns True, then the element exists, and if the algorithm returns False, the element doesn’t exist.
An Indexed Merkle tree is a Merkle tree, extended with additional structure [
Algorithm (alg. 7) is presented in the form of a pseudocode for creating a new empty k-ary
indexed Merkle tree with a predefined height. It is pretty much the same as the other tree-creation
algorithms ((alg. 1), (alg. 6)). The only difference is the arguments for leaf creation are different (like
with sparse Merkle trees).
Appending a new value requires finding the leaf in O(n) comparison operations in a sorted linked
list, and then two updates of the root in O(log2(n)) operations of finding hash values for each
update.
There is an algorithm for appending multiple leaves at once for the indexed Merkle tree. It is the
most efficient when we append the sorted set of values [
Algorithm (alg. 9) for the membership proof generation is similar to previous algorithms but has some differences. The main difference is the additional return values. We need an algorithm to return the set of searched node values because the hash value of a node isn’t only the hash of a value but a hash of the concatenation of node values: val, nextId, nextVal. We can’t know the last two values beforehand, unlike the id in a space Merkle tree.
Algorithm for generating membership proof (alg. 9) [
Verkle Tree [
Radix Merkle is built on top of the Merkle tree but with a different goal. For more, it uses “search proof”. However, as said before, is possible to use both types of proof.
The difference between the Merkle tree and the radix Merkle tree is described in Fig. 3. The
Radix Merkle Tree [
It is common to use the 16-ary radix Merkle tree. Because every inner node has 16 = 24 child nodes, we can name every child node with a hexadecimal digit. Because every symbol takes exactly 4 bits, it is common to use nibbles.
Definition 4.1 (Nibble). A nibble refers to four consecutive binary digits or half of an 8-bit byte.
The term nibble is used to describe a child of a node, and so to define a path from the root to some leaf. Radix tree has a different proof format that uses nibbles. The membership proof is a radix path from the root to the leaf. In other words, the radix path is just an ordered set of directions to the next nodes, i.e., nibbles. We can concatenate those hexadecimal digits into one hexadecimal number representing the path.
The main advantage of a radix tree [
Authors of [
The Relative Index and Time Stamped Merkle Hash Tree (RITS-MHT) is a data structure proposed
in [
Merkle Patricia tree (or Merkle Patricia trie) [
Ethereum requires a tree data structure that can quickly recalculate a tree root after an edit, insert, or delete operation. The tree root must depend on the data and not on the order in which updates are made. Note that regular Merkle trees do not satisfy this requirement. Furthermore, the data structure must prevent Denial-of-Service attacks where malicious attackers may craft transactions to make the tree as deep as possible and, hence, slow updates. To stop this, the data structure must have bounded depth.
In The Merkle Patricia Tries, proof of membership, i.e., key, is encoded using a special
HexPrefix (HP) encoding [
Jellyfish Merkle Tree [
Version-based Node Key. JMT chooses a version-based key schema with multi-fold benefits: Facilitating version-based sharding. Greatly lowering compaction overhead in LSM-tree (Log-Structured Merge-tree) based storage engines such as RocksDB. Smaller key size on average.
Less Complexity. JMT has only two physical node types, Internal Node and Leaf Node. Ex- tension node is removed, because it is unlikely for two paths to share a long common part of the path.
Concise Proof Format. The number of sibling digests in a JMT proof is less on average (Θ(log( number of existent leaves))) than that of the same A(S)RMT without optimizations (Θ(log( number of maximum leaves))), i.e., the height of the equivalent A(S)MT), requiring less computation and space.
Authors of [
In some cases, using Merkle trees to compute digest, i.e. the hash in root, there is a need to
duplicate the node. Authors of [
A sparse Merkle tree is a big mathematical structure, so despite being fast, sparse Merkle trees need a lot of memory because there are a lot of empty nodes, so, there is a necessity to use some memory-saving strategies.
The problem with memory can be solved by associating the empty subtree, i.e. subtree without
non- default leaves, with one node with some default hash [
Another way to save memory for a sparse Merkle tree is not to save inner nodes hash in the
memory, because it is possible to calculate them when needed using leaf hashes. There is an
algorithm, TREEHASH [
To find a compromise between time and space, authors of [
Average membership proof size improvement. In [
Verkle Trees (VT). As was said before, Verkle Trees has a small membership proof because they use committing instead of hashing. That, reduce the proof size from O(k logk(n) to O(logk(n), by the price of computations. There is no problem with implementing that strategy in sparse Merkle trees, indexed Merkle trees, or even in radix Merkle trees.
The Odd and Even Merkle Hash Tree (O&E MHT), proposed in [
Notably, this construction does not reduce algorithmic execution time; on the contrary, it
increases the overall complexity of the implementation. The Modified Merkle Hash Tree (MMHT),
also presented in [
There are some problems with MMHT. The main of them is the time to get to the first blocks. The less the sequence number of the block, the bigger the time is. Because of that, for the first blocks, the proof size is bigger, the modification time is bigger, etc.
In article [
All the mentioned trees have different constructions, use cases, and complexities. Table 1 describes the main advantages and disadvantages of those constructions.
Faster insertion and deletion compared to k-ary MT, support nonmembership proof.
Faster insertion and deletion compared to k-ary MT. Can be built on top of an existing linked list. Has a smaller downgrade for appending multiple elements at once than SMT.
Short proofs, so faster proof exchange and proof verification.
Disadvantages Average speed.
Requires a lot of memory (leaf for every possible output of the hash function).
Slow search of node, which can affect the speed of membership proof creation, element insertion, etc., when the tree is nearly full.
Hard creation and insertion because of the use of vector commitments instead of hashes.
Short proofs, and even shorter proofs for proofs with multiple nodes with a common path.
Complex implementation, memory inefficient.
Theoretical results of the complexity of the main algorithms, i.e. new element insertion, membership proof generation and verification are shown in a table 2.
In Table 2, “h.” means complexity in hashing, and “c.” means complexity in comparisons. There are two exceptions. VT uses a commitment function instead of a hashing and RMT uses a comparison function instead of hashing. MP search means MP creation while the whole tree structure is available
O(k log_k(n)) O(k log_k(n)) O(k log_k(n)) O(log_k(n)) O(k log_k(n)) nibbles
O(k log_k(n)) O(k log_k(n)) O(k log_k(n)) O(k log_k(n)) O(k log_k(n)) Tree type k-ary MT k-ary SMT k-ary IMT k-ary VT k-ary RMT tree size (nodes) Creation (h) Inserting (h) Node search (c) MP search (c) MP creation (h) NMP search (c) NMP creation (h) MMP verification (h)
O(n) O(n) O(n) O(n) O(n) MP verification (h) O(k log_k(n)) O(k log_k(n)) O(k log_k(n)) O(log_k(n)) O(log_k(n)) c O(n) O(n) O(1) O(n) O(n) O(log_k(n)) O(n) O(log_k(n)) O(n)
O(n) O(n) O(n) O(n) O(n) O(k log_k(n)) O(k log_k(n)) O(log_k(n)) O(log_k(n)) c
O(n) O(kn) O(n) O(n) O(n) O(n) O(n)
O(n) O(n) O(1) O(1) O(1) c.
O(1) O(1) c. There are a lot of Merkle tree constructions for different purposes. They have their pros and cons. If we need a simple tree implementation, then the best choice is the sparse Merkle tree (SMT). If the purposeof a tree is to have short proofs for big bandwidth, then the best choices are the Verkle Tree (VT) and the radix Merkle tree (RMT). If the purpose of a tree is to store a huge amount of data, then the best choices are sparse Merkle tree (SMT) and indexed Merkle tree (IMT). If we are constantly modifying the tree, or we need fast proofs having nearly unlimited memory on a Prover and Verifier side, then the best choice is the radix Merkle tree (RMT). And finally, if we are lacking in memory, then the standard Merkle tree could be the best choice. For the best performance, it is better to implement the mentioned in a section 5 improvements if possible.
While preparing this work, the authors used the AI programs Grammarly Pro to correct text grammar and Strike Plagiarism to search for possible plagiarism. After using this tool, the authors reviewed and edited the content as needed and took full responsibility for the publication’s content.