Alphabill State Tree

Historically, different blockchain platforms have tried different approaches to represent the state of managed assets. Bitcoin, for example, stores UTXOs in the chainstate, a levelDB database. Ethereum uses a Merkleized Patricia Trie to represent accounts, that is, each leaf of the tree is either an account or a smart contract serialized by its leaf address.

In Alphabill, we use a count-certified authenticated Adelson-Velsky and Landis (AVL) tree where the nodes of the tree are units, which can be bills, tokens, or smart contracts. Tokens are first-class citizens in that each token in the system (whether native Alphabill currency tokens or user-defined tokens) is serialized by its identifier in the state tree.

Ethereum uses a state tree of accounts, Alphabill uses a state tree of tokens.

Ethereum uses accounts, which are represented as leaves of the state tree. Tokens are then created by smart contracts and those tokens exist as variables inside the smart contract. In Alphabill, individual tokens are created directly on the state tree, and a transaction order in Alphabill will change the ownership of the token.

The main advantage of over accounts is sharded parallelism of production and verification, that is, state, transaction, and network sharding become trivial in a bill-based model. In the example above in contrast with the account model where each transaction impacts at least two accounts, a transaction in the bill model updates only a single unit, that is, all tokens are independent—there are no cross dependencies between tokens that require a global ordering of transactions to achieve deterministic execution.

This allows for perfect parallelism, that is, all tokens can be updated and verified independently, and global state can be partitioned and managed by clusters of machines (validators) operating independently in parallel.

Parallel execution of transaction orders.

The above diagram shows that as the throughput increases, the state tree can be split into two subtrees or shards with each half of the tree being stored in memory of different machines. The key point is that the machines on different shards do not need to communicate with each other during transaction settlement. A transaction involves only a change in the ownership of a token, validated based on local context: the token's previous state and transaction order only. This implies that the subtrees can be processed in parallel without any synchronization or coordination with other subtrees

To understand scalability of verification and explain how individual ledgers for tokens can be verified in parallel, we need to understand how the state tree evolves over time.

Recursion: State Evolution Over Time

The figure below shows the evolution of the state tree for account-based blockchains such as Ethereum. Time moves from left to right and there are 4 blocks with the state tree shown for each block. The state root hash value for each block is shown in red. The leaves of the tree represent four accounts A0 to A3 (the state tree is shown lopsided for reasons which will become clear shortly). In Ethereum, the transaction units are accounts, and each transaction will impact at least two accounts.

Ethereum state evolution over time.

Every block, transaction orders will be processed which will cause the state tree to be updated. In the figure above, we show a transaction order making a transfer from account A3 to A2 in block B₁ and A1 to A0 in block B₃.

The figure below shows the evolution over time of the Alphabill state tree. Time moves from left to right and there are 4 blocks with the state tree shown for each block. The state tree consists of 4 tokens, A0 to A3 ¹. In Alphabill, each transaction will impact a single token.

Alphabill state evolution over time.

The key difference from the previous diagram is that when the state tree is built, the leaf nodes for each token are cryptographically linked to the leaf nodes of the previous token state (the dotted lines). As all settlement is local and all tokens are independent it is possible to extract the history for an individual token and allow it to be verified without requiring the history of other units. This is shown below for an individual token in the state tree. The blue hash-values are effectively an individual token blockchain which can be verified independently with the same security properties as the overall blockchain

An individual token blockchain, extracted from the main chain.

This ability to decompose the ledger into token subledgers allows a recipient of a transaction to independently verify that they are the new owner of a token without needing the full ledger². This is similar to physical cash. A user cares about the bills in their wallet, not those of anyone else. Independent verification can be done on mobile devices, or even offline, without the need to trust third parties as in the case of having to rely on traditional "light clients".

Entire token histories can be stored locally on client-side wallets.

If users can store their tokens off-chain, then a logical conclusion is that no transaction data needs to be stored on-chain at all³. A user can store all necessary information (token ledger and their private key) off-chain. To initiate a peer-to-peer transaction, they will include a signed transaction order along with the token ledger, both of which will be sent to the Alphabill Distributed Machine, which can now validate the transaction statelessly. This approach gets as close as possible to the properties of physical cash—physical cash bills are tokens which are self-verifiable and be passed from party to party.

Offline Transactions

Under certain conditions the system can be extended to support transfer of tokens with final, irrevocable payments even in the absence of network connectivity. A payer who wishes to transfer tokens offline to a known payee (for example, a subway operator) can lock⁴ the token which can then be unlocked either a) after a specified period of time (for example, one week) by an arbitrary transaction from the payer, or b) by a transaction order from the payer, where the recipient can only be the known payee. In an environment with no network connectivity, the payer can then generate a transaction order for a specified amount for the payee and digitally transfer the transaction order without network connectivity to the payee, who can independently and without trusted intermediaries, mathematically verify that only they can unlock the token and claim ownership prior to the timeout period. The only information the payee requires to verify the validity of the transaction is the genesis block (B₀ in the above figures).

Process for implementing off-line transactions.

Once the payee has connectivity, the payee will send the received transaction order to the Alphabill Distributed Machine and claim unconditional ownership of the tokens.

Certificates

A certificate is an authenticated data structure used within Alphabill that contains elements that enable an interested party to verify proofs such as proof of uniqueness, proof of ownership, proof of transfer, etc.

The design of the Alphabill state tree allows to create different types of certificates:

• Unicity Certificate: a proof that the ledger, as a whole and its components, is unique and passed validation.
• Transaction Execution Certificate: a proof that a transaction t is in the block B of the blockchain.
• Unit Certificate: a proof that a token has certain attributes (for example, ownership) in the state tree.

State Tree Splits

It would be inefficient to have to pre-allocate space in the state tree for every possible token. For example, the equivalent of an ERC-20 smart contract may require the issuance of billions of tokens. Fortunately, creating state space for all individual tokens is not necessary as, upon issuance, there are a limited number of owners. In this section, we show how the state tree can be expanded and contracted through transaction orders.

Consider the equivalent of an ERC-20 token called "Atoken", the issuance of which will be 100 billion tokens. Initially, there will be a single owner (the issuer) who will own all 100 billion tokens.

User-created token at issuance.

When a transfer of one token occurs to a new owner, the tree is split and the original token is replaced with a node with child leaves, which represent the new fractions of the token.

User-created token after first split.

The Alphabill AVL tree is count certified so that each parent node maintains the total sum of created parts.

User-created token after second split.

After a second transfer of one token, the state tree initially looks like above⁵.

The same bill-splitting principle can be applied to any fungible token. For example, the figure below shows a user who wishes to make payment of 34 cents using the "Alpha-USD" stable coin but only has one single Alpha-USD dollar.

Precise payment of 0.34 ALPHA-USD.

Allowing for splits in this way also allows for precise atomic payments within a single block. Joins are also possible, however, they are not available as part of transaction orders. Instead, a user may make a "dust collection" swap request such that small value tokens may be consolidated into a single token. The dust collection procedure is executed independently during the creation of a new block.

Note that the state tree splits and joins do not break the parallelism as all splits and joins can be guaranteed to be local to the machine in which the split or join occurs.

Double Spending

Double spending is impossible by design. Each unit has a unique address, and there can only be one proof of uniqueness per round, assuming the hash function used is collision-resistant.

---

¹ The Alphabill Yellowpaper refers to units. There are three types of units: bill, tokens and smart contracts.
² Technically, what is useful as a proof of payment is a "proof of transaction execution" which applies to a single transaction only, without the full transaction and token history.
³ There still needs to be a state tree leaf hash created to allow the validators to verify that token ledger received as part of a transaction order was minted and is the up-to-date version.
⁴ Technically they will install a predicate, see Predicates for Single-Unit Programmability
⁵ In reality, the AVL tree is self-balancing. For a precise description, see Alphabill Yellowpaper