It bugged me that the Insertion algorithm is complicated in my construction. The original construction did not have this problem as it is possible to find the insertion place while traversing because the current key could at each node be compared to the max-key and thus detect if a subtree does not contain the inserted key. My construction threw away the max-key and replaced it with the information necessary to navigate the tree but lost the information needed for early detection of non-membership. Thus here is argumentation that re-enables that property without increasing the proof size
We replace the heigth property with a common-prefix property on each node (this is included in the node Hash): the common-prefix is the shared initial bits of all keys stored in the subtree of a node. The common-prefix of a leaf is just its key.
It has to be noted, that from the common-prefix the height can be restored:
height = n - bitLength(common-prefix) where n is the number of bits in a key.
The additional information allows to check at each node during traversal if common-prefix is a prefix of the lookup key and if not we know the key is not part of the tree and we can abort (in case of an insert we have found nOld)
In case we use this for proofs we do not have to include common-prefix of each node in the proof, it suffices to include height. The common-prefix value can then be restored from the lookup key & height as it is the key without the last height bits. If the wrong key is provided then the prefixes will be wrong and a different root hash is calculated (as common-prefix is included in the node hash).
With that in place Insert becomes:
Insertion of key ki with value vi :
- Traverse the tree until we end at a node/leaf where common-prefix is not a prefix of ki. (if we do not find such a node, it is an update not an insert)
- Replace the found node (called nOld) with a node nNew
common-prefix = sharedPrefix(nOld.common-prefix,ki)
b = nthBitOf(nOld.common-prefix, bitLength(common-prefix)) //index starts at 0
nNew.common-prefix = common-prefix
nNew.leftChild = if(b == 0) leaf( ki , vi ) else nOld
nNew.rightChild = if(b == 0) nOld else leaf( ki , vi )