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.
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 bigendian integer.
Next, append the y coordinate in 32 bytes as a bigendian integer.
The uncompressed SEC format is shown in Figure 41.
The motivation for big and littleendian encodings is storing a number on disk. A number under 256 is easy enough to encode, as a single byte (2^{8}) 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 bigendian, because the “big end” starts first.
Computers can sometimes be more efficient using the opposite order, or littleendian—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 bigendian—that is, 500 = 1 × 256 + 244 (f4
in hexadecimal).
The same number looks like f401
in littleendian.
Unfortunately, some serializations in Bitcoin (like the SEC format x and y coordinates) are bigendian, while others (like the transaction version number in Chapter 5) are littleendian. This book will let you know which ones are big versus littleendian.
Creating the uncompressed SEC format serialization is pretty straightforward. The trickiest part is converting a 256bit number into 32 bytes, bigendian. 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).
Find the uncompressed SEC format for the public key where the private key secrets are:
5,000
2,018^{5}
0xdeadbeef12345
Recall that for any x coordinate, there are at most two y coordinates due to the y^{2} term in the elliptic curve equation (Figure 42).
It turns out that even over a finite field, we have the same symmetry.
This is because for any (x,y) that satisfies y^{2} = x^{3} + 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 bigendian integer.
The compressed SEC format is shown in Figure 43.
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:
It turns out that if the finite field prime p % 4 = 3, we can do this rather easily. Here’s how.
First, we know:
which implies:
That is, (p + 1)/4 is an integer.
By definition:
We are looking for a formula to calculate w. From Fermat’s little theorem:
which means:
Since p is odd (recall p is prime), we know we can divide (p+1) by 2 and still get an integer, implying:
Now we can use (p+1)/4 being an integer this way:
So our formula for finding the square root becomes:
It turns out that the p used in secp256k1 is such that p % 4 == 3, so we can use this formula:
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.
Find the compressed SEC format for the public key where the private key secrets are:
5,001
2,019^{5}
0xdeadbeef54321
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 bigendian 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 bigendian 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 44.
Because we know r
is a 256bit integer, r
will be at most 32 bytes expressed as bigendian.
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.
Find the DER format for a signature whose r
and s
values are:
r = 0x37206a0610995c58074999cb9767b87af4c4978db68c06e8e6e81d282047a7c6 s = 0x8ca63759c1157ebeaec0d03cecca119fc9a75bf8e6d0fa65c841c8e2738cdaec
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.
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 handwrite 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 paytopubkeyhash (p2pkh); more on that in Chapter 6.
This function will take any bytes in Python 3 and convert them to Base58.
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 32character alphabet that’s just numbers and lowercase letters, except 1
, b
, i
, and o
.
Thus far, it’s only used for Segwit (Chapter 13).
Convert the following hex values to binary and then to Base58:
7c076ff316692a3d7eb3c3bb0f8b1488cf72e1afcd929e29307032997a838a3d
eff69ef2b1bd93a66ed5219add4fb51e11a840f404876325a1e8ffe0529a2c
c7207fee197d27c618aea621406f6bf5ef6fca38681d82b2f06fddbdce6feab6
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
])
Testnet is a parallel Bitcoin network that’s meant to be used by developers. The coins on there are not worth anything and the proofofwork 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
(
)
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
)
Find the addresses corresponding to the public keys whose private key secrets are:
5002 (use uncompressed SEC on testnet)
2020^{5} (use compressed SEC on testnet)
0x12345deadbeef (use compressed SEC on mainnet)
The private key in our case is a 256bit 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 humanreadable. 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 32byte bigendian.
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
)
Find the WIF for the private key whose secrets are:
5003 (compressed, testnet)
2021^{5} (uncompressed, testnet)
0x54321deadbeef (compressed, mainnet)
It will be very useful to know how big and littleendian are done in Python, as the next few chapters will be parsing and serializing numbers to and from big/littleendian quite a bit. In particular, Satoshi used a lot of littleendian for Bitcoin and unfortunately, there’s no easytolearn rule for where littleendian is used and where bigendian is used. Recall that SEC format uses bigendian encoding, as do addresses and WIF. From Chapter 5 onward, we will use littleendian 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.
Write a function little_endian_to_int
that takes Python bytes, interprets those bytes in littleendian, and returns the number.
Write a function int_to_little_endian
that does the reverse of the last exercise.
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!
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.
No credit card required