hashchain

package module
v0.1.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Oct 20, 2026 License: MIT Imports: 17 Imported by: 0

README

hashchain

An append-only, tamper-evident log for Go. Every entry commits to the hash of the entry before it, so changing, removing, inserting or reordering a stored entry breaks the chain at a point that verification reports exactly.

  • Canonical, versioned binary encoding (no JSON canonicalization pitfalls)
  • SHA-256 by default, any crypto.Hash, optional HMAC key for keyed chains
  • Genesis entry that binds the chain to its hash configuration and name
  • Full, range and checkpoint verification, streaming with O(1) memory
  • Fork-free concurrent appends, including across processes on Postgres
  • In-memory store and a Postgres store (database/sql, works with pgx and lib/pq)
  • No dependencies outside the standard library (test-only: pgx, lib/pq)
go get github.com/Aquilabot/hashchain

Requires Go 1.25 or later. The Postgres store requires PostgreSQL 14 or later.

Example

import (
	"github.com/Aquilabot/hashchain"
	"github.com/Aquilabot/hashchain/pgstore"
	_ "github.com/jackc/pgx/v5/stdlib"
)

db, _ := sql.Open("pgx", os.Getenv("DATABASE_URL"))
if err := pgstore.Migrate(ctx, db); err != nil { ... }

store, _ := pgstore.New(db, "billing-audit")       // one table, many chains
chain, _ := hashchain.New(store, hashchain.Config{
	Key:  secretKey,                                // optional, enables HMAC
	Name: "billing-audit",                          // committed to by the genesis entry
})

entry, err := chain.Append(ctx, hashchain.Record{
	Kind:    "invoice.paid",
	Payload: []byte(`{"invoice":"inv_1","amount":4200}`),
})

report, err := chain.Verify(ctx)
var broken *hashchain.VerifyError
if errors.As(err, &broken) {
	// broken.Seq is the first broken position, broken.Reason one of
	// ErrHashMismatch, ErrBrokenLink, ErrSequence, ErrGenesis, ErrTruncated,
	// ErrCheckpointMismatch, ErrUnknownVersion, ErrEncoding.
	log.Printf("audit log tampered at seq %d: %v", broken.Seq, err)
}

// Publish the head somewhere the database operator cannot rewrite.
head, _ := chain.Head(ctx)                          // {Seq, Hash}
API
Call What it does
New(store, Config) Configure a chain over a Store.
Append(ctx, Record) Append one entry, return it with Seq, Time, PrevHash, Hash.
AppendBatch(ctx, ...Record) Append several entries in one store transaction.
Head(ctx) Last Checkpoint{Seq, Hash}. Reads the stored hash; nothing is rehashed.
Verify(ctx) Verify from the start of the chain to the current head.
VerifyRange(ctx, from, to) Verify from..to, trusting the stored entry at from-1 as the predecessor.
VerifyFrom(ctx, checkpoint) Verify from a trusted checkpoint to the head; detects rewrites and truncation below it.

A Store has three methods: Append(ctx, build), Head(ctx), Scan(ctx, from, to, fn). Append must call build with the current head while holding exclusive write access to the chain and persist the result atomically; that is the whole concurrency contract.

Threat model

hashchain makes tampering evident. It does not prevent it.

Detected by Verify, with the first broken sequence number:

Tampering Reported as
An entry's kind, payload, time or stored hash is edited ErrHashMismatch at that entry
An entry is edited and its hash recomputed (unkeyed chain) ErrBrokenLink at the next entry
An entry is edited and rehashed on a keyed chain without the key ErrHashMismatch at that entry
An entry is deleted from the middle ErrSequence (or ErrBrokenLink if later entries are renumbered)
Two entries swap positions ErrBrokenLink or ErrSequence
A forged entry is inserted ErrBrokenLink, ErrHashMismatch or ErrSequence
The genesis entry is removed or replaced, or the chain is checked with the wrong hash function, key or name ErrGenesis at seq 0

Detected only with an external anchor (a checkpoint stored outside the attacker's reach, checked with VerifyFrom):

  • Truncation: deleting the newest entries leaves a shorter chain that is still internally valid. VerifyFrom reports ErrTruncated.
  • Whole-chain rewrite: an attacker who can write the store and knows the hash configuration (and the key, for keyed chains) can recompute every hash from the genesis entry on. Nothing inside the store can reveal that. VerifyFrom reports ErrCheckpointMismatch.

Not detected:

  • An attacker who controls both the store and every anchor you check against.
  • Entries that were never written. A compromised application can simply not log an event, or log a false one; the chain proves the log was not altered after the fact, not that it is true.
  • Anything an attacker with the HMAC key can do on a keyed chain: the key adds protection only against attackers who can write the database but cannot read the application's secrets.

Recommendation: periodically publish the head checkpoint (Head) to a place the database operator cannot rewrite, such as a different system's log, a WORM bucket (S3 Object Lock), a signed message, a git commit, or a public transparency log, and verify with VerifyFrom against the latest anchor. How often you anchor bounds how much history can be silently truncated or rewritten.

Encoding (version 1)

Each entry's digest is H(preimage), or HMAC-H(key, preimage) for keyed chains, where preimage is:

Field Size Encoding
domain tag 10 ASCII hashchain followed by 0x00
version 1 0x01
seq 8 uint64, big-endian
time 8 int64, big-endian, Unix time in microseconds, UTC
kind length 4 uint32, big-endian
kind n UTF-8 bytes
payload length 4 uint32, big-endian
payload m raw bytes
prev hash length 1 uint8
prev hash k raw digest bytes (empty for the first entry)

Entry.Hash itself is never part of the preimage. A golden test vector pins this layout (TestV1GoldenVector).

Why length-prefixed binary instead of canonical JSON. The payload is opaque bytes, so it needs no escaping, no Unicode normalization and no number formatting rules; every entry has exactly one encoding, which DecodeV1 enforces by rejecting any input AppendV1 would not produce. JSON canonicalization (RFC 8785) would put float formatting, string escaping and key ordering inside the security boundary, and those are the usual sources of "same data, different hash" bugs. Binary framing is also fast: encoding a typical entry takes about 13 ns with no allocations. Applications that want JSON can put JSON in the payload.

Time precision. Append converts times to UTC and truncates them to whole microseconds before hashing, because PostgreSQL timestamptz stores microseconds. Hashing a finer precision than the store keeps makes entries unverifiable after a round trip, a bug that is easy to ship and hard to notice until the first audit.

Kind must be non-empty, valid UTF-8 and free of NUL bytes (Postgres text rejects NUL).

Genesis. Unless Config.NoGenesis is set, the first append also writes entry 0 with kind hashchain.genesis, an empty prev hash and this payload (newline-separated, fixed order):

hashchain-genesis/1
hash=SHA-256
keyed=true
codec=1
name="billing-audit"

Verifying with a different hash function, key, codec or name fails at seq 0 with ErrGenesis, and entries cannot be spliced between chains with different names. NoGenesis exists for chains that were started without a genesis entry; their first entry is seq 1 with an empty prev hash.

Versioning and legacy formats. Entry.Version selects a Codec. New entries use Config.Codec (default V1Codec); Config.ExtraCodecs lets a chain verify entries written with older encodings, so moving to a new encoding never requires rewriting history. A codec whose stored form cannot reproduce the original preimage exactly (for example, a legacy format that hashed nanosecond timestamps that the database then rounded) can implement HashMatcher to decide matches itself.

Postgres

err := pgstore.Migrate(ctx, db)                          // or run the SQL yourself
ddl, _ := pgstore.MigrationSQL(pgstore.WithTable("audit_chain"))
store, _ := pgstore.New(db, "chain-name", pgstore.WithTable("audit_chain"))

The migration lives in pgstore/migrations/0001_hashchain_entries.sql: one table, primary key (chain, seq), and a statement-level trigger that rejects UPDATE, DELETE and TRUNCATE.

Concurrent appends. Append runs in a READ COMMITTED transaction:

  1. SELECT pg_advisory_xact_lock(key), where key is FNV-1a-64 of "hashchain\0" + table + "\0" + chain (pgstore.LockKey);
  2. read the head (ORDER BY seq DESC LIMIT 1 on the primary key);
  3. compute and insert the new entries (multi-row INSERT, 500 rows per statement);
  4. commit, which releases the lock.

Writers to the same chain are serialized across all connections and processes; different chains do not block each other. The lock is transaction-scoped, so it works behind PgBouncer in transaction pooling mode (session-level advisory locks would not). The primary key is a backstop: two entries can never share a sequence number, so even a writer that skips the lock cannot fork the chain, it just fails. READ COMMITTED is required: under REPEATABLE READ the snapshot would be taken before the lock was granted and the head read could be stale.

Verification reads use keyset pagination (WHERE seq >= $n ORDER BY seq LIMIT 1000, configurable with WithPageSize), so memory stays bounded by one page and no long-lived cursor or transaction is held.

Hardening. Grant the application role only SELECT and INSERT on the table. The trigger stops application bugs, not the table owner or a superuser, who can disable it; the hashes and external anchors are what make their changes visible.

Performance

Measured on an AMD Ryzen 7 5800X3D, Go 1.27.2, linux/amd64, with go test -bench . -benchtime 2s -count 3 (range across the three runs). Postgres is 17 (postgres:17-alpine) in Docker on the same machine, default durability settings (fsync=on, synchronous_commit=on), so Postgres append latency is dominated by the commit flush on this disk.

Benchmark Result
Encode one v1 preimage 12–15 ns, 0 allocs
In-memory Append 0.8–1.3 µs/op
In-memory AppendBatch of 100 0.50–0.58 µs/entry
In-memory Verify, 10k entries, SHA-256 179–217 ns/entry, 12 allocs total
In-memory Verify, 10k entries, HMAC-SHA-256 279–324 ns/entry
Postgres Append (one writer) 6.4–7.4 ms/op
Postgres Append (64 goroutines, 32 connections, one chain) 6.8–7.2 ms/op
Postgres AppendBatch of 100 78–83 µs/entry
Postgres Verify, 10k entries 1.33–1.41 µs/entry

Appends to one chain are serialized by design, so concurrent writers do not increase throughput; batch when you can. Reads never rehash: Head returns the stored hash and only Verify* recomputes digests.

Testing

go test -race ./...                                 # starts postgres:17-alpine with Docker if available
HASHCHAIN_TEST_DSN=postgres://... go test ./...     # use an existing server instead
go test -run '^$' -fuzz FuzzV1RoundTrip -fuzztime 30s .
go test -run '^$' -fuzz FuzzV1Decode -fuzztime 30s .

Postgres tests are skipped when neither Docker nor HASHCHAIN_TEST_DSN is available. The suite includes a tamper matrix (edit, rehash, delete, reorder, insert, truncate, whole-chain rewrite) against the in-memory store and the same attacks through SQL against Postgres, concurrent appends from several connection pools, and fuzzing of the encoder and decoder.

License

MIT. See LICENSE.

Documentation

Overview

Package hashchain implements an append-only, tamper-evident log in which every entry commits to the hash of the entry before it.

A Chain computes and verifies hashes; a Store persists entries. The package ships an in-memory Store (NewMemoryStore) and a Postgres Store in the pgstore subpackage. Entries are hashed over a canonical, versioned binary encoding described in Codec and in the README.

Example
package main

import (
	"context"
	"errors"
	"fmt"

	"github.com/Aquilabot/hashchain"
)

func main() {
	ctx := context.Background()
	chain, err := hashchain.New(hashchain.NewMemoryStore(), hashchain.Config{
		Key:  []byte("load-me-from-a-secret-store"), // optional: keyed (HMAC) chain
		Name: "billing-audit",
	})
	if err != nil {
		panic(err)
	}

	e, err := chain.Append(ctx, hashchain.Record{Kind: "invoice.paid", Payload: []byte(`{"invoice":"inv_1"}`)})
	if err != nil {
		panic(err)
	}
	fmt.Println("appended seq", e.Seq)

	report, err := chain.Verify(ctx)
	var broken *hashchain.VerifyError
	switch {
	case errors.As(err, &broken):
		fmt.Println("tampered at seq", broken.Seq, broken.Reason)
	case err != nil:
		panic(err)
	default:
		fmt.Println("verified", report.Entries, "entries; head seq", report.Last.Seq)
	}
}
Output:
appended seq 1
verified 2 entries; head seq 1

Index

Examples

Constants

View Source
const GenesisKind = "hashchain.genesis"

GenesisKind is the Kind of the genesis entry written at Seq 0.

View Source
const V1 uint8 = 1

V1 is the version number of the canonical binary encoding.

Variables

View Source
var (
	ErrKindTooLong     = errors.New("hashchain: kind longer than 2^32-1 bytes")
	ErrPayloadTooLong  = errors.New("hashchain: payload longer than 2^32-1 bytes")
	ErrPrevHashTooLong = errors.New("hashchain: prev hash longer than 255 bytes")
	ErrMalformed       = errors.New("hashchain: malformed v1 encoding")
)

Encoding errors.

View Source
var (
	// ErrHashMismatch: the stored hash does not match the recomputed hash.
	// The entry's content or its stored hash was modified.
	ErrHashMismatch = errors.New("hash mismatch")
	// ErrBrokenLink: the entry's PrevHash differs from the previous entry's
	// Hash. An entry was inserted, replaced or rehashed before this one.
	ErrBrokenLink = errors.New("prev hash does not match previous entry")
	// ErrSequence: sequence numbers are not contiguous (deleted, inserted or
	// reordered entries).
	ErrSequence = errors.New("sequence gap or reorder")
	// ErrGenesis: the first entry is not a valid genesis for this chain's
	// configuration (wrong hash function, key, or missing genesis).
	ErrGenesis = errors.New("invalid genesis entry")
	// ErrTruncated: entries that must exist (up to the requested end, or
	// the trusted checkpoint) are missing.
	ErrTruncated = errors.New("chain truncated")
	// ErrCheckpointMismatch: the stored entry at a trusted checkpoint has a
	// different hash than the checkpoint.
	ErrCheckpointMismatch = errors.New("checkpoint hash mismatch")
	// ErrUnknownVersion: no Codec is registered for the entry's version.
	ErrUnknownVersion = errors.New("unknown encoding version")
	// ErrEncoding: the entry could not be encoded (codec error).
	ErrEncoding = errors.New("entry cannot be encoded")
)

Reasons a verification can fail. A *VerifyError wraps exactly one of them, so callers can use errors.Is(err, hashchain.ErrHashMismatch) and so on.

Functions

func AppendV1

func AppendV1(dst []byte, e *Entry) ([]byte, error)

AppendV1 appends the v1 encoding of e (ignoring e.Hash and e.Version) to dst.

Types

type Chain

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

Chain appends and verifies entries of one hash chain stored in a Store. A Chain is safe for concurrent use; fork-freedom across processes is the Store's responsibility (see Store.Append).

func New

func New(store Store, cfg Config) (*Chain, error)

New returns a Chain over store.

func (*Chain) Append

func (c *Chain) Append(ctx context.Context, rec Record) (Entry, error)

Append adds one record to the chain and returns the stored entry.

func (*Chain) AppendBatch

func (c *Chain) AppendBatch(ctx context.Context, recs ...Record) ([]Entry, error)

AppendBatch adds records atomically, in order, under a single store transaction. It is much cheaper per record than repeated Append calls on stores with per-transaction overhead.

func (*Chain) Head

func (c *Chain) Head(ctx context.Context) (Checkpoint, error)

Head returns the checkpoint of the last entry without verifying anything. The zero Checkpoint means the chain is empty.

func (*Chain) Verify

func (c *Chain) Verify(ctx context.Context) (Report, error)

Verify checks every entry from the start of the chain to the head that exists when Verify starts. It streams entries from the store and keeps O(1) memory.

Verify cannot detect that entries were removed from the end of the chain, or that the whole chain was rewritten; compare the returned Last checkpoint with an externally anchored one, or use VerifyFrom.

func (*Chain) VerifyFrom

func (c *Chain) VerifyFrom(ctx context.Context, cp Checkpoint) (Report, error)

VerifyFrom verifies the chain from a trusted checkpoint (for example one previously published to an external anchor) up to the current head. It fails with ErrCheckpointMismatch if the stored entry at cp.Seq does not have cp.Hash, and with ErrTruncated if the chain no longer reaches cp.Seq. The zero Checkpoint verifies the whole chain.

func (*Chain) VerifyRange

func (c *Chain) VerifyRange(ctx context.Context, from, to uint64) (Report, error)

VerifyRange checks entries from..to (inclusive). Entry from-1, if any, is used as the trusted predecessor: its hash is not recomputed but entry from must link to it. When from is the first sequence number of the chain the genesis rules are checked instead. Missing entries up to to are reported as ErrTruncated.

type Checkpoint

type Checkpoint struct {
	Seq  uint64
	Hash []byte
}

Checkpoint identifies a chain state by the sequence number and hash of its last entry. Publishing checkpoints outside the store (external anchoring) is what lets a verifier detect a rewritten or truncated chain.

func (Checkpoint) IsZero

func (c Checkpoint) IsZero() bool

IsZero reports whether c is the empty checkpoint (no entries).

type Codec

type Codec interface {
	// Version is the Entry.Version this codec handles.
	Version() uint8
	// AppendPreimage appends the canonical encoding of e to dst. It must not
	// read e.Hash. The result must be a pure function of the other fields.
	AppendPreimage(dst []byte, e *Entry) ([]byte, error)
}

Codec produces the byte string ("preimage") that is hashed for an entry. Each codec owns one Entry.Version value, so a chain can hold entries written with different encodings and still verify all of them.

type Config

type Config struct {
	// Hash is the digest function. Zero means crypto.SHA256. The function
	// must be linked into the binary (import its package, e.g. crypto/sha512).
	Hash crypto.Hash

	// Key, when non-empty, turns the chain into a keyed chain: every digest
	// is HMAC(Key, preimage) instead of Hash(preimage). Without the key
	// nobody can forge or verify entries.
	Key []byte

	// Codec encodes new entries. Zero means V1Codec.
	Codec Codec

	// ExtraCodecs are additional codecs accepted during verification, for
	// chains that contain entries from older encodings.
	ExtraCodecs []Codec

	// NoGenesis disables the genesis entry: the first application entry
	// gets Seq 1 and an empty PrevHash. Use it only for chains created
	// without one (for example, pre-existing legacy chains); a genesis
	// entry binds the chain to its hash configuration and Name.
	NoGenesis bool

	// Name is committed to by the genesis entry. Two chains with different
	// names cannot have their entries spliced into each other even when
	// they share a key.
	Name string

	// Now returns the current time. Zero means time.Now.
	Now func() time.Time
}

Config configures a Chain. The zero value is valid: SHA-256, unkeyed, v1 encoding, with a genesis entry.

type Entry

type Entry struct {
	// Seq is the position of the entry in the chain. The genesis entry has
	// Seq 0 and the first application entry has Seq 1. Sequence numbers are
	// contiguous.
	Seq uint64
	// Version selects the Codec used to hash the entry.
	Version uint8
	// Time is the append time, in UTC, truncated to whole microseconds.
	Time time.Time
	// Kind is an application-defined label, for example "user.login". It must
	// be valid UTF-8, non-empty and free of NUL bytes.
	Kind string
	// Payload is opaque application data. The chain never interprets it.
	Payload []byte
	// PrevHash is the Hash of the entry at Seq-1, or empty for the first
	// entry of the chain.
	PrevHash []byte
	// Hash is the digest of the entry's canonical encoding.
	Hash []byte
}

Entry is one record of a chain as it is persisted.

func DecodeV1

func DecodeV1(b []byte) (Entry, error)

DecodeV1 parses a v1 preimage. It rejects anything that AppendV1 would not produce, including trailing bytes. Slices in the result alias b. Decoded times are in UTC.

func (*Entry) Clone

func (e *Entry) Clone() Entry

Clone returns a deep copy of e.

type HashMatcher

type HashMatcher interface {
	MatchHash(e *Entry, sum func(preimage []byte) []byte) (bool, error)
}

HashMatcher is an optional interface for codecs whose stored form cannot always reproduce the exact preimage, for example a legacy format that hashed nanosecond timestamps but persisted microseconds. When a codec implements it, verification calls MatchHash instead of comparing sum(AppendPreimage(e)) with e.Hash.

sum hashes a preimage with the chain's configured hash (and key) and returns a digest that is only valid until the next call.

type MemoryStore

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

MemoryStore is a Store backed by a slice. It is safe for concurrent use and is intended for tests, examples and short-lived processes.

func NewMemoryStore

func NewMemoryStore() *MemoryStore

NewMemoryStore returns an empty MemoryStore.

func (*MemoryStore) Append

func (s *MemoryStore) Append(ctx context.Context, build func(head *Entry) ([]Entry, error)) error

Append implements Store.

func (*MemoryStore) Head

func (s *MemoryStore) Head(ctx context.Context) (*Entry, error)

Head implements Store.

func (*MemoryStore) Len

func (s *MemoryStore) Len() int

Len returns the number of stored entries.

func (*MemoryStore) Scan

func (s *MemoryStore) Scan(ctx context.Context, from, to uint64, fn func(*Entry) error) error

Scan implements Store. Entries appended after Scan starts are not visited.

type Record

type Record struct {
	// Kind is required; see Entry.Kind.
	Kind string
	// Payload is optional opaque data.
	Payload []byte
	// Time is optional. The zero value means "now" (Config.Now). It is
	// converted to UTC and truncated to microseconds before hashing.
	Time time.Time
}

Record is the input to Chain.Append.

type Report

type Report struct {
	// Entries is the number of entries whose hash was recomputed.
	Entries uint64
	// First and Last are the first and last verified entries. Both are zero
	// when nothing was verified.
	First Checkpoint
	Last  Checkpoint
}

Report summarizes a successful verification.

type Store

type Store interface {
	// Append reads the current head (nil when the chain is empty), calls
	// build with it while holding exclusive write access to the chain, and
	// atomically persists the returned entries. The head passed to build is
	// guaranteed to carry Seq and Hash; other fields may be empty. If build
	// returns an error nothing is written and the error is returned.
	Append(ctx context.Context, build func(head *Entry) ([]Entry, error)) error

	// Head returns the last entry, or (nil, nil) when the chain is empty.
	Head(ctx context.Context) (*Entry, error)

	// Scan calls fn for every entry with from <= Seq <= to, in ascending Seq
	// order, stopping at the first error. Implementations should stream
	// rather than load the whole range. The *Entry and its slices are only
	// valid during the call; fn must copy anything it keeps.
	Scan(ctx context.Context, from, to uint64, fn func(*Entry) error) error
}

Store persists the entries of one chain.

Implementations must make Append atomic and mutually exclusive: while one Append runs build and writes its result, no other Append on the same chain (in this process or any other) may observe the old head. That is what keeps the chain from forking under concurrent writers.

type V1Codec

type V1Codec struct{}

V1Codec is the canonical length-prefixed binary encoding (version 1):

"hashchain" 0x00          10 bytes, domain separation tag
version                    1 byte, 0x01
seq                        8 bytes, uint64 big-endian
time                       8 bytes, int64 big-endian, Unix microseconds (UTC)
len(kind)                  4 bytes, uint32 big-endian
kind                       len(kind) bytes, UTF-8
len(payload)               4 bytes, uint32 big-endian
payload                    len(payload) bytes
len(prev_hash)             1 byte
prev_hash                  len(prev_hash) bytes

Every field has exactly one representation, so equal entries always encode to equal bytes and DecodeV1 accepts only canonical input.

func (V1Codec) AppendPreimage

func (V1Codec) AppendPreimage(dst []byte, e *Entry) ([]byte, error)

AppendPreimage implements Codec.

func (V1Codec) Version

func (V1Codec) Version() uint8

Version implements Codec.

type VerifyError

type VerifyError struct {
	// Seq is the sequence number at which the chain breaks: the entry whose
	// check failed, or the expected position of a missing entry.
	Seq uint64
	// Reason is one of the Err* sentinels above.
	Reason error
	// Expected and Actual hold the compared values for hash and link
	// failures (digests), and are nil otherwise.
	Expected, Actual []byte
	// Detail is a human-readable explanation.
	Detail string
	// Err is an underlying error, for example from a Codec.
	Err error
}

VerifyError points at the first entry where verification failed.

func (*VerifyError) Error

func (e *VerifyError) Error() string

func (*VerifyError) Unwrap

func (e *VerifyError) Unwrap() []error

Unwrap lets errors.Is match both the Reason sentinel and Err.

Directories

Path Synopsis
Package pgstore is a PostgreSQL implementation of hashchain.Store built on database/sql.
Package pgstore is a PostgreSQL implementation of hashchain.Store built on database/sql.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL