Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Honest-sent event costs and worst-case expected combined communication

Definition
QuantumBA_PackedShares_Supplement_Communication

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

byzantine-agreementcommunication-complexityp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information

Fix a qubit protocol PPP, input vector xxx, adaptive adversary AAA, corruption budget ttt and trajectory ω\omegaω. For every round rrr, channel kind and staged-packet index, TTT specifies a sending boundary between staging and delivery. Only packets whose sender is honest at that boundary are charged. CTC_TCT​ counts the actual classical message bits and quantum-header bits, and QTQ_TQT​ counts qubits. Every classical or quantum channel use costs at least one unit even if empty; each recipient is a separate transmission. Include setup and replies to faulty recipients, in rounds through the last correct halt.

CT=∑rCT,r,QT=∑rQT,r,KT(P,t)=sup⁡xsup⁡AEx,A[CT+QT]∈[0,∞].C_T=\sum_r C_{T,r},\qquad Q_T=\sum_r Q_{T,r},\qquad K_T(P,t)=\sup_x\sup_A\mathbb E_{x,A}[C_T+Q_T]\in[0,\infty].CT​=r∑​CT,r​,QT​=r∑​QT,r​,KT​(P,t)=xsup​Asup​Ex,A​[CT​+QT​]∈[0,∞].

All sums, expectations and suprema are nonnegative extended-real operations. The supremum is outside expectation and the two communication kinds are added before taking it. In particular, an infinite expectation or unbounded collection of expectations gives infinity.

The constant last-boundary timing defines the conservative auxiliary count: a sender is charged only if honest through delivery. Permanent corruption makes this count no larger than the count for any earlier sending placement. This order relation is a proof obligation, not a field of the interface. In Section 7 every counted reference sender is correct, so every reference transmission remains counted. The imported staging counters are unchanged.

Formalization Note There are n+2n+2n+2 possible sending boundaries: immediately after honest staging and after each of the n+1n+1n+1 rushing adversarial steps. TTT is accounting data, may depend on the full trajectory, and supplies no information to protocol execution. A quantum packet is a list of qubits, with one classical header per listed register.

Definition code
import Definitions.Def_QuantumBA_PackedShares_Supplement_Physical

set_option autoImplicit false

open scoped ENNReal

namespace QuantumBA.PackedShares.Supplement

variable {n : ℕ} (P : Protocol n Qubit)

/-- Placement of the sending event of each prescribed transmission between staging and
delivery. Slots 0,...,n+1 are the boundaries after staging and after each of the n+1 rushing
adversarial steps. Dependence on the full execution is allowed for accounting only; this
does not give an honest algorithm any extra information. `false` selects classical packets,
`true` quantum packets. The last argument is the packet's index in the staged list. -/
abbrev SendTiming := (Fin n → Bool) → Adversary n Qubit P.M P.Hd →
  (ℕ → Outcome Qubit) → ℕ → Bool → ℕ → Fin (n + 2)

/-- The smallest counting convention: sender must stay honest through delivery. This is
an accounting auxiliary, not a replacement for the source's honest-sent convention. -/
def deliveryTiming : SendTiming P := fun _ _ _ _ _ _ => ⟨n + 1, by omega⟩

/-- Boundary after the honest computation and staging step of round r. -/
def stagedBoundary (n r : ℕ) : ℕ := r * stepsPerRound n + n + 2

/-- The sending boundary, before the corresponding delivery, with corruption tested here. -/
def sendBoundary (T : SendTiming P) (x : Fin n → Bool) (A : Adversary n Qubit P.M P.Hd)
    (ω : ℕ → Outcome Qubit) (r : ℕ) (quantum : Bool) (i : ℕ) : ℕ :=
  stagedBoundary n r + (T x A ω r quantum i).val

/-- Source C and Q in one round: classical packets have their actual bit lengths, including
the one-unit minimum; quantum packets have their qubit lengths, including the one-unit
minimum, and their headers are charged to C. Every recipient is a separate list entry.
Only events whose sender is still honest at the sending boundary are charged. -/
noncomputable def roundSource (T : SendTiming P) (x : Fin n → Bool)
    (A : Adversary n Qubit P.M P.Hd) (t : ℕ) (ω : ℕ → Outcome Qubit) (r : ℕ) : ℕ × ℕ := by
  classical
  let c := cfgAt P x A t ω (stagedBoundary n r)
  let cs := c.stagedC.mapIdx (fun i m =>
    if m.1 ∉ (cfgAt P x A t ω (sendBoundary P T x A ω r false i)).bad
    then chargeC P [(m.2.1, m.2.2)] [] else 0)
  let qcs := c.stagedQ.mapIdx (fun i m =>
    if m.1 ∉ (cfgAt P x A t ω (sendBoundary P T x A ω r true i)).bad
    then chargeC P [] [(m.2.1, m.2.2)] else 0)
  let qs := c.stagedQ.mapIdx (fun i m =>
    if m.1 ∉ (cfgAt P x A t ω (sendBoundary P T x A ω r true i)).bad
    then chargeQ P [(m.2.1, m.2.2)] else 0)
  exact (cs.sum + qcs.sum, qs.sum)

/-- Total honest-sent classical bits through the last correct halt, allowing infinity. -/
noncomputable def sourceC (T : SendTiming P) (x : Fin n → Bool)
    (A : Adversary n Qubit P.M P.Hd) (t : ℕ) (ω : ℕ → Outcome Qubit) : ℝ≥0∞ :=
  ∑' r : ℕ, if (r : ℕ∞) < roundsR P x A t ω then
    ((roundSource P T x A t ω r).1 : ℝ≥0∞) else 0

/-- Total honest-sent qubits through the last correct halt, allowing infinity. -/
noncomputable def sourceQ (T : SendTiming P) (x : Fin n → Bool)
    (A : Adversary n Qubit P.M P.Hd) (t : ℕ) (ω : ℕ → Outcome Qubit) : ℝ≥0∞ :=
  ∑' r : ℕ, if (r : ℕ∞) < roundsR P x A t ω then
    ((roundSource P T x A t ω r).2 : ℝ≥0∞) else 0

/-- The supremum is outside the expectation of the combined source costs. Unbounded
expectations and unbounded worst-case cost retain value infinity. -/
noncomputable def worstCommunication (t : ℕ) (T : SendTiming P) : ℝ≥0∞ :=
  ⨆ (x : Fin n → Bool) (A : Adversary n Qubit P.M P.Hd),
    expect P x A t (fun ω => sourceC P T x A t ω + sourceQ P T x A t ω)

end QuantumBA.PackedShares.Supplement
Source
Jan Olkowski, Fast Quantum Byzantine Agreement with Nearly Linear Quantum Communication, STOC 2027 submission #558 (October 2026), p. 2, Section 1.1 and Theorem 2; pp. 34–35, Section 7 (PDF 3, 35–36)

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