Building Blocks of the State Machine Approach to Consensus

Summary:

The email conversation starts with a question regarding the process of transaction linearization, followed by an explanation of how it is done. The blocks still need to contain a list of full TX Input and Tx Outputs. In another email, a suggestion was made to embed a lisp interpreter such as Scheme in Bitcoin's design, which can be better than the libconsensus library. The email also talks about the benefits of using a functional scripting language for validation. It then discusses the idea of "seals" to solve transaction hash collisions and the issue of continually growing resource consumption.In a separate email thread, Peter Todd wrote a detailed write-up outlining the building blocks of the state-machine approach to so-called "smart contract" systems, extending Bitcoin's own design. The email discusses the need for deterministic code/expressions, proofs, pruning, transactions, proof distribution, uniqueness, and single-use seals. It also talks about the implementation of single-use seals on transactional blockchains and unbounded oracles. Overall, the email provides a comprehensive perspective on the development of Bitcoin and its potential for smart contract systems.The article discusses the concept of oracles, which are trusted entities that provide information to a smart contract. The article talks about how oracles can maintain a set of closed seals and produce signed messages that attest to the fact that a seal was closed. The closed seal set can be published for transparency/auditing purposes. The article also discusses bounded oracles, where users of the oracle allocate seals in advance, analogous to the UTXO set in Bitcoin.Multiple seals can be combined into one by having the open seal commit to a set of sub-seals, and then closing the seal over a second set of closed seal proofs. The article also talks about atomicity and how two-phase timeouts can help resolve the problem of multiple parties controlling the seals. The article then goes on to discuss proof-of-publication and proof-of-non-publication, where a message is provably published publicly in the blockchain as a condition of collecting a payment.Validity oracles can solve the problem of transaction histories becoming impractical to move from one party to another. A particularly generic validity oracle can be created using deterministic expression systems. Fraud proofs can easily generate "fraud proofs," showing that claimed states/proof in the system are actually invalid.The article discusses various techniques to improve the scalability and security of blockchain transactions. One approach is to use deterministic expressions evaluators, which can automatically keep track of required data for a proof and prune all other data when serializing the proof. However, this raises the issue of how to guarantee the ability to prove fraud in the first place. A possible solution is validity challenges, which involve marking potentially fraudulent data and requiring participants to provide marked data to prove the validity of a transaction.Probabilistic validation techniques, such as the Fiat-Shamir transform, can also be used to prove that the percentage of undetected fraud within the system is less than a certain amount with a specified probability. The article also suggests using random beacons and transaction history linearization to reduce the size of probabilistic proofs. For example, by defining coin validity to be probabilistic, it is sufficient for the validity of a transaction to only require one input to be proven.Additionally, allowing occasional transaction proofs without validating any inputs can further improve scalability, provided the probability of this happening can be limited. This technique institutionalizes inflation fraud, where miners roll the dice to create valid "fake" transactions. However, it also puts a floor on the lowest transaction fee possible, making it better to allow both transaction fee and subsidy collection at the same time. The article concludes with several references for further reading.

Updated on: 2023-06-11T05:49:20.692135+00:00