Certified packet encoding and exact pair and triple parsers
DefinitionWitnessEncryption_Runtime_SamplingSerializationFor a finite bit string , the canonical packet encoding inserts a marker before each payload bit and terminates the packet with a delimiter. Its length is
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 realizing , there are fixed such that every encoded input satisfies
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.
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