kolo docsbeta

kolo-braid

The signed strands of several members merged into one deterministic order, which an apply function you write turns into a view.

On this page

A braid is a set of strands: one signed kolo-log per member, stored with kolo-store. Every peer that holds the same entries computes the same order, byte for byte, from Lamport's happened-before relation and the round-based DAG commit rule of DAG-Rider and Bullshark, and feeds it to an apply function you write, a deterministic state machine, which builds a view on kolo-store. Peers sync with ServeConn over direct and relayed connections (kolo-secure, kolo-relay or any kolo-swarm peer), and a new member joins with a join request and a welcome that kolo-invite can carry. The Go packages are kolobraid, kv (a key-value map in the view), devices (a roster of device certificates, and admission of a person's certified devices) and kolobraidtest (checks for an apply function).

The order has two parts. The settled prefix never changes. The tentative tail after it is applied in memory and can still reorder when entries arrive. Reads choose between them: Braid.Settled for the settled view only, Braid.View for settled plus tentative.

All steps

Strands, links, pulses and batches

Every peer that holds the same entries computes the same order, byte for byte, and feeds it to your apply function.

  1. Each member writes its own strand: a signed kolo-log in which every entry names the one before it. Here A and B are settlers and C is a member.
  2. An entry links at most one entry of each other strand: the newest one its writer holds. The links join every strand into one graph.
  3. Settlers write pulses, which settle the order and are never applied. A and B each write a pulse of round 0. In an even round the pulse of that round's pivot seat is the pivot: here A0.
  4. A pulse that holds round-r pulses of q seats is of round r + 1. When the round-1 pulses of q seats hold the pivot, it is committed. With two seats under Majority, q is 2.
  5. The committed pivot settles everything it holds that is not settled yet, as one batch: a topological order whose ties are broken by a hash seeded with the pivot's ID. Settled positions never change.
  6. The rest is the tentative tail, ordered as the batches it is predicted to settle in. It is applied in memory on top of the settled view and can reorder when entries arrive.

Install

go get github.com/ciranda-dev/kolo-braid

It needs Go 1.26 or newer and is pure Go. Build a shared document in two terminals writes one document with two people on 127.0.0.1, step by step, from the kolo-braid-starter repository. Step 7: Agree on members and rooms with kolo-braid keeps the member list and the room list of a desktop chat in a braid. Build with CGO_ENABLED=0 for a binary with no C code: Pebble, used by kolo-store, links a C zstd library when cgo is enabled.

Quick start

One member, one braid on a Pebble directory under the first argument, and an apply function that keeps every message and counts them. The second Append has an empty body, which apply rejects. This is examples/apply of the repository. Run it with go run . "$(mktemp -d)".

main.go
// Command apply writes to a one-member braid on a Pebble directory under the first argument and reads the settled view that its
// apply function built.
package main

import (
	"context"
	"encoding/binary"
	"fmt"
	"log"
	"os"
	"path/filepath"
	"strconv"

	kolobraid "github.com/ciranda-dev/kolo-braid"
	koloid "github.com/ciranda-dev/kolo-id"
	kolostore "github.com/ciranda-dev/kolo-store"
)

func main() {
	if len(os.Args) != 2 {
		log.Fatal("usage: apply <temp dir>")
	}
	ctx := context.Background()
	id, err := koloid.Generate()
	check(err)
	db, err := kolostore.OpenPebble(filepath.Join(os.Args[1], "store"))
	check(err)
	defer db.Close()
	apply := func(tx *kolobraid.Tx, e *kolobraid.Entry) error {
		if e.Kind != kolobraid.KindData {
			return nil
		}
		if len(e.Body) == 0 {
			return kolobraid.Reject("empty message")
		}
		n := 0
		if v, err := tx.Get([]byte("count")); err == nil {
			n, _ = strconv.Atoi(string(v))
		}
		if err := tx.Put(binary.BigEndian.AppendUint64([]byte("msg/"), e.Position), e.Body); err != nil {
			return err
		}
		return tx.Put([]byte("count"), []byte(strconv.Itoa(n+1)))
	}
	b, err := kolobraid.Create(ctx, id, kolobraid.GroupConfig{App: "chat/v1"},
		kolobraid.Options{Backend: db, App: "chat/v1", Apply: apply})
	check(err)
	defer b.Close()
	_, err = b.Append(ctx, []byte("hello"))
	check(err)
	last, err := b.Append(ctx, nil)
	check(err)

	// Wait until the last entry is settled and applied, then read what apply built.
	for {
		if settledPast(b, last.ID) {
			break
		}
		if _, err := b.Next(ctx); err != nil {
			log.Fatal(err)
		}
	}
	s := b.Settled()
	defer s.Close()
	count, err := s.Get([]byte("count"))
	check(err)
	fmt.Printf("%s settled message(s)\n", count)
	rejected := 0
	for o, err := range b.Entries(0) {
		check(err)
		if o.Rejected {
			rejected++
		}
	}
	fmt.Printf("%d rejected by apply\n", rejected)
}

// settledPast reports whether the entry with the given ID is in the settled view.
func settledPast(b *kolobraid.Braid, id kolobraid.EntryID) bool {
	for o, err := range b.Entries(0) {
		check(err)
		if o.ID == id {
			return b.Status().Settled > o.Position
		}
	}
	return false
}

func check(err error) {
	if err != nil {
		log.Fatal(err)
	}
}

It prints:

Text
1 settled message(s)
1 rejected by apply

The rejected entry keeps its position in the order, with Ordered.Rejected set, and its writes are discarded on every peer. Append returns once the entry is written; the loop waits on Next until the entry is settled, then reads the settled view.

The apply function

Go
type ApplyFunc func(tx *Tx, e *Entry) error

apply is called once per entry, in the order, with one transaction on the view. The library makes the order the same on every peer. Only you can make apply give the same result from the same order.

The contract

  • apply must be a pure function of the view before e, e itself and the roster at e's position (Tx.Member, Tx.Members). It sees no clock, no randomness, no map iteration order and no I/O.
  • Floating point that reaches the view must be rounded explicitly after each operation, for example float64(x * y), and functions of math other than Abs, Copysign, Floor, Ceil, Trunc and Sqrt must not reach it. Integers or decimal strings are the simple choice.
  • apply is called for effective entries of the kinds genesis, data, AddMember, RemoveMember, Settlers and Evidence, and never for pulses, seeds and void entries. For membership kinds the library has already applied the effect, so rejecting one discards only apply's own writes.
  • Returning nil commits the writes. Reject(reason) discards them and records the entry as rejected on every peer: it is the only deterministic failure. Any other error, and a panic, halts the view on this peer only: EventHalted and Status.Halted carry the position, and the next Open retries.
  • Per entry, keys are at most 32 KiB and values at most 1 MiB, and the writes have a budget of 16 x MaxBody, where each operation costs its key and value plus 256 bytes. Past a bound the call returns ErrViewLimit and the entry is rejected on every peer, whatever apply returns.
  • A Tx used after apply returned fails with ErrTxDone. apply runs on its own goroutine, so a slow apply delays only application.

Checking that apply is pure

An impure apply breaks convergence even though every peer holds the same order. Two helpers in kolobraidtest run your apply on a history whose final order you give:

  • CheckApply(t, apply, entries) fails the test when settling the history one entry at a time, in random batches and chunk sizes, across restarts, and after a tentative reorganisation and promotion do not all end with the same running digest and view.
  • FindDivergence(apply, entries, replicas, seed) runs replicas that each receive the entries in their own shuffled delivery order, apply what they hold tentatively, reorganise when an earlier entry arrives and settle piece by piece. It returns the first position where a replica's running digest differs from replica 0's, nil when all agree, or an error when apply halted.

This is the package's example, which go test compiles and checks. The second apply counts its calls in a variable outside the view, so replicas that apply tentative entries a different number of times disagree at the first position:

Go
entries := make([]kolobraid.Entry, 12)
for i := range entries {
	entries[i] = kolobraid.Entry{Writer: bytes.Repeat([]byte{byte(1 + i%3)}, 32), Kind: kolobraid.KindData,
		Body: []byte(fmt.Sprintf("k%d=%d", i%4, i))}
}
// good is pure: its effect depends only on the view, the entry and the roster.
good := func(tx *kolobraid.Tx, e *kolobraid.Entry) error {
	k, v, _ := strings.Cut(string(e.Body), "=")
	return tx.Put([]byte(k), []byte(v))
}
// bad is not: it counts its calls in a variable outside the view, and replicas call it a different number of times.
calls := 0
bad := func(tx *kolobraid.Tx, e *kolobraid.Entry) error {
	calls++
	return tx.Put([]byte("calls"), []byte(strconv.Itoa(calls)))
}
for _, c := range []struct {
	name  string
	apply kolobraid.ApplyFunc
}{{"good", good}, {"bad", bad}} {
	d, err := kolobraidtest.FindDivergence(c.apply, entries, 4, 1)
	switch {
	case err != nil:
		fmt.Println(c.name, "halted:", err)
	case d == nil:
		fmt.Println(c.name, "agrees on every replica")
	default:
		fmt.Println(c.name, "diverges at position", d.Position, "on replica", d.Replica)
	}
}
// Output:
// good agrees on every replica
// bad diverges at position 0 on replica 1

A clean result covers only the paths and the entries you gave, so build histories that use every kind of body your application writes. At run time every peer also keeps a running digest of the settled writes. At each checkpoint, every CheckpointEvery settled positions, the settlers claim their digest in their next pulse, and a peer whose digest differs from one that q settlers claimed halts with ErrDiverged and an EventDiverged.

Changing apply between versions

Never change the effect of an entry at a position an older version already applied. Start new behaviour at a position marked by a settled data entry your application defines (or a version field in the bodies), keep the old code path before it, and let old code return an error other than Reject on a marker it does not know, so it halts until it is upgraded. kolobraidtest.CheckUpgrade(t, old, new, entries, marker) checks that the new version keeps every position before the marker.

Writer setup

A device that writes needs an identity it keeps and a storage directory it never shares. This program saves a kolo-id identity in a private directory, creates a braid on a Pebble directory, writes, closes, then loads the identity and opens the braid again. It is examples/writer; run it with go run . "$(mktemp -d)".

main.go
// Command writer sets up a writer: an identity saved in a file, a Pebble directory, a braid created once and opened again
// after a restart. Everything lives under the first argument.
package main

import (
	"context"
	"encoding/binary"
	"fmt"
	"log"
	"os"
	"path/filepath"
	"strings"

	kolobraid "github.com/ciranda-dev/kolo-braid"
	koloid "github.com/ciranda-dev/kolo-id"
	kolostore "github.com/ciranda-dev/kolo-store"
)

// apply keeps every data entry under its position.
func apply(tx *kolobraid.Tx, e *kolobraid.Entry) error {
	if e.Kind != kolobraid.KindData {
		return nil
	}
	return tx.Put(binary.BigEndian.AppendUint64([]byte("msg/"), e.Position), e.Body)
}

func main() {
	if len(os.Args) != 2 {
		log.Fatal("usage: writer <temp dir>")
	}
	ctx := context.Background()
	check(os.Mkdir(filepath.Join(os.Args[1], "id"), 0o700)) // koloid.Save wants a private directory
	idPath := filepath.Join(os.Args[1], "id", "identity")
	dbPath := filepath.Join(os.Args[1], "braid")

	// First run: a new identity, a new braid, one message.
	id, err := koloid.Generate()
	check(err)
	check(id.Save(idPath))
	db, err := kolostore.OpenPebble(dbPath)
	check(err)
	b, err := kolobraid.Create(ctx, id, kolobraid.GroupConfig{App: "notes/v1"},
		kolobraid.Options{Backend: db, App: "notes/v1", Apply: apply})
	check(err)
	_, err = b.Append(ctx, []byte("first"))
	check(err)
	waitMessages(ctx, b, 1)
	fmt.Println("created the braid and wrote 1 message")
	check(b.Close())
	check(db.Close())

	// Second run: the same identity and directory, opened with Open.
	id, err = koloid.Load(idPath)
	check(err)
	db, err = kolostore.OpenPebble(dbPath)
	check(err)
	defer db.Close()
	b, err = kolobraid.Open(ctx, id, kolobraid.Options{Backend: db, App: "notes/v1", Apply: apply})
	check(err)
	defer b.Close()
	fmt.Println("reopened the braid, own strand unconfirmed:", b.Status().Unconfirmed)
	_, err = b.Append(ctx, []byte("second"))
	check(err)
	fmt.Println("messages in the settled view:", strings.Join(waitMessages(ctx, b, 2), ", "))
}

// waitMessages waits until the settled view holds n messages and returns them in the braid's order.
func waitMessages(ctx context.Context, b *kolobraid.Braid, n int) []string {
	for {
		s := b.Settled()
		var msgs []string
		for _, v := range s.Scan([]byte("msg/"), []byte("msg0")) {
			msgs = append(msgs, string(v))
		}
		s.Close()
		if len(msgs) >= n {
			return msgs
		}
		if _, err := b.Next(ctx); err != nil {
			log.Fatal(err)
		}
	}
}

func check(err error) {
	if err != nil {
		log.Fatal(err)
	}
}

It prints:

Text
created the braid and wrote 1 message
reopened the braid, own strand unconfirmed: false
messages in the settled view: first, second

GroupConfig is fixed by the genesis entry and agreed by every peer. Options are local: the backend, a key prefix, the apply function, pins and Limits. Several braids share one backend through PrefixBackend(db, prefix) or Options.Prefix, with prefixes of which none is a prefix of another.

After every Open the own strand is unconfirmed, and writing calls wait for it as long as their context allows:

  • A braid that never had another member and has no pin is confirmed by its own storage at once, as here.
  • A member that is not a settler is confirmed at once by one consistent head of its strand, from a member or a pin, that is as long as the strand. A shorter head confirms it only after ConfirmWait has passed since Open, so a device that is as far behind as a restored backup cannot confirm itself before a member that holds a longer head has shown it.
  • A settler needs such heads from every other settler that answers within ConfirmWait, and from at least q - 1 of them.
  • A longer consistent head means the device is behind: writing calls wait until it caught up from a complete copy. A head that conflicts loses the strand: writes fail with ErrStrandLost.

Never copy a member's data directory or run a copy of it: two running copies both confirm and both write before either sees the other. Options.AppendUnconfirmed writes at once, with that risk.

A braid entry can never be erased. Every peer keeps every entry and its key, so data that may need erasure stays outside the braid. History is never pruned, and each entry costs about 600 bytes of disk on every peer.

Add a writer with kolo-invite

A new member makes its strand with NewJoin and sends Joining.Request to an admin. The admin's Admit appends an AddMember entry and returns the welcome, and the joiner's Complete turns the welcome into its braid. kolo-invite carries both: the join request as the join data, the welcome as the payload sealed to the joiner. kolo-braid only exchanges bytes and does not import kolo-invite.

This program runs it all on 127.0.0.1: an in-process kolo-dht server, the admin with a braid, a manual invite and a kolo-swarm swarm, and the joiner, which finds the inviter on the invite's topic, sends its request, leaves the invite topic, completes the join and syncs on the braid's own topic. It is examples/addwriter; run it with go run . "$(mktemp -d)".

main.go
// Command addwriter adds a writer to a braid with kolo-invite on 127.0.0.1: an in-process kolo-dht server, the admin who
// holds the braid and a manual invite, and the joiner who asks to join with the invite, receives the welcome from Admit and
// Approve and completes it. Every directory lives under the first argument.
package main

import (
	"context"
	"encoding/binary"
	"fmt"
	"log"
	"net/netip"
	"os"
	"path/filepath"
	"slices"
	"sync"
	"sync/atomic"
	"time"

	kolobraid "github.com/ciranda-dev/kolo-braid"
	kolodht "github.com/ciranda-dev/kolo-dht"
	koloid "github.com/ciranda-dev/kolo-id"
	invite "github.com/ciranda-dev/kolo-invite"
	kolostore "github.com/ciranda-dev/kolo-store"
	koloswarm "github.com/ciranda-dev/kolo-swarm"
)

// apply keeps every data entry under its position.
func apply(tx *kolobraid.Tx, e *kolobraid.Entry) error {
	if e.Kind != kolobraid.KindData {
		return nil
	}
	return tx.Put(binary.BigEndian.AppendUint64([]byte("msg/"), e.Position), e.Body)
}

func main() {
	if len(os.Args) != 2 {
		log.Fatal("usage: addwriter <temp dir>")
	}
	dir := os.Args[1]
	ctx, cancel := context.WithTimeout(context.Background(), 2*time.Minute)
	var wg sync.WaitGroup
	open := func(name string) kolostore.Backend {
		db, err := kolostore.OpenPebble(filepath.Join(dir, name))
		check(err)
		return db
	}
	identity := func() *koloid.Identity {
		id, err := koloid.Generate()
		check(err)
		return id
	}
	adminDB, inviteDB, joinerDB := open("admin"), open("invites"), open("joiner")
	defer adminDB.Close()
	defer inviteDB.Close()
	defer joinerDB.Close()
	defer wg.Wait()
	defer cancel()

	// The DHT server that peers find each other through.
	server, err := kolodht.New(ctx, "127.0.0.1:0", identity(), &kolodht.Config{Server: true})
	check(err)
	defer server.Close()
	boot, err := netip.ParseAddrPort(server.Addr().String())
	check(err)

	// The admin: a braid, a kolo-invite instance and a swarm.
	idA := identity()
	a, err := kolobraid.Create(ctx, idA, kolobraid.GroupConfig{App: "chat/v1"},
		kolobraid.Options{Backend: adminDB, App: "chat/v1", Apply: apply})
	check(err)
	defer a.Close()
	in, err := invite.Open(inviteDB, idA, nil)
	check(err)
	defer in.Close()
	admitted := make(chan error, 1)
	wg.Go(func() { // a joiner's request is answered with Admit, then Approve; Deny and RemoveMember undo a failure
		for {
			ev, err := in.Next(ctx)
			if err != nil {
				return
			}
			if ev.Kind != invite.Requested {
				continue
			}
			// nil options admit the joiner as a plain member: not an admin and not a settler
			welcome, err := a.Admit(ctx, ev.Joiner, ev.Data, nil)
			if err != nil {
				in.Deny(ev.Request)
				admitted <- err
				continue
			}
			if err := in.Approve(ev.Request, welcome); err != nil {
				a.RemoveMember(ctx, ev.Joiner)
				admitted <- err
				continue
			}
			admitted <- nil
		}
	})
	var adminBraid atomic.Pointer[kolobraid.Braid]
	adminBraid.Store(a)
	adminSwarm := startSwarm(ctx, &wg, idA, boot, &adminBraid, func(p *koloswarm.Peer) {
		wg.Go(func() { in.ServePeer(ctx, p) })
	})
	defer adminSwarm.Close()
	wg.Go(func() { in.Announce(ctx, adminSwarm) })
	check(adminSwarm.Join(ctx, koloswarm.Topic(a.Topic()), &koloswarm.JoinOptions{Announce: true, Lookup: true}))
	invitation, _, err := in.Create(&invite.CreateOptions{Manual: true, TTL: time.Minute})
	check(err)
	code, err := invite.Parse(invitation)
	check(err)
	fmt.Println("admin: created the braid and a manual invite")

	// The joiner: a new strand, found the inviter through the invite's topic, sent the request, received the welcome.
	idB := identity()
	join, err := kolobraid.NewJoin(ctx, idB, kolobraid.Options{Backend: joinerDB, App: "chat/v1", Apply: apply})
	check(err)
	request, err := join.Request(nil)
	check(err)
	var joinerBraid atomic.Pointer[kolobraid.Braid]
	inviter := make(chan koloswarm.Conn, 1)
	joinerSwarm := startSwarm(ctx, &wg, idB, boot, &joinerBraid, func(p *koloswarm.Peer) {
		if code.Matches(p.PublicKey()) {
			select {
			case inviter <- p.Conn():
			default:
			}
		}
	})
	defer joinerSwarm.Close()
	check(joinerSwarm.Join(ctx, code.Topic(), &koloswarm.JoinOptions{Lookup: true}))
	var conn koloswarm.Conn
	select {
	case conn = <-inviter:
	case <-ctx.Done():
		log.Fatal("the invite topic found no inviter")
	}
	welcome, err := invite.JoinConn(ctx, conn, idB, code, &invite.JoinOptions{Data: request})
	check(err)
	fmt.Println("joiner: sent its join request and received a welcome")
	select {
	case err := <-admitted:
		check(err)
	case <-ctx.Done():
		log.Fatal("the admin did not answer")
	}
	fmt.Println("admin: admitted the joiner with an AddMember entry")

	// The invite connection is done: leave its topic, complete the join and sync on the braid's own topic.
	joinerSwarm.Leave(code.Topic())
	select {
	case <-conn.Context().Done():
	case <-ctx.Done():
		log.Fatal("leaving the invite topic kept the invite connection")
	}
	b, err := join.Complete(ctx, welcome)
	check(err)
	defer b.Close()
	joinerBraid.Store(b)
	check(joinerSwarm.Join(ctx, koloswarm.Topic(b.Topic()), &koloswarm.JoinOptions{Announce: true, Lookup: true}))
	fmt.Println("joiner: completed the join")

	_, err = a.Append(ctx, []byte("hello from the admin"))
	check(err)
	_, err = b.Append(ctx, []byte("hello from the joiner"))
	check(err)
	va, vb := settled(ctx, a, 2), settled(ctx, b, 2)
	fmt.Printf("both settled %d messages in the same order: %v\n", len(va), slices.Equal(va, vb))
}

// startSwarm joins the DHT through boot and runs the one event loop of a peer: a connection that shares the topic of the
// peer's braid is served by the braid, every other connection goes to other.
func startSwarm(ctx context.Context, wg *sync.WaitGroup, id *koloid.Identity, boot netip.AddrPort,
	braid *atomic.Pointer[kolobraid.Braid], other func(*koloswarm.Peer)) *koloswarm.Swarm {
	sw, err := koloswarm.New(ctx, "127.0.0.1:0", id, &koloswarm.Config{LookupInterval: time.Second})
	check(err)
	check(sw.Bootstrap(ctx, []netip.AddrPort{boot}))
	wg.Go(func() {
		for {
			ev, err := sw.Next(ctx)
			if err != nil {
				return
			}
			if ev.Kind != koloswarm.Connected {
				continue
			}
			if b := braid.Load(); b != nil && slices.Contains(ev.Peer.Topics(), koloswarm.Topic(b.Topic())) {
				wg.Go(func() { b.ServeConn(ctx, ev.Peer.Conn()) })
				continue
			}
			other(ev.Peer)
		}
	})
	return sw
}

// settled waits until the braid's settled view holds n messages and returns them in the braid's order.
func settled(ctx context.Context, b *kolobraid.Braid, n int) []string {
	for {
		s := b.Settled()
		var msgs []string
		for _, v := range s.Scan([]byte("msg/"), []byte("msg0")) {
			msgs = append(msgs, string(v))
		}
		s.Close()
		if len(msgs) >= n {
			return msgs
		}
		if _, err := b.Next(ctx); err != nil {
			log.Fatal(err)
		}
	}
}

func check(err error) {
	if err != nil {
		log.Fatal(err)
	}
}

It prints:

Text
admin: created the braid and a manual invite
joiner: sent its join request and received a welcome
admin: admitted the joiner with an AddMember entry
joiner: completed the join
both settled 2 messages in the same order: true

Create invites with Manual: true: an invite that accepts on its own sends one fixed payload, and every joiner needs its own welcome. A connection is served by ServeConn when the peer shares the braid's topic, and by the inviter's ServePeer otherwise; each must be the only acceptor of its connection.

CaseAdminJoiner
AdmittedAdmit appends AddMember (and, with GrowSettlers, a Settlers entry when one is due); Approve sends the welcomethe welcome; Complete
A write fails after the AddMember entrythat error; deny and RemoveMemberinvite.ErrDenied
Already an active memberErrActiveKey; denyinvite.ErrDenied
Strand used before or knownErrKnownStrand; denyinvite.ErrDenied
Request strand signed by another keyErrInvalidArgument; denyinvite.ErrDenied
The admin is not an admin, or holds its own removalErrNotAdmin, ErrRemoved; denyinvite.ErrDenied
The invite expired, was revoked or used up before ApproveApprove returns invite.ErrExpired, ErrRevoked or ErrUsedUp; RemoveMemberthe same error, no welcome
Asking again after an acceptno event, nothing appendedthe same welcome

Without options, Admit admits a plain member: it writes, but it is no admin and no settler, and no Settlers entry is written. AdmitOptions.Roles sets the roles. AdmitOptions.GrowSettlers grows the braid toward MinSettlers seats and MinSettlers - 1 admins: the first joiners become admins, who can add and remove anyone, and settlers, and a Settlers entry is appended when one is due; use it only for joiners you trust that far. Roles together with GrowSettlers is ErrInvalidArgument. Admit calls run one at a time, so joiners admitted at once with GrowSettlers each count the entries of the one before. AdmitOptions.Replace lets a member's new device take over with a new strand and keep its roles.

Braid.CheckAdmit(joiner, request) reports, without writing anything, what Admit would refuse now (ErrNotAdmin, ErrRemoved or ErrNotMember for this peer, ErrActiveKey, ErrKnownStrand), and ErrGroupFull when the group already has MaxMembers active members, which Admit itself does not return: it appends an AddMember entry that the roster then leaves void. WelcomeEntry(welcome) returns the AddMember entry a welcome names, and Braid.PublicKey the key this peer runs the braid with. The devices package below uses all three.

The braid that Complete returns starts once a member serves it the founder strand's genesis entry. Its writing calls wait until it holds that entry and its own AddMember entry is in the order, so the first Append needs no wait of its own; ErrNotMember after that means the order made the AddMember entry void. A join survives a restart of the joiner: NewJoin on the same prefix with the same identity returns the pending join, with the same strand and request.

Remove a writer

RemoveMember by an admin removes a member at the position of its entry, like every membership change. This program admits B, lets it write, removes it, shows what each side keeps, and admits B again with a new strand. It is examples/removewriter; run it with go run . "$(mktemp -d)".

main.go
// Command removewriter removes a writer from a braid on 127.0.0.1: the removed writer keeps what it received, its strand is
// no longer served to it, and it can join again only with a new strand. Every directory lives under the first argument.
package main

import (
	"bytes"
	"context"
	"encoding/binary"
	"errors"
	"fmt"
	"log"
	"os"
	"path/filepath"
	"slices"
	"time"

	kolobraid "github.com/ciranda-dev/kolo-braid"
	koloid "github.com/ciranda-dev/kolo-id"
	kololog "github.com/ciranda-dev/kolo-log"
	kolosecure "github.com/ciranda-dev/kolo-secure"
	kolostore "github.com/ciranda-dev/kolo-store"
	kolosync "github.com/ciranda-dev/kolo-sync"
)

// apply keeps every data entry under its position.
func apply(tx *kolobraid.Tx, e *kolobraid.Entry) error {
	if e.Kind != kolobraid.KindData {
		return nil
	}
	return tx.Put(binary.BigEndian.AppendUint64([]byte("msg/"), e.Position), e.Body)
}

func main() {
	if len(os.Args) != 2 {
		log.Fatal("usage: removewriter <temp dir>")
	}
	ctx, cancel := context.WithTimeout(context.Background(), 2*time.Minute)
	defer cancel()
	options := func(name string) kolobraid.Options {
		db, err := kolostore.OpenPebble(filepath.Join(os.Args[1], name))
		check(err)
		return kolobraid.Options{Backend: db, App: "chat/v1", Apply: apply}
	}
	idA, err := koloid.Generate()
	check(err)
	idB, err := koloid.Generate()
	check(err)
	optsA, optsB := options("a"), options("b")
	defer optsA.Backend.Close()
	defer optsB.Backend.Close()

	// A creates the braid and admits B; A serves every connection that arrives on one kolo-secure listener.
	a, err := kolobraid.Create(ctx, idA, kolobraid.GroupConfig{App: "chat/v1"}, optsA)
	check(err)
	defer a.Close()
	join, err := kolobraid.NewJoin(ctx, idB, optsB)
	check(err)
	request, err := join.Request(nil)
	check(err)
	welcome, err := a.Admit(ctx, idB.PublicKey(), request, nil)
	check(err)
	b, err := join.Complete(ctx, welcome)
	check(err)
	l, err := kolosecure.Listen(ctx, "127.0.0.1:0", idA, nil)
	check(err)
	defer l.Close()
	go func() {
		for {
			c, err := l.Accept(ctx)
			if err != nil {
				return
			}
			go a.ServeConn(ctx, c)
		}
	}()
	conn, err := kolosecure.Dial(ctx, l.Addr().String(), idB, idA.PublicKey(), nil)
	check(err)
	go b.ServeConn(ctx, conn)

	_, err = b.Append(ctx, []byte("from B"))
	check(err)
	settled(ctx, a, 1)
	settled(ctx, b, 1)
	fmt.Println("B wrote a message and both settled it")

	// B reads A's strand over its connection until A settles B's removal.
	var strand kololog.LogID
	for o, err := range b.Entries(0) {
		check(err)
		if o.Kind == kolobraid.KindGenesis {
			strand = o.Strand
			break
		}
	}
	_, err = kolosync.FetchHead(ctx, conn, idA.PublicKey(), strand)
	check(err)
	fmt.Println("B reads A's strand: ok")

	_, err = a.RemoveMember(ctx, idB.PublicKey())
	check(err)
	for isMember(a, idB) {
		_, err := a.Next(ctx)
		check(err)
	}
	fmt.Println("A removed B")
	_, err = kolosync.FetchHead(ctx, conn, idA.PublicKey(), strand)
	fmt.Println("B asks A for A's strand again, refused with ErrNotFound:", errors.Is(err, kolosync.ErrNotFound))
	fmt.Println("A keeps B's earlier message:", len(settled(ctx, a, 1)))
	fmt.Println("B keeps what it received:", len(settled(ctx, b, 1)))

	// B cannot join again with the strand it used: it asks again with a new one.
	_, err = a.Admit(ctx, idB.PublicKey(), request, nil)
	fmt.Println("A admits B's old strand again, refused with ErrKnownStrand:", errors.Is(err, kolobraid.ErrKnownStrand))
	b.Close()
	conn.Close()
	again, err := kolobraid.NewJoin(ctx, idB, options("b-again"))
	check(err)
	request, err = again.Request(nil)
	check(err)
	welcome, err = a.Admit(ctx, idB.PublicKey(), request, nil)
	check(err)
	b2, err := again.Complete(ctx, welcome)
	check(err)
	defer b2.Close()
	conn2, err := kolosecure.Dial(ctx, l.Addr().String(), idB, idA.PublicKey(), nil)
	check(err)
	defer conn2.Close()
	go b2.ServeConn(ctx, conn2)
	_, err = b2.Append(ctx, []byte("B is back"))
	check(err)
	fmt.Println("A settled", len(settled(ctx, a, 2)), "messages after B joined with a new strand")
}

// isMember reports whether the settled roster of b holds id's key.
func isMember(b *kolobraid.Braid, id *koloid.Identity) bool {
	s := b.Settled()
	defer s.Close()
	return slices.ContainsFunc(s.Members(), func(m kolobraid.Member) bool { return bytes.Equal(m.Key, id.PublicKey()) })
}

// settled waits until the braid's settled view holds n messages and returns them in the braid's order.
func settled(ctx context.Context, b *kolobraid.Braid, n int) []string {
	for {
		s := b.Settled()
		var msgs []string
		for _, v := range s.Scan([]byte("msg/"), []byte("msg0")) {
			msgs = append(msgs, string(v))
		}
		s.Close()
		if len(msgs) >= n {
			return msgs
		}
		if _, err := b.Next(ctx); err != nil {
			log.Fatal(err)
		}
	}
}

func check(err error) {
	if err != nil {
		log.Fatal(err)
	}
}

It prints:

Text
B wrote a message and both settled it
B reads A's strand: ok
A removed B
B asks A for A's strand again, refused with ErrNotFound: true
A keeps B's earlier message: 1
B keeps what it received: 1
A admits B's old strand again, refused with ErrKnownStrand: true
A settled 2 messages after B joined with a new strand
  • Membership entries are checked at their own position in the order, never against the roster at arrival time, so every peer decides them the same way. At least one admin and one settler key always remain.
  • Entries of a removed strand ordered before the removal keep their effect; those ordered after it are void everywhere. Removals go first among entries that are ready together, so a concurrent entry is kept only when it was ordered before the removal became ready.
  • A removed member keeps everything it received. kolo-braid cannot take back data a device already holds.
  • Over the network, a removed member is refused, not necessarily told. Peers that hold the removal stop linking its strand and stop serving it from its next request on, and close its connection once its key has been unknown for 60 s. It gets EventRemoved only once it holds the removal settled, which it can only get from a peer that did not hold the removal yet; otherwise it simply receives nothing more.
  • A removed settler is the exception until a settler config without it activates: its pulses still count, so it goes on pulsing and peers go on serving it.
  • A member removed and asked back joins with a new strand (NewJoin on a fresh prefix): its old strand stays used, and Admit refuses it with ErrKnownStrand.

Two peers syncing

Two members on one machine, each with a Pebble directory under the first argument, synced over one kolo-secure connection on 127.0.0.1. A creates the braid and admits B, both append a message, and each settles both in the same order. This is examples/twopeers and the quick start of the README; run it with go run . "$(mktemp -d)".

main.go
// Command twopeers starts a braid and admits a second member, each on a Pebble directory under the first argument, syncs
// them over kolo-secure on 127.0.0.1 and prints what each one settled.
package main

import (
	"context"
	"encoding/binary"
	"fmt"
	"log"
	"os"
	"path/filepath"
	"strconv"

	kolobraid "github.com/ciranda-dev/kolo-braid"
	koloid "github.com/ciranda-dev/kolo-id"
	kolosecure "github.com/ciranda-dev/kolo-secure"
	kolostore "github.com/ciranda-dev/kolo-store"
)

// apply keeps every message under its position and counts them.
func apply(tx *kolobraid.Tx, e *kolobraid.Entry) error {
	if e.Kind != kolobraid.KindData {
		return nil
	}
	if len(e.Body) == 0 {
		return kolobraid.Reject("empty message")
	}
	n := 0
	if v, err := tx.Get([]byte("count")); err == nil {
		n, _ = strconv.Atoi(string(v))
	}
	if err := tx.Put(binary.BigEndian.AppendUint64([]byte("msg/"), e.Position), e.Body); err != nil {
		return err
	}
	return tx.Put([]byte("count"), []byte(strconv.Itoa(n+1)))
}

func main() {
	if len(os.Args) != 2 {
		log.Fatal("usage: twopeers <temp dir>")
	}
	ctx, cancel := context.WithCancel(context.Background())
	defer cancel()
	options := func(name string) kolobraid.Options {
		db, err := kolostore.OpenPebble(filepath.Join(os.Args[1], name))
		check(err)
		return kolobraid.Options{Backend: db, App: "chat/v1", Apply: apply}
	}
	idA, err := koloid.Generate()
	check(err)
	idB, err := koloid.Generate()
	check(err)
	optsA, optsB := options("a"), options("b")
	defer optsA.Backend.Close()
	defer optsB.Backend.Close()

	// A creates the braid; B asks to join and A admits it with an AddMember entry.
	a, err := kolobraid.Create(ctx, idA, kolobraid.GroupConfig{App: "chat/v1"}, optsA)
	check(err)
	defer a.Close()
	join, err := kolobraid.NewJoin(ctx, idB, optsB)
	check(err)
	request, err := join.Request(nil)
	check(err)
	// nil options admit B as a plain member: not an admin and not a settler.
	welcome, err := a.Admit(ctx, idB.PublicKey(), request, nil)
	check(err)
	b, err := join.Complete(ctx, welcome)
	check(err)
	defer b.Close()

	// One kolo-secure connection on 127.0.0.1, served by both braids.
	l, err := kolosecure.Listen(ctx, "127.0.0.1:0", idA, nil)
	check(err)
	defer l.Close()
	go func() {
		if c, err := l.Accept(ctx); err == nil {
			a.ServeConn(ctx, c)
		}
	}()
	conn, err := kolosecure.Dial(ctx, l.Addr().String(), idB, idA.PublicKey(), nil)
	check(err)
	defer conn.Close()
	go b.ServeConn(ctx, conn)

	_, err = a.Append(ctx, []byte("hello from A"))
	check(err)
	_, err = b.Append(ctx, []byte("hello from B"))
	check(err)
	va, vb := settled(ctx, a, 2), settled(ctx, b, 2)
	fmt.Printf("A settled %d messages\n", len(va))
	fmt.Printf("B settled %d messages\n", len(vb))
	fmt.Println("same order:", fmt.Sprint(va) == fmt.Sprint(vb))
}

// settled waits until the braid's settled view holds n messages and returns them in the braid's order.
func settled(ctx context.Context, b *kolobraid.Braid, n int) []string {
	for {
		s := b.Settled()
		var msgs []string
		for _, v := range s.Scan([]byte("msg/"), []byte("msg0")) {
			msgs = append(msgs, string(v))
		}
		s.Close()
		if len(msgs) >= n {
			return msgs
		}
		if _, err := b.Next(ctx); err != nil {
			log.Fatal(err)
		}
	}
}

func check(err error) {
	if err != nil {
		log.Fatal(err)
	}
}

It prints:

Text
A settled 2 messages
B settled 2 messages
same order: true

In an application, join the braid's kolo-swarm topic (Braid.Topic) and serve every connected peer with ServeConn:

Go
sw.Join(ctx, koloswarm.Topic(b.Topic()), nil)
// for every Connected event:
go b.ServeConn(ctx, ev.Peer.Conn())

What moves on a connection:

  • Strands, through kolo-sync, one pull per strand at a time and at most 16 at once. A member's strand is fetched to its settled length plus MaxPullAhead, a settler's to MaxPullAhead past its newest pulse held, and every strand to whatever a held entry links.
  • Heads (ANNOUNCE): every head on the first message, then only the heads that changed, at most one message per AnnounceGap.
  • Second histories and evidence: an entry that a link names but this peer holds another entry in place of is fetched with the writer's signed head and verified entry by entry; two records of one index signed by the writer are evidence, which every peer sends once per connection.
  • After Open, the head of the own strand on each peer, which confirms the own strand or lets it catch up.

Access follows the tentative roster: active members and the settlers of the current and the pending config get entry keys, pins get ciphertext only, and anyone else gets nothing. ServeConn takes both kinds of stream of the connection, so a connection that kolo-invite's ServePeer uses cannot also serve the braid. It returns nil when its context or the connection ends, ErrClosed when the braid closes, and an error wrapping ErrProtocol after it closed the connection of a peer that broke the protocol.

Direct and relayed connections

ServeConn takes a Conn: an authenticated connection to one peer, direct or relayed, such as a *kolosecure.Conn, a *kolorelay.Conn or a koloswarm.Conn. A nil Conn, or one holding a nil pointer, is ErrInvalidArgument. ServeConn trusts RemotePublicKey completely, so pass only connections whose key was proved in a handshake, such as a *kolosecure.Conn: RemotePublicKey must return the key the peer proved in the end-to-end handshake. A relayed link proves it the same way, so the member and pin checks are the same as on a direct connection. A relay copies bytes it cannot read; what it still learns is on the kolo-relay page.

Settlement

Settlers and the quorum rule

Settlers are the members whose pulses settle the order. A config names their keys and the quorum rule, and q of its n seats must hold a pivot for it to be committed. Settlement goes on while q settlers of the current config are online.

SeatsMajority qSettlers that may sign two histories without split prefixesTwoThirds q
1101
2212
3203
4313
5304
7405

Majority, the default, needs floor(n/2) + 1 seats and is for crash faults. TwoThirds needs floor(2n/3) + 1 and is for braids where a settler device may be compromised. Under either rule, settled prefixes never conflict while at most f seats sign two histories, where f is the largest value with 2q - n > f. A settler of the current config that signs two histories stops settlement for good on every peer that sees both (EventSettlementHalted with its key); tentative application and new entries go on. A writer that is not a settler and signs two histories is fenced instead: an Evidence entry makes its strand inactive from that position on, and settlement goes on.

A Settlers entry (SetSettlers) changes the config. A change that adds seats activates at a committed pivot whose past holds a readiness pulse from every added seat; a change that only removes seats activates at once.

Growing to four settlers

MinSettlers is 4: Admit with AdmitOptions.GrowSettlers makes the first joiners admins and settlers until the braid has four seats; a plain Admit does not. Under Majority, 4 settlers give q = 3: one can be offline and one can sign two histories without splitting settled prefixes. 3 or 5 settlers give no such margin, and with them a badly restored or cloned settler device can split the braid. A braid with one settler depends on that device: Status.SingleSettler says so.

Offline settlers

Settlement stops while fewer than q settlers are online and goes on when enough of them are back; in the meantime new entries stay in the tentative tail. A settler that restarts writes again once the other settlers that answer within ConfirmWait confirm its strand. The order among concurrent entries is decided by a hash seeded with the pivot, which the pivot's settler can try to choose: it is not fair, and a "first wins" rule must not rely on it.

Measured times

These numbers come from one run of the test scenarios on one Apple M5 Mac (darwin/arm64, Go 1.27.3), one process per peer on 127.0.0.1, while the machine was busy with other jobs. The peers used short settings: PulseGap 50 ms, PivotWait 500 ms, AnnounceGap 20 ms and ConfirmWait 2 s, where the defaults are 500 ms, 3 s, 100 ms and 10 s. A time runs from the end of the action (the last write returned, a heal, a restart) to the first poll, every 20 to 250 ms, at which every peer agreed. Nothing was measured with the default settings, on other hardware or across a real network.

ScenarioTime
3 peers (3 settlers) write 25 entries each, all settled280 ms
4 peers (4 settlers) write 25 entries each, all settled513 ms
5 peers (4 settlers) write 25 entries each, all settled687 ms
5 peers split 3 and 2: the side with three of the four settlers settles 90 entries678 ms
the same peers agree after the split heals398 ms
3 settlers, 2 stopped, 10 entries stay tentative; one settler restarts2.43 s, of which 2 s is its ConfirmWait
3 peers wrote 10,002 entries in 83.6 s (each Append is durable): all settled after the last write898 ms
a late joiner settles that same prefix after it links to the peers1.392 s
Admit call6 to 19 ms
Admit to the end of Complete13 to 42 ms

Successor braids

When the settler quorum is lost for good, an admin of the old settled roster calls Succeed. The new braid's genesis names the old group, its settled position p and the content digest of the settled view at p; seed entries copy that view, every peer checks the digest (ErrBadSeed on a mismatch), and positions continue at p + 1. Tentative entries of the old braid are not carried. A joiner that never was a member trusts the successor's founder for the seeded view. A member that still holds the old braid passes it as Options.Predecessor, and its braid halts unless the founder was an admin of the old one and the seeded view is the old settled view.

The kv helper

Package github.com/ciranda-dev/kolo-braid/kv keeps a key-value map in the view. Puts and deletes are data entries, and the last effective operation on a key in the braid's order wins, on every peer alike, with no clock. Concurrent writes are decided by the order, which is not fair, so "the first write wins" rules must not rely on it. The map has no access control: any active member can put or delete any key. When keys belong to members, check Entry.Writer (and Tx.Member for its roles) in the apply function before Store.Apply.

Go
settings := kv.New([]byte("settings/"))
apply := func(tx *kolobraid.Tx, e *kolobraid.Entry) error {
	if ok, err := settings.Apply(tx, e); ok || err != nil {
		return err
	}
	return nil // the application's own entries
}
err := settings.Put(ctx, b, []byte("theme"), []byte("dark"))
check(err)
snap := b.Settled() // or b.View() for settled plus tentative
v, err := settings.Get(snap, []byte("theme"))
check(err)
fmt.Printf("theme=%s\n", v)
for k, v := range settings.Range(snap, nil, nil) {
	fmt.Printf("%s=%s\n", k, v) // key order
}
snap.Close()
  • New(prefix): the pairs live in the view under the prefix and the key, and no other key of the application may start with the prefix.
  • Apply handles data entries whose body starts with the kv tag and reports false for every other entry, so an application routes its own entries next to it. A kv body that does not decode, or whose key does not fit with the prefix, is rejected with Reject, the same on every peer.
  • Put and Delete append one entry each, which takes effect at its position. Keys are at most 32 KiB with the prefix and values at most 1 MiB (kolobraid.ErrTooLarge), and the whole body at most the braid's MaxBody.
  • Get and Range read a snapshot: Braid.Settled for what never changes again, Braid.View for settled plus tentative, which a reorg can change. Range(start, end) yields keys in [start, end); an empty end has no upper bound.

The package's tests run it through kolobraidtest.CheckApply and FindDivergence.

Devices of a person

Package github.com/ciranda-dev/kolo-braid/devices keeps the kolo-id device certificates and revocations of the persons in a group in the view, and lets an admin admit a certified device of a person who already belongs to the group without a new decision. A person key, from the 24 words, certifies approver devices, approvers certify ordinary devices, and a device key signs the messages. Each device key is an ordinary member with its own strand. The package changes nothing in the order, the settlement, the membership rules or the formats of the braid, Braid.Admit is unchanged, and a group that does not import it behaves as before. A device gets its certificate from a link-a-device invite of kolo-invite.

This program is examples/devices; run it with go run . "$(mktemp -d)". A laptop founds a group and anchors its approver certificate, certifies a phone, admits it without a new decision, then revokes it.

main.go
// Command devices keeps a device roster in a braid on a Pebble directory under the first argument: a person's laptop founds a
// group and anchors its approver certificate, the phone is certified by the laptop and admitted without a new decision of a
// group admin, and then the laptop revokes it. Nothing leaves the process.
package main

import (
	"context"
	"crypto/ed25519"
	"fmt"
	"log"
	"os"
	"path/filepath"
	"time"

	kolobraid "github.com/ciranda-dev/kolo-braid"
	"github.com/ciranda-dev/kolo-braid/devices"
	koloid "github.com/ciranda-dev/kolo-id"
	kolostore "github.com/ciranda-dev/kolo-store"
)

func check(err error) {
	if err != nil {
		log.Fatal(err)
	}
}

func main() {
	if len(os.Args) != 2 {
		log.Fatal("usage: devices <temp dir>")
	}
	ctx, cancel := context.WithTimeout(context.Background(), 30*time.Second)
	defer cancel()

	roster, err := devices.New([]byte("devices/"), nil)
	check(err)
	apply := func(tx *kolobraid.Tx, e *kolobraid.Entry) error {
		_, err := roster.Apply(tx, e)
		return err
	}
	options := func(name string) kolobraid.Options {
		db, err := kolostore.OpenPebble(filepath.Join(os.Args[1], name))
		check(err)
		return kolobraid.Options{Backend: db, App: "devices/v1", Apply: apply}
	}

	// The person key comes from the 24 words and certifies the laptop as an approver; it is then cleared.
	phrase, err := koloid.GeneratePhrase()
	check(err)
	person, err := phrase.Person()
	check(err)
	phrase.Clear()
	personKey := person.PublicKey()
	laptop, err := koloid.Generate()
	check(err)
	offer, err := person.OfferDeviceCert(laptop.PublicKey(), &koloid.IssueOptions{Serial: 1, Approver: true})
	check(err)
	laptopCert, err := laptop.AcceptDeviceCert(offer, personKey)
	check(err)
	person.Clear()

	// The laptop founds the group and anchors its own certificate: the first device of a person is an admin's decision.
	laptopOpts := options("laptop")
	defer laptopOpts.Backend.Close()
	group, err := kolobraid.Create(ctx, laptop, kolobraid.GroupConfig{App: "devices/v1"}, laptopOpts)
	check(err)
	defer group.Close()
	check(roster.Record(ctx, group, laptopCert))
	waitAnchored(ctx, group, roster, personKey, laptop.PublicKey())
	fmt.Println("laptop: founded the group and anchored its approver certificate")

	// The laptop certifies the phone, which would come from a link-a-device invite. The phone asks to join with a proof.
	phone, err := koloid.Generate()
	check(err)
	offer, err = laptop.OfferDeviceCert(phone.PublicKey(), &koloid.IssueOptions{Parent: laptopCert, Serial: 1})
	check(err)
	phoneCert, err := phone.AcceptDeviceCert(offer, personKey)
	check(err)
	phoneOpts := options("phone")
	defer phoneOpts.Backend.Close()
	join, err := kolobraid.NewJoin(ctx, phone, phoneOpts)
	check(err)
	request, err := devices.NewJoinRequest(join, phone, phoneCert, group.GroupID(), []byte("Maria's phone"))
	check(err)
	name, err := devices.AppData(request)
	check(err)

	// The laptop admits it: the person already belongs to the group, the proof verifies and the person has room.
	welcome, err := roster.Admit(ctx, group, phone.PublicKey(), request)
	check(err)
	phoneBraid, err := join.Complete(ctx, welcome)
	check(err)
	defer phoneBraid.Close()
	fmt.Printf("laptop: admitted %q without a new decision\n", name)

	verify := func() error {
		v := group.View()
		defer v.Close()
		msg := []byte("hello")
		sig, err := phone.Sign("devices/example/v0", msg)
		check(err)
		return roster.Verify(v, personKey, phone.PublicKey(), time.Time{}, "devices/example/v0", msg, sig)
	}
	fmt.Println("the phone verifies as a device of the person:", verify() == nil)

	// The approver revokes the exact certificate it issued; every verifier that holds the record refuses the phone.
	revocation, err := laptop.RevokeDevice(&koloid.RevokeOptions{Person: personKey, Device: phone.PublicKey(), SignerCert: laptopCert, Target: phoneCert})
	check(err)
	body, err := devices.RevocationBody(revocation, phoneCert)
	check(err)
	ref, err := group.Append(ctx, body)
	check(err)
	waitSettled(ctx, group, ref)
	fmt.Println("after the laptop revokes it, the phone verifies:", verify() == nil)
}

// waitSettled waits until the entry ref of the braid is settled.
func waitSettled(ctx context.Context, b *kolobraid.Braid, ref kolobraid.EntryRef) {
	for {
		for o, err := range b.Entries(0) {
			check(err)
			if o.ID == ref.ID && o.Settled {
				return
			}
		}
		if _, err := b.Next(ctx); err != nil {
			log.Fatal(err)
		}
	}
}

// waitAnchored waits until the settled view holds the anchored certificate of device, which Admit trusts.
func waitAnchored(ctx context.Context, b *kolobraid.Braid, roster *devices.Store, person, device ed25519.PublicKey) {
	for {
		v := b.Settled()
		ok, err := roster.Anchored(v, person, device)
		v.Close()
		if err == nil && ok {
			return
		}
		if _, err := b.Next(ctx); err != nil {
			log.Fatal(err)
		}
	}
}

It prints:

Text
laptop: founded the group and anchored its approver certificate
laptop: admitted "Maria's phone" without a new decision
the phone verifies as a device of the person: true
after the laptop revokes it, the phone verifies: false

Records and anchors

  • Records are data entries whose body starts with kolo-braid/devices/v0. Any member may write one, since a certificate or a revocation is its own proof. Apply rejects, the same on every peer, a body that does not decode, a certificate or revocation that does not verify, a certificate whose serial is not higher than the stored one, a certificate issued by an approver already retired, and a record past a bound. It checks structure and signatures with no clock: expiry, revocation and the time of the check belong to the reader.
  • Any member can invent a person key and a certificate for it, so a person counts for admission only when an admin recorded a certificate of it. Such a certificate is anchored. Store.Record is the admin's call for the first device of a person, after the admin decided with Braid.Admit to let that device in, and Store.Admit anchors the certificates it admits.
  • The view keeps one certificate per person and device, the one with the highest serial. An approver's revocation carries its target certificate in the entry, so it can be checked alone and in any order.
  • Cert, Anchored, Devices and Revocations read a snapshot. Verify(snap, person, device, now, context, msg, sig) runs koloid.VerifyDevice on the stored certificate with the stored revocations, for the person you pass: pin the person in your own state, never read it from a certificate. ErrUnknownDevice means the roster has no certificate for the device.
  • Approvers retire by position in the braid's order, which is the same on every peer, not by a clock. A revocation signed by an approver is not used when its position is after the first revocation of that approver by the person key or by the approver itself, and a certificate issued by a retired approver is rejected. A retired approver stays retired even if its key is certified again: use a new key.

Admitting a device

The new device builds its join request with devices.NewJoinRequest(join, id, cert, group, appData), which adds a proof that it holds the certified key: a signature over the person, the group and the request's own strand under kolo-braid/device-admit/v0. An admin calls roster.Admit(ctx, b, joinerKey, request) instead of Braid.Admit. Before it writes anything, it checks in this order:

  1. the request carries a proof and its certificate is for the joiner's key (ErrNotProven);
  2. what Braid.Admit would refuse now, and a full group, through Braid.CheckAdmit (kolobraid.ErrNotAdmin, ErrActiveKey, ErrKnownStrand, kolobraid.ErrGroupFull and the others);
  3. the person has a settled active member in the group whose anchored certificate verifies now (ErrUnknownPerson);
  4. the certificate is not older than the one in the roster, and koloid.VerifyDevice accepts it at Options.Now with the roster's revocations (ErrNotProven, which also matches kolo-id errors such as koloid.ErrCertExpired and koloid.ErrCertRevoked);
  5. when Options.MaxDevices is set, the person has fewer seats than that (ErrTooManyDevices).

Then it appends the certificate, anchored, and waits until the roster holds it (ErrNotRecorded when it settled without effect). It calls Braid.Admit with an ordinary role, no admin and no settler, and waits until the view shows the new member (ErrNotAdmitted when the AddMember entry settled without one). Every wait ends with the caller's context. Nothing is granted when a step before Braid.Admit failed. A group whose policy is that the person approves every device never calls roster.Admit.

Every peer of a group must run the same kolo-id version, because apply verifies signatures with it. Put the kolo-id version in the group's App string, for example chat/v1+id0.1.0, and change it with the version.

Device bounds

There is no limit on the devices of a person by default. Each device takes one seat of the group (MaxMembers, 64 by default), and those seats are the only bound; the anchor is what keeps an invented person from taking seats. A revoked device keeps its seat until an admin removes it with RemoveMember.

devices.OptionsDefaultRangeWhy
MaxCertsPerPerson10241 to 2^20the certificates of one person in a view; the next is rejected
PersonCertReservean eighth of the bound, 1280 to MaxCertsPerPerson, -1 for noneslots kept for certificates the person key issued, so a stolen approver cannot fill the roster
MaxRevocationsPerDevice641 to 2^16approver revocations of one device key
MaxDevicesnoneany positive valuean opt-in ceiling on the seats of one person that Admit lets in (ErrTooManyDevices)

The first three decide which entries apply rejects, so every peer of a group must use the same values. MaxDevices is a setting of the admitting peer: two admins that admit at the same moment each count from their own view, so together they can pass it by one each. A certificate is at most 514 bytes and a revocation 472 bytes, the kolo-id encodings, and a proof is under 700 bytes inside the 64 KiB bound of a join request. A person who loses every device and restores the 24 words gets the person key back but no seat: an admin admits the new device with Braid.Admit and records its certificate.

Formats

Every hash is BLAKE2b-256 over a kolo-codec encoding that starts with its own tag: kolo-braid/entry-id/v0 (entry IDs; the group ID is the genesis entry's ID), kolo-braid/order/v0 (tie-break keys), kolo-braid/config/v0 (config IDs), kolo-braid/digest/v0 (running digest), kolo-braid/content/v0 (content digest) and kolo-braid/topic/v0 (the kolo-swarm topic, Braid.Topic). Entries start with kolo-braid/entry/v0, the join request with kolo-braid/join/v0, the welcome with kolo-braid/welcome/v0 and the kv helper's body with kolo-braid/kv/v0. kolo-braid adds no signature of its own: kolo-log signs every entry.

KindBody
0 genesisapp tag, quorum rule, MaxMembers, MaxSettlers, MinSettlers, MaxBody, CheckpointEvery, and for a successor the old group, position, content digest and seed count
1 dataapplication bytes, at most MaxBody
2 add memberkey, strand log ID, roles, signed log header
3 remove memberkey
4 settlersquorum rule and keys, strictly ascending
5 evidencekey, strand log ID, two signed kolo-log records or heads
6 pulseconfig, activating pivot, optional digest claim, optional readiness
7 seedview pairs of a successor braid

The kv body is, in kolo-codec, the string kolo-braid/kv/v0, a uvarint op (1 put, 2 delete), then the key and the value as bytes, the value empty for a delete.

A devices body is, in kolo-codec, the string kolo-braid/devices/v0, a uvarint op (1 certificate, 2 revocation) and the object as bytes, then, for a revocation only, a bool and the target certificate as bytes. The proof in the data of a join request is the string kolo-braid/devices/proof/v0, the certificate as bytes, the 64-byte signature and the application data as bytes.

API reference

The API reference is generated from the Go source and is in English.

Package kolobraid · github.com/ciranda-dev/kolo-braid · v0.1.0

Package kolobraid merges the entries of several members into one deterministic order that a user-supplied apply function turns into a view.

Each member writes its own signed kolo-log, a strand. A Braid comes from Create, Open or a join (NewJoin, then Joining.Complete); members write with Braid.Append and read with Braid.View (settled plus tentative) or Braid.Settled. Braid.ServeConn syncs the braid over a Conn, direct or relayed. Every peer runs the same ApplyFunc over the same order; the kolobraidtest package checks that an apply function is pure, and the kv package is a key-value helper on top of apply. docs/guide.md explains the rules.

Experimental: the API may change before v1.0.0.

Constants

const (
	// MaxAppTag is the longest application tag in a genesis entry, in bytes.
	MaxAppTag = 64

	// MaxViewKey is the longest key of a view pair, in bytes.
	MaxViewKey = 32 << 10
	// MaxViewValue is the longest value of a view pair, in bytes.
	MaxViewValue = 1 << 20
)
const (
	// MaxJoinRequest is the longest join request, in bytes: the join data bound of kolo-invite.
	MaxJoinRequest = 64 << 10
	// MaxWelcome is the longest welcome, in bytes: the default payload bound of kolo-invite.
	MaxWelcome = 1 << 20
)

Variables

var (
	// ErrClosed is returned by a call on a closed braid.
	ErrClosed = errors.New("kolobraid: closed")
	// ErrInvalidArgument is returned for a nil or out of range argument.
	ErrInvalidArgument = errors.New("kolobraid: invalid argument")
	// ErrInvalidConfig is returned for a GroupConfig outside its ranges.
	ErrInvalidConfig = errors.New("kolobraid: invalid group config")
	// ErrNotMember is returned when the caller's key is not an active member.
	ErrNotMember = errors.New("kolobraid: not an active member")
	// ErrNotAdmin is returned when the caller's key is not an admin.
	ErrNotAdmin = errors.New("kolobraid: not an admin")
	// ErrRemoved is returned when the caller's strand was removed from the braid.
	ErrRemoved = errors.New("kolobraid: member removed")
	// ErrTooLarge is returned for a value over its bound.
	ErrTooLarge = errors.New("kolobraid: value too large")
	// ErrRejected is wrapped by the error that Reject returns.
	ErrRejected = errors.New("kolobraid: entry rejected")
	// ErrViewLimit is returned by a Tx call over a per-entry bound.
	ErrViewLimit = errors.New("kolobraid: view limit exceeded")
	// ErrTxDone is returned by a Tx used after apply returned.
	ErrTxDone = errors.New("kolobraid: transaction done")
	// ErrNotFound is returned for a key or entry that does not exist.
	ErrNotFound = errors.New("kolobraid: not found")
	// ErrHalted is returned when apply failed on this peer and nothing more is applied.
	ErrHalted = errors.New("kolobraid: view halted")
	// ErrDiverged is returned when this peer's running digest differs from one that a quorum of seats claimed.
	ErrDiverged = errors.New("kolobraid: view diverged from a certified digest")
	// ErrErased is returned when an entry the braid needs was erased from the own strand.
	ErrErased = errors.New("kolobraid: strand entry erased")
	// ErrEquivocation is returned when a writer signed two histories of its strand.
	ErrEquivocation = errors.New("kolobraid: writer signed two histories")
	// ErrWrongApp is returned when an app tag differs from the genesis tag.
	ErrWrongApp = errors.New("kolobraid: wrong app tag")
	// ErrWrongGroup is returned for an entry or message of another group.
	ErrWrongGroup = errors.New("kolobraid: wrong group")
	// ErrCorrupt is returned for stored data that does not decode or verify.
	ErrCorrupt = errors.New("kolobraid: corrupt data")
	// ErrProtocol is returned for a stream message that breaks the protocol.
	ErrProtocol = errors.New("kolobraid: protocol violation")
	// ErrUnconfirmed is returned when the own strand is not yet confirmed and the call's context ended.
	ErrUnconfirmed = errors.New("kolobraid: own strand not confirmed")
	// ErrStrandLost is returned when a history of the own strand conflicts with the local one.
	ErrStrandLost = errors.New("kolobraid: own strand lost")
	// ErrBadSeed is returned when the seed entries of a successor braid do not match their content digest.
	ErrBadSeed = errors.New("kolobraid: seed does not match its digest")
	// ErrReorged is returned by Entries when a position it already yielded changed.
	ErrReorged = errors.New("kolobraid: order changed")
	// ErrKnownStrand is returned by Admit for a strand log ID that is already used or known.
	ErrKnownStrand = errors.New("kolobraid: strand already known")
	// ErrGroupFull is returned by CheckAdmit when the group already has MaxMembers active members.
	ErrGroupFull = errors.New("kolobraid: group full")
	// ErrActiveKey is returned by Admit for a key that is already an active member.
	ErrActiveKey = errors.New("kolobraid: key already active")
	// ErrMalformed is returned by a decoder for bytes that break a format rule or are not canonical.
	ErrMalformed = errors.New("kolobraid: malformed encoding")
)

Functions

func PrefixBackend

func PrefixBackend(b kolostore.Backend, prefix []byte) kolostore.Backend

PrefixBackend returns a view of b in which every key starts with prefix, so several braids and other Kolo users can share one backend; no prefix may be a prefix of another. Closing the view leaves b open. An empty prefix returns b itself.

func Reject

func Reject(reason string) error

Reject returns the error that apply returns to refuse an entry: the entry's writes are discarded and every peer records it as rejected. The reason is for the application's own errors and is never stored.

Types

type AdmitOptions

type AdmitOptions struct {
	// Roles are the joiner's roles; nil makes it a plain member that is neither admin nor settler, or, with Replace, keeps the
	// roles of the active key.
	Roles *Role
	// GrowSettlers makes the joiner an admin while the braid has fewer than MinSettlers - 1 admins and a settler while it has
	// fewer than MinSettlers seats, and appends the Settlers entry when one is due. An admin can add and remove anyone, and a
	// settler that signs two histories halts settlement for good, so use it only for joiners you trust that far. It cannot be
	// combined with Roles.
	GrowSettlers bool
	// Replace allows a key that is already active, with a new strand.
	Replace bool
}

AdmitOptions change what Admit appends.

type ApplyFunc

type ApplyFunc func(tx *Tx, e *Entry) error

ApplyFunc turns one entry into writes on the view. It must be a pure deterministic function of the view before e, e and the roster at e's position: no clock, no randomness, no map iteration order, no I/O, no state of its own. It is called for every effective entry of kinds genesis, data, AddMember, RemoveMember, Settlers and Evidence. Nil commits tx's writes; an error wrapping ErrRejected (see Reject) discards them and records the entry as rejected on every peer; any other error and a panic discard them and halt the view on this peer. A Tx call that returned ErrViewLimit rejects the entry on every peer, whatever apply returns. tx and e are valid only during the call. apply can run on several goroutines at once and more than once for one position (tentatively, at settlement, after Open, in Braid.SettledAt), so it must never call a method of the Braid: a SettledAt from apply waits for itself until its context ends.

type Braid

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

Braid is an open braid: the strands of its members merged into one order, applied to a view. It is safe for concurrent use.

func Create
func Create(ctx context.Context, id *koloid.Identity, cfg GroupConfig, opts Options) (*Braid, error)

Create makes a new braid with id as its founder: its strand and the genesis entry that fixes cfg. The founder is the only admin and settler, and its strand is confirmed at once. An error after the genesis is stored leaves the braid to Open.

func Open
func Open(ctx context.Context, id *koloid.Identity, opts Options) (*Braid, error)

Open opens the braid stored in opts.Backend under opts.Prefix. After every Open the own strand is unconfirmed until a member, a pin or, for a braid that never had another member, its own storage confirms it; writing calls wait for that.

func Succeed
func Succeed(ctx context.Context, id *koloid.Identity, old *Braid, cfg GroupConfig, opts Options) (*Braid, error)

Succeed starts a successor of old, for a braid whose settler quorum is lost: a new braid whose genesis names old, its settled position p and the content digest of its settled view at p, followed by seed entries that copy that view. Positions continue at p + 1. The caller must be an admin of old's settled roster at p. Members join the successor again; tentative entries of old are not carried.

func (Braid) AddMember
func (b *Braid) AddMember(ctx context.Context, w NewMember) (EntryRef, error)

AddMember appends an AddMember entry for w, or changes w's roles or strand when its key is active. The caller must be an admin; the header must be w's signed log header for w.Strand.

func (Braid) Admit
func (b *Braid) Admit(ctx context.Context, joiner ed25519.PublicKey, request []byte, opts *AdmitOptions) ([]byte, error)

Admit appends an AddMember entry for the joiner whose key and join request are given, and with GrowSettlers a Settlers entry when one is due, and returns the welcome to seal to the joiner. Without Roles or GrowSettlers the joiner is a plain member: it writes entries but is no admin and no settler. The caller must be an admin (ErrNotAdmin, ErrRemoved). It returns ErrActiveKey for an active key without opts.Replace, ErrKnownStrand for a strand that is used or known and ErrInvalidArgument for Roles together with GrowSettlers. When the welcome is not delivered, or Admit fails after the AddMember entry, remove the joiner with RemoveMember. Calls run one at a time.

func (Braid) Append
func (b *Braid) Append(ctx context.Context, body []byte) (EntryRef, error)

Append writes a data entry to the own strand and returns its reference; whether it takes effect is decided at its position. After every Open it first waits, as long as ctx allows, until the own strand is confirmed (ErrUnconfirmed when ctx ends). A braid entry can never be erased: every peer keeps every entry and its key.

func (Braid) CheckAdmit
func (b *Braid) CheckAdmit(joiner ed25519.PublicKey, request []byte) error

CheckAdmit reports, without writing anything, what Admit would refuse now for joiner and request: ErrNotAdmin, ErrRemoved or ErrNotMember for this peer, ErrActiveKey, ErrKnownStrand (a used, followed or pending strand), and ErrGroupFull, which Admit itself does not return: it appends an AddMember entry that the roster then leaves void. It does not wait for the own strand to be confirmed, as Admit does.

func (Braid) Close
func (b *Braid) Close() error

Close stops the braid and closes its strands and view; the backend stays open. A second Close returns nil.

func (Braid) Entries
func (b *Braid) Entries(from uint64) iter.Seq2[Ordered, error]

Entries yields the order from position from on, as of the call: the settled prefix, then the planned tentative tail up to MaxTail entries. When a reorg changes a position it already yielded, it ends with ErrReorged.

func (Braid) GroupID
func (b *Braid) GroupID() GroupID

GroupID returns the group ID: the entry ID of the genesis entry.

func (Braid) Next
func (b *Braid) Next(ctx context.Context) (Event, error)

Next returns the next event, waiting as long as ctx allows. EventRemoved, EventSettlementHalted, EventStrandLost, EventHalted and EventDiverged are never dropped; other events past MaxEvents are dropped oldest first and counted in Status.EventsDropped.

func (Braid) PublicKey
func (b *Braid) PublicKey() ed25519.PublicKey

PublicKey returns the key of the identity this peer runs the braid with.

func (Braid) RemoveMember
func (b *Braid) RemoveMember(ctx context.Context, key ed25519.PublicKey) (EntryRef, error)

RemoveMember appends a RemoveMember entry for key. The caller must be an admin. Entries of that member ordered before the removal keep their effect; those ordered after it are void.

func (Braid) ServeConn
func (b *Braid) ServeConn(ctx context.Context, conn Conn) error

ServeConn syncs the braid with the peer on conn, direct or relayed, until ctx or the connection ends or the braid closes: it serves the strands this peer holds through kolo-sync, pulls the peer's, and runs the braid's own messages on unidirectional streams. It must be the only caller of conn's AcceptStream and AcceptUniStream. It returns nil when ctx or conn ends, ErrClosed when the braid closes, an error wrapping ErrProtocol after it closed the conn of a peer that broke the protocol, and one wrapping ErrNotMember after it closed the conn of a peer that was neither a member nor a pin after 60 s. Pass only a connection whose peer key was proved in a handshake: the braid trusts conn.RemotePublicKey and hands that key's owner what a member or a pin gets.

func (Braid) SetSettlers
func (b *Braid) SetSettlers(ctx context.Context, keys []ed25519.PublicKey, rule QuorumRule) (EntryRef, error)

SetSettlers appends a Settlers entry. Under Majority, 3 or 5 settlers give f = 0: one settler that signs two histories can split settled prefixes; 4 under Majority, or TwoThirds from 4, do not. A change that adds settlers activates once they are ready, and the settlers it removes keep their seats until then: retire an old device after Status.Config changes.

func (Braid) Settled
func (b *Braid) Settled() *Snapshot

Settled returns a snapshot of the settled view. Close it when done.

func (Braid) SettledAt
func (b *Braid) SettledAt(ctx context.Context, position uint64) (*Snapshot, error)

SettledAt returns a snapshot of the settled view and roster as they were right after the entry at position was applied: what a member's roles, the settler seats (Snapshot.Settlers) and the records of the view were at that position. It replays the settled order into scratch storage under the braid's prefix, calling apply on this goroutine; one call runs at a time. A replay kept at the last batch end it reached makes a later position cost a copy of the view and the positions after that end; an earlier position replays from the braid's first one. Close the snapshot when done; Close of the braid closes it. A position not settled yet returns ErrNotFound, and one before the braid's first position ErrInvalidArgument.

func (Braid) Status
func (b *Braid) Status() Status

Status returns the braid's state.

func (Braid) Topic
func (b *Braid) Topic() [32]byte

Topic returns the kolo-swarm topic of the braid.

func (Braid) View
func (b *Braid) View() *Snapshot

View returns a snapshot of the view as of now: settled plus tentative entries. Close it when done.

type Conn

type Conn interface {
	RemotePublicKey() ed25519.PublicKey
	OpenStream(ctx context.Context) (*kolotransport.Stream, error)
	AcceptStream(ctx context.Context) (*kolotransport.Stream, error)
	OpenUniStream(ctx context.Context) (*kolotransport.SendStream, error)
	AcceptUniStream(ctx context.Context) (*kolotransport.ReceiveStream, error)
	Context() context.Context
	Close() error
	CloseWithError(code uint64, msg string) error
}

Conn is an authenticated connection to one peer, direct or relayed, such as a *kolosecure.Conn, a *kolorelay.Conn or a koloswarm.Conn; RemotePublicKey must return the key the peer proved in the end-to-end handshake.

type Digest

type Digest [32]byte

Digest is a running digest, a content digest or a claim.

func (Digest) String
func (d Digest) String() string

String returns the digest as lowercase hex.

type Entry

type Entry struct {
	ID       EntryID
	Writer   ed25519.PublicKey
	Strand   kololog.LogID
	Index    uint64
	Position uint64
	Kind     Kind
	Body     []byte
	Links    []Link
}

Entry is one entry as apply sees it. It carries no settled flag and no time.

type EntryID

type EntryID [32]byte

EntryID names one strand entry: the BLAKE2b-256 hash of its signed kolo-log record.

func (EntryID) String
func (id EntryID) String() string

String returns the ID as lowercase hex.

type EntryRef

type EntryRef struct {
	Strand kololog.LogID
	Index  uint64
	ID     EntryID
}

EntryRef names one entry the braid wrote: its strand, its index there and its ID.

func WelcomeEntry
func WelcomeEntry(welcome []byte) (EntryRef, error)

WelcomeEntry returns the AddMember entry a welcome names: the strand of the admitting peer, the index there and the entry ID.

type Event

type Event struct {
	Kind     EventKind
	Position uint64
	Member   ed25519.PublicKey
	Err      error
}

Event is one thing that happened to the braid, as Next returns it.

type EventKind

type EventKind int

EventKind says what an Event reports.

const (
	EventApplied          EventKind = iota + 1 // applied through Position (tentative or settled)
	EventReorg                                 // the tentative order changed from Position on
	EventSettled                               // settled through Position
	EventCertified                             // a claim at Position matched q seats
	EventMemberAdded                           // Member became active at Position
	EventMemberRemoved                         // Member became inactive at Position
	EventRemoved                               // this peer's own strand became inactive at Position
	EventEquivocation                          // evidence against Member was found or ordered
	EventSettlementHalted                      // Member, a seat of the current config, signed two histories; that config settles no more
	EventStrandLost                            // a peer holds a history of the own strand that conflicts with ours; writes are refused
	EventStrandCaughtUp                        // the own strand was behind and was rebuilt from a longer consistent copy
	EventHalted                                // apply failed at Position; Err says why
	EventDiverged                              // this peer's running digest differs from a certified claim
)

Event kinds.

type GroupConfig

type GroupConfig struct {
	// App is the application tag, 1 to 64 bytes of UTF-8.
	App string
	// Quorum is the quorum rule; the default is Majority.
	Quorum QuorumRule
	// MaxMembers is the most active members; the default 64 is one node's default peer budget, the range is 2 to 1024.
	MaxMembers int
	// MaxSettlers is the most settlers; the default is 7 (Majority then tolerates 3 offline) or MaxMembers if smaller, the range is 1 to 64.
	MaxSettlers int
	// MinSettlers is the seat count Admit grows to; the default is 4 (Majority has q 3, so one offline and one equivocating seat are tolerated) or MaxSettlers if smaller, the range is 1 to MaxSettlers.
	MinSettlers int
	// MaxBody is the longest data body; the default 1 MiB is the view's value bound, the range 1 KiB to 3 MiB keeps an entry within one 4 MiB sync message.
	MaxBody int
	// CheckpointEvery is the settled positions between digest claims; the default is 1024, the range 64 to 2^20.
	CheckpointEvery int
}

GroupConfig is fixed at Create and agreed by every peer through the genesis entry.

func (GroupConfig) Validate
func (c GroupConfig) Validate() error

Validate returns an error wrapping ErrInvalidConfig unless every field is inside its range.

func (GroupConfig) WithDefaults
func (c GroupConfig) WithDefaults() GroupConfig

WithDefaults returns c with every zero field except App set to its default.

type GroupID

type GroupID [32]byte

GroupID is the entry ID of the genesis entry.

func (GroupID) String
func (id GroupID) String() string

String returns the ID as lowercase hex.

type JoinRequest

type JoinRequest struct {
	Strand  kololog.LogID
	Header  []byte
	AppData []byte
}

JoinRequest is what a joiner sends in a join request: its new strand and app data.

func ParseJoinRequest
func ParseJoinRequest(b []byte) (JoinRequest, error)

ParseJoinRequest parses a join request. The header must be signed by the key it names, name the strand and use the Bytes encoding; whether that key is the joiner's is for the caller to check. It returns an error wrapping ErrMalformed.

type Joining

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

Joining is a strand made for a braid this peer has not joined yet: its join request goes to an admin, whose welcome completes the join.

func NewJoin
func NewJoin(ctx context.Context, id *koloid.Identity, opts Options) (*Joining, error)

NewJoin creates a new strand for id in opts.Backend under opts.Prefix, for a braid to join; nothing else may be stored under that prefix. When a join of id is pending there, from a NewJoin before a restart, it returns that join again, whose request and welcome stay valid.

func (Joining) Complete
func (j *Joining) Complete(ctx context.Context, welcome []byte) (*Braid, error)

Complete opens the braid a welcome names. The returned braid syncs through ServeConn: once a member serves the founder strand's genesis entry it starts, and it checks the welcome's AddMember entry when it holds the inviter's strand. Until then, and until its own AddMember entry is ordered, writing calls wait, and the view is empty. An error after the welcome is stored leaves the join to Open.

func (Joining) Request
func (j *Joining) Request(appData []byte) ([]byte, error)

Request returns the join request to send to an admin: the new strand, its signed log header and appData, which the admin's application reads.

type Kind

type Kind uint8

Kind is the kind of an entry.

const (
	KindGenesis Kind = iota
	KindData
	KindAddMember
	KindRemoveMember
	KindSettlers
	KindEvidence
	KindPulse
	KindSeed
)

Entry kinds. Their numbers are part of the format.

type Limits

type Limits struct {
	// MaxTail is the most tentative entries applied; default 2048 (a reorg replays them within 50 ms), 64 to 2^20.
	MaxTail int
	// MaxTailBytes bounds the tentative overlay; default 4 x 16 x MaxBody (four entries at the write budget) within 1 MiB to 4 GiB.
	MaxTailBytes int64
	// MaxPendingBytes bounds the entries that wait for a predecessor; default 16 MiB, 1 MiB to 1 GiB.
	MaxPendingBytes int64
	// MaxForks is how many second histories of one strand are kept; default 4, 1 to 64: a restored backup that writes on is one,
	// and each one a hostile pair signs costs every peer a segment and a slot in later clocks. At the bound the entries of the next
	// history are refused and no longer fetched, so an entry that needs one never places on this peer.
	MaxForks int
	// MaxPullAhead is how far past its settled length a member's strand is fetched, and a settler's past its newest pulse
	// held; what a held entry links is fetched past it. It is checked every AnnounceGap. Default MaxTail, 64 to 2^20.
	MaxPullAhead int
	// PulseGap is the least time between two pulses of this seat; default 500ms, 10ms to 1m.
	PulseGap time.Duration
	// PivotWait is how long a seat waits for a pivot before voting without it; default 3s, 100ms to 5m.
	PivotWait time.Duration
	// AnnounceGap is the least time between two head announcements on one connection; default 100ms, 10ms to 10s.
	AnnounceGap time.Duration
	// ConfirmWait is how long a seat waits for the other seats' heads after Open; default 10s, 1s to 5m.
	ConfirmWait time.Duration
	// MaxEvents is how many events wait for Next; default 1024, 16 to 2^16.
	MaxEvents int
}

Limits are the local bounds of a peer. A zero field takes its default.

type Member

type Member struct {
	Key    ed25519.PublicKey
	Strand kololog.LogID
	Roles  Role
	// Seat is true for a seat of the settler config of the roster's position, the one Snapshot.Settlers returns.
	Seat bool
}

Member is one member of the roster.

type NewMember

type NewMember struct {
	Key    ed25519.PublicKey
	Strand kololog.LogID
	// Header is the strand's signed log header: at most MaxHeader bytes, signed by Key, naming Strand and the Bytes encoding.
	Header []byte
	Roles  Role
}

NewMember is the body of an AddMember entry, and what AddMember takes.

func (NewMember) Kind
func (NewMember) Kind() Kind

Kind returns KindAddMember.

type Options

type Options struct {
	// Backend holds every strand, the view and the braid's own records; required. Close does not close it.
	Backend kolostore.Backend
	// Prefix is the key prefix of the braid inside Backend, so several braids may share one; nil keeps the braid at the root of
	// Backend. A prefix that nests with another braid's in the same Backend is refused; see PrefixBackend.
	Prefix []byte
	// App is required and must equal the genesis tag.
	App string
	// Apply turns ordered entries into the view; required.
	Apply ApplyFunc
	// Pins are peers that get ciphertext only and can confirm the own strand.
	Pins []ed25519.PublicKey
	// Limits are the local bounds; nil means the defaults.
	Limits *Limits
	// AppendUnconfirmed writes before the own strand is confirmed after Open. A device restored from an older copy then signs a
	// second history of its strand; for a settler that halts settlement, and with 3 or 5 settlers under Majority it can split it.
	AppendUnconfirmed bool
	// Rebuild replays the view from genesis along the stored committed pivots at Open.
	Rebuild bool
	// Predecessor is the old braid, as this peer holds it, of a successor braid it joins: once the successor's genesis is
	// held, its founder must have been an admin of the old settled roster at the old position the genesis names, and the old
	// settled view replayed to that position must have the content digest it names; otherwise the braid halts with
	// ErrNotAdmin or ErrBadSeed, or with ErrNotFound while the old braid has not settled that position (Open checks again).
	// Without it a joiner trusts the successor's founder for both.
	Predecessor *Braid
	// Logger receives operational logs; nil means none. Keys, bodies and view data are never logged.
	Logger *slog.Logger
}

Options are local to this peer.

type Ordered

type Ordered struct {
	Entry
	// Settled is set for an entry of the settled prefix; Void for one that takes no effect at its position; Rejected for one that
	// apply refused (known for settled entries once applied, and for applied tentative ones).
	Settled, Void, Rejected bool
}

Ordered is one entry at its position in the order.

type QuorumRule

type QuorumRule uint8

QuorumRule says how many settlers must agree.

const (
	// Majority needs floor(n/2) + 1 seats and tolerates crashes.
	Majority QuorumRule = 1
	// TwoThirds needs floor(2n/3) + 1 seats and tolerates equivocating seats as well.
	TwoThirds QuorumRule = 2
)

type Role

type Role uint8

Role is a bit set of the rights of a member.

const RoleAdmin Role = 1

RoleAdmin may change the membership.

type Settlers

type Settlers struct {
	// Config is the config number, as in Status.Config; Rule is its quorum rule and Quorum its q over Seats.
	Config uint64
	Rule   QuorumRule
	Quorum int
	// Seats are the config's seats in key order, each with the strand that counts for it and the roles the snapshot's roster
	// gives its key: none for a removed member, which keeps its seat until a config without it activates.
	Seats []Member
}

Settlers is a settler config as a snapshot holds it.

type Snapshot

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

Snapshot is a frozen read view of the braid's view: it keeps showing the state it was taken at while settlement goes on. Close it when done: an open snapshot makes every commit keep the values it replaces.

func (Snapshot) Close
func (s *Snapshot) Close() error

Close releases the snapshot's hold on the overlay and the backend, and deletes the scratch storage of a snapshot from SettledAt; a second Close returns nil.

func (Snapshot) Err
func (s *Snapshot) Err() error

Err returns the error that first ended a Scan of the snapshot early, nil when none did: check it after a Scan loop, since a scan cut short otherwise looks like a shorter range. It is ErrClosed for a Scan of a closed snapshot. It stays once set: ScanErr reports the error of one scan.

func (Snapshot) Get
func (s *Snapshot) Get(key []byte) ([]byte, error)

Get returns a copy of the value of key at the snapshot, or ErrNotFound.

func (Snapshot) Members
func (s *Snapshot) Members() []Member

Members returns the roster of the snapshot.

func (Snapshot) Position
func (s *Snapshot) Position() uint64

Position returns the position of the last entry applied in the snapshot, or 0 when none is; 0 is also the position of a genesis applied alone, so a caller that must tell them apart compares with Status().Settled.

func (Snapshot) Scan
func (s *Snapshot) Scan(start, end []byte) iter.Seq2[[]byte, []byte]

Scan yields copies of the pairs with a key in [start, end) in ascending key order; an empty end means no upper bound. A storage error, or a Close, ends the iteration early, and Err then reports it.

func (Snapshot) ScanErr
func (s *Snapshot) ScanErr(start, end []byte) (iter.Seq2[[]byte, []byte], func() error)

ScanErr is Scan with an error of its own: once the iteration ended, the function reports the error that ended it early, nil when none did, whatever other scans of the snapshot met.

func (Snapshot) Settlers
func (s *Snapshot) Settlers() Settlers

Settlers returns the settler config whose seats Member.Seat marks in the snapshot, read with the roster in one step: the config of the batch that settled the snapshot's last entry, or for View, while it holds tentative entries, the config they are applied under. It is the zero Settlers for a closed snapshot and for one without a roster.

type Status

type Status struct {
	// Settled and Tentative are the next position after the settled entries and after the tentative ones.
	Settled, Tentative uint64
	// Tail is the number of tentative positions, pulses included: a pulse takes a position but is never applied, so an idle
	// braid can keep a tail of pulses.
	Tail int
	// Config is the current settler config number; Seats and Quorum are its seat count and q.
	Config        uint64
	Seats, Quorum int
	// SingleSettler is set when one seat settles a braid with more than one member: losing that device stops settlement.
	SingleSettler bool
	// PendingConfig holds the seats of a pending config, nil when none.
	PendingConfig []Member
	// AwaitingReadiness holds the seats a pending config adds without a readiness pulse that counts: one that the last pivot
	// committed before the config became pending does not hold.
	// Once none is awaited, the online current settlers pulse until the config activates, with no other entry needed.
	AwaitingReadiness []Member
	// Unconfirmed is set until the own strand is confirmed after Open.
	Unconfirmed bool
	// StrandLost is set when a history of the own strand conflicts with ours: writes are refused.
	StrandLost bool
	// SeededFrom is set in a successor braid: the braid it continues.
	SeededFrom *GroupID
	// SettlementHalted says why the current config settles no more, nil while it settles.
	SettlementHalted error
	// Halted says why apply stopped on this peer, nil while it runs.
	Halted error
	// EventsDropped counts the events dropped past MaxEvents.
	EventsDropped uint64
}

Status describes the braid's state.

type Tx

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

Tx is the handle apply works on: reads see the view before the entry plus the entry's own writes, writes are buffered and committed together when apply returns nil. One Tx serves one entry; after apply returns every method fails with ErrTxDone.

func (Tx) Delete
func (tx *Tx) Delete(key []byte) error

Delete removes key; a key that does not exist is not an error. The limits of Put apply.

func (Tx) DeleteRange
func (tx *Tx) DeleteRange(start, end []byte) error

DeleteRange removes every key in [start, end); an empty end means no upper bound. The limits of Put apply to both bounds.

func (Tx) Get
func (tx *Tx) Get(key []byte) ([]byte, error)

Get returns a copy of the value of key, or ErrNotFound.

func (Tx) Member
func (tx *Tx) Member(key ed25519.PublicKey) (Member, bool)

Member returns the roster entry for key at the position of this entry.

func (Tx) Members
func (tx *Tx) Members() []Member

Members returns the roster at the position of this entry.

func (Tx) Put
func (tx *Tx) Put(key, value []byte) error

Put sets key to value. A key over 32 KiB, a value over 1 MiB, or a total over the entry's write budget returns ErrViewLimit, and the entry is then rejected on every peer, whatever apply returns.

func (Tx) Scan
func (tx *Tx) Scan(start, end []byte) iter.Seq2[[]byte, []byte]

Scan yields copies of the pairs with a key in [start, end) in ascending key order, the entry's own writes included; an empty end means no upper bound. The iteration sees the writes made before it started, not those made while it runs. After apply returns it yields nothing, and so it does after a storage error, which also halts the view.

Package kv

github.com/ciranda-dev/kolo-braid/kv

Package kv is a key-value map kept in a braid's view. Puts and deletes are data entries, applied in the braid's order: the last effective operation on a key wins, on every peer alike, and no clock takes part. The order among concurrent writes is decided by the braid and is not fair, so a rule such as "the first write wins" must not rely on it. The map has no access control: any active member can put or delete any key. When keys belong to members, check Entry.Writer (and Tx.Member for its roles) in the apply function before Store.Apply.

A kv entry's body is, in kolo-codec: string "kolo-braid/kv/v0" ‖ uvarint op (1 put, 2 delete) ‖ bytes(key) ‖ bytes(value), the value empty for a delete.

Constants

const (
	// MaxKeySize is the longest key in bytes, with the store's prefix: the bound of a view key.
	MaxKeySize = kolobraid.MaxViewKey
	// MaxValueSize is the longest value in bytes: the bound of a view value.
	MaxValueSize = kolobraid.MaxViewValue
)

Types

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

Store is a kv map whose pairs live in the view under its prefix: key k is the view key prefix ‖ k. No other key of the application's view may start with the prefix.

func New
func New(prefix []byte) *Store

New returns a store with the given view key prefix; prefix plus key is at most MaxKeySize bytes.

func (Store) Apply
func (s *Store) Apply(tx *kolobraid.Tx, e *kolobraid.Entry) (handled bool, err error)

Apply applies e when it is a data entry whose body starts with the kv tag, and reports false for every other entry, so that an application routes its own entries next to it. A kv body that does not decode, or whose key does not fit with the prefix, is rejected: the same on every peer.

func (Store) Delete
func (s *Store) Delete(ctx context.Context, b *kolobraid.Braid, key []byte) error

Delete appends an entry that removes key; a key that does not exist is not an error.

func (Store) Get
func (s *Store) Get(v *kolobraid.Snapshot, key []byte) ([]byte, error)

Get returns the value of key in v, or kolobraid.ErrNotFound. Read from Braid.Settled for values that never change again, from Braid.View for settled plus tentative ones.

func (Store) Put
func (s *Store) Put(ctx context.Context, b *kolobraid.Braid, key, value []byte) error

Put appends an entry that sets key to value. It takes effect at the entry's position in the order; a body over the braid's MaxBody returns kolobraid.ErrTooLarge.

func (Store) Range
func (s *Store) Range(v *kolobraid.Snapshot, start, end []byte) iter.Seq2[[]byte, []byte]

Range yields the pairs of v with a key in [start, end) in ascending key order; an empty end means no upper bound, as in Snapshot.Scan, and start >= end yields nothing. A storage error ends it early, and v.Err reports it.

Package devices

github.com/ciranda-dev/kolo-braid/devices

Package devices keeps the device certificates and revocations of a group's persons in a braid's view and admits a certified device into a group its person already belongs to. The rules are in docs/guide.md.

Constants

const (
	// DefaultMaxCertsPerPerson is the default of Options.MaxCertsPerPerson.
	DefaultMaxCertsPerPerson = 1024
	// DefaultMaxRevocationsPerDevice is the default of Options.MaxRevocationsPerDevice.
	DefaultMaxRevocationsPerDevice = 64
)

Variables

var (
	// ErrTooManyDevices is returned by Admit when Options.MaxDevices is set and the person already has that many devices.
	ErrTooManyDevices = errors.New("kolobraid: too many devices of this person in the group")
	// ErrNotProven is returned by Admit and Record when the certificate or the proof of the joiner does not hold.
	ErrNotProven = errors.New("kolobraid: device certificate not proven")
	// ErrUnknownPerson is returned by Admit when no admin has anchored a device of the person in the group.
	ErrUnknownPerson = errors.New("kolobraid: person has no anchored device in the group")
	// ErrUnknownDevice is returned by Verify for a device without a stored certificate of the person.
	ErrUnknownDevice = errors.New("kolobraid: no certificate for this device")
	// ErrNotRecorded is returned when the roster applied or rejected the record without holding it anchored, or when the caller's
	// context ended first; in that case the entry may still apply later, anchored or not, and nothing else was written.
	ErrNotRecorded = errors.New("kolobraid: the roster did not take the record")
	// ErrNotAdmitted is returned by Admit when the AddMember entry was written but the group did not take the member (it is void,
	// for example in a full group), or when the caller's context ended first, in which case the entry may still apply later:
	// remove the joiner with RemoveMember if no welcome reaches it.
	ErrNotAdmitted = errors.New("kolobraid: the group did not take the member")
)

Functions

func AppData
func AppData(request []byte) ([]byte, error)

AppData returns the application data NewJoinRequest carried in request; ErrNotProven when it carries no device proof.

func CertBody
func CertBody(c *koloid.DeviceCert) ([]byte, error)

CertBody returns the body of the data entry that records c in a roster.

func Certificate
func Certificate(request []byte) (*koloid.DeviceCert, error)

Certificate returns the certificate NewJoinRequest carried in request, not verified; ErrNotProven when it carries none.

func NewJoinRequest
func NewJoinRequest(j *kolobraid.Joining, id *koloid.Identity, cert *koloid.DeviceCert, group kolobraid.GroupID, appData []byte) ([]byte, error)

NewJoinRequest returns the join request of j with a proof that id holds the key cert certifies, bound to group, which the application tells the joiner (for example in its invite). appData comes back through AppData.

func RevocationBody
func RevocationBody(r *koloid.Revocation, target *koloid.DeviceCert) ([]byte, error)

RevocationBody returns the body of the data entry that records r; an approver-signed revocation needs target, the other kinds take nil.

Types

type Options
type Options struct {
	// MaxDevices, when positive, is the most seats of one person that Admit lets in: the members that hold an anchored certificate
	// of it, revoked or not. Zero, the default, is no ceiling: the group's MaxMembers seats are the only bound. Local to the
	// admitting peer.
	MaxDevices int
	// MaxCertsPerPerson is the most device certificates a view holds for one person; the next is rejected. Default
	// DefaultMaxCertsPerPerson, range 1 to 2^20: it bounds the scan of one apply.
	MaxCertsPerPerson int
	// PersonCertReserve of those slots are kept for certificates the person key issued, so a stolen approver cannot fill the
	// roster: approver-issued certificates stop at MaxCertsPerPerson - PersonCertReserve. Default an eighth of
	// MaxCertsPerPerson, at least 1 when MaxCertsPerPerson is above 1; range 0 to MaxCertsPerPerson; zero stands for the default,
	// and -1 reserves nothing.
	PersonCertReserve int
	// MaxRevocationsPerDevice is the most approver-signed revocations kept for one device key, one per certificate it had; the
	// next is rejected. Default DefaultMaxRevocationsPerDevice, range 1 to 2^16: an arbitrary safety bound.
	MaxRevocationsPerDevice int
	// Now is the clock of Admit; nil means time.Now.
	Now func() time.Time
}

Options are the choices of a Store. The three bounds of apply decide which entries are rejected, so every peer of a group must use the same values, as it must run the same apply function.

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

Store reads and writes the roster in a view under its key prefix; no other view key may start with the prefix.

func New
func New(prefix []byte, o *Options) (*Store, error)

New returns a store whose records live in the view under prefix, which may be empty.

func (Store) Admit
func (s *Store) Admit(ctx context.Context, b *kolobraid.Braid, joiner ed25519.PublicKey, request []byte) ([]byte, error)

Admit admits the device whose key and join request are given when the request proves a valid certificate of the joiner's key for a person an admin already anchored in the group, and returns the welcome as Braid.Admit does; the checks and their order are in the guide. The caller must be an admin. Every wait ends with ctx.

func (Store) Anchored
func (s *Store) Anchored(v *kolobraid.Snapshot, person, device ed25519.PublicKey) (bool, error)

Anchored reports whether an admin recorded the certificate of device, which is what lets Admit trust the person.

func (Store) Apply
func (s *Store) Apply(tx *kolobraid.Tx, e *kolobraid.Entry) (handled bool, err error)

Apply applies e when it is a roster entry and reports false for every other entry; see the guide for what it rejects.

func (Store) Cert
func (s *Store) Cert(v *kolobraid.Snapshot, person, device ed25519.PublicKey) (*koloid.DeviceCert, error)

Cert returns the certificate of device in the roster of person at v, the one with the highest serial, not verified; it returns kolobraid.ErrNotFound for a device with none.

func (Store) CertTx
func (s *Store) CertTx(tx *kolobraid.Tx, person, device ed25519.PublicKey) (*koloid.DeviceCert, error)

CertTx is Cert inside apply: it reads the roster at the position of the entry that tx applies, with the writes tx made so far.

func (Store) Devices
func (s *Store) Devices(v *kolobraid.Snapshot, person ed25519.PublicKey) ([]*koloid.DeviceCert, error)

Devices returns the certificates of person at v in device key order, not verified.

func (Store) Record
func (s *Store) Record(ctx context.Context, b *kolobraid.Braid, c *koloid.DeviceCert) error

Record appends the certificate c as a roster entry from this peer, which must be an admin, and returns once the roster holds it anchored. An admin's record anchors a person: use it for the first device of a person, after the admin decided to admit it. It returns ErrNotRecorded when the entry was applied or rejected without an anchored certificate, or the context ended.

func (Store) Revocations
func (s *Store) Revocations(v *kolobraid.Snapshot, person, device ed25519.PublicKey) ([]*koloid.Revocation, error)

Revocations returns the revocations of the device key that apply to person at v, for koloid.VerifyOptions; see the guide for the retirement of approvers. A certificate an approver issued is also void when the approver is revoked: RevocationsOf returns both, as Verify uses them.

func (Store) RevocationsOf
func (s *Store) RevocationsOf(v *kolobraid.Snapshot, person ed25519.PublicKey, c *koloid.DeviceCert) ([]*koloid.Revocation, error)

RevocationsOf returns the revocations at v that can void c for person, the set Verify passes to koloid.VerifyDevice: those of c's device and, for a certificate an approver issued, those of the approver.

func (Store) RevocationsOfTx
func (s *Store) RevocationsOfTx(tx *kolobraid.Tx, person ed25519.PublicKey, c *koloid.DeviceCert) ([]*koloid.Revocation, error)

RevocationsOfTx is RevocationsOf inside apply, at the position of the entry that tx applies: with koloid.DeviceCert.Verify it tells whether c was revoked at or before that position.

func (Store) RevocationsTx
func (s *Store) RevocationsTx(tx *kolobraid.Tx, person, device ed25519.PublicKey) ([]*koloid.Revocation, error)

RevocationsTx is Revocations inside apply: it reads the roster at the position of the entry that tx applies, with the writes tx made so far. Like Revocations it leaves out the revocations of the certificate's issuer: RevocationsOfTx has them.

func (Store) Verify
func (s *Store) Verify(v *kolobraid.Snapshot, person, device ed25519.PublicKey, now time.Time, context string, msg, sig []byte) error

Verify checks that sig is a signature of msg under context by device, a device of person, at time now (zero means now), with koloid.VerifyDevice on the stored certificate and revocations. The person is the caller's, never read from a certificate.

Package kolobraidtest

github.com/ciranda-dev/kolo-braid/kolobraidtest

Package kolobraidtest checks that an apply function keeps the contract of kolobraid: its effect depends only on the view before the entry, the entry and the roster. It replays a recorded history through many settlement paths and delivery orders and compares running digests.

Functions

func CheckApply
func CheckApply(t TB, apply kolobraid.ApplyFunc, entries []kolobraid.Entry)

CheckApply replays entries, which are in their final order, through many paths and fails t when two of them end with a different running digest or view: single and random batch replays, tentative application with a reorganisation and promotion, and restarts between batches. Entries without an ID get one; the keys that wrote them form the roster, each an admin and a seat, and membership entries never change it, so an apply that reads roles is checked for that roster only.

func CheckUpgrade
func CheckUpgrade(t TB, old, upgraded kolobraid.ApplyFunc, entries []kolobraid.Entry, marker int)

CheckUpgrade replays entries with the old and the new apply function and fails t unless the running digests are equal at every position before marker, the position of the entry that starts the new behaviour. The roster is CheckApply's.

Types

type Divergence
type Divergence struct {
	Position uint64
	// Replica differs from replica 0 at Position; Want is replica 0's running digest there and Got the other's.
	Replica   int
	Want, Got kolobraid.Digest
}

Divergence is the first position at which two replicas of one history have different running digests.

func FindDivergence
func FindDivergence(apply kolobraid.ApplyFunc, entries []kolobraid.Entry, replicas int, seed uint64) (*Divergence, error)

FindDivergence runs apply on replicas copies of the history entries (in final order), each fed in its own shuffled delivery order seeded by seed, and returns the lowest position where a running digest differs from replica 0's, nil when every replica agrees, and an error if apply halts. The roster is CheckApply's.

func (Divergence) String
func (d *Divergence) String() string

String describes the divergence for a test failure.

type TB
type TB interface {
	Helper()
	Fatalf(format string, args ...any)
}

TB is the part of testing.TB that the checks use.

Good to know

Defaults

Fixed by the genesis entry (GroupConfig), a zero field takes the default and a value outside its range returns ErrInvalidConfig:

FieldDefaultWhy
QuorumMajority, or TwoThirdscrash faults; TwoThirds when a settler device may be compromised
MaxMembers64, range 2 to 1024one node's default peer budget
MaxSettlers7 or MaxMembers if smaller, range 1 to 64Majority then tolerates 3 offline
MinSettlers4 or MaxSettlers if smaller, range 1 to MaxSettlersone settler offline and one that signs two histories are tolerated
MaxBody1 MiB, range 1 KiB to 3 MiBthe view's value bound
CheckpointEvery1024 settled positions, range 64 to 2^20a divergence is caught within that many

Local to a peer (Limits), a value outside its range returns ErrInvalidArgument:

FieldDefault
MaxTail2048: a reorg replays at most this many entries
MaxPendingBytes16 MiB of entries that wait for a predecessor; one strand holds at most MaxPendingBytes / MaxMembers of it (one entry always fits)
MaxForks4, range 1 to 64: the second histories of one strand a peer keeps; the entries of the next are refused and no longer fetched
MaxPullAheadMaxTail
PulseGap500 ms
PivotWait3 s
AnnounceGap100 ms
ConfirmWait10 s
MaxEvents1024

Security

  • kolo-log signs and encrypts every entry; kolo-braid adds no signature of its own. Every head, record, proof and entry from a peer is verified, and a message that is malformed, over its bound, of another group, version or type, with trailing bytes, or that does not verify closes the connection, as does a request not answered within 60 s.
  • Membership is checked at each entry's position in the order, so every peer decides it the same way. A strand is followed under the key of the AddMember entry that the order makes effective, never under the key of a void one.
  • Evidence counts only when the key that signed both objects is the key of the strand they name.
  • A key that is neither a member's, a settler's nor a pin's gets nothing from kolo-sync, only its ANNOUNCE messages are read past their prefix, and its connection is closed once it has been unknown for 60 s.
  • ServeConn trusts Conn.RemotePublicKey: pass only connections whose key was proved in a handshake, such as a *kolosecure.Conn.
  • The kv map has no access control: any active member writes any key.
  • A person counts for roster.Admit only once an admin recorded a certificate of it, so a plain member cannot invent one. After that, roster.Admit lets in each later device that proves a valid certificate, with no rate limit: the group's seats and MaxCertsPerPerson are the only bounds. Approver-issued certificates cannot fill the roster, since PersonCertReserve keeps 128 of the 1024 slots for the person key.
  • devices.Store.Verify checks a device for the person you pass. Pin the person in your own state, never take it from a certificate.
  • Two running copies of one data directory both write before either sees the other: for a settler that halts settlement, and with 3 or 5 settlers under Majority it can split settled prefixes.

Status

Beta and experimental, like every Kolo library at v0.x: the API may change before v1.0.0.

  • Done: strands, the order with its settled prefix and tentative tail, the apply contract and its checks, membership and admission, settlement with configs and successor braids, sync over direct and relayed connections, the kv helper and the devices package.
  • Tested: unit, property and fuzz tests, model checks of settlement and membership over bounded scopes (scripts/modelcheck.sh), which cover only the sizes they enumerate and are not a proof for every size, and scenarios with several processes on one Mac, on 127.0.0.1 only. The Linux and Windows builds were vetted, not run.
  • Settlement keeps one round mark per settler per round of the current settler config, until the config changes: 16 bytes in memory and one key of about 40 bytes on disk, written once. A braid that settles all day with 4 settlers at the default PulseGap can add up to about 1.4 million a day, about 22 MB of memory and 55 MB of disk; with 64 settlers 16 times that, and more with a shorter PulseGap (up to 50 times at 10 ms). These are upper bounds; slice growth adds up to a quarter to the memory figure. They are what lets a pulse that arrives late get its exact round, and a settler config change removes them.

Errors

ErrorMessage
ErrActiveKeykolobraid: key already active
ErrBadSeedkolobraid: seed does not match its digest
ErrClosedkolobraid: closed
ErrCorruptkolobraid: corrupt data
ErrDivergedkolobraid: view diverged from a certified digest
ErrEquivocationkolobraid: writer signed two histories
ErrErasedkolobraid: strand entry erased
ErrGroupFullkolobraid: group full
ErrHaltedkolobraid: view halted
ErrInvalidArgumentkolobraid: invalid argument
ErrInvalidConfigkolobraid: invalid group config
ErrKnownStrandkolobraid: strand already known
ErrMalformedkolobraid: malformed encoding
ErrNotAdminkolobraid: not an admin
ErrNotFoundkolobraid: not found
ErrNotMemberkolobraid: not an active member
ErrProtocolkolobraid: protocol violation
ErrRejectedkolobraid: entry rejected
ErrRemovedkolobraid: member removed
ErrReorgedkolobraid: order changed
ErrStrandLostkolobraid: own strand lost
ErrTooLargekolobraid: value too large
ErrTxDonekolobraid: transaction done
ErrUnconfirmedkolobraid: own strand not confirmed
ErrViewLimitkolobraid: view limit exceeded
ErrWrongAppkolobraid: wrong app tag
ErrWrongGroupkolobraid: wrong group
devices.ErrNotAdmittedkolobraid: the group did not take the member
devices.ErrNotProvenkolobraid: device certificate not proven
devices.ErrNotRecordedkolobraid: the roster did not take the record
devices.ErrTooManyDeviceskolobraid: too many devices of this person in the group
devices.ErrUnknownDevicekolobraid: no certificate for this device
devices.ErrUnknownPersonkolobraid: person has no anchored device in the group

Test errors with errors.Is. The library's own error messages start with kolobraid:.

References