16
$\begingroup$

It seems that merkle hash tree (MHT) traversals have been discussed somewhat in the literature, but there does not appear to be much written on inserting, deleting, and updating leaves. Is this lack of material regarding updating MHT's possibly due to the fact that the data (e.g. one time signatures) hashed to form MHT leaves, get typically distributed prior to any possible updates, making it hard to recalculate the verification paths of already distributed leaves?

The trivial insert operation (see Fig 2 below) increases the height of the tree linear in the number of inserts requiring comparatively larger proofs for inserted items, but keeps re-hashing to $\log n$ hashes. The ideal insert operation (see Fig 3 below), keeps optimal height, but depending on where insertion occurs, can require a full tree re-hash.

So, given a merkle tree with the following properties:

  • $n$ ordered data items hashed only at the leaves, where $n=2^b$ and $b$ is a positive integer
  • height $h=\log n + 1$,

Is it possible to design efficient algorithms for insertion, deletion and updates of leaves, where

  • the number of re-hashing operations performed as a result of any operation is within a (smallish) constant factor of $\log n$,
  • the proofs for any data item remains within a (smallish) constant factor of $\log n + 1$
  • there are no orphans unless $n$ is odd, in which case the last item is an orphan
  • the data items remain ordered
  • the tree is kept as balanced as possible?

If so, what would these algorithms look like?

I am assuming the canonical binary tree flavor of MHT's but if other n-ary versions provide greater flexibility without increasing the proof size too much then I would appreciate reading about them as well.

Example diagrams of the problem are shown below, showing insertions of leaf 0 at the start. Nodes requiring recalculations are in blue.

Original Fig.1 Original Tree.


Trivial insertion of data item 0

Fig. 2 Updated tree resulting from trivial insertion of leaf 0. Blue shaded nodes require re-hashing.


Ideal insertion of data item 0

Fig. 3 Updated tree resulting from ideal insertion of leaf 0. Blue shaded nodes require re-hashing.


Please note this question has been updated to make it a little more precise and clearer, whilst preserving the essence of the original question.

$\endgroup$
4
  • $\begingroup$ The basic variant of merkle trees is only efficient for leaf replacements and appending to the end of the dat, but not efficient insertions/deletions in the middle. But there are other hash tree constructions that allow efficient insertions. $\endgroup$ Jan 30, 2015 at 11:07
  • $\begingroup$ @CodesInChaos Ok that sounds good, but if you could expand further that would be great... $\endgroup$ Jan 30, 2015 at 11:12
  • $\begingroup$ It seems that this is an active area of research, fro example in this paper: tamperevident.cs.rice.edu/papers/paper-pad.pdf the authors try to build a tree for which the hash will be the same whatever the insertion order. $\endgroup$
    – agemO
    Dec 2, 2019 at 8:07
  • $\begingroup$ @agem0 The link is broken. I believe the new link is: static.usenix.org/event/sec09/tech/full_papers/crosby.pdf . And also some slides related to the paper: handouts.secappdev.org/handouts/2016/Dan%20Wallach/… $\endgroup$ Jul 8, 2022 at 13:05

2 Answers 2

8
$\begingroup$

Updating a Merkle hash tree is trivial. For instance, if you want to update a leaf, then you update it and then update every node on the path from it to the root. If you have a particular operation on the tree in mind, the necessary updates follow immediately from the kind of update you want to do. It's all very straightforward. There's no reason to expect people to publish papers about this topic in general: it seems too obvious to count as novel, publishable research.

If you are worried about ensuring that the tree remains balanced or that the height remains logarithmic in the number of nodes, you can use any of the standard schemes for balanced binary trees: e.g., AVL trees, red-black trees, splay trees, 2-3 trees, and so on. You can use any of them with a Merkle tree. The balanced binary tree data structure describes how you modify the tree on each operation. The Merkle tree structure adds extra hashes.

Note that there are many standard schemes for balanced binary trees that ensure that all of the basic operations can be done in $O(\lg n)$ time, and ensure that the height of the tree is always bounded by $O(\lg n)$. Take any of those schemes; it is easy to see that updating all of the Merkle hashes can be done in $O((\lg n)^2)$ time (for each node that is touched, you might potentially need to update the hashes in it and all nodes on the path from it to the root; because of the bound on the height, this means changing at most $O(\lg n)$ hashes per node that is touched). For many of those schemes, if you analyze them more closely, you find that updating all of the Merkle hashes can in fact be done in $O(\lg n)$ time (because the nodes they touch are all closely related, say, are all on the path from some leaf to the root, or something close to that).

Therefore, you can combine standard balanced binary tree data structures with Merkle hashing to get a Merkle hash tree that can be efficiently updated. Again, no reason to expect this to lead to lots of publications in the literature: it is combining two standard ideas, and so not terribly novel and thus not likely to lead to lots of publishable papers.


Based on the comments, I realize there is something else I should explain. In most applications, the exact shape or structure of the Merkle tree is unimportant. For most applications, all that matters is the set of values that are in the leaves of the tree, and that the height be not too large (say, $O(\lg n)$, where $n$ is the number of leaves). For those applications, balanced binary tree data structures are fine.

For instance, a typical use of a Merkle tree is as an authenticated set dictionary structure: a data structure that holds a set of values. The order in which those values appear in the internal data structure doesn't matter; all that matters is, for each possible value, whether it is present in the set or not. Thus, there is no requirement for the values in the leaves to appear in any particular order -- you can store them in any order you like, and an insert operation can add a new value anywhere in the tree.

More generally, we could imagine some application that cares about the set of values in the leaves and additionally requires they be ordered in some order (say, the values are in increasing order, if you traverse the leaves in left-to-right order). This too can be accommodated with balanced binary trees. Notice that such an application still doesn't care about the exact shape or height of the tree, as long as the leaves are in proper order and the height is $O(\lg n)$.

Now if hypothetically we had some application where the exact shape of the binary tree was essential, and each insert operation had absolutely no freedom or flexibility about the shape of the modified tree, then that'd be a different situation. In that case, standard balanced binary tree data structures would be inapplicable, because they fundamentally need some flexibility in the allowable shapes of the tree. However, this kind of requirement seems to be extremely rare in practice, and it's not clear what the motivation for it would be. Therefore, you shouldn't be surprised if there aren't many, or any, published papers that address this odd variant of the problem.

From your comments, it sounds like you are imposing a requirement that is stronger than it needs to be. It sounds like you are implicitly assuming that the Merkle tree needs to be fully packed at all times, i.e., that it's height needs to be exactly $\lg n$ at all times (plus or minus 1), where $n$ is the number of leaves. However, there's no need to impose this restriction. For practical applications, a slightly weaker condition is perfectly adequate: if we can guarantee that at all times the height of the Merkle tree will be $\le 2 \lg n$, that is perfectly sufficient.

And this weaker condition is what allows operations to be efficient. If you look at standard balanced binary tree data structures, they ensure that the height of the tree is $O(\lg n)$ at all times (or some similar invariant). This provides a degree of flexibility regarding the shape of the tree: it doesn't have to be fully packed. This relaxation is what allows balanced binary tree data structures to be efficient (including to efficiently implement the insert-at-front operation you mentioned). In practical applications there's no reason why we need the Merkle tree to have height exactly $\lg n$; height $2 \lg n$ is just about as good.

Of course, if you have a special application where you need some stricter requirement -- such as that the tree be fully packed, or that it has to have some specific shape at all points -- then standard solutions using standard balanced binary tree data structures might not suffice. However, that's an unusual requirement whose motivation is unclear, so don't be surprised if there haven't been many, or any, published papers on that variant of the problem.


Hopefully this answers your question about why there haven't been many papers in the cryptographic literature on the topics you mentioned. The short answer: addressing those problems is straightforward using standard computer science ideas, in the cases that seem to come up in practice, so not publishable (and any remaining variants don't seem to have an obvious practical motivation, so there's no reason why anyone would publish on those remaining variants).

$\endgroup$
13
  • $\begingroup$ @user3150164, sure you can. You can do an order-preserving update by simply inserting the new value in the correct location (and if necessary deleting the old value) -- still trivial, nothing that would rise to the level of novel, publishable research. If you have a specific kind of operation that you can't see how to handle, I suggest you ask a specific question about that, but the question you actually asked was a very broad question, and I think my answer explains the answer to that broad question. $\endgroup$
    – D.W.
    Jan 30, 2015 at 6:42
  • $\begingroup$ I have always thought of MHT's as order-preserving, but perhaps you may not have so I have updated the question accordingly to make it more obvious. Updating (i.e. an existing data value to another is still trivial), but not insertion and deletion, without unnecessarily increasing the tree height and doing a larger number of node recalculations. I will try to provide an example but I may have to resort to a diagram to make it clear... $\endgroup$ Jan 30, 2015 at 6:57
  • $\begingroup$ Thanks for your efforts so far. Your last claim is "...updating all of the Merkle hashes can in fact be done in $O(\lg n)$ time...". Even though I haven't shown it in the example, think of the scenario where a single or odd number of data items is inserted at the start (i.e. before the first original data item). In this case, the entire tree needs to be updated. Please tell me if I'm wrong, because I don't feel that your claim is justifiable for all situations. So unless I missed something, my original question hasn't been answered i.e. see Q3 about the tree being efficiently updateable. $\endgroup$ Jan 30, 2015 at 23:16
  • 1
    $\begingroup$ @user3150164, You can have a Merkle tree that has data values in internal nodes, if you want -- it's straightforward to extend all the ideas to that case. Alternatively, it's also possible to build a balanced binary tree data structure with values only in the leaves (and not in any internal nodes); the details of that are out of scope for this site (they're more appropriate for CS.SE than Crypto.SE). This is not a discussion forum, and not a place for extended back-and-forth or an interactive tutorial. I encourage you to formulate the original question more precisely in the future. $\endgroup$
    – D.W.
    Jan 31, 2015 at 0:29
  • 1
    $\begingroup$ Well, I feel that this question is appropriate for Crypto.SE because the merkle tree is a crypto primitive and works differently to normal binary trees, since the parent nodes are a function of the child nodes (and optionally values in the parent), and hence my question. The typical hash tree only has values in the leaves, and even for trees that have values in the upper nodes, they are still a function of the subtree hierarchy that they sit on. I sincerely thank you for your efforts, but I can't accept your solution because it makes a claim that does not appear to be correct. $\endgroup$ Jan 31, 2015 at 0:52
0
$\begingroup$

This is an answer that I haven't fully vetted but am providing because I haven't seen it elsewhere and believe it addresses many of the issues you've raised.

The basic idea is, at each level of the tree, treat the hashed value as data to be used to construct group node boundaries. For example, provide a rolling hash (e.g. adler32) to group nodes under the same parent before a boundary break. Rolling hashes are nice for computational efficiency so, if you don't care about that, just use any hash (sha256, etc.), feeding in node values and causing a boundary break when the lower bits meet some pattern criteria (say the lower two bits are 0, giving a break $\frac{1}{4}$ of the time).

As you scan a level of Merkle indexes, add parent nodes to the level above as needed, grouping one, two, three, etc. ($1$ to $K$ children, say) under a single parent. When only one parent remains, you've reached the top of the tree.

Since everything is local, alterations to a single node, whether it's a leaf node or an index node, be it edit, insert or delete, will most likely only have local consequences, which translates to $O(\lg n)$ operations. That is, whenever a node has been altered, scan left and scan right to find boundaries, marking nodes that need to be altered as necessary and traversing up the tree with the alterations as needed.


For a "vanilla" Merkle tree, the whole tree index might need to be recalculated after one alteration. Using a self balancing tree, like an AVL or red-black tree, might help, but would be dependent on the order of edit, insert or delete, which means you would need to carry the history of edits around with the structure rather than being able to construct the structure just from the data (the $n = 2^b$ nodes).

Tying the tree structure to the content means that it's order independent, allowing two different parties to come up with the same index tree based on the underlying data.

Here are some crude pictures to illustrate:

An edit to one of the underlying blocks that percolates up the hashed indicies of the tree:

enter image description here

An insert that causes a height change and some neighboring nodes to alter:

enter image description here

Red nodes are nodes directly affected by the alteration and purple nodes are ones affected by changing the boundary. Dashed and dotted vertical lines are the group boundary breaks based on hashing the nodes index values for a given (horizontal) level.

Again, I haven't fully vetted this idea so there might be some fundamental problems with this approach.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.