handshake-org / handshake-org/urkel

Consider switching to the merklix tree

Open
#2 2 comments 0 reactions 0 assignees View on GitHub
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.