Khipu: The Fastest Ethereum Implementation in the World

As the continuous rise and volatility of Bitcoin take a firm grip on each currency fan lately, the investment enthusiasm of the currency circles has also been mobilized. The industry is eagerly waiting to see whether the next bull market will arrive earlier. At the same time, more and more people are also brought into the blockchain industry.

From Satoshi Nakamoto’s Bitcoin to Vitalik Buterin’s Ethereum, exactly ten years have passed. Over this period, blockchain technology has evolved from a small-scale encrypted currency experiment to a large-scale distributed application involving tens of millions of participating accounts every day. An important development direction of blockchain is to use digital currency to connect with traditional banks and financial markets. It is encouraging to see that as more and more people now participate in the industry, more funds will be inevitably brought in and push forward the better development of blockchain. Correspondingly, there will be higher performance requirements for Ethereum-based Blockchain 2.0.

Currently, Ethereum performance improvement faces many bottlenecks, which gives rise to the demand for blockchain technology innovation. It is believed that before the next bull market arrives, blockchain will be significantly improved and upgraded. Khipu has shown necessity and foresight in its exploration of the problems faced by Ethereum, as well as in its innovation of relevant solutions to these problems.

Where are the bottlenecks of Ethereum?
We take Ethereum as a typical case because it is a blockchain implementation that does not make any compromise on the way towards the ultimate form of distributed computing. So, what is Ethereum’s limit of block execution on a single node? Where are the bottlenecks?

For enterprise applications, TPS is now Ethereum’s main bottleneck. One way of to increase TPS is sharding. For example, at the current processing capacity (the theoretical value of TPS is about 25), 100 shared chains may reach a TPS of 2,500 at the cost of only 1/100 or 500 endorsing nodes for each chain, only 1/10 of the 50,000 nodes endorsing a chain in the past. When TPS goes up, security and credibility both fall. Therefore, raising single-node TPS (i.e. the TPS of a single node) is always most critical. For example, if the TPS of one chain can be increased to 1,000, then 10 shared chains will have a TPS of 10,000, while each chain can still guarantee the endorsement of 5,000 nodes. TPS is related to the improvement of CPU. At present, transactions can only serially by single threads. Only after the ability to execute transactions in parallel is improved can CPU breakthroughs be made.

The difficulty of parallel contract execution within a block lies in that we do not know in advance the relationship of dependency between contracts. Access to the Account, Storage and Evn Code of the same address is where race conditions may exist in Ethereum contracts. If users are asked to identify and specify the address ranges over which condition conflicts occur when they compile contracts, it is clearly unrealistic to expect no errors or omissions. Whether, where and under what condition bifurcations will race conditions occur can only be judged after the current state involved is deterministically obtained. With existing contract programming languages, it is almost impossible to obtain through static code analysis completely correct results without missing items.

However, this does not mean that the parallel execution of contracts in a block is absolutely impossible. Interestingly, this question has been raised by Ethereum for several years now, but nobody has really tried to solve it. In fact, the current problem is more of an engineering than a theoretical or design one. In the process of project implementation, it is possible to find out problems in the design and then come up with better designs.

Khipu breaks through the bottlenecks of Blockchain 2.20 and solves practical difficulties
Khipu has made comprehensive efforts in this regard and completed project implementation.

Khipu’s implementation solution is to respectively execute all transactions in parallel starting from the world state of the block of the previous period. In the process of execution, the above three race conditions encountered on all ideal paths are recorded. After the parallel stage ends, the merger stage is entered where the parallel world states are merged one by one. When merging a transaction, firstly judge from the recorded race conditions whether they are in conflict with the preceding merged race conditions. If not, merge the transaction directly. If yes, execute the process again with the previously merged world state as the starting point. Finally, use the hash of the block as the final check on the merged state of the world. This is the last line of defense. If an error is found in the check, abandon the preceding parallel scheme, and serially execute the transactions in the block again.

Here, Khipu introduces a parallelism index, namely the proportion of transactions within a block that can merge results directly without requiring execution again. According to Khipu’s actual test results, the parallelism ratio can reach 80% on average.

Overall, if computing tasks can be fully parallelized, single-chain scalability will be unlimited: you can add more CPU cores to each node. If this is not the case, then the maximum theoretical rate will be limited by Amdahl's law: the system speedup limit you can achieve depends on the reciprocal of those parts that cannot be parallelized. If you can parallelize 99% of them, you will be able to speed up the system 100 times; but if you can only achieve 95% parallelization, then you will only speed up the system 20 times. In the case of Ethereum, if there is 80% parallelization, it means that 20% of the parts cannot be parallelized. As the reciprocal of 20% is 5, Khipu’s speedup limit will be 5 times.

Another limitation of Ethereum lies in its access efficiency when there are high-level trie nodes on a single computer. This loophole resulted in the DDos attack on Ethereum in 2016. After analyzing the existing storage engine loopholes and the characteristics of blockchain data, Khipu has especially developed a storage engine called Kesque suitable for blockchain kv data. Test results of the new engine show that there is only one-thousandth probability of collision for hundreds of millions of Ethereum kv data records. In 99% of the situations, for a given key, disk IO can be loaded into the exact corresponding record one time at most. When processing hundreds of millions of typical Ethereum data, this newly designed storage engine can have a random read capacity which is an order of magnitude higher than that of LevelDB.

Khipu has become the fastest Ethereum implementation in the world
With its optimization of parallel Ethereum transaction execution and the specially designed storage engine Kesque, Khipu has reached the following performance when batch processing 6,184 blocks with more than 6.4 million numbers on a computer with a 32G memory, SATA SSD hard disk, and Intel® Xeon® E3-1231 v3 @ 3.40GHz quad-core CPU: 4.11 blocks are processed per second, actual TPS reaches 384, 23.5 MGAs are executed per second, the degree of parallelism is 80%, and processing speed is twice that of Parity-2.1.5 developed using Rust language, which is the fastest Ethereum implementation in the world.

Khipu’s breakthrough in parallel execution marks a historic innovation. It brings a big step forward in the performance of Ethereum and elevates the development of the entire blockchain industry to a new level. Khipu will also effectively leverage its technological strengths in multiple scenarios. The first product to be introduced will be a decentralized Khipu search engine. On this basis, Khipu will implement more application scenarios. It will continue to pursue higher technological breakthroughs and create more possibilities.

http://khipu.io/
https://twitter.com/dcaoyuan
https://github.com/dcaoyuan
https://weibo.com/u/1875401263