How Karma and Sumus Dev team found some core blockchain bugs in EOS
When the project passes an ICO stage, the volume of work increasing several times. Today we do not want to talk about the necessity of launching an ICO, but we want to show what a huge amount of work awaits for each project during the next stages. Work, which is rarely spoken of.
While searching for our own technical solutions, Karma.red and SUMUS dev teams are engaged in studying the best practice and experience of blockchain technology implementation. I will describe one day of work on the project in 2017, which will demonstrate how important it is to work under the conditions of complete immersion in the details of the subject matter.
For example, one of the fundamental algorithms of blockchain technology is a Merkle tree construction, where unconfirmed transactions are packaged while creating a new block.
The Merkle tree is a complete binary tree with hashes from the data blocks in its leaf nodes, while internal vertices contain hashes from the addition of values in the child vertices.
The importance of building a Merkle tree for a blockchain is extremely high, because using this tree, a blockchain network participant performs a quick check of the correctness of the block without analyzing the correctness of all transactions within the block.
The algorithm for constructing a Merkle tree can be described as follows:
- 1. Receive all the hashes of transactions that need to be placed in the block.
- 2. The hashes of transactions are stacked in pairs, if the number of hashes is odd, then it is necessary to supplement the block with another empty transaction or duplicate the latter, since the Merkle tree is binary.
- 3. Next, the hashes are computed from the sum of two transaction hashes, the addition process is repeated until the root of the tree is received.
- 4. The root of the tree is written to the block header.
We studied the implementation of the Merkle trees in various blockchains, including in the Graphene and EOS blockchains.
The following method “calculate_merkle_root” of the class “signed_block” calculates the root of the Merkle tree in the Graphene blockchain.
The transaction hashes are written to the “ids” vector, see line 7-8 of the code.
Next, a loop is created with a condition, see line 11 in which the hash calculation cycle is executed from the sum of two hashes, lines 16–17.
The loop terminates when the variable “current_number_of_hashes” is less than two, the variable is overridden by the value “i_max / 2” every time, see line 20, when the loop described in 16–17 ends, where “i_max” is the number of hashes that are added to each other. It can be argued that the code written above works correctly and a hash of the root of the Merkle tree will be obtained as a result of its work, see line 22.
The implementation of the construction of the Merkle tree in the EOS blockchain is in the “block.cpp” file, and the code is presented below.
If you pay attention to the string that specifies cycle at line 5 for (int i = 0; i <ids.size () / 2; ++ i) »++ i) », you can verify that in the Merkle tree only transactions that are in the first half of the list are addressed to the address “Ids.size () / 2”. The block can be modified by replacing existing transactions in the gap between “ids.size () / 2” and “ids.size ()”, and such block will be recognized as legitimate, since the given transactions do not participate in the calculations of the Merkle tree.
Now it becomes clear how important it is to understand the solutions that you are going to use in your projects.
We've notified EOS team about this vulnerability and we're glad that in February, when the EOS development branches merged, this issue was eliminated. And we hope, that the entire community will also help each other during the development of blockchain technologies.
Here's what happened to the vulnerability found and how it is solved.
The “merkle” method is now implemented correctly:
As shown in line 7 above, the EOS team fixed the vulnerability of calculations in the Merkle tree by doubling the value of the variable “i” “ids [i] = digest_type :: hash (make_canonical_pair (ids [2 * i], ids [(2 * i ) + 1])); “.
We express our respect to the professionalism of the EOS team and we hope that other teams within the blockchain community will help and support each other, bringing together solutions for the creation of advanced and stable blockchain platforms.
Cheers
ˆ_ˆ
