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.
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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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-braidEla 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)".
// 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:
1 settled message(s)
1 rejected by applyA 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
type ApplyFunc func(tx *Tx, e *Entry) errorO 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óprioee do roster na posição dee(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 demathque não sejamAbs,Copysign,Floor,Ceil,TrunceSqrtnã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:EventHaltedeStatus.Haltedtrazem a posição, e o próximoOpententa 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 retornaErrViewLimite a entrada é rejeitada em todos os peers, seja o que for que o apply retorne. - Um
Txusado depois que o apply retornou falha comErrTxDone. 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:
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 1Um 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)".
// 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:
created the braid and wrote 1 message
reopened the braid, own strand unconfirmed: false
messages in the settled view: first, secondGroupConfig é 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
ConfirmWaitpassou desde oOpen, 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)".
// 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:
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: trueCrie 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.
| Caso | Admin | Quem entra |
|---|---|---|
| Admitido | Admit acrescenta AddMember (e, com GrowSettlers, uma entrada Settlers quando é a vez); Approve envia o welcome | o welcome; Complete |
| Uma escrita falha depois da entrada AddMember | esse erro; deny e RemoveMember | invite.ErrDenied |
| Já é um membro ativo | ErrActiveKey; deny | invite.ErrDenied |
| Strand usado antes ou conhecido | ErrKnownStrand; deny | invite.ErrDenied |
| Strand do pedido assinado por outra chave | ErrInvalidArgument; deny | invite.ErrDenied |
| O admin não é admin, ou tem a própria remoção | ErrNotAdmin, ErrRemoved; deny | invite.ErrDenied |
O convite expirou, foi revogado ou esgotado antes do Approve | Approve retorna invite.ErrExpired, ErrRevoked ou ErrUsedUp; RemoveMember | o mesmo erro, sem welcome |
| Pedir de novo depois de um aceite | nenhum evento, nada acrescentado | o 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)".
// 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:
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
EventRemovedsó 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 (
NewJoinem um prefixo novo): o seu strand antigo fica usado, eAdmito recusa comErrKnownStrand.
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)".
// 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:
A settled 2 messages
B settled 2 messages
same order: trueEm uma aplicação, entre no topic da kolo-swarm do braid (Braid.Topic) e atenda cada peer conectado com ServeConn:
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éMaxPullAheaddepois 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.
| Assentos | q com Majority | Settlers que podem assinar dois históricos sem dividir prefixos | q com TwoThirds |
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| 2 | 2 | 1 | 2 |
| 3 | 2 | 0 | 3 |
| 4 | 3 | 1 | 3 |
| 5 | 3 | 0 | 4 |
| 7 | 4 | 0 | 5 |
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ário | Tempo |
|---|---|
| 3 peers (3 settlers) escrevem 25 entradas cada, tudo assentado | 280 ms |
| 4 peers (4 settlers) escrevem 25 entradas cada, tudo assentado | 513 ms |
| 5 peers (4 settlers) escrevem 25 entradas cada, tudo assentado | 687 ms |
| 5 peers divididos em 3 e 2: o lado com três dos quatro settlers assenta 90 entradas | 678 ms |
| os mesmos peers concordam quando a divisão termina | 398 ms |
| 3 settlers, 2 parados, 10 entradas ficam tentativas; um settler reinicia | 2,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 escrita | 898 ms |
| um membro que entra depois assenta esse mesmo prefixo depois de se ligar aos peers | 1,392 s |
chamada de Admit | de 6 a 19 ms |
do Admit ao fim do Complete | de 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.
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.Applytrata 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 comReject, igual em todos os peers.PuteDeleteacrescentam 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 oMaxBodydo braid.GeteRangeleem um snapshot:Braid.Settledpara o que não muda mais,Braid.Viewpara 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.
// 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:
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: falseRegistros 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.Applyrejeita, 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 comBraid.Admitdeixar esse dispositivo entrar, eStore.Admitancora 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,DeviceseRevocationsleem um snapshot.Verify(snap, person, device, now, context, msg, sig)rodakoloid.VerifyDevicesobre 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.ErrUnknownDevicequer 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:
- o pedido leva uma prova e o seu certificado é para a chave de quem entra (
ErrNotProven); - o que
Braid.Admitrecusaria agora, e um grupo cheio, comBraid.CheckAdmit(kolobraid.ErrNotAdmin,ErrActiveKey,ErrKnownStrand,kolobraid.ErrGroupFulle os outros); - a pessoa tem no grupo um membro ativo assentado cujo certificado ancorado se verifica agora (
ErrUnknownPerson); - o certificado não é mais antigo que o do registro, e
koloid.VerifyDeviceo aceita emOptions.Nowcom as revogações do registro (ErrNotProven, que também corresponde a erros da kolo-id comokoloid.ErrCertExpiredekoloid.ErrCertRevoked); - quando
Options.MaxDevicesestá 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.Options | Padrão | Faixa | Por quê |
|---|---|---|---|
MaxCertsPerPerson | 1024 | de 1 a 2^20 | os certificados de uma pessoa em uma visão; o seguinte é rejeitado |
PersonCertReserve | um oitavo do limite, 128 | de 0 a MaxCertsPerPerson, -1 para nenhuma | espaços reservados para certificados emitidos pela chave de pessoa, para que um aprovador roubado não consiga encher o registro |
MaxRevocationsPerDevice | 64 | de 1 a 2^16 | revogações de aprovador de uma chave de dispositivo |
MaxDevices | nenhum | qualquer valor positivo | um 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.
| Tipo | Corpo |
|---|---|
| 0 genesis | tag 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 data | bytes da aplicação, no máximo MaxBody |
| 2 add member | chave, ID do log do strand, papéis, cabeçalho de log assinado |
| 3 remove member | chave |
| 4 settlers | regra de quórum e chaves, em ordem estritamente crescente |
| 5 evidence | chave, ID do log do strand, dois registros ou heads assinados da kolo-log |
| 6 pulse | configuração, pivô de ativação, declaração de digest opcional, prontidão opcional |
| 7 seed | pares 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.
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.BackendPrefixBackend 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) errorReject 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) errorApplyFunc 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) errorCheckAdmit 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() errorClose 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() GroupIDGroupID 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.PublicKeyPublicKey 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) errorServeConn 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() *SnapshotSettled 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() StatusStatus returns the braid's state.
func (Braid) Topic
func (b *Braid) Topic() [32]byteTopic returns the kolo-swarm topic of the braid.
func (Braid) View
func (b *Braid) View() *SnapshotView 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]byteDigest is a running digest, a content digest or a claim.
func (Digest) String
func (d Digest) String() stringString 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]byteEntryID names one strand entry: the BLAKE2b-256 hash of its signed kolo-log record.
func (EntryID) String
func (id EntryID) String() stringString 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 intEventKind 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() errorValidate returns an error wrapping ErrInvalidConfig unless every field is inside its range.
func (GroupConfig) WithDefaults
func (c GroupConfig) WithDefaults() GroupConfigWithDefaults returns c with every zero field except App set to its default.
type GroupID
type GroupID [32]byteGroupID is the entry ID of the genesis entry.
func (GroupID) String
func (id GroupID) String() stringString 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 uint8Kind 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 Link
type Link struct {
Strand kololog.LogID
Index uint64
ID EntryID
}Link names one entry of another strand in the causal past of the entry that holds it.
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() KindKind 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 uint8QuorumRule 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 uint8Role is a bit set of the rights of a member.
const RoleAdmin Role = 1RoleAdmin 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() errorClose 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() errorErr 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() []MemberMembers returns the roster of the snapshot.
func (Snapshot) Position
func (s *Snapshot) Position() uint64Position 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() SettlersSettlers 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) errorDelete 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) errorDeleteRange 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() []MemberMembers returns the roster at the position of this entry.
func (Tx) Put
func (tx *Tx) Put(key, value []byte) errorPut 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
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) *StoreNew 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) errorDelete 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) errorPut 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
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) errorRecord 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) errorVerify 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
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() stringString 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:
| Campo | Padrão | Por quê |
|---|---|---|
Quorum | Majority, ou TwoThirds | falhas por queda; TwoThirds quando um dispositivo settler pode ser comprometido |
MaxMembers | 64, faixa de 2 a 1024 | o orçamento de peers padrão de um nó |
MaxSettlers | 7 ou MaxMembers se for menor, faixa de 1 a 64 | com Majority, tolera então 3 offline |
MinSettlers | 4 ou MaxSettlers se for menor, faixa de 1 a MaxSettlers | tolera um settler offline e um que assina dois históricos |
MaxBody | 1 MiB, faixa de 1 KiB a 3 MiB | o limite de valor da visão |
CheckpointEvery | 1024 posições assentadas, faixa de 64 a 2^20 | uma divergência é detectada dentro dessas posições |
Locais a um peer (Limits); um valor fora da sua faixa retorna ErrInvalidArgument:
| Campo | Padrão |
|---|---|
MaxTail | 2048: uma reorganização reaplica no máximo essas entradas |
MaxPendingBytes | 16 MiB de entradas que esperam por uma anterior; um strand guarda no máximo MaxPendingBytes / MaxMembers delas (uma entrada sempre cabe) |
MaxForks | 4, 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 |
MaxPullAhead | MaxTail |
PulseGap | 500 ms |
PivotWait | 3 s |
AnnounceGap | 100 ms |
ConfirmWait | 10 s |
MaxEvents | 1024 |
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
ServeConnconfia emConn.RemotePublicKey: passe só conexões cuja chave foi provada em um handshake, como um*kolosecure.Conn. - O mapa do
kvnão tem controle de acesso: qualquer membro ativo escreve qualquer chave. - Uma pessoa só conta para
roster.Admitdepois que um admin registrou um certificado dela, então um membro simples não consegue inventar uma. A partir daí,roster.Admitdeixa entrar cada dispositivo seguinte que prove um certificado válido, sem limite de taxa: as vagas do grupo eMaxCertsPerPersonsão os únicos limites. Os certificados emitidos por aprovadores não conseguem encher o registro, porquePersonCertReservereserva 128 dos 1024 espaços para a chave de pessoa. devices.Store.Verifyverifica 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
PulseGappadrã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 umPulseGapmenor (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
| Erro | Mensagem |
|---|---|
ErrActiveKey | kolobraid: key already active |
ErrBadSeed | kolobraid: seed does not match its digest |
ErrClosed | kolobraid: closed |
ErrCorrupt | kolobraid: corrupt data |
ErrDiverged | kolobraid: view diverged from a certified digest |
ErrEquivocation | kolobraid: writer signed two histories |
ErrErased | kolobraid: strand entry erased |
ErrGroupFull | kolobraid: group full |
ErrHalted | kolobraid: view halted |
ErrInvalidArgument | kolobraid: invalid argument |
ErrInvalidConfig | kolobraid: invalid group config |
ErrKnownStrand | kolobraid: strand already known |
ErrMalformed | kolobraid: malformed encoding |
ErrNotAdmin | kolobraid: not an admin |
ErrNotFound | kolobraid: not found |
ErrNotMember | kolobraid: not an active member |
ErrProtocol | kolobraid: protocol violation |
ErrRejected | kolobraid: entry rejected |
ErrRemoved | kolobraid: member removed |
ErrReorged | kolobraid: order changed |
ErrStrandLost | kolobraid: own strand lost |
ErrTooLarge | kolobraid: value too large |
ErrTxDone | kolobraid: transaction done |
ErrUnconfirmed | kolobraid: own strand not confirmed |
ErrViewLimit | kolobraid: view limit exceeded |
ErrWrongApp | kolobraid: wrong app tag |
ErrWrongGroup | kolobraid: wrong group |
devices.ErrNotAdmitted | kolobraid: the group did not take the member |
devices.ErrNotProven | kolobraid: device certificate not proven |
devices.ErrNotRecorded | kolobraid: the roster did not take the record |
devices.ErrTooManyDevices | kolobraid: too many devices of this person in the group |
devices.ErrUnknownDevice | kolobraid: no certificate for this device |
devices.ErrUnknownPerson | kolobraid: 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
- Keidar, Kokoris-Kogias, Naor and Spiegelman, All you need is DAG, PODC 2021.
- Usa: a ordenação do histórico causal dos líderes confirmados em um DAG por rodadas.
- Não implementa: uma camada de difusão confiável. Um assento que equivoca interrompe o assentamento em seu lugar.
- Spiegelman, Giridharan, Sonnino and Kokoris-Kogias, Bullshark: DAG BFT protocols made practical, CCS 2022.
- Usa: líderes em rodadas alternadas.
- Não implementa: nada.
- Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, 1978.
- Usa: a relação happened-before.
- Não implementa: os relógios físicos.
- Fidge, Logical time in distributed computing systems, Computer, 1991, and Schwarz and Mattern, Detecting causal relationships in distributed computations: in search of the holy grail, Distributed Computing, 1994.
- Usa: relógios vetoriais derivados dos links, nunca enviados.
- Não implementa: nada.
- Kahn, Topological sorting of large networks, Communications of the ACM, 1962.
- Usa: ordenação topológica com desempate determinístico.
- Não implementa: nada.
- Merkle, A digital signature based on a conventional encryption function, CRYPTO '87.
- Usa: cadeias ligadas por hash e o DAG de Merkle.
- Não implementa: nada.
- Kleppmann and Howard, Byzantine eventual consistency and the fundamental limits of peer-to-peer databases, arXiv:2012.00472, 2020.
- Usa: a equivocação como prova.
- Não implementa: nada.
- Défago, Schiper and Urbán, Total order broadcast and multicast algorithms: taxonomy and survey, ACM Computing Surveys, 2004, and Gifford, Weighted voting for replicated data, SOSP 1979.
- Usa: a classe de difusão com ordem total, e a interseção de quóruns.
- Não implementa: nada.
- Lamport, Malkhi and Zhou, Reconfiguring a state machine, ACM SIGACT News, 2010, and Ongaro and Ousterhout, In search of an understandable consensus algorithm, USENIX ATC 2014, section 6.
- Usa: a reconfiguração como comandos do log, e os membros novos que se atualizam antes de contar.
- Não implementa: nada.
- Saito and Shapiro, Optimistic replication, ACM Computing Surveys, 2005, and Terry et al., Managing update conflicts in Bayou, a weakly connected replicated storage system, SOSP 1995.
- Usa: execução tentativa, reversão e confirmação.
- Não implementa: nada.
- Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys, 1990.
- Usa: a máquina de estados determinística alimentada por uma ordem acordada.
- Não implementa: nada.
- Dennis and Van Horn, Programming semantics for multiprogrammed computations, Communications of the ACM, 1966, and RFC 2693, SPKI Certificate Theory (Experimental, setembro de 1999).
- Usa: a lista de capacidades, e a autorização de um salto.
- Não implementa: as cadeias de delegação.
- RFC 9162, Certificate Transparency Version 2.0 (Experimental, December 2021) and RFC 8032, Edwards-Curve Digital Signature Algorithm (EdDSA) (Informational, janeiro de 2017).
- Usa: os strands assinados e ligados por hash e o Ed25519ctx, por meio da kolo-log e da kolo-id.
- Não implementa: nada.
- RFC 7693, The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC) (Informational, novembro de 2015).
- Usa: BLAKE2b-256 para cada hash.
- Não implementa: nada.
- ITU-T G.114, One-way transmission time (05/2003, em vigor).
- Usa: 150 ms e 400 ms de atraso em um sentido, para
PivotWait. - Não implementa: nada.
- Usa: 150 ms e 400 ms de atraso em um sentido, para
- Cerca de 100 ms, o limite habitual para uma interface parecer imediata.
- Usa: um orçamento de entrada de 50 ms, metade dele, para o
MaxTailpadrão. - Não implementa: nada.
- Usa: um orçamento de entrada de 50 ms, metade dele, para o
- Kulkarni, Demirbas, Madappa, Avva and Leone, Logical physical clocks, OPODIS 2014.
- Usa: nada.
- Não implementa: tudo. Foi considerado e não usado, porque uma entrada não tem campo de tempo.