kolo docsbeta

kolo-blobs

Encrypted, content-addressed file storage. Store a file of any size, read any range of it, and keep it on pinning peers that cannot read it.

On this page

kolo-blobs stores a file's bytes and nothing else: no names, folders or versions. Write cuts a file into chunks at points that depend on its content (FastCDC), encrypts each chunk (AES-GCM, NIST SP 800-38D) under keys derived by HKDF (RFC 5869) from a random key for that file, builds a Merkle tree over them and returns the blob's ID, the SHA-256 (FIPS 180-4) hash of the tree's root. Open returns a reader that checks every chunk against the tree while it streams, and reads any range by fetching only the chunks that cover it. With NewLogBackend, a blob's pieces are entries of a kolo-store log, so they travel with kolo-sync and rest on kolo-pin pinning peers, which hold only ciphertext and never a key. The Go package is named koloblobs.

All steps

From a file to a blob ID

A blob is a file's bytes only. Names, folders and versions belong to the layer above, such as kolo-files.

  1. Write cuts the file into chunks where its content says so: at least 256 KiB, about 1 MiB on average. The cut points also depend on the file key, so they differ between keys.
  2. Each chunk becomes one object: a 32-byte content MAC, then the chunk sealed with AES-256-GCM under a key derived from the file key and the content. The object's SHA-256 hash is its name.
  3. A tree lists every object's hash and size, up to 256 children a node. A file of up to 256 chunks needs a single root above them.
  4. The root also commits to the file key. The blob ID is the SHA-256 hash of the root object, so it names every byte of the file under that key.
  5. A new version written with the same key cuts the same chunks away from the edit. Only the chunk around it and a new root are stored; the other objects are shared.

Install

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

Builds with CGO_ENABLED=0 for a pure Go binary. Share files between two terminals sends a file from one peer to another with a share code, step by step.

Quick start

This program stores a 20 MB file in a kolo-store log on disk, in a temporary directory. It reads 16 bytes from the middle back, then stores an edited version under the same key.

main.go
package main

import (
	"bytes"
	"context"
	"fmt"
	"io"
	"log"
	"math/rand/v2"
	"os"
	"path/filepath"

	koloblobs "github.com/ciranda-dev/kolo-blobs"
	koloid "github.com/ciranda-dev/kolo-id"
	kolostore "github.com/ciranda-dev/kolo-store"
)

func main() {
	dir, err := os.MkdirTemp("", "kolo-blobs")
	if err != nil {
		log.Fatal(err)
	}
	defer os.RemoveAll(dir)
	ctx := context.Background()

	// A kolo-store log on disk holds the blob, one object per entry.
	db, err := kolostore.OpenPebble(filepath.Join(dir, "store"))
	if err != nil {
		log.Fatal(err)
	}
	st := kolostore.New(db)
	defer st.Close()
	me, err := koloid.Generate()
	if err != nil {
		log.Fatal(err)
	}
	l, err := st.Create(me)
	if err != nil {
		log.Fatal(err)
	}
	blobs := koloblobs.New(koloblobs.NewLogBackend(l))

	// A 20 MB file under a new key. The key and the ID are what a reader needs.
	file := make([]byte, 20_000_000)
	rand.NewChaCha8([32]byte{1}).Read(file)
	key := koloblobs.NewKey()
	id, err := blobs.Write(ctx, key, bytes.NewReader(file))
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("stored %d bytes as %d log entries\n", len(file), l.Len())

	// A range read fetches and checks only the chunk under it and the tree above it.
	r, err := blobs.Open(ctx, id, key)
	if err != nil {
		log.Fatal(err)
	}
	part, err := io.ReadAll(io.NewSectionReader(r, 12_000_000, 16))
	r.Close()
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("bytes 12000000 to 12000016 match: %v\n", bytes.Equal(part, file[12_000_000:12_000_016]))

	// An edited version under the same key shares every chunk away from the edit.
	before := l.Len()
	edited := append(append(append([]byte{}, file[:10_000_000]...), "an insertion"...), file[10_000_000:]...)
	if _, err := blobs.Write(ctx, key, bytes.NewReader(edited)); err != nil {
		log.Fatal(err)
	}
	fmt.Printf("the edited version added %d entries\n", l.Len()-before)
}

It prints:

Text
stored 20000000 bytes as 17 log entries
bytes 12000000 to 12000016 match: true
the edited version added 2 entries

The first number was 17, 18 or 19 in six runs, since the chunk boundaries depend on the random key: the chunks plus one root. The edited version adds the chunk around the insertion and a new root.

API reference

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

Package koloblobs · github.com/ciranda-dev/kolo-blobs · v0.1.0

Package koloblobs stores files as encrypted, content-addressed blobs for Kolo: the content layer under kolo-files, with no names, folders or versions.

Write cuts a file into content-defined chunks, encrypts each under keys derived from a random per-file key, builds a Merkle tree over them and returns the blob's ID, the hash of the tree's root. Open returns a Reader that checks every chunk against the tree while it streams, and reads any range by fetching only the chunks that cover it. Objects live in a Backend; LogBackend keeps them as kolo-log entries, so blobs travel with kolo-sync and rest on kolo-pin pinning peers, which hold only ciphertext and never a key.

Experimental: the API may change before v1.0.0.

Constants

const (
	// KeySize is the size in bytes of a file key.
	KeySize = 32
	// HashSize is the size in bytes of an object hash and a content ID.
	HashSize = sha256.Size
	// MaxObjectSize is the largest object, the largest kolo-log entry value that kolo-sync carries.
	MaxObjectSize = 4128764
	// ObjectOverhead is what encryption adds to a chunk or node: a 32-byte content MAC and a 16-byte tag.
	ObjectOverhead = 48
	// MaxChunkSize is the largest chunk of plaintext, so that its object is at most MaxObjectSize.
	MaxChunkSize = MaxObjectSize - ObjectOverhead
	// MinChunkSize is the smallest chunk the chunker cuts; only a blob's last chunk can be smaller.
	MinChunkSize = 256 << 10
	// Fanout is the most children a tree node lists.
	Fanout = 256
	// MaxHeight is the most node levels above the chunks; 256^6 chunks of MinChunkSize exceed MaxSize.
	MaxHeight = 6
	// MaxSize is the largest blob in bytes, the largest offset of io.Seeker.
	MaxSize = math.MaxInt64
)

Variables

var (
	// ErrInvalidArgument means a nil store, backend, log, source, context or function, a negative or
	// out-of-range offset, an unknown whence, or a Put whose hash is not the object's.
	ErrInvalidArgument = errors.New("koloblobs: invalid argument")
	// ErrNotFound means the backend does not have an object of the blob.
	ErrNotFound = errors.New("koloblobs: object not found")
	// ErrCorrupt means an object does not match its hash, does not decrypt or breaks a tree rule.
	ErrCorrupt = errors.New("koloblobs: object does not verify")
	// ErrWrongKey means the blob's root does not open under the key, or commits to another key.
	ErrWrongKey = errors.New("koloblobs: wrong key for this blob")
	// ErrTooLarge means a source longer than MaxSize, or an object over MaxObjectSize.
	ErrTooLarge = errors.New("koloblobs: too large")
	// ErrReadOnly means Put on a RemoteBackend, or on a LogBackend whose log cannot append.
	ErrReadOnly = errors.New("koloblobs: backend is read-only")
	// ErrClosed means a Read, ReadAt or Seek on a closed Reader.
	ErrClosed = errors.New("koloblobs: reader closed")
)

Types

type Backend

type Backend interface {
	// Get returns the object stored under h, or an error wrapping ErrNotFound. The caller does not modify it.
	// A Get that waits on the network returns when ctx is done.
	Get(ctx context.Context, h Hash) ([]byte, error)
	// Put stores obj under h, its SHA-256, atomically; an object already stored is not stored again. Put must not keep obj.
	Put(ctx context.Context, h Hash, obj []byte) error
}

Backend holds objects by hash. Implementations must be safe for concurrent use.

type FetchFunc

type FetchFunc func(ctx context.Context, index uint64) ([]byte, error)

FetchFunc returns the value of a content-log entry, checked by the transport; deleted or keyless entries wrap kololog.ErrDeleted or kololog.ErrKeyUnavailable.

type Hash

type Hash [HashSize]byte

Hash is the SHA-256 of an object, the name a Backend stores it under.

func (Hash) String
func (h Hash) String() string

String returns the hash as lowercase hex.

type ID

type ID [HashSize]byte

ID is a blob's content ID: the hash of its root object.

func (ID) String
func (id ID) String() string

String returns the ID as lowercase hex.

type Key

type Key [KeySize]byte

Key is a file key, for one file and its versions only; it formats and logs as [redacted].

func NewKey
func NewKey() Key

NewKey returns a random file key; use a new one for each file.

func (Key) Format
func (Key) Format(f fmt.State, _ rune)

Format writes [redacted] for every verb, so no fmt verb prints the key.

func (Key) LogValue
func (Key) LogValue() slog.Value

LogValue returns [redacted].

func (Key) MarshalJSON
func (Key) MarshalJSON() ([]byte, error)

MarshalJSON returns "[redacted]"; store a key only in a binary encoding.

func (Key) String
func (Key) String() string

String returns [redacted].

type LocateFunc

type LocateFunc func(h Hash) (uint64, bool)

LocateFunc returns the content-log index of the object h, or false if it does not know it.

type Log

type Log interface {
	Len() uint64
	Get(index uint64) ([]byte, error)
	EntryInfo(index uint64) (kololog.EntryInfo, error)
}

Log is what a LogBackend reads: a kolo-store or kolo-log log or replica. One with an Append(v any) (uint64, error) method, such as a log, can also be written to. Get and EntryInfo must be safe for concurrent use: a LogBackend reads several entries at once when it indexes a log.

type LogBackend

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

LogBackend keeps objects as entries of a log, one per entry, indexed by hash on first use; it is safe for concurrent use.

func NewLogBackend
func NewLogBackend(l Log) *LogBackend

NewLogBackend returns a Backend on l. Put appends to l if l has an Append method, and returns ErrReadOnly otherwise.

func (LogBackend) Get
func (b *LogBackend) Get(ctx context.Context, h Hash) ([]byte, error)

Get returns the object stored under h, or ErrNotFound. Entries that are deleted or whose kolo-log key is not here cannot be read, and their objects are not found. ctx bounds the index scan.

func (LogBackend) Index
func (b *LogBackend) Index(ctx context.Context, h Hash) (uint64, error)

Index returns the entry index of the object h in the log, or an error wrapping ErrNotFound; a deleted entry is not found. ctx bounds the index scan.

func (LogBackend) Put
func (b *LogBackend) Put(ctx context.Context, h Hash, obj []byte) error

Put appends obj as a new entry unless the log already holds it live. It returns ErrInvalidArgument if h is not the SHA-256 of obj and ErrTooLarge over MaxObjectSize. ctx bounds the index scan.

type Reader

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

Reader reads one blob as an io.Reader, io.ReaderAt and io.Seeker, checking every object before returning its bytes; it is safe for concurrent use, one call at a time.

func (Reader) Close
func (r *Reader) Close() error

Close clears the reader's key material and chunk; later reads return ErrClosed. Closing twice is fine.

func (Reader) Read
func (r *Reader) Read(p []byte) (int, error)

Read reads from the current offset and advances it.

func (Reader) ReadAt
func (r *Reader) ReadAt(p []byte, off int64) (int, error)

ReadAt reads len(p) bytes from offset off, or up to the end of the blob with io.EOF.

func (Reader) Seek
func (r *Reader) Seek(offset int64, whence int) (int64, error)

Seek sets the offset of the next Read, as io.Seeker; an offset past the end reads io.EOF.

func (Reader) Size
func (r *Reader) Size() int64

Size returns the blob's size in bytes.

type RemoteBackend

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

RemoteBackend reads objects from a content log on another peer, one entry per object; it is read-only and safe for concurrent use if fetch and locate are.

func NewRemoteBackend
func NewRemoteBackend(fetch FetchFunc, locate LocateFunc) *RemoteBackend

NewRemoteBackend returns a Backend that finds an object's entry with locate and gets it with fetch.

func (RemoteBackend) Get
func (b *RemoteBackend) Get(ctx context.Context, h Hash) ([]byte, error)

Get fetches the entry holding h; an unknown object or a deleted or keyless entry is ErrNotFound.

func (RemoteBackend) Put
func (b *RemoteBackend) Put(context.Context, Hash, []byte) error

Put returns ErrReadOnly: objects are written on the peer that owns the content log.

type Stats

type Stats struct {
	BytesWritten   uint64 // plaintext bytes Write read from its sources
	BytesRead      uint64 // plaintext bytes returned by Readers
	ObjectsPut     uint64 // objects passed to Backend.Put
	ObjectsFetched uint64 // objects returned by Backend.Get
	Rejected       uint64 // fetched objects that failed a check
}

Stats are a Store's totals since New.

type Store

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

Store writes and reads blobs on a Backend; it is safe for concurrent use.

func New
func New(b Backend) *Store

New returns a Store on b.

func (Store) Objects
func (s *Store) Objects(ctx context.Context, id ID, key Key) iter.Seq2[Hash, error]

Objects lists the hash of every object of the blob id, root first, fetching the nodes but not the chunks; it stops at the first error, yielded with a zero Hash.

func (Store) Open
func (s *Store) Open(ctx context.Context, id ID, key Key) (*Reader, error)

Open returns a Reader for the blob id under key after checking the root: ErrWrongKey for another key, ErrNotFound if the backend lacks it. The Reader passes ctx to every Backend.Get it makes.

func (Store) Stats
func (s *Store) Stats() Stats

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

func (Store) Write
func (s *Store) Write(ctx context.Context, key Key, src io.Reader) (ID, error)

Write reads src to its end, stores it as a blob under key and returns its ID; the same bytes and key give the same ID, so a Write killed part way is resumed by running it again. It checks ctx between chunks.

Chunking, sealing and Put run as a pipeline, so a Write uses several cores and a slow Put does not hold up the chunker. Put is still called from one goroutine, one object at a time in chunk order, so the objects, the tree and the ID are those of a Write that does everything in turn. A panic of src or of Put reaches the caller of Write.

Good to know

The same bytes under the same key give the same ID and store no new object. So a Write that was stopped or killed is resumed by running it again with the same key and source, and a new version written with the file's key stores only the chunks that changed. kolo-store appends each entry atomically and syncs it, so a killed write leaves whole entries only. The cost of a resume is reading and hashing the source again. After a failure or a cancel, Write stops reading the source at once and seals no more chunks. A panic of the source, of the backend's Put or of the sealing reaches the caller of Write on its own goroutine, with the same value, so the caller may recover it; the goroutines of the write are ended and its buffers cleared.

All steps

Reading and checking a range

Every object is checked against the hash its parent lists, so a read returns the right bytes or an error, never wrong bytes.

  1. Open fetches the root by the blob ID, checks that its SHA-256 hash is the ID, decrypts it and checks the key commitment. Another key is ErrWrongKey.
  2. ReadAt walks down one node per level, chosen by the child sizes its parent lists, and checks each node against the hash its parent gives.
  3. It fetches only the chunks that cover the range. Each one is checked against its hash, decrypted, and its content MAC computed again before a byte is returned.
  4. A missing or altered object stops the read with ErrNotFound or ErrCorrupt. The bytes before it come back with the error, never a wrong byte.
  5. Objects come from a Backend: a local kolo-store log, a replica pulled with kolo-sync, or entries fetched one by one from another peer.

A Reader is an io.Reader, io.ReaderAt and io.Seeker, safe for concurrent use. Concurrent ReadAt calls run one at a time, since the lock is held while a chunk is fetched, so use one Reader per goroutine to fetch in parallel. ReadAt fetches one node per tree level and the chunks that cover the range, and io.NewSectionReader(r, start, length) gives a range as a stream. Every object is checked before any of its bytes are returned; a read that hits a bad or missing object returns the bytes before it and the error. The reader passes the context given to Open to every Backend.Get, so ending it ends the reads with ctx.Err().

NewLogBackend keeps each object as one entry of a kolo-store or kolo-log log or replica. Its first Get, Put or Index reads and decrypts every live entry of the log that has its key, once, under the backend's lock, to index the entries by object hash. That first scan costs a read of the whole log, not of the blob, and the context ends it with ctx.Err(); later calls read only the entries added since. Entries without a key are read again, in windows of 64 entries on up to 4 goroutines, only when a Get or Index misses, never on a Put. For range reads on a large log without that scan, use NewRemoteBackend with a fetch that reads the log (Get) and a locate from an object table the writer made with Objects and Index.

NewRemoteBackend(fetch, locate) reads a content log on another peer, one entry per object, for example through kolo-sync's ranged Fetch with each entry's inclusion proof. A range read through it fetches the root, one node per level and the chunks under the range. An entry the peer serves without its kolo-log key, as a pinning peer does, reads as ErrNotFound unless the reader holds that key. A blob on a pinning peer reads in two ways: pull its log into a replica and get the entry keys from one of the owner's devices; or, for range reads while the owner is offline, get the owner's head and the entry keys of the blob's entries once with kolo-sync's FetchHead and FetchKeys, keep them, and wire fetch to kolo-sync's FetchWithKeys against that head. kolo-sync then opens each entry locally with the held key, after the stream is closed; no key reaches the pinning peer, which holds none. A held key that does not match is kolosync.ErrKeyMismatch, returned wrapped. The README has the code.

Limits

All of these are format constants, not settings: each follows from something outside the library, and changing one would change every ID. None is a limit on file size below MaxSize; a file takes as many chunks and nodes as it needs.

  • MaxObjectSize, 4,128,764 bytes: the largest kolo-log entry value that kolo-sync carries, so every object syncs. A reader checks an object's size against it before it hashes or decrypts.
  • ObjectOverhead, 48 bytes per object: the content MAC (32) and the GCM tag (16).
  • MaxChunkSize, 4,128,716 bytes, MaxObjectSize minus ObjectOverhead. A chunk is cut there when no cut point is found.
  • MinChunkSize, 262,144 bytes (256 KiB). Only a blob's last chunk is smaller. Chunks average about 1 MiB.
  • Fanout, 256 children per node. A full node is about 10 KiB.
  • MaxHeight, 6 levels: 256^6 chunks of the minimum size are more than MaxSize, so no honest tree is taller, and a reader refuses a taller one.
  • MaxSize, 2^63 - 1 bytes, the largest offset of Go's io.Seeker. A longer source is ErrTooLarge.
  • KeySize and HashSize, 32 bytes. ID.String() and Hash.String() are lowercase hex.
  • Memory: Write runs the chunker, 2 sealing goroutines and the backend's Put as a pipeline, so it holds at most 5 chunks in flight, each a plaintext buffer and an object buffer, plus the chunker's buffer and one pending node per tree level. A Reader holds the nodes on the path to its last chunk and that chunk's plaintext. Neither depends on the file size: a generated 10 GiB file is written and read back with a 54 MiB peak heap and an 84 MiB peak resident size, and 82 MiB and 173 MiB through a kolo-store log on Pebble, under GOMEMLIMIT=64MiB. A LogBackend adds its index, which grows with the log and is not bounded: about 140 bytes of heap per entry (142 measured for 1 million entries), so a log of 10 million entries from a peer you do not trust costs about 1.4 GB once indexed.
  • Objects is the one operation whose work follows the size the root claims rather than the bytes asked for: about one hash per MinChunkSize of claimed size, up to about 2^45 for MaxSize, with one node fetch per 256. Give it a context with a deadline for blobs from writers you do not trust.

Security

  • Encryption is deterministic encryption with a content-derived key. HKDF-SHA256 (RFC 5869) derives three subkeys from the file key: a content MAC key, an object key and the table the chunker uses. An object is a 32-byte HMAC-SHA256 (RFC 2104) of its type label and plaintext under the content MAC key, followed by the plaintext sealed with AES-256-GCM (NIST SP 800-38D) under a key that is the HMAC of that value under the object key, with a fixed nonce. Each derived key encrypts one plaintext only. On open the reader computes the MAC again and refuses a mismatch with ErrCorrupt, so every plaintext has exactly one object.
  • Dedup stays inside one key. Without the key nobody can compute an object, its hash or its cut points for a guessed file, so a holder of the objects cannot test whether a known file is stored. Different keys never share an object.
  • The root holds SHA-256("kolo-blobs/key/v0" ‖ key), checked on open, so an ID opens under one key only, and every other object is fixed by its hash in the tree: one ID gives one plaintext. Each object type (chunk, node, root) has its own label, and an object of one type never opens as another.
  • The ID, the SHA-256 of the root object, commits to the key, the size, the tree shape and every chunk, comes from the content and the key only, and reveals nothing about the content without the key.
  • What storage sees: on a raw Backend, each object's exact size (its chunk's size plus 48 bytes), repeated hashes and the number of objects per write. Only LogBackend pads: each object is a kolo-log entry, encrypted again under an entry key the storage peer lacks and padded by kolo-log, so a pinning peer sees entry counts and padded sizes, and how many new entries each version adds. A peer that serves Fetch or FetchWithKeys to a RemoteBackend sees the reader's identity, which entries it fetches and when, their sizes and the size of the head it checks against, so it learns the tree's shape, which blob is opened and which ranges of it are read, and where a read stops. It never learns content or keys.
  • Chunk sizes come from a table derived from the file key, so cut points cannot be matched across keys. Under one key, someone who knows or chooses part of a file and sees the chunk sizes may learn enough of that table to test guesses about other content under the key from its chunk sizes.
  • Two layers of keys on a log: kolo-log's entry keys protect each entry in transit and on every peer, and travel only to peers with kolo-sync Keys access; the file key protects the blob and travels with the ID to those who may read it. A pinning peer has neither. The library's test dumps a pinning peer's store and finds no file key, subkey, entry key, blob object or plaintext.
  • A Key value, a pointer to one or one in an exported struct field prints and logs as [redacted] with fmt, slog and encoding/json. In an unexported struct field, fmt's %v and %+v and slog's text handler print the raw bytes, so never keep a key in an unexported field of a struct that is printed or logged. key[:] gives the bytes; keep them only in an encrypted form. No error carries key bytes or content.
  • Reader.Close clears the reader's subkeys and chunk buffer. The AES ciphers' internal copies of object keys stay in memory until the runtime reuses them, as with kolo-log.
  • Deletion is best effort, and this library never deletes. A layer above that removes a blob deletes its log entries with kolo-log's Delete, which holds on peers that follow the protocol; a peer that already has the entry key can keep the data. See Deletion. Versions written under one key, and identical rewrites, share entries, so deleting one version's Objects breaks the others: delete only the entries that no kept blob under the key lists. The objects of a write that was never completed stay in the log until they are deleted.

Building an update system on it

These are facts about the library, not a feature: kolo-blobs has no update system.

  • Every object is checked against its hash before its bytes are returned, so reading a blob to the end checks all of it against its ID.
  • A range read fetches only the chunks that cover the range, plus one tree node per level.
  • Equal content dedups only under the same key. kolo-files gives each file one key, so new content written to the same path in a kolo-files volume reuses its unchanged chunks.
  • A pinning peer serves ciphertext only.

Known limits

  • Without AES instructions in the CPU (some 32-bit or embedded CPUs), Go's software AES is slower.
  • LogBackend's first scan reads every live keyed entry of the log, so on a large log a first range read costs that scan. RemoteBackend with an object table avoids it.
  • All tests run on 127.0.0.1. Experimental. The API may change before v1.0.0.

Errors

ErrorMessage
ErrClosedkoloblobs: reader closed
ErrCorruptkoloblobs: object does not verify
ErrInvalidArgumentkoloblobs: invalid argument
ErrNotFoundkoloblobs: object not found
ErrReadOnlykoloblobs: backend is read-only
ErrTooLargekoloblobs: too large
ErrWrongKeykoloblobs: wrong key for this blob

Test errors with errors.Is; none carries key bytes or content. ErrNotFound also covers a deleted entry and one without its key for a LogBackend, and an object that locate does not know or that fetch reports deleted or keyless for a RemoteBackend. A root that does not open under the key, or commits to another key, is ErrWrongKey, and so is a non-root object given as an ID. Errors from the source and the backend come back wrapped, and Write returns ctx.Err() when the context ends.

References