How to calculate `action_mroot`

Question

UPDATE #3 for future action_mroot calculators:

The two critical bits of info needed to do this (that are neither easy to find nor documented) are:

• There exists an extra action (which has a receipt) in every block that's called the onblock action. This is not reported on most block-explorers and requires a plugin on your node in order to get it.

• The action_mroot is calculated from the serialized action_receipts (including the onblock action) and not the serialized actions themselves.

I can't post any code despite now being able to calculate the action_mroot correctly because alas the Rust that I've written is currently private/proprietary. That said, it's easy to get the code itself from the EOS codebase, that difficulty was in finding out the above two pieces of information.

 

 

---

UPDATE #2:

So per @conr2d's comment on his answer & @riccardo's elaboration, it turns out that the action_digest in the merkle function in the EOS code base is not using the action_digest within an action, but is calculating a different digest using the entire action_receipt.

This unfortunate naming collision appears to be the root (harr) of this whole issue.

 

 

---

 

 

UPDATE #1:

So @conr2d's answer has shed some light on the situation but the puzzle is still unsolved.

With @conr2d's help we now know that in blocks which bloks.io report as having zero actions and zero transactions there actually is one action!

It's called the onblock action and it occurs in every block. Bloks.io doesn't bother to report for some reason. This higher precision block explorer does include this extra hidden action though, but not in the format we need it.

The still incorrect calculation:

And so now instead consider the Jungle block #56234435 which bloks.io reports as having zero actions but which Eosq correctly shows with one action.

Diving into that action we find the action itself:

"act" : {
    "account" : "eosio",
    "name" : "onblock",
    "authorization" : [ {
        "actor" : "eosio",
        "permission" : "active"
    } ],
    "data" : "ee9f854a500f7598aaa9d4650000035a11c19eada85e71976a9d04cb26c767ec25fa590830bec03ebf8746d7630795c33c4d4f672b0da40a7c96eb4ae7c18a25613cae2f377d2df6891c889b06fc73746a81d348db1fa682ee525bfd4cef4ea7d915aaaf4b973be1886716d3dadd1c0100000000"
}

...along with the action_digest of a6a370c6569034a4cc41935dd88f83d1c64e0414580872f29d87f69fe7a5d769.

However the problem still remains, because the block in question's action_mroot is 6cd473b189a292bd520cac3430cc7934273da81cc3417376194a5d757b4abdc8

Per the merkle function posted below in the original question, a merkle tree made over a single digest should have that digest as its root.

But here, that's clearly not the case!

Tl;dr:

How to calculate the action_mroot of: 6cd473b189a292bd520cac3430cc7934273da81cc3417376194a5d757b4abdc8

...from this single action_digest of: a6a370c6569034a4cc41935dd88f83d1c64e0414580872f29d87f69fe7a5d769?

What ELSE am I missing?

 

 

---

 

 

The Original Question:

So given the Jungle Testnet block #55033985 that has:

 

• an action_mroot of 7f3d...9928
• one action with a digest of e6a5...c058 (from the tx here)

 

My question is: How to calculate 7f3d...9928 from e6a5...c058??

 

---

 

Looking through the EOS codebase, I know that it's using sha256 as it's hashing function. I've also read that the action_mroot is the root of a merkle-tree over all the actions retired in the block. (Source for that here.)

Digging into the source shows the function that calculates the action_merkle to look like so:

 

   checksum256_type calculate_action_merkle() {
      vector<digest_type> action_digests;
      const auto& actions = pending->_block_stage.get<building_block>()._actions;
      action_digests.reserve( actions.size() );
      for( const auto& a : actions )
         action_digests.emplace_back( a.digest() );

      return merkle( move(action_digests) );
   }

Where the merkle function looks like:

digest_type merkle(vector<digest_type> ids) {
   if( 0 == ids.size() ) { return digest_type(); }

   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);
   }

   return ids.front();
}

But looking at that merkle function, it would suggest that having one digest in the passed-in vector would mean the merkle-root would be that lone digest. However as we can see from the block above, that is not the case.

 

---

 

Other things I've tried

Having read that EOS also uses balanced merkle-trees, and that in the case where there are an odd number of leaves, the final leaf is duplicated and concatenated with itself, I tried that.

So taking the action-digest of e6a5...c058 I made the two leaves by duplicating it then making one a canonical_left and the other a canonical_right (by setting or clearing the first bit):

• Left = 66a5...c058
• Right = e6a5...c058

But then concatenating them together and hashing resulted in 8742...44fc and so it still didn't work to get action_mroot of `7f3d...9928``.

 

What am I missing?

 

Answer 1

Unlike transaction_mroot (transaction_mroot is null when no trx is pushed to block), for calculating action_mroot, you should consider implicit action eosio::onblock which is added to block automatically. Block explorers usually omit onblock action from listing, but if you run full-node with history plugins like state_history_plugin or mongo_db_plugin, you can find the full list of actions including onblock.

Answer 2

Apparently, the vector<digest_type> action_digests defined in the EOS code here:

   checksum256_type calculate_action_merkle() {
      vector<digest_type> action_digests;
      const auto& actions = pending->_block_stage.get<building_block>()._actions;
      action_digests.reserve( actions.size() );
      for( const auto& a : actions )
         action_digests.emplace_back( a.digest() );

      return merkle( move(action_digests) );
   }

is the vector of the digests of the action_receipt and not of the action_digest. The action_receipt is defined here: https://github.com/EOSIO/eos/blob/7d210b387ce5ec9089ab31e9cc0e237bceb25622/libraries/chain/include/eosio/chain/action_receipt.hpp

struct action_receipt {
      account_name                    receiver;
      digest_type                     act_digest;
      uint64_t                        global_sequence = 0; ///< total number of actions dispatched since genesis
      uint64_t                        recv_sequence   = 0; ///< total number of actions with this receiver since genesis
      flat_map<account_name,uint64_t> auth_sequence;
      fc::unsigned_int                code_sequence = 0; ///< total number of setcodes
      fc::unsigned_int                abi_sequence  = 0; ///< total number of setabis

      digest_type digest()const { return digest_type::hash(*this); }
   };