Un braid es un conjunto de strands: un log firmado de kolo-log por miembro, guardado con kolo-store. Cada peer que tiene las mismas entradas calcula el mismo orden, byte a byte, a partir de la relación happened-before de Lamport y de la regla de commit sobre un DAG por rondas de DAG-Rider y Bullshark, y se lo pasa a una función apply escrita por ti, una máquina de estados determinista, que construye una vista sobre kolo-store. Los peers se sincronizan con ServeConn por conexiones directas y a través de un relay (kolo-secure, kolo-relay o cualquier peer de kolo-swarm), y un miembro nuevo entra con una solicitud de entrada y un welcome que puede llevar kolo-invite. Los paquetes Go son kolobraid, kv (un mapa clave-valor en la vista), devices (un registro de certificados de dispositivo, y la admisión de los dispositivos certificados de una persona) y kolobraidtest (comprobaciones para una función apply).
El orden tiene dos partes. El prefijo asentado no cambia nunca. La cola tentativa que lo sigue se aplica en memoria y todavía puede reordenarse cuando llegan entradas. Las lecturas eligen entre las dos: Braid.Settled para la vista asentada sola, Braid.View para lo asentado más lo tentativo.
Strands, links, pulsos y lotes
Cada peer que tiene las mismas entradas calcula el mismo orden, byte a byte, y se lo pasa a tu función apply.
- Cada miembro escribe su propio strand: un log de kolo-log firmado en el que cada entrada nombra a la anterior. Aquí A y B son settlers y C es un miembro.
- Una entrada enlaza como mucho una entrada de cada otro strand: la más nueva que tiene quien la escribe. Los links unen todos los strands en un solo grafo.
- Los settlers escriben pulsos, que asientan el orden y nunca se aplican. A y B escriben cada uno un pulso de la ronda 0. En una ronda par, el pulso del asiento pivote de esa ronda es el pivote: aquí A0.
- Un pulso que contiene pulsos de la ronda r de q asientos es de la ronda r + 1. Cuando los pulsos de la ronda 1 de q asientos contienen el pivote, queda confirmado. Con dos asientos y Majority, q es 2.
- El pivote confirmado asienta, como un lote, todo lo que contiene y aún no está asentado: un orden topológico cuyos empates se deciden con un hash sembrado con el ID del pivote. Las posiciones asentadas no cambian nunca.
- El resto es la cola tentativa, ordenada como los lotes en los que se prevé que se asiente. Se aplica en memoria sobre la vista asentada y puede reordenarse cuando llegan entradas.
Instalación
go get github.com/ciranda-dev/kolo-braidNecesita Go 1.26 o posterior y es Go puro. Construye un documento compartido en dos terminales explica paso a paso cómo dos personas escriben un mismo documento en 127.0.0.1, a partir del repositorio kolo-braid-starter. Paso 7: Acordar miembros y salas con kolo-braid guarda en un braid la lista de miembros y la lista de salas de un chat de escritorio. Compila con CGO_ENABLED=0 para un binario sin código C: Pebble, que usa kolo-store, enlaza una biblioteca zstd en C cuando cgo está activo.
Inicio rápido
Un miembro, un braid en un directorio de Pebble dentro del primer argumento y una función apply que guarda cada mensaje y los cuenta. El segundo Append tiene el cuerpo vacío, y apply lo rechaza. Es examples/apply del repositorio. Ejecútalo con 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)
}
}Imprime:
1 settled message(s)
1 rejected by applyLa entrada rechazada conserva su posición en el orden, con Ordered.Rejected activado, y sus escrituras se descartan en todos los peers. Append vuelve en cuanto la entrada está escrita; el bucle espera en Next hasta que la entrada queda asentada y después lee la vista asentada.
La función apply
type ApplyFunc func(tx *Tx, e *Entry) errorapply se llama una vez por entrada, en el orden, con una transacción sobre la vista. La biblioteca hace que el orden sea el mismo en todos los peers. Solo tú puedes hacer que apply dé el mismo resultado a partir del mismo orden.
El contrato
- apply debe ser una función pura de la vista anterior a
e, deey del roster en la posición dee(Tx.Member,Tx.Members). No ve reloj, ni azar, ni el orden de iteración de un map, ni E/S. - La coma flotante que llega a la vista debe redondearse de forma explícita después de cada operación, por ejemplo
float64(x * y), y las funciones demathque no seanAbs,Copysign,Floor,Ceil,TruncySqrtno deben llegar a ella. Los enteros o las cadenas decimales son la opción sencilla. - apply se llama para las entradas efectivas de los tipos genesis, data, AddMember, RemoveMember, Settlers y Evidence, y nunca para pulsos, seeds y entradas nulas. En los tipos de membresía la biblioteca ya aplicó el efecto, así que rechazar una solo descarta las escrituras de apply.
- Devolver nil confirma las escrituras.
Reject(reason)las descarta y registra la entrada como rechazada en todos los peers: es el único fallo determinista. Cualquier otro error, y un panic, detiene la vista solo en este peer:EventHaltedyStatus.Haltedllevan la posición, y el siguienteOpenlo reintenta. - Por entrada, las claves miden como mucho 32 KiB y los valores 1 MiB, y las escrituras tienen un presupuesto de 16 x
MaxBody, donde cada operación cuesta su clave y su valor más 256 bytes. Pasado un límite la llamada devuelveErrViewLimity la entrada se rechaza en todos los peers, devuelva lo que devuelva apply. - Un
Txusado después de que apply volvió falla conErrTxDone. apply corre en su propia goroutine, así que un apply lento solo retrasa la aplicación.
Comprobar que apply es puro
Un apply impuro rompe la convergencia aunque todos los peers tengan el mismo orden. Dos funciones de kolobraidtest ejecutan tu apply sobre un historial cuyo orden final das tú:
CheckApply(t, apply, entries)hace fallar el test cuando asentar el historial entrada a entrada, en lotes y tamaños de bloque aleatorios, entre reinicios, y después de una reorganización tentativa y su promoción, no termina siempre con el mismo digest acumulado y la misma vista.FindDivergence(apply, entries, replicas, seed)ejecuta réplicas que reciben cada una las entradas en su propio orden de entrega barajado, aplican de forma tentativa lo que tienen, se reorganizan cuando llega una entrada anterior y asientan por partes. Devuelve la primera posición en la que el digest acumulado de una réplica difiere del de la réplica 0, nil cuando todas coinciden, o un error cuando apply se detuvo.
Este es el ejemplo del paquete, que go test compila y comprueba. El segundo apply cuenta sus llamadas en una variable fuera de la vista, así que las réplicas que aplican entradas tentativas un número distinto de veces discrepan en la primera posición:
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 1Un resultado limpio cubre solo los caminos y las entradas que diste, así que construye historiales que usen cada tipo de cuerpo que escribe tu aplicación. En ejecución, cada peer guarda además un digest acumulado de las escrituras asentadas. En cada checkpoint, cada CheckpointEvery posiciones asentadas, los settlers declaran su digest en su siguiente pulso, y un peer cuyo digest difiere del que declararon q settlers se detiene con ErrDiverged y un EventDiverged.
Cambiar apply entre versiones
No cambies nunca el efecto de una entrada en una posición que una versión anterior ya aplicó. Empieza el comportamiento nuevo en una posición marcada por una entrada de datos asentada que define tu aplicación (o un campo de versión en los cuerpos), conserva el camino de código antiguo antes de ella, y haz que el código antiguo devuelva un error distinto de Reject ante un marcador que no conoce, para que se detenga hasta que se actualice. kolobraidtest.CheckUpgrade(t, old, new, entries, marker) comprueba que la versión nueva conserva cada posición anterior al marcador.
Preparar un escritor
Un dispositivo que escribe necesita una identidad que conserve y un directorio de almacenamiento que no comparta nunca. Este programa guarda una identidad de kolo-id en un directorio privado, crea un braid en un directorio de Pebble, escribe, cierra, y luego carga la identidad y abre el braid de nuevo. Es examples/writer; ejecútalo con 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)
}
}Imprime:
created the braid and wrote 1 message
reopened the braid, own strand unconfirmed: false
messages in the settled view: first, secondGroupConfig queda fijado por la entrada genesis y todos los peers lo acuerdan. Options es local: el backend, un prefijo de clave, la función apply, los pins y Limits. Varios braids comparten un backend con PrefixBackend(db, prefix) o Options.Prefix, con prefijos de los que ninguno es prefijo de otro.
Después de cada Open, el strand propio no está confirmado, y las llamadas de escritura lo esperan mientras su contexto lo permita:
- Un braid que nunca tuvo otro miembro y no tiene pin queda confirmado por su propio almacenamiento enseguida, como aquí.
- Un miembro que no es settler queda confirmado de inmediato por un head consistente de su strand, de un miembro o de un pin, que sea tan largo como el strand. Un head más corto lo confirma solo cuando ha pasado
ConfirmWaitdesdeOpen, así que un dispositivo tan atrasado como una copia de seguridad restaurada no puede confirmarse antes de que un miembro con un head más largo lo haya mostrado. - Un settler necesita esos heads de cada uno de los demás settlers que responden dentro de
ConfirmWait, y de al menos q - 1 de ellos. - Un head consistente más largo significa que el dispositivo va atrasado: las llamadas de escritura esperan hasta que se ponga al día desde una copia completa. Un head en conflicto hace perder el strand: las escrituras fallan con
ErrStrandLost.
No copies nunca el directorio de datos de un miembro ni ejecutes una copia de él: dos copias en marcha confirman las dos y escriben las dos antes de que una vea a la otra. Options.AppendUnconfirmed escribe enseguida, con ese riesgo.
Una entrada de un braid no se puede borrar nunca. Cada peer guarda cada entrada y su clave, así que los datos que puedan necesitar borrarse quedan fuera del braid. El historial no se poda nunca, y cada entrada cuesta unos 600 bytes de disco en cada peer.
Añadir un escritor con kolo-invite
Un miembro nuevo crea su strand con NewJoin y envía Joining.Request a un admin. El Admit del admin añade una entrada AddMember y devuelve el welcome, y el Complete del que entra convierte el welcome en su braid. kolo-invite lleva las dos cosas: la solicitud de entrada como datos de entrada y el welcome como payload sellado para quien entra. kolo-braid solo intercambia bytes y no importa kolo-invite.
Este programa lo ejecuta todo en 127.0.0.1: un servidor de kolo-dht en el mismo proceso, el admin con un braid, una invitación manual y un swarm de kolo-swarm, y el que entra, que encuentra al anfitrión en el topic de la invitación, envía su solicitud, deja el topic de la invitación, completa la entrada y se sincroniza en el topic propio del braid. Es examples/addwriter; ejecútalo con 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)
}
}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: trueCrea las invitaciones con Manual: true: una invitación que acepta sola envía un payload fijo, y cada persona que entra necesita su propio welcome. Una conexión la atiende ServeConn cuando el peer comparte el topic del braid, y el ServePeer del anfitrión en otro caso; cada uno debe ser el único que acepta streams en su conexión.
| Caso | Admin | Quien entra |
|---|---|---|
| Admitido | Admit añade AddMember (y, con GrowSettlers, una entrada Settlers cuando toca); Approve envía el welcome | el welcome; Complete |
| Falla una escritura después de la entrada AddMember | ese error; deny y RemoveMember | invite.ErrDenied |
| Ya es un miembro activo | ErrActiveKey; deny | invite.ErrDenied |
| Strand usado antes o conocido | ErrKnownStrand; deny | invite.ErrDenied |
| Strand de la solicitud firmado por otra clave | ErrInvalidArgument; deny | invite.ErrDenied |
| El admin no es admin, o tiene su propia eliminación | ErrNotAdmin, ErrRemoved; deny | invite.ErrDenied |
La invitación caducó, se revocó o se agotó antes de Approve | Approve devuelve invite.ErrExpired, ErrRevoked o ErrUsedUp; RemoveMember | el mismo error, sin welcome |
| Volver a pedir después de una aceptación | ningún evento, nada añadido | el mismo welcome |
Sin opciones, Admit admite a un miembro simple: escribe, pero no es admin ni settler, y no se escribe ninguna entrada Settlers. AdmitOptions.Roles fija los roles. AdmitOptions.GrowSettlers hace crecer el braid hacia MinSettlers asientos y MinSettlers - 1 admins: los primeros en entrar pasan a ser admins, que pueden añadir y quitar a cualquiera, y settlers, y se añade una entrada Settlers cuando toca; úsalo solo con quienes les confíes tanto. Roles junto con GrowSettlers es ErrInvalidArgument. Las llamadas a Admit se ejecutan de una en una, así que los que se admiten a la vez con GrowSettlers cuentan cada uno las entradas del anterior. AdmitOptions.Replace permite que el dispositivo nuevo de un miembro tome el relevo con un strand nuevo y conserve sus roles.
Braid.CheckAdmit(joiner, request) informa, sin escribir nada, de lo que Admit rechazaría ahora (ErrNotAdmin, ErrRemoved o ErrNotMember para este peer, ErrActiveKey, ErrKnownStrand), y de ErrGroupFull cuando el grupo ya tiene MaxMembers miembros activos, que Admit no devuelve: añade una entrada AddMember que el roster deja luego sin efecto. WelcomeEntry(welcome) devuelve la entrada AddMember que nombra un welcome, y Braid.PublicKey la clave con la que este peer ejecuta el braid. El paquete devices de más abajo usa las tres.
El braid que devuelve Complete arranca en cuanto un miembro le sirve la entrada genesis del strand fundador. Sus llamadas de escritura esperan hasta que tenga esa entrada y su propia entrada AddMember esté en el orden, así que el primer Append no necesita esperar por su cuenta; un ErrNotMember después de eso significa que el orden dejó nula la entrada AddMember. Una entrada sobrevive a un reinicio de quien entra: NewJoin en el mismo prefijo con la misma identidad devuelve la entrada pendiente, con el mismo strand y la misma solicitud.
Quitar un escritor
RemoveMember, llamado por un admin, quita a un miembro en la posición de su entrada, como cualquier cambio de membresía. Este programa admite a B, le deja escribir, lo quita, muestra lo que conserva cada lado y vuelve a admitir a B con un strand nuevo. Es examples/removewriter; ejecútalo con 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)
}
}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- Las entradas de membresía se comprueban en su propia posición del orden, nunca frente al roster del momento en que llegan, así que todos los peers las deciden igual. Siempre quedan al menos una clave de admin y una de settler.
- Las entradas de un strand quitado ordenadas antes de la eliminación conservan su efecto; las ordenadas después son nulas en todas partes. Las eliminaciones van primero entre las entradas que están listas a la vez, así que una entrada concurrente se conserva solo si quedó ordenada antes de que la eliminación estuviera lista.
- Un miembro quitado conserva todo lo que recibió. kolo-braid no puede recuperar datos que un dispositivo ya tiene.
- Por la red, a un miembro quitado se le deniega el acceso, no necesariamente se le avisa. Los peers que tienen la eliminación dejan de enlazar su strand y dejan de servirle desde su siguiente petición, y cierran su conexión cuando su clave lleva 60 s desconocida. Recibe
EventRemovedsolo cuando tiene la eliminación asentada, y eso solo puede dárselo un peer que todavía no tenía la eliminación; si no, simplemente no recibe nada más. - Un settler quitado es la excepción hasta que se activa una configuración de settlers sin él: sus pulsos siguen contando, así que sigue escribiendo pulsos y los peers siguen sirviéndole.
- Un miembro quitado al que se invita de nuevo entra con un strand nuevo (
NewJoinen un prefijo nuevo): su strand antiguo queda usado, yAdmitlo rechaza conErrKnownStrand.
Dos peers sincronizados
Dos miembros en una misma máquina, cada uno con un directorio de Pebble dentro del primer argumento, sincronizados por una conexión de kolo-secure en 127.0.0.1. A crea el braid y admite a B, los dos añaden un mensaje y cada uno asienta los dos en el mismo orden. Es examples/twopeers y el inicio rápido del README; ejecútalo con 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)
}
}Imprime:
A settled 2 messages
B settled 2 messages
same order: trueEn una aplicación, únete al topic de kolo-swarm del braid (Braid.Topic) y atiende a cada peer conectado con ServeConn:
sw.Join(ctx, koloswarm.Topic(b.Topic()), nil)
// for every Connected event:
go b.ServeConn(ctx, ev.Peer.Conn())Lo que pasa por una conexión:
- Los strands, con kolo-sync, un pull por strand a la vez y como mucho 16 a la vez. El strand de un miembro se trae hasta su longitud asentada más
MaxPullAhead, el de un settler hastaMaxPullAheaddespués de su pulso más nuevo que se tiene, y cada strand hasta lo que enlace una entrada que se tiene. - Los heads (ANNOUNCE): todos los heads en el primer mensaje, después solo los que cambiaron, como mucho un mensaje por
AnnounceGap. - Segundos historiales y pruebas: una entrada que nombra un link pero en cuyo lugar este peer tiene otra se trae con el head firmado de quien la escribió y se verifica entrada a entrada; dos registros de un mismo índice firmados por quien escribe son una prueba, que cada peer envía una vez por conexión.
- Después de
Open, el head del strand propio en cada peer, que confirma el strand propio o le permite ponerse al día.
El acceso sigue al roster tentativo: los miembros activos y los settlers de la configuración actual y de la pendiente reciben las claves de las entradas, los pins solo texto cifrado, y cualquier otro nada. ServeConn toma los dos tipos de stream de la conexión, así que una conexión que usa el ServePeer de kolo-invite no puede servir también al braid. Devuelve nil cuando termina su contexto o la conexión, ErrClosed cuando el braid se cierra, y un error que envuelve ErrProtocol después de cerrar la conexión de un peer que rompió el protocolo.
Conexiones directas y a través de un relay
ServeConn recibe un Conn: una conexión autenticada con un peer, directa o a través de un relay, como un *kolosecure.Conn, un *kolorelay.Conn o un koloswarm.Conn. Un Conn nil, o uno que guarda un puntero nil, es ErrInvalidArgument. ServeConn confía por completo en RemotePublicKey, así que pasa solo conexiones cuya clave se haya demostrado en un handshake, como un *kolosecure.Conn: RemotePublicKey tiene que devolver la clave que el peer demostró en el handshake de extremo a extremo. Un enlace a través de un relay la demuestra igual, así que las comprobaciones de miembros y pins son las mismas que en una conexión directa. Un relay copia bytes que no puede leer; lo que aun así llega a saber está en la página de kolo-relay.
Asentamiento
Settlers y la regla de quórum
Los settlers son los miembros cuyos pulsos asientan el orden. Una configuración nombra sus claves y la regla de quórum, y q de sus n asientos deben contener un pivote para que quede confirmado. El asentamiento continúa mientras q settlers de la configuración actual están en línea.
| Asientos | q con Majority | Settlers que pueden firmar dos historiales sin dividir prefijos | q con 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, el valor por defecto, necesita floor(n/2) + 1 asientos y es para fallos por caída. TwoThirds necesita floor(2n/3) + 1 y es para braids en los que un dispositivo settler puede quedar comprometido. Con cualquiera de las dos reglas, los prefijos asentados no entran nunca en conflicto mientras como mucho f asientos firmen dos historiales, donde f es el mayor valor con 2q - n > f. Un settler de la configuración actual que firma dos historiales detiene el asentamiento para siempre en cada peer que ve los dos (EventSettlementHalted con su clave); la aplicación tentativa y las entradas nuevas siguen. Un escritor que no es settler y firma dos historiales queda aislado: una entrada Evidence deja su strand inactivo desde esa posición, y el asentamiento sigue.
Una entrada Settlers (SetSettlers) cambia la configuración. Un cambio que añade asientos se activa en un pivote confirmado cuyo pasado contiene un pulso de disponibilidad de cada asiento añadido; un cambio que solo quita asientos se activa enseguida.
Crecer hasta cuatro settlers
MinSettlers vale 4: Admit con AdmitOptions.GrowSettlers convierte en admins y settlers a los primeros que entran hasta que el braid tiene cuatro asientos; un Admit simple no lo hace. Con Majority, 4 settlers dan q = 3: uno puede estar desconectado y uno puede firmar dos historiales sin dividir los prefijos asentados. 3 o 5 settlers no dan ese margen, y con ellos un dispositivo settler mal restaurado o clonado puede dividir el braid. Un braid con un solo settler depende de ese dispositivo: Status.SingleSettler lo indica.
Settlers desconectados
El asentamiento se detiene mientras hay menos de q settlers en línea y sigue cuando vuelven suficientes; mientras tanto las entradas nuevas se quedan en la cola tentativa. Un settler que se reinicia vuelve a escribir cuando los demás settlers que responden dentro de ConfirmWait confirman su strand. El orden entre entradas concurrentes lo decide un hash sembrado con el pivote, que el settler del pivote puede intentar elegir: no es justo, y una regla de "gana el primero" no debe depender de él.
Tiempos medidos
Estos números vienen de una ejecución de los escenarios de prueba en un Mac con Apple M5 (darwin/arm64, Go 1.27.3), un proceso por peer en 127.0.0.1, mientras la máquina estaba ocupada con otros trabajos. Los peers usaron ajustes cortos: PulseGap 50 ms, PivotWait 500 ms, AnnounceGap 20 ms y ConfirmWait 2 s, cuando los valores por defecto son 500 ms, 3 s, 100 ms y 10 s. Un tiempo va desde el final de la acción (la última escritura que volvió, una reconexión, un reinicio) hasta la primera consulta, cada 20 a 250 ms, en la que todos los peers coincidían. No se midió nada con los ajustes por defecto, en otro hardware ni a través de una red real.
| Escenario | Tiempo |
|---|---|
| 3 peers (3 settlers) escriben 25 entradas cada uno, todo asentado | 280 ms |
| 4 peers (4 settlers) escriben 25 entradas cada uno, todo asentado | 513 ms |
| 5 peers (4 settlers) escriben 25 entradas cada uno, todo asentado | 687 ms |
| 5 peers divididos en 3 y 2: el lado con tres de los cuatro settlers asienta 90 entradas | 678 ms |
| los mismos peers coinciden cuando la división se cura | 398 ms |
| 3 settlers, 2 detenidos, 10 entradas quedan tentativas; un settler se reinicia | 2,43 s, de los que 2 s son su ConfirmWait |
3 peers escribieron 10.002 entradas en 83,6 s (cada Append es duradero): todo asentado después de la última escritura | 898 ms |
| un miembro que entra tarde asienta ese mismo prefijo después de conectarse a los peers | 1,392 s |
llamada a Admit | de 6 a 19 ms |
de Admit al final de Complete | de 13 a 42 ms |
Braids sucesores
Cuando el quórum de settlers se pierde para siempre, un admin del roster asentado antiguo llama a Succeed. La entrada genesis del braid nuevo nombra el grupo antiguo, su posición asentada p y el digest de contenido de la vista asentada en p; las entradas seed copian esa vista, cada peer comprueba el digest (ErrBadSeed si no coincide) y las posiciones siguen en p + 1. Las entradas tentativas del braid antiguo no pasan. Quien entra y nunca fue miembro confía en el fundador del sucesor para la vista sembrada. Un miembro que todavía tiene el braid antiguo lo pasa como Options.Predecessor, y su braid se detiene salvo que el fundador fuera admin del antiguo y la vista sembrada sea la vista asentada antigua.
El helper kv
El paquete github.com/ciranda-dev/kolo-braid/kv mantiene un mapa clave-valor en la vista. Los puts y los deletes son entradas de datos, y la última operación efectiva sobre una clave en el orden del braid gana, igual en todos los peers, sin reloj. Las escrituras concurrentes las decide el orden, que no es justo, así que las reglas de "gana la primera escritura" no deben depender de él. El mapa no tiene control de acceso: cualquier miembro activo puede poner o borrar cualquier clave. Cuando las claves pertenecen a miembros, comprueba Entry.Writer (y Tx.Member para sus roles) en la función 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): los pares viven en la vista bajo el prefijo y la clave, y ninguna otra clave de la aplicación puede empezar por el prefijo.Applytrata las entradas de datos cuyo cuerpo empieza con la etiqueta kv y devuelve false para cualquier otra entrada, así que una aplicación dirige sus propias entradas a su lado. Un cuerpo kv que no se decodifica, o cuya clave no cabe con el prefijo, se rechaza conReject, igual en todos los peers.PutyDeleteañaden una entrada cada uno, que surte efecto en su posición. Las claves miden como mucho 32 KiB con el prefijo y los valores 1 MiB (kolobraid.ErrTooLarge), y el cuerpo entero como mucho elMaxBodydel braid.GetyRangeleen una instantánea:Braid.Settledpara lo que ya no cambia,Braid.Viewpara lo asentado más lo tentativo, que una reorganización puede cambiar.Range(start, end)da las claves en[start, end); un end vacío no tiene límite superior.
Los tests del paquete lo pasan por kolobraidtest.CheckApply y FindDivergence.
Dispositivos de una persona
El paquete github.com/ciranda-dev/kolo-braid/devices guarda en la vista los certificados de dispositivo y las revocaciones de kolo-id de las personas de un grupo, y deja que un admin admita un dispositivo certificado de una persona que ya pertenece al grupo sin una decisión nueva. Una clave de persona, sacada de las 24 palabras, certifica dispositivos aprobadores, los aprobadores certifican dispositivos normales, y una clave de dispositivo firma los mensajes. Cada clave de dispositivo es un miembro normal con su propio strand. El paquete no cambia nada en el orden, el asentamiento, las reglas de membresía ni los formatos del braid, Braid.Admit no cambia, y un grupo que no lo importa se comporta como antes. Un dispositivo recibe su certificado con una invitación de kolo-invite para vincular un dispositivo.
Este programa es examples/devices; ejecútalo con go run . "$(mktemp -d)". Un portátil funda un grupo y ancla su certificado de aprobador, certifica un teléfono, lo admite sin una decisión nueva y después lo revoca.
// 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)
}
}
}Imprime esto:
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 y anclas
- Los registros son entradas de datos cuyo cuerpo empieza por
kolo-braid/devices/v0. Cualquier miembro puede escribir uno, porque un certificado o una revocación es su propia prueba.Applyrechaza, igual en todos los peers, un cuerpo que no se decodifica, un certificado o una revocación que no se verifica, un certificado cuyo número de serie no es mayor que el guardado, un certificado emitido por un aprobador ya retirado y un registro que supera un límite. Comprueba la estructura y las firmas sin reloj: la caducidad, la revocación y el momento de la comprobación son cosa de quien lee. - Cualquier miembro puede inventarse una clave de persona y un certificado para ella, así que una persona solo cuenta para la admisión cuando un admin registró un certificado suyo. Ese certificado queda anclado.
Store.Recordes la llamada del admin para el primer dispositivo de una persona, después de que el admin decidiera conBraid.Admitdejar entrar a ese dispositivo, yStore.Admitancla los certificados que admite. - La vista guarda un certificado por persona y dispositivo, el de número de serie más alto. La revocación de un aprobador lleva en la entrada el certificado al que apunta, así que se puede comprobar sola y en cualquier orden.
Cert,Anchored,DevicesyRevocationsleen una instantánea.Verify(snap, person, device, now, context, msg, sig)ejecutakoloid.VerifyDevicesobre el certificado guardado con las revocaciones guardadas, para la persona que le pasas: fija la persona en tu propio estado, nunca la leas de un certificado.ErrUnknownDevicesignifica que el registro no tiene ningún certificado para el dispositivo.- Los aprobadores se retiran por la posición en el orden del braid, que es la misma en todos los peers, no por un reloj. Una revocación firmada por un aprobador no se usa cuando su posición va después de la primera revocación de ese aprobador por la clave de persona o por el propio aprobador, y un certificado emitido por un aprobador retirado se rechaza. Un aprobador retirado sigue retirado aunque su clave se certifique de nuevo: usa una clave nueva.
Admitir un dispositivo
El dispositivo nuevo prepara su solicitud de entrada con devices.NewJoinRequest(join, id, cert, group, appData), que añade una prueba de que tiene la clave certificada: una firma sobre la persona, el grupo y el strand de la propia solicitud con kolo-braid/device-admit/v0. Un admin llama a roster.Admit(ctx, b, joinerKey, request) en lugar de Braid.Admit. Antes de escribir nada, comprueba en este orden:
- la solicitud lleva una prueba y su certificado es para la clave de quien entra (
ErrNotProven); - lo que
Braid.Admitrechazaría ahora, y un grupo lleno, conBraid.CheckAdmit(kolobraid.ErrNotAdmin,ErrActiveKey,ErrKnownStrand,kolobraid.ErrGroupFully los demás); - la persona tiene en el grupo un miembro activo asentado cuyo certificado anclado se verifica ahora (
ErrUnknownPerson); - el certificado no es más antiguo que el del registro, y
koloid.VerifyDevicelo acepta enOptions.Nowcon las revocaciones del registro (ErrNotProven, que también coincide con errores de kolo-id comokoloid.ErrCertExpiredykoloid.ErrCertRevoked); - cuando
Options.MaxDevicesestá fijado, la persona tiene menos plazas que eso (ErrTooManyDevices).
Después añade el certificado, anclado, y espera a que el registro lo tenga (ErrNotRecorded cuando se asentó sin efecto). Llama a Braid.Admit con un rol normal, ni admin ni settler, y espera a que la vista muestre al miembro nuevo (ErrNotAdmitted cuando la entrada AddMember se asentó sin él). Cada espera termina con el contexto de quien llama. No se concede nada cuando falló un paso anterior a Braid.Admit. Un grupo cuya política es que la persona apruebe cada dispositivo nunca llama a roster.Admit.
Todos los peers de un grupo tienen que usar la misma versión de kolo-id, porque apply verifica las firmas con ella. Pon la versión de kolo-id en la cadena App del grupo, por ejemplo chat/v1+id0.1.0, y cámbiala con la versión.
Límites de los dispositivos
Por defecto no hay límite de dispositivos por persona. Cada dispositivo ocupa una plaza del grupo (MaxMembers, 64 por defecto), y esas plazas son el único límite; el ancla es lo que impide que una persona inventada ocupe plazas. Un dispositivo revocado conserva su plaza hasta que un admin lo quita con RemoveMember.
devices.Options | Por defecto | Rango | Por qué |
|---|---|---|---|
MaxCertsPerPerson | 1024 | de 1 a 2^20 | los certificados de una persona en una vista; el siguiente se rechaza |
PersonCertReserve | una octava parte del límite, 128 | de 0 a MaxCertsPerPerson, -1 para ninguna | huecos reservados para certificados emitidos por la clave de persona, para que un aprobador robado no pueda llenar el registro |
MaxRevocationsPerDevice | 64 | de 1 a 2^16 | revocaciones de aprobador de una clave de dispositivo |
MaxDevices | ninguno | cualquier valor positivo | un tope opcional de las plazas de una persona que Admit deja entrar (ErrTooManyDevices) |
Los tres primeros deciden qué entradas rechaza apply, así que todos los peers de un grupo tienen que usar los mismos valores. MaxDevices es un ajuste del peer que admite: dos admins que admiten en el mismo momento cuentan cada uno desde su propia vista, así que entre los dos pueden pasarse en uno cada uno. Un certificado ocupa como mucho 514 bytes y una revocación 472 bytes, las codificaciones de kolo-id, y una prueba ocupa menos de 700 bytes dentro del límite de 64 KiB de una solicitud de entrada. Una persona que pierde todos sus dispositivos y restaura las 24 palabras recupera la clave de persona pero no una plaza: un admin admite el dispositivo nuevo con Braid.Admit y registra su certificado.
Formatos
Cada hash es BLAKE2b-256 sobre una codificación de kolo-codec que empieza con su propia etiqueta: kolo-braid/entry-id/v0 (IDs de entrada; el ID del grupo es el ID de la entrada genesis), kolo-braid/order/v0 (claves de desempate), kolo-braid/config/v0 (IDs de configuración), kolo-braid/digest/v0 (digest acumulado), kolo-braid/content/v0 (digest de contenido) y kolo-braid/topic/v0 (el topic de kolo-swarm, Braid.Topic). Las entradas empiezan con kolo-braid/entry/v0, la solicitud de entrada con kolo-braid/join/v0, el welcome con kolo-braid/welcome/v0 y el cuerpo del helper kv con kolo-braid/kv/v0. kolo-braid no añade ninguna firma propia: kolo-log firma cada entrada.
| Tipo | Cuerpo |
|---|---|
| 0 genesis | etiqueta de app, regla de quórum, MaxMembers, MaxSettlers, MinSettlers, MaxBody, CheckpointEvery y, para un sucesor, el grupo antiguo, la posición, el digest de contenido y el número de seeds |
| 1 data | bytes de la aplicación, como mucho MaxBody |
| 2 add member | clave, ID del log del strand, roles, cabecera de log firmada |
| 3 remove member | clave |
| 4 settlers | regla de quórum y claves, en orden estrictamente creciente |
| 5 evidence | clave, ID del log del strand, dos registros o heads firmados de kolo-log |
| 6 pulse | configuración, pivote de activación, declaración de digest opcional, disponibilidad opcional |
| 7 seed | pares de la vista de un braid sucesor |
El cuerpo kv es, en kolo-codec, la cadena kolo-braid/kv/v0, un uvarint de operación (1 put, 2 delete) y luego la clave y el valor como bytes, con el valor vacío para un delete.
Un cuerpo de devices es, en kolo-codec, la cadena kolo-braid/devices/v0, un uvarint de operación (1 certificado, 2 revocación) y el objeto como bytes, y luego, solo en una revocación, un bool y el certificado al que apunta como bytes. La prueba en los datos de una solicitud de entrada es la cadena kolo-braid/devices/proof/v0, el certificado como bytes, la firma de 64 bytes y los datos de la aplicación como bytes.
Referencia de la API
La referencia de la API se genera a partir del código Go y está en 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
)Variables
var (
// ErrClosed is returned by a call on a closed braid.
ErrClosed = errors.New("kolobraid: closed")
// ErrInvalidArgument is returned for a nil or out of range argument.
ErrInvalidArgument = errors.New("kolobraid: invalid argument")
// ErrInvalidConfig is returned for a GroupConfig outside its ranges.
ErrInvalidConfig = errors.New("kolobraid: invalid group config")
// ErrNotMember is returned when the caller's key is not an active member.
ErrNotMember = errors.New("kolobraid: not an active member")
// ErrNotAdmin is returned when the caller's key is not an admin.
ErrNotAdmin = errors.New("kolobraid: not an admin")
// ErrRemoved is returned when the caller's strand was removed from the braid.
ErrRemoved = errors.New("kolobraid: member removed")
// ErrTooLarge is returned for a value over its bound.
ErrTooLarge = errors.New("kolobraid: value too large")
// ErrRejected is wrapped by the error that Reject returns.
ErrRejected = errors.New("kolobraid: entry rejected")
// ErrViewLimit is returned by a Tx call over a per-entry bound.
ErrViewLimit = errors.New("kolobraid: view limit exceeded")
// ErrTxDone is returned by a Tx used after apply returned.
ErrTxDone = errors.New("kolobraid: transaction done")
// ErrNotFound is returned for a key or entry that does not exist.
ErrNotFound = errors.New("kolobraid: not found")
// ErrHalted is returned when apply failed on this peer and nothing more is applied.
ErrHalted = errors.New("kolobraid: view halted")
// ErrDiverged is returned when this peer's running digest differs from one that a quorum of seats claimed.
ErrDiverged = errors.New("kolobraid: view diverged from a certified digest")
// ErrErased is returned when an entry the braid needs was erased from the own strand.
ErrErased = errors.New("kolobraid: strand entry erased")
// ErrEquivocation is returned when a writer signed two histories of its strand.
ErrEquivocation = errors.New("kolobraid: writer signed two histories")
// ErrWrongApp is returned when an app tag differs from the genesis tag.
ErrWrongApp = errors.New("kolobraid: wrong app tag")
// ErrWrongGroup is returned for an entry or message of another group.
ErrWrongGroup = errors.New("kolobraid: wrong group")
// ErrCorrupt is returned for stored data that does not decode or verify.
ErrCorrupt = errors.New("kolobraid: corrupt data")
// ErrProtocol is returned for a stream message that breaks the protocol.
ErrProtocol = errors.New("kolobraid: protocol violation")
// ErrUnconfirmed is returned when the own strand is not yet confirmed and the call's context ended.
ErrUnconfirmed = errors.New("kolobraid: own strand not confirmed")
// ErrStrandLost is returned when a history of the own strand conflicts with the local one.
ErrStrandLost = errors.New("kolobraid: own strand lost")
// ErrBadSeed is returned when the seed entries of a successor braid do not match their content digest.
ErrBadSeed = errors.New("kolobraid: seed does not match its digest")
// ErrReorged is returned by Entries when a position it already yielded changed.
ErrReorged = errors.New("kolobraid: order changed")
// ErrKnownStrand is returned by Admit for a strand log ID that is already used or known.
ErrKnownStrand = errors.New("kolobraid: strand already known")
// ErrGroupFull is returned by CheckAdmit when the group already has MaxMembers active members.
ErrGroupFull = errors.New("kolobraid: group full")
// ErrActiveKey is returned by Admit for a key that is already an active member.
ErrActiveKey = errors.New("kolobraid: key already active")
// ErrMalformed is returned by a decoder for bytes that break a format rule or are not canonical.
ErrMalformed = errors.New("kolobraid: malformed encoding")
)Funciones
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.
Paquete 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.
Paquete 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
)Variables
var (
// ErrTooManyDevices is returned by Admit when Options.MaxDevices is set and the person already has that many devices.
ErrTooManyDevices = errors.New("kolobraid: too many devices of this person in the group")
// ErrNotProven is returned by Admit and Record when the certificate or the proof of the joiner does not hold.
ErrNotProven = errors.New("kolobraid: device certificate not proven")
// ErrUnknownPerson is returned by Admit when no admin has anchored a device of the person in the group.
ErrUnknownPerson = errors.New("kolobraid: person has no anchored device in the group")
// ErrUnknownDevice is returned by Verify for a device without a stored certificate of the person.
ErrUnknownDevice = errors.New("kolobraid: no certificate for this device")
// ErrNotRecorded is returned when the roster applied or rejected the record without holding it anchored, or when the caller's
// context ended first; in that case the entry may still apply later, anchored or not, and nothing else was written.
ErrNotRecorded = errors.New("kolobraid: the roster did not take the record")
// ErrNotAdmitted is returned by Admit when the AddMember entry was written but the group did not take the member (it is void,
// for example in a full group), or when the caller's context ended first, in which case the entry may still apply later:
// remove the joiner with RemoveMember if no welcome reaches it.
ErrNotAdmitted = errors.New("kolobraid: the group did not take the member")
)Funciones
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.
Paquete 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.
Funciones
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.
Conviene saber
Valores por defecto
Fijados por la entrada genesis (GroupConfig); un campo a cero toma el valor por defecto y un valor fuera de su rango devuelve ErrInvalidConfig:
| Campo | Por defecto | Por qué |
|---|---|---|
Quorum | Majority, o TwoThirds | fallos por caída; TwoThirds cuando un dispositivo settler puede quedar comprometido |
MaxMembers | 64, rango de 2 a 1024 | el presupuesto de peers por defecto de un nodo |
MaxSettlers | 7 o MaxMembers si es menor, rango de 1 a 64 | con Majority se toleran entonces 3 desconectados |
MinSettlers | 4 o MaxSettlers si es menor, rango de 1 a MaxSettlers | se toleran un settler desconectado y uno que firma dos historiales |
MaxBody | 1 MiB, rango de 1 KiB a 3 MiB | el límite de valor de la vista |
CheckpointEvery | 1024 posiciones asentadas, rango de 64 a 2^20 | una divergencia se detecta dentro de esas posiciones |
Locales a un peer (Limits); un valor fuera de su rango devuelve ErrInvalidArgument:
| Campo | Por defecto |
|---|---|
MaxTail | 2048: una reorganización vuelve a aplicar como mucho esas entradas |
MaxPendingBytes | 16 MiB de entradas que esperan a una anterior; un strand guarda como máximo MaxPendingBytes / MaxMembers de ellas (una entrada siempre cabe) |
MaxForks | 4, rango de 1 a 64: los segundos historiales de un strand que guarda un peer; las entradas del siguiente se rechazan y ya no se piden |
MaxPullAhead | MaxTail |
PulseGap | 500 ms |
PivotWait | 3 s |
AnnounceGap | 100 ms |
ConfirmWait | 10 s |
MaxEvents | 1024 |
Seguridad
- kolo-log firma y cifra cada entrada; kolo-braid no añade ninguna firma propia. Cada head, registro, prueba y entrada de un peer se verifica, y un mensaje mal formado, por encima de su límite, de otro grupo, versión o tipo, con bytes de sobra o que no se verifica cierra la conexión, igual que una petición sin respuesta en 60 s.
- La membresía se comprueba en la posición de cada entrada en el orden, así que todos los peers la deciden igual. Un strand se sigue bajo la clave de la entrada AddMember que el orden hace efectiva, nunca bajo la clave de una nula.
- Una prueba solo cuenta cuando la clave que firmó los dos objetos es la clave del strand que nombran.
- Una clave que no es de un miembro, de un settler ni de un pin no recibe nada de kolo-sync, de sus mensajes solo se leen los ANNOUNCE más allá de su prefijo, y su conexión se cierra cuando lleva 60 s desconocida.
ServeConnconfía enConn.RemotePublicKey: pasa solo conexiones cuya clave se haya demostrado en un handshake, como un*kolosecure.Conn.- El mapa de
kvno tiene control de acceso: cualquier miembro activo escribe cualquier clave. - Una persona solo cuenta para
roster.Admitcuando un admin registró un certificado suyo, así que un miembro simple no puede inventarse una. A partir de ahí,roster.Admitdeja entrar a cada dispositivo posterior que pruebe un certificado válido, sin límite de frecuencia: las plazas del grupo yMaxCertsPerPersonson los únicos límites. Los certificados emitidos por aprobadores no pueden llenar el registro, porquePersonCertReservereserva 128 de los 1024 huecos para la clave de persona. devices.Store.Verifycomprueba un dispositivo para la persona que le pasas. Fija la persona en tu propio estado, nunca la tomes de un certificado.- Dos copias en marcha de un mismo directorio de datos escriben las dos antes de que una vea a la otra: en un settler eso detiene el asentamiento, y con 3 o 5 settlers y Majority puede dividir los prefijos asentados.
Estado
Beta y experimental, como toda biblioteca de Kolo en v0.x: la API puede cambiar antes de v1.0.0.
- Hecho: los strands, el orden con su prefijo asentado y su cola tentativa, el contrato de apply y sus comprobaciones, la membresía y la admisión, el asentamiento con configuraciones y braids sucesores, la sincronización por conexiones directas y a través de un relay, el helper kv y el paquete devices.
- Probado: tests unitarios, de propiedades y fuzz, comprobación de modelos del asentamiento y de la membresía en ámbitos acotados (
scripts/modelcheck.sh), que solo cubren los tamaños que recorren y no son una prueba para cualquier tamaño, y escenarios con varios procesos en un Mac, solo en 127.0.0.1. Las compilaciones para Linux y Windows pasaron vet, no se ejecutaron. - El asentamiento guarda una marca de ronda por settler y por ronda de la configuración de settlers actual, hasta que la configuración cambia: 16 bytes en memoria y una clave de unos 40 bytes en disco, escrita una vez. Un braid que asienta todo el día con 4 settlers y el
PulseGappor defecto puede sumar hasta unos 1,4 millones al día, unos 22 MB de memoria y 55 MB de disco; con 64 settlers, 16 veces más, y más con unPulseGapmás corto (hasta 50 veces con 10 ms). Son cotas superiores; el crecimiento de los slices añade hasta una cuarta parte a la cifra de memoria. Son lo que permite que un pulso que llega tarde obtenga su ronda exacta, y un cambio de la configuración de settlers las elimina.
Errores
| Error | Mensaje |
|---|---|
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 |
Comprueba los errores con errors.Is. Los mensajes de error propios de la biblioteca empiezan por kolobraid:.
Referencias
- Keidar, Kokoris-Kogias, Naor and Spiegelman, All you need is DAG, PODC 2021.
- Toma: el orden del historial causal de los líderes confirmados en un DAG por rondas.
- No implementa: una capa de difusión fiable. Un asiento que equivoca detiene el asentamiento en su lugar.
- Spiegelman, Giridharan, Sonnino and Kokoris-Kogias, Bullshark: DAG BFT protocols made practical, CCS 2022.
- Toma: líderes en rondas alternas.
- No implementa: nada.
- Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, 1978.
- Toma: la relación happened-before.
- No implementa: los relojes 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.
- Toma: relojes vectoriales derivados de los enlaces, nunca enviados.
- No implementa: nada.
- Kahn, Topological sorting of large networks, Communications of the ACM, 1962.
- Toma: orden topológico con desempate determinista.
- No implementa: nada.
- Merkle, A digital signature based on a conventional encryption function, CRYPTO '87.
- Toma: cadenas enlazadas por hash y el DAG de Merkle.
- No implementa: nada.
- Kleppmann and Howard, Byzantine eventual consistency and the fundamental limits of peer-to-peer databases, arXiv:2012.00472, 2020.
- Toma: la equivocación como prueba.
- No 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.
- Toma: la clase de difusión con orden total, y la intersección de quórums.
- No 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.
- Toma: la reconfiguración como comandos del log, y los miembros nuevos que se ponen al día antes de contar.
- No 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.
- Toma: ejecución tentativa, retroceso y confirmación.
- No implementa: nada.
- Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys, 1990.
- Toma: la máquina de estados determinista alimentada por un orden acordado.
- No implementa: nada.
- Dennis and Van Horn, Programming semantics for multiprogrammed computations, Communications of the ACM, 1966, and RFC 2693, SPKI Certificate Theory (Experimental, septiembre de 1999).
- Toma: la lista de capacidades, y la autorización de un salto.
- No implementa: las cadenas de delegación.
- RFC 9162, Certificate Transparency Version 2.0 (Experimental, December 2021) and RFC 8032, Edwards-Curve Digital Signature Algorithm (EdDSA) (Informational, enero de 2017).
- Toma: los strands firmados y enlazados por hash y Ed25519ctx, a través de kolo-log y kolo-id.
- No implementa: nada.
- RFC 7693, The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC) (Informational, noviembre de 2015).
- Toma: BLAKE2b-256 para cada hash.
- No implementa: nada.
- ITU-T G.114, One-way transmission time (05/2003, en vigor).
- Toma: 150 ms y 400 ms de retardo en un sentido, para
PivotWait. - No implementa: nada.
- Toma: 150 ms y 400 ms de retardo en un sentido, para
- Unos 100 ms, el límite habitual para que una interfaz se sienta inmediata.
- Toma: un presupuesto de entrada de 50 ms, la mitad, para el
MaxTailpor defecto. - No implementa: nada.
- Toma: un presupuesto de entrada de 50 ms, la mitad, para el
- Kulkarni, Demirbas, Madappa, Avva and Leone, Logical physical clocks, OPODIS 2014.
- Toma: nada.
- No implementa: todo. Se consideró y no se usó, porque una entrada no tiene campo de tiempo.