Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Honest histories preserve occupancy and successful row equations

Proved
GBFPlus.OccupancyDisclosure.history_invariants

by queelius · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

cryptographygbfplusoccupancy-disclosure

For every valid configuration and every finite honest insertion history starting from the empty array, the final occupied set is exactly the union of the successful rows' position sets. Every successful row still XORs to its original target in the final snapshot, even when later insertions overlap it. Also, for any snapshot, an admissible failed attempt leaves it unchanged. Failed attempts do not contribute to the successful-row list or its length. These invariants follow from the residual update and reuse of occupied words; they are not assumptions in the definition of an honest history.

Preamble
import Mathlib
import Definitions.Def_GBFPlus_OccupancyDisclosure
Formal statement
namespace GBFPlus.OccupancyDisclosure

theorem history_invariants (C : Config) (es : List (Attempt C))
    (h : Honest (empty C) es) :
    occupied (finalSnapshot es) = supportUnion (successful es) ∧
    (∀ r ∈ successful es, rowXor (finalSnapshot es) r = r.target) ∧
    (∀ (A : Snapshot C) (e : Attempt C), admissible A e →
      e.pivot = none → step A e = A) := by sorry

end GBFPlus.OccupancyDisclosure
Source
Alexander Richard Towell, Adjacent-Domain Disclosure from Public Occupancy in GBFPlus, archival preprint v1.0.0, 20 October 2026, Section 2, DOI 10.5281/zenodo.23497466. Original analyzed protocol: Qin, Zhou, Dai, Sun and Qiang, Entropy 28 (2026), 947, DOI 10.3390/e28090947, Algorithm 4 and Sections 5.1–5.2. The source note is CC-BY-4.0; this new Lean formalization retains attribution and is prepared for the platform public-contribution terms. Section 2, construction paragraph immediately after Eq.(1), including its stated consequences.
Read-back

What the Lean code literally says, in plain math · OpenAI Codex (exact model identifier unavailable)

For every choice of natural numbers m,k,a,bm,k,a,bm,k,a,b satisfying 1≤k≤m1\le k\le m1≤k≤m, 1≤a1\le a1≤a, and 1≤b1\le b1≤b, put I={0,…,m−1}I=\{0,\ldots,m-1\}I={0,…,m−1} and W=(F2)a×(F2)bW=(\mathbb F_2)^a\times(\mathbb F_2)^bW=(F2​)a×(F2​)b, where F2\mathbb F_2F2​ is the two-element field and addition in WWW is componentwise addition modulo 222. A snapshot is a function A:I→W⊔{⊥}A:I\to W\sqcup\{\bot\}A:I→W⊔{⊥}, where ⊥\bot⊥ means that the cell is empty. A row rrr consists of a subset Sr⊆IS_r\subseteq ISr​⊆I with exactly kkk elements, an arbitrary vector ur∈(F2)au_r\in(\mathbb F_2)^aur​∈(F2​)a, and an arbitrary vector vr∈(F2)bv_r\in(\mathbb F_2)^bvr​∈(F2​)b; write τr=(ur,vr)\tau_r=(u_r,v_r)τr​=(ur​,vr​). An attempt e=(r,p,f)e=(r,p,f)e=(r,p,f) consists of such a row, either a cell p∈Ip\in Ip∈I or no pivot p=⊥p=\botp=⊥, and an arbitrary function f:I→Wf:I\to Wf:I→W. Define FA,f(i)F_{A,f}(i)FA,f​(i) to be the stored word A(i)A(i)A(i) when that cell is occupied, and f(i)f(i)f(i) otherwise. Define the update T(A,e)T(A,e)T(A,e) as follows: if p=⊥p=\botp=⊥, it is exactly AAA; if p∈Ip\in Ip∈I, every cell outside SrS_rSr​ retains its previous value, every cell i∈Sri\in S_ri∈Sr​ with i≠pi\ne pi=p is occupied with word FA,f(i)F_{A,f}(i)FA,f​(i), and, if p∈Srp\in S_rp∈Sr​, cell ppp is occupied with word τr+∑j∈Sr∖{p}FA,f(j)\tau_r+\sum_{j\in S_r\setminus\{p\}}F_{A,f}(j)τr​+∑j∈Sr​∖{p}​FA,f​(j). Call the attempt admissible at AAA when, in the no-pivot case, every cell of SrS_rSr​ is already occupied, and, in the case p∈Ip\in Ip∈I, the pivot lies in SrS_rSr​ and is empty in AAA. For every finite list of attempts e1,…,ene_1,\ldots,e_ne1​,…,en​, including n=0n=0n=0, let A0(i)=⊥A_0(i)=\botA0​(i)=⊥ for every i∈Ii\in Ii∈I, and recursively let At=T(At−1,et)A_t=T(A_{t-1},e_t)At​=T(At−1​,et​) for 1≤t≤n1\le t\le n1≤t≤n. Suppose that each ete_tet​ is admissible at At−1A_{t-1}At−1​. Let RRR be the list of rows from precisely those attempts whose pivot is a cell, retaining their order and any repetitions, and let PA(i)P_A(i)PA​(i) equal the stored word when A(i)≠⊥A(i)\ne\botA(i)=⊥ and the zero word of WWW otherwise. Then the following three assertions hold jointly: the set {i∈I:An(i)≠⊥}\{i\in I:A_n(i)\ne\bot\}{i∈I:An​(i)=⊥} is exactly ⋃r∈RSr\bigcup_{r\in R}S_r⋃r∈R​Sr​, with the union defined to be empty when RRR is empty; for every row rrr occurring in RRR, ∑i∈SrPAn(i)=τr\sum_{i\in S_r}P_{A_n}(i)=\tau_r∑i∈Sr​​PAn​​(i)=τr​; and for every snapshot B:I→W⊔{⊥}B:I\to W\sqcup\{\bot\}B:I→W⊔{⊥} and every attempt e=(r,p,f)e=(r,p,f)e=(r,p,f) with these same parameters, admissibility at BBB together with p=⊥p=\botp=⊥ implies T(B,e)=BT(B,e)=BT(B,e)=B. This last quantification ranges over all snapshots and attempts, not only those in the given history, and in its no-pivot case admissibility requires that all cells in SrS_rSr​ be occupied. All sums are finite sums in WWW, so an empty sum is the zero word; in particular, when k=1k=1k=1, the sum used to fill an admissible pivot is empty. The parameter conditions exclude zero cells, zero shares, and zero lengths for either vector component. The empty history satisfies the hypothesis, has empty occupied set and empty RRR, and makes the assertion about rows in RRR vacuous, while retaining the universally quantified update assertion. Because k≥1k\ge1k≥1, an admissible first attempt in a nonempty history cannot have no pivot. There are no assumptions of disjoint row supports, randomness of the functions fff, or additional relations among the row vectors.

Human review
  • Endorsed by Shuze Chen · Oct 23, 2026

    Confirmed by the moderator at approval.

  • Endorsed by queelius · Oct 23, 2026

    Confirmed by the mission captain (proposal self-audit).

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me