SeqHashes are uniquely represented Merkle Trees that also represents a sequence. Concatenation of two SeqHashes is O(log(n)). In turn, the cryptographic signing of SeqHashes is O(1) as each tree node carries a cryptographic hash.
Of course, for each node to carry a hash incurs a hefty overhead but that can be alleviated by (lazily) grouping nodes into buckets (turning it in some kind of BTree).
SeqHashes also don't support splitting in O(log(n)) like for example AVL trees.
I've created an Btree version of SeqHash that also allows splitting SeqHashes in O(log(n)) called SplitHash.
This data structure is an immutable, uniquely represented Sequence ADS (Authenticated Data Structure) with various interesting use cases.
It is based on a novel hashing scheme that was first introduced with SeqHash.
See http://www.bu.edu/hic/files/2015/01/versum-ccs14.pdf) by Jelle van den Hooff , a brilliant young researcher back then.
SeqHashes are uniquely represented Merkle Trees that also represents a sequence. Concatenation of two SeqHashes is O(log(n)). In turn, the cryptographic signing of SeqHashes is O(1) as each tree node carries a cryptographic hash.
Of course, for each node to carry a hash incurs a hefty overhead but that can be alleviated by (lazily) grouping nodes into buckets (turning it in some kind of BTree).
SeqHashes also don't support splitting in O(log(n)) like for example AVL trees.
I've created an Btree version of SeqHash that also allows splitting SeqHashes in O(log(n)) called SplitHash.
See: https://github.com/odipar/spread/blob/master/src/main/scala/...