Building Blocks of the State Machine Approach to Consensus

Summary:

Bitcoin developers are considering the possibility of embedding a Lisp interpreter, like Scheme, into the blockchain protocol to provide validation in a functional scripting language. This approach could be more efficient than the current libconsensus library and allow for deterministic serialization of proof data. The system would require proofs, one per input, that satisfy the conditions associated with each output. A practical implementation could use two merkle-sum trees, one for the inputs and one for the outputs, with witnesses provided separately. The idea of cryptographic single-use seals is also introduced, which can ensure uniqueness and prevent double-spending. Trusted oracles can maintain closed seals and produce signed messages attesting to the fact that a seal was closed. However, this implementation has unbounded storage requirements, so bounded oracles that allocate seals in advance could be implemented.The article delves into various methods of using oracles to prove the validity or non-validity of transactions, messages, and seals in decentralized systems. Seals are explained, including the combination of multiple seals and the problem of atomicity when multiple parties control the seals. The article explores different implementations of oracles, including decentralized blockchains, centralized public logs, and receipt oracles. Validity oracles are discussed as a solution for when transaction histories become impractical to move between parties. Fraud proofs and probabilistic validation techniques are also examined, including the use of random beacons and linearization of transaction history.The scalability of transaction history proofs can be improved by using a random beacon and taking advantage of inflation. PoW blockchains can act as random beacons since it is provably expensive for miners to manipulate the hash digests of blocks they produce. An example where this capability is essential is in the author's transaction history linearization technique. By redefining coin validity to be probabilistic, the growth of history proofs can be linearized. In addition, the validity of a transaction can be defined based on randomly chosen inputs weighted by their values. If the random beacon is truly unpredictable, there is no economic advantage to creating fake inputs, and it is sufficient for validity to only require one input to be proven, giving O(n) scaling for transaction history proofs. Transaction history proof scalability can be further improved by allowing a transaction proof to be considered valid without validating any of the inputs and resetting the size of the transaction history proof. This approach can be a source of inflation, but the maximum rate of inflation can be limited by limiting the probability of this happening. In a system like Bitcoin, where miners are expected to validate, a transaction proof could consist of just a single merkle path showing that a single-use seal was closed in some kind of TXO commitment - probably under 10KB of data. This gives a history proof less than 18.4MB in size, 99% of the time, and less than 9.2MB in size 90% of the time. An interesting outcome of this design is that inflation fraud can be institutionalized, with the entire block reward being replaced by miners rolling the dice, attempting to create valid "fake" transactions. However, such a pure implementation would put a floor on the lowest transaction fee possible, so it is better to allow both transaction fee and subsidy collection at the same time.References for this context include links to GitHub repositories for PayPub and TimeLock, as well as articles on zero-knowledge contingent payments and the Reusable Proofs of Work system.

Updated on: 2023-06-11T05:50:50.941360+00:00