Merkleize All The Things

Summary:

Salvatore Ingala has proposed a new approach, called MATT (Merkleize All The Things), to enable general smart contracts in Bitcoin. This approach uses covenants to add restrictions on the outputs of the transaction spending the UTXO. The covenant enables introspection limited to a single hash attached to the UTXO and input/output amounts, pre-commitment to every possible future script, and few simple opcodes operating with the covenant data. Salvatore argues that such a simple covenant construction is enough to extend the power of Bitcoin's layer 1 to become a universal settlement layer for arbitrary computation.The smart contract is created by creating a UTXO encumbered with a covenant. Each node of the finite state machine (FSM) has an associated state and a set of transition rules that define who can use the rule, what is the next active node in the FSM, and what is the state of the next active node. The covenant allows the enforcement of such state transitions by only allowing outputs that commit to a valid next node and corresponding state in the FSM. Arbitrary computation is possible over the committed state as long as relatively simple arithmetic or logical operations are available over the state.To build contracts that allow conditions of the type "f(x) = y", without forcing layer 1 to perform any expensive computation, Salvatore proposes the challenge protocol. Alice posts the statement "f(x) = y," and after a challenge period, if no challenge occurs, Alice is free to continue and unlock the funds; the statement is true. At any time before the challenge period expires, Bob can start a challenge: "actually, f(x) = z". The article discusses the challenge resolution protocol for smart contracts in the UTXO model using Merkle trees. The bisection protocol for arbitrary computation is explained, which involves decomposing the computation into simple elementary steps and representing them as triples. The challenge starts at the root of the Merkle tree and proceeds in steps to find a leaf where Alice and Bob disagree. The arbitration mechanism knows the function but not the correct computation trace hash. With the right economic incentives, playing a losing game always loses money compared to cooperating. The bisection protocol operates under the honest miner majority assumption.The article also suggests covenant opcodes that are taproot-friendly and can be added in a soft fork to the existing SegWitv1 Script. It proposes embedding covenant data in P2TR outputs and replacing the internal pubkey with a key obtained by tweaking it with the covenant data. Changes to the Script and potential additional opcodes are discussed. The article also mentions the availability of additional introspection opcodes in Blockstream Liquid that could allow MATT covenants.The article discusses the use of MAST (Merkelized Abstract Syntax Trees) and covenants to improve Bitcoin's smart contract capabilities. The covenant proposal allows for fully recursive constructions, providing an arbitrary depth of the covenant execution tree. However, if recursivity is not desired, a counter could be attached to the covenant to limit the depth. The article explores potential use cases of the covenant technique, including state channels, CoinPool, ZK-proofs in L2 protocols, and optimistic rollups. The possible changes required for Validity Rollups on Bitcoin's layer 1 are also discussed. The author acknowledges Antoine Poinsot and others for their contributions to the proposal. Finally, the article provides references for further reading on related topics.

Updated on: 2023-06-16T03:01:33.994815+00:00