1

In the below file, https://github.com/EOSIO/eos/blob/v1.7.4/libraries/chain/merkle.cpp, what do ids.front() mean?; what exactly this function Merkle is returning?

Could you please explain what this contract is doing?

1 Answer 1

2

You have multiple questions in this post, in the future you should try to have a more focused question.

".front()" is a vector function. From the documentation:

std::vector::front() Returns a reference to the first element in the vector.

Now, I'll assume you weren't actually asking about front(), and instead about the purpose of the merkle() function in EOSIO.

Background

To understand, you need some background information:

  • A digest in cryptography is the output of the hashing function, which in EOSIO is currently sha256.
  • A merkle tree data structure is just a binary tree for which each node is a hash of its child nodes. Merkle tree structure

So now let's take it line by line (Source).

if( 0 == ids.size() ) { return digest_type(); }

This is simply handling the case where there are no digests in the list, it returns a default-constructed digest.

Now the interesting part:

while( ids.size() > 1 ) {
  if( ids.size() % 2 )
     ids.push_back(ids.back());

  for (size_t i = 0; i < ids.size() / 2; i++) {
     ids[i] = digest_type::hash(make_canonical_pair(ids[2 * i], ids[(2 * i) + 1]));
  }

  ids.resize(ids.size() / 2);
}

Firstly, notice that it loops until the vector side <= 1, so we know whatever happens inside the loop is going to be reducing the size of the vector.

Secondly, the start of the while loop ensures that the total number of elements is divisible by two. How?

if( ids.size() % 2 ) // If the remainder of size() / 2 is not 0
     ids.push_back(ids.back());  //Push back a duplicate of the last element

For the following while loop, I made a diagram to explain what it's doing more easily: eosio::chain::merkle flowchart

Once the merkle tree has been reduced to size 1, the single element left is known as the "merkle root" and it is returned.

return ids.front(); // Returns the only element left in the vector

As an example, here's what the algorithm looks like visually on an example set: enter image description here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.