For classic non-membership proofs in Merkle trees, one needs to maintain a sorted ordering for leaves. Instead, we can use a linked list at the leaf layer to get non-membership proofs without shuffling the leaves of the tree. See https://eprint.iacr.org/2021/1263.pdf. However, if we use this system naively, we need to update the linked list during each append which will reset all the hashes in the tree. We should find a safe way to include the indexing property without the overhead of recomputing hashes. Can we put an upper bound on the amount of computation on the append operation?
For classic non-membership proofs in Merkle trees, one needs to maintain a sorted ordering for leaves. Instead, we can use a linked list at the leaf layer to get non-membership proofs without shuffling the leaves of the tree. See https://eprint.iacr.org/2021/1263.pdf. However, if we use this system naively, we need to update the linked list during each append which will reset all the hashes in the tree. We should find a safe way to include the indexing property without the overhead of recomputing hashes. Can we put an upper bound on the amount of computation on the append operation?