Indexing Blockchain While Introducing Parallel Processing — aelf’s Solution

Published in

aelf

5 min readMar 1, 2019

Introducing any new innovation often comes with growing pains. One such has been found by many emerging projects as they attempt to solve the scalability debacle. Aelf model relies in indexing the transactions through the use of merkle tree technology, but this also introduces a new hurdle as the project also incorporates parallel processing.

Indexing is how side chains connect to the aelf main chain. To participate in the aelf ecosystem, a side chain requests indexing by the main chain, for which the side chain pays transaction fees. Indexing a static blockchain comes with its own challenges. As more blocks are added to the chain, it becomes more time-consuming to index the entire chain.

However, even this challenge takes a somewhat simplistic view, as it assumes indexing happens while the blockchain itself is static, when in reality more and more blocks are being added while indexing is ongoing. This brings a more significant set of challenges, as there will be dependencies between the inputs and outputs of some transactions, while others are unrelated to one another. So, in trying to index a dynamic blockchain, it’s inevitable that indexing will at some point become stuck at a transaction dependent on another that has yet to be processed.

Blockchains such as Ethereum overcome this by requiring transactions to be processed strictly in sequence. However, sequential processing puts a limit on transaction speed and thus, on scalability.

In the development of aelf, we have set out to build an ecosystem that overcomes these problems. Our solution provides a high transaction throughput on the aelf main chain, allowing side chains to process transactions at speed and process unrelated transactions in parallel to one another.

At the same time, the main chain must also be able to index the necessary transactions on the side chains at the same pace. This is achieved through a side chain dynamic indexing system which operates alongside parallel transaction processing.

Side Chain Indexing

Side chains on aelf may be either internal side chains operating under the aelf OS, or they may be external side chains of high importance, such as the Bitcoin or Ethereum blockchains. The nodes on the main chain read information from the side chains and form a Merkle Tree root. In the case of external blockchains, this root obtains Merkle proofs via messaging to verify any given transaction.

The precise indexing strategy for each side chain is determined based on its unique characteristics. This flexibility in indexing strategy overcomes the issue that different side chains may have different block generation speeds. It also avoids the wasted effort of indexing orphaned blocks on blockchains that have a high probability of forking.

So, for instance, the indexing strategy for a blockchain such as Bitcoin could mean indexing happens one minute after block formation, once a block can be confirmed not to be an orphan. If an aelf side chain and the main chain adopt merge mining, then the miners of both chains can also index both chains in real-time.

Indexing of side chains is incentivized through the aelf token system, which pays miners in transaction fees generated by the side chains. In this way, side chains must also ensure that indexing remains economically favorable for the miners.

Parallel Processing

Sequential processing requires that all transactions are processed in sequence. It offers the benefit of more straightforward indexing; however it’s inefficient as it hampers the speed at which a blockchain can operate.

Parallel processing allows unrelated transactions to be confirmed in parallel to one another. So, a transaction from one side chain can be processed at the same time as one on a different and unrelated side chain. In aelf, a node will assign unrelated (mutex) transactions to different groups. Within a single group, all transactions are processed in sequence. However, the groups are all processed in parallel, achieving far faster confirmation time than pure sequential processing.

Nodes will prioritize transactions that can be processed in parallel. However, it may be that a particular transaction cannot be processed because its input is dependent on an unconfirmed output. These “special” transactions can be processed in sequence, rather than in parallel, provided the side chain is able to pay sufficient transaction fees to the miners to incentivize them to do so. Otherwise, nodes can simply reject these transactions.

If one node ends up accepting seemingly dubious transactions that can’t be processed in parallel or within an acceptable time frame, then it increases the likelihood that the block will be rejected by other nodes.

If a transaction is left unconfirmed and isn’t withdrawn within a short timeframe, it will be deemed to be in “chaos.” To handle this, aelf requires that each transaction is marked with the header of the latest block at the time it’s broadcast to the network. If the transaction remains unconfirmed after 64 subsequent blocks are confirmed, then it will expire.

Amdahl’s Law and Computing Resource Efficiency

Amdahl’s Law allows us to calculate the theoretical speedup resulting from using parallel processing. The law shows that the execution efficiency of the whole task increases with better resources in the system. The increase in speed is always limited by any part of the task that doesn’t benefit from the improvement. In other words, if a blockchain network with sequential processing is a herd of buffalo, it can only move as fast as the slowest member of the herd.

Therefore, aelf’s Parallel Execution Scheduler (GPES) separates transaction data and computational dependency from the memory pool. Cloud computing allows nodes to operate across clusters of machines, thereby enabling increased transaction speed which supports parallel processing across the entire network.

The Takeaway

Scalability is one of blockchain’s most significant problems to date and one that aelf has set out to tackle from multiple dimensions. Through the deployment of the DPoS protocol, combined with parallel processing and a dynamic side chain indexing mechanism, aelf aims to achieve an unprecedented level of scalability, the start of it already having taking form in the initial TPS results of 14,968 in Aug, 2018 at the start of the testnet.