Merkle hash tree updates 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.


Fig.1 Original Tree.





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





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.
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).