[Little Brosers] The tree comparison protocol

This week I am going to describe the tree comparison protocol that the drops will be using with the smartphones to determine which message is missing to each device.


As mentioned in one of my previous posts, the general idea is that each device has a local stack of operations to keep track of what is the next step. In each element of the stack, there are three informations:

  • The type of the operation: either transmission or reception
  • The type of the transmission (only useful for transmissions)
  • The node of the Merkle tree associated with the operation, which we will call the associated node


Here are the three different types of transmissions and their meanings:

  • C, for children: “The hash you sent me is not equal to the one I have, here are the hashes of the children”
  • E, for equal: “The hash you sent me is equal to the one I have, we are stopping here for this subtree”
  • B, for bucket: “The hash you sent me is not equal to the one I have but we are at the end of the subtree (bucket of message) so here are the UUIDs of the messages I have in this bucket”


The type of the message will obviously define what the payload contains. After an initialization where one device sends its root hash to the other, we enter the standard behaviour of the protocol which goes as follow:


While the device’s stack of operation is not empty, we pop the first operation and look at its type.



If the operation is a transmission, we look at the type and build the message payload:

  • C: The hashes of the children of the associated node, add a reception associated with each child to the stack
  • E: Empty payload
  • B: The UUIDs of the messages in the bucket of the associated node


Once the payload is formed, the transmission is sent to the other device



If the operation is a reception, the device waits for the other device to send a message, then looks at its type and payload

  • C: Compares the hashes of the payload with the hashes of the children of the associated node. For each child, if the hash is equal add a transmission of type E associated with the child. If the hash is not equal, add a transmission associated with the child of type C (if the child is not a leaf) or of type B (if the child is a leaf)
  • E: Do nothing
  • B: Compare the UUIDs of the payload with the UUIDs of the bucket of the associated node. Detect which messages the device will have to send, and which messages the device will have to request.


This is what the python script simulates and the results have been pretty good so far, so we are pretty happy with that.


Next up is something quite different, I am going to catch up on the group’s work on Android and try to make the nrf52832 devkit dialog with the application. I also started to get myself into the Nordic SDK but this has proven to be quite difficult for now since there are a lot of librairies which are often not that great documented. Luckily there are a lot of examples si I am not completely lost.


Thank you for reading and see you next week !



Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>




This site uses Akismet to reduce spam. Learn how your comment data is processed.