kolo docsbeta

kolo-sync

Copies a signed kolo-log log from one peer to another, pull only, or fetches some of its entries without a replica.

On this page

kolo-sync keeps a replica of someone's kolo-log log up to date from any peer that holds a copy, by the fetch-and-verify model of Certificate Transparency 2.0 (RFC 9162): heads, consistency proofs and inclusion proofs, checked against the owner's signatures only. A Server offers the logs the application chooses and asks it which peer may pull which log. Pull opens one stream per log on a connection, checks the peer's signed head, fetches the missing entries with consistency proofs and grows a kolo-store replica, which verifies every entry before it stores it. Delete markers follow, and so do entry keys for the peers allowed to read them. Fetch gets a range of entries on its own, each checked with its inclusion proof against a signed head, to read part of a log without keeping it. It takes a connection you already have and never finds or dials peers. It works over direct and relayed connections: every call takes a Conn, which a kolo-secure connection and a kolo-swarm peer link, direct or through a relay, both satisfy. See Replicas.

All steps

A pull between two peers

The puller asks and checks; the server only answers. Nothing is stored until it is verified.

  1. The puller opens a stream on its kolo-secure connection and sends HEAD_REQ with the owner's key and the log ID.
  2. The server asks its authorize function about this peer and this log. A log it does not offer and a peer with no access get the same not-found error. Otherwise it answers HEAD: the signed head and the log header.
  3. The puller checks the head's signature. If it already has an older head, PROOF_REQ asks for a consistency proof that the new head extends it.
  4. ENTRIES_REQ asks for the missing range. Answers hold at most 4 MiB, and Replica.Update checks every record and proof before it stores anything.
  5. STATE_REQ asks for delete markers and keys. The puller checks and applies the markers, then adds the keys.
  6. The puller closes the stream. The server never writes to the puller: kolo-sync is pull only.

Install

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

Builds without cgo.

Quick start

Alice writes a log of two entries and offers it to bob only. Bob connects on loopback, fetches the signed log header, opens a replica and pulls. Then he fetches one entry without a replica, checked against alice's signed head.

main.go
package main

import (
	"context"
	"crypto/ed25519"
	"fmt"
	"log"
	"time"

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

func main() {
	ctx, cancel := context.WithTimeout(context.Background(), 30*time.Second)
	defer cancel()
	alice, err := koloid.Generate()
	check(err)
	bob, err := koloid.Generate()
	check(err)

	// Alice writes a log and offers it, with its entry keys, to bob only.
	as := kolostore.New(kolostore.NewMemory())
	defer as.Close()
	l, err := as.Create(alice)
	check(err)
	_, err = l.Append([]byte("hello from alice"))
	check(err)
	_, err = l.Append([]byte("second entry"))
	check(err)
	srv := kolosync.NewServer(func(peer, _ ed25519.PublicKey, _ kololog.LogID) kolosync.Access {
		if peer.Equal(bob.PublicKey()) {
			return kolosync.Keys
		}
		return kolosync.NoAccess
	})
	check(srv.Offer(l))
	ln, err := kolosecure.Listen(ctx, "127.0.0.1:0", alice, nil)
	check(err)
	defer ln.Close()
	go func() {
		conn, err := ln.Accept(ctx)
		if err != nil {
			return
		}
		srv.Serve(ctx, conn)
	}()

	// Bob knows alice's key and the log ID, and keeps a replica in his own store.
	conn, err := kolosecure.Dial(ctx, ln.Addr().String(), bob, alice.PublicKey(), nil)
	check(err)
	defer conn.Close()
	bs := kolostore.New(kolostore.NewMemory())
	defer bs.Close()
	header, err := kolosync.FetchHeader(ctx, conn, alice.PublicKey(), l.ID())
	check(err)
	rep, err := bs.OpenReplica(alice.PublicKey(), l.ID(), header)
	check(err)
	check(kolosync.Pull(ctx, conn, rep))
	v, err := rep.Get(0)
	check(err)
	fmt.Printf("bob read %q from %d entries\n", v, rep.Len())

	// Without a replica, bob checks one entry against alice's signed head.
	h, err := kolosync.FetchHead(ctx, conn, alice.PublicKey(), l.ID())
	check(err)
	got, err := kolosync.Fetch(ctx, conn, h, 1, 1)
	check(err)
	fmt.Printf("bob fetched %q at index %d\n", got[0].Data, got[0].Index)
}

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

It prints:

Text
bob read "hello from alice" from 2 entries
bob fetched "second entry" at index 1

A real application keeps its stores on disk with kolostore.OpenPebble.

API reference

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

Package kolosync · github.com/ciranda-dev/kolo-sync · v0.1.0

Package kolosync replicates kolo-log logs between two peers, pull only, over any authenticated Conn: a kolo-secure connection or a kolo-swarm link, direct or relayed.

A Server offers logs, and authorizes each peer per log. Pull opens one stream per log, verifies the peer's signed head, fetches the missing range with consistency proofs, and grows a kolo-store Replica, which verifies every entry before it stores it. Delete markers and, for authorized peers, entry keys follow. Fetch gets a range of entries without a replica, each checked with its inclusion proof against a head the client trusts; FetchWithKeys opens them with keys the client holds, which FetchKeys gets from a peer with Keys access, so a client can read from a peer that holds ciphertext only. Many logs share one connection.

Experimental: the API may change before v1.0.0.

Constants

const (
	// DefaultInFlight is PullOptions.InFlight when it is 0.
	DefaultInFlight = 3
	// MaxInFlight is the largest PullOptions.InFlight.
	MaxInFlight = 8
)
const (
	// DefaultMaxTotalStreams is the default ServerOptions.MaxTotalStreams: 16 connections each serving MaxStreams streams.
	DefaultMaxTotalStreams = 16 * MaxStreams
	// DefaultMaxAnswerBytes is the default ServerOptions.MaxAnswerBytes, a quarter of kolo-transport's DefaultMaxMemory (1 GiB),
	// which leaves the rest of that budget to the connections themselves.
	DefaultMaxAnswerBytes = 256 << 20
)
const (
	// MaxMessageSize is the largest message, length prefix excluded, that a peer sends or accepts.
	MaxMessageSize = 4 << 20
	// MaxStreams is how many streams Serve handles at once per connection; more are answered busy.
	MaxStreams = 16
	// Timeout bounds opening a stream, the wait for the next request, and the start of each message read or write.
	// A message of n bytes may then take another n at MinRate, so a slow but moving 4 MiB answer is not cut off.
	Timeout = 60 * time.Second
	// MinRate is the slowest average speed, in bytes a second, at which a message may be read or written.
	MinRate = 16 << 10
)

Variables

var (
	// ErrInvalidArgument means a nil connection, replica, source or key, a key of the wrong size, a zero head,
	// a Fetch, FetchWithKeys or FetchKeys range that is empty or past the head (wrapping kololog.ErrOutOfRange),
	// or a PullOptions.KeysFrom past the replica's length.
	ErrInvalidArgument = errors.New("kolosync: invalid argument")
	// ErrNotFound means the peer does not serve the log to us: it does not have it, did not offer it, or did not authorize us.
	ErrNotFound = errors.New("kolosync: log not found")
	// ErrDiverged means the owner signed two histories: the peer's signed head or record conflicts with ours or with the head
	// Fetch, FetchWithKeys or FetchKeys checks against. Neither log was changed.
	ErrDiverged = errors.New("kolosync: logs diverged")
	// ErrInvalid means the peer sent a head, proof, entry, marker or key that does not verify; a kolo-log error is wrapped too.
	ErrInvalid = errors.New("kolosync: peer sent data that does not verify")
	// ErrProtocol means a malformed, truncated or unexpected message, or another protocol version.
	ErrProtocol = errors.New("kolosync: protocol error")
	// ErrTooLarge means a message over MaxMessageSize, or an entry too large to fit in one.
	ErrTooLarge = errors.New("kolosync: message too large")
	// ErrBehind means the peer's head has fewer entries than the head Fetch, FetchWithKeys or FetchKeys checks against,
	// or, for PullWith with NoMarkers, than the head the replica is filling toward (after ErrMarked); no entry or key is added.
	ErrBehind = errors.New("kolosync: peer is behind the head")
	// ErrKeyMismatch, in Fetched.Err, means a key given to FetchWithKeys does not match its entry's record.
	ErrKeyMismatch = errors.New("kolosync: held key does not match its record")
	// ErrBusy means the peer refused the stream or an answer (MaxStreams, ServerOptions) or could not read its log, or another Pull of the replica is running.
	ErrBusy = errors.New("kolosync: peer busy")
	// ErrMarked means the peer serves a deleted entry to a PullWith with NoMarkers; the replica then holds
	// only the entries before it, so its Len is that entry's index.
	ErrMarked = errors.New("kolosync: peer serves a deleted entry")
	// ErrTimeout means a message read or write took longer than Timeout.
	ErrTimeout = errors.New("kolosync: timeout")
)

Functions

func FetchHead

func FetchHead(ctx context.Context, conn Conn, owner ed25519.PublicKey, logID kololog.LogID) (kololog.VerifiedHead, error)

FetchHead returns the signed head of the log logID that the peer on conn serves, verified against owner.

func FetchHeader

func FetchHeader(ctx context.Context, conn Conn, owner ed25519.PublicKey, logID kololog.LogID) ([]byte, error)

FetchHeader returns the signed header of the log logID that the peer on conn serves, checked against owner, for opening a new replica with kolostore.Store.OpenReplica.

func FetchKeys

func FetchKeys(ctx context.Context, conn Conn, h kololog.VerifiedHead, start, end uint64) ([]kololog.EntryKey, error)

FetchKeys gets the entry keys of the entries start to end, end included, from a peer with Keys access, without their ciphertexts; element i is the key of entry start+i, or nil where the peer gave none.

func Pull

func Pull(ctx context.Context, conn Conn, rep *kolostore.Replica) error

Pull brings rep up to date with the copy of its log that the peer on conn serves, then applies the peer's delete markers and, if the peer gives them, the keys rep lacks; a key other than one rep holds is ErrInvalid. Only rep's Update, ApplyDelete and AddKey store anything, and each verifies first. A second Pull of the same replica while one runs returns ErrBusy; pulls of different replicas may run at once on one connection.

func PullCiphertext

func PullCiphertext(ctx context.Context, conn Conn, rep *kolostore.Replica) error

PullCiphertext is Pull for a peer that must never hold entry keys: it never asks for them, never calls AddKey, and an answer that carries a key anyway is ErrProtocol, with nothing from it stored.

Types

type Access

type Access int

Access is what a peer may pull from one offered log.

const (
	// NoAccess gives the peer the same answer as a log we do not have.
	NoAccess Access = iota
	// Ciphertext gives records, proofs, ciphertexts and delete markers, but no entry keys.
	Ciphertext
	// Keys gives everything Ciphertext gives, and the entry keys.
	Keys
)

type Conn

type Conn interface {
	RemotePublicKey() ed25519.PublicKey
	OpenStream(ctx context.Context) (*kolotransport.Stream, error)
	AcceptStream(ctx context.Context) (*kolotransport.Stream, error)
}

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

type Fetched

type Fetched struct {
	Index uint64
	Data  []byte // the entry's value, as kololog.Log.Get returns it; nil when Err is set
	// Err is kololog.ErrDeleted, kololog.ErrKeyUnavailable, ErrKeyMismatch or nil (see the README).
	Err error
}

Fetched is one entry that Fetch got from the peer and verified.

func Fetch
func Fetch(ctx context.Context, conn Conn, h kololog.VerifiedHead, start, end uint64) ([]Fetched, error)

Fetch gets the entries start to end, end included, of the log of h from the peer on conn, without a replica. Each entry is checked with its inclusion proof in the tree of h's size, so the peer must hold h's entries: a peer with a smaller head is ErrBehind, one with another root at h's size ErrDiverged.

func FetchWithKeys
func FetchWithKeys(ctx context.Context, conn Conn, h kololog.VerifiedHead, start, end uint64,
	keys func(index uint64) (kololog.EntryKey, error)) ([]Fetched, error)

FetchWithKeys is Fetch for a caller that holds entry keys, such as one reading from a peer that serves ciphertext only; keys returns a copy of the key held for an entry that came without one (see the README). keys is asked after the stream is closed, so its use shows only in how long FetchWithKeys takes to return.

type PullMeter

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

PullMeter collects the statistics of a pull while it runs. Its zero value is ready to use: pass it in PullOptions.Meter and call Stats from any goroutine. A meter measures one pull at a time: starting a pull with a meter another pull is using is ErrInvalidArgument, and one that starts after the last has ended resets it.

func (PullMeter) Stats
func (m *PullMeter) Stats() PullStats

Stats returns the statistics so far, or the whole pull's once it has ended; it is safe to call at any time.

type PullOptions

type PullOptions struct {
	// NoMarkers makes the pull neither request nor store delete markers: a chunk is stored only up
	// to its first deleted entry (ErrMarked), and STATE markers are ignored.
	NoMarkers bool
	// KeysFrom is the first index the caller may hold without its key; the pull scans and asks for
	// keys only from there.
	KeysFrom uint64
	// InFlight is the most requests for entries the pull has waiting at once, 1 to MaxInFlight. A peer that streams is
	// sent credit in requests of 2 MiB and keeps from 2 up to InFlight of them waiting, as many as twice the measured
	// round trip times the speed asks for; 0 is MaxInFlight, and 1 asks again only when the credit is used up.
	// For a peer that does not stream, such as v0.1.7, it is how many answers are asked for before the first is
	// stored: 0 is DefaultInFlight, and 1 asks for each after the one before is stored. The pull holds at most 6 MiB
	// of answers not yet stored whatever it is.
	InFlight int
	// Meter, if not nil, collects the statistics of the pull while it runs; see PullMeter.
	Meter *PullMeter
}

PullOptions changes how PullWith pulls; the zero value pulls as Pull does.

type PullResult

type PullResult struct {
	// KeysFrom is the first index still held without its key after the pull.
	KeysFrom uint64
	// Stats is how the pull went, also when it failed.
	Stats PullStats
}

PullResult is what PullWith reports.

func PullWith
func PullWith(ctx context.Context, conn Conn, rep *kolostore.Replica, opts *PullOptions) (PullResult, error)

PullWith is Pull with opts (nil for none). On an error the result's KeysFrom is opts.KeysFrom, and a KeysFrom past rep.Len() is ErrInvalidArgument.

type PullStats

type PullStats struct {
	// Streamed is true when the peer served the entries as a stream (STREAM_REQ) and false when the pull asked for them one
	// answer at a time, as for a peer that predates streaming.
	Streamed bool
	// Elapsed is the time since the pull started, or its whole length once it has ended.
	Elapsed time.Duration
	// Bytes, Entries and Answers count the ENTRIES answers read: their message bytes, entries and messages.
	Bytes   uint64
	Entries uint64
	Answers uint64
	// Requests counts the requests for entries sent: ENTRIES_REQ, or STREAM_REQ and CREDIT_REQ.
	Requests uint64
	// ReaderWait is the time the reader spent waiting for the bytes of answers, not counting waits for memory.
	ReaderWait time.Duration
	// CommitBusy is the time the goroutine that stores the answers spent verifying and storing them, and CommitIdle the
	// time it spent waiting for an answer.
	CommitBusy time.Duration
	CommitIdle time.Duration
	// FirstByteMin, FirstByteAvg and FirstByteMax are the time from writing the request for entries to reading the
	// first bytes of its answer. A request sent while others wait includes the time of the answers before it; a streamed
	// pull has one sample for each fill: its STREAM_REQ.
	FirstByteMin time.Duration
	FirstByteAvg time.Duration
	FirstByteMax time.Duration
	// InFlightMax and InFlightAvg are the most requests for entries asked for and not yet answered, and their average over
	// time. For a streamed pull a request is 2 MiB of credit.
	InFlightMax int
	InFlightAvg float64
	// InFlightBlocked counts the times the limit on requests in flight, PullOptions.InFlight, held a request back.
	InFlightBlocked uint64
	// MemoryBlocked counts the times the reader had to wait for room under the 6 MiB of answers a pull holds, and
	// MemoryWait is the time it waited. HeldMax is the most bytes of answers held at once.
	MemoryBlocked uint64
	MemoryWait    time.Duration
	HeldMax       int
}

PullStats says where the time of a pull went and how full it kept the link. All durations are wall time.

func (PullStats) AvgAnswer
func (s PullStats) AvgAnswer() uint64

AvgAnswer returns the average size in bytes of an ENTRIES answer, 0 if none was read.

type Server

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

Server serves the logs the application offers to the peers it authorizes; it is safe for concurrent use. A log is named by its owner's key and its log ID, so two owners' logs with one ID are two logs.

func NewServer
func NewServer(authorize func(peer, owner ed25519.PublicKey, logID kololog.LogID) Access) *Server

NewServer returns a Server with no offered logs. authorize is asked on every request, for any owner and log ID; nil, a panic or any other value than Ciphertext or Keys means NoAccess.

func NewServerWith
func NewServerWith(authorize func(peer, owner ed25519.PublicKey, logID kololog.LogID) Access, opts *ServerOptions) (*Server, error)

NewServerWith is NewServer with the server-wide limits of opts; nil is all defaults. A negative limit, or a MaxAnswerBytes below 2 * MaxMessageSize, is ErrInvalidArgument.

func (Server) Offer
func (s *Server) Offer(src Source) error

Offer makes src available under its owner's key and log ID, replacing an earlier source with both the same. src's header must be signed by its owner and name src's log ID; past that, Offer trusts src to serve that log.

func (Server) Serve
func (s *Server) Serve(ctx context.Context, conn Conn) error

Serve answers the streams the peer opens on conn, for Pull, PullCiphertext, FetchHeader, FetchHead, Fetch, FetchWithKeys and FetchKeys, until ctx is done or conn ends, then waits for them. It must be the only caller of conn.AcceptStream.

func (Server) Stats
func (s *Server) Stats() ServerStats

Stats returns the server's totals; it is safe to call at any time.

func (Server) Withdraw
func (s *Server) Withdraw(owner ed25519.PublicKey, logID kololog.LogID)

Withdraw stops offering the log logID of owner; requests for it then get the answer of a missing log.

type ServerOptions

type ServerOptions struct {
	// MaxTotalStreams is the most streams served at once over all connections.
	MaxTotalStreams int
	// MaxAnswerBytes is the most memory the answers being built or written may hold at once; each answer counts twice its
	// size, the entries read from the log and the frame sent. At least 2 * MaxMessageSize, so one largest answer always fits.
	MaxAnswerBytes int64
}

ServerOptions are the limits a Server applies over all the connections it serves, on top of MaxStreams for each. A zero field is its default. A stream or an answer over a limit is answered busy, which a Pull or Fetch returns as ErrBusy.

type ServerStats

type ServerStats struct {
	BytesSent      uint64 // frame bytes written, every answer included
	ActiveStreams  int    // streams being served now, refused ones not included
	RefusedByLimit uint64 // streams and answers refused because MaxTotalStreams or MaxAnswerBytes was reached
	AnswerBytes    int64  // memory the answers being built or written hold now, counted as MaxAnswerBytes counts it
}

ServerStats are a Server's totals over all its connections.

type Source

type Source interface {
	ID() kololog.LogID
	Header() kololog.LogHeader
	Head() (kololog.Head, error)
	Record(index uint64) (kololog.Record, error)
	Entry(index uint64) (kololog.Entry, error)
	EntryInfo(index uint64) (kololog.EntryInfo, error)
	Key(index uint64) (kololog.EntryKey, error)
	InclusionProof(index, size uint64) (kololog.InclusionProof, error)
	ConsistencyProof(oldSize, newSize uint64) (kololog.ConsistencyProof, error)
}

Source is a log a Server can offer: a kolo-store Log or Replica, or a kolo-log Log or Replica.

Good to know

All steps

Fetching single entries

Fetch reads a few entries from any peer without copying the log. Each entry is checked against a head you already trust.

  1. The reader holds a verified head of size n, from FetchHead or an earlier pull. Fetch checks the range against it before it sends anything.
  2. HEAD_REQ gets the peer's head. A peer with a shorter log cannot prove these entries: Fetch returns ErrBehind, so ask another peer.
  3. FETCH_REQ asks for start to end, in the tree of size n.
  4. FETCH answers each entry with its record, its ciphertext or delete marker, its key when access allows, and an inclusion proof in that tree.
  5. OpenEntry checks the record and the proof against the trusted root, then decrypts. A deleted entry comes back as ErrDeleted.

Trust comes from the owner's signatures only, so any peer with a verified copy can serve it: a Source is a kolo-store or kolo-log *Log or *Replica, and a replica serves its last fully held head. A custom Source needs ID, Header, Head, Record, Entry, EntryInfo, Key, InclusionProof and ConsistencyProof. Offer keys the log by src.Header().LogKey and src.ID() and replaces an earlier source with both the same. It refuses a source whose header is not signed by that key or names another log ID (ErrInvalidArgument wrapping kololog.ErrBadLogHeader). After Withdraw, requests for the log get the answer of a missing log.

Pull checks everything against the owner key in the replica's header and returns nil when the peer is behind or even. A pull that stops in the middle leaves the replica a target, kept by kolo-store; the next pull fills up to it first, and returns nil from a peer whose head is below it. A key in a STATE answer for an entry the replica already holds with its key must be that key, or the pull fails with ErrInvalid. A pull with nothing new reads no ciphertext on either side: both ends use kolo-log's per-entry flags and read only the delete markers and keys they send or apply.

FetchHead returns the peer's signed head, verified against the owner key and log ID, for a client that holds no head yet. It is the head this peer holds, which may be older than the newest one. Fetch(ctx, conn, h, start, end) gets entries start to end, end included, against the head h the client trusts. Each Fetched has Index, Data and Err: nil, kololog.ErrDeleted for an entry with a verified delete marker, or kololog.ErrKeyUnavailable when the peer sent no key. Any other failure fails the whole call and returns no entries. A peer whose head is smaller than h gives ErrBehind; ask another peer. Fetch keeps the values of the range you asked for, so its memory is that range, at most one message more.

Direct and relayed connections

Every call takes a Conn: RemotePublicKey, OpenStream and AcceptStream, the only methods kolo-sync uses. A *kolosecure.Conn and a koloswarm.Conn satisfy it, so kolo-sync works over direct and relayed connections, and a relayed connection carries the sync exactly as a direct one. RemotePublicKey must return the key the peer proved in the end-to-end handshake. A relayed link proves it the same way, so authorize gets the same key as on a direct link. The peer-key checks and the wire format are unchanged.

A nil Conn, or one holding a nil pointer such as a nil *kolosecure.Conn, is ErrInvalidArgument. Serve refuses a Conn whose RemotePublicKey is not 32 bytes with ErrInvalidArgument before it accepts a stream.

Pulling without delete markers

PullWith(ctx, conn, rep, opts) is Pull with a *PullOptions and returns a PullResult. With nil or the zero value it pulls and sends exactly the messages Pull does. PullOptions has four fields; NoMarkers and KeysFrom are described here, InFlight below and Meter in Pull statistics.

  • NoMarkers: the pull neither requests nor stores delete markers, so a peer that deleted entries, or claims it did, cannot erase them from the replica. An ENTRIES answer is checked before anything is stored: at its first entry that carries a marker, only the entries before it go to Replica.Update, with one more PROOF request for that shorter prefix so the replica stays verified, and the pull returns ErrMarked naming that index. rep.Len() is then that index, and the replica fills toward that peer's head: pull the rest from a peer whose head is at least as large. A peer behind that head adds nothing and returns ErrBehind (Pull returns nil there). The marker is never decoded or checked, so a forged one stops the pull the same way. STATE markers are ignored, also bad or misplaced ones, and no STATE request asks for markers alone; the keys in STATE answers are checked and added as in Pull. A marker already in the replica stays.
  • KeysFrom: the first index the caller may hold without its key. The local scan for missing keys and the STATE requests for keys start there. With NoMarkers a pull then costs the new entries and the entries still without a key, not the whole log; without it the delete markers are still asked from index 0. A value past rep.Len() is ErrInvalidArgument.

PullResult.KeysFrom is the first index still held without its key after the pull (deleted entries are passed over), or rep.Len() when every entry has its key: keep it with the replica and give it to the next pull. On an error it is opts.KeysFrom, so the cursor never skips an entry. The wire format is unchanged.

A pull that tries the next peer when one serves a deleted entry or is behind the head the replica fills toward:

Go
func pullLive(ctx context.Context, peers []*kolosecure.Conn, rep *kolostore.Replica, keysFrom uint64) (uint64, error) {
	err := kolosync.ErrNotFound
	for _, conn := range peers {
		var res kolosync.PullResult
		res, err = kolosync.PullWith(ctx, conn, rep, &kolosync.PullOptions{NoMarkers: true, KeysFrom: keysFrom})
		if err == nil {
			return res.KeysFrom, nil
		}
		if !errors.Is(err, kolosync.ErrMarked) && !errors.Is(err, kolosync.ErrBehind) {
			return keysFrom, err
		}
		// rep holds the entries before the deleted one; the next peer goes on from rep.Len().
	}
	return keysFrom, err
}

Answers in flight

A pull asks for the entries in answers of about 1 MiB. Asking for one answer at a time sends the next request only when the first bytes of the answer before it arrive, so it moves about one answer, 1 MiB, for each round trip, whatever the link can carry: 10 MB/s at 100 ms. A pull of a peer of this version asks for the entries once and keeps the link full. Its first request for entries, STREAM_REQ, names where to start and gives credit in bytes; the peer then sends each answer, followed by the proof of where it ends, without waiting for another request, as long as the credit lasts, and the pull sends more credit (CREDIT_REQ) before it is used up. One goroutine reads the stream, and the caller's goroutine verifies and stores the answers in order with Replica.Update, so the replica only ever grows by verified answers, in order.

  • For a peer that streams, InFlight bounds the requests of credit, 2 MiB each, that wait at the peer: 1 to MaxInFlight (8), and 0 is MaxInFlight; any other value is ErrInvalidArgument. The pull keeps 2 of them waiting and more as it measures the round trip and the speed it reads at (twice the bandwidth-delay product, in requests), up to InFlight, so at most 16 MiB of answers are on their way. With 1 the pull asks again only after the credit before is used up.
  • A peer that does not stream answers STREAM_REQ with an error and closes the stream. The pull then opens another stream and asks one request and one proof for each answer, up to InFlight requests ahead (0 is DefaultInFlight, 3), at the cost of two round trips in each pull that has entries to get. A server streams only when it is asked to, so it also serves a pull that does not stream.
  • Answers that are already waiting when one is stored go into the same Update, one commit and one sync of the store, up to 4 MiB of answers; if it fails they are stored one at a time, so the entries stored before a bad answer, and the error, are the same as when each is stored alone.
  • A failure, a hostile answer or a cancel leaves the replica as it is after the last answer that was stored whole, and rep.Len() is where the next Pull resumes. A peer that stops sending in the middle of the credit is ErrTimeout.
  • A pull holds at most 6 MiB of answers that are not stored yet, whatever InFlight is. The credit that waits is the peer's answers on the wire and in the transport's windows, not in the pull's memory.

The window that kolo-transport gives a stream still bounds one stream to its window per round trip, so a pull reaches the smaller of that and the link: a stream window of 4 MiB is about 40 MB/s at 100 ms and 20 MB/s at 200 ms. Raising kolo-transport's window ceilings, MaxGrownStreamReceiveWindow and MaxGrownConnReceiveWindow, is how a pull goes faster than that (see kolo-transport). InFlight needs no change for it.

Pull statistics

PullResult.Stats says where the time of a PullWith went, also when it failed. For the numbers while it runs, give PullOptions.Meter a *PullMeter (its zero value is ready) and call Meter.Stats() from any goroutine. A meter measures one pull at a time: a pull that starts with a meter another pull is using returns ErrInvalidArgument.

  • Streamed: the peer streamed the entries; false for a peer that predates STREAM_REQ.
  • Elapsed, Bytes, Entries, Answers and Requests: the time of the pull, the ENTRIES answers read and the requests for entries sent.
  • ReaderWait, CommitBusy and CommitIdle: the time the reader waited for bytes, and the time the goroutine that verifies and stores was busy and idle.
  • FirstByteMin, FirstByteAvg and FirstByteMax: from writing a request for entries to the first bytes of its answer.
  • InFlightMax, InFlightAvg, InFlightBlocked, MemoryBlocked, MemoryWait and HeldMax: the requests waiting, the times InFlight or the 6 MiB held the pull back, and the most bytes of answers held.

CommitIdle and ReaderWait near Elapsed mean the pull waits for the peer or the network, not for this machine. CommitBusy near Elapsed means the machine verifies and stores as fast as it can. FirstByteMin far above the round trip means the peer is slow to read its log.

Reading from a pin that serves ciphertext only

A pinning peer holds a verified copy of a log and serves it with Ciphertext access, so it has no entry keys. Fetch against it returns each live entry with kololog.ErrKeyUnavailable. Use Fetch when the peer sends the keys (Keys access) or you only need to know which entries exist. Use FetchWithKeys when the keys are already with you and the peer serves ciphertext only, for example to read while the owner is offline.

The keys come from you, never from the pin. Get a head with FetchHead and the keys of the range with FetchKeys from the owner or another peer with Keys access, and keep them where your application keeps its state. Later, FetchWithKeys(ctx, conn, h, start, end, keys) is Fetch with a function keys(index) that returns the key you hold for an entry that came without one. Log.Key and Replica.Key fit as keys when you keep a log or a replica, and the function can read from a map or a file just as well. Both calls are checked against the head h, as Fetch is.

main.go
package main

import (
	"context"
	"crypto/ed25519"
	"errors"
	"fmt"
	"log"
	"time"

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

func main() {
	ctx, cancel := context.WithTimeout(context.Background(), 30*time.Second)
	defer cancel()
	alice, err := koloid.Generate()
	check(err)
	device, err := koloid.Generate() // another device of alice, with Keys access
	check(err)
	reader, err := koloid.Generate() // reads from the pin, with Ciphertext access
	check(err)

	// One server plays both parts here: it gives keys to the device and
	// ciphertext only to the reader, as a pin would.
	as := kolostore.New(kolostore.NewMemory())
	defer as.Close()
	l, err := as.Create(alice)
	check(err)
	_, err = l.Append([]byte("hello from alice"))
	check(err)
	_, err = l.Append([]byte("second entry"))
	check(err)
	srv := kolosync.NewServer(func(peer, _ ed25519.PublicKey, _ kololog.LogID) kolosync.Access {
		switch {
		case peer.Equal(device.PublicKey()):
			return kolosync.Keys
		case peer.Equal(reader.PublicKey()):
			return kolosync.Ciphertext
		}
		return kolosync.NoAccess
	})
	check(srv.Offer(l))
	ln, err := kolosecure.Listen(ctx, "127.0.0.1:0", alice, nil)
	check(err)
	defer ln.Close()
	go func() {
		for {
			conn, err := ln.Accept(ctx)
			if err != nil {
				return
			}
			go srv.Serve(ctx, conn)
		}
	}()

	// The device gets a head and the keys of both entries, and keeps them.
	dconn, err := kolosecure.Dial(ctx, ln.Addr().String(), device, alice.PublicKey(), nil)
	check(err)
	defer dconn.Close()
	h, err := kolosync.FetchHead(ctx, dconn, alice.PublicKey(), l.ID())
	check(err)
	keys, err := kolosync.FetchKeys(ctx, dconn, h, 0, 1)
	check(err)

	// The reader asks the pin. Fetch alone cannot open the entries.
	rconn, err := kolosecure.Dial(ctx, ln.Addr().String(), reader, alice.PublicKey(), nil)
	check(err)
	defer rconn.Close()
	got, err := kolosync.Fetch(ctx, rconn, h, 0, 1)
	check(err)
	fmt.Println("without keys:", errors.Is(got[0].Err, kololog.ErrKeyUnavailable))

	// FetchWithKeys opens them with the held keys, which never leave the reader.
	got, err = kolosync.FetchWithKeys(ctx, rconn, h, 0, 1, func(i uint64) (kololog.EntryKey, error) {
		return append(kololog.EntryKey(nil), keys[i]...), nil
	})
	check(err)
	for _, f := range got {
		if f.Err != nil { // for example kolosync.ErrKeyMismatch
			log.Fatal(f.Err)
		}
		fmt.Printf("with keys: %q at index %d\n", f.Data, f.Index)
	}
}

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

It prints:

Text
without keys: true
with keys: "hello from alice" at index 0
with keys: "second entry" at index 1

What stays on the client: the keys, and which of them it holds. The pin gets the same requests as for Fetch and needs no key material. keys is asked only after the last answer has arrived and the stream is closed, so neither the pace nor the end of the stream tells the pin whether you hold keys. FetchWithKeys clears each key after use, so keys returns a copy.

A nil or empty key, or an error wrapping kololog.ErrKeyUnavailable, means none is held and the entry is reported with kololog.ErrKeyUnavailable. The kololog.ErrOutOfRange of Log.Key and Replica.Key counts as none held, and their kololog.ErrDeleted reports the entry as deleted. A held key that does not match the entry's signed record is reported for that entry alone with ErrKeyMismatch, and the other entries are opened. Any other error from keys fails the call. Once ctx is done no more keys are asked, and on any error no entries are returned and the values already opened are cleared.

The time FetchWithKeys takes to return depends on the held keys: it opens the entries after the stream ends, so a peer that sees your next request on the same connection can tell from the delay whether you held keys and whether they matched. The same goes for what your application does next, such as stopping after a mismatch. Nothing on the wire changes with the keys. If that matters, open the next stream after a fixed delay, or on another connection.

FetchKeys(ctx, conn, h, start, end) returns one element per entry asked: element i is the key of entry start+i, or nil where the peer gave none (a deleted entry, a key it does not hold or no Keys access: these look the same). It does not check a key, because kolo-log has no check of a key without its ciphertext; FetchWithKeys does, against the signed record. Clear the keys when you are done.

Run one Serve per connection, as the only caller of conn.AcceptStream, and one Pull per replica at a time (a second one returns ErrBusy). Pulls of different replicas and many fetches may share a connection, each on its own stream, and both ends may serve and pull on one connection.

Limits

  • MaxMessageSize: 4 MiB per message, length prefix checked before allocating. An entry whose padded ciphertext does not fit in one message cannot be synced or fetched (ErrTooLarge), see Known limits.
  • MaxStreams: 16 streams served at once per connection, pull and fetch streams alike, the same as kolo-transport's default stream limit. More are answered busy, and the client gets ErrBusy.
  • ServerOptions.MaxTotalStreams: 256 streams served at once over all connections (DefaultMaxTotalStreams, 16 connections of MaxStreams). ServerOptions.MaxAnswerBytes: 256 MiB of answers being built or written over all connections (DefaultMaxAnswerBytes), at least 2 x MaxMessageSize; an answer counts twice its size. Set them with NewServerWith. A stream or an answer past either is answered busy, the client gets ErrBusy, and ServerStats.RefusedByLimit counts it.
  • Timeout: 60s for opening a stream, for the start of each message read or write and for the wait for the next request. A message of n bytes may take Timeout plus n at MinRate (16 KiB/s), so a full 4 MiB message is cut off only below 16 KiB/s. A silent peer holds a stream for at most Timeout; a client that waits too long gets ErrTimeout.
  • An answer to a request for entries is filled to about 1 MiB once it holds an entry; a larger entry goes alone, up to MaxMessageSize.
  • PullOptions.InFlight: from 1 to 8 (MaxInFlight); any other value is ErrInvalidArgument. For a peer that streams it is the most requests of credit, 2 MiB each, that wait (0 is 8); for an older peer, the answers in flight (0 is DefaultInFlight, 3). A pull holds at most 6 MiB of answers that are not stored yet, and one commit stores the answers that wait, up to 4 MiB.
  • Credit of a streamed pull: the peer holds at most 64 MiB of credit for one stream and refuses a request of more.
  • One STATE answer looks at most at 32768 entries (MaxMessageSize / 128), then stops early and the puller asks for the rest. It reads only the delete markers and keys it sends, never a ciphertext.
  • On the wire, heads, headers, records, markers and proofs are at most 4 KiB each, and an entry key is 0 or 32 bytes.
  • The limits are fixed constants, except the two of ServerOptions. Connections come from kolo-secure, so kolo-sync is IPv4 only.

Security

  • Entry keys travel only on the connection you give, never in an error or a log line. No error carries bytes a peer sent, only numbers such as sizes and indexes.
  • The peer's head is verified (signature under kolo-log/tree-head/v0, owner key, log ID) before any other message is read, and proofs are checked only against verified heads. kolo-sync signs nothing.
  • Each fetched chunk goes to Replica.Update, which checks every record signature, ciphertext hash, key commitment and the rebuilt root before it stores anything. Replica.AddKey checks a late key against the key commitment. On ErrInvalid the replica keeps what it held.
  • The delete markers of one STATE answer go to one Replica.ApplyDelete, in one commit, after every item of the answer is checked: a bad or misplaced marker, or any malformed item, applies none of them.
  • Fetch checks everything against the head h you give, never against the peer's word. Each entry goes through kololog.OpenEntry, which checks its inclusion proof in the tree of h's size, the record's signature and index, the ciphertext or delete marker and the key against its commitment before it decrypts. Each proof must be for the index asked.
  • ErrDiverged needs evidence: a head of a size we hold, or of h's size for Fetch, with another root, or an owner-signed record from the peer that differs from ours at our last held index. A bad proof without such evidence is ErrInvalid, since any peer can send one. Neither copy is changed.
  • The puller states what it holds by what it asks for and never sends its own head. The server never writes.
  • authorize runs before the offered logs are looked at, so a missing, an unoffered and an unauthorized log, and a log ID offered only under another owner, take one path and give the same bytes. A log that is stored but not offered is never read.
  • A server accepts only requests and a client only answers, checked before the fields. Another version, non-minimal varints or trailing bytes end the stream.

Known limits

  • Experimental. The API may change before v1.0.0.
  • Wire format version 1. A peer that speaks another version gets a protocol error.
  • Pull only: a peer cannot push a log to another.
  • An entry whose padded ciphertext is over MaxMessageSize cannot be synced or fetched, deleted or not, and the log does not sync past it. The server checks the record's size first and never reads such an entry.
  • A fork that starts after the entries we hold leaves no evidence: its proofs fail, and the pull returns ErrInvalid, not ErrDiverged.
  • Fetch cannot tell a peer without Keys access from one that does not hold the key or chose not to send it: all give kololog.ErrKeyUnavailable.
  • Heads have no timestamp, so a newer head is a larger one. To read the newest entries, get a newer head first with FetchHead or a Pull.
  • There is no JSON form of the wire format.

Errors

ErrorMessage
ErrBehindkolosync: peer is behind the head
ErrBusykolosync: peer busy
ErrDivergedkolosync: logs diverged
ErrInvalidkolosync: peer sent data that does not verify
ErrInvalidArgumentkolosync: invalid argument
ErrKeyMismatchkolosync: held key does not match its record
ErrMarkedkolosync: peer serves a deleted entry
ErrNotFoundkolosync: log not found
ErrProtocolkolosync: protocol error
ErrTimeoutkolosync: timeout
ErrTooLargekolosync: message too large

Test errors with errors.Is. ErrInvalid also wraps the kolo-log error (such as kololog.ErrBadEntry, kololog.ErrInvalidHead or kololog.ErrBadProof), ErrDiverged can wrap kololog.ErrDiverged, ErrInvalidArgument wraps kololog.ErrOutOfRange for a Fetch range that is empty or past the head, and an ErrTimeout on a message read or write wraps os.ErrDeadlineExceeded. ErrKeyMismatch comes in Fetched.Err and wraps kololog.ErrBadEntry. Once ctx is done, Pull, FetchHeader, FetchHead, Fetch, FetchWithKeys, FetchKeys and Serve return ctx.Err().

ErrMarked comes only from PullWith with NoMarkers: the peer serves a deleted entry, or one with a marker, where the replica needs a live one. The replica holds the entries before it, so rep.Len() is its index, which the error message also names; pull the rest from another peer whose head reaches that peer's head. PullWith with NoMarkers also returns ErrBehind when the peer's head has fewer entries than the head the replica fills toward, so no entry or key is added: ask another peer, or a later one.

References

  • RFC 9162, Certificate Transparency Version 2.0 (Experimental, December 2021).
    • Takes: signed tree heads (4.10), consistency proofs (2.1.4), inclusion proofs (2.1.3), get-sth (5.2), get-sth-consistency (5.3), get-entries (5.6) and the monitor that keeps a whole log (8.2).
    • Not implemented: HTTPS and JSON (kolo-codec messages on a kolo-secure stream instead) and get-proof-by-hash as a request, since a replica holds every entry and rebuilds the root.
  • RFC 6962, Certificate Transparency (Experimental, June 2013, obsoleted by RFC 9162).
    • Takes: get-entry-and-proof (4.8), an entry with its inclusion proof by index and tree size.
  • RFC 8032, Edwards-Curve Digital Signature Algorithm (EdDSA) (Informational, January 2017).
    • Takes: Ed25519ctx (5.1, 8.3), through the contexts of kolo-log.
    • Not implemented: kolo-sync signs nothing.
  • RFC 9113, HTTP/2 (Proposed Standard, June 2022).
    • Takes: the stream concurrency limit and refused streams (5.1.2, 6.5.2).
    • Not implemented: HTTP/2 itself.