<commit_before>/*
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.
*/
package balloon

import (
	"bytes"
	"errors"
	"sort"
	"strconv"

	"github.com/mndrix/ps"
	"github.com/pylls/balloon/hashtreap"
	"github.com/pylls/balloon/historytree"
	"github.com/pylls/balloon/util"
)

// Balloon is a balloon.
type Balloon struct {
	treap          *hashtreap.HashTreap
	history        *historytree.Tree
	events         ps.Map
	sk, vk         []byte
	latestsnapshot Snapshot
}

// Event is an event that gets inserted into a balloon.
type Event struct {
	Key, Value []byte
}

// Snapshot fixes the entire Balloon at the time of snapshot creation.
type Snapshot struct {
	Roots     Roots
	Signature []byte
	Index     int
}

// QueryProof is a proof of a membership query.
type QueryProof struct {
	TreapProof   hashtreap.QueryProof
	HistoryProof historytree.MembershipProof
}

// PruneProof is a proof of a prune query.
type PruneProof struct {
	Event      Event
	TreapProof hashtreap.PruneProof
	QueryProof QueryProof
}

// Roots contain the roots of the hash treap and history tree, together with
// the version of the history tree.
type Roots struct {
	Version        int
	Treap, History []byte
}

// ByKey is a type used for sorting events.
type ByKey []Event

// Len returns the length of the events being sorted.
func (a ByKey) Len() int { return len(a) }

// Swap swaps two events being sorted by key.
func (a ByKey) Swap(i, j int) { a[i], a[j] = a[j], a[i] }

// Less returns true if the event with index i is less than the event with index j
func (a ByKey) Less(i, j int) bool { return bytes.Compare(a[i].Key, a[j].Key) == -1 }

// NewBalloon returns a new balloon.
func NewBalloon() (balloon *Balloon) {
	balloon = new(Balloon)
	balloon.treap = hashtreap.NewHashTreap()
	balloon.history = historytree.NewTree()
	balloon.events = ps.NewMap()
	return
}

// Clone creates a copy of the balloon.
func (balloon *Balloon) Clone() (clone *Balloon) {
	clone = new(Balloon)
	clone.treap = balloon.treap
	clone.history = balloon.history.Clone()
	clone.events = balloon.events
	clone.latestsnapshot = balloon.latestsnapshot
	clone.sk = balloon.sk
	clone.vk = balloon.vk
	return
}

// Size returns the number of events in the balloon.
func (balloon *Balloon) Size() int {
	return balloon.history.Size()
}

// Size returns the size, in bytes, of the query proof.
func (proof *QueryProof) Size() (bytes int) {
	return proof.HistoryProof.Size() + proof.TreapProof.Size()
}

// Size returns the size, in bytes, of the prune proof.
func (proof *PruneProof) Size() (bytes int) {
	return len(proof.Event.Key) + len(proof.Event.Value) +
		proof.QueryProof.Size() + proof.TreapProof.Size()
}

// Equal determines if another snapshot is equal to this snapshot.
func (snap *Snapshot) Equal(other *Snapshot) bool {
	if snap == nil || other == nil ||
		snap.Index != other.Index ||
		!util.Equal(snap.Signature, other.Signature) ||
		!util.Equal(snap.Roots.History, other.Roots.History) ||
		!util.Equal(snap.Roots.Treap, other.Roots.Treap) ||
		snap.Roots.Version != other.Roots.Version {
		return false
	}

	return true
}

// Genkey generates a key-pair for balloon. Note that the ordering function
// is hardcoded in this implentation.
func Genkey() (sk, vk []byte, err error) {
	return util.GenerateSigningKeyPair()
}

// 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.
func Setup(events []Event, sk, vk []byte) (balloon *Balloon, snap *Snapshot, err error) {
	balloon = NewBalloon()
	balloon.sk = sk
	balloon.vk = vk

	// do same as update, allow events to be empty
	if len(events) > 0 {
		sort.Sort(ByKey(events))

		// add events
		for i := 0; i < len(events); i++ {
			// add the hash of the entire event to the history tree
			_, err = balloon.history.Add(util.Hash(append(events[i].Key, events[i].Value...)))
			if err != nil {
				return
			}

			// add to the treap the hash of the key pointing to the index (version) of the
			// hash of the event in the history tree
			balloon.treap, err = balloon.treap.Add(util.Hash(events[i].Key),
				util.Itob(balloon.history.LatestVersion()))
			if err != nil {
				return
			}
		}
	}

	// create first snapshot
	snap = new(Snapshot)
	snap.Index = 0
	snap.Roots.History = balloon.history.Root()
	snap.Roots.Treap = balloon.treap.Root()
	snap.Roots.Version = balloon.history.LatestVersion()

	signature, err := util.Sign(balloon.sk,
		append(append([]byte("snapshot"), snap.Roots.History...), snap.Roots.Treap...))
	if err != nil {
		panic(err)
	}
	snap.Signature = signature
	balloon.latestsnapshot = *snap

	return
}

// Update updates balloon with the slice of events, producing the next snapshot.
// Run by the author on trusted input.
func (balloon *Balloon) Update(events []Event, current *Snapshot,<commit_msg>Setup now stores the actual event, not only the authenticated part<commit_after>/*
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.
*/
package balloon

import (
	"bytes"
	"errors"
	"sort"
	"strconv"

	"github.com/mndrix/ps"
	"github.com/pylls/balloon/hashtreap"
	"github.com/pylls/balloon/historytree"
	"github.com/pylls/balloon/util"
)

// Balloon is a balloon.
type Balloon struct {
	treap          *hashtreap.HashTreap
	history        *historytree.Tree
	events         ps.Map
	sk, vk         []byte
	latestsnapshot Snapshot
}

// Event is an event that gets inserted into a balloon.
type Event struct {
	Key, Value []byte
}

// Snapshot fixes the entire Balloon at the time of snapshot creation.
type Snapshot struct {
	Roots     Roots
	Signature []byte
	Index     int
}

// QueryProof is a proof of a membership query.
type QueryProof struct {
	TreapProof   hashtreap.QueryProof
	HistoryProof historytree.MembershipProof
}

// PruneProof is a proof of a prune query.
type PruneProof struct {
	Event      Event
	TreapProof hashtreap.PruneProof
	QueryProof QueryProof
}

// Roots contain the roots of the hash treap and history tree, together with
// the version of the history tree.
type Roots struct {
	Version        int
	Treap, History []byte
}

// ByKey is a type used for sorting events.
type ByKey []Event

// Len returns the length of the events being sorted.
func (a ByKey) Len() int { return len(a) }

// Swap swaps two events being sorted by key.
func (a ByKey) Swap(i, j int) { a[i], a[j] = a[j], a[i] }

// Less returns true if the event with index i is less than the event with index j
func (a ByKey) Less(i, j int) bool { return bytes.Compare(a[i].Key, a[j].Key) == -1 }

// NewBalloon returns a new balloon.
func NewBalloon() (balloon *Balloon) {
	balloon = new(Balloon)
	balloon.treap = hashtreap.NewHashTreap()
	balloon.history = historytree.NewTree()
	balloon.events = ps.NewMap()
	return
}

// Clone creates a copy of the balloon.
func (balloon *Balloon) Clone() (clone *Balloon) {
	clone = new(Balloon)
	clone.treap = balloon.treap
	clone.history = balloon.history.Clone()
	clone.events = balloon.events
	clone.latestsnapshot = balloon.latestsnapshot
	clone.sk = balloon.sk
	clone.vk = balloon.vk
	return
}

// Size returns the number of events in the balloon.
func (balloon *Balloon) Size() int {
	return balloon.history.Size()
}

// Size returns the size, in bytes, of the query proof.
func (proof *QueryProof) Size() (bytes int) {
	return proof.HistoryProof.Size() + proof.TreapProof.Size()
}

// Size returns the size, in bytes, of the prune proof.
func (proof *PruneProof) Size() (bytes int) {
	return len(proof.Event.Key) + len(proof.Event.Value) +
		proof.QueryProof.Size() + proof.TreapProof.Size()
}

// Equal determines if another snapshot is equal to this snapshot.
func (snap *Snapshot) Equal(other *Snapshot) bool {
	if snap == nil || other == nil ||
		snap.Index != other.Index ||
		!util.Equal(snap.Signature, other.Signature) ||
		!util.Equal(snap.Roots.History, other.Roots.History) ||
		!util.Equal(snap.Roots.Treap, other.Roots.Treap) ||
		snap.Roots.Version != other.Roots.Version {
		return false
	}

	return true
}

// Genkey generates a key-pair for balloon. Note that the ordering function
// is hardcoded in this implentation.
func Genkey() (sk, vk []byte, err error) {
	return util.GenerateSigningKeyPair()
}

// 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.
func Setup(events []Event, sk, vk []byte) (balloon *Balloon, snap *Snapshot, err error) {
	balloon = NewBalloon()
	balloon.sk = sk
	balloon.vk = vk

	// do same as update, allow events to be empty
	if len(events) > 0 {
		sort.Sort(ByKey(events))

		// add events
		for i := 0; i < len(events); i++ {
			// add the hash of the entire event to the history tree
			_, err = balloon.history.Add(util.Hash(append(events[i].Key, events[i].Value...)))
			if err != nil {
				return nil, nil, err
			}

			// add to the treap the hash of the key pointing to the index (version) of the
			// hash of the event in the history tree
			balloon.treap, err = balloon.treap.Add(util.Hash(events[i].Key),
				util.Itob(balloon.history.LatestVersion()))
			if err != nil {
				return nil, nil, err
			}

			// store event
			balloon.events = balloon.events.Set(strconv.Itoa(balloon.history.LatestVersion()), events[i])
		}
	}

	// create first snapshot
	snap = new(Snapshot)
	snap.Index = 0
	snap.Roots.History = balloon.history.Root()
	snap.Roots.Treap = balloon.treap.Root()
	snap.Roots.Version = balloon.history.LatestVersion()

	signature, err := util.Sign(balloon.sk,
		append(append([]byte("snapshot"), snap.Roots.History...), snap.Roots.Treap...))
	if err != nil {
		panic(err)
	}
	snap.Signature = signature
	balloon.latestsnapshot = *snap

	return
}

// Update updates balloon with the slice of events, producing the next snapshot.
// Run by the author on trusted input.
func (balloon *Balloon) Update(events []Event, current *Snapshot,
{'fraction_non_alphanumeric': 0.11546291808046534, 'fraction_numerical': 0.002132816286960737, 'mean_word_length': 3.5225778167470407, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6142754', 'n_tokens_mistral': 3600, 'n_tokens_neox': 3370, 'n_words': 1156}