High-Frequency Timestamping: Designing an Internal RFC 3161 Pipeline for Millions of Tokens

What high frequency means in practice

Most timestamping discussions assume documents: a contract, an invoice, a signed PDF. Technical workloads behave differently. They produce records continuously, in many parallel streams, and the value of timestamping comes from covering all of them, not a selection.

Two observations follow. First, the volume quickly reaches hundreds of millions of tokens a year. Second, design choices such as batching change the volume by orders of magnitude, which is why granularity is the first decision to make.

Why per-token external services do not fit

• Cost scales with volume. Per-token pricing is reasonable for documents and prohibitive for continuous technical streams.
• Latency enters the critical path. An internet round-trip per record adds latency and a failure mode to every producer that waits for a token.
• Rate limits and fair-use policies. Many public services throttle sustained high-frequency clients, which turns a design parameter into an external constraint.
• Availability coupling. Every outage or network issue on the provider side becomes an unprotected window in your records.
• Network and data boundaries. Isolated segments cannot reach an external service at all, and even hash-only traffic may be undesirable from some zones.

An internal TSA removes these constraints: requests stay on the local network, the marginal cost per token is zero, and capacity is something you size rather than negotiate.

Granularity: per object, per segment or per batch

Granularity defines what a single token proves, and therefore what you can demonstrate later about an individual record.

• Per object. Each record, file or artefact gets its own token. The evidence is self-contained and can be disclosed for one object without the others. Volume equals the number of objects.
• Per segment. A stream is cut into segments by time or size, for example one log segment per minute per source. A token covers the whole segment, so the time resolution of the evidence equals the segment length.
• Per batch with a Merkle tree. Many objects are combined into a tree and only the root is timestamped. Each object keeps an individual proof, at the cost of storing an audit path next to it.

The right choice depends on the exposure window you can accept. A record written just after a token is issued is unprotected until the next token, so the segment or batch interval is effectively the maximum time during which a change would go undetected.

Hash chaining

Timestamping segments independently proves that each segment existed unchanged. It does not prove that the set of segments is complete. Hash chaining closes that gap. Each segment header carries:

• the source identifier and a monotonically increasing sequence number;
• the hash of the segment content;
• the hash of the previous segment header.

The header hash is what gets timestamped. Removing, inserting or reordering a segment breaks the chain, and a gap in sequence numbers is immediately visible. Truncation of the most recent segments is detected by checking the expected cadence: if a source produces a segment every minute, a missing minute is an event in itself.

Keep one chain per source or per stream. A single global chain serialises all producers and makes partial disclosure harder.

Merkle trees

When objects arrive faster than you want to issue tokens, a Merkle tree lets one token cover a whole batch without losing per-object evidence. The object hashes are the leaves, each internal node is the hash of its two children, and only the root is timestamped.

To prove a single object later, you need the object, the token and the audit path: the sibling hashes from the leaf to the root. For n objects the path contains about log₂(n) hashes, so 10,000 objects need 14 hashes and 1,000,000 objects need 20. The proof for one object reveals nothing about the content of the others.

For long-term archiving, RFC 4998 (Evidence Record Syntax) and RFC 6283 (its XML variant) standardise this structure, including the renewal of the evidence over time. Using a standard format is preferable to a proprietary one when the evidence must outlive the software that produced it.

Request handling

Keep producers independent of the TSA

Producers should hand hashes to a local agent and continue. The agent places requests in a durable queue, and workers send them to the TSA. If the TSA is slow or unavailable, records are still written; they are timestamped as soon as the service responds, and the delay is recorded.

• Retry with exponential backoff and jitter, so recovery does not produce a request storm.
• Make requests idempotent on your side: a retried request for the same hash and sequence number must not produce two competing records.
• Alert on queue depth and age, not only on errors. A growing backlog is the earliest sign of an under-sized TSA.

Request parameters

• Hash algorithm. SHA-256 is the usual baseline; SHA-384 or SHA-512 where policy requires a longer digest. Keep the algorithm consistent per stream.
• Nonce. A random nonce in each request lets the client check that the response belongs to that request. It costs nothing and should always be used.
• certReq. When true, the TSA includes its certificate in each token, which makes tokens self-contained but larger. At millions of tokens a day, storing the TSA certificate once per certificate period and requesting tokens without it can reduce storage noticeably.
• Policy OID. If you run several TSA policies, for example different accuracy commitments, request the intended one explicitly.

Ordering

RFC 3161 tokens are not inherently ordered. Unless the TSA asserts ordering, two tokens can be ordered by their genTime only if the difference between them exceeds the sum of their accuracies. For strict ordering within a stream, rely on the sequence numbers and the hash chain rather than on token times.

Capacity planning and scaling

TSA Server issues up to 100 tokens per second on standard hardware, which corresponds to 360,000 tokens per hour or 8.64 million per day for a single node. Three factors decide what you actually get:

• Peaks, not averages. Log volume after an incident, month-end batch jobs or a full rebuild can exceed the daily average several times. Size for the peak you can observe, plus headroom.
• The signing device. With an HSM accessed through PKCS#11, signatures are processed one at a time per session, so the device's signing latency sets the ceiling. Measure it with your real key type before committing to a capacity figure.
• Key type. RSA-4096 signatures are considerably slower than RSA-2048, and ECDSA keys are typically faster still. Choose the key type for your security policy first, then measure the throughput it gives.

Scaling out

Beyond one node, place several TSA nodes behind a load balancer. The cleanest design gives each node its own TSU certificate and key:

• RFC 3161 requires the serial number to be unique for every token issued by a given TSA. Separate TSU identities make serial number spaces independent by construction.
• Key custody and incident scope stay separate: a compromised or retired key affects only the tokens of one node.
• Each node can be taken out of rotation for maintenance or certificate rollover without affecting the others.

Validators need to trust all TSU certificates, which is straightforward when they are issued by the same internal CA.

Operations

Time synchronisation

The time in a token is the time of the TSA host. Synchronise it with a reliable reference, an NTP or PTP hierarchy traceable to UTC, or a GNSS-disciplined time server in closed networks, and monitor the offset continuously. On Windows, the Windows Time service can be configured for high accuracy on recent server versions; its default domain configuration is designed for Kerberos tolerances, not for timestamping. Set the accuracy declared in the tokens to a value your synchronisation actually guarantees, and alert when the measured offset approaches it.

Key protection and certificate lifecycle

• Keep the signing key non-exportable, in an HSM through PKCS#11 where possible.
• The TSU certificate must carry the id-kp-timeStamping extended key usage, marked critical, as its only purpose.
• Plan rollover before expiry: issue the new certificate, switch the nodes, and keep the old certificate chain and its revocation information. Tokens already issued remain verifiable with the certificate that signed them.
• Choose the certificate validity with the retention period of your evidence in mind. Records that must outlive the certificate need archive timestamps before it expires.

Token storage

Store each token next to the object or segment it protects, and index it by hash and sequence number. Tokens are typically a few kilobytes, more when the TSA certificate is embedded, so a million tokens a day means several gigabytes a day. Include tokens in the same retention and backup policies as the data they protect; a record whose token is lost is no longer evidence.

Continuous verification

Evidence that is never checked fails silently. A scheduled job should:

1. recompute the hash of each object or segment and compare it with the token;
2. verify the token signature and the TSU certificate chain;
3. check chain continuity and sequence numbers per source;
4. compare the observed cadence with the expected one and report gaps;
5. raise an alert on any failure, and treat it as a security event.

Monitoring and access

• Track request latency (p95 and p99), error rate, issuance rate per source, queue depth and clock offset.
• Use the TSA Server audit trail for server events, and enable the per-token log where you need a record of every issued token.
• Restrict who can request tokens: enable client authentication and serve the endpoint over HTTPS, so credentials never travel in clear text.

Scope of internal evidence

Tokens from an internal TSA prove integrity and time under your own policy, and are trusted by every system that trusts your CA. Where the evidence must also convince parties outside your organization, see Qualified vs Self-Hosted Timestamping for how internal and qualified timestamps differ and when each is appropriate.

Frequently asked questions