* I'm concerned about the choice of a BST:
* making it balanced would require adding rotations, which is a big evolution. If it gets more complex, why not go for patricia trees ?
Balancing the tree is a non-issue because the keys can be randomized such that an attacker wouldn't have control over the content of the key in order to manipulate the shape of the tree.
* as is, it is fairly complex already. If it is temporary, and we try to have something simple and correct first, to obtain a Proof Of Concept, I'd get rid of `remove` altogether. I'm not sure it adds much value, but it definitely adds complexity.
Indeed, remove adds a bit of complexity but, since a potential attacker could take advantage of the lack of remove, it's important to implement it
* To be even more simple, I think that proofs could be computed after the fact: if there is no rotation, then we can compare the proofs of existence of the value at a given key (possibly none) in the tree _before_ and _after_ update. All the subtrees hidden by hashes are identical, only the new hashes from the leaf to the root matter. In fact, we can reconstruct one proof from the other as long as we have the two values.
I don't understand your comment. It would help if you would explain how to change the proof data structure.
@pecornilleau See answers below: