Categories

[Little Brosers] PCB, Images, hash digests and flash memory

Hello everyone,

 

This week, and particulary this week-end have been quite intense. Let’s sum it up.

PCB : First hands-on and testing

We received our PCBs this week ! It was awesome to see it, like, for real, not only on my screen. We spent a day testing each component and all went beautifully well. We had a software issue with the external flash’s pins but somme google research solved it. We forgot to configure the pin used for SPI’s CS, which is used for NFC by default. We juste had to declare a preprocessor constant to remove the NFC from this pin.

 

Some pics :

 

Banana for scale

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

In case you wonder, our drop’s PCB roll very well and resists to battery pole inversion 🙂

Docker images

Finally, after weeks of procrastination about Docker, I finally took the time to make a precisely adapted image for each jobs of our CI. “Took the time” means 1 full night and one full day but at least we now have beautiful lightweight alpine/arch docker images for our jobs. Tests run way faster than before !

 

Hash digests

So, for the last weeks, I have been in charge of our merkle tree and for simplicity, I never implemented messages hash. I always used the first byte of the message’s payload to run our sub-sorting, first one being timestamp. Also I never took care of computing the nodes’s hash of our merkle tree. This was just not usefull for what I had to do.

However the project is progressing and we came to the point where we needed those hash digests. Thus during friday, I sat at a table with Chris and we reviewed together the hash code for the drop. At the end of the day, we ended up with the exact same code for computing code from simulation or from the drops. We just made sure to redirect the “#include”s to the appropriate header files.

This is going to be merged into master branch pretty soon.

 

External flash memory

Ok, this time, it’s simple : my whole week-end was dedicated to the external flash memory. Saturday I started from master with what Xavier had already written for it and started to build basic functions like a get_status() function allowing main() to read the status register of the flash and I spent the rest of the day reading the datasheet. Today was all about writing a full Little Brosers message to the flash. Knowing that a flash page is 528 bytes, we decided that our messaged would be 528 bytes long for the maximum length. The external flash memory has 8192 pages.

So to make a quick summuray of what I have learned:

The flash has two SRAM buffer of 528 bytes buffer. They are used to optimize writing and reading operation. In our case it is very usefull.

Indeed, the nrf52 SPI driver only allows SPI transfers up to 255 bytes(i.e. 251 bytes of payload, 4 bytes being used by the flash commandID and page/word address). We won’t be able to fill a full page with only one transfert, even if the flash allows it, the nrf doesn’t. I mean, we could force the sending of more than 255 bytes using nrf52’s SPI driver but it would require a heavy structure using nrf52’s timers and PPIs to make it possible. We don’t have time for such a complex thing. Instead, we chose the following procedure to write a msg in the page i using buffer1:

-> transform the message_t C struct into a byte array of size 528
-> write msg[0] to msg[250] in buffer1[0] for 251 bytes
-> write msg[251] to msg[501] in buffer1[251] for 251 bytes
-> write msg[502] to msg[527] in buffer1[501] for 26 bytes
-> push whole buffer1 to page i

 

The procedure for reading is quite similar except that we do not use the buffers. Indeed, we use the low power continuous array read on the page i three times (0->250, 251->501, 502->527).

 

It is 22h36 and for now, it “seems” that writing works fine, not so sure about reading. I’ll stop here for today, we’ll see tomorrow with a full night of recover. I’ll have to show it to my coworkers and see if they have any idea how to debug this part. I have to admit that it is not very easy since we still not fully master the NRF_LOG macro which is supposed to replace the usual printf() of the libc. It very often doesn’t actually print the characters I asked for; skipping some of them if the number of characters is too high. Even if I raise the RTT buffer size.

So for now, flash support is not reliable.

 

See you

 

Antony Lopez

[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