import SeedPacket.Codec namespace SeedPacket open OmegaTransport def seedPacket (recipe seed : Nat) : List Nat := 1 :: recipe :: toBytes 2 seed def witnessPacket (recipe seed : Nat) : List Nat := 1 :: recipe :: packet seed def parse : List Nat → Option (Nat × Nat) | 1 :: recipe :: body => if recipe < 256 then if body.length = 2 then let seed := fromBytes body if seed ≤ maxSeed ∧ toBytes 2 seed = body then some (recipe, seed) else none else if body.length = 6 then let seed := (decodePacket body).headD 0 if seed ≤ maxSeed ∧ packet seed = body then some (recipe, seed) else none else none else none | _ => none theorem seed_packet_length (recipe seed : Nat) : (seedPacket recipe seed).length = 4 := by simp [seedPacket, bytes_length] theorem witness_packet_length (recipe seed : Nat) : (witnessPacket recipe seed).length = 8 := by simp [witnessPacket, packet_length] theorem parse_seed (recipe seed : Nat) (hr : recipe < 256) (hs : seed ≤ maxSeed) : parse (seedPacket recipe seed) = some (recipe, seed) := by have hw : seed < 256 ^ 2 := by unfold maxSeed at hs omega simp [parse, seedPacket, hr, bytes_length, from_to_bytes _ _ hw, hs] theorem parse_witness (recipe seed : Nat) (hr : recipe < 256) (hs : seed ≤ maxSeed) : parse (witnessPacket recipe seed) = some (recipe, seed) := by have hseed : (decodePacket (packet seed)).headD 0 = seed := by rw [packet_recovers_history seed hs, trace_head] simp only [parse, witnessPacket, if_pos hr, packet_length, if_neg (by decide : (6 : Nat) ≠ 2), if_pos (rfl : (6 : Nat) = 6), hseed] simp [hs] /-- A recipe is a function of the recipe ID and the recovered seed. -/ def rebuild (recipe : Nat → Nat → α) (bytes : List Nat) : Option α := (parse bytes).map (fun (id, seed) => recipe id seed) theorem rebuild_seed (recipe : Nat → Nat → α) (id seed : Nat) (hi : id < 256) (hs : seed ≤ maxSeed) : rebuild recipe (seedPacket id seed) = some (recipe id seed) := by simp [rebuild, parse_seed id seed hi hs] theorem rebuild_witness (recipe : Nat → Nat → α) (id seed : Nat) (hi : id < 256) (hs : seed ≤ maxSeed) : rebuild recipe (witnessPacket id seed) = some (recipe id seed) := by simp [rebuild, parse_witness id seed hi hs] /-- Exact reconstruction is possible precisely when each packet fiber has one output. -/ theorem reconstructible_iff_constant_on_fibers (observe : X → P) (generate : X → A) : (∃ receive : P → Option A, ∀ x, receive (observe x) = some (generate x)) ↔ ∀ x y, observe x = observe y → generate x = generate y := by constructor · intro h x y hxy obtain ⟨receive, correct⟩ := h have heq := congrArg receive hxy rw [correct x, correct y] at heq exact Option.some.inj heq · intro hf classical let receive (p : P) : Option A := if hp : ∃ x, observe x = p then some (generate (Classical.choose hp)) else none refine ⟨receive, ?_⟩ intro x have hx : ∃ y, observe y = observe x := ⟨x, rfl⟩ change (if h : ∃ y, observe y = observe x then some (generate (Classical.choose h)) else none) = some (generate x) rw [dif_pos hx] exact congrArg some (hf _ x (Classical.choose_spec hx)) /-- An inverse coordinate map can follow exact quotient-residual readout. -/ theorem reconstruct_after_resolution (encode : X → Int) (decode : Int → X) (inverse : ∀ x, decode (encode x) = x) (h : Int) (x : X) : decode (h * (encode x / h) + encode x % h) = x := by rw [Int.ediv_add_emod, inverse] theorem seed_399 : seedPacket 2 399 = [1, 2, 143, 1] := by decide theorem witness_399 : witnessPacket 2 399 = [1, 2, 9, 6, 0, 0, 0, 0] := by decide /-- The signed LEB128 cases used by the WebAssembly recipe for a 15-bit seed. -/ def wasmBytes (seed : Nat) : List Nat := let immediate := if seed < 64 then [seed] else if seed < 8192 then [128 + seed % 128, seed / 128] else [128 + seed % 128, 128 + seed / 128 % 128, seed / 16384] let body := [0x00, 0x41] ++ immediate ++ [0x0b] [0x00, 0x61, 0x73, 0x6d, 0x01, 0x00, 0x00, 0x00, 0x01, 0x05, 0x01, 0x60, 0x00, 0x01, 0x7f, 0x03, 0x02, 0x01, 0x00, 0x07, 0x07, 0x01, 0x03, 0x72, 0x75, 0x6e, 0x00, 0x00, 0x0a, body.length + 2, 0x01, body.length] ++ body def wasmRecipe (id seed : Nat) : List Nat := if id = 10 then wasmBytes seed else [] theorem wasm_round_trip (seed : Nat) (hs : seed ≤ maxSeed) : rebuild wasmRecipe (witnessPacket 10 seed) = some (wasmBytes seed) := by rw [rebuild_witness wasmRecipe 10 seed (by decide) hs] rfl theorem wasm_399 : rebuild wasmRecipe [1, 10, 9, 6, 0, 0, 0, 0] = some [0x00, 0x61, 0x73, 0x6d, 0x01, 0x00, 0x00, 0x00, 0x01, 0x05, 0x01, 0x60, 0x00, 0x01, 0x7f, 0x03, 0x02, 0x01, 0x00, 0x07, 0x07, 0x01, 0x03, 0x72, 0x75, 0x6e, 0x00, 0x00, 0x0a, 0x07, 0x01, 0x05, 0x00, 0x41, 0x8f, 0x03, 0x0b] := by decide #print axioms rebuild_seed #print axioms rebuild_witness #print axioms reconstructible_iff_constant_on_fibers #print axioms reconstruct_after_resolution #print axioms seed_399 #print axioms witness_399 #print axioms wasm_round_trip #print axioms wasm_399 #eval parse (seedPacket 2 399) #eval parse (witnessPacket 2 399) end SeedPacket