Blockchain’s rapid evolution has led to the development of numerous distributed applications. So, when it comes to application ‘landing’, what are the potential problems in the underlying blockchain infrastructure, and how is the parallel execution of transactions important?
Development background
By building a new trust mechanism, blockchain greatly expands the basic functions of information technology and the depth and breadth of applications. One of the key public blockchain characteristics is consensus. Consensus is the way users agree on how to write new transactions in the database. In addition, there are a series of incentives to keep the system running: there need to be rewards to attract enough users to help maintain the blockchain; and there need to be penalties to keep people from attacking the system (eg overloading the system by imitating a large number of fake users).
In terms of blockchain technology, consensus refers to ‘complete transaction sequencing and reach consensus on the latest state’. For blockchains using the account model, transactions only contain events, and the state is generated after the transaction is executed. A common way of achieving consensus on the latest state can be described as follows: the consensus node executes all transactions in the block before packaging the block, and saves the calculated latest state in the block header to be packaged. After the block containing the latest state reaches a consensus, the transactions in the block are sequenced, and the latest state also completes the consensus. Any other consensus node can replay the transactions in the block to verify the correctness of the state.
However, this processing method restricts the transaction processing capability of the consensus algorithm. For example, when the block B(h) with height h reaches a consensus, the consensus node (also called leader node) with height h+1 packages and executes B(h+1) before broadcasting B(h+1) , other consensus nodes must execute B(h+1) after receiving B(h+1) to verify its correctness.
During the entire consensus process, these two serial block execution processes (transactions are executed first, then consensus results) slow down the consensus efficiency.
Current issues
At the same time, TPS (Transaction per Second), which currently reflects transaction throughput, is an indicator for evaluating performance. In order to improve TPS, the industry has proposed an endless stream of optimisation solutions. The ultimate focus of these is to maximise the parallel execution capability of transactions, and reduce the entire transaction processing time. At present, the industry has the following two processing methods for transaction execution:
1. Transaction serial processing method: For example, there are 1000 transactions in a block, and the serial processing method is to perform the following process from the first transaction to the 1000th transaction in sequence:
Data Fetch — Decode Decode — Hash Operation (Transaction Verification) — State Change (Native Transfer and Smart Contract Execution) — Write Data (World Database) 5 steps.
The asymmetric elliptic curve algorithm is used to decrypt the transaction signature, which takes CPU time in particular. In addition, the execution of the smart contract also needs to call the EVM virtual machine, and there is also a lot of context switching overhead.
2. Transaction pipeline processing method: This architecture is similar to the Classic RISC pipeline (classic reduced instruction set pipeline), which divides the following 5 steps into pipelines, and each pipeline stage processes one instruction at a time. Each of these stages consists of an initial set of instructions that operate on the outputs of incoming transactions.
Block decoding (decode):
Blocks need to be sent from one node to another during consensus or synchronisation between nodes. During this process, blocks are transmitted between networks in the form of RLP encoding. After the node receives the block code, it needs to decode and restore the block to a binary object in memory before further processing.
Transaction verification (verify):
The data obtained by the signature can be divided into three parts (v, r, s). The transaction is signed by the sender before it is sent, restores the public key of the transaction sender, and verifies the identity of the transaction sender.
Transaction execution (execute):
Executes all transactions in the block, updating the blockchain state.
Data commit (commit):
After the block is executed, the block and related data need to be written to the disk for persistent storage.
Solution
Regardless of the serial processing method or the pipeline processing method, only one transaction can be processed at the same time, and the transaction can’t be processed in parallel. This is because the same address account may be operated in multiple transactions. If it is processed well, it may cause a double-spending problem. Only after the execution of the previous transaction is completed, the next transaction can be executed, so as not to interfere with each other. Ensure that transactions are executed correctly.
We know that there will be a large number of unrelated transactions in the same block, for example: transaction 1 is account A transfer to account B. Transaction 2 is a transfer from account C to account D. These two transactions are completely unrelated. No matter who writes to the world database first, it will not have any impact on the final result.
However, the above two processing methods cannot bring about parallel execution of transactions. For this reason, we have created a new transaction method based on the relationship of transaction dependencies. First of all, we use this method to group transactions, and divide the classes with transaction correlation into one group, and there is no dependency relationship between transaction groups and groups, thus forming a DAG (directed acyclic graph). Based on intra-block transactions, batch asynchronous verification of transactions and result sets, analysis of transaction DAGs, and batch execution of read and write operations that do not have account correlations according to the read-write set value range.
For example, the nth block contains five transactions, t1(A->B), t2(B->C), t3(D->E), t4(C->C), t5(B->F), According to the analysis of the account correlation algorithm, the read sets of t2 and t5 to account B must depend on the write set of t1 to account B, the read and write sets of t4 to account C depend on the write set of t2 to account C, and the read and write sets of t1 and t3, not relevant.
Therefore, the two transactions t1 and t3 can be carried out at the same time. When the write set of account B by t1 is executed, the two transactions of t2 and t5 must be executed sequentially due to the conflict between the read and write sets of account B of the two transactions t2 and t5.
Assuming that t2 is executed first, after t2 is executed on the write set of account B, the write set of t2 to account C and the read and write set of t5 to account B can be performed at the same time, the write set of t5 to account F and the read and write set of t4. There is no correlation, so it can be carried out at the same time, and the execution of five transactions has been completed. The transaction read-write set domain is highly related to the block, that is, when the n+1th block comes, there will be a new read-write set domain.
In common blockchains, transactions are executed sequentially. Assuming that each transaction takes 0.1 seconds, the total time is 0.5 seconds. Our blockchain uses pre-execution and read-write sets because it can be batched. Therefore, the time will be reduced to 0.3 seconds, not only the efficiency is increased, but also the parallel computing resources of the computer GPU/FPGA can be fully utilised.
Of course, this is just a simple comparison example. However, it is foreseeable that our transaction speed will increase exponentially in the future as the number of transactions increases dramatically and the overlap decreases. From an industry development perspective, the scalability problem can be solved with parallel execution. One of the logical progressions is pre-execution (pre-simulated execution), which we’ll look at more closely next time.
For more information: caduceus.foundation/ info@caduceus.foundation
Discord: discord.com/invite/ztygXMtr3d
Twitter: twitter.com/Caduceus_CMP
Telegram: t.me/CaduceusMetaverseProtocol
Facebook: facebook.com/CaduceusMetaverseProtocol/
