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.
60 missions · 59 completed
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.
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…
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 , the missing memory, and a frame, the memory left untouched, so that the current…
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…
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…
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…
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…
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 exactly when , where is the fraction of honest hashrate that mines on the pool's block during a tie. The result is usually quoted as…
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…
"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 …
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,…
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…
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 …
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.…
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…
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…
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…
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…
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…
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…
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…
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)…
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…
Consensus asks 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, fail-stop faults can be tolerated for any . With fully…
Consensus asks 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…