## IPFSMerkleTree - Githubissues

owlprotocol / merkledb

Bridge web2.0 databases with decentralized smart contracts

1 stars 1 forks source link

## IPFSMerkleTree #40

Closed github-actions[bot] closed 2 years ago

github-actions[bot] commented 2 years ago

IPFSMerkleTree

Using the existing Tree & Search Tree primites, create a decentralized lazy-loading immutable Merkle tree meant to be stored on IPFS.

Requirements

The data structure has the following requirements:

O(log(n)) traversal insert/delete
O(log(n)) node changes on insert/delete
O(log(n)) merkle proof parent traversal
O(log(n)) leaf access for proof generation
Efficiently Immutable: inserts/deletes are done by generating copies of changed nodes only
Lazy loading: data is fetched only when necessary and cached (but released if node garbage collected)

Architecture

The IPFSMerkleTree relies on several primitives to efficiently store the tree:

BalancedTree: A balanced tree to store nodes. Must NOT have any circular reference to parent. Use breath-first search with a null node for insertions.
BinarySearchTree: hash => CID<ParentCID> A binary search tree to index leaf nodes and enable parent tree recursion.

Tasks

Map<K,V> interface
IPFSMap<string, CID> abstraction built on top of binary tree
Review IPFSTree insertion/deletion (especially duplicate handling)
MerkleTreeIndex data model
MerkleTree insertion
MerkleTree proof

closes #39