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.
A pull between two peers
The puller asks and checks; the server only answers. Nothing is stored until it is verified.
- The puller opens a stream on its kolo-secure connection and sends HEAD_REQ with the owner's key and the log ID.
- 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.
- 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.
- 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.
- STATE_REQ asks for delete markers and keys. The puller checks and applies the markers, then adds the keys.
- 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-syncBuilds 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.
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:
bob read "hello from alice" from 2 entries
bob fetched "second entry" at index 1A 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 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) errorPull 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) errorPullCiphertext 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 intAccess 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() PullStatsStats 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() uint64AvgAnswer 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) *ServerNewServer 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) errorOffer 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) errorServe 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() ServerStatsStats 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
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.
- 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.
- HEAD_REQ gets the peer's head. A peer with a shorter log cannot prove these entries: Fetch returns ErrBehind, so ask another peer.
- FETCH_REQ asks for start to end, in the tree of size n.
- FETCH answers each entry with its record, its ciphertext or delete marker, its key when access allows, and an inclusion proof in that tree.
- 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 toReplica.Update, with one more PROOF request for that shorter prefix so the replica stays verified, and the pull returnsErrMarkednaming 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 returnsErrBehind(Pullreturns 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 inPull. 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. WithNoMarkersa 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 pastrep.Len()isErrInvalidArgument.
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:
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,
InFlightbounds the requests of credit, 2 MiB each, that wait at the peer: 1 toMaxInFlight(8), and 0 isMaxInFlight; any other value isErrInvalidArgument. 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 toInFlight, 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
InFlightrequests ahead (0 isDefaultInFlight, 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 nextPullresumes. A peer that stops sending in the middle of the credit isErrTimeout. - A pull holds at most 6 MiB of answers that are not stored yet, whatever
InFlightis. 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,AnswersandRequests: the time of the pull, the ENTRIES answers read and the requests for entries sent.ReaderWait,CommitBusyandCommitIdle: the time the reader waited for bytes, and the time the goroutine that verifies and stores was busy and idle.FirstByteMin,FirstByteAvgandFirstByteMax: from writing a request for entries to the first bytes of its answer.InFlightMax,InFlightAvg,InFlightBlocked,MemoryBlocked,MemoryWaitandHeldMax: the requests waiting, the timesInFlightor 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.
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:
without keys: true
with keys: "hello from alice" at index 0
with keys: "second entry" at index 1What 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 getsErrBusy.ServerOptions.MaxTotalStreams: 256 streams served at once over all connections (DefaultMaxTotalStreams, 16 connections ofMaxStreams).ServerOptions.MaxAnswerBytes: 256 MiB of answers being built or written over all connections (DefaultMaxAnswerBytes), at least 2 xMaxMessageSize; an answer counts twice its size. Set them withNewServerWith. A stream or an answer past either is answered busy, the client getsErrBusy, andServerStats.RefusedByLimitcounts 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 takeTimeoutplus n atMinRate(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 mostTimeout; a client that waits too long getsErrTimeout.- 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 isErrInvalidArgument. 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 isDefaultInFlight, 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.AddKeychecks a late key against the key commitment. OnErrInvalidthe 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. Fetchchecks everything against the headhyou give, never against the peer's word. Each entry goes throughkololog.OpenEntry, which checks its inclusion proof in the tree ofh'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.ErrDivergedneeds evidence: a head of a size we hold, or ofh's size forFetch, 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 isErrInvalid, 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.
authorizeruns 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
MaxMessageSizecannot 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, notErrDiverged. Fetchcannot tell a peer withoutKeysaccess from one that does not hold the key or chose not to send it: all givekololog.ErrKeyUnavailable.- Heads have no timestamp, so a newer head is a larger one. To read the
newest entries, get a newer head first with
FetchHeador aPull. - There is no JSON form of the wire format.
Errors
| Error | Message |
|---|---|
ErrBehind | kolosync: peer is behind the head |
ErrBusy | kolosync: peer busy |
ErrDiverged | kolosync: logs diverged |
ErrInvalid | kolosync: peer sent data that does not verify |
ErrInvalidArgument | kolosync: invalid argument |
ErrKeyMismatch | kolosync: held key does not match its record |
ErrMarked | kolosync: peer serves a deleted entry |
ErrNotFound | kolosync: log not found |
ErrProtocol | kolosync: protocol error |
ErrTimeout | kolosync: timeout |
ErrTooLarge | kolosync: 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.