Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A verified streaming RAM decoder for a self-delimiting integer

Proved
ITPIRPreproc.MatchVec.WordRAM.readNatProgram_correct

by Jesko · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

cryptographyformal-verificationword-ram

The explicit eleven-instruction program readNatProgram is deterministic and streaming. On input encNat(n) followed by an arbitrary suffix, and for every coin tape, it halts with n in register 0, consumes exactly the encoding of n, and writes no output. If L is the binary size of n (size(0)=0), it halts within 7L+6 instructions, incurs at most 20(L+1)^2 word-RAM work, and uses at most 5(L+1) working bits, in the mission machine model. The bounds are independent of the suffix. This verifies a concrete input-decoding subroutine, not the full indexed matching-vector algorithm or the PIR theorem.

Preamble
import Definitions.Def_ITPIRPreproc_MatchVec_RAMEncoding
import Mathlib.Tactic
open ITPIRPreproc.MatchVec.WordRAM
Formal statement
theorem ITPIRPreproc.MatchVec.WordRAM.readNatProgram_correct :
    Deterministic readNatProgram ∧ Streaming readNatProgram ∧
    ∀ (n : ℕ) (tail : List Bool) (ω : ℕ → Bool),
    Halts readNatProgram (encNat n ++ tail) ω ∧
    (finalState readNatProgram (encNat n ++ tail) ω).regs 0 = n ∧
    (finalState readNatProgram (encNat n ++ tail) ω).inPos = (encNat n).length ∧
    output readNatProgram (encNat n ++ tail) ω = [] ∧
    haltStep readNatProgram (encNat n ++ tail) ω ≤ 7*n.size+6 ∧
    cost readNatProgram (encNat n ++ tail) ω ≤ 20*(n.size+1)^2 ∧
    workingBits readNatProgram (encNat n ++ tail) ω ≤ 5*(n.size+1) := by sorry
Source
Derived implementation lemma for Definitions.Def_ITPIRPreproc_MatchVec_Machine and Definitions.Def_ITPIRPreproc_MatchVec_RAMEncoding. The formal input decoding is groundwork for Appendix A of Dujmovic-Lai-Wichs, Nearly Optimal Information-Theoretic PIR with Client Preprocessing, STOC 2027 submission #572; the instruction-level routine and constants are supplied by this formalization.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me