Prolly Tree in Waku

The Synchronization (Sync) protocol in the Waku network is designed to maintain consistent data and messages across all nodes. It functions by establishing a communication between two nodes: a node sends a Sync request to its peer, which then processes this request and begins the synchronization process. This is facilitated by the use of a Prolly Tree, an advanced data structure that combines the best of skip lists and balanced trees for efficient data handling.

A Prolly Tree is particularly well-suited for tasks like this due to its probabilistic nature, which allows it to dynamically adjust its structure for optimal data storage and retrieval. This ensures log time search, insertion (random), and deletion operations. It maintains data integrity and order by using Merkel hashes and boundary nodes, making it robust and reliable for various applications, including complex peer-to-peer networks like Waku.

The issues aim to solve the problem of fragmented states in Waku Store nodes, where some messages may be missing in nodes present in the network. We intend to present a Proof of Concept (PoC) of a working Conflict-Free Replicated Data Type (CRDT), specifically a Prolly tree in our case. The Prolly tree will act as a foundational backbone, enabling peers to synchronize the state of their Waku Store nodes efficiently. This work is built on top of notable research in the field, as seen in research1, research2. Our contributions are:

Custom implementation of the Prolly tree.
A simple protocol for synchronizing the state of Waku Store nodes using the Prolly tree.
Comparison of our proposed Prolly tree with other CRDTs.

The pros:

Easier to Sync the Store node state in a Peer-to-Peer manner
It is simpler to understand and program/maintain/extend the Waku Prolly tree since it encompasses an elegant and straightforward design with a higher degree of modularity while having the same features as other Prolly trees
Ability to run advanced queries using multiple Prolly trees on Waku node

The Cons:

Consuming more space of the node since the CRDT is going to occupy additional space on memory

Definitions:

Node - It is the simplest unit of data storage in Prolly tree. It has a key and a value at Level 0 of the Prolly Tree. At Non-zero levels, only the key is used to traverse the tree. In this document, Node is sometimes referred to as a key-value pair or a key.
Level - It is the level of the tree at which the node is present. Level 0 is the leaf level of the tree where Nodes have both key and value filled in them. At Non-zero levels, only the key is used to traverse the tree.
Tail/Anchor Node: It is the last/right-most node of the Prolly Tree. It can also be termed as a Fake node. It acts as a backbone for the Prolly tree. At each level of the tree, there is a Tail node. It has the property that it is always a boundary node by default. For the incoming nodes that are inserted in the tree and most recent in the network and happen to be non-boundary nodes then we need some node to store their Merkel hash as well so that they can also be tracked in the Sync process. This is where the Tail node comes into the picture. It stores the Merkel hash of the incoming non-boundary nodes.
Boundary Node: It is a simple node as mentioned above but its node_hash attribute falls below a certain threshold. Due to this it is promoted to the next level in the Prolly tree. This node contains the rolling Merkel-hash of the non-boundary nodes which are present in the level just below it until the first boundary node or None is seen when moving from right to left. It is also called a Promoted Node.
Bucket/Chunk: It is a collection of nodes that are present at the same level in the Prolly tree and on either end there are boundary nodes. The bucket/chunk boundary starts from the last seen boundary node in a sequence until the first seen Boundary node. For. eg. at level 0, there are 4 nodes with keys 1, 2, 3, 4, and 4 is the boundary node and 1, 2, 3 are non-boundary nodes. then the chunk will be (1, 2, 3, 4). The chunk is also represented using the rolling Merkel hash of the non-boundary nodes that are present in the chunk/bucket. The Merkel hash of the chunk is stored in the boundary node present at the level just above it. In this example in Node(4) of Level 1. Using this Merkel hash we can verify the integrity of the chunk/bucket.

How a node is promoted to the next level in Waku Prolly Tree:

This concept can be interpreted as the maximum number of levels that a Node (symbolizing a key-value pair) can ascend in a Waku Prolly tree. At the Prolly Tree's level 0 or leaf level, a Node containing the key-value pair is stored. For identifying this node from any level above 0 in a Prolly tree, a Node (comprising only key value) is promoted. In the Waku Prolly tree, to promote a node from level x to x+1, its key-value hash (referred to as node_hash) is utilized at level 0. However, for levels above 0, the process involves rehashing the node_hash content. This method offers a significant benefit in terms of determining the height of a particular node or key-value pair (universally). It notably influences the diff algorithm, simplifying the process of calculating the diff. Just to put in perspective, whether a node is being promoted depends on the node_hash attribute of that node, imagine a particular key/value node is promoted 3 times

Level3 node_hash -> h(Level2 node_hash) Level2 node_hash -> h(Level1 node_hash) Level1 node_hash -> h(Level0 node_hash) Level0 node_hash -> h(key-value)

At non-0 levels, the node_hash is calculated by rehashing the previous level's node_hash attribute.

There can be alternate methods to promote a Node, as seen in the examples of Canvas, Dolthub, MST, Authenticated Dictionaries etc. However, the method described above is one of the most suitable for the Waku Prolly Tree.

Alternatively, with minor code changes we can substitute the node promotion method with the one described in any of the above mentioned examples.

Prolly Tree Construction

In the context of Waku, the Prolly Tree is constructed using key-value pairs, often with the 'timestamp' as the key and 'messageHash' as the value. This allows for effective tracking and synchronization of messages over time. The messages within the tree are grouped into buckets, small units that are compared based on their combined hashes, known as Merkel hashes. This chunking of data into buckets allows the Sync process to be faster and more efficient, as comparing smaller units is less computationally intensive, following a logarithmic complexity pattern.

The structure also incorporates a threshold mechanism that controls the number of nodes a parent node can contain, in other terms how many nodes a bucket can have. This is crucial in cases where the data to be synchronized is out of order. It ensures that similar types of data will result in similar chunking and hashes, thereby streamlining the synchronization process across the network. This thoughtful design makes the Sync protocol an effective tool for maintaining harmony and consistency across the Waku network.

In the context of Waku messages, each message inherently contains a Unix timestamp, offering a natural order. Utilizing this, a chunking algorithm based on the individual timestamps of messages, rather than a combined hash of previous messages, is more effective. By organizing messages according to their specific timestamps, this approach minimizes the overlap or spillover of messages between chunks. Consequently, this tailored chunking method enhances the speed and efficiency of the Sync process, aligning messages more coherently and streamlining synchronization within the network.

The figures below illustrate the different stages of constructing a Prolly Tree from a series of key-value pairs. The key-value pairs are sorted based on their timestamps. A new bucket boundary is determined based on the individual node's hash when it falls below a certain threshold.

The figure below shows a bunch of key nodes arranged in sorted order based on their timestamp. This represents level 0 of the Prolly Tree. The nodes are then grouped into buckets based on their hash, and this process is followed up to the root of the Prolly Tree.

prolly_tree_plain drawio

In the figure below, the nodes are grouped into buckets based on their hash. At level 0, it's the hash of their key-value pair. At level 1, it's the node's own hash acting as input to the hash function, aka rehashing. At subsequent levels in a Prolly Tree, only a few nodes are selected to be the boundary nodes. The nodes 3, 4, 6, and 9 are selected as boundary nodes. We have a special node called "tail," which is always the last node in the tree and consists of all nodes that are not boundary nodes. The tail node is always a boundary node. Here, the first bucket is formed using nodes 0, 1, 2, and 3. A boundary node is highlighted in green. This node is promoted to the next level with its original key and a pointer to the boundary node at the level just below it. The promoted node contains the Merkel root of the nodes in the bucket starting from the promoted node below it to all nodes to its left until another boundary node is hit, or there is None. In our example, bucket 1's Merkel root is stored in Node 3 of level 1. Further, this node will be used in comparison with other peer nodes on the same level.

prolly_tree_level0 drawio

Similarly, the process continues at level 1, where the promoted/boundary (of level 0) nodes are grouped into buckets based on their individual hash. The nodes 4 and 9 are selected to be promoted, among others, of course, including the Tail node.
The process continues recursively at level 2, where the nodes are grouped into buckets based on their hash. Here Node 9 here is promoted to level 3 where it is only joined by the tail node.

prolly_tree_level2 drawio

Finally, there is one node at the very top, and it will always be the Tail node of the topmost level that contains the Merkel hash of the entire tree. This node serves as the root of the Prolly Tree. The Node R (in pink) in the figure is the root of the tree, this root will be shared with peer nodes to Sync with them using a Diff protocol.

prolly_tree_level3 drawio

Comparison between the other Prolly tree implementations vs Waku Prolly Tree implementation:

Right side Backbone: In Canvas they use the left side backbone i.e. the fake node is the first node of the tree and stores the state till the next boundary node of the initial nodes of the respective level. While this is a valid implementation, it is not the most efficient one as in regular append-only insertions it requires the change to be propagated to the root node in a spiral/waterfall fashion until the root node. As shown in the picture below. This is not the case in Waku Prolly tree as the change is propagated only upwards in a vertical fashion if they are not boundary nodes, which is the case in most of the scenarios bounded by the chunking factor.

Left_Tail_insert_path drawio

Waku Prolly tree uses the Right side backbone i.e., a Fake/anchor node that stores the state of the upcoming transaction from last observed boundary node in the case where no new boundary node has appeared upon append-only insertions. Since every intermediate node stores the Merkel state of the non-boundary nodes appearing before it a level down, in this case when a Prolly tree is progressing then we need to have a fake boundary node that can store the state of those non-boundary nodes from the last boundary node. As seen in the picture below, the path in green is the affected path due to sequential insertions, while the dotted subtree remains unaffected. That can later be used in parallel read/write.

Right_Tail_insert_path drawio

No Split of bucket nodes: In Waku Prolly tree, the bucket nodes are not split into two buckets based on a rolling hash of the previous non-boundary nodes. The reason is that for a node to become a boundary node only the individual hash of the node is considered and not the hash of the bucket. So the insertions even the random ones are only making local spill vertical but never the horizontal spill. This is not the Dolthub or Canvas case where the bucket nodes may split into two buckets upon a new node insertion when they reach the chunking factor and this spill can cascade even further. This is a valid implementation but it is not the most efficient one as it can spill the change and restructure the tree horizontally and vertically.
Batch Insertions: A batch insertion is a group of nodes already structured as a subtree inserted into the Prolly tree. While this is a future upgrade it is apparent at this stage that the batch insertions are not possible in Canvas as the append-only insertions are subjected to the non-boundary node before the insertion (as the rolling Merkel hash decides boundary node condition), as this might impact the structure of the tree. But in the case of Waku Prolly tree, batch insertions are possible as the insertion ahead of any type of node will not impact the tree's structure. Only the Merkel hashes of the nodes need to be refreshed. This can be an interesting feature for the future as it can be used to insert the subtree of the nodes in a single transaction instead of using the insert operation for each node and updating the Merkel hashes of the intermediate nodes on the way.

PoC of the Prolly tree

The PoC and the code of Prolly tree implementation can be found in the repository below:

https://github.com/ABresting/Prolly-Tree-Waku-Message

using key-value pairs, often with the 'timestamp' as the key and 'messageHash' as the value

Not sure why "often" and not "always". And perhaps highlighting the obvious but the timestamp can be duplicated so afaik they can't be used as the key?

using key-value pairs, often with the 'timestamp' as the key and 'messageHash' as the value

Not sure why "often" and not "always". And perhaps highlighting the obvious but the timestamp can be duplicated so afaik they can't be used as the key?

Well timestamp is more favorable since running range queries is much easier which also makes it a good candidate for initial version of Sync Protocol, also in the case when timestamp is duplicated then we have a provision to have a linked list of data associated to the duplicated timestamp, this change is easier to manage in the current implementation. In the worst case, it will scale depending on the duplicated key, in the case of the DoS type attack then it is not a Prolly tree problem anymore.

Thanks for this! We've discussed this in our call, but there are still some things that are a bit unclear:

At level 1, it's the node's own hash acting as input to the hash function, aka rehashing.

Does this mean the merkle hash value for that node is not incorporated into the input for the hash function? In other words, only the timestamp key's hash? In other words, the children of this node will affect the merkle hash, but not the boundary condition of the node itself?

No Split of bucket nodes

Presumably, the bucket can still split if an out of order insertion happen on a timestamp that hashes to a boundary node? This will then affect the merkle hashes of the parents of neighbouring buckets too?

At level 1, it's the node's own hash acting as input to the hash function, aka rehashing.

Does this mean the merkle hash value for that node is not incorporated into the input for the hash function? In other words, only the timestamp key's hash? In other words, the children of this node will affect the merkle hash, but not the boundary condition of the node itself?

Good question! To promote a node from level x to x+1, it's key-value hash (stored as node_hash) is used at level 0, but for the non-0 levels then rehashing its own node_hash content is used. There is advantage of this approach when it comes to knowing the height of a particular node/key-value-pair (universally), it directly impacts the diff algorithm and makes it simpler to calculate the diff. Just to put in perspective, whether a node is being promoted depends on the node_hash attribute of that node, imagine a particular key/value node is promoted 3 times

Level3 node_hash -> h(Level2 node_hash) Level2 node_hash -> h(Level1 node_hash) Level1 node_hash -> h(Level0 node_hash) Level0 node_hash -> h(key-value)

At non-0 levels, the node_hash is calculated by rehashing the previous level's node_hash attribute.

Now merkel_hash is another attribute to the node. This value is the rolling hash of all non-boundary nodes sequentially appearing at the level just below the current level. SO from the example above, Node promoted to Level 1 will have merkel_hash filled by all the nodes starting from that key at level 0 going backward in sequence until the first boundary node is seen. If there are 3 nodes (keys 1,2,3 - all non-boundary nodes) before the promoted node (boundary node) with key 4 i.e. Node(data:"xyz", timestamp:4) then: At level 1 Node(4) will have merkel_hash as h(h(Node(1)),h(Node(2)),h(Node(3)),h(Node(4))) these nodes are at level 0.

No Split of bucket nodes

Presumably, the bucket can still split if an out of order insertion happen on a timestamp that hashes to a boundary node? This will then affect the merkle hashes of the parents of neighbouring buckets too?

Indeed, but it will only impact the merkel_hash of the split bucket, and this split will only be done once and will not cascade further. For eg.

At level 0, there are 4 nodes 1,2,3,4 and 4 is the boundary node and 1,2,3 are non-boundary nodes. Then as explained above Node 4 will move up a level and will contain the rolling hash of 1,2,3,4. So (1, 2, 3, 4) is now acting as a bucket of nodes --> Let's call it bucket 1.

Now Imagine if an insertion comes with the key 2.5, now this should go between the node with keys 2 and 3. But not just that, 2.5 also happens to be a boundary node. then the bucket will split bucket 1.

Now there will be two buckets, (1, 2, 2.5) and (3, 4). As expected, Node(2.5) at level 1 will have merkel_hash --> h(h(Node(1)),h(Node(2)),h(Node(2.5)))

And existing bucket 1, will be shortened to (3, 4). With Node(4) of Level 1 merkel_hash --> h(h(Node(3)),h(Node(4)))

To note, only the Merkel-hash of Node(4) level 1 will change. The restructure of bucket nodes will not spill horizontally. Only a vertical refresh of Merkel hashes will take place.

Thanks for the definitions! Very useful.

Good question! To promote a node from level x to x+1, it's key-value hash (stored as node_hash) is used at level 0, but for the non-0 levels then rehashing its own node_hash content is used.

Shouldn't it be chunk hash instead of node hash? At lvl X>0 you only need the hashes of lvl X-1 chunks

At lvl 0, K/V are timestamp/message hash but otherwise they are timestamp/chunk hash

Could you specify the data structures used?

Now Imagine if an insertion comes with the key 2.5, now this should go between the node with keys 2 and 3. But not just that, 2.5 also happens to be a boundary node. then the bucket will split bucket 1.

Now there will be two buckets, (1, 2, 2.5) and (3, 4). As expected, Node(2.5) at level 1 will have merkel_hash --> h(h(Node(1)),h(Node(2)),h(Node(2.5)))

And existing bucket 1, will be shortened to (3, 4). With Node(4) of Level 1 merkel_hash --> h(h(Node(3)),h(Node(4)))

To note, only the Merkel-hash of Node(4) level 1 will change. The restructure of bucket nodes will not spill horizontally. Only a vertical refresh of Merkel hashes will take place.

If you start with keys; 1, 2, 3, 4 then lvl 0 -> chunk(1, 2, 3, 4) and lvl 1 chunk(4)

Then if you add boundary node 2.5 then the tree would become. lvl 0 -> chunk(1, 2, 2.5), chunk(3, 4), lvl 1 -> chunk(2.5, 4), lvl 2 -> chunk(4) no?

I'm still not sure I understand how you can avoid horizontal restructuring.

Thanks for the detailed explanation. I got to more or less the same conclusion studying the issue description and your python implementation.

In other words, in some sense there are two trees - the one is the "structure tree" that determines which nodes are promoted to branches and superbranches; the other is the Merkle tree that superimposes the merkle hashes (hashing the children) to the structure tree by adding these as a property to each node. However, the merkle hashes never play a role in how the tree is structured, so no amount of additions (or subtractions) to the children of a node affects the tree structure. The exception is when a new leaf node gets inserted that itself gets promoted to a new boundary node, but even then it's only the merkle hash property (not playing a role in the tree structure) of the neighbouring bucket and parents that are affected. Is this a fair summary of what you explained? :)

I'm still trying to wrap my head around the relative advantages or disadvantages of such an approach vs a "fully-merklized" prolly tree (i.e. where the merkle hashes themselve determine the structure).

Let's look at an example similar to yours, but instead of timestamp-like node key-values of 1,2,3,4 I will use a,b,c,d,e so that I can reserve numbers to refer to the levels. Say at level 0 you have key-values a, b, e. h(e) falls below the threshold, so becomes the right boundary and promoted to level 1. This is the case in both your tree and in "traditional" prolly trees (sibling hashes are not taken into account). So you have for your tree and a traditional prolly tree: level 0: (0,a) (0,b) (0,e) level 1: (1,e) The difference now comes in to determine whether (1,e) also gets further promoted to (2,e). In your tree the only determinant here is h(h(e)), whereas in traditional prolly trees the determinant is h(h(a,b,e)). For your tree, you would still need to do another hash calculation for h(h(a,b,e)) to populate the merkle_hash property at (1,e), but this does not affect the structure. Let's assume for the sake of illustration that both h(h(e)) and h(h(a,b,e)) meets the boundary condition and gets promoted. For both your tree and the traditional prolly tree you'll now have: level 0: (0,a) (0,b) (0,e) level 1: (1,e) level 2: (2,e) Now, if you were to insert (0,c) (and assuming h(c) does not meet boundary condition), in both your tree and the traditional tree, (1,e)'s position will remain unaffected, but its merkle hash will change to h(a,b,c,e). The difference is that (2,e) will remain unaffected in your tree (since it's just h(h(e))) while in traditional prolly tree, depending on h(h(a,b,c,e)), the node can either remain promoted or be demoted from (2,e). Of course, if there were a level 3, this would have somewhat of a cascading effect.

However, is the occasional demotion and promotion not part of the prolly tree algorithm to keep the structure and tree depth contained? In your case it seems as if nodes can only ever be promoted and no amount of horisontal changes or additions will ever demote any parent nodes. Wouldn't this very rigid structure tend towards higher and higher tree depths (i.e. more levels)? I'm also unclear if the total number of changes are much different, because in your case you would need to maintain the merkle tree in parallel in any case and compute two hashes for each node. I don't really have an intuition here, so more a comment than a real concern. I'm also unclear what the difference is in (programmatic) difficulty for generating these trees. In a traditional prolly tree, the rolling hashes determine the structure, so the structure "emerges" as you compute hashes for nodes in order. In your case the structure is determined first after which rolling hashes need to be computed based on which nodes have been promoted as parents. It seems to me that the latter may be more complex for large trees.

Shouldn't it be chunk hash instead of node hash?

@SionoiS my understanding is that chunk hash is never used in the tree structure. In other words, the promoted node hash is simply a hash of the node hash at the previous level and does not consider any of its siblings in the same chunk/bucket. Correct me if I'm wrong, @ABresting?

@ABresting one more random question, presumably at level 0 the node hash will be computed over the content of the timestamp and the list of Waku message hashes with the same timestamp (we should expect many timestamp clashes, because we propose coarse timestamp resolutions)? In this case inserting a new message hash to an already-existing list with the same timestamp, will affect the node_hash property and tree structure?

Shouldn't it be chunk hash instead of node hash? At lvl X>0 you only need the hashes of lvl X-1 chunks

Well, using chunk hash to promote a node vs using individual node_hash actually brings the same probability of nodes getting promoted, and this is apparent after I insert a lot of nodes then the height of the tree moves in order of log. And the average chunk size is also more of less the same. In short, having the same tree structure properties as Canvas Prolly tree. Also having individual nodes content deciding the height if the tree is very useful when calculating diff as irrespective the order and position of keys the height of the tree shall remain the same. So in this case, if you have a smaller tree than your neighbor's then in the bigger tree the same nodes that the small tree has will be found at the same height as in the bigger tree. So just make a height comparison and come to that height from a bigger tree and voila!, now you can calculate the diff easily.

At lvl 0, K/V are timestamp/message hash but otherwise they are timestamp/chunk hash

Could you specify the data structures used?

at lvl 0 the original node will have keys as well as values, but for nodes at lvl > 0 then only the values will be kept blank since there is no use of those values since intermediate nodes of the tree will just be used for key comparison/traversal and merkel_hash comparison to check the integrity of that branch, just like in Btrees + merkel trees. Tthe node structure used follows:
self.timestamp = timestamp
self.data = data
self.node_hash = calculate_hash(str(data) + str(timestamp))
self.level = 0
self.up = None
self.down = None
self.left = None
self.right = None
self.merkel_hash = self.node_hash
self.boundary = None
self.is_tail = is_tail
for lvl 0 even the merkel_hash is same as node_hash since node points to itself since it is the leaf node.

If you start with keys; 1, 2, 3, 4 then lvl 0 -> chunk(1, 2, 3, 4) and lvl 1 chunk(4)

Then if you add boundary node 2.5 then the tree would become. lvl 0 -> chunk(1, 2, 2.5), chunk(3, 4), lvl 1 -> chunk(2.5, 4), lvl 2 -> chunk(4) no?

I'm still not sure I understand how you can avoid horizontal restructuring.

yes, so the process follows like you described since the original chunk will be divided into two and the remaining part of the nodes and changes (such as refreshing the merkel hashes) are done vertically. BUT in traditional case such as Canvas and dolthub, Horizontal split spill-over comes into the picture when chunk (1, 2, 3, 4) spilt into (1, 2, 2.5) and the remaining one's rolling hash may not fall under a threshold anymore, so what happens in this case? that's where the cascading spill of split happens that may change the structure and the merkel hashes. This process serves so much complexity with no advantage over our Prolly tree structure. Insertion, search, deletion all happening in log time.

Horizontal split spill-over comes into the picture when chunk (1, 2, 3, 4) spilt into (1, 2, 2.5) and the remaining one's rolling hash may not fall under a threshold anymore, so what happens in this case?

We don't need to use a rolling hash, I think we agree on this.

that's where the cascading spill of split happens that may change the structure and the merkel hashes.

That's a feature not a bug. The tree rebalance itself this way.

I feel you should stick to the normal/standard prolly tree, would be simpler. If we need your enhancement, we can implement them later.

Building a prolly tree with chunks only storing K/Vs would also save data. Something like.

type
  Chunk[K]* = object
    keys: seq[Ordinal[K]]
    values: seq[array[32, byte]]

However, the merkle hashes never play a role in how the tree is structured, so no amount of additions (or subtractions) to the children of a node affects the tree structure.

Actually in the case of substraction/deletion of a node the structure (height) of the tree may be changed (reduced) coz imagine if that was the node with the most height. So our structure is flexible and not rigid.

The exception is when a new leaf node gets inserted that itself gets promoted to a new boundary node, but even then it's only the merkle hash property (not playing a role in the tree structure) of the neighbouring bucket and parents that are affected. Is this a fair summary of what you explained? :)

Yes this part you got it right.

For your tree, you would still need to do another hash calculation for h(h(a,b,e)) to populate the merkle_hash property at (1,e),

At this particular step one round of rolling hash is in both our and others' implementation.

The difference is that (2,e) will remain unaffected in your tree (since it's just h(h(e))) while in traditional prolly tree, depending on h(h(a,b,c,e)), the node can either remain promoted or be demoted from (2,e). Of course, if there were a level 3, this would have somewhat of a cascading effect.

yes, that is a notable advantage not only in maintenance/programmatically but also when the insertions are happening from one end. Since then this spill is contained to only between the non-boundary nodes and anchor/fake node which is present at each level. Remaining of the tree can be read and Sync'ed without complete locking (good candidate for future upgrade).

However, is the occasional demotion and promotion not part of the prolly tree algorithm to keep the structure and tree depth contained? In your case it seems as if nodes can only ever be promoted and no amount of horisontal changes or additions will ever demote any parent nodes. Wouldn't this very rigid structure tend towards higher and higher tree depths (i.e. more levels)?

On the contrary our tree's depth can be decreased as well, especially when there are a lot of nodes then you won't even know the difference! Like I said it has all the good properties of traditions Prolly trees. :)

I'm also unclear if the total number of changes are much different, because in your case you would need to maintain the merkle tree in parallel in any case and compute two hashes for each node. I don't really have an intuition here, so more a comment than a real concern.

I felt your concern, but the heavy part of compute is rolling hash which is same in both there trees.

I'm also unclear what the difference is in (programmatic) difficulty for generating these trees. In a traditional prolly tree, the rolling hashes determine the structure, so the structure "emerges" as you compute hashes for nodes in order. In your case the structure is determined first after which rolling hashes need to be computed based on which nodes have been promoted as parents. It seems to me that the latter may be more complex for large trees.

Actually, the probability of both trees are same in that regard, at least the Maths check out to be that way. Also, most of the development in the tree happens because of the unit insertions and not making the Prolly tree from scratch. In the case of insertion too the complexity is the same minus the overload of horizontal spills (Merkel hash calculation must and chance of restructure).

Shouldn't it be chunk hash instead of node hash?

@SionoiS my understanding is that chunk hash is never used in the tree structure. In other words, the promoted node hash is simply a hash of the node hash at the previous level and does not consider any of its siblings in the same chunk/bucket. Correct me if I'm wrong, @ABresting?

In the case of Dolthub Prolly tree, they use the chunk hash/rolling hash to promote the node aka form a bucket. In the case of Canvas the horizontal spills at higher levels are more concerning. There is no one standard implementation of the Prolly tree as we can see, so I am just trying to come up with a simpler but powerful implementation that we can own.

@ABresting one more random question, presumably at level 0 the node hash will be computed over the content of the timestamp and the list of Waku message hashes with the same timestamp (we should expect many timestamp clashes, because we propose coarse timestamp resolutions)? In this case inserting a new message hash to an already-existing list with the same timestamp, will affect the node_hash property and tree structure?

Indeed, and it may change the structure of the tree, this is common in all Prolly tree implementations. In Canvas they call it updates inside the tree and the structure was changing in some cases, which is normal.

that's where the cascading spill of split happens that may change the structure and the merkel hashes.

That's a feature not a bug. The tree rebalance itself this way.

The rebalance is costly as we can see with horizontal spills and programming it is way more complex and prone to errors. I am not sure if it is giving us any advantage?

I feel you should stick to the normal/standard prolly tree, would be simpler. If we need your enhancement, we can implement them later.

The thing is there is no standard Prolly tree implementation, if you look at the Dolthub implementation they do it differently than Canvas and us. The implementation we have is much simpler to understand and operate with. Our PoC puts forward some enhanced properties, the same features and less operating complexity.

Building a prolly tree with chunks only storing K/Vs would also save data. Something like.
type
  Chunk[K]* = object
    keys: seq[Ordinal[K]]
    values: seq[array[32, byte]]

well, that is an implementation difference, keys/values are anyways accessed sequentially, so will they in the case of Linked list. For production, anyone from engineering who wants to implement it can choose as they like.

waku-org / research

Prolly Tree PoC and technical writeup #78