certrax is a Rust certificate-transparency collector and an embedded DNS/validity search index. It reconciles the Chrome and Apple registries, monitors RFC 6962 and static/tiled CT logs, reconstructs signed Merkle roots, stores raw evidence and issuer objects, and exposes exact or wildcard domain queries ordered by certificate issuance time.

• One RocksDB write batch contains raw CT leaves, new certificate identities, normalized DNS postings, the per-log next-leaf cursor, and (on the terminal batch) the verified signed tree head. A crash exposes either side of that transaction, never a partially advanced cursor.
• (LogID, leaf_index) is the raw-entry identity. SHA-256(DER) is the cross-log certificate identity. Repeated observations do not duplicate DNS postings.
• Downloads complete out of order with a bounded c-range window; commits are reordered into strictly contiguous leaf-index order. A short server response causes only its missing suffix to be rescheduled. Configuration clones share a second semaphore of size g, so aggregate active range fetches remain min(a × c, g) for a simultaneously backfilled logs.
• Registry-driven streaming filters LogIDs by browser program, protocol, registry state, operator/description substring, and explicit identity. One worker runs per selected log, RFC and static workers share an HTTP connection pool, and a failed worker is reported without cancelling healthy workers. If one reconciled LogID exposes both protocol types, mixed mode rejects it unless one --api is selected because cursor/tree equivalence is otherwise unknown.
• RFC 6962 get-entries responses are staged outside the query index because they are unsigned. A compact frontier is reconstructed over the staged leaf bytes and must equal the signed STH root before any certificate is promoted. Staging and partial promotion are restartable.
• Large root-verified generations can be promoted by bounded-memory external sorting into non-overlapping SST files. Multipass merging caps each merge at 64 input runs instead of scaling open file descriptors with corpus size. A durable cross-column-family marker makes partial ingestion invisible to query snapshots; restart replays an unacknowledged SST safely and finalizes the cursor, head, frontier, and marker deletion atomically. Ordinary batched promotion remains the tailing default.
• Static-CT checkpoints verify their registered origin, note key ID, embedded RFC 6962 timestamp, and ECDSA/RSA signature. Data tiles verify the mandatory 40-bit leaf-index extension and reconstruct ordinary RFC 6962 leaf bytes. Issuer objects are fetched with bounded parallelism and accepted only when SHA-256(DER) equals the tile fingerprint.
• Browser LogIDs are recomputed as SHA-256(SPKI) and Chrome/Apple descriptors are reconciled by that identity. Chrome's JSON must also pass its detached RSA PKCS#1 v1.5 / SHA-256 signature under the pinned published v3 key. Exact source JSON and authentication status are persisted content-addressably.
• An X.509 parse failure can be represented as an opaque entry and still moves the Merkle/log cursor. A malformed dNSName is retained in metadata but is not allowed to corrupt the search index.
• Exact and suffix postings are lexicographically ordered by descending notBefore, descending notAfter, then certificate SHA-256. Queries do not materialize and sort the whole match set.
• *.example.com means strict descendants at any label depth and excludes the apex example.com. A certificate SAN *.example.com is a descendant posting for example.com, but it is not an exact posting for the apex.
• Every query has a result limit and posting scan budget. Continuation cursors encode the last scanned posting, which guarantees progress even when validity predicates reject many candidates.
• issued_before and valid_at impose an upper bound on notBefore; the descending encoding converts that bound into a direct RocksDB seek rather than scanning all newer certificates. Matching certificate metadata is read with one snapshot-consistent MultiGet while retaining posting order.
• Wildcard suffix postings maintain a hierarchical notBefore synopsis at 1-, 32-, 1,024-, and 32,768-day widths, each containing the minimum and maximum notAfter. A validity predicate first tests the day and, when it is impossible, selects the largest impossible enclosing bucket before seeking directly to its older boundary. Synopsis checks have an independent bound and continuation cursors encode the end of a skipped bucket, so summary-only pages also make progress. Normal commits use associative merge operands; external SSTs emit RocksDB merge records, preserving extrema when a bulk generation overlaps an existing domain/day.

For canonical A-label domain d, validity times nb and na in Unix milliseconds, and certificate digest h, the posting key is:

d || 0x00 || descending_i64(nb) || descending_i64(na) || h

descending_i64(x) = BE64(!(u64(x) XOR 2^63)). The sign-bit transform maps signed chronological order to unsigned order; complementing reverses it. Thus ordinary byte order is newest issuance first for the full i64 domain.

A non-wildcard SAN creates one exact posting plus one posting for each proper DNS suffix. A wildcard SAN additionally creates a posting for its own base. Duplicate postings from multiple SANs in one certificate are removed before the write batch is constructed.

Let N be certificates, L the mean count of distinct SAN names per certificate, and D the mean DNS label depth. The worst-case posting count is O(N L D), ingestion CPU is O(L D log(LD)) for per-certificate de-duplication, and an ordered query is O(log P + s) LSM seek/scan operations for P postings and scan budget s when no validity buckets are used. For a wildcard validity query that checks v hierarchical buckets, the bound is O(log P + v(log P + log V) + s), where V is synopsis cardinality; both v and s are explicit per-page budgets. Query memory is O(limit). One parallel backfiller retains at most approximately c × b leaves, where c is max_in_flight_ranges and b is range_entries. Across a selected logs, at most min(a × c, g) range sources execute concurrently under global_in_flight_ranges = g; ordered pending responses remain bounded by O(a c b) because every log has an independent commit frontier. Both schedulers enforce next_scheduled ≤ min(tree_size, next_commit + c × b), so a stalled earliest range cannot cause later completions to advance the lookahead window.

For suffix domain d, level l, multiplier m_l ∈ {1, 32, 1,024, 32,768}, and q = floor(nb / (86,400,000 ms × m_l)), the synopsis key and fixed-width value are:

d || 0x00 || U8(l) || BE64(q) -> BE64(min(na)) || BE64(max(na))

The value is 16 bytes. An enclosing bucket is skipped only when max(na) is below the required expiration lower bound or min(na) is above the expiration upper bound. Extrema can produce false positives but cannot omit a matching posting. Offline reconstruction is O(P_suffix) sequential reads, holds one active aggregate per hierarchy level plus at most 10,000 pending summaries, and is restartable from the disabled ready marker.

Name SSTs use prefix-only full Bloom filters plus partitioned two-level indexes and filters. Whole posting keys are omitted from Bloom filters because the query operation is a domain-prefix seek. Top-level metadata is pinned while partitions remain governed by the configured block-cache bound.

For K key/value records, external promotion creates memory-bounded sorted runs and performs multipass merges with fan-in F = 64. With R initial runs, comparison cost is O(K log R), merge I/O is O(K ceil(log_F R)), memory is O(M + F B) bytes for configured sort memory M and maximum encoded record size B, and at most F + 1 merge files are open. Peak temporary merge storage is O(K) in addition to the authenticated staging copy and generated SSTs.

The exact uncompressed key bytes for a posting are len(d) + 49. RocksDB adds internal keys, block indexes, filters, WAL, manifests, and compaction amplification; certificate metadata, DER, and CT raw payloads are separate. Capacity planning therefore requires a representative SST-size measurement. For example, multiplying logical bytes by an assumed factor without measuring SAN depth, compression, and write amplification is not a valid billion-entry storage estimate.

cargo run --release -- --database ./certrax.db init
cargo run --release -- --database ./certrax.db query '*.example.com' \
  --limit 100 --valid-at-ms 1783958400000 \
  --validity-bucket-budget 4096

The response is JSON. Results are in descending notBefore order. If truncated is true, pass next_cursor to --cursor. postings_scanned, validity_buckets_checked, and validity_buckets_skipped expose bounded work. Time fields are signed Unix milliseconds; CLI values are dimensionally milliseconds, not seconds.

Protocol operations are explicit:

# Validate and display registry authentication plus reconciled logs.
cargo run --release -- registry

# Verify live heads/checkpoints without downloading their leaves.
cargo run --release -- probe-rfc <log-id>
cargo run --release -- probe-rfc-entry <log-id> [--leaf-index <n>]
cargo run --release -- probe-static <log-id>

# Authenticated historical backfill, then continuous selected-log monitoring.
cargo run --release -- --database ./certrax.db backfill-rfc <log-id>
cargo run --release -- --database ./certrax.db backfill-static <log-id>
cargo run --release -- --database ./certrax.db stream-rfc --log-id <id> --log-id <id>
cargo run --release -- --database ./certrax.db stream-static --log-id <id>

# Deterministically preview or run a mixed registry selection.
cargo run --release -- --database ./certrax.db stream-registry \
  --state usable --api both --program chrome --maximum-logs 20 --list-only
cargo run --release -- --database ./certrax.db stream-registry \
  --state usable --api both --program chrome --maximum-logs 20 \
  --in-flight-ranges 16 --global-in-flight-ranges 128

# Root-verified offline bulk promotion and database telemetry.
cargo run --release -- --database ./certrax.db backfill-static <log-id> \
  --bulk-work-directory /separate-volume/certrax-sort
cargo run --release -- --database ./certrax.db rebuild-validity-summaries
cargo run --release -- --database ./certrax.db stats

A new log starts at leaf zero because root authentication requires the complete prefix or an equivalent authenticated frontier. Backfills can therefore be large; staging bounds RAM but temporarily duplicates the unpromoted disk data. External SST mode additionally requires sort-run and generated-SST space. Query snapshots return BulkPromotionInProgress while cross-CF ingestion is active; this prevents partial visibility but makes the mode an offline promotion path. Databases initialized before the validity synopsis existed report it as not ready and retain linear-scan correctness. rebuild-validity-summaries holds the writer, removes the ready marker, reconstructs bounded batches from authoritative suffix postings, and publishes the marker only after the final batch. A crash leaves partial summaries disabled and the command restarts reconstruction.

For a labeled smoke measurement on an empty database directory:

cargo run --release --bin certrax-bench -- \
  --database /tmp/certrax-bench --certificates 100000 --query-iterations 1000

Recorded smoke results and environment details are in BENCHMARKS.md.

The resumable posting-scale harness isolates posting cardinality and can also exercise the production suffix CF, sampled metadata MultiGet, public wildcard query API, and full validity reconstruction:

cargo run --release --bin certrax-posting-scale -- \
  --database /tmp/certrax-posting-scale --entries 1000000000 \
  --sst-entries 5000000 --query-iterations 2000

cargo run --release --bin certrax-posting-scale -- \
  --production-fixture --database /tmp/certrax-posting-production \
  --entries 1000000000 --sst-entries 5000000 \
  --query-iterations 2000

The first mode is index-only. The second mode still omits CT evidence, DER, exact postings, and a complete certificate-metadata corpus. Both use structured single-domain keys and therefore measure actual posting cardinality, not a billion-certificate CT corpus. Existing compatible fixtures resume at a validated SST boundary; --query-only performs no fixture writes.

The production suffix path has been measured at one billion actual posting keys: with an empty process-local RocksDB cache and an unevicted OS cache, p99 for 100-result newest and historical-valid wildcard queries was 0.650 ms and 0.860 ms. Maxima were 4.565 ms and 6.636 ms, so a universal 1 ms bound is falsified. This is not evidence for one billion complete certificates. A deployment claim is falsified or supported by recording at minimum:

1. corpus certificate count, exact/suffix posting count, logical bytes, live SST bytes, and peak compaction bytes;
2. CPU model/count, RAM bytes, storage device and filesystem, RocksDB options, cache state, and reader/writer concurrency;
3. separate warm-cache and cold-cache latency histograms (p50, p95, p99, maximum) for exact, selective suffix, broad suffix, and validity-filtered queries;
4. posting scans and validity-bucket checks alongside latency, including deliberately expired-heavy prefixes that exhaust each independent budget;
5. thread-local RocksDB work counters per query distribution, including user key comparisons, child seeks, cache hits, file block reads/read bytes, iterator bytes, and MultiGet bytes;
6. sustained ingest leaves/s during concurrent queries, write amplification, compaction debt, and restart/recovery time.

An unbounded *.com result cannot have cardinality-independent latency. The API therefore bounds work and reports truncation. A millisecond service-level target is plausible only for bounded, cache-resident prefix/index work on measured hardware; cold random storage I/O and adversarially unselective validity filters are explicit falsification cases.

• High impact: external SST promotion currently holds the process-local writer and rejects query snapshots during cross-CF ingestion. A shadow index followed by an atomic directory/service-generation switch isolates bulk construction from continuously served readers and writers.
• High impact: the cardinality/latency protocol determines a measured shard count. Deterministic domain-suffix shards keep each exact/suffix query on one shard when one RocksDB instance cannot contain the write or compaction rate.
• High impact: rebuilding the validity hierarchy scanned 10⁹ suffix postings in 1,169.776 s (854,865 postings/s) under a contended host. Normal ingest maintains summaries incrementally; a shadow synopsis generation or checkpointed parallel reconstruction would reduce maintenance interruption.
• Medium impact: broad suffixes such as TLDs create large posting lists and storage amplification. Public-suffix-aware admission policies could omit operationally irrelevant ancestors, but would change query semantics.
• Medium impact: hierarchical expiration extrema skip wholly impossible ranges, but a high-cardinality day whose minimum/maximum straddle the predicate can still consume posting scan budget. Finer leaf buckets exchange more keys and merge work for tighter rejection bounds.
• Medium impact: a Chrome registry-signing-key rotation deliberately fails closed until the pinned key is updated. An announced transition can be validated with both the existing and replacement pins.
• Medium impact: registry refresh currently occurs at process start. A long-running supervisor can refresh snapshots and add newly qualified logs without restarting existing per-log workers.
• Medium impact: the shared global semaphore now bounds aggregate data-range fetches across selected logs. Static-CT issuer retrieval retains a separate per-client bound of 32, so nested issuer HTTP concurrency is not governed by global_in_flight_ranges.
• Medium impact: the lookahead invariant bounds pending leaves per log, but aggregate pending bytes still scale with the number of selected logs and variable CT leaf payload sizes. A global byte-weighted semaphore would bound memory more tightly than range counts alone.
• Low impact: the database has an explicit schema version, but future migrations still require version-specific rewrite tooling.

• RFC 6962, Certificate Transparency, DOI 10.17487/RFC6962.
• RFC 5280, Internet X.509 Public Key Infrastructure Certificate and CRL Profile, DOI 10.17487/RFC5280.
• RFC 5890, Internationalized Domain Names for Applications: Definitions and Document Framework, DOI 10.17487/RFC5890.
• C2SP, Static Certificate Transparency API.
• Chrome, CT log lists and detached signatures.
• Apple, current CT log list.
• RocksDB, Prefix Seek partitioned indexes, Bloom filters, per-query performance context, merge operators, and external SST ingestion.