1
$\begingroup$


I've been reading some papers about using blockchain in VANETs (Vehicular Adhoc Networks).
Some of them have mentioned something called a chronological merkle tree (CMT). Is this different from the normal merkle tree? Here is a quote from one of them:

The chronological Merkle tree (CMT) is the underlying data structure of the conventional blockchain

this paper can be found here: Here

$\endgroup$
3
  • $\begingroup$ I presume that this is just a Merkle tree where the branches / leafs are chronologically ordered according to a point in time that is apparent from the data that was hashed. There must be a way to know which data is first when hashing anything, after all; an unordered set would be able to produce different hashes as you need to do some kind of ordering before you can start to hash. $\endgroup$
    – Maarten Bodewes
    Nov 5, 2019 at 14:36
  • $\begingroup$ @MaartenBodewes so for example we could say that the leftmost leaf is always the oldest (has an older timestamp) among other leafs? $\endgroup$
    – Abol_Fa
    Nov 6, 2019 at 11:51
  • $\begingroup$ Yeah, that was I meant, and hopefully also what was meant by VANET, but I don't know that protocol. $\endgroup$
    – Maarten Bodewes
    Nov 6, 2019 at 19:32

1 Answer 1

0
$\begingroup$

Let's assign indices to the leaves of the Merkle tree: from left to right we number the leaves $0$, $1$, $\ldots$, $2^n-1$, or 0000, 0001, ..., 1111 in binary. When we now walk from the root to a leaf, at each node 0 means taking the left branch and 1 means taking the right branch (when viewed from above).

Initially we have an empty tree. If we start adding elements, we need to insert them at some index (= at some leaf).

If we choose the the indices incrementally, we obtain a dense or chronological Merkle tree. There are only leaves on the left, all the leaves on the right are empty. This also means that there is a large empty subtree on the right.

If we choose the indices randomly, we obtain a sparse Merkle tree. Empty and non-empty leaves are randomly distributed across the tree.

$\endgroup$

Your Answer

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

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