handshake-org / handshake-org/urkel
Consider switching to the merklix tree
- Dominant language
- JavaScript
- Stars
- 124
- Forks
- 21
- PR merge metrics
- No merged PRs in 30d
Description
There's a merklix tree implementation on the [merklix](https://github.com/handshake-org/urkel/tree/merklix) branch.
You could say the way the urkel tree currently handles bit collisions is naive, but in benchmarks, there are __no__ noticeable differences between the urkel tree and a merklix tree in terms of performance or storage. The average case proof size is also identical.
Still, we have to consider the possibility that people may try to DoS the tree. In this case, the merklix tree holds up better.
So, I'm hesitating here for two reasons:
1. This adds massive complexity to the implementation of the tree and proof verification.
2. In order to reduce storage, nodes have to be stored as a variable size. I've been given advice to try a "merklix-2" or "merklix-4" tree (where only 2/4 colliding bits are stored on internal nodes, thus allowing us a constant size node), but I find this even _more_ convoluted since it basically requires combining both methods of handling bit collisions. This also adds complexity with a new "pointer" system you'll notice on the merklix branch.
3. As a result of the last issue, memory usage increases a lot, I want to say it's nearly double, since we now have a lot more properties/objects in memory to track size/bits/etc.
If we can solve the memory issue, I have no issue with using our merklix implementation.
Opening this up to discussion.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.