Design of the Fetch.AI Scalable Ledger

Scalability has undoubtedly been the topic at the forefront of decentralised ledger design throughout 2018 with rates of thousands, tens of thousands and even millions of transactions per second (TPS) claimed by many of the projects slated for launch over the coming year. Even on established platforms, such as Bitcoin, the typical demand for transactions falls well below the upper end of this range, so the novel ledger designs have at best been operating under test conditions. It remains to be seen how successful they will be in supporting huge transaction volumes while maintaining security and keeping costs low. The prize for solving these technical challenges is a slice of the future multi-trillion-dollar market in powering the machine-to-machine economy, which is the target of the system under development at Fetch.AI.

In the decentralised world envisaged by Fetch, every network-enabled device is controlled by an Autonomous Economic Agent (AEA) that facilitates communication and financial exchange. The Fetch ecosystem enables agents to collaborate with each other to find bottom-up solutions to supply-chain optimisation, energy markets or digital health, to name a few examples. This places certain demands on the ledger, which must scale to accommodate millions of transactions while still delivering rapid and consistent confirmation times. Another key requirement is an expressive and low cost smart contract system. In this article we provide an accessible introduction to the scalable ledger. Additional details can be found in our technical white paper.

When we consider the prototypical blockchain structure (see Figure 1) there are several points that could act as potential bottlenecks:

Figure 1 In a typical blockchain, each block is proposed by one node in the decentralised network. This block is broadcast to other nodes, which decide whether to add it to their local representation of the blockchain. If all of the local representations of the blockchain are identical this constitutes a global state.

· Block Synchronisation Latency in broadcasting mined blocks across the network. Increasing the rate at which blocks are produced or their size might increase throughput but at the cost of reduced security.

· Memory/Storage Maintaining a complete record of the blockchain becomes expensive for participating nodes.

· Contract Execution The time required to execute transactions could act as a bottleneck on ledgers with complex smart contract languages and large state databases.

A simple solution to the scalability issue is to simply duplicate the blockchain so that network traffic and execution is divided between multiple independent chains. This process can be repeated multiple times to scale the network to a theoretically infinite number of TPS (see Figure 2). However, this leads to a second problem of how to enable transactions between the different chains.

Figure 2 Duplicating a typical blockchain including the peer-to-peer network leads to a doubling of the transaction throughput.

One approach is to incorporate another layer to mediate communications between the different chains or to specify a reference chain to resolve conflicts between subsidiary chains (also known as side-chains). However, this potentially introduces additional performance bottlenecks or security vulnerabilities. The Fetch scalable ledger resolves this issue by instead associating each subnetwork with a structure known as a resource lane. Nodes that mint blocks, also known as block producers, sit at intersections of all of the independent subnetworks (In Figure 2, these nodes are members of both blockchains and are represented by concentric green and purple circles). A node that has been nominated to be the producer for the next block has access to a set of transactions from several resource lanes, as shown in Figure 3.

Figure 3 Resource lanes and block architectures. Each horizontal line represents a single resource lane (in this example there a five, each represented by a different colour and city). Transactions are represented by vertically oriented pale blue blocks. These contain coloured circles that denote the resource lanes that are involved in the transaction. In this example, the left-most transaction involves resources in lanes 1 and 5, corresponding to Tokyo and Mumbai. The vertical black line represents the final valid block slice. In this example, the block producer could earn a higher fee by moving the transaction in the fifth slice to the second slice, as shown by the arrow.

The blocks in the Fetch ledger are divided into a fixed number of slices that can each contain multiple transactions. The transactions involving a single lane are equivalent to within-chain transactions, while cross-chain transactions affect multiple resource lanes. To be valid, all of the transactions within a slice cannot affect overlapping resources. This is the key property that enables the transactions within the block slice to be safely executed in parallel. A transaction that only involves resources from lane 2 can, for example, be executed at the same time as a transaction that only involves resources from lane 3 since the two transactions involve a non-overlapping set of wallet addresses and state variables.

An analogy that can help to understand this concept is to imagine that there is a transaction, let’s call it A, between two users in London while a second transaction, B, is between two users in New York. This information alone is enough to ensure that these transactions cannot be in conflict. It’s possible that a different transaction, C, between two London users might not be in conflict with A. (One type of conflict might be spending money that has already left an account in transaction A). However, checking whether this is the case requires additional computational effort, and this problem becomes much more acute when more complex transactions such as smart contracts are executed. The resource lane architecture allows these sequential checking steps to be performed in parallel to increase the ledger’s throughput.

From the perspective of the block producer, the objective is to pack as many transactions as possible into the block of a specified size to maximise the fees that they receive (Figure 4). This process is analogous to the one of the key innovations in modern CPU architectures, where non-conflicting operations are arranged so that the maximum number can be executed in parallel for a particular number of clock cycles. In the case of the ledger, the improved performance arises from the economic incentive for the block producer to increase their transaction fees. Once the block has been prepared, the transactions within it are cryptographically secured with a Merkle tree and the block is synchronised across the network.

Figure 4 By packing as many transactions as possible into the block, the producer maximises the fee they receive. A side-effect of this process is that this also increases the number of transactions that can be executed in parallel.

The design of the Fetch ledger enables all of the potential bottlenecks to be relieved by increasing the number of resource lanes in operation, similarly to the naive approach of duplicating independent chains. The ledger’s principal benefit is that it provides a scalable and secure mechanism for enabling transactions between chains. The design also allows the number of lanes to be increased or decreased to meet changes in demand, while the strict ordering of transactions and parallel execution provides a suitable platform for delivering cheaper and more expressive smart contracts. A final advantage of the design is that it can be considered as a sharding scheme that enables light nodes to keep track of only some of the resource lanes in the blockchain.

Fetch.AI will be showcasing results from its test network towards the end of 2018 with detailed analysis of the transaction throughput.