Top 1.0% dependent repos on proxy.golang.org
Top 5.4% forks on proxy.golang.org
proxy.golang.org : github.com/keybase/go-merkle-tree
Package merkletree is a generic Merkle Tree implementation, for provably publishing lots of data under one succinct tree root. Install: Design: This package outputs a MerkleTree with two types of nodes: interior index nodes, or iNodes, and exterior data nodes, of Leaf nodes. The inodes consist of tables that map prefixes to child pointers. The leafs map a full hash to a "value". This is best demonstrated with a simple example. Let's say you are storing the key-value pair (`0123456789abcdef`, {"name" : "max"}) in the Merkle tree. Let's say that the shape of the tree is to have 256 children per inode. Then this key-value pair might be stored under the path Meaning at the root node, we take the first 256-bits of the needed key to get a prefix `01`, and look that up in the node's pointer table to get a child pointer, which is `aabbccdd`. This is a hash of an iNode, which we can fetch from storage, verify it matches the hash, and then recursively apply the same algorithm to find the next step in the path. The leaf node has a sparse table of long-hashes (which are the keys) that map to the values actually stored in the tree. Implementation: All nodes are encoded with msgpack before being hashed or written to store. See `types.go` for the exactly layout of the msgpack objects. Usage: To construct a new Tree from scratch, you need to specify three parameters: A Config, which specifies the shape of the Tree. That is, how many children per interior Node, and how big leaves can get before a new level of the tree is introduced. Also, the hash function to use for hashing nodes into pointers. A StorageEngine, which determines how to load and store tree Nodes from storage, and how to load and store the root hash of the Merkle tree. An array of KeyValuePairs, the things actually stored in the Merkle tree.
Registry
-
Source
- Documentation
- JSON
purl: pkg:golang/github.com/keybase/go-merkle-tree
License: BSD-3-Clause
Latest release: over 1 year ago
First release: over 2 years ago
Namespace: github.com/keybase
Dependent repositories: 29
Stars: 103 on GitHub
Forks: 16 on GitHub
See more repository details: repos.ecosyste.ms
Last synced: about 1 month ago