This is a read note of Programming Bitcoin Ch04: Serialization. Keys and signatures need to be serialized to be transmitted over network or saved to disk.

1 SEC Format

Standards for Efficient Cryptography (SEC) is a standard for serializing ECDSA public keys. There are uncompressed format and compressed format.

Here is how the uncompressed SEC format for a given point P = (x,y) is generated:

  1. Start with the prefix byte, which is 0x04.
  2. Next, append the x coordinate in 32 bytes as a big-endian integer.
  3. Next, append the y coordinate in 32 bytes as a big-endian integer.

Unfortunately, some serializations in Bitcoin (like the SEC format x and y coordinates) are big-endian, while others (like the transaction version number are little-endian.

The two y coordinates of a public key has an odd number and an even nubmber that can be derived from its x value. Therefore, the serialization of the compressed SEC format for a given point P = (x,y):

  1. Start with the prefix byte. If y is even, it’s 0x02; otherwise, it’s 0x03.
  2. Next, append the x coordinate in 32 bytes as a big-endian integer.

The big advantage of the compressed SEC format is that it only takes up 33 bytes instead of 65 bytes.

To calculate the y, using the following steps:

  • calculate the right side of bitcoin curve: v = x ** 3 + b, then, y ** 2 = v.
  • bcause y ** 2 = y ** 2 * (y ** (p - 1)) = y ** (p + 1), then y = y ** ((p + 1)/2) => y = (y ** 2) ((p + 1) / 4) => y = v ** ((p + 1) / 4).

The p used in secp256k1 is divisible by 4, therefore, we can find a y. The other value of y is N - y.

2 DER Signature

The standard for serializing signature is called Distinguished Encoding Rules (DER).

DER signature format is defined like this:

  1. Start with the 0x30 byte.
  2. Encode the length of the rest of the signature (usually 0x44 or 0x45) and append. In decimal, it is 68 or 69 bytes.
  3. Append the marker byte, 0x02.
  4. Encode r as a big-endian integer, but prepend it with the 0x00 byte if r’s first byte ≥ 0x80. Prepend the resulting length to r. Add this to the result.
  5. Append the marker byte, 0x02.
  6. Encode s as a big-endian integer, but prepend with the 0x00 byte if s’s first byte ≥ 0x80. Prepend the resulting length to s. Add this to the result.

The rules for #4 and #6 with the first byte starting with something greater than or equal to 0x80 are because DER is a general encoding and allows for negative numbers to be encoded. The first bit being 1 means that the number is negative. All numbers in an ECDSA signature are positive, so we have to prepend with 0x00 if the first bit is zero, which is equivalent to first byte ≥ 0x80.

3 Base58 and Address

There are three major considerations for poeple to use the key or address values in bitcion. The first is that the public key be readable (easy to hand-write and not too difficult to mistake, say, over the phone). The second is that it’s short (not so long that it’s cumbersome). The third is that it’s secure (so it’s harder to make mistakes).

Base64 uses 6 bit per character. Removing six similar characters of 0, o, l, I, -, and _, there are 58 characters: BASE58_ALPHABET = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'. It is around 5.86 bits per character.

Bitcoin uses the following method to create addresses from public keys:

  1. For mainnet addresses, start with the prefix 0x00, for testnet 0x6f.
  2. Take the SEC format (compressed or uncompressed) and do a sha256 operation followed by the ripemd160 hash operation, the combination of which is called a hash160 operation.
  3. Combine the prefix from #1 and resulting hash from #2.
  4. Do a hash256 of the result from #3 and get the first 4 bytes. This is the checksum.
  5. Take the combination of #3 and #4 and encode it in Base58.

By not using the SEC format directly, we go from 33 bytes to 20 bytes, shortening the address significantly.

4 WIF Format

Wallet Import Format (WIF) is used to serialize private keys.

  1. For mainnet private keys, start with the prefix 0x80, for testnet 0xef.
  2. Encode the secret in 32-byte big-endian.
  3. If the SEC format used for the public key address was compressed, add a suffix of 0x01.
  4. Combine the prefix from #1, serialized secret from #2, and suffix from #3.
  5. Do a hash256 of the result from #4 and get the first 4 bytes.
  6. Take the combination of #4 and #5 and encode it in Base58.