hashtreap

Documentation

Overview

Package hashtreap implements a hash treap. A hash treap is a treap that is authenticated by having the nodes of the tree form a hash (Merkle) tree. This implementation is based on a heavily modified immutable treap implementation by https://github.com/steveyen, available at https://github.com/steveyen/gtreap under the MIT license. My work is available under the Apache 2 license, see the LICENSE and README.md files for further details.

Index

• Variables
• type HashTreap
  • func NewHashTreap() *HashTreap
  • func (t *HashTreap) Add(key, value []byte) (*HashTreap, error)
  • func (t *HashTreap) Get(target []byte) []byte
  • func (t *HashTreap) MembershipQuery(key []byte) (proof QueryProof)
  • func (t *HashTreap) QueryPrune(keys [][]byte, minimalProof bool) (answer bool, proof PruneProof)
  • func (t *HashTreap) Root() []byte
  • func (t *HashTreap) Size() int
  • func (t *HashTreap) Update()
• type ProofNode
• type PruneProof
  • func (p *PruneProof) Size() (bytes int)
  • func (p *PruneProof) Update(keys, values [][]byte) (root []byte, err error)
  • func (p *PruneProof) Verify(keys [][]byte, answer bool, root []byte) (valid bool)
• type QueryProof
  • func (p *QueryProof) Size() (bytes int)
  • func (p *QueryProof) Verify(key, root []byte) (valid bool)

Variables

var NoNodeHash []byte

NoNodeHash represents the hash of a node that does not exist. Having a hash for a non-existent node encodes the structure of the treap into the root hash, which is crucial for security (if nothing else enforces structure).

Types

type HashTreap

type HashTreap struct {
	// contains filtered or unexported fields
}

HashTreap is a treap authenticated by building a hash (Merkle) tree.

func NewHashTreap

func NewHashTreap() *HashTreap

NewHashTreap cretes a new hash treap.

func (*HashTreap) Add

func (t *HashTreap) Add(key, value []byte) (*HashTreap, error)

Add attempts to adds a new node with the provided key and value, and returns the new hash treap or an error if a node with the provided key already exists. Note that the hash of the root of the hash treap is not updated without calling Update() or Roots() on the hash treap.

func (*HashTreap) Get

func (t *HashTreap) Get(target []byte) []byte

Get returns the value of a target node with the provided key, or nil if no node with the target key exists.

func (*HashTreap) MembershipQuery

func (t *HashTreap) MembershipQuery(key []byte) (proof QueryProof)

MembershipQuery performs a provable query for the membership of a privded key. The proof shows either that the key is not a member of the hash treap (proof.Value is then nil), or that the key is a member (proof.Value is then != nil). Note that the resulting proof is not an unique representation of the proof. In particular, some keys and values that make up proof nodes in the proof can be modified and yet the proof is a correct proof of a membership query.

func (*HashTreap) QueryPrune

func (t *HashTreap) QueryPrune(keys [][]byte, minimalProof bool) (answer bool, proof PruneProof)

QueryPrune performs a prune query in the hash treap for a set of keys. The minimalProof flag removes redundant nodes in the proof, greatly reducing proof size for large sets of keys. Returns true if the keys can be used to update the Balloon, otherwise false. The proof proofs the reply.

func (*HashTreap) Root

func (t *HashTreap) Root() []byte

Root returns the root hash of the hash treap that fixes the entire hash trep.

func (*HashTreap) Size

func (t *HashTreap) Size() int

Size returns the number of nodes in the hash treap.

func (*HashTreap) Update

func (t *HashTreap) Update()

Update updates the root hash of the hash treap to cover all nodes in the treap.

type ProofNode

type ProofNode struct {
	Key, Value, Hash []byte
}

ProofNode is a node in a proof.

type PruneProof

type PruneProof struct {
	Key   []byte
	Nodes []ProofNode
}

PruneProof is a list of nodes as a reply to a pruned query.

func (*PruneProof) Size

func (p *PruneProof) Size() (bytes int)

Size returns the size in bytes of the prune proof.

func (*PruneProof) Update

func (p *PruneProof) Update(keys, values [][]byte) (root []byte, err error)

Update creates for a valid PruneProof, with the same keys and answer true, the resulting root of updating the hash treap the PruneProof was created from when adding the provided keys and values. Returns the updated root, or an error if the update fails.

func (*PruneProof) Verify

func (p *PruneProof) Verify(keys [][]byte, answer bool, root []byte) (valid bool)

Verify verifies a prune proof for the provided arguments. Returns true if valid, otherwise false.

type QueryProof

type QueryProof struct {
	Nodes      []ProofNode
	Key, Value []byte
}

QueryProof is a proof proving the correctness of a query.

func (*QueryProof) Size

func (p *QueryProof) Size() (bytes int)

Size returns the size in bytes of the query proof.

func (*QueryProof) Verify

func (p *QueryProof) Verify(key, root []byte) (valid bool)

Verify verifies a membership query for a provided key from an expected root hash that fixes a hash treap. Returns true if the proof is valid , false otherwise.