As entradas ficam em uma árvore Merkle cujo hash e cujas provas seguem o
Certificate Transparency 2.0 (RFC 9162), com
BLAKE2b-256 (RFC 7693) no lugar do SHA-256, e o dono assina cada
registro e cada head com Ed25519ctx (RFC 8032), então qualquer peer pode
verificar que uma entrada está no log e que o log só cresceu. Cada entrada é
criptografada com a sua própria chave, e excluir uma entrada destrói essa
chave, enquanto todas as provas continuam válidas, como propuseram
Boneh e Lipton. Um
log também pode derivar as chaves das suas entradas de um segredo de grupo,
para que os leitores o abram a partir de qualquer cópia enquanto quem
escreve está offline. As identidades vêm da kolo-id e as codificações da
kolo-codec. Um log guarda as suas entradas em
um Storage: NewMemory para um log que não é persistido, ou a
kolo-store em disco. Veja
Logs e Réplicas.
Acrescentar uma entrada
As entradas não são encadeadas umas às outras por hashes. A árvore de Merkle as liga, e cada head assinado cobre todas as entradas anteriores.
- Append cria uma chave de entrada nova de 32 bytes. O valor é preenchido e cifrado com XChaCha20-Poly1305.
- O registro guarda o índice, o tamanho, um hash do texto cifrado e um compromisso com a chave. O dono o assina.
- A folha é o hash BLAKE2b-256 de 0x00 e do registro assinado. Ela entra na árvore pela direita.
- Cada nó acima é o hash de 0x01 e dos seus dois filhos, até uma raiz nova.
- O dono assina um head novo: o log, o tamanho e a raiz. Entrada, chave e head são gravados em um só commit.
Instalação
go get github.com/ciranda-dev/kolo-logCompila sem cgo.
Início rápido
Acrescente uma entrada, prove que ela está no log e depois exclua essa entrada.
package main
import (
"errors"
"fmt"
"log"
koloid "github.com/ciranda-dev/kolo-id"
kololog "github.com/ciranda-dev/kolo-log"
)
func main() {
me, err := koloid.Generate()
check(err)
l, err := kololog.New(me, kololog.NewMemory(), kololog.WithValueEncoding(kololog.UTF8))
check(err)
defer l.Close()
i, err := l.Append("hello")
check(err)
// A reader trusts only the owner's public key and the log ID.
h, err := l.Head()
check(err)
head, err := kololog.VerifyHead(me.PublicKey(), l.ID(), h)
check(err)
rec, err := l.Record(i)
check(err)
proof, err := l.InclusionProof(i, head.Size())
check(err)
fmt.Println("included:", kololog.VerifyInclusion(head, rec, proof))
check(l.Delete(i))
var s string
fmt.Println("deleted:", errors.Is(l.Read(i, &s), kololog.ErrDeleted))
fmt.Println("still included:", kololog.VerifyInclusion(head, rec, proof))
}
func check(err error) {
if err != nil {
log.Fatal(err)
}
}O programa imprime included: true, deleted: true e still included: true:
a entrada não pode mais ser lida, mas o head assinado e a prova continuam
válidos.
Referência da API
A referência da API é gerada a partir do código Go e está em inglês.
Package kololog is a signed append-only log on a Merkle tree for Kolo. Each entry has its own key, random by default or derived from a group secret with WithDerivedKeys; deleting an entry destroys its stored key, not the proofs.
This package is experimental and its API may change before v1.0.0.
Constantes
const (
// DerivedHeaderContext is the signing context of the header of a log with [DerivedKeys].
DerivedHeaderContext = "kolo-log/derived-header/v0"
// EntryKeyContext starts the HKDF info of a derived entry key.
EntryKeyContext = "kolo-log/entry-key/v0"
)const (
// HeadContext is the signing context of tree heads.
HeadContext = "kolo-log/tree-head/v0"
// RecordContext is the signing context of entry records.
RecordContext = "kolo-log/record/v1"
// KeyContext starts the hashed input of an entry key commitment.
KeyContext = "kolo-log/key/v0"
)const DeleteContext = "kolo-log/delete/v0"DeleteContext is the signing context of delete markers.
const EntrySecretSize = 32EntrySecretSize is the size in bytes of an EntrySecret.
const HashSize = blake2b.Size256HashSize is the size in bytes of a tree hash.
const HeaderContext = "kolo-log/header/v0"HeaderContext is the signing context of log headers.
const LogIDSize = 32LogIDSize is the size in bytes of a log ID.
const MaxAddKeys = 32768MaxAddKeys is the most keys one Replica.AddKeys call takes: as many entries as one kolo-sync answer can carry, its 4 MiB message bound over the 128-byte smallest signed record (kolo-sync wire.go, MaxMessageSize and minSigned).
Variáveis
var (
// ErrNotDerived is returned by [NewKeyDeriver] for a header with [RandomKeys].
ErrNotDerived = errors.New("kololog: log does not use derived keys")
// ErrKeyModeMismatch is returned by [Restore] when the header's key mode or epoch differs from the options.
ErrKeyModeMismatch = errors.New("kololog: key mode mismatch")
// ErrSecretMismatch is returned by [Restore] when the entry secret does not derive the newest entry's key.
ErrSecretMismatch = errors.New("kololog: entry secret mismatch")
// ErrMissingSecret is returned by [New], [Restore] and [NewKeyDeriver] for a nil entry secret.
ErrMissingSecret = errors.New("kololog: missing entry secret")
// ErrDeriverClosed is returned by [KeyDeriver.Key] after [KeyDeriver.Close].
ErrDeriverClosed = errors.New("kololog: key deriver closed")
)var (
// ErrWrongValueType is returned when a value or output does not match the log's value encoding.
ErrWrongValueType = errors.New("kololog: wrong value type")
// ErrInvalidUTF8 is returned by a UTF8 log for a string that is not valid UTF-8.
ErrInvalidUTF8 = errors.New("kololog: invalid UTF-8")
// ErrUnknownEncoding is returned for a value encoding other than Bytes, UTF8 or JSON.
ErrUnknownEncoding = errors.New("kololog: unknown value encoding")
)var (
// ErrInvalidHead is returned by [VerifyHead] for any rejected head; the errors below wrap it.
ErrInvalidHead = errors.New("kololog: invalid head")
// ErrBadHeadSignature is returned when a head is not signed by the given key or names another key.
ErrBadHeadSignature error = &headError{"kololog: invalid head signature"}
// ErrWrongLogID is returned when a correctly signed head belongs to another log.
ErrWrongLogID error = &headError{"kololog: head belongs to another log"}
)var (
// ErrDeleted is returned by [Log.Get] for an entry whose key was destroyed by [Log.Delete].
ErrDeleted = errors.New("kololog: entry deleted")
// ErrOutOfRange is returned for an index or tree size the log does not have.
ErrOutOfRange = errors.New("kololog: index out of range")
// ErrMalformed is returned when an encoding cannot be parsed.
ErrMalformed = errors.New("kololog: malformed encoding")
)var (
// ErrBadLogHeader is returned when a log header is not signed by the expected key.
ErrBadLogHeader = errors.New("kololog: bad log header")
// ErrMissingHeader is returned by [Restore] and [RestoreReplica] for a nil or empty header.
ErrMissingHeader = errors.New("kololog: missing log header")
// ErrEncodingMismatch is returned by [Restore] when the header's value encoding differs from the options.
ErrEncodingMismatch = errors.New("kololog: value encoding mismatch")
)var (
// ErrLogOpen is returned by [New], [Restore] and the Reserve functions when a writable log with the same author key and log ID
// is already open in this process, or that pair or log ID is reserved.
ErrLogOpen = errors.New("kololog: log already open in this process")
// ErrLogClosed is returned by writes and Head after [Log.Close].
ErrLogClosed = errors.New("kololog: log closed")
)var (
// ErrDiverged is returned by [Replica.Update] when the owner signed two histories: a head whose root differs from the held
// entries at its size, a head of the target's size with another root, or entries toward a newer head that miss the target's root.
ErrDiverged = errors.New("kololog: head diverges from the held entries or the pending target")
// ErrBadProof is returned by [Replica.Update] when the consistency proof does not verify, and by [OpenEntry] when the inclusion proof does not.
ErrBadProof = errors.New("kololog: consistency proof does not verify")
// ErrBadEntry is returned by [Replica.Update], [Replica.AddKey], [Replica.ApplyDelete] and [OpenEntry] for an entry, key or marker that does not match its signed record or the head, and wrapped by [BadKeyError].
ErrBadEntry = errors.New("kololog: entry does not match its signed record or the head")
// ErrNoHead is returned by [Replica.Head] before the replica has a verified head.
ErrNoHead = errors.New("kololog: replica has no verified head")
)var (
// ErrRestoreMismatch is returned by [Restore] when stored data does not match the signed head or records.
ErrRestoreMismatch = errors.New("kololog: restored data does not match the signed head or records")
// ErrRollback is returned by [Restore] when the snapshot is older than or forks from a trusted head, and by [Replica.Update]
// for a head of the held history smaller than the verified one, or, unchecked, smaller than a pending target.
ErrRollback = errors.New("kololog: snapshot or head is older than a known head or forks from it")
// ErrKeyUnavailable is returned when an entry's ciphertext is present but its key is not in this log.
ErrKeyUnavailable = errors.New("kololog: entry key not available")
)var (
// ErrNoStorage is returned by [New], [Restore], [NewReplica] and [RestoreReplica] for a nil [Storage].
ErrNoStorage = errors.New("kololog: nil storage")
// ErrStorageMismatch is returned by a read whose [Storage] returns an entry or key that does not match the entry's verified record.
ErrStorageMismatch = errors.New("kololog: stored entry does not match its verified record")
// ErrStorageNotEmpty is returned by [New] and [NewReplica] for a [Storage] that already holds an entry.
ErrStorageNotEmpty = errors.New("kololog: storage already holds entries")
)var ErrEntryTooLarge = errors.New("kololog: entry too large")ErrEntryTooLarge is returned by Log.Append for an entry over the size cap. The cap is about 254 GiB on 64-bit and about 512 MiB on 32-bit platforms.
var ErrMalformedEntry = errors.New("kololog: malformed entry")ErrMalformedEntry is returned by Log.Get when a stored ciphertext does not open to a valid entry.
var ErrNotDecodable = errors.New("kololog: a VerifiedHead cannot be decoded; decode a Head and call VerifyHead")ErrNotDecodable is returned by VerifiedHead.UnmarshalJSON, always.
var ErrTooManyKeys = errors.New("kololog: too many keys in one call")ErrTooManyKeys is returned by Replica.AddKeys for more than MaxAddKeys keys.
Funções
func OpenEntry
func OpenEntry(h VerifiedHead, p InclusionProof, e Entry) ([]byte, error)OpenEntry checks an entry received on its own against a verified head and the entry's inclusion proof in it, then returns its stored bytes as Log.Get does. Its record, ciphertext or marker, and key are checked by the same code as in Replica.Update. It returns ErrInvalidHead for a zero head, ErrBadProof for a proof that does not put the record in h, ErrBadEntry for a part that does not match the record, and, after those checks, ErrDeleted for an entry with a valid delete marker and ErrKeyUnavailable for one without its key.
func Reserve
func Reserve(logKey ed25519.PublicKey, id LogID) (release func(), err error)Reserve keeps New and Restore from opening a writable log with this key and ID until release is called. It returns ErrLogOpen if such a log is open or the pair is already reserved.
func ReserveID
func ReserveID(id LogID) (release func(), err error)ReserveID reserves a log ID under every key, for storage that cannot trust which key a log belongs to. It returns ErrLogOpen if a log with that ID is open or reserved under any key; release is idempotent.
func VerifyConsistency
func VerifyConsistency(old, new VerifiedHead, p ConsistencyProof) boolVerifyConsistency reports whether old and new belong to the same log and p proves old is a prefix of new.
func VerifyDeleteMarker
func VerifyDeleteMarker(pub ed25519.PublicKey, logID LogID, r Record, m DeleteMarker) boolVerifyDeleteMarker reports whether m is pub's valid marker for record r of the log logID. It never panics on untrusted input.
func VerifyInclusion
func VerifyInclusion(h VerifiedHead, r Record, p InclusionProof) boolVerifyInclusion reports whether r is signed by h's log key, belongs to h's log, and p proves r is in h.
func VerifyLogHeader
func VerifyLogHeader(pub ed25519.PublicKey, h LogHeader) errorVerifyLogHeader returns ErrBadLogHeader unless h is signed by pub under the context of its key mode; it refuses an unknown key mode and a header with RandomKeys and a nonzero epoch. It never panics on untrusted input.
func VerifyRecord
func VerifyRecord(pub ed25519.PublicKey, logID LogID, r Record) boolVerifyRecord reports whether r is signed by pub and belongs to the log logID. It never panics on untrusted input.
Tipos
type BadKeyError
type BadKeyError struct {
Indexes []uint64 // ascending
}BadKeyError is the error of Replica.AddKeys for the keys that do not belong to their entries; it wraps ErrBadEntry.
func (BadKeyError) Error
func (e *BadKeyError) Error() stringError returns how many keys were refused and the first refused index.
type Change
type Change struct {
Start uint64 // the log's length before the change, in every Change: Entries are stored from this index on
Entries []Entry // new entries, each with its key when it has one
Deleted []Deletion // entries whose ciphertext and key are replaced by their delete marker
Keys []KeyAt // keys of entries stored without one, in ascending index order
Heads *Heads // when not nil, replaces the stored heads
}Change is one atomic change a log makes to its Storage.
type ConsistencyProof
type ConsistencyProof struct {
OldSize uint64
NewSize uint64
Path [][HashSize]byte
}ConsistencyProof shows that the tree of OldSize entries is a prefix of the tree of NewSize entries.
func DecodeConsistencyProof
func DecodeConsistencyProof(b []byte) (ConsistencyProof, error)DecodeConsistencyProof parses an encoding made by ConsistencyProof.Encode.
func (ConsistencyProof) Encode
func (p ConsistencyProof) Encode() []byteEncode returns the canonical encoding of p.
func (ConsistencyProof) LogValue
func (p ConsistencyProof) LogValue() slog.ValueLogValue returns p as a slog group with full hex values.
func (ConsistencyProof) MarshalJSON
func (p ConsistencyProof) MarshalJSON() ([]byte, error)MarshalJSON encodes p as a JSON view.
func (ConsistencyProof) String
func (p ConsistencyProof) String() stringString returns a short summary of p.
func (ConsistencyProof) UnmarshalJSON
func (p *ConsistencyProof) UnmarshalJSON(b []byte) errorUnmarshalJSON strictly decodes the view made by ConsistencyProof.MarshalJSON.
type DeleteMarker
type DeleteMarker struct {
LogKey ed25519.PublicKey
LogID LogID
Index uint64
LeafHash [HashSize]byte
Signature []byte
}DeleteMarker is the log owner's signed statement that the entry with this leaf hash was deleted.
func DecodeDeleteMarker
func DecodeDeleteMarker(b []byte) (DeleteMarker, error)DecodeDeleteMarker parses an encoding made by DeleteMarker.Encode.
func (DeleteMarker) Encode
func (m DeleteMarker) Encode() []byteEncode returns the canonical encoding of m.
func (DeleteMarker) LogValue
func (m DeleteMarker) LogValue() slog.ValueLogValue returns m as a slog group with full hex values.
func (DeleteMarker) MarshalJSON
func (m DeleteMarker) MarshalJSON() ([]byte, error)MarshalJSON encodes m as a JSON view; the binary encoding is the only one that is signed.
func (DeleteMarker) String
func (m DeleteMarker) String() stringString returns a short summary of m.
func (DeleteMarker) UnmarshalJSON
func (m *DeleteMarker) UnmarshalJSON(b []byte) errorUnmarshalJSON strictly decodes the view made by DeleteMarker.MarshalJSON.
type Deletion
type Deletion struct {
Index uint64
Record []byte
Marker []byte
}Deletion is the stored form of a deleted entry: its record and its delete marker.
type Entry
type Entry struct {
Record []byte // Record.Encode() of the entry, exactly as hashed into the tree
Ciphertext []byte // nonce || sealed padded frame; nil after Delete
Marker []byte // DeleteMarker.Encode() of a deleted entry; nil otherwise
Key EntryKey `json:"-"` // the entry key; nil when unknown or deleted
}Entry is the stored form of one entry: its signed record, either its ciphertext or its delete marker, and its key when known. encoding/json leaves Key out; an encoder that ignores MarshalJSON, such as encoding/gob, writes the key in clear.
type EntryInfo
type EntryInfo struct {
Deleted bool // a delete marker is stored in place of the ciphertext and key
Keyed bool // the entry key is stored
}EntryInfo is what the log keeps in memory about the stored form of an entry.
type EntryKey
type EntryKey []byteEntryKey is the encryption key of one entry; formatted or logged on its own, or as a field fmt and slog can reach, it shows only as [redacted].
func (EntryKey) Format
func (EntryKey) Format(f fmt.State, _ rune)Format writes [redacted] for every verb, so no fmt verb prints the key.
func (EntryKey) LogValue
func (EntryKey) LogValue() slog.ValueLogValue returns [redacted].
func (EntryKey) MarshalJSON
func (EntryKey) MarshalJSON() ([]byte, error)MarshalJSON returns "[redacted]"; send a key only in a binary encoding over a secure channel.
func (EntryKey) String
func (EntryKey) String() stringString returns [redacted].
type EntrySecret
type EntrySecret [EntrySecretSize]byteEntrySecret is the group secret of a log with DerivedKeys: 32 uniformly random bytes used for nothing else. A guessable secret can be found offline from any record, because a record's KeyCommit is public. Every copy of the array is another copy of the secret. fmt, slog and JSON show it as [redacted], but it prints raw inside an unexported struct field (by value or behind one pointer), with %p of a value, and in encoding/gob.
func (EntrySecret) Format
func (EntrySecret) Format(f fmt.State, _ rune)Format writes [redacted] for every verb.
func (EntrySecret) GoString
func (EntrySecret) GoString() stringGoString returns [redacted].
func (EntrySecret) LogValue
func (EntrySecret) LogValue() slog.ValueLogValue returns [redacted].
func (EntrySecret) MarshalJSON
func (EntrySecret) MarshalJSON() ([]byte, error)MarshalJSON returns "[redacted]".
func (EntrySecret) String
func (EntrySecret) String() stringString returns [redacted].
type Head
type Head struct {
LogKey ed25519.PublicKey
LogID LogID
Size uint64
Root [HashSize]byte
Signature []byte
}Head is a signed statement of the size and root hash of a log, as sent over the network.
func DecodeHead
func DecodeHead(b []byte) (Head, error)DecodeHead parses an encoding made by Head.Encode.
func (Head) Encode
func (h Head) Encode() []byteEncode returns the canonical encoding of h.
func (Head) LogValue
func (h Head) LogValue() slog.ValueLogValue returns h as a slog group with full hex values.
func (Head) MarshalJSON
func (h Head) MarshalJSON() ([]byte, error)MarshalJSON encodes h as a JSON view; the binary encoding is the only one that is signed.
func (Head) String
func (h Head) String() stringString returns a short summary of h.
func (Head) UnmarshalJSON
func (h *Head) UnmarshalJSON(b []byte) errorUnmarshalJSON strictly decodes the view made by Head.MarshalJSON; verify the result with VerifyHead.
type Heads
type Heads struct {
Head *Head // the last head whose every entry is stored; nil for a replica with no head yet
Target *Head // a replica's catch-up target, past Head; nil when none is pending
Proof ConsistencyProof // with Target: the proof that the stored entries are a prefix of it
}Heads is what a log stores about its heads.
type InclusionProof
type InclusionProof struct {
Index uint64
Size uint64
Path [][HashSize]byte
}InclusionProof shows that the entry at Index is in the tree of Size entries.
func DecodeInclusionProof
func DecodeInclusionProof(b []byte) (InclusionProof, error)DecodeInclusionProof parses an encoding made by InclusionProof.Encode.
func (InclusionProof) Encode
func (p InclusionProof) Encode() []byteEncode returns the canonical encoding of p.
func (InclusionProof) LogValue
func (p InclusionProof) LogValue() slog.ValueLogValue returns p as a slog group with full hex values.
func (InclusionProof) MarshalJSON
func (p InclusionProof) MarshalJSON() ([]byte, error)MarshalJSON encodes p as a JSON view.
func (InclusionProof) String
func (p InclusionProof) String() stringString returns a short summary of p.
func (InclusionProof) UnmarshalJSON
func (p *InclusionProof) UnmarshalJSON(b []byte) errorUnmarshalJSON strictly decodes the view made by InclusionProof.MarshalJSON.
type KeyAt
type KeyAt struct {
Index uint64
Key EntryKey
}KeyAt is the key of entry Index, in a Change.
type KeyDeriver
type KeyDeriver struct {
// contains filtered or unexported fields
}KeyDeriver derives the entry keys of one log with DerivedKeys; it is safe for concurrent use. fmt and slog show a *KeyDeriver as [redacted]; a KeyDeriver value prints its log key, log ID and epoch, never the PRK.
func NewKeyDeriver
func NewKeyDeriver(secret *EntrySecret, owner ed25519.PublicKey, h LogHeader) (*KeyDeriver, error)NewKeyDeriver checks h with VerifyLogHeader(owner, h) and returns its deriver, or ErrNotDerived for a header with RandomKeys.
func (KeyDeriver) Close
func (d *KeyDeriver) Close()Close clears the PRK; Key calls that hold the read lock finish first. HMAC's own copies stay in memory until the runtime reuses them.
func (KeyDeriver) Format
func (*KeyDeriver) Format(f fmt.State, _ rune)Format writes [redacted] for every verb.
func (KeyDeriver) GoString
func (*KeyDeriver) GoString() stringGoString returns [redacted].
func (KeyDeriver) Key
func (d *KeyDeriver) Key(index uint64) (EntryKey, error)Key returns the key of entry index, or ErrDeriverClosed after Close; the caller should clear it.
func (KeyDeriver) LogValue
func (*KeyDeriver) LogValue() slog.ValueLogValue returns [redacted].
func (KeyDeriver) String
func (*KeyDeriver) String() stringString returns [redacted].
type KeyMode
type KeyMode uint8KeyMode is how a log makes its entry keys.
const (
// RandomKeys gives every entry a fresh random key that only the writer holds; it is the default.
RandomKeys KeyMode = iota
// DerivedKeys derives every entry key from an [EntrySecret], the log and the entry's index.
DerivedKeys
)func (KeyMode) String
func (m KeyMode) String() stringString returns "random" or "derived".
type Log
type Log struct {
// contains filtered or unexported fields
}Log is a signed append-only log owned by one writer; it is safe for concurrent use. It keeps its tree hashes and a compact copy of each record in memory, and its entries in its Storage.
func New
func New(id *koloid.Identity, s Storage, opts ...Option) (*Log, error)New returns an empty Log with a random log ID and a signed LogHeader, which keeps its entries in s. s must belong to this log only. New stores nothing: the caller stores the header if it keeps the log. It returns koloid.ErrInvalidIdentity for a nil or zero identity instead of panicking, ErrNoStorage for a nil s, ErrStorageNotEmpty for an s that returns an entry at index 0, and the storage's error if it fails to read index 0.
func Restore
func Restore(id *koloid.Identity, header, head []byte, s Storage, opts ...Option) (*Log, error)Restore rebuilds a writable log from its persisted header and head and the entries in s, verifying all of it. It reads the head's entries from s once each in increasing order, checks them in parallel and keeps only their records; the error is the first bad entry in log order. A live entry without its key returns ErrRestoreMismatch.
func (Log) Append
func (l *Log) Append(v any) (uint64, error)Append encodes v with the log's value encoding, encrypts it, stores it with a head signed over it in one Storage.Commit and returns its index. If the commit fails, the log is unchanged and the error wraps the storage's. With JSON, encoding/json keeps its own internal buffers, which kololog cannot clear.
func (Log) Close
func (l *Log) Close() errorClose releases the log ID for another writable log in this process and clears a derived log's PRK; reads keep working. Append, Head and Delete then return ErrLogClosed. Closing twice is not an error.
func (Log) ConsistencyProof
func (l *Log) ConsistencyProof(oldSize, newSize uint64) (ConsistencyProof, error)ConsistencyProof returns a proof that the tree of oldSize entries is a prefix of the tree of newSize entries.
func (Log) Delete
func (l *Log) Delete(indexes ...uint64) errorDelete signs a DeleteMarker for each entry at indexes and stores them in place of the entries' ciphertexts and keys in one Storage.Commit, so deleting many entries costs one durable write; the records and every proof stay valid. An index out of range returns ErrOutOfRange and deletes nothing. Entries already deleted, and repeated indexes, are skipped; if the commit fails, every entry stays as it was.
func (Log) Entry
func (l *Log) Entry(index uint64) (Entry, error)Entry returns the stored form of the entry at index, its key included; clear Key when done with it. It reads the entry from storage and checks it against the entry's record: a deleted entry must come with its marker only.
func (Log) EntryInfo
func (l *Log) EntryInfo(index uint64) (EntryInfo, error)EntryInfo returns whether the entry at index is deleted and whether its key is stored, without reading storage.
func (Log) Format
func (l *Log) Format(f fmt.State, _ rune)Format writes l.String() for every verb, so no verb prints the log's storage and the entry keys in it.
func (Log) Get
func (l *Log) Get(index uint64) ([]byte, error)Get returns the stored bytes of the entry at index, ErrDeleted after Log.Delete, or ErrKeyUnavailable for an entry stored without its key. It reads the entry from storage and checks it against the entry's record first.
func (Log) GoString
func (l *Log) GoString() stringGoString returns l.String().
func (Log) Head
func (l *Log) Head() (Head, error)Head returns a signed head for the current tree.
func (Log) Header
func (l *Log) Header() LogHeaderHeader returns a copy of the signed log header.
func (Log) ID
func (l *Log) ID() LogIDID returns the random ID of the log.
func (Log) InclusionProof
func (l *Log) InclusionProof(index, size uint64) (InclusionProof, error)InclusionProof returns a proof that the entry at index is in the tree of the first size entries.
func (Log) Key
func (l *Log) Key(index uint64) (EntryKey, error)Key returns the key of the entry at index, read from storage without its ciphertext and checked against the record's key commitment; clear it when done. A deleted entry returns ErrDeleted, one stored without its key ErrKeyUnavailable.
func (Log) Len
func (l *Log) Len() uint64Len returns the number of entries in the log, deleted ones included.
func (Log) LogValue
func (l *Log) LogValue() slog.ValueLogValue returns l's log ID, value encoding, key mode and epoch as a slog group.
func (Log) Read
func (l *Log) Read(index uint64, out any) errorRead decodes the entry at index into out with the log's value encoding. With JSON, encoding/json keeps its own internal buffers, which kololog cannot clear.
func (Log) Record
func (l *Log) Record(index uint64) (Record, error)Record returns the public record of the entry at index, which stays available after Log.Delete.
func (Log) String
func (l *Log) String() stringString returns a short summary of l: its log ID, value encoding, key mode and epoch.
type LogHeader
type LogHeader struct {
LogKey ed25519.PublicKey
LogID LogID
Encoding ValueEncoding
Keys KeyMode
Epoch uint64 // 0 with RandomKeys
Signature []byte
}LogHeader is the signed description of a log, persisted next to its data by the storage layer. A header with RandomKeys has the encoding of kolo-log v0.1.6; one with DerivedKeys has its own tag and signing context.
func DecodeLogHeader
func DecodeLogHeader(b []byte) (LogHeader, error)DecodeLogHeader parses an encoding made by LogHeader.Encode.
func (LogHeader) Encode
func (h LogHeader) Encode() []byteEncode returns the canonical encoding of h.
func (LogHeader) LogValue
func (h LogHeader) LogValue() slog.ValueLogValue returns h as a slog group with full hex values.
func (LogHeader) MarshalJSON
func (h LogHeader) MarshalJSON() ([]byte, error)MarshalJSON encodes h as a JSON view; the binary encoding is the only one that is signed. A header with DerivedKeys adds "keys": "derived" and "epoch".
func (LogHeader) String
func (h LogHeader) String() stringString returns a short summary of h.
func (LogHeader) UnmarshalJSON
func (h *LogHeader) UnmarshalJSON(b []byte) errorUnmarshalJSON strictly decodes the view made by LogHeader.MarshalJSON: the four fields of a header with random keys, or those and both "keys": "derived" and "epoch".
type LogID
type LogID [LogIDSize]byteLogID is the random ID that separates logs under the same identity.
func (LogID) LogValue
func (id LogID) LogValue() slog.ValueLogValue returns the log ID as lowercase hex.
func (LogID) MarshalJSON
func (id LogID) MarshalJSON() ([]byte, error)MarshalJSON encodes the log ID as a lowercase hex string.
func (LogID) String
func (id LogID) String() stringString returns the log ID as lowercase hex.
func (LogID) UnmarshalJSON
func (id *LogID) UnmarshalJSON(b []byte) errorUnmarshalJSON decodes a lowercase hex string of exactly 32 bytes.
type Option
type Option func(*options)func ReserveForRestore
func ReserveForRestore(logKey ed25519.PublicKey, id LogID) (opt Option, release func(), err error)func WithDerivedKeys
func WithDerivedKeys(secret *EntrySecret, epoch uint64) OptionWithDerivedKeys makes New derive entry keys from secret under epoch, and makes Restore require a log that does. It copies secret when called; the copy lives as long as the Option. A nil secret makes New and Restore return ErrMissingSecret.
func WithTrustedHead
func WithTrustedHead(h Head) Optionfunc WithValueEncoding
func WithValueEncoding(e ValueEncoding) OptionWithValueEncoding sets the value encoding of the log; the default is Bytes.
type Record
type Record struct {
LogKey ed25519.PublicKey
LogID LogID
Index uint64
Size uint64 // padded ciphertext length in bytes
ContentHash [HashSize]byte // BLAKE2b-256 of the ciphertext
KeyCommit [HashSize]byte // BLAKE2b-256 of KeyContext and the entry key, so one record opens to one plaintext only
Signature []byte
}Record is the signed public metadata of one entry; its encoding is the Merkle leaf.
func DecodeRecord
func DecodeRecord(b []byte) (Record, error)DecodeRecord parses an encoding made by Record.Encode.
func (Record) Encode
func (r Record) Encode() []byteEncode returns the canonical encoding of r.
func (Record) LogValue
func (r Record) LogValue() slog.ValueLogValue returns r as a slog group with full hex values.
func (Record) MarshalJSON
func (r Record) MarshalJSON() ([]byte, error)MarshalJSON encodes r as a JSON view; the binary encoding is the only one that is signed.
func (Record) String
func (r Record) String() stringString returns a short summary of r.
func (Record) UnmarshalJSON
func (r *Record) UnmarshalJSON(b []byte) errorUnmarshalJSON strictly decodes the view made by Record.MarshalJSON.
type Replica
type Replica struct {
// contains filtered or unexported fields
}Replica is a read-only copy of a log, opened from the owner's public key; it is safe for concurrent use. It grows only through Replica.Update, which verifies everything before it commits any of it to its Storage.
func NewReplica
func NewReplica(pub ed25519.PublicKey, logID LogID, header []byte, s Storage) (*Replica, error)NewReplica returns an empty replica of the log logID owned by pub, from the log's signed header, keeping its entries in s. s must belong to this replica only: one that returns an entry at index 0 gives ErrStorageNotEmpty, and a failed read of index 0 the storage's error. NewReplica stores nothing: the caller stores the header if it keeps the replica.
func RestoreReplica
func RestoreReplica(pub ed25519.PublicKey, logID LogID, header []byte, heads Heads, s Storage) (*Replica, error)RestoreReplica rebuilds a replica from its persisted header and heads and the entries in s, verifying all of it like Restore, then replays a pending heads.Target through the checks of Replica.Update. Zero heads are a replica that has not grown yet. Errors in the stored data wrap ErrRestoreMismatch.
func (Replica) AddKey
func (r *Replica) AddKey(index uint64, key []byte) errorAddKey gives a held entry that came without its key the key, after checking it against the record's key commitment and that it opens the ciphertext read from storage, and commits it. The key an entry already has does nothing; another key returns ErrBadEntry. The caller should clear key.
func (Replica) AddKeys
func (r *Replica) AddKeys(start uint64, keys []EntryKey) errorAddKeys checks every key in keys against the held entries from start on, and stores every key that passes in one Storage.Commit. A nil or empty key skips its entry, and so does an entry that is deleted or already keyed. Keys the signed record proves wrong are refused together in one *BadKeyError, and the keys that passed are still stored. A storage error or ErrStorageMismatch stores nothing. More than MaxAddKeys keys is ErrTooManyKeys, and keys past Len ErrOutOfRange. The caller should clear keys.
func (Replica) ApplyDelete
func (r *Replica) ApplyDelete(markers ...[]byte) errorApplyDelete verifies encoded [DeleteMarker]s for entries the replica holds, then commits them in place of those entries' ciphertexts and keys in one Storage.Commit. The records and the markers stay, and reads return ErrDeleted. A marker that does not decode, is out of range or does not match its entry returns an error and applies none of them; a marker for an entry already deleted, or repeated, is skipped.
func (Replica) Close
func (r *Replica) Close() errorClose stops Update, AddKey, AddKeys and ApplyDelete, which then return ErrLogClosed; reads keep working.
func (Replica) ConsistencyProof
func (r *Replica) ConsistencyProof(oldSize, newSize uint64) (ConsistencyProof, error)ConsistencyProof returns a proof that the tree of oldSize entries is a prefix of the tree of newSize entries.
func (Replica) Entry
func (r *Replica) Entry(index uint64) (Entry, error)Entry returns the stored form of the entry at index, its key included; clear Key when done with it.
func (Replica) EntryInfo
func (r *Replica) EntryInfo(index uint64) (EntryInfo, error)EntryInfo returns whether the entry at index is deleted and whether its key is stored, without reading storage.
func (Replica) Format
func (r *Replica) Format(f fmt.State, _ rune)Format writes r.String() for every verb.
func (Replica) Get
func (r *Replica) Get(index uint64) ([]byte, error)Get returns the stored bytes of the entry at index, ErrKeyUnavailable without its key, or ErrDeleted.
func (Replica) GoString
func (r *Replica) GoString() stringGoString returns r.String().
func (Replica) Head
func (r *Replica) Head() (Head, error)Head returns the last verified head whose every entry the replica holds, exactly as received, or ErrNoHead.
func (Replica) Header
func (r *Replica) Header() LogHeaderHeader returns a copy of the signed log header.
func (Replica) ID
func (r *Replica) ID() LogIDID returns the log ID.
func (Replica) InclusionProof
func (r *Replica) InclusionProof(index, size uint64) (InclusionProof, error)InclusionProof returns a proof that the entry at index is in the tree of the first size entries.
func (Replica) Key
func (r *Replica) Key(index uint64) (EntryKey, error)Key returns the key of the entry at index without reading its ciphertext, as Log.Key does.
func (Replica) Len
func (r *Replica) Len() uint64Len returns the number of verified entries, deleted ones included; during a catch-up it can exceed Head's size.
func (Replica) LogValue
func (r *Replica) LogValue() slog.ValueLogValue returns r's log ID, value encoding, key mode and epoch as a slog group.
func (Replica) Read
func (r *Replica) Read(index uint64, out any) errorRead decodes the entry at index into out with the log's value encoding.
func (Replica) Record
func (r *Replica) Record(index uint64) (Record, error)Record returns the public record of the entry at index.
func (Replica) String
func (r *Replica) String() stringString returns a short summary of r: its log ID, value encoding, key mode and epoch.
func (Replica) Target
func (r *Replica) Target() (h Head, p ConsistencyProof, ok bool)Target returns the head an unfinished catch-up is filling and the proof that the first Len entries are a prefix of it, or ok false. The replica commits both with each chunk, and RestoreReplica replays them.
func (Replica) Update
func (r *Replica) Update(h Head, p ConsistencyProof, entries []Entry) errorUpdate verifies h, the entries from Len on and a consistency proof p, then commits them all in one Storage.Commit; on any error the replica is unchanged. The entries may stop at any size m up to h's size, so a replica far behind catches up in chunks; p then proves the tree of m entries, rebuilt from every verified leaf, is a prefix of h (RFC 9162). When the entries reach h's size, p may also be the proof from Len, or anything for an empty replica, and the rebuilt root must equal h's root. Until a chunk reaches h, h is the target (Replica.Target) and Replica.Head stays the last head whose every entry is held. A head whose entries the replica already holds becomes its head or is a no-op; an older one returns ErrRollback if it matches the held entries and ErrDiverged if not, as does a head of the size of the head or target with another root. While a target is pending, a head between Len and the target's size is refused unchecked with ErrRollback, a chunk toward a larger head must reach the target's size (ErrBadEntry otherwise), and the rebuilt root there must equal the target's root (ErrDiverged otherwise). An entry may come without a key and then reads as ErrKeyUnavailable; a deleted one carries its marker.
type Storage
type Storage interface {
// Entry returns the stored form of the entry at index, its key included, as copies the log may keep or clear.
// For an index that holds no entry it returns an error wrapping [ErrOutOfRange]; any other error means the storage failed.
// Restore and RestoreReplica ask for each index once, in increasing order, from one goroutine at a time that is not the caller's,
// and after a bad entry may still ask for a few more.
Entry(index uint64) (Entry, error)
// Key returns the stored key of the entry at index, nil if it has none, as a copy the log clears.
Key(index uint64) (EntryKey, error)
// Commit stores c atomically and durably, or nothing at all when it returns an error. It must copy what it keeps:
// the log zeroes the keys in c after Commit returns.
Commit(c Change) error
}Storage keeps one log's entries and heads. A log or replica keeps only tree hashes and a compact copy of each record in memory, reads entries from its Storage and checks them against the record, and makes every change through Commit. The log calls Storage with its own lock held: Commit never runs at the same time as another call, reads may run together.
func NewMemory
func NewMemory() StorageNewMemory returns an empty in-memory Storage, for one log or replica that is not persisted.
type ValueEncoding
type ValueEncoding uint8ValueEncoding is how Log.Append encodes values and Log.Read decodes them.
const (
// Bytes stores []byte values unchanged; it is the default.
Bytes ValueEncoding = iota
// UTF8 stores string values, which must be valid UTF-8.
UTF8
// JSON stores any value as its encoding/json form.
JSON
)func (ValueEncoding) String
func (e ValueEncoding) String() stringString returns "bytes", "utf8" or "json".
type VerifiedHead
type VerifiedHead struct {
// contains filtered or unexported fields
}VerifiedHead is a Head whose signature and log ID VerifyHead has checked. Only VerifyHead can build one; the zero value verifies nothing.
func VerifyHead
func VerifyHead(pub ed25519.PublicKey, logID LogID, h Head) (VerifiedHead, error)VerifyHead checks that h is signed by pub and belongs to the log logID. It never panics on untrusted input.
func (VerifiedHead) Head
func (v VerifiedHead) Head() HeadHead returns a copy of the signed head, for sending it on.
func (VerifiedHead) LogID
func (v VerifiedHead) LogID() LogIDLogID returns the ID of the log the head belongs to.
func (VerifiedHead) LogKey
func (v VerifiedHead) LogKey() ed25519.PublicKeyLogKey returns the public key that signed the head.
func (VerifiedHead) LogValue
func (v VerifiedHead) LogValue() slog.ValueLogValue returns v like Head.LogValue.
func (VerifiedHead) MarshalJSON
func (v VerifiedHead) MarshalJSON() ([]byte, error)MarshalJSON encodes v like Head.MarshalJSON.
func (VerifiedHead) Root
func (v VerifiedHead) Root() [HashSize]byteRoot returns the root hash of the tree.
func (VerifiedHead) Size
func (v VerifiedHead) Size() uint64Size returns the number of entries in the tree.
func (VerifiedHead) String
func (v VerifiedHead) String() stringString returns a short summary of v.
func (VerifiedHead) UnmarshalJSON
func (v *VerifiedHead) UnmarshalJSON([]byte) errorUnmarshalJSON always returns ErrNotDecodable.
Bom saber
Conferir uma prova de inclusão
Uma prova mostra que uma entrada está no log sem enviar as outras. Ela segue a RFC 9162, com BLAKE2b-256.
- O leitor tem um head assinado pelo dono: tamanho 5 e a raiz. Primeiro ele confere a assinatura.
- Ele pede a entrada 2 e recebe o registro assinado e um caminho de auditoria de três hashes: a folha 3, o nó 0-1 e a folha 4.
- Ele confere a assinatura do registro, transforma o registro na folha 2 e sobe pela árvore com cada hash do caminho.
- Se o resultado for igual à raiz assinada, a entrada 2 está no log com esse tamanho. Qualquer outro registro dá outra raiz.
Excluir uma entrada
Excluir tira o conteúdo, não a entrada: o registro fica, então todos os heads e provas continuam valendo.
- A entrada 2 é guardada como o seu registro assinado, o seu texto cifrado e a sua chave de entrada.
- Delete cria um marcador de exclusão: o log, o índice e o hash da folha, assinados pelo dono.
- O texto cifrado e a chave são descartados; o registro e o marcador ficam. A árvore e o head não mudam.
- Uma réplica confere o marcador e descarta a sua cópia desse texto cifrado e dessa chave. Ler a entrada dá ErrDeleted.
- Uma cópia feita antes, ou uma chave que alguém guardou, fica fora de alcance. A exclusão é feita da melhor forma possível.
Um log ou uma réplica mantém na memória só os hashes da sua árvore e uma
cópia compacta de cada registro. Os textos cifrados, as chaves e os
marcadores de exclusão ficam no seu Storage, uma interface com três
métodos: Entry, Key e Commit. Cada mudança é um único Commit
atômico, feito com o lock do log antes de a mudança aparecer: Append
confirma a entrada com o head assinado logo depois, Delete e ApplyDelete
os registros e os marcadores no lugar dos textos cifrados e das chaves,
AddKey e AddKeys as chaves (Change.Keys, uma lista de índice e chave
em ordem crescente), e Update as suas entradas com os novos heads. Um commit
que falha deixa o log ou a réplica exatamente como estava. Um armazenamento
pertence a um único log: New e NewReplica retornam ErrStorageNotEmpty
para um que já guarda uma entrada.
Entry precisa retornar um erro que envolva ErrOutOfRange para um índice
que não guarda nenhuma entrada. New e NewReplica leem o índice 0 para
verificar que o armazenamento está vazio, e retornam qualquer outro erro
dessa leitura, como uma leitura que falhou ou um backend fechado, em vez de
começar um log sobre ele. Para uma entrada que o log tem, ErrOutOfRange do
armazenamento significa que o armazenamento a perdeu: as leituras retornam
ErrStorageMismatch, e Restore e RestoreReplica ErrRestoreMismatch,
nunca ErrOutOfRange. Um Storage próprio precisa seguir esse contrato e
guardar cada chave de Change.Keys. A kolo-store faz isso.
Cada leitura verifica o que o armazenamento retorna contra o registro na
memória e retorna ErrStorageMismatch se houver diferença. Get e Key de
uma entrada excluída retornam ErrDeleted sem ler o armazenamento. Key e
EntryInfo informam a uma camada de sincronização a chave de uma entrada, e
se ela está excluída ou tem chave, sem ler o seu texto cifrado. Restore e
RestoreReplica leem cada entrada do armazenamento uma vez, em ordem,
e verificam cada uma: uma goroutine lê o armazenamento, até GOMAXPROCS
trabalhadores (no máximo 16) conferem as entradas, e os resultados são aplicados
na ordem dos índices, então o erro é sempre o da primeira entrada ruim na ordem
do log. Por isso um Storage é lido por uma goroutine diferente da de quem
chama, uma chamada por vez, e pode ser pedido a ele até 2 x trabalhadores + 1
entradas além da primeira ruim. Restore retorna ErrRestoreMismatch para uma
entrada viva de um log próprio guardada sem a sua chave. Restaurar 200 entradas
de 1 MiB levou 164 ms em vez de 471 ms, e 20.000 entradas de 100 bytes 140 ms em
vez de 1,38 s, em uma máquina de 10 núcleos com carga; o tempo cresce com os
bytes guardados divididos pelos trabalhadores, mais o tempo que o armazenamento
leva para lê-los, enquanto Append, Head e as provas nunca leem as entradas
guardadas.
Delete(indexes...) e ApplyDelete(markers...) recebem várias entradas ou
marcadores e confirmam todos de uma vez, tudo ou nada. Um índice fora do
intervalo ou um marcador inválido não exclui nada, e as entradas já
excluídas são puladas.
Um Log tem um único escritor. Não existe log com vários escritores: o uso em
vários dispositivos e o chat usam um log por dispositivo ou por pessoa, e cada
um é replicado pelos outros como uma Replica somente leitura. Uma Replica
precisa só da chave pública do dono, do ID do log e do cabeçalho assinado do
log, nunca de uma chave privada, e só cresce por meio de Update, que verifica
tudo antes de guardar qualquer coisa. Uma réplica muito atrasada pode se
atualizar em partes: Update aceita entradas que param antes do head,
confirma esse head e a sua prova como alvo pendente junto com as entradas, e
RestoreReplica reproduz o alvo depois de uma reinicialização. OpenEntry
verifica uma entrada buscada sozinha contra um head verificado e a sua prova
de inclusão.
Chaves de entrada derivadas
Um log tem um de dois modos de chave, fixado no seu cabeçalho assinado. Com
RandomKeys, o padrão, cada entrada recebe uma chave aleatória nova que só
quem escreve tem, e um leitor recebe as chaves de quem escreve. Com
DerivedKeys, a partir de New(id, s, WithDerivedKeys(&secret, epoch)),
cada chave de entrada é derivada de um segredo de grupo, do log e do índice
da entrada. Quem tem o segredo deriva a chave de qualquer entrada e abre o
texto cifrado que recebeu de quem escreve, de uma réplica ou de um pin, sem
quem escreve estar online. Nenhuma chave precisa viajar. Um log criado sem
WithDerivedKeys não muda, byte a byte.
Use DerivedKeys só quando todo detentor do segredo puder ler todas as
entradas do log. Um log que esconde chaves de alguns leitores continua com
RandomKeys.
- A derivação é HKDF-SHA256 do
EntrySecret, com a chave do log, o ID do log, a época e o índice no seu info. A chave derivada passa pela mesma criptografia e pelo mesmoKeyCommitque uma aleatória. - O
EntrySecretprecisa ter 32 bytes uniformemente aleatórios, decrypto/rand, e não servir para mais nada. Com um segredo adivinhável, quem tem um único registro consegue encontrá-lo offline. - A época é definida por quem chama e fica no cabeçalho assinado. Um segredo novo vai com logs novos na época seguinte, e um log nunca mistura épocas. A kolo-log nunca compara épocas entre logs: uma aplicação que passa para uma época nova precisa recusar um cabeçalho cuja época seja menor que a que ela usa.
RestoreretornaErrKeyModeMismatchquando o cabeçalho e as opções discordam sobre o modo ou a época, eErrSecretMismatchquando o segredo não deriva a chave da entrada mais nova.WithDerivedKeys(nil, epoch)dáErrMissingSecret.- Um leitor cria um
KeyDerivercomNewKeyDeriver(secret, owner, header)(ErrNotDerivedpara um cabeçalho com chaves aleatórias).Closeo limpa. Replica.AddKeys(start, keys)verifica muitas chaves de uma vez, no máximoMaxAddKeys(32.768) por chamada, e guarda em um único commit cada chave que passa. As chaves que um registro assinado prova erradas voltam juntas em um único*BadKeyError, que envolveErrBadEntry.
O que o modo significa para os leitores, nas palavras do guia da kolo-log:
- Quem lê. Todo mundo que já teve o segredo lê cada entrada da época cujo texto cifrado consegue obter, de quem escreve, de uma réplica ou de qualquer pin, sem quem escreve estar online, enquanto houver cópias.
- Leitor removido. A kolo-log não tem membros. Um leitor que teve o segredo de uma época continua lendo cada entrada dessa época. Mantê-lo fora das entradas seguintes exige um segredo novo, feito de bytes aleatórios novos e nunca derivado do antigo, entregue só aos leitores que ficam, e logs novos na época seguinte; ele fica com cada época que teve e com nada depois disso.
- Leitor novo. Quem recebe o segredo lê todo o histórico da época, inclusive as entradas escritas antes de receber o segredo, também as de autores que ele nunca encontra.
- Excluir não revoga a leitura. Excluir uma entrada não consegue tirá-la de quem tem o segredo e guardou uma cópia do texto cifrado dela: uma chave que pode ser derivada de novo não pode ser destruída.
- Sem sigilo futuro (forward secrecy) dentro de uma época. Quem recebe o segredo de uma época, a qualquer momento, lê cada entrada dessa época que ainda esteja em um pin ou em uma cópia, passada e futura. Chaves aleatórias deixam quem escreve destruir uma chave; chaves derivadas abrem mão disso.
Um pin, ou qualquer outro detentor de texto cifrado sem o segredo, fica sabendo o modo e a época de cada log pelo cabeçalho dele, e não lê nada. O Kolo Chat usa este modo, então uma mensagem é lida de um pin enquanto quem a enviou está offline.
Limites
- Tamanho da entrada: cerca de 254 GiB em plataformas de 64 bits e cerca de
512 MiB em plataformas de 32 bits. Acima disso,
AppendretornaErrEntryTooLarge. - Preenchimento: toda entrada de até 254 bytes ocupa um frame de 256 bytes antes da criptografia e 296 bytes de texto cifrado em disco (um nonce de 24 bytes e uma tag de 16 a mais). As maiores são arredondadas para cima com o preenchimento Padmé, com no máximo cerca de 6% a mais.
- Memória: cerca de 64 bytes de hashes da árvore e 144 bytes de registro por entrada. Ela cresce com o número de entradas, nunca com o tamanho delas.
- ID do log: 32 bytes, aleatório. Hashes da árvore: 32 bytes (BLAKE2b-256).
- Caminhos de prova: no máximo 65 hashes.
- Entrada JSON: no máximo 4 KiB, ou 8 KiB para provas. Entradas maiores,
campos desconhecidos ou duplicados, hex em maiúsculas, sequências de escape
e dados sobrando retornam um erro que envolve
ErrMalformed. - Um log gravável por (chave do autor, ID do log) em um processo.
NeweRestoreretornamErrLogOpenpara um segundo log, ou enquanto o par estiver reservado porReserveouReserveForRestore, ou o ID do log porReserveID.
Segurança
- Heads, registros, marcadores de exclusão e o cabeçalho do log são
assinados com Ed25519ctx sob contextos próprios:
kolo-log/tree-head/v0,kolo-log/record/v1,kolo-log/delete/v0ekolo-log/header/v0, oukolo-log/derived-header/v0para o cabeçalho de um log com chaves derivadas. - A árvore usa o hashing da RFC 9162 com BLAKE2b-256. As entradas são criptografadas com XChaCha20-Poly1305.
- O XChaCha20-Poly1305 não se compromete com a chave, então cada registro
carrega
KeyCommit, o hash BLAKE2b-256 dekolo-log/key/v0e da chave da entrada.Restore,RestoreReplica,Update,AddKeyeOpenEntryverificam a chave contra esse valor antes de descriptografar, então um registro assinado abre para um único texto em claro. - O hash do texto cifrado é verificado em cada leitura, porque a chave fica guardada ao lado do texto cifrado: outros dados selados com essa chave também abririam.
- Para cada entrada, a chave do autor, o ID do log, o índice, o tamanho com preenchimento, o hash do texto cifrado e o compromisso da chave são públicos. O conteúdo, o seu tamanho real e o momento em que foi escrito não são, nem depois da exclusão.
- O log limpa as chaves que usa assim que termina, mas a cópia interna da
chave no objeto de cifra fica na memória até o runtime reaproveitar esse
espaço. Com a codificação
JSON, oencoding/jsonmantém os seus próprios buffers, que a kolo-log não consegue limpar. - Toda função
Decodee todo verificador recebem bytes não confiáveis e retornam um erro ou false, nunca um pânico. - O JSON é uma visão para APIs, depuração e configuração. Ele nunca é
assinado, e um
Headlido de JSON só é confiável depois deVerifyHead. - Passe
WithTrustedHeadcom o head mais recente que você já viu paraRestore. Assim um snapshot mais antigo ou bifurcado retornaErrRollback, e um log restaurado nunca assina de novo um índice que já foi publicado. Replica.UpdateretornaErrDivergedquando o dono assinou dois históricos, eErrRollbackpara um head mais antigo do mesmo histórico. Em qualquer erro a réplica fica exatamente como estava.
Limites conhecidos
- Experimental. A API pode mudar antes da v1.0.0.
NewMemoryguarda as entradas só na memória e não guarda heads, então o log dele não pode ser restaurado depois de uma reinicialização. Para isso, use umStoragepersistente, como a kolo-store.- As chaves ficam confiadas ao armazenamento. Um valor antigo de entrada
colocado de volta nele é recusado enquanto o log está aberto, mas depois de
um
Restoreele é lido de novo como a entrada viva. - Os heads não têm timestamp, então uma réplica ordena os heads só pelo tamanho e pela raiz.
- Enquanto há um alvo de atualização pendente,
Updaterecusa sem verificar, comErrRollback, um head entreLene o tamanho do alvo. Nesse caso o erro não quer dizer que o head compartilha o histórico da réplica. VerifyConsistencytambém aceita um tamanho antigo de 0 e tamanhos iguais, que a RFC 9162 deixa sem definição.- Uma entrada recebida sem a sua chave é lida como
ErrKeyUnavailableaté queAddKeyouAddKeyslhe entregue a chave.
Erros
| Erro | Mensagem |
|---|---|
ErrBadEntry | kololog: entry does not match its signed record or the head |
ErrBadHeadSignature | |
ErrBadLogHeader | kololog: bad log header |
ErrBadProof | kololog: consistency proof does not verify |
ErrDeleted | kololog: entry deleted |
ErrDeriverClosed | kololog: key deriver closed |
ErrDiverged | kololog: head diverges from the held entries or the pending target |
ErrEncodingMismatch | kololog: value encoding mismatch |
ErrEntryTooLarge | kololog: entry too large |
ErrInvalidHead | kololog: invalid head |
ErrInvalidUTF8 | kololog: invalid UTF-8 |
ErrKeyModeMismatch | kololog: key mode mismatch |
ErrKeyUnavailable | kololog: entry key not available |
ErrLogClosed | kololog: log closed |
ErrLogOpen | kololog: log already open in this process |
ErrMalformed | kololog: malformed encoding |
ErrMalformedEntry | kololog: malformed entry |
ErrMissingHeader | kololog: missing log header |
ErrMissingSecret | kololog: missing entry secret |
ErrNoHead | kololog: replica has no verified head |
ErrNoStorage | kololog: nil storage |
ErrNotDecodable | kololog: a VerifiedHead cannot be decoded; decode a Head and call VerifyHead |
ErrNotDerived | kololog: log does not use derived keys |
ErrOutOfRange | kololog: index out of range |
ErrRestoreMismatch | kololog: restored data does not match the signed head or records |
ErrRollback | kololog: snapshot or head is older than a known head or forks from it |
ErrSecretMismatch | kololog: entry secret mismatch |
ErrStorageMismatch | kololog: stored entry does not match its verified record |
ErrStorageNotEmpty | kololog: storage already holds entries |
ErrTooManyKeys | kololog: too many keys in one call |
ErrUnknownEncoding | kololog: unknown value encoding |
ErrWrongLogID | |
ErrWrongValueType | kololog: wrong value type |
Teste os erros com errors.Is, porque a maioria vem envolvida com o índice ou
com um motivo. ErrBadHeadSignature e ErrWrongLogID correspondem a
ErrInvalidHead, e qualquer coisa que não possa ser interpretada corresponde
a ErrMalformed. Um texto cifrado guardado que não abre retorna
ErrMalformedEntry. New e Restore envolvem koloid.ErrInvalidIdentity
para uma identidade nula ou zerada, e New, Restore, NewReplica e
RestoreReplica retornam ErrNoStorage para um armazenamento nulo. Um erro
do armazenamento volta envolvido, então os erros dele continuam acessíveis
com errors.Is.
Referências
- RFC 9162, Certificate Transparency Version 2.0 (Experimental, December 2021).
- Usa: o hash da árvore (2.1.1), as provas de inclusão e de consistência (2.1.3, 2.1.4) e o monitor que guarda todas as entradas (8.2).
- Não implementa: SHA-256 (no lugar dele, BLAKE2b-256) e os timestamps nos heads.
- RFC 7693, The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC) (Informational, November 2015).
- Usa: BLAKE2b com saída de 32 bytes para cada hash.
- Não implementa: o modo MAC com chave.
- RFC 8032, Edwards-Curve Digital Signature Algorithm (EdDSA) (Informational, January 2017).
- Usa: Ed25519ctx (5.1, 8.3), um contexto por codificação assinada.
- Não implementa: Ed25519ph.
- RFC 5869, HMAC-based Extract-and-Expand Key Derivation Function (HKDF) (Informational, May 2010).
- Usa: extract e expand (2.2, 2.3) para as chaves das entradas.
- Não implementa: nada ficou de fora.
- draft-irtf-cfrg-xchacha-03, XChaCha: eXtended-nonce ChaCha and AEAD_XChaCha20_Poly1305 (Internet-Draft, expired, never an RFC).
- Usa: o AEAD de cada frame.
- Não implementa: o compromisso de chave (key commitment), substituído por um compromisso hash no registro assinado.
- Nikitin et al., Reducing Metadata Leakage from Encrypted Files and Communication with PURBs, PETS 2019.
- Usa: o padding Padmé.
- Len, Grubbs and Ristenpart, Partitioning Oracle Attacks, USENIX Security 2021; Albertini et al., How to Abuse and Fix Authenticated Encryption Without Key Commitment, USENIX Security 2022.
- Usa: por que a chave precisa de um compromisso.
- Não implementa: um AEAD com compromisso de chave.
- Boneh and Lipton, A Revocable Backup System, USENIX Security 1996.
- Usa: excluir destruindo a chave.
- Não implementa: a exclusão só vale nos peers que seguem o protocolo.