Crate provsum 

provsum

Fixed-size digests of provenance polynomials.

Every error-origin site in a codebase gets a 16-byte GUID. Each GUID is hashed to a nonzero point in F_p (one per lane, p = 2^61 - 1). The digest of an error is its N[X] provenance polynomial evaluated at those points:

• origin(site) → r_site
• wrap(site, d) → r_site · d
• merge(a, b) → a + b
• pick(site, [d_0, d_1,…]) → Σ r_{site,slot_i} · d_i

pick is how order enters a commutative semiring: the site contributes a distinct variable per slot, so returning a and discarding b yields a different polynomial from the reverse. Slot 0 is the returned error.

Two digests are equal iff the two polynomials are equal, except with probability at most (d/(p-1))^LANES where d is the max wrap depth (Schwartz–Zippel, lanes independent). The construction is not designed against an adversary who controls GUIDs or points; it is meant for comparing two implementations of the same code.

The point derivation is pinned (splitmix64 finalizer over the GUID bytes) so that a second implementation (see python/provsum.py) reproduces the same digests byte-for-byte.

Modules

poly

Expanded N[X] provenance for diagnostics.

Structs

Digest

A provenance digest: the polynomial’s value in each lane, plus an upper bound on its total degree (used only for the collision bound; equality compares lanes only).

Site

A 16-byte site identifier. Assign one per error-origin / wrap / pick site in the source, and carry the same bytes in the same order across implementations. Point derivation interprets each consecutive 8-byte chunk as little-endian; it never uses the host’s native byte order.

Constants

DIGEST_BYTES

Serialized digest size in bytes: LANES * 8 for the lanes, plus 2 for depth.

LANES

Number of independent lanes. Each lane is an independent evaluation point.

NO_SLOT

Slot value used by origin/wrap (no positional slot).

P

The Mersenne prime 2^61 - 1.

Functions

point

Derive the evaluation point for (site, slot, lane). pick uses slots 0..n; origin/wrap use NO_SLOT.