Directory / cardano-sl / hd.md

You are browsing a mirror of a file hosted on GitHub. View original

Cardano SL HD Wallets

The problem

When the user U creates a new wallet W, he is able to receive money from other users. To do it, U have to generate a new address A for his wallet W, after that other users will be able to send money to A.

Suppose other user sent 100 ADA to address A. Technically it means that new transaction was created, and this transaction will be a part of some block in the Cardano blockchain. Later, during synchronization with the blockchain, wallet W will find address A and since this address was generated by W, this money is owned by user U, so 100 ADA will be shown as a balance of wallet W.

The main problem is to prove that address A was generated by wallet W.

HD wallet

HD (Hierarchical Deterministic) wallet has hierarchical, tree-based structure. The root of this tree is a pair of user’s secret key RootSK and corresponding public key RootPK. RootSK is a key we obtain during creation of the wallet: by default RootSK is generating from 12-words mnemonic (or “wallet backup phrase”).

RootSK and RootPK are crucially important keys:

  • Wallet’s identifier is based on RootPK.
  • RootSK is using to derive new keys for generating new addresses from them (see below).
  • RootPK is using during synchronization with the blockchain to find out current balance of this wallet.

So, who owns the root keys - he owns the wallet and all its money.

Tree structure

In general case structure of the tree can be arbitrary, but currently we use two layered structure: nodes of the first layer are called “accounts”, nodes of the second layer are called “addresses” (you can think of them as leaves of the tree). Sometimes layer is called “level”. It can be represented like this:

          first            second
          layer/level      layer/level

Root --
       `- Account [0] --
       `                `- Address [0]
       `                `- Address [1]
       `                `  ...
       `                `- Address [M]
       `
       `- Account [1] --
       `                `- ...
       `  ...
       `- Account [N] --
                        `- ...

Each address belongs to one account. There can be potentially 2³² accounts (N is Word32 value) and each account can have 2³² addresses (M is Word32 value as well), so wallet can have 2⁶⁴ addresses in total.

Intuitively, balance of each account can be computed as a sum of balances of addresses which belong to it, and therefore balance of the wallet is a sum of balances of its accounts. The details are however much more subtle, please see the formal wallet specification.

Please note that current structure of the tree will change in some future: the number of layers will be increased.

Index and path

As was shown above, each node of the wallet tree has a unique index, it allows us to identify each node:

Root --
       `- Account A [0] --
       `                  `- Address B [0]
       `                  `- Address C [1]
       `
       `- Account D [1] --
                          `- Address E [0]
                          `- Address F [1]
                          `- Address G [2]

In this example address B has index 0, but address E has index 0 too. To identify address uniquely we specify full path from the root. This path is a list of node indexes, and since our tree is 2-layered, path contains indexes of account and address. Thus, address C has a path [0, 1] and address G has a path [1, 2].

Derivation, parent and child

To generate a new address for the wallet (addresses in HD wallet are called HD addresses), we have to obtain a new pair of secret/public keys and generate new address from it. HD wallet allows us to derive new pair of keys from the RootSK. Actually all the pairs of keys we need to generate all possible wallet’s addresses are derived from the RootSK. Let’s call such keys derived ones, dSK and dPK, so address B from the last example was generated from dSK_B, address E - from dSK_E and so on.

To specify relations between nodes of the wallet tree we define parents and children. Keys of the child node can be derived from keys of the parent node. So particular address is a child of the particular account, and all accounts are children of the root:

parent ......... child

Root keys --
            `--> Account [N] keys --
                                    `--> Address [M] keys

                 parent ................ child

That’s why full path from the tree root to the tree leaf (here it is [N, M]) is called “derivation path”: to derive child’s SK from parent’s SK we need not only parent’s SK, but child’s index (part of the path) as well:

deriveChildSK :: ChildIndex -> ParentExtSK -> ChildExtSK

Please note that ParentExtSK and ChildExtSK are extended keys. Extended key is a pair of ordinary key and special 32-bytes seed (it’s called “chain code”).

HD address payload

“Account” and “address” entities were mentioned, but only addresses appear in the blockchain. When we create a transaction, we specify destination address and coins for each output of transaction. So neither transaction or block knows anything about accounts and wallets.

We want to be able to track our addresses in the blockchain to compute our wallet balance (because money on our addresses is ours). To prove that particular address was generated by our wallet we need some special information stored in the address.

The idea is it: let’s store derivation path in the address. For example, when we derived a new dSK for the node with the path [12456, 10], let’s generate a new address A from dSK and store this path in the A. To hide this path from other parties we will encrypt it (see below). Eventually this serialized and encrypted derivation path we call HDAddressPayload becomes a part of the address. You can think of this payload as a secret stamp we put on all our addresses: everyone can see it but only we can read it. This corresponds to the current implementation, but it is going to change in some future.

To encrypt address payload we use a special passphrase we call HDPassphrase. We don’t need to store this passphrase because it can be derived from the RootPK (technically HDPassphrase is a HMAC-SHA512 hash of the RootPK).

So, during synchronization with the blockchain we take some address, extract encrypted payload from it and then try to decrypt it using our HDPassphrase. If it’s successfully decrypted then it proves that this address belongs to our wallet and, vice versa, address doesn’t belong to our wallet if decryption is failed.

After successful decryption of all our addresses we get whole hierarhy of the wallet tree because decrypted derivation paths describe it.

So now it’s obviously that if you share your RootPK - you give to anyone an ability to reveal all your addresses in the blockchain!

Transaction creation

Suppose that we derived dSK_A and generated a new address A from it. Some other user OU sent 100 ADA to the address A. Technically it means that OU created a new transaction T1 and its output O contains an address A and this amount.

Now we want to send these 100 ADA to another user AU. Technically it means that we have to create a new transaction T2 and its input I will refer to an output O of T1:

    T1               T2
+--------+       +--------+
|        |       |        |
|    +---+       +---+    |
|    | O |------>| I |    |
|    +---+       +---+    |
|        |       |        |
+--------+       +--------+

Now we must prove that we have a right to spend money from the address A (which is in O). To do it we must prove that address A was generated by our wallet (because if so, money on this address is ours and we obviously may spend it).

This is where derivation path helps us: since address A contains this path, we can take it and derive dSK_A and corresponding dPK. This is how we prove that address A is ours: only we could derive dPK, which means that only we could generate address A.

Now we have to create a witness for each input of transaction. A witness is our proof that we may spend money from corresponding address, it includes a signature S and public key PK:

  1. S is a signature of entire transaction (technically it’s a signature of the hash of the transaction),
  2. PK is a derived public key that corresponds to derived secret key which was used to generate our address.

In our example address A was generated from dSK_A, so witness for I will include:

  1. A signature of the transaction T2,
  2. Public key dPK_A that corresponds to dSK_A.

Please note: although we can reveal all wallet’s addresses just knowing RootPK of this wallet, to spend money RootSK is needed.

Formal specification

Please note that the purpose of this document is to provide a high-level overview of HD wallets. For technical details please read Formal specification for a Cardano wallet.