What exactly the merkle function is returning?

Question

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?

Answer 1

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.

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:

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: