SuperAsset Contracts: A Scalable Layer 1 Account and Token Contract Design Using The Bitcoin UTXO Model

A Breakthrough design is presented that enables arbitrary state storage and computation in a Bitcoin UTXO by leveraging a technique known as stateless execution. This is a general purpose design for emulating accounts on a UTXO blockchain and creating scalable state storage that enables comparable functionality to other account-based blockchains such as Ethereum.

Copyright 2021. Matter Web Services Inc., Attila Aros
Attila Aros — Chief Technology Officer, Matter Web Services Inc.

Document version 1.0.0

Abstract

This paper introduces a general design to emulate Contract Accounts in account-based blockchain by using the Bitcoin UTXO model. This approach greatly simplifies the design of Fungible Tokens (ie: “colored coins”) on Bitcoin. We present a breakthrough design that enables arbitrary state storage and computation in a Bitcoin UTXO by leveraging a technique known as stateless execution.

This technique makes it easy to implement a highly scalable general purpose data store and contract account capable of scaling to trillions of state elements while providing efficient O(logN) state proofs. We present a hypothetical layer 1 fungible token contract design that can handle arbitrary precision and provide rapid global and user account balance enumeration in O(1) and O(logN) respectively.

Note: Throughout this document “Bitcoin” refers to the original protocol “Bitcoin (BSV)”.

Problem Statement

The Bitcoin UTXO processing model is secure, efficient and parallelizable, however it comes at a cost: there is no notion of coin or account identities. Each UTXO is globally unique and once spent it can never be re-used, the successor UTXOs have their own identities corresponding to the newly created outputs identified by their outpoint (transaction id and index).

Although the UTXO model lends itself to better privacy than account-based blockchains, it is practically infeasible to implement a fungible token solution across many UTXOs as data or “coin carriers”. The reason it is infeasible is that each UTXO takes on a new identity and linking “back to genesis” requires an exponential amount of storage and space to be able to assure an independent verifier that the coins are not forged or inauthentic.

An earlier Fungible Token solution was introduced by the author: SuperAsset (See ‘colored coins’). However, the key limitation of that token solution is that it requires an indexer to track the “global state” across potentially millions or more UTXOs. Another key limitation is that it is impossible for an unlocking script to ascertain (in polynomial space and time) the authenticity (or lineage) of any particular other UTXO that the coins are being merged with. The result is that an attacker could spoof a chain of spends and convince someone to accept these “fake coins” (ie: coins that have no chain of spends that tracks back to the genesis minting event) and thereby destroying legitable coins of the victim.

The naive use of the UTXO model to implement ‘colored coins’ also makes it extremely rigid to do anything but transfer coins for payment and makes it very difficult to perform atomic swaps with other token types (other “colors”) due to the same problem of being unable to efficiently verify authenticity. There is no way to “account” for the types of coins and the trades amongst them.

UTXO blockchains enforce double-spending of outpoints only: there is no concept of an ‘account’ or ‘contract identity’ and therefore unlocking scripts cannot rely on *only* the spending of outpoints to enforce the rules and security of the contract operations.

Solution Requirements

The solution should be a general purpose Contract Account and enable Fungible-Token (FT) Contracts with similar properties to the “ERC20” or “ERC721” Ethereum contracts. The design of the Contract Account should work equally well for fungible assets (those in which the balances of accounts are fungible) and also for non-fungible assets.

What is needed is an abstraction on top of the UTXO processing model to emulate accounts. In particular we want to emulate Contract Accounts and also the User Accounts asset holders within Contract Accounts.

We need a solution to practically simulate the concept of Contract and User Accounts in blockchains such as Ethereum, then we can achieve a higher degree of interactivity and sophistication of the types of programs that can execute in the Bitcoin UTXO model.

1. Unique Contract Identity

Each contract should have a globally unique Contract ID. At any given time it should be possible to trace the entire history of a contract through a chain of spends to arrive at the latest UTXO.

2. Validated in Bitcoin Script by Miners; Zero Consensus Changes

No changes are required to the Bitcoin (BSV) protocol and zero consensus changes. Miners do not need to run special software nodes or do anything beyind what they are already doing today, with the node software they have today.

3. No “Back to Genesis” Overhead

There is no need for verifiers, wallets, and users to “track back” the coins they received to the genesis event to verify that they are authentic. It should be impossible to receive fraudulent requests in the first place and therefore there is no need to verify anything except that the UTXO exists in an unspent state in some block using SPV.

4. Update UTXOs are of size <= O(logN)

The size of the UTXO should be worst-case O(logN) where N is the total number of state elements such as User Account IDs.
For just over 4 billion User Account IDs the size of the UTXO should be some constant multipled by 32, as an example. As a practical estimate, assume that the base contract size is 5 KB, then each transfer or state update will be at most 160 KB.

5. Enumerating Global Contract Balance takes O(1) time and space

It should take worst-case O(1) time and space to provide a proof of the global Contract Balance. It should be a very fast operation so that it is easy to audit the total funds locked into the Contract.

6. Enumerating User Account Balance takes O(logN) time and space

It should take worst-case O(logN) time and space to provide a proof of the User Account Balance where N is the total number of state elements such as User Account IDs.

7. Unbounded Scale to Trillions of Accounts and Key Values

The solution should be completely scalable to billions (or even trillions!) of accounts and values. There should be no limitation to the type and size of the data that can be stored. The growth of the global state into hundreds of gigabytes, terabytes or petabytes should still result in the space and time complexity of O(1)

8. Generate User Account Proofs Efficiently on Demand

Building on requirements 5, 6, 7, 8 we want to have a general purpose state proof system where any state can be verified in worst case O(logN) time and space where N is the total number of state elements such as User Account IDs.

It should be impossible to accidentally spend or destroy coins. It should be impossible to send inauthentic or fake coins, the system should prevent it and users can trust the UTXO prima facie.

Solution Overview

This paper assumes that the reader is familiar with Merkle Patricia Trees. Although this solution could be implemented with Merkle Trees where each node in the tree is a tuple (account, balance), however that would result in a much larger data structure and require many more loop iterations. Conceptually the technique will work with either a Merkle Tree or a Merkle Patricia Trie.

Reproduced here for convenience is the (Modified) Merkle Patricia Trie that tracks the Ethereum world state.

Modified Merkle Patricia Trie Ethereum Diagram

Stateless Execution Model

The “stateless client concept” was introduced by Vitalik Buterin, which he describes as follows:

STF(S, B) -> S’, where S and S’ are states, B is a block (or it could be a transaction T), and STF is the state transition function.

Then, we can transform:
S -> the state root of S (ie. the 32 byte root hash of the Merkle Patricia tree containing S)

B -> (B, W), where W is a “witness” — a set of Merkle branches proving the values of all data that the execution of B accesses STF -> STF’, which takes as input a state root and a block-plus-witness, uses the witness as a “database” any time the execution of the block needs to read any accounts, storage keys or other state data [exiting with an error if the witness does not contain some piece of data that is being asked for], and outputs the new state root.

Source: https://ethresear.ch/t/the-stateless-client-concept/172

The key insight here is that nodes (or our Contract Account UTXO) does not need to store the global state, but only the ‘State Root’. It is the users of the Contract Account which provide the appropriate merkle branches to prove what the state was prior to making a spend of the Contract Account UTXO. The Contract Account code does a validity to check to see that the merkle branches provide a valid attestation of accounts and balances being touched (By computing the merkle hashes up to the state root) and only if it matches the current State Root will it allow the State Root to be updated again.

This is a significant result because it means that the size of the “state” stored in the UTXO is only 32 bytes! What makes the UTXO larger, however, is the merkle branches that must be provided on each transition. Since the time and space complexity to read and update a Merkle Patricia Trie is O(logN) it follows that the inputs to the unlocking script are also O(logN) where N is the total number of accounts and keys stored in the global state. This is extremely scalable to trillions of elements and beyond which will still keep the UTXO under approximately 200 kb.

Unique Contract Identity

The follow sections will refer to a UTXO field called an asset identity invariant (or simply “identity” or “asset id”). This is the globally unique identifier of a contract.

This is a standard technique for embedding a unique identifier in a UTXO by requiring it to match the previous outpoint in the spend immediately following a special “minting” transaction.

This technique is used in the Deploy and Mint procedure.

Deploy and Mint

SuperAsset Contract Account: Deploy and Mint Diagram

Deploying a new Contract Account UTXO is to simply deploy the code to a new output with the contractId and stateRoot initialized to null (all zeroes).

The only way to spend this ‘genesis’ transaction is by filling in the contractId to the prev outpoint of the deployment transaction and to also include an initial user account that will hold the initial supply of coins.

We use the convention that each satoshi represents a single unit of the token. The satoshis never move between the (Sub) User Accounts in the Contract Account UTXO but represent the total aggregate value. The User Accounts can have decimal numbers of arbitrary precision to provide adequate divisibility while still tracking the total contract value in Satoshis.
Note that it is not shown here, but we can have a rule that allows a special address to continue to issue (mint) additional supply and increase the total amount of satoshis, and also transfer the minted balance to an account to add it into circulation.

The Merkle Patricia Trie gets initialized with a single key value pair, namely the hash of the single node of the userAccount => Balance. Balance must equal the outpoint amount (Satoshis) that was input.

Also note that a User Account is identified by the hash160 address.

Transfer

SuperAsset Contract Account Transfer Diagram

To transfer some of the balance to another User Account, simply provide the previous merkle paths for the user account which wants to send coins. The signature of the owner of the the hash160 address is provided to ensure that they authorize the transaction.

The contract logic enforces the atomic update of debiting the source account and crediting the destination account. Note that the total Satoshi quantity is conservedd in the UTXO and did not change between spends. It is the data key value storage amount that changed in the global state that is referenced by the State Root of the MPT.

Limitations

The reader will notice that the above mechanism implies that only a single account transfer can take place with each spend of the Contract Account UTXO. This limitation can be mitigated by having miners or ‘transaction aggregators’ package up multiple disjoint merkle paths into a single batch update to the UTXO.

In this manner there could be potentially hundreds or many more transfers packaged up into a single spend saving time and space. Further research area is to create an incentive structure for users *and* transaction aggregators (such as miners) to *want* to bundle up as many transactions into a single UTXO. This may be done by adding a small fee paid to the transaction aggregator or perhaps using Boost POW to throttle spends.

Another limitation is that since the state does not exist explicitly, there is a need for State Providers to index the Contract UTXOs to be able to quickly serve and compute merkle paths on demand. This is easier than it sounds since it is simply following the chain of spends from genesis to the chain-tip and then serving up any merkle branch in O(logN)

Further Research

Further exploration and research is needed in how to implement Strict Access Lists, Contract Upgradeability, and also Inter-Contract Communication.

Additional work will be done to show that it is easy for multiple users, who hold different token balances on different Contract UTXOs, to be able to atomicall swap tokens between each other. Each user can coordinate and then provide the outpoint of their token contract and the state merkle branches to spend the respective contracts in the normal way.

More work needs to be done on how to demonstrate a ‘transaction aggregation’ service that will allow greater speeds and throughput and also the prevention of ‘spamming’ the Contract UTXO that effectively blocks out others who may wish to interact with the contract.

Conclusion

This paper introduced a general design to emulate Contract Accounts in account-based blockchain by using the Bitcoin UTXO model. This approach greatly simplifies the design of Fungible Tokens (ie: “colored coins”) on Bitcoin. We presented a breakthrough design that enables arbitrary state storage and computation in a Bitcoin UTXO by leveraging a technique known as _stateless execution_.

We designed a highly scalable general purpose data store and contract account capable of scaling to trillions of state elements while providing efficient O(logN) state proofs. We presented a hypothetical layer 1 fungible token contract design that can handle arbitrary precision and provide rapid global and user account balance enumeration in O(1) and O(logN) respectively.

References

[1] John Adler, “Accounts, Strict Access Lists, and UTXOs”, https://talk.lazyledger.org/t/accounts-strict-access-lists-and-utxos/37

[2] Vitalik Buterin, “The Stateless Client Concept”, https://ethresear.ch/t/the-stateless-client-concept/172

[3] John Adler, “Practical parallel transaction validation without state lookups using Merkle accumulators”, https://ethresear.ch/t/practical-parallel-transaction-validation-without-state-lookups-using-merkle-accumulators/5547

[4] Xiaohui Liu, “Bitcoin Smart Contract 2.0”, https://xiaohuiliu.medium.com/bitcoin-smart-contract-2-0-d1e044abed5a

[5] Satoshi Nakamoto, “Bitcoin: A Peer-to-Peer Electronic Cash System”, https://bitcoin.org/bitcoin.pdf

[6] Gavin Wood, “ETHEREUM: A SECURE DECENTRALISED GENERALISED TRANSACTION LEDGER”, https://ethereum.github.io/yellowpaper/paper.pdf

[7] Attila Aros, “SuperAsset”, https://media.blockpress.com/file/d6c18189966ea060452bcf59157235f2e15df3abf7383d9d450acff69cf29181

--

--

--

https://blockpress.com https://mattercloud.io

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Aavegotchi GHST Token Is Now Live on Aave.com

TooNFT joins the BGA community!

The AppCoins Whitepaper In Short

Ethereum Proof of Stake (PoS) for Beginners

Ether Illustrative Photo

Swappi x Conflux x cBridge Cross-Chain Joint Event

Rapids Network - November 2021 Review

ARPA Monthly Report | December Progress Review

ARPA Russian Reps Joined the Commission on Blockchain Technologies and Crypto Economy of Russia

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Attila

Attila

https://blockpress.com https://mattercloud.io

More from Medium

Ethereum: ERC-20 Token Standard

How to Make a DAO for Complete Beginners

PolyPunks Clone Script — To Launch NFT Collectible Marketplace like PolyPunks on Polygon Network

This week in Dapps Ep.61