coinZdense deep Dive: KDF-index-space allocation

Level Keys

index

Signing keys

---

KDF-index-space allocation

---

---

KDF and index-space

The libsodium key derivation functionality allows for the reproducible creation of subkeys from a master key, where both the master key and the sub-key are high entropy bytes of data. In our case, the master key is our actual low level private key underlaying our full-authority signing key. We will discuss the signing key in more detail in the next post, and to an extent below. This functionality provides us basically with a function that, given a single high entropy master key plus a 64 bit index, gives us up to 2^64 high entropy sub keys. If we have just one master key as our secret key, if we manage the indices right, like a resource, we end up with a 2^64 value index-space that we need to manage. The design of coinZdense pick an index-space allocation design inspired by computer memory. We will look at index-space as a memory model with a stack and a heap that we shall be growing our allocation in from two directions. Once index-space is exhausted, our key is considered exhausted as well. This is a design concept that I've found pretty difficult to explain to even the most intelligent reviewers, so far, and there is a bit of a chicken/egg problem explaining signing keys and explaining KDF-index-space allocation, so we are going to be discussing the hardest part first. If you get this part, understanding the rest of this series of posts should be peanuts.

Signing key level allocation of index space

At any point in time, a Signing-key will consist of two or more level keys. We refer to the highest level key as the Root Key, the lowest level key as the Transaction Key, and to any intermediate level keys as Intermediate Keys. There is always a root key and always a transaction key. The number of intermediate keys can be zero or more, up to a largish number not yet relevant for this description. In the image below, we have a root key (RK), a single intermediate key, and a single transaction key, each with a height of only three.

Note that there is already a divide, complicating our index-space allocation. The two images aren't the same key at different times, they are actually the same key at the same time. Why? Because signing transactions and deriving and signing attenuated-authority keys are operations that require a different amount of index-space. To get around this reality, as we discussed in our post on parameterization, our signing key as a whole has a chunk of its transaction signing space, the first chunk, reserved for deriving and signing attenuated-authority keys. In the top image, we see the higher level overview of the transaction signing allocation part. Below, a similar image for the attenuated-authority key part.

The root key can be used to sign up to eight intermediate keys. Each of these intermediate keys can be used to sign up to eight transaction keys and each of these transaction keys can be used to sign up to eight transaction OR derive and sign up to eight attenuated authority keys. Note that we are not pre-allocating anything, we are allocating as things become needed. We are though reserving a small chunk of index-space specifically for attenuated-authority key generation and signing.

Index-space stack abstraction

If we look at key-space allocation to the different building blocks of our design, for a large part we can look at index-space as a stack. Two stacks, actually, a small one and a large one. First we allocate the root key on the small reserved stack, then the 1st intermediate key. We don't allocate any intermediate key on the non-reserved part of the stack yet because this one is shared with the reserved part. Next, things spilt up. We allocate two transaction keys, one (TK0) on our reserved part of the stack for attenuated-authority key signing, and one, in this case TK5 on the non-reserved part of the stack.

Every time we create an attenuated-authority key, we allocate one salt and one link chunk. Every time we sign a transaction, we allocate just a salt.

When a transaction key gets exhausted, the index-space for a new transaction key is allocated on the appropriate stack and if needed, first for one or sometimes more new intermediate key too.

Please note that the blocks in this image are not to scale. an RK IK or TK allocation will in reality be many times bigger than a LNL or SLT allocation. We will look at this in more detail later in this post.

Index space heap abstraction and sub-authority index-space allocation

If you thought things were growing a bit complicated; we've seen nothing yet. As we've just seen, we have a stack within a stack, both growing up. The reserved mini stack has a fixed size. The larger stack as we will see now has not, as another allocation mechanism, as we create attenuated authority keys, is shrinking the remaining stack from the top down, potentially at one point in time competing for index space. This other side we look at as the index-space heap, conceptually. If you are asking yourself: Why don't derived keys get their own 64 bits of index-space? That is an excellent question, and the short answer is: revocation and wallet instance synchronization. I know the short answer raises only more questions, but today's post is complicated enough without the long answer to that question, so we delay the answer to that question to when we'll discuss the details of authority attenuation.

Basically, whenever you derive a key from an existing key, you also allocate a chunk of index-space for that derived key on the heap. That chunk of index-space, for the derived key, will be considered as the index space, and as such will get its own index-space stack, and possibly its own reserved stack area and its own heap as well.

In level-key index-space

As we have seen, there are a number of different high-level index-space allocation chunks:

1. Level key index-space allocation
2. salt index-space allocation
3. link index-space allocation
4. attenuated-authority subkey index-space allocation

Let's start discussing the level keys, that should be in the back of our minds already, as we discussed a lot about those in the previous post in this series. The simplest way to discuss level-key index-space allocation, is to write it out as a tree:

• Allocate 1 for lksalt
• For each of 2^height signatures this level key kan do:
  • For each of the otsbits chunks of bits needed to encode hashlength bytes:
    • Allocate 2, one for an up chunk OTS private key and one for a down chunk OTS private key

Number two is easy, salt index-space allocation takes exactly one index.

• Allocate 1 for tksalt

The third one, is quite simple too:

• Allocate 1 for the KDF function used to generate the master-key
• Allocate 1 extra, details will be discussed later.

The last one is a bit complicated. In short, allocation on the index-space heap is done explicitly, but with caveats. There is a minimum size flowing from key parameters that is non-negotiable. Competition between heap and stack is acceptable, but at the very least the allocated heap should be big enough to hold just the 100% filled up stack by itself given the key dimensions.

up next

This post is the most technical one and the most complicated one in the series. If you get this one, the rest of the series should be fine. Up next we'll look into the signing keys and you could give your brain a rest for a while till we get to authority decomposition and sub-key revocation.

Level Keys

index

Signing keys