Why prove the integrity of a log?
In most modern systems, maintaining a log journal allows for tracing actions performed and understanding what happened in the event of an incident. In cybersecurity, we often talk aboutaudit trail.
Logging is an essential building block for any system that handles sensitive data. It serves to diagnose, audit, and respond to incidents. The problem is that, after the database, the second target of an attacker is often the logs themselves: by altering them, they can conceal a compromise or erase any evidence of unauthorised access, which makes detection and response much more difficult.
If these logs can be modified or deleted, then the entire chain of trust becomes debatable.
Furthermore, some standards require these logs to be tamper-proof.
This is the case for NF525 (cash register software certification), but also for the standard
PCI-DSS (payment security) or the
HDS for health data hosts (modelled on the standard
ISO 27001).
Even outside of regulatory constraints, in fields such as health or finance, the ability to guarantee log integrity is no longer a luxury but a necessity.
When designing such a system, three aspects deserve particular attention:
Integration complexity on the application side,
Costs induced by storage and digital signature,
The operational burden related to the management and verification of secured logs.
In this post, we will compare two approaches to achieve this objective:
a naïve implementation based on a
blockchain (which is a simple and effective solution, but which does not allow for log rotation),
a more efficient and pragmatic version built around
Merkle Trees*.
We will consider here that our logs have the simple structure below, but it can be extended as needed (source, level, …).
type LogEntry struct {
Message string `json:"message"`
Timestamp time.Time `json:"timestamp"`
}
Naïve implementation: a blockchain
The hash chain (referred to as blockchain by misuse of language), although primarily linked to the world of cryptocurrencies today, is a cryptographic concept dating back to the 1980s, and whose first concrete use case was the timestamping of digital documents to prevent their falsification.
A hash chain is simply a list of data blocks, where each block is hashed on the concatenation of the previous block's checksum and its own data (SHA-256 or BLAKE3 for example). (using
SHA-256 or BLAKE3 for example).
Transposed to a log journal, this amounts to forging one block per entry; as soon as one wants to purge, it would be necessary to replay or re-sign millions of blocks, which is disproportionate for a simple application log.
Given that the first block in the chain has no parent, it is the sole point of trust in our system, which is why it is often called “block 0” or “genesis block” (genesis block in English).
Hash chain implementation diagram
Although in practice this system is consistent, it presents several limitations in practice.
An attacker can, in theory, recalculate the entire chain if they have access to the genesis block : it is enough to forge a new block 0, replay all hashes and replace the log with this falsified version, which local verification will accept. We only reduce the risk, not eliminate it, as long as the anchoring point remains within the same perimeter of trust as the logs. It is only by externalising or cryptographically signing the root (e.g. signature with a key stored elsewhere or periodic publication outside the IS) that this undetectable recalculation is made impossible.
The verification of a complete hash chain also remains linear: each block must be replayed to confirm the integrity of the whole. For large volumes of logs, this quickly becomes resource-intensive.
Another problem: the complete lack of parallelisation. Each block depends on the previous one, which prevents recalculating or verifying multiple parts of the chain in parallel. This is a major bottleneck for high-traffic applications or distributed architectures.
Finally, a hash chain does not allow for any natural log rotation : in a context of multi-year retention (which is rather common under several standards), it is necessary to delete the entire history, then reconstruct a new chain from scratch, an operation that is particularly heavy and unrealistic for application logs.
Merkle Tree: a more flexible alternative
A more flexible approach consists of replacing the hash chain with a Merkle Trees.
Used in the file system
ZFS to counter data degradation in a
RAID or in protocols such as
IPFS, the concept of merkle trees is to group logs as leaves in a binary tree. Each leaf contains the log's hash, and each internal node contains the hash of the concatenation of its two children. The top of the tree, called the “root”, represents a cryptographic commitment to all the logs.
The benefit of this model is to allow for much faster and partial verification. To prove that a given log belongs to the tree, you provide:
the leaf's hash (the log itself),
the ordered list of sibling hashes encountered when going up towards the root, as well as their left/right position.
The verifier then recalculates, step by step, the parent's hash from the current hash and its sibling, then that of the upper level, until the root is recomposed. If the obtained root matches the public root, the proof is accepted; otherwise it fails. This proof, called Merkle Proof (or “proof of membership”), is calculated with logarithmic complexity.
This approach practically corrects all the drawbacks of a hash chain when talking about log records.
It is no longer necessary to replay the entire sequence of events; to verify a log, a proof of membership, composed solely of the lateral hashes, is sufficient.
Each sub-tree can be calculated independently, which allows the computation to be distributed across multiple machines (or threads), eliminating the bottleneck inherent in the hash chain (where each block depends on the previous one).
A complete sub-tree can be truncated or archived without breaking the validity of the rest: the link to the obsolete part is cut, the hashes are recalculated up to the cut-off node, and this node is considered the new root for the current window. No need to delete or replay all retained leaves.
Each service or VM can build its own tree in parallel and publish its root; these roots can then be combined into a tree of roots, making the model perfectly horizontally scalable.
Proof of concept
This PoC sets four objectives:
To build and update the root in streaming via a StreamBuilder, in O(log n) memory (so there's no complete tree in RAM).
To generate and verify inclusion proofs with an explicit tree, serialisable in SQLite for auditing and reconstruction.
To validate stream <=> tree equivalence, including in concurrency, via deterministic tests and fuzzing.
To regularly publish roots (and signatures) in immutable storage such as S3 Object Lock / equivalent, to date and lock checkpoints.
To verify the theory, we implemented a PoC in Go (which offers native fuzzing tools for the Go toolchain), consisting of a few simple Go modules: a struct LogEntry, digests with domain separation, a StreamBuilder in O(log n) memory, an explicit tree for proof generation, and SQLite persistence for auditing.
const (
leafPrefix byte = 0x00
internalPrefix byte = 0x01
)
func LeafDigest(e LogEntry) [32]byte {
m := e.Serialize()
b := make([]byte, 1+len(m))
b[0] = leafPrefix
copy(b[1:], m)
return sha256.Sum256(b)
}
func CombineDigests(l, r [32]byte) [32]byte {
var buf [1 + 32 + 32]byte
buf[0] = internalPrefix
copy(buf[1:33], l[:])
copy(buf[33:], r[:])
return sha256.Sum256(buf[:])
}
The prefix 0x00 for leaves and 0x01 for internal nodes avoids any structural collision (a message cannot “resemble” a node).
Explicit Tree and Proofs
Node carries either a leaf (Data), or pointers Left/Right and a cached hash.
BuildMerkleRoot folds each level up to the root.
GenerateProof goes up from the leaf to the root by collecting the sibling hashes and their left/right position.
VerifyProof retraces the path and compares it to the expected root.
type ProofStep struct{ Hash [32]byte; Right bool }
func VerifyProof(leaf LogEntry, proof []ProofStep, root [32]byte) bool {
h := LeafDigest(leaf)
for _, s := range proof {
if s.Right { h = CombineDigests(h, s.Hash) } else { h = CombineDigests(s.Hash, h) }
}
return h == root
}
Streaming in O(log n)
StreamBuilder accumulates a hash “per level” (binary counter) and keeps only one slot per tree height.
type StreamBuilder struct {
mu sync.Mutex
levels []levelDigest
entryCount int
}
func (s *StreamBuilder) AddEntry(e LogEntry) {
d := LeafDigest(e)
s.mu.Lock()
s.foldDigestLocked(0, d)
s.entryCount++
s.mu.Unlock()
}
func (s *StreamBuilder) Root() ([32]byte, bool) {
s.mu.Lock(); defer s.mu.Unlock()
var out [32]byte; var ok bool
for _, slot := range s.levels {
if !slot.filled { continue }
if !ok { out, ok = slot.hash, true; continue }
out = CombineDigests(slot.hash, out)
}
return out, ok
}
The same root is obtained as with a complete tree, but without storing the tree.
Persistence and Auditing
The tree can then be stored in a database by inserting the leaves (payload + hash) as well as the internal nodes (level, position, hash), which allows for:
replaying the tree / verifying proofs locally
exporting original leaves for a window of N days back
inspecting the structure by sorting by level / position.
Tests, robustness, and fuzzing
The objective of the tests is twofold: to lock cryptographic invariants (domain separation, left/right order, stability) and to ensure that the O(log n) streaming path produces exactly the same root and proofs as an explicit tree, including in a concurrent environment where multiple goroutines feed and read the state in parallel.
Hash and Order Invariants
Effective domain separation: a leaf hash must never equal an internal hash with the same payload (prefixes 0x00 / 0x01).
Non-commutativity: reversing left/right must yield a different digest, which prevents reordering children without alerting.
Stability: for identical input, the digest is stable (no hidden state or source of randomness).
Tree, proofs, and negatives
A proof of membership for a real leaf is valid by recomposing up to the expected root. Negative alterations fail (same proof but modified payload, or same payload with a permutation of a sibling hash).
A correct proof applied to a different root must also fail, which protects against out-of-window replays.
Concurrency
Multiple goroutines each build a stream on the same batch of inputs and compare it to the reference root (tested with -race).
The simultaneous generation and verification of proofs on a shared tree validates thread-safe reading and the purity of hash functions. In progressive concatenation, entries are added while another thread reads the root, without observable divergence.
Fuzzing
Fuzzers generate random log sequences, build the root, verify a proof on a random index, then alter the payload or sibling order to ensure the proof fails.
The parity between StreamBuilder and BuildMerkleRoot is verified on odd sizes or incomplete levels to guarantee the same root.
Bounded cases (size 1, 2, and powers of two) verify slot chaining and any potential duplications of the last leaf.
Fuzzing tests run continuously on a small fuzzing farm of 56 vCPU for the equivalent of 176 CPU hours (~3h real time) without false-negatives, false-positives, crashes, or timeouts, providing good coverage of critical paths.
Once the Merkle root is calculated, it must be anchored somewhere, i.e., published in a space where it can no longer be modified.
Why anchor checkpoints?
The Merkle tree gives us a unique root that represents the exact state of the logs at a given time T.
But this root remains a simple hash: if it is stored in a classic database or on a disk, nothing prevents it from being rewritten later.
For the proof to remain legally and technically valid, each root must be immutabilised upon its publication.
a root is calculated for a given period (e.g., one day)
it is published in immutable storage
it is never touched again
Thus, an auditor verifying a log at D-45 only needs to compare the proof to the root of the D-45 checkpoint to ensure it was already anchored on that date.
How often should the root be published?
The root must cover the period of the log to be verified. If you only publish one root per day at 23:59, a morning log cannot be immutably auditable until after the evening checkpoint is published. Here are two practical options:
Publish more frequently (e.g., hourly, or every 10k entries). The cost is negligible as a checkpoint is just a hash + signature.
Maintain a continuously generated "working" root (the StreamBuilder can provide the root at any time) and anchor it in the object store as soon as an audit is requested. This instantaneous root then becomes the reference point for that log.
S3 Object Lock: immutability guaranteed at storage level
On AWS, the simplest solution to achieve this immutability is S3 Object Lock.
It allows storing an object (here a JSON file / a blob containing the root + an
ED25519) signature with two guarantees:
The object cannot be modified or deleted until the retention period has expired (Write Once Read Many)
Any attempt to replace it creates a new version; a legal hold can also be applied to block administrative deletion.
In practice, this means that a simple upload is enough to make the checkpoint unalterable until the chosen retention period.
aws s3api put-object \
--bucket merkle-checkpoints \
--key roots/2025-10-01.json \
--object-lock-mode COMPLIANCE \
--object-lock-retain-until-date 2025-12-31T00:00:00Z \
--body checkpoint.json
Example of object locking with the AWS CLI
The application no longer manages immutability; it is delegated to the Cloud Provider (here AWS).
Alternatives from other providers
Azure Blob Storage : offers immutable blob policies and legal holds, with similar mechanisms (retention period or legal lock).
Google Cloud Storage : offers the Object Retention Policies and Bucket Lock, locking objects for predefined durations.
MinIO : in self-hosted mode, it also implements Object Lock, compatible with the S3 API (reliable provided a zero-trust infrastructure).
Why this approach is ideal
It directly addresses the retention requirements of standards like NF525, PCI-DSS or HDS : the checkpoint is in Write Once, Read Many (WORM) mode. If raw logs were deleted elsewhere, the proof of inclusion would fail, making deletion detectable; for prevention, logs are also stored in a bucket with retention/Object Lock.
Each checkpoint is an object of a few bytes stored only once, so the cost is negligible compared to the volume of the logs themselves.
One root per day / week is sufficient; they can be replicated and signed to strengthen traceability.
Cost optimisation and operational design
The objective is not only to be compliant but to remain efficient in storage and computations.
Storage
The volume of logs often grows very quickly; a good practice is to dissociate Merkle proofs from logs:
Compute
Thanks to the Merkle structure, the verification of a given log is logarithmic. Even if the complete history contains several million events, the entirety is never necessary, which saves on egress.
Conclusion
This proof of concept shows that it is possible to guarantee the integrity of a log journal without a hash chain, without a specialised database, and without complex infrastructure.
By combining simple primitives (SHA-256 / BLAKE3, Merkle tree, immutable storage) and cloud-native mechanisms such as S3 Object Lock, we obtain a verifiable, frugal, and compliant system that meets modern traceability requirements.
This solution does not replace governance or application supervision, but is a solid cryptographic foundation upon which to build a durable and transparent audit trail.
