This is a read note of Mastering Bitcoin Chapter 04: Keys and Addresses.

1 Introduction

Ownership of bitcoin is established through digital keys, Bitcoin addresses, and digital signatures. The digital keys are not dependent on the Bitcoin protocol/network, but are instead created and stored by users in a file, or simple database, called a wallet. Keys enable many of the interesting properties of bitcoin, including decentralized trust and control, ownership attestation, and the cryptographic-proof security model.

  • The digital signature used to spend funds is also referred to as a witness, a term used in cryptography.
  • In the payment portion of a bitcoin transaction, the recipient’s public key is represented by its digital fingerprint, called a Bitcoin address. In most cases, a Bitcoin address is generated from and corresponds to a public key. However, not all Bitcoin addresses represent public keys; they can also represent other beneficiaries such as scripts

2 PKI

Since the invention of public key cryptography in 1970s, several suitable mathematical functions, such as prime number exponentiation and elliptic curve multiplication, have been discovered. Bitcoin uses elliptic curve multiplication as the basis for its cryptography.

In bitcoin, we use public key cryptography to create a key pair that controls access to bitcoin. The key pair consists of a private key and—​derived from it—​a unique public key. the public key can be calculated from the private key. The public key is used to receive funds, and the private key is used to sign transactions to spend the funds.

A bitcoin wallet contains a collection of key pairs, each consisting of a private key and a public key. The private key (k) is a number, usually picked at random. From the private key, we use elliptic curve multiplication, a one-way cryptographic function, to generate a public key (K). From the public key (K), we use a one-way cryptographic hash function to generate a Bitcoin address (A). The k -> K -> A is a one way process, the reverse functions of A -> K and K -> k are computationally impossible.

2.1 Private Key

The bitcoin private key is just a number. You can pick your private keys randomly using just a coin, pencil, and paper: toss a coin 256 times and you have the binary digits of a random private key you can use in a bitcoin wallet. The public key can then be generated from the private key.

The first and most important step in generating keys is to find a secure source of entropy, or randomness. Creating a bitcoin key is essentially the same as “Pick a number between 0 and n-1 where n is 1.1578 * 10 ** 77, slightly less than 2**256.” Bitcoin software uses the underlying operating system’s random number generators to produce 256 bits of entropy (randomness). In programming terms, this is usually achieved by feeding a larger string of random bits, collected from a cryptographically secure source of randomness, into the SHA256 hash algorithm, which will conveniently produce a 256-bit number. If the result is less than n, we have a suitable private key. Correct implementation of the CSPRNG (cryptographically secure pseudorandom number generator) is critical to the security of the keys.

2.2 Public Key

The public key is calculated from the private key using elliptic curve multiplication, which is irreversible: K = k * G, where k is the private key, G is a constant point called the generator point, and K is the resulting public key. The reverse operation, known as “finding the discrete logarithm” - calculating k if you know K — is as difficult as trying all possible values of k, i.e., a brute-force search.

Elliptic curve multiplication is a type of function that cryptographers call a “one-way” function: it is easy to do in one direction (multiplication) and impossible to do in the reverse direction (“division”, or finding the discrete logarithm). Elliptic curve cryptography is a type of asymmetric or public key cryptography based on the discrete logarithm problem as expressed by addition and multiplication on the points of an elliptic curve.

Bitcoin uses a specific elliptic curve and set of mathematical constants, as defined in a standard called secp256k1, established by the National Institute of Standards and Technology (NIST). The secp256k1 curve is defined by the following function, which produces an elliptic curve: y ** 2 mod p = (x ** 3 + 7) mod p, where p = 2 ** 256 – 2 ** 32 – 2 ** 9 – 2 ** 8 – 2 ** 7 – 2 ** 6 – 2 ** 4 – 1, a very large prime number.

Because this curve is defined over a finite field of prime order instead of over the real numbers, it looks like a pattern of dots scattered in two dimensions, which makes it difficult to visualize. However, the math is identical to that of an elliptic curve over real numbers.

3 Bitcoin Addresses

A Bitcoin address is a string of digits and characters that can be shared with anyone who wants to send you money. Addresses produced from public keys consist of a string of numbers and letters, beginning with the digit “1”. Here’s an example of a Bitcoin address: 1J7mdg5rbQyUHENYdx39WVWK7fsLpEoXZy.

The algorithms used to make a Bitcoin address from a public key are the Secure Hash Algorithm (SHA) and the RACE Integrity Primitives Evaluation Message Digest (RIPEMD), specifically SHA256 and RIPEMD160. Starting with the public key K, we compute the SHA256 hash and then compute the RIPEMD160 hash of the result, producing a 160-bit (20-byte) number: A = RIPEMD160(SHA256(K)).

To convert data (a number), we first add a prefix to the data, called the “version byte,” which serves to easily identify the type of data that is encoded. For example, in the case of a Bitcoin address the prefix is zero (0x00 in hex), whereas the prefix used when encoding a private key is 128 (0x80 in hex).

Next, we compute the “double-SHA” checksum, meaning we apply the SHA256 hash-algorithm twice on the previous result (prefix and data): checksum = SHA256(SHA256(prefix+data)).

From the resulting 32-byte hash (hash-of-a-hash), we take only the first four bytes. These four bytes serve as the error-checking code, or checksum. The checksum is concatenated (appended) to the end. The result is composed of three items: a prefix, the data, and a checksum.

This result is encoded using “Base58Check”, which uses 58 characters (a Base58 number system) and a checksum to help human readability, avoid ambiguity, and protect against errors in address transcription and entry. Base58 is a subset of Base64, using upper- and lowercase letters and numbers, but omitting four characters (0, O, l, I) that are frequently mistaken for one another and can appear identical when displayed in certain fonts.

Base58Check is also used in many other ways in bitcoin, whenever there is a need for a user to read and correctly transcribe a number, such as a Bitcoin address, a private key, an encrypted key, or a script hash. The prefix tells the data type. For example, 1 for Bitcoin address, 3 for script address, m or n for Testnet address, 5, K or L for privaite key Wallet Import Format(WIF), 6P for BIP-38 encrypted private key, xpub for BIP-32 extended public key.

4 Key Formats

Private keys can be in four formats: Raw, Hex, WIF and WIF-compressed.

the public key is a point on the elliptic curve consisting of a pair of coordinates (x,y). It is usually presented with the prefix 04 followed by two 256-bit numbers: one for the x coordinate of the point, the other for the y coordinate. The prefix 04 is used to distinguish uncompressed public keys from compressed public keys that begin with a 02 or a 03. To distinguish between the two possible values of y, we store a compressed public key with the prefix 02 if the y is even, and 03 if it is odd, allowing the software to correctly deduce the y coordinate from the x coordinate and uncompress the public key to the full coordinates of the point.

The term “compressed private key” really means “private key from which only compressed public keys should be derived,” whereas “uncompressed private key” really means “private key from which only uncompressed public keys should be derived.” You should only refer to the export format as “WIF-compressed” or “WIF” and not refer to the private key itself as “compressed” to avoid further confusion.

If a bitcoin wallet is able to implement compressed public keys, it will use those in all transactions.

5 Advanced Keys and Addresses

5.1 P2SH

Bitcoin addresses that begin with the number “3” are pay-to-script hash (P2SH) addresses. They designate the beneficiary of a bitcoin transaction as the hash of a script, instead of the owner of a public key. The feature was introduced in January 2012 with BIP-16.

A P2SH address is created from a transaction script, which defines who can spend a transaction output. Encoding a P2SH address involves using the same double-hash function as used during creation of a Bitcoin address, only applied on the script instead of the public key: script hash = RIPEMD160(SHA256(script)). The resulting “script hash” is encoded with Base58Check with a version prefix of 5, which results in an encoded address starting with a 3.

Currently, the most common implementation of the P2SH function is the multi-signature address script. As the name implies, the underlying script requires a minimum number of signatures to prove ownership and therefore spend funds. The bitcoin multi-signature feature is designed to require M signatures (also known as the “threshold”) from a total of N keys, known as an M-of-N multisig, where M is equal to or less than N.

5.2 Vanity Address

Vanity addresses are valid Bitcoin addresses that contain human-readable messages. For example, 1LoveBPzzD72PUXLzCkYAtGFYmK5vYNR33 is a valid address that contains the letters forming the word “Love” as the first four Base58 letters. Vanity addresses require generating and testing billions of candidate private keys, until a Bitcoin address with the desired pattern is found. Vanity addresses can be used to enhance and to defeat security measures.