balloon

README

Balloon

A forward-secure append-only persistent authenticated data structure. This is a proof-of-concept implementation, please do not use for anything serious.

Design

Balloon is composed of a history tree (like Certificate Transparency) and a hash treap (think authenticated index). Please read the paper for details. To run and reproduce parts of the benchmark from the paper, see the paper-bench branch.

License

Apache 2.0. The hash treap implementation is based on the treap implementation by Steve Yen under the MIT license.

Documentation

Overview

Package balloon implements Balloon, an authenticated data structure that is based on a hash treap and a history tree. The design is available at https://eprint.iacr.org/2015/007 .

This is a proof-of-concept implementation and should not be used for anything serious.

Index

• func Genkey() (sk, vk []byte, err error)
• func Setup(events []Event, sk, vk []byte, storage EventStorage) (balloon *Balloon, snap *Snapshot, err error)
• type Balloon
  • func NewBalloon(storage EventStorage) (balloon *Balloon)
  • func (balloon *Balloon) Clone() (clone *Balloon)
  • func (balloon *Balloon) QueryMembership(key []byte, queried *Snapshot, vk []byte) (answer bool, event *Event, proof QueryProof, err error)
  • func (balloon *Balloon) QueryPrune(events []Event, vk []byte, minimalProof bool) (answer bool, proof PruneProof)
  • func (balloon *Balloon) Refresh(events []Event, current, next *Snapshot, vk []byte) (err error)
  • func (balloon *Balloon) RefreshVerify(events []Event, current, next *Snapshot, vk []byte) (answer bool)
  • func (balloon *Balloon) Size() int
  • func (balloon *Balloon) Update(events []Event, current *Snapshot, sk []byte) (next *Snapshot, err error)
• type ByKey
  • func (a ByKey) Len() int
  • func (a ByKey) Less(i, j int) bool
  • func (a ByKey) Swap(i, j int)
• type Event
• type EventStorage
• type PruneProof
  • func (proof *PruneProof) Size() (bytes int)
  • func (proof *PruneProof) Update(events []Event, current *Snapshot, sk []byte) (next *Snapshot, err error)
  • func (proof *PruneProof) Verify(events []Event, answer bool, current *Snapshot, vk []byte) (valid bool)
• type QueryProof
  • func (proof *QueryProof) Size() (bytes int)
  • func (proof *QueryProof) Verify(key []byte, queried, current *Snapshot, answer bool, event *Event, vk []byte) (valid bool)
• type Roots
• type Snapshot
  • func (snap *Snapshot) Equal(other *Snapshot) bool

Functions

func Genkey

func Genkey() (sk, vk []byte, err error)

Genkey generates a key-pair for balloon. Note that the ordering function is hardcoded in this implentation.

func Setup

func Setup(events []Event, sk, vk []byte, storage EventStorage) (balloon *Balloon, snap *Snapshot, err error)

Setup creates a new balloon based on the slice of events (may be empty or nil). Returns the first snapshot. Run by the author on trusted input.

Types

type Balloon

type Balloon struct {
	Storage EventStorage
	// contains filtered or unexported fields
}

Balloon is a balloon.

func NewBalloon

func NewBalloon(storage EventStorage) (balloon *Balloon)

NewBalloon returns a new balloon.

func (*Balloon) Clone

func (balloon *Balloon) Clone() (clone *Balloon)

Clone creates a copy of the balloon.

func (*Balloon) QueryMembership

func (balloon *Balloon) QueryMembership(key []byte, queried *Snapshot,
	vk []byte) (answer bool, event *Event, proof QueryProof, err error)

QueryMembership queries for an event with a key in a particular snapshot in the balloon. Returns an answer (is member?), an event (if the answer is true), and a proof (always). Run by the server with untrusted input (key and queried).

func (*Balloon) QueryPrune

func (balloon *Balloon) QueryPrune(events []Event, vk []byte,
	minimalProof bool) (answer bool, proof PruneProof)

QueryPrune performs a prune query for a slice of events. Returns an answer indicating if the events can be added and a proof. Run by the server on untrusted input. The minimalProof flag trades a small amount of computation for a significantly smaller proof (the more events, the bigger the reduction).

func (*Balloon) Refresh

func (balloon *Balloon) Refresh(events []Event, current, next *Snapshot,
	vk []byte) (err error)

Refresh updates balloon with the slice of events. Returns an error if the update fails to produce a snapshot identical to the provided next one. Run by the server on input (events and next) that will be verified.

func (*Balloon) RefreshVerify

func (balloon *Balloon) RefreshVerify(events []Event, current, next *Snapshot,
	vk []byte) (answer bool)

RefreshVerify attempts to refresh the balloon with the provided events and compares the resulting balloon with that fixed by the next snapshot. Returns true if valid, otherwise false. Run by the server, monitor, or auditor on input that will be verified.

func (*Balloon) Size

func (balloon *Balloon) Size() int

Size returns the number of events in the balloon.

func (*Balloon) Update

func (balloon *Balloon) Update(events []Event, current *Snapshot,
	sk []byte) (next *Snapshot, err error)

Update updates balloon with the slice of events, producing the next snapshot. Run by the author on trusted input.

type ByKey

type ByKey []Event

ByKey is a type used for sorting events.

func (ByKey) Len

func (a ByKey) Len() int

Len returns the length of the events being sorted.

func (ByKey) Less

func (a ByKey) Less(i, j int) bool

Less returns true if the event with index i is less than the event with index j

func (ByKey) Swap

func (a ByKey) Swap(i, j int)

Swap swaps two events being sorted by key.

type Event

type Event struct {
	Key, Value []byte
}

Event is an event that gets inserted into a balloon.

type EventStorage

type EventStorage interface {
	// Store stores a set of events and the generated snapshot as a result of
	// storing the events in Balloon.
	Store(events []Event, snap Snapshot) (err error)
	// LookupEvent returns the event, if it exists, with the provided key.
	LookupEvent(key []byte) (event *Event, err error)
	// Clone creates a copy of the EventStorage.
	Clone() (clone EventStorage)
}

EventStorage specifies the interface for how to store and lookup events.

type PruneProof

type PruneProof struct {
	Event      Event
	TreapProof hashtreap.PruneProof
	QueryProof QueryProof
}

PruneProof is a proof of a prune query.

func (*PruneProof) Size

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

Size returns the size, in bytes, of the prune proof.

func (*PruneProof) Update

func (proof *PruneProof) Update(events []Event, current *Snapshot,
	sk []byte) (next *Snapshot, err error)

Update creates the next snapshot from adding the provided events in the balloon fixed by the current snapshot. This function depends on that the provided prune proof has been successfully verified for the answer true. Run by the author on input that should have been verified before by using Verify.

func (*PruneProof) Verify

func (proof *PruneProof) Verify(events []Event, answer bool, current *Snapshot,
	vk []byte) (valid bool)

Verify verifies a proof and answer from QueryPrune. Returns true if the answer and proof is correct, otherwise false. Run by the author.

type QueryProof

type QueryProof struct {
	TreapProof   hashtreap.QueryProof
	HistoryProof historytree.MembershipProof
}

QueryProof is a proof of a membership query.

func (*QueryProof) Size

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

Size returns the size, in bytes, of the query proof.

func (*QueryProof) Verify

func (proof *QueryProof) Verify(key []byte, queried, current *Snapshot,
	answer bool, event *Event, vk []byte) (valid bool)

Verify verifies a proof and answer from QueryMembership. Returns true if the answer and proof are correct and consistent, otherwise false. Run by a client on input that should be verified.

type Roots

type Roots struct {
	Version        int
	Treap, History []byte
}

Roots contain the roots of the hash treap and history tree, together with the version of the history tree.

type Snapshot

type Snapshot struct {
	Roots     Roots
	Signature []byte
	Index     int
	Previous  []byte
}

Snapshot fixes the entire Balloon at the time of snapshot creation.

func (*Snapshot) Equal

func (snap *Snapshot) Equal(other *Snapshot) bool

Equal determines if another snapshot is equal to this snapshot.