Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Certified packet encoding and exact pair and triple parsers

Definition
WitnessEncryption_Runtime_SamplingSerialization

by vigyan · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

generic-groupspolynomial-timeruntimewe-prime-order-2026witness-encryption

For a finite bit string bbb, the canonical packet encoding inserts a marker before each payload bit and terminates the packet with a delimiter. Its length is

∣packet⁡(b)∣=2∣b∣+1.|\operatorname{packet}(b)|=2|b|+1.∣packet(b)∣=2∣b∣+1.

This module provides concrete realizers for packet encoding, packet scanning, and exact pair and triple parsing. The pair and triple parsers require the entire input to consist of exactly two or three packets, respectively, and return failure on malformed input or trailing data. The implementations are total on arbitrary input bit strings.

The realizers carry polynomial resource certificates: for each fixed routine RRR realizing fff, there are fixed d,CT,CV∈Nd,C_T,C_V\in\mathbb Nd,CT​,CV​∈N such that every encoded input xxx satisfies

R.time⁡(x)≤CT(vol⁡(x)+2)d,vol⁡(f(x))≤CV(vol⁡(x)+2)d.R.\operatorname{time}(x)\le C_T(\operatorname{vol}(x)+2)^d,\qquad \operatorname{vol}(f(x))\le C_V(\operatorname{vol}(x)+2)^d.R.time(x)≤CT​(vol(x)+2)d,vol(f(x))≤CV​(vol(x)+2)d.

The module also supplies certificate-preserving option and branching combinators and the concrete two-field and three-field serialization routines. For each fixed tag pattern, its equality-test program has a polynomial resource certificate with that pattern as a fixed program parameter. These interfaces support the byte-level sampling and oracle-program inputs used by the witness-encryption construction.

Definition code
import Definitions.Def_WitnessEncryption_Runtime_Core
import Definitions.Def_GenericGroupWE_Main_Complexity
import Definitions.Def_GenericGroupWE_Main_Oracle

set_option autoImplicit false

section
-- Source: WitnessEncryption.Runtime.Sampling.Packets

set_option maxHeartbeats 2000000

namespace GenericGroupWE.Main.SamplingRuntime

open OAI.ThreeMachine.StackCompiler

theorem packet_length (bs : Bits) : (packet bs).length = 2*bs.length+1 := by
  induction bs with
  | nil => rfl
  | cons b bs ih => simp only [packet,List.length_cons,ih]; omega





def readPair (bs : Bits) : Option (Bits × Bits) := do
  let (first, rest) ← unpacket bs
  let (second, tail) ← unpacket rest
  if tail.isEmpty then pure (first,second) else none






















 theorem packet_prefix (bs : Bits) :
    packet bs = (bs.flatMap fun b => [true,b]) ++ [false] := by
  induction bs with
  | nil => rfl
  | cons b bs ih => simp [packet,ih]

 theorem packet_fold (bs acc : Bits) :
    bs.reverse.foldl (fun ys b => true :: b :: ys) acc =
      (bs.flatMap fun b => [true,b]) ++ acc := by
  induction bs with
  | nil => rfl
  | cons b bs ih => simp [List.reverse_cons,List.foldl_append,ih]

def packetStep : Uniform (fun (_ : Unit) (x : Bool × Bits) => true :: x.1 :: x.2) :=
  (((Uniform.constant true).pair
    (Uniform.cons : Uniform (fun (_ : Unit) (x : Bool × Bits) => x.1 :: x.2))).comp Uniform.cons).congr
      (fun _ _ => rfl)

def packetUniform : Uniform (fun (_ : Unit) (bs : Bits) => packet bs) :=
  (((Uniform.reverse.pair (Uniform.constant ([false] : Bits))).comp packetStep.fold)).congr (fun _ bs => by
    simp only [Function.comp_apply,packet_fold]
    exact (packet_prefix bs).symm)

def packetRealizer : Realizer packet := packetUniform.specialize ()

 theorem packet_step_time (b : Bool) (ys : Bits) :
    packetStep.time () (b,ys) ≤ 2000 * (volume (b,ys)+1) := by
  simp only [packetStep,Uniform.time_congr,Uniform.time_comp,Uniform.time_pair,Uniform.time_constant,Uniform.time_cons,
    volume_pair,volume_cons,volume_bool_true]
  omega

 theorem packet_fold_time (xs ys : Bits) :
    Realizer.foldTime (packetStep.specialize ()) ys xs ≤
      xs.length * (10000 * (5*volume xs+volume ys+1)) + 1 := by
  induction xs generalizing ys with
  | nil => simp [Realizer.foldTime]
  | cons b xs ih =>
    have hh := ih (true :: b :: ys)
    have hs := packet_step_time b ys
    change Realizer.time (packetStep.specialize ()) (b,ys) +
      Realizer.foldTime (packetStep.specialize ()) (true :: b :: ys) xs +
      20*(volume (b :: xs)+volume ys+volume (true :: b :: ys)+1) ≤ _
    change Realizer.time (packetStep.specialize ()) (b,ys) ≤ _ at hs
    simp only [volume_cons,volume_pair,volume_bool_true,List.length_cons] at hh hs ⊢
    nlinarith [volume_pos b,volume_pos xs,volume_pos ys]

 theorem bits_volume (bs : Bits) : volume bs ≤ 4*bs.length+1 := by
  simpa only [show (3:ℕ)+1=4 from rfl,Nat.mul_comm] using
    volume_list_le bs 3 (fun b _ => volume_bool b)

theorem packet_realizer_time (bs : Bits) :
    packetRealizer.time bs ≤ CookLevin.polyBound 10000000 2 bs.length := by
  have hr := Uniform.time_reverse (I := Unit) (α := fun _ => Bool) () bs
  have hf := packet_fold_time bs.reverse [false]
  have hv := bits_volume bs
  simp only [List.length_reverse,volume_reverse,volume_cons,volume_bool_false,volume_nil] at hf
  have hv1 : volume bs + 1 ≤ 4*bs.length+2 := by omega
  have hfv : 5*volume bs+4 ≤ 5*(4*bs.length+1)+4 := by omega
  have hr' := hr.trans (Nat.mul_le_mul_left (200*(bs.length+1)) hv1)
  have hf' := hf.trans (Nat.add_le_add_right (Nat.mul_le_mul_left bs.length
    (Nat.mul_le_mul_left 10000 hfv)) 1)
  change packetUniform.time () bs ≤ _
  simp only [packetUniform,Uniform.time_congr,Uniform.time_comp,Uniform.time_pair,Uniform.time_constant,Uniform.time_fold,
    volume_pair,volume_cons,volume_bool_false,volume_nil,volume_reverse]
  unfold CookLevin.polyBound
  nlinarith



end GenericGroupWE.Main.SamplingRuntime


end

section
-- Source: WitnessEncryption.Runtime.Sampling.Parser

namespace GenericGroupWE.Main.SamplingRuntime

/-- Exact three-field parser; the continuation envelope has two fields instead. -/
def readTriple (bs : Bits) : Option (Bits × Bits × Bits) := do
  let (first,rest) ← unpacket bs
  let (second,rest) ← unpacket rest
  let (third,tail) ← unpacket rest
  if tail.isEmpty then pure (first,second,third) else none




open OAI.ThreeMachine.StackCompiler WitnessEncryption.Runtime
open WitnessEncryption.Runtime.ListPrimitives

universe u v

def iteR {α : Type u} {β : Type v} [Coding α] [Coding β]
    {p : α → Bool} {f g : α → β} (P : Realizer p) (T : Realizer f) (E : Realizer g) :
    Realizer (fun x => if p x then f x else g x) :=
  ((P.pair Realizer.id).comp (T.choose E)).congr (fun _ => rfl)

theorem ite_certified {α : Type u} {β : Type v} [Coding α] [Coding β]
    {p : α → Bool} {f g : α → β} {P : Realizer p} {T : Realizer f} {E : Realizer g}
    (hP : Certified P) (hT : Certified T) (hE : Certified E) :
    Certified (iteR P T E) := by
  exact ((hP.pair Certified.identity).comp (hT.choose hE)).congr (fun _ => rfl)

def optionSomeR {α : Type u} [Coding α] : Realizer (fun a : α => some a) :=
  (((Realizer.id.pair (Realizer.constant ())).comp
    (Realizer.reinterpret (fun x : α × Unit => some x.1) (fun _ => rfl)))).congr (fun _ => rfl)

theorem optionSome_certified {α : Type u} [Coding α] :
    Certified (optionSomeR : Realizer (fun a : α => some a)) := by
  exact ((Certified.identity.pair (Certified.constant ())).comp
    (Certified.reinterpret (fun x : α × Unit => some x.1) (fun _ => rfl))).congr (fun _ => rfl)







abbrev PacketScanState := Bool × Bool × Bits × Bits

/-- One physical input bit; flags encode done/pending-data and both lists are reversed. -/
def packetScanStep (x : Bool × PacketScanState) : PacketScanState :=
  let b := x.1
  let s := x.2
  if s.1 then (true,s.2.1,s.2.2.1,b :: s.2.2.2)
  else if s.2.1 then (false,false,b :: s.2.2.1,s.2.2.2)
  else if b then (false,true,s.2.2.1,s.2.2.2)
  else (true,false,s.2.2.1,s.2.2.2)

def packetScan (bs : Bits) (s : PacketScanState) : PacketScanState :=
  bs.foldl (fun s b => packetScanStep (b,s)) s

def packetScanFinish (s : PacketScanState) : Option (Bits × Bits) :=
  if s.1 then some (s.2.2.1.reverse,s.2.2.2.reverse) else none

def unpacketScan (bs : Bits) : Option (Bits × Bits) :=
  packetScanFinish (packetScan bs (false,false,[],[]))

 theorem scan_done (bs : Bits) (pending : Bool) (decoded tail : Bits) :
    packetScan bs (true,pending,decoded,tail) =
      (true,pending,decoded,bs.reverse ++ tail) := by
  induction bs generalizing tail with
  | nil => rfl
  | cons b bs ih =>
    simpa [packetScan,packetScanStep,List.reverse_cons,List.append_assoc] using ih (b::tail)

 theorem scan_correct_aux (bs decoded : Bits) :
    packetScanFinish (packetScan bs (false,false,decoded,[])) =
      (unpacket bs).map (fun x => (decoded.reverse ++ x.1,x.2)) := by
  cases bs with
  | nil => rfl
  | cons flag tail =>
    cases flag with
    | false =>
      change packetScanFinish (packetScan tail (true,false,decoded,[])) = _
      rw [scan_done]
      simp [packetScanFinish,unpacket]
    | true =>
      cases tail with
      | nil => rfl
      | cons b bs =>
        change packetScanFinish (packetScan bs (false,false,b::decoded,[])) = _
        rw [scan_correct_aux bs (b::decoded)]
        cases h : unpacket bs <;> simp [unpacket,h,List.reverse_cons,List.append_assoc]
termination_by bs.length

theorem unpacketScan_eq (bs : Bits) : unpacketScan bs = unpacket bs := by
  have h := scan_correct_aux bs []
  simpa [unpacketScan] using h

 def scanBitR : Realizer (fun x : Bool × PacketScanState => x.1) := Realizer.fst
 def scanDoneR : Realizer (fun x : Bool × PacketScanState => x.2.1) :=
  Realizer.snd.comp Realizer.fst
 def scanPendingR : Realizer (fun x : Bool × PacketScanState => x.2.2.1) :=
  (Realizer.snd.comp Realizer.snd).comp Realizer.fst
 def scanDecodedR : Realizer (fun x : Bool × PacketScanState => x.2.2.2.1) :=
  ((Realizer.snd.comp Realizer.snd).comp Realizer.snd).comp Realizer.fst
 def scanTailR : Realizer (fun x : Bool × PacketScanState => x.2.2.2.2) :=
  ((Realizer.snd.comp Realizer.snd).comp Realizer.snd).comp Realizer.snd

 theorem scanBit_certified : Certified scanBitR := Certified.fst
 theorem scanDone_certified : Certified scanDoneR := Certified.snd.comp Certified.fst
 theorem scanPending_certified : Certified scanPendingR :=
  (Certified.snd.comp Certified.snd).comp Certified.fst
 theorem scanDecoded_certified : Certified scanDecodedR :=
  ((Certified.snd.comp Certified.snd).comp Certified.snd).comp Certified.fst
 theorem scanTail_certified : Certified scanTailR :=
  ((Certified.snd.comp Certified.snd).comp Certified.snd).comp Certified.snd

 def scanDoneBranchR : Realizer (fun x : Bool × PacketScanState =>
    (true,x.2.2.1,x.2.2.2.1,x.1 :: x.2.2.2.2)) :=
  (Realizer.constant true).pair (scanPendingR.pair
    (scanDecodedR.pair ((scanBitR.pair scanTailR).comp Realizer.cons)))
 def scanPendingBranchR : Realizer (fun x : Bool × PacketScanState =>
    (false,false,x.1 :: x.2.2.2.1,x.2.2.2.2)) :=
  (Realizer.constant false).pair ((Realizer.constant false).pair
    (((scanBitR.pair scanDecodedR).comp Realizer.cons).pair scanTailR))
 def scanTrueBranchR : Realizer (fun x : Bool × PacketScanState =>
    (false,true,x.2.2.2.1,x.2.2.2.2)) :=
  (Realizer.constant false).pair ((Realizer.constant true).pair (scanDecodedR.pair scanTailR))
 def scanFalseBranchR : Realizer (fun x : Bool × PacketScanState =>
    (true,false,x.2.2.2.1,x.2.2.2.2)) :=
  (Realizer.constant true).pair ((Realizer.constant false).pair (scanDecodedR.pair scanTailR))

 theorem scanDoneBranch_certified : Certified scanDoneBranchR :=
  (Certified.constant true).pair (scanPending_certified.pair
    (scanDecoded_certified.pair ((scanBit_certified.pair scanTail_certified).comp cons_certified)))
 theorem scanPendingBranch_certified : Certified scanPendingBranchR :=
  (Certified.constant false).pair ((Certified.constant false).pair
    (((scanBit_certified.pair scanDecoded_certified).comp cons_certified).pair scanTail_certified))
 theorem scanTrueBranch_certified : Certified scanTrueBranchR :=
  (Certified.constant false).pair ((Certified.constant true).pair (scanDecoded_certified.pair scanTail_certified))
 theorem scanFalseBranch_certified : Certified scanFalseBranchR :=
  (Certified.constant true).pair ((Certified.constant false).pair (scanDecoded_certified.pair scanTail_certified))

def packetScanStepR : Realizer packetScanStep :=
  (iteR scanDoneR scanDoneBranchR
    (iteR scanPendingR scanPendingBranchR
      (iteR scanBitR scanTrueBranchR scanFalseBranchR))).congr (fun _ => rfl)

theorem packetScanStep_certified : Certified packetScanStepR :=
  (ite_certified scanDone_certified scanDoneBranch_certified
    (ite_certified scanPending_certified scanPendingBranch_certified
      (ite_certified scanBit_certified scanTrueBranch_certified scanFalseBranch_certified))).congr (fun _ => rfl)

 theorem packetScanStep_volume (x : Bool × PacketScanState) :
    volume (packetScanStep x) ≤ volume x.2+8 := by
  rcases x with ⟨b,done,pending,decoded,tail⟩
  cases b <;> cases done <;> cases pending <;>
    simp [packetScanStep,volume_cons,volume_pair] <;> omega

 theorem packetScan_volume (bs : Bits) (s : PacketScanState) :
    volume (packetScan bs s) ≤ volume s+8*bs.length := by
  induction bs generalizing s with
  | nil => simp [packetScan]
  | cons b bs ih =>
    have hh := ih (packetScanStep (b,s))
    have hs := packetScanStep_volume (b,s)
    change volume (packetScanStep (b,s)) ≤ volume s+8 at hs
    change volume (packetScan bs (packetScanStep (b,s))) ≤ _
    simp only [List.length_cons]
    omega

 theorem packetScanFold_certified : Certified packetScanStepR.fold := by
  apply Certified.fold packetScanStep_certified
  refine ⟨10,1,?_⟩
  intro x j hj
  have hv := packetScan_volume (x.1.take j) x.2
  have hl := List.length_take_le j x.1
  have hx := WitnessEncryption.Runtime.length_le_volume x.1
  change volume (packetScan (x.1.take j) x.2) ≤ _
  have htotal := volume_prod x
  simp only [pow_one]
  omega

 def packetScanR : Realizer (fun bs : Bits => packetScan bs (false,false,[],[])) :=
  ((Realizer.id.pair (Realizer.constant (false,false,([] : Bits),([] : Bits)))).comp
    packetScanStepR.fold).congr (fun _ => rfl)

 theorem packetScan_certified : Certified packetScanR :=
  ((Certified.identity.pair (Certified.constant (false,false,([] : Bits),([] : Bits)))).comp
    packetScanFold_certified).congr (fun _ => rfl)

 def finishDoneR : Realizer (fun s : PacketScanState => s.1) := Realizer.fst
 def finishDecodedR : Realizer (fun s : PacketScanState => s.2.2.1.reverse) :=
  ((Realizer.snd.comp Realizer.snd).comp Realizer.fst).comp reverseR
 def finishTailR : Realizer (fun s : PacketScanState => s.2.2.2.reverse) :=
  ((Realizer.snd.comp Realizer.snd).comp Realizer.snd).comp reverseR

 theorem finishDone_certified : Certified finishDoneR := Certified.fst
 theorem finishDecoded_certified : Certified finishDecodedR :=
  ((Certified.snd.comp Certified.snd).comp Certified.fst).comp reverse_certified
 theorem finishTail_certified : Certified finishTailR :=
  ((Certified.snd.comp Certified.snd).comp Certified.snd).comp reverse_certified

 def packetScanFinishR : Realizer packetScanFinish :=
  (iteR finishDoneR ((finishDecodedR.pair finishTailR).comp optionSomeR)
    (Realizer.constant none)).congr (fun _ => rfl)

 theorem packetScanFinish_certified : Certified packetScanFinishR :=
  (ite_certified finishDone_certified
    ((finishDecoded_certified.pair finishTail_certified).comp optionSome_certified)
    (Certified.constant none)).congr (fun _ => rfl)

def unpacketRealizer : Realizer unpacket :=
  (packetScanR.comp packetScanFinishR).congr unpacketScan_eq

theorem unpacket_realizer_certified : Certified unpacketRealizer :=
  (packetScan_certified.comp packetScanFinish_certified).congr unpacketScan_eq

theorem test_certified {α : Type u} [Coding α] (p : α → Bool)
    (h : ∀ x, (enc x).nonempty = p x) : Certified (Realizer.test p h) := by
  refine ⟨1, ?_, (Poly.volumeBool volume p).lift (by omega)⟩
  apply Poly.of_le (g := fun x : α => 10000*(volume x+1))
  · exact Realizer.time_test_le p h
  · simpa only [Nat.max_zero,Nat.zero_add] using
      (OAI.ThreeMachine.StackCompiler.Poly.const volume 10000).mul
        ((Poly.size volume).add (OAI.ThreeMachine.StackCompiler.Poly.const volume 1))

def optionIsSomeR {α : Type u} [Coding α] : Realizer (fun o : Option α => o.isSome) :=
  Realizer.test _ (by intro o; cases o <;> rfl)

theorem optionIsSome_certified {α : Type u} [Coding α] :
    Certified (optionIsSomeR : Realizer (fun o : Option α => o.isSome)) :=
  test_certified _ _

def bitsIsEmptyR : Realizer (fun bs : Bits => bs.isEmpty) :=
  ((Realizer.test (fun bs : Bits => !bs.isEmpty) (by intro bs; cases bs <;> rfl)).comp
    Realizer.not).congr (fun bs => by cases bs <;> rfl)

theorem bitsIsEmpty_certified : Certified bitsIsEmptyR :=
  ((test_certified _ _).comp (Certified.of_finite Realizer.not)).congr
    (fun bs => by cases bs <;> rfl)

def optionBindR {α : Type u} {β : Type v} [Coding α] [Coding β] [Inhabited α]
    {f : α → Option β} (F : Realizer f) : Realizer (fun o : Option α => o.bind f) :=
  (iteR optionIsSomeR
    ((((Realizer.id.pair (Realizer.constant (default : α))).comp getDR).comp F))
    (Realizer.constant none)).congr (fun o => by cases o <;> rfl)

theorem optionBind_certified {α : Type u} {β : Type v} [Coding α] [Coding β] [Inhabited α]
    {f : α → Option β} {F : Realizer f} (hF : Certified F) : Certified (optionBindR F) :=
  (ite_certified optionIsSome_certified
    ((((Certified.identity.pair (Certified.constant (default : α))).comp getD_certified).comp hF))
    (Certified.constant none)).congr (fun o => by cases o <;> rfl)

def optionBindEnvR {α : Type u} {β : Type v} {γ : Type*}
    [Coding α] [Coding β] [Coding γ] [Inhabited α]
    {f : α × γ → Option β} (F : Realizer f) :
    Realizer (fun x : Option α × γ => x.1.bind (fun a => f (a,x.2))) :=
  (iteR (Realizer.fst.comp optionIsSomeR)
    (((((Realizer.fst.pair (Realizer.constant (default : α))).comp getDR).pair Realizer.snd)).comp F)
    (Realizer.constant none)).congr (fun x => by rcases x with ⟨o,e⟩; cases o <;> rfl)

theorem optionBindEnv_certified {α : Type u} {β : Type v} {γ : Type*}
    [Coding α] [Coding β] [Coding γ] [Inhabited α]
    {f : α × γ → Option β} {F : Realizer f} (hF : Certified F) :
    Certified (optionBindEnvR F) :=
  (ite_certified (Certified.fst.comp optionIsSome_certified)
    (((((Certified.fst.pair (Certified.constant (default : α))).comp getD_certified).pair
      Certified.snd)).comp hF)
    (Certified.constant none)).congr (fun x => by rcases x with ⟨o,e⟩; cases o <;> rfl)

 def pairFinish (x : (Bits × Bits) × Bits) : Option (Bits × Bits) :=
  if x.1.2.isEmpty then some (x.2,x.1.1) else none

 def pairFinishR : Realizer pairFinish :=
  (iteR ((Realizer.fst.comp Realizer.snd).comp bitsIsEmptyR)
    ((Realizer.snd.pair (Realizer.fst.comp Realizer.fst)).comp optionSomeR)
    (Realizer.constant none)).congr (fun _ => rfl)

 theorem pairFinish_certified : Certified pairFinishR :=
  (ite_certified ((Certified.fst.comp Certified.snd).comp bitsIsEmpty_certified)
    ((Certified.snd.pair (Certified.fst.comp Certified.fst)).comp optionSome_certified)
    (Certified.constant none)).congr (fun _ => rfl)

 def pairAfterFirst (x : Bits × Bits) : Option (Bits × Bits) :=
  (unpacket x.2).bind (fun y => pairFinish (y,x.1))

 def pairAfterFirstR : Realizer pairAfterFirst :=
  ((((Realizer.snd.comp unpacketRealizer).pair Realizer.fst).comp
    (optionBindEnvR pairFinishR))).congr (fun _ => rfl)

 theorem pairAfterFirst_certified : Certified pairAfterFirstR :=
  ((((Certified.snd.comp unpacket_realizer_certified).pair Certified.fst).comp
    (optionBindEnv_certified pairFinish_certified))).congr (fun _ => rfl)

 theorem pair_after_spec (bs : Bits) : (unpacket bs).bind pairAfterFirst = readPair bs := by
  rfl

def readPairRealizer : Realizer readPair :=
  (unpacketRealizer.comp (optionBindR pairAfterFirstR)).congr pair_after_spec

theorem readPair_realizer_certified : Certified readPairRealizer :=
  (unpacket_realizer_certified.comp (optionBind_certified pairAfterFirst_certified)).congr pair_after_spec

 def tripleBuild (x : (Bits × Bits) × Bits) : Option (Bits × Bits × Bits) :=
  some (x.2,x.1.1,x.1.2)

 def tripleBuildR : Realizer tripleBuild :=
  ((Realizer.snd.pair Realizer.fst).comp optionSomeR).congr (fun _ => rfl)

 theorem tripleBuild_certified : Certified tripleBuildR :=
  ((Certified.snd.pair Certified.fst).comp optionSome_certified).congr (fun _ => rfl)

 def tripleAfterFirst (x : Bits × Bits) : Option (Bits × Bits × Bits) :=
  (readPair x.2).bind (fun y => tripleBuild (y,x.1))

 def tripleAfterFirstR : Realizer tripleAfterFirst :=
  ((((Realizer.snd.comp readPairRealizer).pair Realizer.fst).comp
    (optionBindEnvR tripleBuildR))).congr (fun _ => rfl)

 theorem tripleAfterFirst_certified : Certified tripleAfterFirstR :=
  ((((Certified.snd.comp readPair_realizer_certified).pair Certified.fst).comp
    (optionBindEnv_certified tripleBuild_certified))).congr (fun _ => rfl)

 theorem triple_after_spec (bs : Bits) :
    (unpacket bs).bind tripleAfterFirst = readTriple bs := by
  cases h0 : unpacket bs with
  | none => simp [h0,readTriple]
  | some pair =>
    rcases pair with ⟨first,rest⟩
    cases h1 : unpacket rest with
    | none => simp [h0,h1,readTriple,tripleAfterFirst,readPair]
    | some pair =>
      rcases pair with ⟨second,rest⟩
      cases h2 : unpacket rest with
      | none => simp [h0,h1,h2,readTriple,tripleAfterFirst,readPair]
      | some pair =>
        rcases pair with ⟨third,tail⟩
        by_cases ht : tail = [] <;>
          simp [h0,h1,h2,ht,readTriple,tripleAfterFirst,readPair,tripleBuild]

def readTripleRealizer : Realizer readTriple :=
  (unpacketRealizer.comp (optionBindR tripleAfterFirstR)).congr triple_after_spec

theorem readTriple_realizer_certified : Certified readTripleRealizer :=
  (unpacket_realizer_certified.comp (optionBind_certified tripleAfterFirst_certified)).congr triple_after_spec

end GenericGroupWE.Main.SamplingRuntime



end

section
-- Source: WitnessEncryption.Runtime.Sampling.Realization

namespace GenericGroupWE.Main.SamplingRuntime
namespace ScalarCost
open OAI.ThreeMachine.StackCompiler WitnessEncryption.Runtime
open WitnessEncryption.Runtime.ListPrimitives

 theorem packet_certified : Certified packetRealizer := by
  have hv (bs : Bits) : volume bs ≤ 4*bs.length+1 := by
    simpa only [show (3:ℕ)+1=4 from rfl,Nat.mul_comm] using
      volume_list_le bs 3 (fun b _ => volume_bool b)
  refine ⟨2, ⟨10000000, ?_⟩, ⟨10, ?_⟩⟩
  · intro bs
    exact (packet_realizer_time bs).trans (by
      unfold CookLevin.polyBound
      exact Nat.mul_le_mul_left _ (Nat.pow_le_pow_left (by have := length_le_volume bs; omega) 2))
  · intro bs
    have h := hv (packet bs)
    rw [packet_length] at h
    have hl := length_le_volume bs
    simp only [pow_two]
    nlinarith

def pack2R : Realizer (fun x : Bits × Bits => pack [x.1,x.2]) :=
  (((Realizer.fst.comp packetRealizer).pair (Realizer.snd.comp packetRealizer)).comp appendR).congr
    (fun x => by simp [pack])
theorem pack2_certified : Certified pack2R :=
  (((Certified.fst.comp packet_certified).pair (Certified.snd.comp packet_certified)).comp
    append_certified).congr (fun x => by simp [pack])

def pack3R : Realizer (fun x : Bits × Bits × Bits => pack [x.1,x.2.1,x.2.2]) :=
  (((Realizer.fst.comp packetRealizer).pair (Realizer.snd.comp pack2R)).comp appendR).congr
    (fun x => by simp [pack])
theorem pack3_certified : Certified pack3R :=
  (((Certified.fst.comp packet_certified).pair (Certified.snd.comp pack2_certified)).comp
    append_certified).congr (fun x => by simp [pack])




def headBitR : Realizer (fun bs : Bits => bs.head?.getD false) :=
  ((headR.pair (Realizer.constant false)).comp getDR).congr (fun _ => rfl)
theorem headBit_certified : Certified headBitR :=
  ((head_certified.pair (Certified.constant false)).comp getD_certified).congr (fun _ => rfl)

def boolEqR (b : Bool) : Realizer (fun a : Bool => decide (a=b)) :=
  ((Realizer.id.choose Realizer.not : Realizer (fun x : Bool × Bool => if x.1 then x.2 else !x.2)) |> 
    ((Realizer.constant b).pair Realizer.id).comp).congr (fun a => by cases a <;> cases b <;> rfl)
theorem boolEq_certified (b : Bool) : Certified (boolEqR b) := Certified.of_finite _

/-- A fixed finite tag is matched by actual head/tail routines, never Nat decoding. -/
def bitsEqR : (pat : Bits) → Realizer (fun bs : Bits => decide (bs=pat))
  | [] => bitsIsEmptyR.congr (fun bs => by cases bs <;> rfl)
  | b::pat =>
    (iteR bitsIsEmptyR (Realizer.constant false)
      (iteR (headBitR.comp (boolEqR b)) (tailR.comp (bitsEqR pat)) (Realizer.constant false))).congr
      (fun bs => by cases bs with
        | nil => rfl
        | cons a bs => cases a <;> cases b <;> simp <;> exact Bool.decide_congr Iff.rfl)

theorem bitsEq_certified (pat : Bits) : Certified (bitsEqR pat) := by
  induction pat with
  | nil => exact bitsIsEmpty_certified.congr (fun bs => by cases bs <;> rfl)
  | cons b pat ih =>
    exact (ite_certified bitsIsEmpty_certified (Certified.constant false)
      (ite_certified (headBit_certified.comp (boolEq_certified b))
        (tail_certified.comp ih) (Certified.constant false))).congr
      (fun bs => by cases bs with
        | nil => rfl
        | cons a bs => cases a <;> cases b <;> simp <;> exact Bool.decide_congr Iff.rfl)



























































































































end ScalarCost
end GenericGroupWE.Main.SamplingRuntime

end
Source
Runtime formalization supporting Hair and Sahai, Witness Encryption via Prime-Order Generic Groups, Section 6.5 and Theorems 3.1/6.1; supplied paper https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/47.pdf . Exact selected original declarations from WitnessEncryption/Runtime/Sampling/Packets.lean, Parser.lean and Realization.lean. Only the 53 required private modifiers are removed at their exact parsed positions; binding identifiers, values, proof bodies and reference text are unchanged; the 53 private kernel names become the explicitly mapped public names; export SHA256 7db3091cd1c89f1c8f10cc096eb97a5ac6c9d5d760add63d24bbe45ff58368e8.

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