System basics, Keys, and Addresses

System basics

The ownership and transfer of coins are specified by digital keys, addresses, and digital signatures. The Bitcoin protocol relies on public-key cryptography in order to create a corresponding pair of a private key $d$ and a public key $Q$ for access control and to provide the ability to generate digital signatures. More precisely, the Bitcoin protocol uses elliptic curve cryptography based on the elliptic curve secp256k1, which is specified by Certicom. Each user occupies their own database, called a Bitcoin wallet, which contains a collection of corresponding key pairs, whereas a valid Bitcoin address is a hash of the public key. Each user is allowed to generate as many keys and addresses as they want. An owner of a private key that corresponds to funds on the public ledger can spend the funds to an address of any recipient by signing a transaction.

Keys and addresses

In this section, we introduce Bitcoin’s key and address creation. The Bitcoin protocol uses the Elliptic Curve Digital Signature Algorithm (ECDSA) based on the $secp256k1$ curve.

The $secp256k1$ private key $d$ is a randomly selected 256-bit (32-byte) unsigned integer $d \in[1, n-1]$, where $n=\# E\left(\mathbb{F}_{p}\right)$ is the order of the elliptic curve. The secp256k1 public key $Q$ is then derived from the private key $k$ by $d P=Q=\left(x_{0}, y_{Q}\right)$, where $P$ is the specified basepoint and the coordinates $x_{Q}$ and $y_{Q}$ are two 256 -bit integers. Since the public key is deterministically derived through a one-way function from the corresponding private key, the public key doesn’t need to be stored in the protocol. The public key $Q$ is represented in a compressed format $\bar{Q}$, where the compressed key is $33$ bytes long and only consists of the coordinate $x_{Q}$, including a constant prefix either of $0$x$03$ if the $x_{Q}$ coordinate is odd, or $0$x$02$ if the $x_{Q}$ coordinate is even.

In early versions of the Bitcoin protocol, the address was represented by the public key Q. However, Bitcoin changed this and is now using the hash of the public key $Q$ as an address instead of the public key itself. This selection wasn’t made intentionally because of security reasons, but rather to save memory space. However, as we’ll see later, this choice yields an advantage for quantum security. So, a Bitcoin address is, roughly speaking, a representation of the $Base58$ encoded cryptographic hash of the compressed ECDSA public key, computed according to Algorithm 8.

The compressed ECDSA public key $\bar{Q}$ is hashed twice, first using $SHA256$, which produces a hash of 256 bits (32 bytes), and then RIPEMD160, which produces a hash $h_{1}$ of 160 bits (20 bytes). According to Franco (2014)Pedro Franco. Understanding Bitcoin: Cryptography, Engineering, and Economics. The Wiley Finance Series. New York, NY, 2014. Wiley., the second hashing is only done to reduce the size of the address in order to save memory space. In the next step, a prefix $0$x$00$ is added in front of the hash value $h_{1}$. Next, a checksum is computed by applying the double-SHA256 hash to $h_{1}$, whereas only the first four bytes of the resulting 32-byte (256-bit) hash are kept to serve as error-checking code, which is then concatenated to the end of $h_{1}$. The final result is then encoded with $B a s e 58$, a binary-to-text encoding protocol that computes binary data to a readable text format in order to generate a compact and easy-to-read address.

---

Algorithm 8: Bitcoin address generation

---

Required: Compressed public key $\bar{Q}$.

1. $h_1 = \text{RIPEMD160(SHA256(}\bar{Q}))$.
2. $a = 0x00 \| h1$.
3. $h_2 = \text{SHA256(SHA256(}a))$
4. $A = \text{Base58(}a \| h2 [ 31 : 28])$
5. Return Bitcoin address A.

---

Implementation

Note: The code will take a long time the first time we execute it, but it will run smoothly after that.