Categories

[Little-Brosers] Merkle trees

Hello everyone, this is Guillaume from the Little Brosers group.

 

We started this week working collectively by trying to estimate the key numbers of our project like memory size of our data, average and peak consumption, the rates needed at various interfaces… I’m not going to lie, this was a bit puzzling since we have a huge chunk of theoretical work to do before being able to correctly evaluate these things. However, the fact that we tried meant that even though our evaluations have turned out to be mostly approximations, our vision of the projects greatly advanced. We were able to take the decisions concerning the cryptographic algorithms we are going to use, our preliminary message structure, and I then started the works on the Merkle tree.

 

The Merkle tree structure will define how a drop and a phone can efficiently identify the messages they are missing from each other.

For those not familiar with it, a Merkle tree is something quite simple yet efficient used for example in P2P protocols to easily identify which data chunk is missing from users. The way it works is the following: each leaf represents a data chunk hashed using one’s favorite hash function. Then, each node is built by hashing concatenation of the children’s hashes. Two parties can then quickly identify what piece of information they have in common and what piece of information differs by comparing their Merkle tree. The comparison stars by the root, and if it is different, the children of the root are then compared etc… The comparison of a branch stops when you find two equal hashes or you reach the leaf, identifying a data block you’re missing.

 

Most classical examples of Merkle trees are binary trees, however in our case the tree will be n-ary, where n will be defined by the max number of hashes we can send over bluetooth in a single message, for energy efficiency purposes. The hash are most likely going to be md5, therefore 16 bytes long. The values we found for the max bluetooth payload in 4.2 are around 200 bytes, however we do not know how our payload will be when we really get our hands on the actual PCB. While we are still looking into bluetooth specs to determine which n we are going to use, i took 4 as reasonable example to start working on it while the rest of the group can continue their research.

 

One of the challenges was that we want to build our Merkle tree around chronological ordering of messages, where each node represents a time frame. However, our system will most likely not even keep track of time since it would be a waste of energy. What we decided to do was to implement a certificate signed by the server and delivered daily to all users, most likely at the same time everyday, certifying the current time. When a user encounters a drop during handshake there will be a phase where each party agrees on what time is “now” and recalculate its Merkle tree if needed. That way, a drop will at most have to recalculate their Merkle tree once every 24 hours + every time they receive new messages.

 

Since the agreement of what is considered “now” is the only agreement between the two parties before comparing trees, the next challenge was to think of the actual Merkle tree model to be used. I will skip on the details since the model is still prone to change in the next few days, but hopefully my next week post will be done once the tree structure and comparison protocol is formalised. I will then explain the choices made and think worst case scenarios.

That is what my next week will be: formally put on paper what I am currently thinking the Merkle tree comparison process will be, as well as update the first draft of the Merkle tree model. Once it is done, I will try to formally prove that the algorithm does the work, and try to look into worst case scenarios to ensure the process will still be reasonable in unusual cases.

 

For the moment, here is the draft of how a Merkle tree will be built. The is a small mistake in the placement of Message 14. The +6/+12 node should not have been subdivided since there is only one message inside. Message 14 should have been put directly inside the node. The formal rules will be available on our wiki most likely during next week (I do not know if the readers outside of Telecom have acess to it though, if not and some people are interested we will find another solution).

 

 

Thanks for reading, cheers, and see you next week,

Guillaume

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>