Skip to content

An abstract implementation of a Merkle Search Tree, structurally compatible with ATProto's instantiation

License

Notifications You must be signed in to change notification settings

DavidBuchanan314/merkle-search-tree

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

9 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

merkle-search-tree

An abstract implementation of a Merkle Search Tree, structurally compatible with ATProto's instantiation.

As described in https://inria.hal.science/hal-02303490/document ("Alex Auvolat, François Taïani. Merkle Search Trees: Efficient State-Based CRDTs in Open Networks. SRDS 2019 - 38th IEEE International Symposium on Reliable Distributed Systems, Oct 2019, Lyon, France. pp.1-10, ff10.1109/SRDS.2019.00032") and https://atproto.com/specs/repository

The goal of this implementation is to be simple and understandable, but not necessarily useful for any real-world applications.

Normally, a MST is layered over some existing key/value store. For simplicity, this one is not, which limits its usefulness. The tree structure exists only in memory. Although you can quite easily write code to serialise and deserialise a tree from, say, an atproto CAR file, you need to load the whole tree - there is no support for "lazy" loading of nodes on an ad-hoc basis. Again, this is for simplicity.

CRUD operations are implemented, tree diffing operations are coming next, maybe.

I also plan to write a version that does layer over an existing key/value store.

Also included is a script for generating graphviz graphs of a tree. Sample output:

image

For testing purposes, I use len() for deciding the height of a key, as opposed to the more usual process of counting the number of leading zeroes from a hash.

Specializing the MSTNode class for use with ATProto's hash function and fanout (of 4) might look like this:

from mst import MSTNode
import hashlib

class ATNode(MSTNode):
	@staticmethod
	def key_height(key: str) -> int:
		digest = int.from_bytes(hashlib.sha256(key.encode()).digest(), "big")
		leading_zeroes = 256 - digest.bit_length()
		return leading_zeroes // 2

About

An abstract implementation of a Merkle Search Tree, structurally compatible with ATProto's instantiation

Topics

Resources

License

Stars

Watchers

Forks

Languages