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?
EOS.IO Stack Exchange is a question and answer site for users and developers of distributed applications built on top of the blockchain operating system, EOS.IO. It only takes a minute to sign up.
Sign up to join this communityIn 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?
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:
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: