We’ve created a lot of classes thus far, including PrivateKey, S256Point and Signature. We now need to start thinking about how to transmit thes objects to other computers on the network, or even to disk as we’ll need to store objects of these classes. 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 (Networking).
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 SEC. SEC stands for Standards for Efficient Cryptography and as the name suggests, it’s got minimal overhead. There are two forms of SEC format that we need to be concerned with and the first is the uncompressed SEC format and the second compressed SEC format.
Here is how the uncompressed SEC format for a given point P=(x,y) is generated:
-
Start with the prefix byte. This is always 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.
Here is what the uncompressed SEC format looks like:
|
Warning
|
Big and Little Endian
The motivation for Big and Little Endian encodings is storing a number on disk. Arabic numberals 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 this in Big-Endian Unfortunately, some stuff in Bitcoin (like the SEC format x and y coordinates) are in Big-Endian. Other stuff in Bitcoin (like the transaction version number) are in Little-Endian. This book will let you know which ones are Big vs Little Endian. |
This procedure is pretty straightforward. The trickiest part being converting a 256-bit number into a 32 bytes. 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') # (1)-
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 sidebar).
Recall that for any x-coordinate, there are only two different possible y-coordinates due to the y2 term in the elliptic curve equation:
It turns out that even over a Finite Field, we have the same symmetry.
This is because for any (x,y) that satisfies the y2=x3+ax+b, (x,-y) also satisfies the equation. Furthermore, in a Finite Field, -y (mod p) = p - y. 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 above, so if we know x, we know P can only be one of (x,y), (x,p-y).
Since p is a prime number greater than 2, we know that p is odd. Thus, if y is even, p-y 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. Essentially, we need to provide the x-coordinate and the parity, or even-ness of the y-coordinate. We do so this way:
Here is how the Compressed SEC format for a given point P=(x,y) is generated:
-
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 looks like this:
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 here is that this only takes up 33 bytes instead of the uncompressed’s 65 bytes. This is a huge savings and is a lot more efficient.
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.
y2=x3+ax+b=v
We can already calculate v if we have x using the normal Finite Field operations. But then we have to take a square root to get y. How do we do this?
It turns out that if the Field prime has a certain property, this is easy to calculate. And indeed the prime used for our field has this property. Specifically:
p % 4 == 3
How does this help?
(p + 1) % 4 == 0
means that
(p+1) = 4q or q = (p+1)/4 where q is an integer
We know y2 already (from the elliptic curve equation’s right side). If we are trying to take the square root of a number in a prime field, we can say this;
let w2 = y
From Fermat’s Little Theorem:
w2=y=1⋅y=ypy=y(p+1)
Since p is odd, we know we can divide by two implying
w=y(p+1)/2=y2(p+1)/4=(y2)(p+1)/4=vq
We can calculate w from v (calculated from x) and q (calculated from p), both of which we know!
y2 = x3 + ax + b
y = (x3+ax+b)(p+1)/4 provided p + 1 % 4 = 0
That will be one of the two possible y’s the other will be p-y.
It turns out the prime in SEC256k1 (p=2256-232-277) is indeed (p=3%4)
We can actually add this as a general method in the S256Field
class S256Field(FieldElement):
...
def sqrt(self):
return self**((P + 1) // 4)Another class that we need to learn to serialize are signatures. 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 is called DER format. DER stands for Distinguished Encoding Rules and was used by Satoshi to create Bitcoin. This was most likely because the standard was already defined in 2008 and it was easy enough to adopt, rather than creating a new standard.
DER Signatures are created 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 with 0x00 byte if r’s first byte >= 0x80. Add this to the result
-
Append the marker byte (0x02)
-
Encode s as a big endian integer, but prepend with 0x00 byte if s’s first byte >= 0x80. Add this to the result
Here’s what it looks like:
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 part 4 can be at most 33-bytes. However, if r is a relatively small number, it could be less than 32 bytes. Same goes for s and part 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 # (1)
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 4 bytes that aren’t necessary.
At this point, you may think that communicating our public keys via SEC format and signing transactions to have other nodes on the network verifying these transactions with the public key would be enough. Indeed that’s what happened 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 (Script), this turned out to be both wasteful and less secure than what we use now. In this chapter, we’ll go through what addresses are and how they are encoded.
In order for Alice to effectively pay Bob, she has to know where to send Bob the money. This is true not just in Bitcoin, but any medium of exchange. 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 write down or even say over the phone). The second is that it’s short (not be so long that it’s cumbersome). The third is that it’s secure (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 actually double the length (130 or 66 characters). Can we do better?
We can use something like Base64 which can express 6 bits per character and becomes 87 or 44 characters. 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 have something that’s got 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 is called Base58. Instead of hexadecimal (base 16) or Base64, we’re going to have to encode numbers in Base58.
The actual mechanics of doing the base58 encoding are as follows.
All numbers, upper case letters and lower case 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 base 58. We can encode with a function that does exactly this:
def encode_base58(s):
count = 0
for c in s: # (1)
if c == 0:
count += 1
else:
break
prefix = b'1' * count
num = int.from_bytes(s, 'big')
result = bytearray()
while num > 0: # (2)
num, mod = divmod(num, 58)
result.insert(0, BASE58_ALPHABET[mod])
return prefix + bytes(result) # (3)-
The purpose of this loop is to determine how many of the bytes are 0 bytes. We want to add them back at the end.
-
This is the loop that figures out what base-58 digit to use.
-
Finally, we prepend all the zeros that we detected because otherwise, they wouldn’t show up as prefixed 1’s. This annoyingly happens with pay-to-pubkey-hash (p2pkh). More on that in Chapter 7 (Script)
This will take any bytes in Python 3 and convert it to base58 bytes
It turns out that the 260 bits from a compressed SEC format is still a bit too long, not to mention a bit less secure (see Chapter 6). To both shorten and increase security, we can utilize the RIPEMD160 hash to compress the public key to a 20-byte hash.
By taking the SEC format from 33 bytes to 20 bytes, we can shorten the address significantly. Here is how the Address format 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.
-
combine the prefix from #1 and resulting hash from #2
-
Do a double SHA256 of the result from #3 and get the first 4 bytes.
-
Take the combination of #3 and #4 and encode in Base58.
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(s):
return encode_base58(s + double_sha256(s)[:4]).decode('ascii') # (1)-
Note that the
decode('ascii)` part is necessary to convert from Python 3 bytes to a Python 3 string.
The process of doing a SHA256 operation followed by a RIPEMD160 operation is called a HASH160 operation in Bitcoin. We can implement this fairly easily in helper.py.
def hash160(s):
return hashlib.new('ripemd160', hashlib.sha256(s).digest()).digest()We can also update S256Point to have the h160 and address methods.
class S256Point:
...
def h160(self, compressed=True):
return hash160(self.sec(compressed))
def address(self, compressed=True, testnet=False):
'''Returns the address string'''
h160 = self.h160(compressed)
if testnet:
prefix = b'\x6f'
else:
prefix = b'\x00'
return encode_base58_checksum(prefix + h160)The Private Key in our case is a 256-bit number. Generally, you are not going to need to serialize your 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 this purpose, there is a format called WIF, which stands for Wallet Import Format. 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 double SHA256 of the result from #4 and get the first 4 bytes.
-
Take the combination of #4 and #5 and encode 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)It will be very useful to know how Big and Little Endian are done in Python as the next few chapters will utilize 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 rule for determining where Little Endian was used and where Big Endian was used. Recall that SEC format use Big Endian encoding as do addresses and WIF. A lot of stuff coming up in Chapter 5 onward will utilze Little Endian encoding. For this reason, we turn to these two exercises.
Write a function little_endian_to_int which takes Python bytes, interprets those bytes in Little Endian and returns the number.