tari-project / tari / 5335858590
62%

DEFAULT BRANCH: development
Ran
Jobs 1
Files 0
Run time 1s
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst
5335858590

push

github

web-flow 
feat: sparse merkle trees (#5457)

# Sparse Merkle trees 

## Description

A sparse Merkle tree is a Merkle tree where the non-empty nodes are
stored in a map with the key being the hash
of the node and the value being the node itself.

Merkle trees are a mutable Merkle-ish tree structure, that supports full
CRUD operations.

### Todo in this PR

* [x] Insert new values
* [x] Update existing values
* [x] Delete values
* [x] Inclusion proofs 
* [x] exclusion proofs.
* [x] Benchmarks

This implementation assumed that there is a key-value store elsewhere.
Only the tree hashes themselves are
handled in this data structure.

When constructing a new tree, a hashing algorithm is specified. This is
used to hash the non-leaf nodes. The
"values" provided to the tree must already be a hash, and should have
been generated from a different hashing
algorithm to the one driving the tree, in order to prevent second
pre-image attacks.

## Motivation and Context

tl;dr:
* Bandwidth  savings
* Scalability benefits
* Privacy benefits
* Compact inclusion _and_ exclusion proofs!

### Details
The SMT implementation is faster than `MutableMMR` up to around 10,000
nodes, and then the average depth starts to affect it. By 1,000,000
nodes, it is significantly slower than MMR.

This makes sense since MMR is basically O(1) for inserts, while SMT is
O(log(n)).

You can see some results here:

```text
Starting: SMT: Inserting 1000000 keys
Finished: SMT: Inserting 1000000 keys - 1.921310493s
Starting: SMT: Calculating root hash
Tree size: 1000000. Root hash: 3e42ca40db120bc3c882fc29bf05dc1d7
Finished: SMT: Calculating root hash - 644.226062ms
Starting: SMT: Deleting 500000 keys
Finished: SMT: Deleting 500000 keys - 863.873761ms
Starting: SMT: Calculating root hash
Tree size: 500000. Root hash: 2a7b51f11160a5eab0d90f89a3bcf09f8
Finished: SMT: Calculating root hash ... (continued)

0 of 0 relevant lines covered (NaN%)

0.0 hits per line

Jobs
ID Job ID Ran Files Coverage
1 5335858590.1 0
0.0
 GitHub Action Run
Source Files on build 5335858590
Detailed source file information is not available for this build.