Lemma 3.4 — , are fixed functions of , and -bit messages
ProvedDistVerif.Simulation.lemma_3_4Let be a deterministic B-model algorithm on the network of §3.1, with inputs at and at , and write and for the configurations of the -left and -right sets at the end of round . Let . Then:
- (3.2) There are slots, each either empty or an edge of with , and a function , such that for all inputs
where is the -bit message sent in round along the edge of slot (and a fixed dummy message if slot is empty). 2. (3.1) Symmetrically, there are slots, each empty or an edge with , and a function , such that for all inputs
This is the step of the Simulation Theorem: Bob, who knows , can compute once Alice sends him messages of bits, which she can compute from , and vice versa.
Formalization Note The functions and the slot edges are chosen once, before the inputs, and depend only on , and the network. The paper's wording ("Fix any deterministic algorithm and input strings and … there exist functions") read literally would let depend on , which makes the lemma trivial; its proof constructs input-independent functions and edges, and the proof of Theorem 3.1 needs that, since Bob evaluates without knowing . Empty slots are the paper's padding ("if there are less than such messages, then we add some empty messages"). The node indices need , which is a hypothesis.
import Mathlib import Definitions.Def_DistVerif_Simulation_Network import Definitions.Def_DistVerif_Simulation_Algorithm
namespace DistVerif.Simulation
/-- **Lemma 3.4** (p. 1249). Let `A` be a deterministic B-model algorithm on `G(Γ, d, p)`
(inputs at `s = u^p_0` and `r = u^p_{d^p-1}`) and `0 < t < (d^p - 1)/2`.
* (3.2) There are `d·p` slots `eR`, each either empty or an edge `(w, u)` of the graph with
`w ∈ L_{t-1}`, and a function `gR`, both independent of the inputs, such that for all inputs
`x, y` the configuration `C_{R_t}` equals `gR` applied to `C_{R_{t-1}}` and the `B`-bit
messages sent along the slots' edges in round `t` (an all-`false` message for empty slots).
* (3.1) Symmetrically for `C_{L_t}`, with `d·p` edges leaving `R_{t-1}` and a function `gL`. -/
theorem lemma_3_4 (Γ d p B b : ℕ) (hdp : 0 < d ^ p) (A : DetAlg (Vtx Γ d p) B b)
(t : ℕ) (ht0 : 0 < t) (ht : (t : ℝ) < ((d : ℝ) ^ p - 1) / 2) :
(∃ eL : Fin (d * p) → Option (Vtx Γ d p × Vtx Γ d p),
∃ gL : (↥(L Γ d p (t - 1)) → A.State) → (Fin (d * p) → Msg B) → (↥(L Γ d p t) → A.State),
(∀ i w u, eL i = some (w, u) → w ∈ R Γ d p (t - 1) ∧ (graph Γ d p).Adj w u) ∧
∀ x y : Fin b → Bool,
(fun v : ↥(L Γ d p t) =>
A.exec (graph Γ d p) (sNode Γ d p hdp) (rNode Γ d p hdp) x y t v) =
gL (fun v : ↥(L Γ d p (t - 1)) =>
A.exec (graph Γ d p) (sNode Γ d p hdp) (rNode Γ d p hdp) x y (t - 1) v)
(fun i => match eL i with
| some (w, u) => A.send w u
(A.exec (graph Γ d p) (sNode Γ d p hdp) (rNode Γ d p hdp) x y (t - 1) w)
| none => fun _ => false)) ∧
(∃ eR : Fin (d * p) → Option (Vtx Γ d p × Vtx Γ d p),
∃ gR : (↥(R Γ d p (t - 1)) → A.State) → (Fin (d * p) → Msg B) → (↥(R Γ d p t) → A.State),
(∀ i w u, eR i = some (w, u) → w ∈ L Γ d p (t - 1) ∧ (graph Γ d p).Adj w u) ∧
∀ x y : Fin b → Bool,
(fun v : ↥(R Γ d p t) =>
A.exec (graph Γ d p) (sNode Γ d p hdp) (rNode Γ d p hdp) x y t v) =
gR (fun v : ↥(R Γ d p (t - 1)) =>
A.exec (graph Γ d p) (sNode Γ d p hdp) (rNode Γ d p hdp) x y (t - 1) v)
(fun i => match eR i with
| some (w, u) => A.send w u
(A.exec (graph Γ d p) (sNode Γ d p hdp) (rNode Γ d p hdp) x y (t - 1) w)
| none => fun _ => false)) := by sorry
end DistVerif.Simulation
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.