Btc-verified: formalizing the Bitcoin protocol

Formal Verification represents a significant advance in software development, offering more reliable assurances compared to conventional testing or discussions. This methodology is particularly useful in environments like Bitcoin development, where making precise, verifiable statements about the protocol's operation is crucial. The project hosted on GitHub leverages Lean4, an Interactive Theorem Prover (ITP), which benefits from its growing body of mathematical knowledge housed in the "mathlib" library. This choice enables rigorous inquiries into the protocol without needing to rebuild foundational mathematical principles.

The primary aim of this initiative is to resolve factual disputes that arise during design discussions of Bitcoin by providing formal, verifiable proof of specific claims. For instance, the Bitcoin Improvement Proposal (BIP) 340 claims regarding Schnorr signatures are explored and verified within this framework. These include assertions of provable security, non-malleability, and linearity, each backed by solid evidence and mathematical formulations that allow these properties to be formally verified and reused in future arguments.

An interesting early outcome of this verification process pertains to the Merkle Tree and Root construction used in Bitcoin blocks. Typically, this process has been optimized for performance with little regard for formal correctness, which can obscure deeper understanding. The project endeavors to bridge this gap by defining a notion of Canonicality and proving algorithmic equivalences that uphold the integrity of the protocol while aligning closely with its practical implementation. This approach not only clarifies the functionality but also reinforces the compositional understanding of Bitcoin’s operational integrity.

However, it is critical to acknowledge the limitations of this project. While providing valuable insights, the verification work does not extend to guaranteeing the behavior of the entire Bitcoin Core as discrepancies can still exist between the model used in btc-verified and the actual implementations like Bitcoin Core or alternatives such as btcd. This project does not seek to specify how Bitcoin should operate but rather focuses on documenting and verifying what is provably correct about the existing system.

In essence, this project stands out as a sophisticated tool for enhancing understanding and resolving technical disputes through formal verification, contributing to a more robust architectural comprehension of Bitcoin’s protocol. As it matures, the potential for generating formally verified common infrastructure could significantly impact broader adoption and trust in blockchain technologies.