Chapter 4. Serialization

We’ve created a lot of classes thus far, including PrivateKey, S256Point, and Signature. We now need to start thinking about how to transmit these objects to other computers on the network, or even to disk. This is where serialization comes into play. We want to communicate or store a S256Point or a Signature or a PrivateKey. Ideally, we want to do this efficiently, for reasons we’ll see in Chapter 10.

Uncompressed SEC Format

We’ll start with the S256Point class, which is the public key class. Recall that the public key in elliptic curve cryptography is really a coordinate in the form of (x,y). How can we serialize this data?

It turns out there’s already a standard for serializing ECDSA public keys, called Standards for Efficient Cryptography (SEC)—and as the word “Efficient” in the name suggests, it has minimal overhead. There are two forms of SEC format that we need to be concerned with: uncompressed and compressed. We’ll begin with the former, and look at the compressed format in the next section.

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 32 bytes as a big-endian integer.
Next, append the y coordinate in 32 bytes as a big-endian integer.

The uncompressed SEC format is shown in Figure 4-1.

Big- and Little-Endian

The motivation for big- and little-endian encodings is storing a number on disk. A number under 256 is easy enough to encode, as a single byte (2⁸) is enough to hold it. When it’s bigger than 256, how do we serialize the number to bytes?

Arabic numerals are read left to right. A number like 123 is 100 + 20 + 3 and not 1 + 20 + 300. This is what we call big-endian, because the “big end” starts first.

Computers can sometimes be more efficient using the opposite order, or little-endian—that is, starting with the little end first.

Since computers work in bytes, which have 8 bits, we have to think in base 256. This means that a number like 500 looks like 01f4 in big-endian—that is, 500 = 1 × 256 + 244 (f4 in hexadecimal). The same number looks like f401 in little-endian.

Unfortunately, some serializations in Bitcoin (like the SEC format x and y coordinates) are big-endian, while others (like the transaction version number in Chapter 5) are little-endian. This book will let you know which ones are big- versus little-endian.

Creating the uncompressed SEC format serialization is pretty straightforward. The trickiest part is converting a 256-bit number into 32 bytes, big-endian. Here’s how this is done in code:

class S256Point(Point):
...
    def sec(self):
        '''returns the binary version of the SEC format'''
	return b'\x04' + self.x.num.to_bytes(32, 'big') \
            + self.y.num.to_bytes(32, 'big')

: In Python 3, you can convert a number to bytes using the to_bytes method. The first argument is how many bytes it should take up and the second argument is the endianness (see the preceding note).

Exercise 1

Find the uncompressed SEC format for the public key where the private key secrets are:

5,000
2,018⁵
0xdeadbeef12345

Compressed SEC Format

Recall that for any x coordinate, there are at most two y coordinates due to the y² term in the elliptic curve equation (Figure 4-2).

It turns out that even over a finite field, we have the same symmetry.

This is because for any (x,y) that satisfies y² = x³ + ax + b, (x,–y) also satisfies the equation. Furthermore, in a finite field, –y % p = (p – y) % p. Or, more accurately, if (x,y) satisfies the elliptic curve equation, (x,p – y) also satisfies the equation. These are the only two solutions for a given x, as shown, so if we know x, we know the y coordinate has to be either y or p – y.

Since p is a prime number greater than 2, we know that p is odd. Thus, if y is even, p – y (odd minus even) will be odd. If y is odd, p – y will be even. In other words, between y and p – y, exactly one will be even and one will be odd. This is something we can use to our advantage to shorten the uncompressed SEC format: we can provide the x coordinate and the evenness of the y coordinate. We call this the compressed SEC format because of how the y coordinate is compressed into a single byte (namely, whether it’s even or odd).

Here is 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’s 0x03.
Next, append the x coordinate in 32 bytes as a big-endian integer.

The compressed SEC format is shown in Figure 4-3.

Again, the procedure is pretty straightforward. We can update the sec method to handle compressed SEC keys:

class S256Point(Point):
...
    def sec(self, compressed=True):
        '''returns the binary version of the SEC format'''
        if compressed:
            if self.y.num % 2 == 0:
                return b'\x02' + self.x.num.to_bytes(32, 'big')
            else:
                return b'\x03' + self.x.num.to_bytes(32, 'big')
        else:
            return b'\x04' + self.x.num.to_bytes(32, 'big') + \
                self.y.num.to_bytes(32, 'big')

The big advantage of the compressed SEC format is that it only takes up 33 bytes instead of 65 bytes. This is a big savings when amortized over millions of transactions.

At this point, you may be wondering how you can analytically calculate y given the x coordinate. This requires us to calculate a square root in a finite field.

Stated mathematically:

Find w such that w² = v when we know v.

It turns out that if the finite field prime p % 4 = 3, we can do this rather easily. Here’s how.

First, we know:

p % 4 = 3

which implies:

(p + 1) % 4 = 0

That is, (p + 1)/4 is an integer.

By definition:

w² = v

We are looking for a formula to calculate w. From Fermat’s little theorem:

w^p–1 % p = 1

which means:

w² = w² ⋅ 1 = w² ⋅ w^p–1 = w^(p+1)

Since p is odd (recall p is prime), we know we can divide (p+1) by 2 and still get an integer, implying:

w = w^(p+1)/2

Now we can use (p+1)/4 being an integer this way:

w = w^(p+1)/2 = w^2(p+1)/4 = (w²)^(p+1)/4 = v^(p+1)/4

So our formula for finding the square root becomes:

if w² = v and p % 4 = 3, w = v^(p+1)/4

It turns out that the p used in secp256k1 is such that p % 4 == 3, so we can use this formula:

w² = v
w = v^(p+1)/4

That will be one of the two possible w’s; the other will be p – w. This is due to taking the square root means that both the positive and negative will work.

We can add this as a general method in the S256Field class:

class S256Field(FieldElement):
...
    def sqrt(self):
        return self**((P + 1) // 4)

When we get a serialized SEC pubkey, we can write a parse method to figure out which y we need:

class S256Point:
...
    @classmethod
    def parse(self, sec_bin):
        '''returns a Point object from a SEC binary (not hex)'''
        if sec_bin[0] == 4:  
            x = int.from_bytes(sec_bin[1:33], 'big')
            y = int.from_bytes(sec_bin[33:65], 'big')
            return S256Point(x=x, y=y)
        is_even = sec_bin[0] == 2  
        x = S256Field(int.from_bytes(sec_bin[1:], 'big'))
        # right side of the equation y^2 = x^3 + 7
        alpha = x**3 + S256Field(B)
        # solve for left side
        beta = alpha.sqrt()  
        if beta.num % 2 == 0:  
            even_beta = beta
            odd_beta = S256Field(P - beta.num)
        else:
            even_beta = S256Field(P - beta.num)
            odd_beta = beta
        if is_even:
            return S256Point(x, even_beta)
        else:
            return S256Point(x, odd_beta)

: The uncompressed SEC format is pretty straightforward.
: The evenness of the y coordinate is given in the first byte.
: We take the square root of the right side of the elliptic curve equation to get y.
: We determine evenness and return the correct point.

Exercise 2

Find the compressed SEC format for the public key where the private key secrets are:

5,001
2,019⁵
0xdeadbeef54321

DER Signatures

Another class that we need to learn to serialize is Signature. Much like the SEC format, it needs to encode two different numbers, r and s. Unfortunately, unlike S256Point, Signature cannot be compressed as s cannot be derived solely from r.

The standard for serializing signatures (and lots of other things, for that matter) is called Distinguished Encoding Rules (DER) format. DER format was used by Satoshi to serialize signatures. This was most likely because the standard was already defined in 2008, was supported in the OpenSSL library (used in Bitcoin at the time), and was easy enough to adopt, rather than creating a new standard.

DER signature format is defined like this:

Start with the 0x30 byte.
Encode the length of the rest of the signature (usually 0x44 or 0x45) and append.
Append the marker byte, 0x02.
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.
Append the marker byte, 0x02.
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 1, which is equivalent to first byte ≥ 0x80.

The DER format is shown in Figure 4-4.

Because we know r is a 256-bit integer, r will be at most 32 bytes expressed as big-endian. It’s also possible the first byte could be ≥ 0x80, so #4 can be at most 33 bytes. However, if r is a relatively small number, it could be less than 32 bytes. The same goes for s and #6.

Here’s how this is coded in Python:

class Signature:
...
    def der(self):
        rbin = self.r.to_bytes(32, byteorder='big')
        # remove all null bytes at the beginning
        rbin = rbin.lstrip(b'\x00')
        # if rbin has a high bit, add a \x00
        if rbin[0] & 0x80:
            rbin = b'\x00' + rbin
        result = bytes([2, len(rbin)]) + rbin  
        sbin = self.s.to_bytes(32, byteorder='big')
        # remove all null bytes at the beginning
        sbin = sbin.lstrip(b'\x00')
        # if sbin has a high bit, add a \x00
        if sbin[0] & 0x80:
            sbin = b'\x00' + sbin
        result += bytes([2, len(sbin)]) + sbin
        return bytes([0x30, len(result)]) + result

: In Python 3, you can convert a list of numbers to the byte equivalents using bytes([some_integer1, some_integer2]).

Overall, this is an inefficient way to encode r and s as there are at least 6 bytes that aren’t strictly necessary.

Exercise 3

Find the DER format for a signature whose r and s values are:

r = 0x37206a0610995c58074999cb9767b87af4c4978db68c06e8e6e81d282047a7c6

s = 0x8ca63759c1157ebeaec0d03cecca119fc9a75bf8e6d0fa65c841c8e2738cdaec

Base58

In the early days of Bitcoin, bitcoins were assigned to public keys specified in SEC format (uncompressed) and then were redeemed using DER signatures. For reasons we’ll get to in Chapter 6, using this particular very simple script turned out to be both wasteful for storing unspent transaction outputs (UTXOs) and a little less secure than the scripts in more prominent use now. For now, we’ll go through what addresses are and how they are encoded.

Transmitting Your Public Key

In order for Alice to pay Bob, she has to know where to send the money. This is true not just in Bitcoin, but for any method of payment. Since Bitcoin is a digital bearer instrument, the address can be something like a public key in a public key cryptography scheme. Unfortunately, SEC format, especially uncompressed, is a bit long (65 or 33 bytes). Furthermore, the 65 or 33 bytes are in binary format—not something that’s easy to read, at least raw.

There are three major considerations. 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).

So how do we get readability, compression, and security? If we express the SEC format in hexadecimal (4 bits per character), it’s double the length (130 or 66 characters). Can we do better?

We can use something like Base64, which can express 6 bits per character. This results in 87 characters for uncompressed SEC and 44 characters for compressed SEC. Unfortunately, Base64 is prone to mistakes, as a lot of letters and numbers look similar (0 and O, l and I, - and _). If we remove these characters, we can achieve a result that has good readability and decent compression (around 5.86 bits per character). Lastly, we can add a checksum at the end to ensure that mistakes are easy to detect.

This construction is called Base58. Instead of hexadecimal (base 16) or Base64, we’re encoding numbers in Base58.

The actual mechanics of doing the Base58 encoding are as follows.

All numbers, uppercase letters, and lowercase letters are utilized, except for the aforementioned 0/O and l/I. That leaves us with 10 + 26 + 26 – 4 = 58. Each of these characters represents a digit in Base58. We can encode with a function that does exactly this:

BASE58_ALPHABET = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
...
def encode_base58(s):
    count = 0
    for c in s:  
        if c == 0:
            count += 1
        else:
            break
    num = int.from_bytes(s, 'big')
    prefix = '1' * count
    result = ''
    while num > 0:  
        num, mod = divmod(num, 58)
        result = BASE58_ALPHABET[mod] + result
    return prefix + result

: The purpose of this loop is to determine how many of the bytes at the front are 0 bytes. We want to add them back at the end.
: This is the loop that figures out what Base58 digit to use.
: Finally, we prepend all the zeros that we counted at the front, because otherwise they wouldn’t show up as prefixed ones. This annoyingly happens with pay-to-pubkey-hash (p2pkh); more on that in Chapter 6.

This function will take any bytes in Python 3 and convert them to Base58.

Why Base58 Is on the Way Out

Base58 has been used for a long time, and while it does make it somewhat easier than something like Base64 to communicate, it’s not really that convenient. Most people prefer to copy and paste the addresses, and if you’ve ever tried to communicate a Base58 address vocally, you know it can be a nightmare.

What’s much better is the new Bech32 standard, which is defined in BIP0173. Bech32 uses a 32-character alphabet that’s just numbers and lowercase letters, except 1, b, i, and o. Thus far, it’s only used for Segwit (Chapter 13).

Exercise 4

Convert the following hex values to binary and then to Base58:

7c076ff316692a3d7eb3c3bb0f8b1488cf72e1afcd929e29307032997a838a3d
eff69ef2b1bd93a66ed5219add4fb51e11a840f404876325a1e8ffe0529a2c
c7207fee197d27c618aea621406f6bf5ef6fca38681d82b2f06fddbdce6feab6

Address Format

The 264 bits from compressed SEC format are still a bit too long, not to mention a bit less secure (see Chapter 6). To both shorten the address and increase security, we can use the ripemd160 hash.

By not using the SEC format directly, we can go from 33 bytes to 20 bytes, shortening the address significantly. Here is how a Bitcoin address is created:

For mainnet addresses, start with the prefix 0x00, for testnet 0x6f.
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.
Combine the prefix from #1 and resulting hash from #2.
Do a hash256 of the result from #3 and get the first 4 bytes.
Take the combination of #3 and #4 and encode it in Base58.

The result of step 4 of this process is called the checksum. We can do steps 4 and 5 in one go this way:

def encode_base58_checksum(b):
    return encode_base58(b + hash256(b)[:4])

What Is Testnet?

Testnet is a parallel Bitcoin network that’s meant to be used by developers. The coins on there are not worth anything and the proof-of-work required to find a block is relatively easy. The mainnet chain as of this writing has around 550,000 blocks, while testnet has significantly more (around 1,450,000 blocks).

We can implement the hash160 operation in helper.py:

def hash160(s):
    '''sha256 followed by ripemd160'''
    return hashlib.new('ripemd160', hashlib.sha256(s).digest()).digest()

: Note that hashlib.sha256(s).digest does the sha256 and the wrapper around it does the ripemd160.

We can also update S256Point with hash160 and address methods:

class S256Point:
...
    def hash160(self, compressed=True):
        return hash160(self.sec(compressed))

    def address(self, compressed=True, testnet=False):
        '''Returns the address string'''
        h160 = self.hash160(compressed)
        if testnet:
            prefix = b'\x6f'
        else:
            prefix = b'\x00'
        return encode_base58_checksum(prefix + h160)

Exercise 5

Find the addresses corresponding to the public keys whose private key secrets are:

5002 (use uncompressed SEC on testnet)
2020⁵ (use compressed SEC on testnet)
0x12345deadbeef (use compressed SEC on mainnet)

WIF Format

The private key in our case is a 256-bit number. Generally, we are not going to need to serialize our secret that often, as it doesn’t get broadcast (that would be a bad idea!). That said, there are instances where you may want to transfer your private key from one wallet to another—for example, from a paper wallet to a software wallet.

For this purpose, you can use Wallet Import Format (WIF). WIF is a serialization of the private key that’s meant to be human-readable. WIF uses the same Base58 encoding that addresses use.

Here is how the WIF format is created:

For mainnet private keys, start with the prefix 0x80, for testnet 0xef.
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 hash256 of the result from #4 and get the first 4 bytes.
Take the combination of #4 and #5 and encode it in Base58.

We can now create the wif method on the PrivateKey class:

class PrivateKey
...
    def wif(self, compressed=True, testnet=False):
        secret_bytes = self.secret.to_bytes(32, 'big')
        if testnet:
            prefix = b'\xef'
        else:
            prefix = b'\x80'
        if compressed:
            suffix = b'\x01'
        else:
            suffix = b''
        return encode_base58_checksum(prefix + secret_bytes + suffix)

Exercise 6

Find the WIF for the private key whose secrets are:

5003 (compressed, testnet)
2021⁵ (uncompressed, testnet)
0x54321deadbeef (compressed, mainnet)

Big- and Little-Endian Redux

It will be very useful to know how big- and little-endian are done in Python, as the next few chapters will be parsing and serializing numbers to and from big-/little-endian quite a bit. In particular, Satoshi used a lot of little-endian for Bitcoin and unfortunately, there’s no easy-to-learn rule for where little-endian is used and where big-endian is used. Recall that SEC format uses big-endian encoding, as do addresses and WIF. From Chapter 5 onward, we will use little-endian encoding a lot more. For this reason, we turn to the next two exercises. The last exercise of this section is to create a testnet address for yourself.

Exercise 7

Write a function little_endian_to_int that takes Python bytes, interprets those bytes in little-endian, and returns the number.

Exercise 8

Write a function int_to_little_endian that does the reverse of the last exercise.

Exercise 9

Create a testnet address for yourself using a long secret that only you know. This is important as there are bots on testnet trying to steal testnet coins. Make sure you write this secret down somewhere! You will be using it later to sign transactions.

Go to a testnet faucet and send some testnet coins to that address (it should start with m or n, or else something is wrong). If you succeeded, congrats! You’re now the proud owner of some testnet coins!

Conclusion

In this chapter we learned how to serialize a lot of different structures that we created in the previous chapters. We now turn to parsing and understanding transactions.

Get Programming Bitcoin now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Programming Bitcoin by