Online Supplementary Appendix

Abstract

A line of impossibility results holds that a distributed ledger must either store a global state linear in the number of accounts or impose a near-linear rate of proof updates on its users; the most general, the revocable-proof-system lower bound of Christ and Bonneau, concludes there is "no useful trade-off." We show this impossibility does not bind the validity predicate Bitcoin actually uses—an artifact of one modelling choice, that validity is decided by a holder-maintained witness checked against a single mutating commitment. We define the spend-event validity predicate (SEVP) that a UTXO ledger uses instead, and prove it is not a revocable proof system: it instantiates no holder witnesses, so it lies outside the domain the lower bound quantifies over rather than within either branch of the dichotomy. The same exclusion holds for the related accumulator-update bounds. We are explicit about scope—stateless UTXO constructions that issue holder witnesses (accumulator- and vector-commitment designs) are correctly bound; the claim is that the UTXO model as Bitcoin implements it is not such a construction. This is not hypothetical: public Teranode benchmark evidence demonstrates one-million-transactions-per-second validation in a six-region BSV benchmark, while companion measurements report a 520-million-output active set with no holder-maintained witnesses. We then develop the supporting machinery. The binding resource is active-state maintenance in fast memory, not archival disk, and pruning bounds that state safely with a parameter-free reduction ratio of exactly T_yr/(d·T_block) (263× at retention depth d = 200), never altering the ledger and preserving the forensic record through self-interested retention plus archival nodes. For certification we give a construction and cost analysis for interval non-revocation, combining known authenticated-dictionary primitives so that interval validity is decided by a single point query with no trusted responder. Bounds are closed-form under stated assumptions; the one-million-TPS regime is demonstrated, the tens-of-millions a marked near-term projection.