Random Key Generation vs. Deterministic Key Generation (vs. Single Key Generation)

All Bitcoin wallet programs provide new users with at least one randomly generated Bitcoin address and private key. How and whether additional addresses are generated is a design choice that can incite very strong opinions among Bitcoin developers. The original Bitcoin wallet program assumed that users would never reuse an address after spending bitcoins from it. Every time a user wanted to spend bitcoins, a certain amount would go to the intended recipient, but the rest would be moved to a new, randomly generated Bitcoin address called the change address. This approach helps protect the privacy of the user, because it is more difficult for an external observer to track an individual's bitcoins if the person continually changes addresses. It's not possible to distinguish the transfer of bitcoins to a change address from the transfer of bitcoins from one person to another. Not everyone likes this behavior, though; some think it's easier to have just one Bitcoin address (like having one email address) and aren't as concerned about privacy. So some Bitcoin wallet programs provide only a single address that is continuously reused. These single key generation wallet programs allow you to generate additional addresses manually, but the default behavior is to reuse existing addresses.

Among the Bitcoin wallet programs that constantly generate new addresses, differences in implementation exist. Recall that a private key is a 256-bit integer that is usually generated by some random process. From the private key, Bitcoin wallet programs can calculate the associated public key (which is a point on an elliptic curve; see Chapter 7 for the cryptographic details), which in turn can be converted into a Bitcoin address by applying the RIPEMD[1] 60 and SHA256 hash functions. To generate a collection of private key/Bitcoin address pairs, many programs use correspondingly as many random numbers. This is known as random key generation. Every time a user needs a new Bitcoin address, a new random number is used as the private key. The drawback to this approach is that backups need to be updated regularly—essentially, every time a new address is created. This is particularly important to keep in mind in the context of change addresses. If you send some of your bitcoins to a friend and the remainder of your balance is sent to a newly generated change address, potentially the majority of your funds are no longer backed up! Some unfortunate incidents have occurred in Bitcoin's history in which users of random key generation-based wallets deleted or lost their wallets shortly after their funds were sent to a new change address but before they updated their backup.

An alternative approach is deterministic key generation. With this approach, only the first private key is a randomly chosen 256-bit integer, which is known as the master private key, and it has a corresponding master public key. Whenever the user needs a new Bitcoin address, a new private key is chosen that is related to the master private key by a simple mathematical relationship (no randomness is involved). In the simplest implementation, the master private key is simply incremented by 1 to generate a new key (e.g., if the master private key is the number 47, subsequent private keys would be 48, 49, 50, etc.). The advantage of this approach is that a single backup, created when a user first creates a new Bitcoin wallet, is sufficient and never needs to be updated.1 In fact, this is how Electrum works. Recall that in Chapter 2, Electrum prompted you to write down a 12-word mnemonic for backup purposes. That mnemonic was, in fact, a master private key.[2] All of the Bitcoin addresses in your Electrum wallet can be derived from this master private key.

Combining Deterministic Key Generation with Watch-Only Wallets

Imagine the following scenario:

• Lisa owns a restaurant that accepts Bitcoin.

• All the waiters in the restaurant have Bitcoin wallets on their phones to accept payments.

• Lisa wants to be the only person who can spend the money sent to these wallets.

Clearly, it would be very convenient if Lisa could set up this system, but it seems like it would be a technical challenge: Every waiter would need the ability to create tons of new Bitcoin addresses on demand in their wallets, yet Lisa still needs to be the only person with access to the private keys that power each wallet.

However, when you combine deterministic key generation with a watch-only wallet, this type of system is actually straightforward: Surprisingly, it is possible for a watch-only wallet (running on every waiter's phone) to create many new public keys arbitrarily without having any knowledge about the private keys associated with them!

This is all Lisa has to do:

1. Create public and private keys on her computer using deterministic key generation.

2. Give a public key to each waiter along with a program that supports a watch-only feature as well as deterministic keys.

3. Waiters can then accept as many payments with their wallets as they like.

4. Only Lisa can spend the money in these wallets using her computer's wallet. Her computer is the only computer able to generate the corresponding private keys for all Bitcoin transactions in the restaurant.

Whether you run a restaurant, a bank, or any other business, having a payment mechanism whereby your employees can arbitrarily accept payments from customers but only you, the owner of the business, can unlock the money is a powerful feature.

The Math Behind Deterministic Key Generation with Watch-Only Wallets

So how is it mathematically possible to generate new keys using only public key information? To explain, we'll refer to the cryptography on how private keys and public keys are mathematically related. In Chapter 7, we explained that given a secret private key, d (let's call this a master private key), the corresponding (master) public key, Q, is determined by the point multiplication operation:

Recall that both G and Q are points on the elliptic curve, but that G is publicly known to everyone and is a hard-coded constant in the Bitcoin protocol (whereas Q is unique to you). The master Bitcoin address is then derived from Q using several hash functions and other formatting.

The obvious way to deterministically generate a new Bitcoin address is to first choose a new private key, dnew= d + 1, and then calculate the corresponding new public key, Qnew:

However, this method of generating a new public key requires you to know the master private key. So what if you don't know the master private key? Could you generate a new Bitcoin address with only the knowledge of a master public key? Yes!

We can rewrite the equation for Qnew as follows:

Observe that the term dG can be rewritten as the master public key, Q:

As a result, we can calculate new public keys using only the knowledge of the master public key and the public constant G. Additional public keys can be generated by adding any number of G points:

Of course, a danger of the deterministic key generation approach is that if your master private key falls into the wrong hands, all of the derived Bitcoin addresses would be compromised. Also, from a privacy standpoint, if someone sees your master public key (which becomes public information once you send bitcoins to the corresponding address), that person can derive your subsequent public keys in an attempt to track your spending.

Although we won't delve into the mathematical details, deterministic key generation allows for another, even more advanced Bitcoin wallet feature, hierarchical deterministic wallets, that may appeal particularly to large organizations. The master private key can be branched into sub-master keys, which can be further branched into sub-submaster keys and so on. Each has a property that allows any key at one level to access the bitcoins held at every level below it. For example, a bank manager may hold a level-two private key (the level-one key is held by the CEO), and his staff may each hold level-three keys. Everyone shares the same hierarchical wallet, but the manager has access to his own funds and those of his staff, and the staff can access only their own accounts. Hierarchical deterministic wallets might also be useful for families in which the parents want to give their children bitcoins but maintain access as well.

  • [1] An important exception is if the user imports a randomly generated private key (perhaps from a paper wallet) into his deterministically generated Bitcoin wallet. In this case, a new backup needs to be created because the imported key cannot be derived from the master private key.
  • [2] The 12-word mnemonic is just one of an infinite variety of ways to encode a 256-bit integer. You can encode an integer in binary, hex, ASCII letters, lines of poetry, or ice cream toppings.
 
< Prev   CONTENTS   Next >