kolo docsbeta

kolo-braid

Os strands assinados de vários membros, unidos em uma única ordem determinística que uma função apply escrita por você transforma em uma visão.

Nesta página

Um braid é um conjunto de strands: um log assinado da kolo-log por membro, guardado com a kolo-store. Todo peer que tem as mesmas entradas calcula a mesma ordem, byte a byte, a partir da relação happened-before de Lamport e da regra de commit sobre um DAG por rodadas do DAG-Rider e do Bullshark, e a entrega a uma função apply escrita por você, uma máquina de estados determinística, que constrói uma visão sobre a kolo-store. Os peers sincronizam com ServeConn por conexões diretas e por relay (kolo-secure, kolo-relay ou qualquer peer da kolo-swarm), e um membro novo entra com um pedido de entrada e um welcome que a kolo-invite pode levar. Os pacotes Go são kolobraid, kv (um mapa chave-valor na visão), devices (um registro de certificados de dispositivo, e a admissão dos dispositivos certificados de uma pessoa) e kolobraidtest (verificações para uma função apply).

A ordem tem duas partes. O prefixo assentado nunca muda. A cauda tentativa que vem depois dele é aplicada em memória e ainda pode ser reordenada quando chegam entradas. As leituras escolhem entre as duas: Braid.Settled para a visão assentada sozinha, Braid.View para o assentado mais o tentativo.

Todos os passos

Strands, links, pulsos e lotes

Todo peer que tem as mesmas entradas calcula a mesma ordem, byte a byte, e a entrega à sua função apply.

  1. Cada membro escreve o próprio strand: um log da kolo-log assinado em que cada entrada nomeia a anterior. Aqui A e B são settlers e C é um membro.
  2. Uma entrada aponta para no máximo uma entrada de cada outro strand: a mais nova que quem a escreve tem. Os links unem todos os strands em um só grafo.
  3. Os settlers escrevem pulsos, que assentam a ordem e nunca são aplicados. A e B escrevem cada um um pulso da rodada 0. Em uma rodada par, o pulso do assento pivô dessa rodada é o pivô: aqui, A0.
  4. Um pulso que contém pulsos da rodada r de q assentos é da rodada r + 1. Quando os pulsos da rodada 1 de q assentos contêm o pivô, ele é confirmado. Com dois assentos e Majority, q é 2.
  5. O pivô confirmado assenta, como um lote, tudo o que contém e ainda não está assentado: uma ordem topológica cujos empates são decididos por um hash semeado com o ID do pivô. Posições assentadas nunca mudam.
  6. O resto é a cauda tentativa, ordenada como os lotes em que se prevê que ela seja assentada. Ela é aplicada em memória sobre a visão assentada e pode ser reordenada quando chegam entradas.

Instalação

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

Ela precisa do Go 1.26 ou mais novo e é Go puro. Construa um documento compartilhado em dois terminais mostra passo a passo duas pessoas escrevendo o mesmo documento em 127.0.0.1, a partir do repositório kolo-braid-starter. Passo 7: Combine membros e salas com o kolo-braid guarda em um braid a lista de membros e a lista de salas de um chat de desktop. Compile com CGO_ENABLED=0 para um binário sem código C: o Pebble, usado pela kolo-store, liga uma biblioteca zstd em C quando o cgo está ativo.

Início rápido

Um membro, um braid em um diretório do Pebble dentro do primeiro argumento e uma função apply que guarda cada mensagem e as conta. O segundo Append tem o corpo vazio, e o apply o rejeita. É o examples/apply do repositório. Rode com 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)
	}
}

Ele imprime:

Texto
1 settled message(s)
1 rejected by apply

A entrada rejeitada mantém a sua posição na ordem, com Ordered.Rejected marcado, e as suas escritas são descartadas em todos os peers. Append retorna assim que a entrada é escrita; o laço espera em Next até a entrada ficar assentada e depois lê a visão assentada.

A função apply

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

O apply é chamado uma vez por entrada, na ordem, com uma transação sobre a visão. A biblioteca faz a ordem ser a mesma em todos os peers. Só você pode fazer o apply dar o mesmo resultado a partir da mesma ordem.

O contrato

  • O apply deve ser uma função pura da visão antes de e, do próprio e e do roster na posição de e (Tx.Member, Tx.Members). Ele não vê relógio, nem aleatoriedade, nem a ordem de iteração de um map, nem E/S.
  • Ponto flutuante que chega à visão deve ser arredondado de forma explícita depois de cada operação, por exemplo float64(x * y), e funções de math que não sejam Abs, Copysign, Floor, Ceil, Trunc e Sqrt não devem chegar a ela. Inteiros ou strings decimais são a escolha simples.
  • O apply é chamado para as entradas efetivas dos tipos genesis, data, AddMember, RemoveMember, Settlers e Evidence, e nunca para pulsos, seeds e entradas nulas. Nos tipos de associação a biblioteca já aplicou o efeito, então rejeitar uma descarta só as escritas do próprio apply.
  • Retornar nil confirma as escritas. Reject(reason) as descarta e registra a entrada como rejeitada em todos os peers: é a única falha determinística. Qualquer outro erro, e um panic, para a visão só neste peer: EventHalted e Status.Halted trazem a posição, e o próximo Open tenta de novo.
  • Por entrada, as chaves têm no máximo 32 KiB e os valores 1 MiB, e as escritas têm um orçamento de 16 x MaxBody, em que cada operação custa a sua chave e o seu valor mais 256 bytes. Passado um limite, a chamada retorna ErrViewLimit e a entrada é rejeitada em todos os peers, seja o que for que o apply retorne.
  • Um Tx usado depois que o apply retornou falha com ErrTxDone. O apply roda na sua própria goroutine, então um apply lento atrasa só a aplicação.

Verificar que o apply é puro

Um apply impuro quebra a convergência mesmo com todos os peers tendo a mesma ordem. Duas funções da kolobraidtest rodam o seu apply sobre um histórico cuja ordem final você informa:

  • CheckApply(t, apply, entries) faz o teste falhar quando assentar o histórico entrada por entrada, em lotes e tamanhos de bloco aleatórios, entre reinícios, e depois de uma reorganização tentativa e da sua promoção, não termina sempre com o mesmo digest acumulado e a mesma visão.
  • FindDivergence(apply, entries, replicas, seed) roda réplicas que recebem cada uma as entradas na sua própria ordem de entrega embaralhada, aplicam de forma tentativa o que têm, se reorganizam quando chega uma entrada anterior e assentam por partes. Ela retorna a primeira posição em que o digest acumulado de uma réplica difere do da réplica 0, nil quando todas concordam, ou um erro quando o apply parou.

Este é o exemplo do pacote, que o go test compila e verifica. O segundo apply conta as suas chamadas em uma variável fora da visão, então réplicas que aplicam entradas tentativas um número diferente de vezes discordam na primeira posição:

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

Um resultado limpo cobre só os caminhos e as entradas que você deu, então monte históricos que usem cada tipo de corpo que a sua aplicação escreve. Em execução, cada peer também mantém um digest acumulado das escritas assentadas. Em cada checkpoint, a cada CheckpointEvery posições assentadas, os settlers declaram o seu digest no próximo pulso, e um peer cujo digest difere do que q settlers declararam para com ErrDiverged e um EventDiverged.

Mudar o apply entre versões

Nunca mude o efeito de uma entrada em uma posição que uma versão anterior já aplicou. Comece o comportamento novo em uma posição marcada por uma entrada de dados assentada que a sua aplicação define (ou um campo de versão nos corpos), mantenha o caminho de código antigo antes dela, e faça o código antigo retornar um erro diferente de Reject diante de um marcador que ele não conhece, para que pare até ser atualizado. kolobraidtest.CheckUpgrade(t, old, new, entries, marker) verifica que a versão nova mantém cada posição anterior ao marcador.

Preparar um escritor

Um dispositivo que escreve precisa de uma identidade que ele guarda e de um diretório de armazenamento que ele nunca compartilha. Este programa salva uma identidade da kolo-id em um diretório privado, cria um braid em um diretório do Pebble, escreve, fecha, e depois carrega a identidade e abre o braid de novo. É o examples/writer; rode com 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)
	}
}

Ele imprime:

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

GroupConfig é fixado pela entrada genesis e todos os peers concordam com ele. Options é local: o backend, um prefixo de chave, a função apply, os pins e Limits. Vários braids compartilham um backend com PrefixBackend(db, prefix) ou Options.Prefix, com prefixos dos quais nenhum é prefixo de outro.

Depois de cada Open, o strand próprio não está confirmado, e as chamadas de escrita esperam por ele enquanto o seu contexto permitir:

  • Um braid que nunca teve outro membro e não tem pin é confirmado pelo próprio armazenamento na hora, como aqui.
  • Um membro que não é settler é confirmado na hora por um head consistente do seu strand, vindo de um membro ou de um pin, que seja tão longo quanto o strand. Um head mais curto o confirma só depois que ConfirmWait passou desde o Open, então um dispositivo tão atrasado quanto um backup restaurado não consegue se confirmar antes que um membro com um head mais longo o tenha mostrado.
  • Um settler precisa desses heads de cada um dos outros settlers que respondem dentro de ConfirmWait, e de pelo menos q - 1 deles.
  • Um head consistente mais longo quer dizer que o dispositivo está atrasado: as chamadas de escrita esperam até ele se atualizar a partir de uma cópia completa. Um head em conflito faz perder o strand: as escritas falham com ErrStrandLost.

Nunca copie o diretório de dados de um membro nem rode uma cópia dele: duas cópias rodando confirmam as duas e escrevem as duas antes que uma veja a outra. Options.AppendUnconfirmed escreve na hora, com esse risco.

Uma entrada de um braid nunca pode ser apagada. Cada peer guarda cada entrada e a sua chave, então dados que podem precisar ser apagados ficam fora do braid. O histórico nunca é podado, e cada entrada custa cerca de 600 bytes de disco em cada peer.

Adicionar um escritor com a kolo-invite

Um membro novo cria o seu strand com NewJoin e envia Joining.Request a um admin. O Admit do admin acrescenta uma entrada AddMember e retorna o welcome, e o Complete de quem entra transforma o welcome no seu braid. A kolo-invite leva os dois: o pedido de entrada como dados de entrada e o welcome como payload selado para quem entra. A kolo-braid só troca bytes e não importa a kolo-invite.

Este programa roda tudo em 127.0.0.1: um servidor da kolo-dht no mesmo processo, o admin com um braid, um convite manual e um swarm da kolo-swarm, e quem entra, que encontra o anfitrião no topic do convite, envia o seu pedido, sai do topic do convite, conclui a entrada e sincroniza no topic do próprio braid. É o examples/addwriter; rode com 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)
	}
}

Ele imprime:

Texto
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

Crie os convites com Manual: true: um convite que aceita sozinho envia um payload fixo, e cada pessoa que entra precisa do seu próprio welcome. Uma conexão é atendida por ServeConn quando o peer compartilha o topic do braid, e pelo ServePeer do anfitrião nos outros casos; cada um deve ser o único que aceita streams na sua conexão.

CasoAdminQuem entra
AdmitidoAdmit acrescenta AddMember (e, com GrowSettlers, uma entrada Settlers quando é a vez); Approve envia o welcomeo welcome; Complete
Uma escrita falha depois da entrada AddMemberesse erro; deny e RemoveMemberinvite.ErrDenied
Já é um membro ativoErrActiveKey; denyinvite.ErrDenied
Strand usado antes ou conhecidoErrKnownStrand; denyinvite.ErrDenied
Strand do pedido assinado por outra chaveErrInvalidArgument; denyinvite.ErrDenied
O admin não é admin, ou tem a própria remoçãoErrNotAdmin, ErrRemoved; denyinvite.ErrDenied
O convite expirou, foi revogado ou esgotado antes do ApproveApprove retorna invite.ErrExpired, ErrRevoked ou ErrUsedUp; RemoveMembero mesmo erro, sem welcome
Pedir de novo depois de um aceitenenhum evento, nada acrescentadoo mesmo welcome

Sem opções, Admit admite um membro simples: ele escreve, mas não é admin nem settler, e nenhuma entrada Settlers é escrita. AdmitOptions.Roles define os papéis. AdmitOptions.GrowSettlers faz o braid crescer até MinSettlers assentos e MinSettlers - 1 admins: os primeiros que entram viram admins, que podem adicionar e remover qualquer um, e settlers, e uma entrada Settlers é acrescentada quando é a vez; use só com quem você confia a esse ponto. Roles junto com GrowSettlers é ErrInvalidArgument. As chamadas de Admit rodam uma de cada vez, então quem é admitido ao mesmo tempo com GrowSettlers conta cada um as entradas do anterior. AdmitOptions.Replace deixa o dispositivo novo de um membro assumir com um strand novo e manter os seus papéis.

Braid.CheckAdmit(joiner, request) informa, sem escrever nada, o que Admit recusaria agora (ErrNotAdmin, ErrRemoved ou ErrNotMember para este peer, ErrActiveKey, ErrKnownStrand), e ErrGroupFull quando o grupo já tem MaxMembers membros ativos, que Admit não retorna: ele acrescenta uma entrada AddMember que o roster depois deixa sem efeito. WelcomeEntry(welcome) devolve a entrada AddMember que um welcome nomeia, e Braid.PublicKey a chave com que este peer roda o braid. O pacote devices mais abaixo usa as três.

O braid que Complete retorna começa assim que um membro lhe serve a entrada genesis do strand fundador. As suas chamadas de escrita esperam até ele ter essa entrada e a sua própria entrada AddMember estar na ordem, então o primeiro Append não precisa esperar por conta própria; um ErrNotMember depois disso quer dizer que a ordem deixou a entrada AddMember nula. Uma entrada sobrevive a um reinício de quem entra: NewJoin no mesmo prefixo com a mesma identidade retorna a entrada pendente, com o mesmo strand e o mesmo pedido.

Remover um escritor

RemoveMember, chamado por um admin, remove um membro na posição da sua entrada, como qualquer mudança de associação. Este programa admite B, deixa B escrever, remove B, mostra o que cada lado mantém e admite B de novo com um strand novo. É o examples/removewriter; rode com 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)
	}
}

Ele imprime:

Texto
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
  • As entradas de associação são verificadas na sua própria posição da ordem, nunca contra o roster do momento em que chegam, então todos os peers as decidem do mesmo jeito. Sempre sobram pelo menos uma chave de admin e uma de settler.
  • As entradas de um strand removido ordenadas antes da remoção mantêm o seu efeito; as ordenadas depois são nulas em todo lugar. As remoções vão primeiro entre as entradas que ficam prontas juntas, então uma entrada concorrente só é mantida se foi ordenada antes de a remoção ficar pronta.
  • Um membro removido mantém tudo o que recebeu. A kolo-braid não pode tomar de volta dados que um dispositivo já tem.
  • Pela rede, um membro removido tem o acesso recusado, não necessariamente é avisado. Os peers que têm a remoção param de apontar para o seu strand e de servi-lo a partir do seu próximo pedido, e fecham a sua conexão quando a sua chave fica desconhecida por 60 s. Ele recebe EventRemoved só quando tem a remoção assentada, e isso só um peer que ainda não tinha a remoção pode lhe dar; senão ele simplesmente não recebe mais nada.
  • Um settler removido é a exceção até que uma configuração de settlers sem ele seja ativada: os seus pulsos continuam contando, então ele continua escrevendo pulsos e os peers continuam a servi-lo.
  • Um membro removido que é convidado de novo entra com um strand novo (NewJoin em um prefixo novo): o seu strand antigo fica usado, e Admit o recusa com ErrKnownStrand.

Dois peers sincronizando

Dois membros em uma mesma máquina, cada um com um diretório do Pebble dentro do primeiro argumento, sincronizados por uma conexão da kolo-secure em 127.0.0.1. A cria o braid e admite B, os dois acrescentam uma mensagem e cada um assenta as duas na mesma ordem. É o examples/twopeers e o início rápido do README; rode com 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)
	}
}

Ele imprime:

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

Em uma aplicação, entre no topic da kolo-swarm do braid (Braid.Topic) e atenda cada peer conectado com ServeConn:

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

O que passa por uma conexão:

  • Os strands, pela kolo-sync, um pull por strand de cada vez e no máximo 16 ao mesmo tempo. O strand de um membro é buscado até o seu tamanho assentado mais MaxPullAhead, o de um settler até MaxPullAhead depois do seu pulso mais novo que se tem, e cada strand até o que uma entrada que se tem aponta.
  • Os heads (ANNOUNCE): todos os heads na primeira mensagem, depois só os que mudaram, no máximo uma mensagem por AnnounceGap.
  • Segundos históricos e provas: uma entrada que um link nomeia, mas em cujo lugar este peer tem outra, é buscada com o head assinado de quem a escreveu e verificada entrada por entrada; dois registros de um mesmo índice assinados por quem escreve são uma prova, que cada peer envia uma vez por conexão.
  • Depois do Open, o head do strand próprio em cada peer, que confirma o strand próprio ou o deixa se atualizar.

O acesso segue o roster tentativo: os membros ativos e os settlers da configuração atual e da pendente recebem as chaves das entradas, os pins só texto cifrado, e qualquer outro nada. ServeConn pega os dois tipos de stream da conexão, então uma conexão que o ServePeer da kolo-invite usa não pode também servir o braid. Ela retorna nil quando o seu contexto ou a conexão termina, ErrClosed quando o braid fecha, e um erro que envolve ErrProtocol depois de fechar a conexão de um peer que quebrou o protocolo.

Conexões diretas e por relay

ServeConn recebe um Conn: uma conexão autenticada com um peer, direta ou por relay, como um *kolosecure.Conn, um *kolorelay.Conn ou um koloswarm.Conn. Um Conn nil, ou um que guarda um ponteiro nil, é ErrInvalidArgument. O ServeConn confia por completo em RemotePublicKey, então passe só conexões cuja chave foi provada em um handshake, como um *kolosecure.Conn: RemotePublicKey precisa retornar a chave que o peer provou no handshake de ponta a ponta. Um link por relay prova a chave do mesmo jeito, então as verificações de membros e pins são as mesmas de uma conexão direta. Um relay copia bytes que não consegue ler; o que ele ainda fica sabendo está na página da kolo-relay.

Assentamento

Settlers e a regra de quórum

Os settlers são os membros cujos pulsos assentam a ordem. Uma configuração nomeia as suas chaves e a regra de quórum, e q dos seus n assentos precisam conter um pivô para ele ser confirmado. O assentamento continua enquanto q settlers da configuração atual estão online.

Assentosq com MajoritySettlers que podem assinar dois históricos sem dividir prefixosq com TwoThirds
1101
2212
3203
4313
5304
7405

Majority, o padrão, precisa de floor(n/2) + 1 assentos e é para falhas por queda. TwoThirds precisa de floor(2n/3) + 1 e é para braids em que um dispositivo settler pode ser comprometido. Com qualquer uma das duas regras, os prefixos assentados nunca entram em conflito enquanto no máximo f assentos assinam dois históricos, em que f é o maior valor com 2q - n > f. Um settler da configuração atual que assina dois históricos para o assentamento de vez em cada peer que vê os dois (EventSettlementHalted com a sua chave); a aplicação tentativa e as entradas novas continuam. Um escritor que não é settler e assina dois históricos é isolado: uma entrada Evidence deixa o seu strand inativo a partir dessa posição, e o assentamento continua.

Uma entrada Settlers (SetSettlers) muda a configuração. Uma mudança que acrescenta assentos é ativada em um pivô confirmado cujo passado contém um pulso de prontidão de cada assento acrescentado; uma mudança que só remove assentos é ativada na hora.

Crescer até quatro settlers

MinSettlers é 4: Admit com AdmitOptions.GrowSettlers transforma em admins e settlers os primeiros que entram até o braid ter quatro assentos; um Admit simples não faz isso. Com Majority, 4 settlers dão q = 3: um pode estar offline e um pode assinar dois históricos sem dividir os prefixos assentados. 3 ou 5 settlers não dão essa margem, e com eles um dispositivo settler mal restaurado ou clonado pode dividir o braid. Um braid com um único settler depende desse dispositivo: Status.SingleSettler indica isso.

Settlers offline

O assentamento para enquanto há menos de q settlers online e continua quando voltam settlers suficientes; nesse meio-tempo as entradas novas ficam na cauda tentativa. Um settler que reinicia volta a escrever quando os outros settlers que respondem dentro de ConfirmWait confirmam o seu strand. A ordem entre entradas concorrentes é decidida por um hash semeado com o pivô, que o settler do pivô pode tentar escolher: ela não é justa, e uma regra de "o primeiro ganha" não deve depender dela.

Tempos medidos

Estes números vêm de uma execução dos cenários de teste em um Mac com Apple M5 (darwin/arm64, Go 1.27.3), um processo por peer em 127.0.0.1, enquanto a máquina estava ocupada com outros trabalhos. Os peers usaram ajustes curtos: PulseGap 50 ms, PivotWait 500 ms, AnnounceGap 20 ms e ConfirmWait 2 s, enquanto os padrões são 500 ms, 3 s, 100 ms e 10 s. Um tempo vai do fim da ação (a última escrita que retornou, uma reconexão, um reinício) até a primeira consulta, a cada 20 a 250 ms, em que todos os peers concordavam. Nada foi medido com os ajustes padrão, em outro hardware ou por uma rede real.

CenárioTempo
3 peers (3 settlers) escrevem 25 entradas cada, tudo assentado280 ms
4 peers (4 settlers) escrevem 25 entradas cada, tudo assentado513 ms
5 peers (4 settlers) escrevem 25 entradas cada, tudo assentado687 ms
5 peers divididos em 3 e 2: o lado com três dos quatro settlers assenta 90 entradas678 ms
os mesmos peers concordam quando a divisão termina398 ms
3 settlers, 2 parados, 10 entradas ficam tentativas; um settler reinicia2,43 s, dos quais 2 s são o seu ConfirmWait
3 peers escreveram 10.002 entradas em 83,6 s (cada Append é durável): tudo assentado depois da última escrita898 ms
um membro que entra depois assenta esse mesmo prefixo depois de se ligar aos peers1,392 s
chamada de Admitde 6 a 19 ms
do Admit ao fim do Completede 13 a 42 ms

Braids sucessores

Quando o quórum de settlers se perde de vez, um admin do roster assentado antigo chama Succeed. A entrada genesis do braid novo nomeia o grupo antigo, a sua posição assentada p e o digest de conteúdo da visão assentada em p; as entradas seed copiam essa visão, cada peer verifica o digest (ErrBadSeed se não bate) e as posições continuam em p + 1. As entradas tentativas do braid antigo não passam. Quem entra e nunca foi membro confia no fundador do sucessor para a visão semeada. Um membro que ainda tem o braid antigo o passa como Options.Predecessor, e o seu braid para a menos que o fundador tenha sido admin do antigo e a visão semeada seja a visão assentada antiga.

O helper kv

O pacote github.com/ciranda-dev/kolo-braid/kv mantém um mapa chave-valor na visão. Puts e deletes são entradas de dados, e a última operação efetiva sobre uma chave na ordem do braid ganha, igual em todos os peers, sem relógio. Escritas concorrentes são decididas pela ordem, que não é justa, então regras de "a primeira escrita ganha" não devem depender dela. O mapa não tem controle de acesso: qualquer membro ativo pode pôr ou apagar qualquer chave. Quando as chaves pertencem a membros, verifique Entry.Writer (e Tx.Member para os papéis dele) na função apply antes de 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): os pares vivem na visão sob o prefixo e a chave, e nenhuma outra chave da aplicação pode começar com o prefixo.
  • Apply trata as entradas de dados cujo corpo começa com a tag kv e retorna false para qualquer outra entrada, então uma aplicação encaminha as suas próprias entradas ao lado dele. Um corpo kv que não decodifica, ou cuja chave não cabe com o prefixo, é rejeitado com Reject, igual em todos os peers.
  • Put e Delete acrescentam uma entrada cada, que vale a partir da sua posição. As chaves têm no máximo 32 KiB com o prefixo e os valores 1 MiB (kolobraid.ErrTooLarge), e o corpo inteiro no máximo o MaxBody do braid.
  • Get e Range leem um snapshot: Braid.Settled para o que não muda mais, Braid.View para o assentado mais o tentativo, que uma reorganização pode mudar. Range(start, end) entrega as chaves em [start, end); um end vazio não tem limite superior.

Os testes do pacote o passam por kolobraidtest.CheckApply e FindDivergence.

Dispositivos de uma pessoa

O pacote github.com/ciranda-dev/kolo-braid/devices guarda na visão os certificados de dispositivo e as revogações da kolo-id das pessoas de um grupo, e deixa um admin admitir um dispositivo certificado de uma pessoa que já pertence ao grupo sem uma nova decisão. Uma chave de pessoa, tirada das 24 palavras, certifica dispositivos aprovadores, os aprovadores certificam dispositivos comuns, e uma chave de dispositivo assina as mensagens. Cada chave de dispositivo é um membro comum com o seu próprio strand. O pacote não muda nada na ordem, no assentamento, nas regras de associação nem nos formatos do braid, Braid.Admit não muda, e um grupo que não o importa se comporta como antes. Um dispositivo recebe o seu certificado com um convite da kolo-invite para vincular um dispositivo.

Este programa é o examples/devices; rode-o com go run . "$(mktemp -d)". Um notebook funda um grupo e ancora o seu certificado de aprovador, certifica um celular, o admite sem uma nova decisão e depois o revoga.

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)
		}
	}
}

Ele imprime isto:

Texto
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

Registros e âncoras

  • Os registros são entradas de dados cujo corpo começa com kolo-braid/devices/v0. Qualquer membro pode escrever um, porque um certificado ou uma revogação é a sua própria prova. Apply rejeita, igual em todos os peers, um corpo que não decodifica, um certificado ou uma revogação que não se verifica, um certificado cujo número de série não é maior que o guardado, um certificado emitido por um aprovador já aposentado e um registro que passa de um limite. Ele verifica a estrutura e as assinaturas sem relógio: a expiração, a revogação e o momento da verificação ficam com quem lê.
  • Qualquer membro pode inventar uma chave de pessoa e um certificado para ela, então uma pessoa só conta para a admissão quando um admin registrou um certificado dela. Esse certificado fica ancorado. Store.Record é a chamada do admin para o primeiro dispositivo de uma pessoa, depois de o admin decidir com Braid.Admit deixar esse dispositivo entrar, e Store.Admit ancora os certificados que admite.
  • A visão guarda um certificado por pessoa e dispositivo, o de número de série mais alto. A revogação de um aprovador leva na entrada o certificado que ela atinge, então pode ser verificada sozinha e em qualquer ordem.
  • Cert, Anchored, Devices e Revocations leem um snapshot. Verify(snap, person, device, now, context, msg, sig) roda koloid.VerifyDevice sobre o certificado guardado com as revogações guardadas, para a pessoa que você passa: fixe a pessoa no seu próprio estado, nunca a leia de um certificado. ErrUnknownDevice quer dizer que o registro não tem nenhum certificado para o dispositivo.
  • Os aprovadores se aposentam pela posição na ordem do braid, que é a mesma em todos os peers, não por um relógio. Uma revogação assinada por um aprovador não é usada quando a sua posição vem depois da primeira revogação desse aprovador pela chave de pessoa ou pelo próprio aprovador, e um certificado emitido por um aprovador aposentado é rejeitado. Um aprovador aposentado continua aposentado mesmo que a sua chave seja certificada de novo: use uma chave nova.

Admitir um dispositivo

O dispositivo novo monta o seu pedido de entrada com devices.NewJoinRequest(join, id, cert, group, appData), que acrescenta uma prova de que ele tem a chave certificada: uma assinatura sobre a pessoa, o grupo e o strand do próprio pedido com kolo-braid/device-admit/v0. Um admin chama roster.Admit(ctx, b, joinerKey, request) em vez de Braid.Admit. Antes de escrever qualquer coisa, ele verifica nesta ordem:

  1. o pedido leva uma prova e o seu certificado é para a chave de quem entra (ErrNotProven);
  2. o que Braid.Admit recusaria agora, e um grupo cheio, com Braid.CheckAdmit (kolobraid.ErrNotAdmin, ErrActiveKey, ErrKnownStrand, kolobraid.ErrGroupFull e os outros);
  3. a pessoa tem no grupo um membro ativo assentado cujo certificado ancorado se verifica agora (ErrUnknownPerson);
  4. o certificado não é mais antigo que o do registro, e koloid.VerifyDevice o aceita em Options.Now com as revogações do registro (ErrNotProven, que também corresponde a erros da kolo-id como koloid.ErrCertExpired e koloid.ErrCertRevoked);
  5. quando Options.MaxDevices está definido, a pessoa tem menos vagas que isso (ErrTooManyDevices).

Depois ele acrescenta o certificado, ancorado, e espera até o registro tê-lo (ErrNotRecorded quando ele foi assentado sem efeito). Ele chama Braid.Admit com um papel comum, nem admin nem settler, e espera até a visão mostrar o membro novo (ErrNotAdmitted quando a entrada AddMember foi assentada sem ele). Cada espera termina com o contexto de quem chama. Nada é concedido quando um passo anterior a Braid.Admit falhou. Um grupo cuja política é que a pessoa aprove cada dispositivo nunca chama roster.Admit.

Todos os peers de um grupo precisam usar a mesma versão da kolo-id, porque o apply verifica as assinaturas com ela. Ponha a versão da kolo-id na string App do grupo, por exemplo chat/v1+id0.1.0, e mude-a junto com a versão.

Limites dos dispositivos

Por padrão não há limite de dispositivos por pessoa. Cada dispositivo ocupa uma vaga do grupo (MaxMembers, 64 por padrão), e essas vagas são o único limite; a âncora é o que impede uma pessoa inventada de ocupar vagas. Um dispositivo revogado mantém a sua vaga até um admin removê-lo com RemoveMember.

devices.OptionsPadrãoFaixaPor quê
MaxCertsPerPerson1024de 1 a 2^20os certificados de uma pessoa em uma visão; o seguinte é rejeitado
PersonCertReserveum oitavo do limite, 128de 0 a MaxCertsPerPerson, -1 para nenhumaespaços reservados para certificados emitidos pela chave de pessoa, para que um aprovador roubado não consiga encher o registro
MaxRevocationsPerDevice64de 1 a 2^16revogações de aprovador de uma chave de dispositivo
MaxDevicesnenhumqualquer valor positivoum teto opcional das vagas de uma pessoa que Admit deixa entrar (ErrTooManyDevices)

Os três primeiros decidem quais entradas o apply rejeita, então todos os peers de um grupo precisam usar os mesmos valores. MaxDevices é um ajuste do peer que admite: dois admins que admitem no mesmo momento contam cada um a partir da própria visão, então juntos podem passar dele por um cada. Um certificado tem no máximo 514 bytes e uma revogação 472 bytes, as codificações da kolo-id, e uma prova tem menos de 700 bytes dentro do limite de 64 KiB de um pedido de entrada. Uma pessoa que perde todos os dispositivos e restaura as 24 palavras recupera a chave de pessoa, mas não uma vaga: um admin admite o dispositivo novo com Braid.Admit e registra o seu certificado.

Formatos

Todo hash é BLAKE2b-256 sobre uma codificação da kolo-codec que começa com a sua própria tag: kolo-braid/entry-id/v0 (IDs de entrada; o ID do grupo é o ID da entrada genesis), kolo-braid/order/v0 (chaves de desempate), kolo-braid/config/v0 (IDs de configuração), kolo-braid/digest/v0 (digest acumulado), kolo-braid/content/v0 (digest de conteúdo) e kolo-braid/topic/v0 (o topic da kolo-swarm, Braid.Topic). As entradas começam com kolo-braid/entry/v0, o pedido de entrada com kolo-braid/join/v0, o welcome com kolo-braid/welcome/v0 e o corpo do helper kv com kolo-braid/kv/v0. A kolo-braid não acrescenta assinatura própria: a kolo-log assina cada entrada.

TipoCorpo
0 genesistag do app, regra de quórum, MaxMembers, MaxSettlers, MinSettlers, MaxBody, CheckpointEvery e, para um sucessor, o grupo antigo, a posição, o digest de conteúdo e o número de seeds
1 databytes da aplicação, no máximo MaxBody
2 add memberchave, ID do log do strand, papéis, cabeçalho de log assinado
3 remove memberchave
4 settlersregra de quórum e chaves, em ordem estritamente crescente
5 evidencechave, ID do log do strand, dois registros ou heads assinados da kolo-log
6 pulseconfiguração, pivô de ativação, declaração de digest opcional, prontidão opcional
7 seedpares da visão de um braid sucessor

O corpo kv é, em kolo-codec, a string kolo-braid/kv/v0, um uvarint de operação (1 put, 2 delete) e depois a chave e o valor como bytes, com o valor vazio para um delete.

Um corpo de devices é, em kolo-codec, a string kolo-braid/devices/v0, um uvarint de operação (1 certificado, 2 revogação) e o objeto como bytes, e depois, só em uma revogação, um bool e o certificado atingido como bytes. A prova nos dados de um pedido de entrada é a string kolo-braid/devices/proof/v0, o certificado como bytes, a assinatura de 64 bytes e os dados da aplicação como bytes.

Referência da API

A referência da API é gerada a partir do código Go e está em inglês.

Pacote 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.

Constantes

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
)

Variáveis

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")
)

Funções

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.

Tipos

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.

Pacote 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.

Constantes

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
)

Tipos

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.

Pacote 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.

Constantes

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

Variáveis

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")
)

Funções

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.

Tipos

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.

Pacote 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.

Funções

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.

Tipos

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.

Bom saber

Padrões

Fixados pela entrada genesis (GroupConfig); um campo zerado recebe o padrão e um valor fora da sua faixa retorna ErrInvalidConfig:

CampoPadrãoPor quê
QuorumMajority, ou TwoThirdsfalhas por queda; TwoThirds quando um dispositivo settler pode ser comprometido
MaxMembers64, faixa de 2 a 1024o orçamento de peers padrão de um nó
MaxSettlers7 ou MaxMembers se for menor, faixa de 1 a 64com Majority, tolera então 3 offline
MinSettlers4 ou MaxSettlers se for menor, faixa de 1 a MaxSettlerstolera um settler offline e um que assina dois históricos
MaxBody1 MiB, faixa de 1 KiB a 3 MiBo limite de valor da visão
CheckpointEvery1024 posições assentadas, faixa de 64 a 2^20uma divergência é detectada dentro dessas posições

Locais a um peer (Limits); um valor fora da sua faixa retorna ErrInvalidArgument:

CampoPadrão
MaxTail2048: uma reorganização reaplica no máximo essas entradas
MaxPendingBytes16 MiB de entradas que esperam por uma anterior; um strand guarda no máximo MaxPendingBytes / MaxMembers delas (uma entrada sempre cabe)
MaxForks4, faixa de 1 a 64: os segundos históricos de um strand que um peer guarda; as entradas do próximo são recusadas e deixam de ser buscadas
MaxPullAheadMaxTail
PulseGap500 ms
PivotWait3 s
AnnounceGap100 ms
ConfirmWait10 s
MaxEvents1024

Segurança

  • A kolo-log assina e cifra cada entrada; a kolo-braid não acrescenta assinatura própria. Cada head, registro, prova e entrada de um peer é verificado, e uma mensagem malformada, acima do seu limite, de outro grupo, versão ou tipo, com bytes sobrando ou que não verifica fecha a conexão, assim como um pedido sem resposta em 60 s.
  • A associação é verificada na posição de cada entrada na ordem, então todos os peers a decidem do mesmo jeito. Um strand é seguido sob a chave da entrada AddMember que a ordem torna efetiva, nunca sob a chave de uma nula.
  • Uma prova só conta quando a chave que assinou os dois objetos é a chave do strand que eles nomeiam.
  • Uma chave que não é de um membro, de um settler nem de um pin não recebe nada da kolo-sync, das suas mensagens só os ANNOUNCE são lidos além do prefixo, e a sua conexão é fechada quando ela fica desconhecida por 60 s.
  • O ServeConn confia em Conn.RemotePublicKey: passe só conexões cuja chave foi provada em um handshake, como um *kolosecure.Conn.
  • O mapa do kv não tem controle de acesso: qualquer membro ativo escreve qualquer chave.
  • Uma pessoa só conta para roster.Admit depois que um admin registrou um certificado dela, então um membro simples não consegue inventar uma. A partir daí, roster.Admit deixa entrar cada dispositivo seguinte que prove um certificado válido, sem limite de taxa: as vagas do grupo e MaxCertsPerPerson são os únicos limites. Os certificados emitidos por aprovadores não conseguem encher o registro, porque PersonCertReserve reserva 128 dos 1024 espaços para a chave de pessoa.
  • devices.Store.Verify verifica um dispositivo para a pessoa que você passa. Fixe a pessoa no seu próprio estado, nunca a tire de um certificado.
  • Duas cópias rodando de um mesmo diretório de dados escrevem as duas antes que uma veja a outra: em um settler isso para o assentamento, e com 3 ou 5 settlers e Majority pode dividir os prefixos assentados.

Status

Beta e experimental, como toda biblioteca da Kolo em v0.x: a API pode mudar antes da v1.0.0.

  • Feito: os strands, a ordem com o seu prefixo assentado e a sua cauda tentativa, o contrato do apply e as suas verificações, a associação e a admissão, o assentamento com configurações e braids sucessores, a sincronização por conexões diretas e por relay, o helper kv e o pacote devices.
  • Testado: testes unitários, de propriedades e fuzz, verificação de modelos do assentamento e da associação em escopos limitados (scripts/modelcheck.sh), que só cobrem os tamanhos que percorrem e não são uma prova para qualquer tamanho, e cenários com vários processos em um Mac, só em 127.0.0.1. As compilações para Linux e Windows passaram pelo vet, não foram executadas.
  • O assentamento guarda uma marca de rodada por settler e por rodada da configuração de settlers atual, até a configuração mudar: 16 bytes na memória e uma chave de uns 40 bytes no disco, escrita uma vez. Um braid que assenta o dia todo com 4 settlers e o PulseGap padrão pode somar até cerca de 1,4 milhão por dia, uns 22 MB de memória e 55 MB de disco; com 64 settlers, 16 vezes isso, e mais com um PulseGap menor (até 50 vezes com 10 ms). São limites superiores; o crescimento dos slices soma até um quarto ao número de memória. Elas são o que permite que um pulso que chega tarde receba a sua rodada exata, e uma mudança da configuração de settlers as remove.

Erros

ErroMensagem
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

Teste os erros com errors.Is. As mensagens de erro próprias da biblioteca começam com kolobraid:.

Referências