Categories
IOTA

IOTA on the Ledger Nano S: Development Report 2

A good afternoon! I’m sitting here in front of family and friends who are playing Monopoly, waiting for the clock to hit 00:00. A new year will start. I’m also celebrating this yearly event, maybe a little different than I usually would, but in all honesty, I’m pretty damn happy about what I’m going to share with you, probably even more than if I did play along with them 🙂

Before we dive into the action again, I want to shed some light on the past 6 months. These 6 months, have been, in one word: Marvelous. It was the time I entered the IOTA community. During this time, so many things have happened. I cannot sum it all up in this post. Really, before I encountered IOTA, I had this year all planned out, I was working on a digital marketing company (it’s more exciting than it sounds) and will proceed to launch and raise funds during the end of this year.

But my focus totally shifted after finding out about IOTA. The level of excitement was simply too high to let this one slide. It was like when I first encountered Bitcoin in 2011. I just mailed some people from IOTA and joined their slack. I asked what I could do, it didn’t matter what, I just had to join in on this one.

From that point on, it brought me so many things. I was fortunate enough to work with Dom, Paul, Lewis and Chris on IOTA Flash, after my first IOTA talk and the first official meetup, I had so many offers that I couldn’t even react to them all! Of course, I had my ups and downs, but learning and growing doesn’t always have to feel good, what matters is what you let these experiences turn yourself into.

I also learned a freaking lot. I taught myself coding from 13y/o and never stopped since then. The same thing happened with machine learning 3 years ago. This year, the same happened with cryptography and math. I am a total noob when it comes to math, but I started a math course on EDx and learned myself the concepts of how crypto and math works and how you can apply it in real life. Not even Bitcoin got me to learn those things. All of this in just 6 months!

So, thanks a lot to the IOTA team, the community, and all the people I worked with on IOTA related projects, for being patient and give the energy and strength to people who are willing to contribute to something they believe in. And another huge thanks for bringing me the best year ever. I hope to make a great next 10 years out of that!

But what about the Ledger?

Enough with the chit-chat! I have to say: I wanted to post more, but I just really like to make 1 more post just before the end of the year 🙂

2 weeks ago we created a system to store 4 trits in 8 bits, requiring 25% of the memory originally required. If you want to know how, see the previous post of this series: https://codebuffet.co/2017/12/10/iota-on-the-ledger-nano-s-development-report-1/

Today my plan was to do 2 things:

  • Port Kerl (IOTA’s hashing function) and the conversion functions (trit to word etc) to use the ternary store instead of raw integers (to save 75% of RAM)  [done 100%].
  • Implement the private key generator and see if we can create our private keys based on the seed [done 80%, see below]

Unfortunately, even after the 75% ram optimization, we still didn’t have enough memory to create the private key. We could store the first half of the private key at the PC during the key creation, but that info is obviously sensitive. We also could apply an encryption format to make sure that the PC can’t read the contents it is temporarily saving. That’s quite overkill, and should be avoided, yet considered when we have no options or memory left.

Fortunately a reddit user called ‘0x1A9E’ created this comment: https://www.reddit.com/r/Iota/comments/7ixgfm/decided_to_write_a_journal_about_iota_on_ledger/dr31kt5/

It shows us not how to store 4 trits in 8 bits, but 5! The memory required to store the private key is 13.122kb. The Ledger only has 4kb for app use. With my optimization we require 3.2805kb, which leaves rarely any memory for the rest. With 0x1A9E’s solution we would have enough with 2.6244kb, which is already much more doable!

I wanted to leave this optimization in the backlog, as with 4 trits in 8 bit we might already have enough, but I think it’s better to start using the 5 trits in 8 bit solution right away. The very good thing is that if we solve the private key generation, we have successfully implemented the hardest part (as far as I can tell, as it requires the most RAM).

Right now, I extended 0x1A9E’s solution to add an inversion function (to convert trits back to integers, see: (https://github.com/peterwilli/iota-ledger-nano-s/blob/2241ceb2230ecc89b3b486f5210309cabbeabbd0/external_tests/5trit_store/test.py#L1) which is required to change trits on the go.

So next up will be the actual implementation of the function mentioned above in C (will do probably tomorrow).

If you’re a developer or just like to see the insides of these updates, they are not posted (yet) on the master branch, but on a special branch, for as long as we progress with this (this is to avoid unexpected breaks in the software). All the related updates to this post are at: https://github.com/peterwilli/iota-ledger-nano-s/tree/private-key-generation

Wrapping up

Would you like to donate or just say hi? Be sure to comment in this post below, or donate IOTA  at: ADLJXS9SKYQKMVQFXR9JDUUJHJWGDNWHQZMDGJFGZOX9BZEKDSXBSPZTTWEYPTNM9OZMYDQWZXFHRTXRCOITXAGCJZ

There is also a group forming a crowd-funding on Reddit at: https://www.reddit.com/r/Iota/comments/7l5jl2/and_if_will_we_donate_1miota_each

Would you like to contribute as a dev? You can by checkout the 5 trits per 8 bit function mentioned above and re-implement it in C in the ternary store (see: https://github.com/peterwilli/iota-ledger-nano-s/blob/2241ceb2230ecc89b3b486f5210309cabbeabbd0/blue-app-iota/src/ternary_store.c). If you do, please contact me on Github, so I won’t redo all the work when I get at it again 🙂

Now I’m going to celebrate a happy new year, and you should too! Happy new year!

Categories
IOTA

IOTA on the Ledger Nano S: Development Report 1

Hi guys,

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:

[su_table]

Bits Trit
00 0
10 -1
01 1

[/su_table]

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’.

Wrapping up

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.