I’ve barely slept since the picture I posted with the random IOTA seed on the Ledger (https://www.reddit.com/r/Iota/comments/7iaf3x/as_night_covers_the_netherlands_ive_been_able_to). It was overwhelming and it gave me a lot of energy. Today, I’d like to try something new. Because of all the reactions, I’d like to take you along the journey. That is, if you guys like it, it’ll be a series of posts during the development cycle. Don’t be afraid to give any feedback, and also let me know if you like the series to be more or less technical next time.
Before we get into the action, let me take a moment to explain what exactly happened and why it drove me to do this. Everyone knows the IOTA price has grown a lot over the past week. This also gave me a different feeling.
I don’t hold a lot of money in cryptocurrencies (or, I think it’s not a lot) but I do hold a lot of different ones. A few days ago I got my Ledger Nano S from a good friend and he told me I should stash my crypto’s on it and make sure that if something where to happen to me, my family could regain the funds. A healthy thought. After finding out IOTA wasn’t working at the moment on the Ledger, the first thing that came up to me was: make it work!
So, in all honesty, I’m by no means an expert in C, embedded hardware, or the Ledger in general. I am, however, a very fast learner. During the first days of that week, all I did was digesting information until I understood it all, especially on the specs of the ledger and the SDK. This is basically how I taught all my skills in development.
After that, I made a list of priorities, so that, even if a part of the list is completed, we will be able to store our IOTAs (and I would be able to store mine). It was something in the sense of:
- Generate valid IOTA seeds based on your Ledger seed.
- Generate valid addresses based on that seed
- Note that if this is complete, we can already store IOTA.
- Allow transactions to be made
At thursday december 7th, around 12:30 in the night, I was able to fully execute IOTA’s hashing algorithm on the Ledger, resulting in valid seeds. I was so excited by this, especially because it worked at once. I decided to post a picture and go to bed. So I turned on my laptops webcam, made a pic and posted it, and at the moment I closed my laptop, not much than 3 minutes later, reactions streamed in, hundreds of them. I couldn’t believe it. I really didn’t know it was that big of a deal. The main motivation that drove me was to make sure my funds were safe and that my family would know how to recover it in case of a sudden death. What happened after that, was, well, definitively not sleep 🙂
Back to the present
After all the fuss I didn’t stop, I worked harder. So the next big thing we needed was generating private keys and then addresses. So, I got started at the beginning, and did the thing that made most sense, it was just copying the address generator from the Trezor version of the IOTA wallet. And the Ledger stalled. This is not a surprise to me, because the memory in the Trezor is much more than the Ledger (Trezor has 128kb ram, and the Ledger has “only” 4Kb ram available for applications)
Having so little memory poses a significant challenge, but it’s exciting too. It forces you to think very differently. If it weren’t for IOTA or Ledger, I’d probably wouldn’t have been sitting in a cinema with a pen and paper thinking how to squeeze as much data in 4kb of RAM.
These are the workarounds we have (sorted by most preferable):
- Rewriting functions to use less memory
- Use the connection with the computer to store part of the data externally
- Store a part of the data in flash-memory
So, I started opening up the source code of the Trezor-IOTA firmware, checking out every function that has been called from the private key generation, and while reading it, thinking about how to use less RAM to do the same thing.
One thing that caught my eye instantly, is the way trits are stored. For newcomers, trits are IOTA’s entire base. Instead of having bits, which is 0 and 1, IOTA has trits, which are -1, 0 and 1. The whole reasoning behind this is because a ternary processor would be able to handle IOTA much more efficiently, even more efficiently than a binary processor would be able to handle binary applications.
Trits are being stored in the smallest possible number in C. This is int8_t. This number can hold 256 different values, and takes 8 bits of memory. So that means, that for each trit we need to occupy 8 bits of memory. If you think about it, that’s quite a lot, as trits only need 3 different states.
So, knowing that we can’t store numbers smaller than 8 bit, and that a trit only needs 3 different values, the first thing that came in mind was, can we squeeze more than 1 trit in a 8-bit number? It turns out, we can!
Let’s take a look at the memory space of a 8bit number: 00000000
So 8 zeroes. Each zero can also be 1.
So, after a bit of thinking and writing notes, I came up with the following idea: 1 bit has 2 states, so with 2 bits we have 4 states. 1 trit has 3 states, which means that it fits well within the 2 bits. Now we just need to ‘map’ the 2 bit states to a single trit-state. It looks something like this:
Now we can store 1 trit in each 2 bits. Because we have 8 bits in 1 number, that means we can store 4 trits in 1 number!
Using ‘chains’ of these 8bit numbers, we can store lots (in the thousands) of trits, with only 25% of the memory currently required! This is math porn.
For the techies, the source to the ‘ternary store’ is here: https://github.com/peterwilli/iota-ledger-nano-s/blob/master/blue-app-iota/src/ternary_store.c
All we need to do now, is, finding the right number a trit is stored, given an index of a trit you’d like to retrieve, and then finding the right position within that number. For this I have created a function called ‘ternary_store_get_position’.
While the ternary store is not yet tested on the Ledger (I did tests with storing 1000’s of random trits and it worked all the time), I’m very confident that it will bring us one step closer to full IOTA on Ledger. More optimizations will have to be done, but we will get there.
After the first announcement of this project, other people joined too. So we get contributions to the project rolling in right now. I also joined the Ledger dev Slack to coordinate and discuss IOTA development on the Ledger as we progress as a community. So there is a lot happening in the scene, and I’m very confident we’ll have a strong community behind this in no-time.
Right now I’m going to take a break and regain some sleep, and make sure I stay focused on my other projects.
If you want to contribute to further development, IOTA donations are accepted at: ADLJXS9SKYQKMVQFXR9JDUUJHJWGDNWHQZMDGJFGZOX9BZEKDSXBSPZTTWEYPTNM9OZMYDQWZXFHRTXRCOITXAGCJZ
I’d like to thank IOTA as a community once more. Thanks to you guys I’m exploring all these new things and have fun doing it. This is literally the most fun thing I did in the weekend (it probably is the only thing, though).
I also like to thank the Ledger team who is very helpful and involved. I’m very glad having them watching and giving their feedback.
And a huge shoutout to Bart Slinger, who made the Trezor version (see: https://www.bartslinger.com/iota/iota-transactions-with-trezor-hardware/). Thanks to his contributions, I had a head-start, and was able to focus on heavy memory optimizations like the Ternary store. Without his help, I would’ve been busy a lot longer.