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:
- Start with the prefix byte, which is
0x04. - Next, append the x coordinate in
32bytes as a big-endian integer. - Next, append the y coordinate in
32bytes 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):
- Start with the prefix byte. If y is even, it’s
0x02; otherwise, it’s0x03. - Next, append the x coordinate in
32bytes 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), theny = 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:
- Start with the
0x30byte. - Encode the length of the rest of the signature (usually
0x44or0x45) and append. In decimal, it is68or69bytes. - Append the marker byte,
0x02. - Encode
ras a big-endian integer, but prepend it with the0x00byte ifr’s first byte ≥ 0x80. Prepend the resulting length tor. Add this to the result. - Append the marker byte,
0x02. - Encode
sas a big-endian integer, but prepend with the0x00byte ifs’s first byte ≥ 0x80. Prepend the resulting length tos. 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:
- For mainnet addresses, start with the prefix
0x00, for testnet0x6f. - Take the SEC format (compressed or uncompressed) and do a
sha256operation followed by theripemd160hash operation, the combination of which is called ahash160operation. - Combine the prefix from
#1and resulting hash from#2. - Do a
hash256of the result from#3and get the first4bytes. This is the checksum. - Take the combination of
#3and#4and encode it inBase58.
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.
- For mainnet private keys, start with the prefix
0x80, for testnet0xef. - Encode the secret in 32-byte big-endian.
- If the SEC format used for the public key address was compressed, add a suffix of
0x01. - Combine the prefix from
#1, serialized secret from#2, and suffix from#3. - Do a
hash256of the result from#4and get the first4bytes. - Take the combination of
#4and#5and encode it in Base58.