Word-RAM routine for reading one self-delimiting integer
DefinitionITPIRPreproc_MatchVec_RAMEncodingcryptographyformal-verificationword-ram
An explicit 11-instruction deterministic streaming word-RAM program for the integer encoding used by this mission. The encoding stores the binary digits in little-endian order, with a true continuation flag before each digit and a false terminating flag. The program accumulates the value in register 0, keeps the next power of two in register 1, and halts after reading the terminating flag. Registers 2 and 3 are temporary, register 4 holds one, and register 5 remains zero. It produces no output bits.
This is an implementation helper for the mission's formal input format, not a new definition of PIR or an assumed implementation theorem. Its correctness, termination, and costs are separate proof obligations.
Definition code
import Definitions.Def_ITPIRPreproc_MatchVec_Machine
namespace ITPIRPreproc.MatchVec.WordRAM
/-- A streaming deterministic program reading one `encNat` integer. Register 0 is
the accumulator, 1 is the current binary weight, 2 is the continuation flag,
3 is the bit/contribution temporary, 4 contains one, and 5 remains zero.
The program halts immediately after the first terminating false flag. -/
def readNatProgram : Program :=
[ .const 0 0,
.const 1 1,
.const 4 1,
.inBit 2,
.jlt 5 2 6,
.halt,
.inBit 3,
.mul 3 3 1,
.add 0 0 3,
.add 1 1 1,
.jlt 5 4 3 ]
end ITPIRPreproc.MatchVec.WordRAM
Source
Derived implementation for encNat in Definitions.Def_ITPIRPreproc_MatchVec_Machine (the mission word-RAM and bit-string encoding). Used by the indexed matching-vector routines of Dujmovic-Lai-Wichs, Nearly Optimal Information-Theoretic PIR with Client Preprocessing, Appendix A, printed pp.36-37. The instruction sequence is supplied by this formalization, not stated in the paper.