lemmaroutine

Pairwise-collision hash from few random bits

O(\log B)

random bits give a hash with pairwise collision probability ≤

C/B

cheap salt separating endpoints

Lemma·lem:fp-hash·§9.1 Uniform salts and their access rule

Statement (paper)

Suppose every endpoint has an injective, fixed-length binary encoding of length

L\le c_{\mathrm{ID}}B

. There is a uniform construction from

O(\log B)

independent fair bits of a map

k:\{\text{endpoint IDs}\}\longrightarrow\{1,\ldots,B\}

such that, for distinct fixed IDs

v,w

\Pr[k(v)=k(w)]\le C/B\le C B^{-1/2}.

Evaluating the map at a presented endpoint needs

O(\log B)

arithmetic scratch in addition to access to its encoding.

In plain English

If endpoint IDs are injective binary strings of length

L\le c_{\mathrm{ID}}B

, then

O(\log B)

fair bits suffice to build a map

k

from endpoint IDs to

\{1,\ldots,B\}

such that any two distinct fixed IDs collide with probability at most

C/B\le CB^{-1/2}

. Evaluating

k

on a presented endpoint takes

O(\log B)

extra arithmetic scratch beyond access to its encoding.

Why it's here

This gives the paper a cheap random salt that sends distinct endpoints to distinct labels in

\{1,\ldots,B\}

with high probability, using only logarithmically many random bits and logarithmic scratch space. The later envelope and block-coupling results rely on this low collision probability and small evaluation cost to keep representatives distinguishable within the space budget.}</br>

Classified routine:

This is a standard polynomial-identity fingerprinting hash: treat the ID as a polynomial over a prime field of size about B^2 or B, evaluate it at a random point, and bound collisions by Schwartz–Zippel or the degree bound. It is the Karp–Rabin / Carter–Wegman-style universal hashing, adapted here to the parameters L ≤ c_ID·B.

Uses

Nothing else in the paper

Used by

lemWitness envelope is small and collision-controlledpropActual runs stay close to clean runsclaimOrder of constant choices is consistent

Sources

PaperOpen

Section: §9.1 Uniform salts and their access rule
Page: —
Label: lem:fp-hash
Line: sections/fingerprints.tex:38

Leannot aligned

Phase 2 aligns this node to a Lean declaration.