Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Formal Verification

60 missions · 59 completed

Missions

Open1Completed59All60
🏆Completed
Mathematical LogicTheoretical Computer Science·Captain: Rizwan G Mir

The Cook-Levin Theorem: NP-Completeness of Boolean Satisfiability in Lean 4Research Paper

The Cook-Levin theorem states that CNF SAT is NP-complete. This mission formalizes the theorem over a multi-tape Turing machine model in Lean 4.

175 thms9 active usersReviewed
🏆Completed
Mathematical LogicTheoretical Computer ScienceTopology·Captain: Shuze Chen

Distributed LTL Synthesis under Arbitrary Message AdversariesResearch Paper

Reactive synthesis asks for a program whose outputs satisfy a logical specification against every input stream. For a single process and specifications in linear temporal logic (LTL) it is decidable (Pnueli–Rosner 1989); for several processes with partial information it is undecidable in general (Pnueli–Rosner 1990), and decidable cases rely on a hierarchy…

31 thms5 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: mikedeng1

Compositional Shape Analysis by Means of Bi-Abduction 2: With Precise Preconditions and Best Anti-Frames, the Canonical Precondition of an Action Sequence Is Its FootprintResearch Paper

Automatic program analyses for heap-manipulating code have to infer, for each procedure, a precondition describing the memory the procedure needs. Calcagno, Distefano, O'Hearn and Yang (J. ACM 2011) do this with bi-abduction: at a call site the analysis asks for an anti-frame MMM, the missing memory, and a frame, the memory left untouched, so that the current…

9 thms5 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Büchi Determinization with Optimal States and Square Root Index ImprovementResearch Paper

Automata on infinite words describe behavior that continues indefinitely. In formal verification, a system execution is such a word, and an acceptance condition expresses a property of its long-term behavior. Converting a nondeterministic automaton to a deterministic one can make subsequent operations possible, but the conversion has two costs: the number…

31 thms3 active usersReviewed
🏆Completed
Mathematical LogicTheoretical Computer Science·Captain: mikedeng1

Compositional Shape Analysis by Means of Bi-Abduction 1: The Best Abductive Solution for Points-To Symbolic Heaps Is a Computable Disjunction of Symbolic HeapsResearch Paper

Automatic verification of programs that manipulate pointers needs procedure specifications: preconditions saying which part of the heap a procedure touches and postconditions saying what it leaves behind. Writing them by hand does not scale to millions of lines of code. Calcagno, Distefano, O'Hearn and Yang (J. ACM 58(6), 2011) infer them compositionally…

13 thms3 active usersReviewed
🏆Completed
Mathematical LogicTheoretical Computer Science·Captain: mikedeng1

Tree Equivalence of Higher-Order Recursion Schemes Is UndecidableResearch Paper

A higher-order recursion scheme (HORS) is a finite, simply typed recursive program whose terminal symbols act as tree constructors. Unfolding it from its start symbol generates a possibly infinite ordered, labelled tree. Schemes are a standard model of higher-order functional programs: Ong proved that monadic second-order properties of the generated tree…

30 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: pitimespi

Bitcoin Mainnet: Correctness of the Consensus RulesTextbook

Bitcoin nodes must agree on which blocks are valid and on the spendable outputs that a valid block creates. A discrepancy in an arithmetic boundary, script operation, or historical exception can change that decision. This mission targets all Bitcoin mainnet consensus rules, including their historical applicability, through a source-linked Lean 4…

161 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: pitimespi

Bitcoin: the Eyal-Sirer selfish-mining thresholdTextbook

Eyal and Sirer (2014) showed that a mining pool can earn more than its share of the hashrate by withholding blocks: the pool's revenue share under the selfish strategy exceeds α\alphaα exactly when α>(1−γ)/(3−2γ)\alpha > (1-\gamma)/(3-2\gamma)α>(1−γ)/(3−2γ), where γ\gammaγ is the fraction of honest hashrate that mines on the pool's block during a tie. The result is usually quoted as…

18 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: pitimespi

Bitcoin: no free relay and the pinning cost under Core's replace-by-fee rulesTextbook

Replace-by-fee (BIP125) is defended with two informal properties: "no free relay" (a transaction cannot be replaced over and over without each replacement paying for the bandwidth of the previous one) and the "pinning" observation (a counterparty who attaches high-fee descendants to a transaction can make it arbitrarily expensive to replace). Both are…

16 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: pitimespi

The Difficulty Moves by at Most a Factor of Four per Period: Raw, Encoded, over Many Periods, and on a ChainTextbook

"Difficulty adjusts by at most a factor of four per period" is the rule everyone states about the retarget, and the timewarp attack is the observation that a miner who controls timestamps can push the adjustment to that limit every period. The proof-of-work mission transcribed CalculateNextWorkRequired and proved its output satisfies Core's own …

12 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: pitimespi

BIP30 and BIP34: Where the Scan Runs Outputs Are Fresh, and Post-BIP34 Coinbases Are Pairwise DistinctTextbook

ConnectBlock guards against a block creating coins at an outpoint that already holds some (BIP30) by scanning the UTXO set — except when the BIP34 activation block is an ancestor, until height 1,983,702. The justification, a comment in Core, is that BIP34 forces every coinbase to begin with a push of its height, so no two coinbases are the same transaction,…

15 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: pitimespi

Reorganization Safety: Disconnecting a Chain and Connecting Another Reaches the Directly Validated StateTextbook

A Bitcoin node does not keep every chain it has seen; it keeps one UTXO set, and when a longer branch arrives it reorganizes: it disconnects blocks from its tip, restoring the coins each block spent from the undo data it wrote when it connected them, and then connects the blocks of the new branch. The claim a node relies on is that the state it ends up with…

10 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: pitimespi

Bitcoin Block Validation Composed, Revision 2: C(S,B,t)C(S,B,t)C(S,B,t) Accepts iff V(S,B,t)V(S,B,t)V(S,B,t), ApplySpec, DisconnectBlockTextbook

This proposal supersedes the published mission Bitcoin Block Validation Composed (definition BitcoinBlock, 19 theorems). A line-by-line source review of that definition against the pinned revision found one transcription error: the transaction sigop cost added, for every non-P2SH spent output, the accurate sigop count of that output's script, whereas …

20 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: pitimespi

Bitcoin Block Validation Composed: C(S,B,t) Accepts iff V(S,B,t), ApplySpec, and DisconnectBlockTextbook

Every component mission transcribed one layer of Bitcoin Core's validation: the subsidy schedule, compact targets and retargeting, the merkle root, the ledger accounting, median time past and the header rules, the activation heights and flag exceptions, serialization and hashing, the Script interpreter, the signature layer, the SegWit and Taproot dispatch.…

20 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: pitimespi

Bitcoin Taproot: Key Path, Script Path Commitment, and Tapscript RulesTextbook

Since block 709,632 (BIP341 activation, November 2021) every version-1 witness program with a 32-byte payload is a Taproot output. Spending it means either a key-path spend — one Schnorr signature by the output key — or a script-path spend that reveals a leaf script together with a control block proving that the leaf is committed to by the output key, and…

16 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: pitimespi

Bitcoin VerifyScript: P2SH, SegWit v0 Programs, and Witness DispatchTextbook

EvalScript decides what a script does; VerifyScript decides which scripts run, on what stack, under which signature version, and what counts as success. It is where pay-to-script-hash (BIP16), segregated witness (BIP141) and the hand-off to Taproot live: the output script is evaluated first, then — if it is a witness program — the witness is interpreted, or…

12 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: pitimespi

Bitcoin Signatures: Strict DER, Signature Hashes, secp256k1 ECDSA/Schnorr, and the Concrete P2PKH TheoremTextbook

A Bitcoin transaction is authorized by signatures, and whether a signature counts is decided by a chain of exact rules: the byte layout the signature must have (strict DER since BIP66), which parts of the transaction the signature commits to (the signature hash, in its legacy and BIP143 forms, with the historical SIGHASH_SINGLE bug), how the public key is…

16 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: pitimespi

Bitcoin Serialization and Hashing: CompactSize, Transactions, Blocks, SHA-256d, and the Genesis BlockTextbook

Every commitment in Bitcoin — a transaction id, a merkle root, a block hash, the proof-of-work target test — is a hash of a byte string, and the byte string is produced by a serializer that every node must implement identically. A node that encoded a CompactSize one byte longer, or read a witness flag differently, would compute different ids for the same…

18 thms2 active usersReviewed
🏆Completed
Theoretical Computer ScienceTheory of Computation·Captain: mikedeng1

Multiparty Asynchronous Session Types 1: A Global Type's One-Time Unfolding Is Linear iff Its n-th Unfolding Is Linear, for Every n ≥ 1Research Paper

Multiparty communication protocols involve several participants who send messages over shared session channels. An implementation may send a later message before an earlier one has been received, so a written sequence of interactions does not by itself prevent a receiver from taking the wrong message. Honda, Yoshida, and Carbone use global types to specify…

4 thms2 active usersReviewed
🏆Completed
Mathematical LogicTheory of Computation·Captain: mikedeng1

Monitoring Metric First-Order Temporal Properties: The Monitor M_Φ Outputs Exactly the Violations (¬Φ)^(D̄,τ̄,i) of a Bounded MFOTL Formula Φ, as Regular Sets, at Every Time Point iResearch Paper

Runtime monitoring checks a running system against a specification by inspecting its trace of events as it is produced. Policies on data, such as "every published report was approved within the last 10 days" or "each value stored in in reaches out within 5 time units", quantify over data values and constrain the time between events. Metric first-order…

14 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: mikedeng1

Reaching Agreement in the Presence of Faults 3: With Authenticated Messages, the S_pq Procedure Assures Interactive Consistency for m Faults for Every n ≥ mResearch Paper

Processors in a distributed system may hold separate readings of a sensor, clock, or diagnostic result while some processors give misleading reports. The aim of interactive consistency is for every functioning processor to compute the same vector of reported values and to put each functioning processor's actual private value in its corresponding position. A…

5 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: mikedeng1

Reaching Agreement in the Presence of Faults 2: If |V| ≥ 2 and 3 ≤ n ≤ 3m, No Family {F_p} Assures Interactive Consistency for m Faults, However Many Rounds Are UsedResearch Paper

A fault-tolerant system built from several processors must let its working processors act on the same data, even though some processors may have failed in ways nobody can predict: a failed processor may stop relaying information, relay something it invented, or tell different processors different things. Pease, Shostak and Lamport (J. ACM 27 (1980) 228–234)…

6 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: mikedeng1

Reaching Agreement in the Presence of Faults 1: With n ≥ 3m + 1 Processors, the Recursive Majority Procedure on (m + 1)-Level Scenarios Assures Interactive Consistency for m FaultsResearch Paper

A fault-tolerant system often replicates a computation on several processors and needs the nonfaulty ones to act on the same data, even though some processors may fail in arbitrary ways: send wrong values, send different values to different recipients, or lie about what they were told. Pease, Shostak and Lamport posed the question in 1980, motivated by the…

7 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: mikedeng1

Consensus in the Presence of Partial Synchrony II: With Synchronous Processors, Partially Synchronous Communication and t Fail-Stop Faults, No Consensus Protocol Exists When 2 ≤ N ≤ 2tResearch Paper

Consensus asks NNN processors, each holding an initial value, to agree on one value despite some of them failing. It underlies replicated databases, atomic commit and state-machine replication. Its solvability depends on the timing assumptions. With fully synchronous processors and communication, ttt fail-stop faults can be tolerated for any t<Nt < Nt<N. With fully…

5 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: mikedeng1

Consensus in the Presence of Partial Synchrony I: For N ≥ 2t + 1, Algorithm 1 Achieves Consistency, Strong Unanimity and Termination in the Basic Round Model with Fail-Stop or Omission FaultsResearch Paper

Consensus asks NNN processors, each starting with a value, to agree on one value although some of them may be faulty. It underlies replicated databases, atomic commitment and state-machine replication. Two classical models bracket the problem. In a fully synchronous system, with known bounds on message delay and processor speed, consensus is solvable for many…

6 thms2 active usersReviewed
PreviousPage 1 of 3Next

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