Deterministic Diffing of Redaction Versions

Computing which redaction spans and pages changed between two document versions is only defensible if the same two inputs always yield the byte-identical diff, so that a diff produced during discovery matches the one re-run months later under scrutiny.

Prerequisites & Version Matrix #Permalink to this section

This procedure assumes the content-addressed snapshots described in Redaction Version Tracking, where each version carries a decision set of redaction spans. Pin these library versions so the normalization and hashing steps behave identically across machines:

A redaction span is normalized to (page, x0, y0, x1, y1, entity_type). Diffing operates on these tuples, never on rendered pixels, so the result stays stable regardless of viewer or DPI.

Step-by-Step Implementation #Permalink to this section

1. Normalize spans. Floating-point coordinates from PDF parsers jitter in the least-significant digits between runs. Quantize every coordinate to a fixed grid and lower-case the entity type so trivial representational differences never register as changes.

from dataclasses import dataclass

@dataclass(frozen=True)
class Span:
    page: int
    x0: float
    y0: float
    x1: float
    y1: float
    entity_type: str

def normalize(span: Span, grid: int = 100) -> tuple:
    """Quantize coordinates to a 1/grid grid so float jitter is erased."""
    q = lambda v: round(v * grid) / grid          # deterministic rounding
    return (span.page, q(span.x0), q(span.y0),
            q(span.x1), q(span.y1), span.entity_type.lower())

2. Extract redaction span sets. Build a frozen set of normalized tuples per version. Sets make the diff order-independent: whether the parser emitted spans top-to-bottom or by object id, the set is identical.

def span_set(spans: list[Span]) -> frozenset:
    """Order-independent set of normalized spans for one version."""
    return frozenset(normalize(s) for s in spans)

3. Structural diff. Compute added and removed spans with set algebra, then emit them in a canonical, fully sorted order. Sorting is what makes serialization reproducible — Python set iteration order is not guaranteed across processes.

def diff_versions(v1: list[Span], v2: list[Span]) -> dict:
    """Return spans added and removed going from v1 to v2, canonically ordered."""
    a, b = span_set(v1), span_set(v2)
    return {
        "removed": sorted(a - b),   # present in v1, gone in v2
        "added":   sorted(b - a),   # new in v2
    }

4. Hash the diff. Serialize with sorted keys and compact separators, then SHA-256 the bytes. This digest is the diff’s stable identity — the value asserted in tests and recorded alongside the version pair.

import hashlib
import json

def diff_digest(diff: dict) -> str:
    """Deterministic SHA-256 over the canonical diff serialization."""
    body = json.dumps(diff, sort_keys=True, separators=(",", ":"))
    return hashlib.sha256(body.encode("utf-8")).hexdigest()

Compliance Checkpoint #Permalink to this section

Under FRCP Rule 34(b), a requesting party may specify the form of production and challenge whether responsive material was altered between states. A deterministic diff answers that challenge directly: producing counsel can show, span by span, exactly what the redacted version removed relative to the detected version, and prove the comparison is reproducible because its digest is stable. A diff that changes value on re-run is inadmissible as evidence of process integrity; determinism is the property that makes the artifact hold up.

Gotchas #Permalink to this section

• Float coordinate jitter. PDF text extraction returns coordinates as IEEE-754 doubles that vary in the 6th–7th decimal between library builds. Skipping the quantization step in normalization produces phantom “changed” spans on every run. Round to a coarse grid (1/100 pt is well below any visible redaction boundary).
• Page-reorder false positives. If a downstream step reorders pages, spans that never changed appear moved because their page index shifted. Diff against a stable logical page key (an original page id captured at ingestion), not the physical index, when reordering is possible.
• PDF object id churn. Re-saving a PDF renumbers internal object ids, so any diff keyed on annotation object ids reports wholesale change. Key exclusively on geometry and entity type, never on parser-assigned object ids.

Verification & Testing #Permalink to this section

The essential property is that diff(v1, v2) is byte-identical across independent runs. This test computes the diff digest twice from separately constructed span lists and asserts equality, guarding against set-ordering and float-jitter regressions.

def test_diff_is_byte_identical_across_runs():
    v1 = [Span(1, 10.0, 20.0, 90.0, 32.0, "SSN"),
          Span(2, 15.000001, 40.0, 80.0, 55.0, "NAME")]
    # Same logical spans, different construction order and jittered floats.
    v2 = [Span(2, 15.0, 40.0, 80.0, 55.0, "name"),
          Span(1, 10.0, 20.0, 90.0, 32.0, "ssn"),
          Span(3, 12.0, 12.0, 60.0, 24.0, "EMAIL")]

    first = diff_digest(diff_versions(v1, v2))
    second = diff_digest(diff_versions(v1, v2))
    assert first == second                      # reproducible within a run
    # v1 and v2 differ only by the added EMAIL span on page 3.
    d = diff_versions(v1, v2)
    assert d["removed"] == []
    assert len(d["added"]) == 1 and d["added"][0][0] == 3

Run repeatedly with pytest -p no:randomly across separate processes; the digest must match every time. Wire this assertion into the redaction validation stage so a non-deterministic renderer is caught before its output ever reaches an audit manifest.

Related #Permalink to this section

This procedure consumes the snapshots defined in Redaction Version Tracking and produces digests suited to the hash-linked records in Cryptographic Audit Manifests. To assemble the full chronological history rather than compare two states, see Reconstructing Audit Timelines from Event Logs. Part of the Immutable Audit Trails & Chain of Custody field guide.