Pinsketch decoder I: the word-RAM machine model and its state predicates
DefinitionLinearSetReconciliation327_Main_DecoderModelpinsketchset-reconciliationword-ram
This bundle fixes the deterministic word-RAM model in which the Pinsketch decoder is written, and the vocabulary used to state its contracts.
A program is a finite sequence of statements over a small instruction set: immediate loads, register moves and additions, indexed loads and stores, comparisons and conditional jumps. Also defined are:
- the statement and condition syntax, together with a compiler that turns structured statements into the flat instruction list executed by
Sem; - the predicate
At P pc c, asserting that the code stored at program addresspcis the compiled form ofc; - the big-step relation
Sem P E pc k s k' s', asserting that programP, started at addresspcin RAM stateswith field-data environmentE, halts after at mostksteps in states'with program counter at mostk'(theboundaryStatenormal form); - the memory predicates
MemoryFrame,FieldArrayStoredandPolynomialStored, which describe which addresses a stage may modify and how a field array or a polynomial is laid out in memory.
This is the interface layer: it contains no algorithmic content, but every decoder specification and every composition of the four decoder stages is expressed in this vocabulary.
Definition code
import Definitions.Def_LinearSetReconciliation327_Main_WordRAM
/-! Decoder model: instruction shapes, `Stmt`/`Cond`/`At`/`Sem`, state predicates, `enc`/`dec`, `r0`..`r15` notations.
Generated by `p21opt/gen/emit.py` by skeleton subtraction from
`Solutions/_p21_opt3.lean` (Stage-2 declaration spans). -/
set_option autoImplicit false
open scoped ENNReal
open Finset Polynomial
namespace LinearSetReconciliation327.Main
section FieldFacts
variable {F : Type} [Field F] [Algebra (ZMod 2) F]
end FieldFacts
section PowerSums
variable {F : Type} [Field F] [Algebra (ZMod 2) F]
variable {N : ℕ}
/-- The `ZMod 2`-support of a binary vector, written exactly as in the statement. -/
def binSupp (x : Fin N → ZMod 2) : Finset (Fin N) := univ.filter (fun i => x i = 1)
end PowerSums
/-- Little-endian packing of a list of `w`-bit fields into one word. -/
def packL (w : ℕ) : List ℕ → ℕ
| [] => 0
| x :: xs => x + 2 ^ w * packL w xs
notation "r0" => (0 : Fin 16)
notation "r1" => (1 : Fin 16)
notation "r2" => (2 : Fin 16)
notation "r3" => (3 : Fin 16)
notation "r4" => (4 : Fin 16)
notation "r5" => (5 : Fin 16)
notation "r6" => (6 : Fin 16)
notation "r7" => (7 : Fin 16)
notation "r8" => (8 : Fin 16)
notation "r9" => (9 : Fin 16)
notation "r10" => (10 : Fin 16)
notation "r11" => (11 : Fin 16)
notation "r12" => (12 : Fin 16)
notation "r13" => (13 : Fin 16)
notation "r14" => (14 : Fin 16)
notation "r15" => (15 : Fin 16)
abbrev iImm (d : Fin 16) (v : ℕ) : Instr := .imm d v
abbrev iAdd (d a b : Fin 16) : Instr := .add d a b
abbrev iSub (d a b : Fin 16) : Instr := .sub d a b
abbrev iMul (d a b : Fin 16) : Instr := .mul d a b
abbrev iDiv (d a b : Fin 16) : Instr := .div d a b
abbrev iMod (d a b : Fin 16) : Instr := .mod d a b
abbrev iBand (d a b : Fin 16) : Instr := .band d a b
abbrev iBor (d a b : Fin 16) : Instr := .bor d a b
abbrev iBxor (d a b : Fin 16) : Instr := .bxor d a b
abbrev iShl (d a b : Fin 16) : Instr := .shl d a b
abbrev iShr (d a b : Fin 16) : Instr := .shr d a b
abbrev iLt (d a b : Fin 16) : Instr := .lt d a b
abbrev iLd (d a : Fin 16) : Instr := .load d a
abbrev iSt (a v : Fin 16) : Instr := .store a v
abbrev iTbl (d a : Fin 16) : Instr := .qDet d a
abbrev iJz (c : Fin 16) (t : ℕ) : Instr := .jz c t
abbrev iJmp (t : ℕ) : Instr := .jmp t
abbrev iHalt : Instr := .halt
/-- `d := v`. -/
abbrev movI (d : Fin 16) (v : ℕ) : List Instr := [iImm d v]
/-- `d := a + b`. -/
abbrev addR (d a b : Fin 16) : List Instr := [iAdd d a b]
/-- `d := a * b`. -/
abbrev mulR (d a b : Fin 16) : List Instr := [iMul d a b]
/-- `d := a / b`. -/
abbrev divR (d a b : Fin 16) : List Instr := [iDiv d a b]
/-- `d := a % b`. -/
abbrev modR (d a b : Fin 16) : List Instr := [iMod d a b]
/-- `d := a &&& b`. -/
abbrev bandR (d a b : Fin 16) : List Instr := [iBand d a b]
/-- `d := a >>> b`. -/
abbrev shrR (d a b : Fin 16) : List Instr := [iShr d a b]
/-- `d := mem[a]`. -/
abbrev ld (d a : Fin 16) : List Instr := [iLd d a]
/-- `mem[a] := v`. -/
abbrev st (a v : Fin 16) : List Instr := [iSt a v]
/-- `d := det[a]`, the preprocessed table. -/
abbrev tbl (d a : Fin 16) : List Instr := [iTbl d a]
/-- The body of one machine step: exactly the per-instruction branch of `step`. -/
def execInstr (i : Instr) (E : RAMEnv) (s : RAMState) : RAMState :=
let wr (d : Fin 16) (v : ℕ) : RAMState :=
{ s with pc := s.pc + 1, regs := Function.update s.regs d (v % 2 ^ E.W) }
let r := s.regs
match i with
| .halt => s
| .imm d v => wr d v
| .add d a b => wr d (r a + r b)
| .sub d a b => wr d (r a + 2 ^ E.W - r b)
| .mul d a b => wr d (r a * r b)
| .div d a b => wr d (r a / r b)
| .mod d a b => wr d (r a % r b)
| .band d a b => wr d (r a &&& r b)
| .bor d a b => wr d (r a ||| r b)
| .bxor d a b => wr d (r a ^^^ r b)
| .shl d a b => wr d (r a * 2 ^ r b)
| .shr d a b => wr d (r a / 2 ^ r b)
| .lt d a b => wr d (if r a < r b then 1 else 0)
| .load d a => wr d (s.mem (r a))
| .store a v => { s with pc := s.pc + 1, mem := Function.update s.mem (r a) (r v) }
| .jz c t => { s with pc := if r c = 0 then t else s.pc + 1 }
| .jmp t => { s with pc := t }
| .qDet d a => wr d (E.det (r a))
| .qPerm d k a => wr d (E.perm (r k) (r a))
| .qPermInv d k a => wr d (E.permInv (r k) (r a))
| .qCoeff d k a => wr d (E.coeff (r k) (r a))
/-- An instruction that neither jumps nor halts. -/
def Instr.NoBranchI (i : Instr) : Prop :=
(∀ t, i ≠ .jmp t) ∧ (∀ d t, i ≠ .jz d t) ∧ i ≠ .halt
/-- A chunk is straight-line when it has no `jmp`, no `jz` and no `halt`. -/
def NoBranch : List Instr → Prop
| [] => True
| i :: c => i.NoBranchI ∧ NoBranch c
/-- Run a jump-free block of instructions. -/
def runBlock (code : List Instr) (E : RAMEnv) (s : RAMState) : RAMState :=
code.foldl (fun acc i => execInstr i E acc) s
/-- `At P a l`: the instructions of `l` occupy the consecutive addresses `a, a+1, …, a+l.length-1`
of `P`. -/
def At (P : Program) (a : ℕ) (l : List Instr) : Prop :=
∀ r, r < l.length → P[a + r]? = l[r]?
/-- A test on the machine's registers. -/
inductive Cond where
/-- Holds iff `r ≠ 0`. -/
| neqz (r : Fin 16)
/-- Holds iff `a < b`, materialised as `d := (a < b)`. -/
| lt (d a b : Fin 16)
/-- The straight-line code that materialises a test. -/
def Cond.code : Cond → List Instr
| .neqz _ => []
| .lt d a b => [iLt d a b]
/-- The register whose being zero means that the test fails. -/
def Cond.test : Cond → Fin 16
| .neqz r => r
| .lt d _ _ => d
/-- A statement of the programming language. -/
inductive Stmt where
/-- A straight-line chunk. -/
| code (l : List Instr)
/-- `a` then `b`. -/
| seq (a b : Stmt)
/-- If the test holds then `a`, else `b`. -/
| ite (c : Cond) (a b : Stmt)
/-- While the test holds, `b`. -/
| loop (c : Cond) (b : Stmt)
/-- The number of instructions a statement compiles to. -/
def Stmt.len : Stmt → ℕ
| .code l => l.length
| .seq a b => a.len + b.len
| .ite c a b => c.code.length + a.len + b.len + 3
| .loop c b => c.code.length + b.len + 2
/-- Compile a statement at the absolute address `base`: every jump target is computed here, once. -/
def Stmt.compile : Stmt → ℕ → Program
| .code l, _ => l
| .seq a b, base => a.compile base ++ b.compile (base + a.len)
| .ite c a b, base =>
c.code ++ [iJz c.test (base + c.code.length + a.len + 2)] ++ a.compile (base + c.code.length + 1) ++
[iJmp (base + c.code.length + a.len + b.len + 3)] ++ b.compile (base + c.code.length + a.len + 2) ++
[iJmp (base + c.code.length + a.len + b.len + 3)]
| .loop c b, base =>
c.code ++ [iJz c.test (base + c.code.length + b.len + 2)] ++ b.compile (base + c.code.length + 1) ++
[iJmp base]
/-- `Sem P E a b s Q`: from the state `s`, whose program counter is `a`, the machine reaches a state
whose program counter is `b`, in `k` steps, and `Q k` holds of that state. The cost is the first
argument of `Q`, so a time bound is part of the postcondition. -/
def Sem (P : Program) (E : RAMEnv) (a b : ℕ) (s : RAMState) (Q : ℕ → RAMState → Prop) : Prop :=
s.pc = a ∧ ∃ (k : ℕ) (s' : RAMState), (step P E)^[k] s = s' ∧ s'.pc = b ∧ Q k s'
section Enc
variable {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
/-- The integer whose `k`-th bit is the `k`-th coordinate of `z` in the basis `b`. This is the form
in which the word-RAM stores a field element: one `w`-bit field of a word. -/
noncomputable def enc (b : Module.Basis (Fin w) (ZMod 2) F) (z : F) : ℕ :=
∑ k : Fin w, (b.repr z k).val * 2 ^ (k : ℕ)
/-- The field element spelled by the `w`-bit integer `a`; the machine side of `enc`. -/
noncomputable def dec (b : Module.Basis (Fin w) (ZMod 2) F) (a : ℕ) : F :=
b.repr.symm
(Finsupp.equivFunOnFinite.symm (fun k : Fin w => (((a / 2 ^ (k : ℕ)) % 2 : ℕ) : ZMod 2)))
end Enc
section Tables
variable {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
end Tables
section ReadInt
end ReadInt
section ReadLoop
end ReadLoop
section ProgramAt
end ProgramAt
section ReadSpec
end ReadSpec
section ReadStmt
end ReadStmt
section Bounds
end Bounds
section Prologue
end Prologue
section ReadAssembly
variable {F : Type} [Field F] [Algebra (ZMod 2) F]
end ReadAssembly
section Expand
variable {F : Type} [Field F] [Algebra (ZMod 2) F]
end Expand
section ExpandStd
variable {F : Type} [Field F] [Algebra (ZMod 2) F]
end ExpandStd
/-- The first `L` coefficients of a polynomial are stored at `B`. -/
def PolynomialStored {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (m : ℕ → ℕ) (B L : ℕ) (p : F[X]) : Prop :=
∀ i < L, m (B + i) = enc b (p.coeff i)
def boundaryState (pc : ℕ) (m : ℕ → ℕ) : RAMState := ⟨pc, fun _ => 0, m⟩
def MemoryFrame (allowed : ℕ → Prop) (before after : ℕ → ℕ) : Prop :=
∀ addr, ¬ allowed addr → after addr = before addr
/-- A field-valued vector stored in consecutive RAM words. -/
def FieldArrayStored {F : Type} [Field F] [Algebra (ZMod 2) F] {w : ℕ}
(b : Module.Basis (Fin w) (ZMod 2) F) (m : ℕ → ℕ) (B len : ℕ) (v : ℕ → F) : Prop :=
∀ j < len, m (B + j) = enc b (v j)
section PinBits
variable {F : Type} [Field F] [Algebra (ZMod 2) F]
end PinBits
section Uniqueness
variable {F : Type} [Field F] [Algebra (ZMod 2) F]
end Uniqueness
section Slp
variable {F : Type} [Field F]
end Slp
end LinearSetReconciliation327.Main
Source
arXiv:2611.11409, Section 2.2 (Pinsketch) and Appendix C (decoder implementation); Dodis, Ostrovsky, Reyzin, Smith, Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data, SIAM J. Comput. 38(1), 2008, Section 6.3