Algorithms: The Math Behind Bitcoin

An algorithm is a process or procedure for making calculations. They are not always intimidating scribblings mapped across multiple chalkboards in college classrooms. For example, y = mx + b is the line drawing algorithm from algebra and is not very intimidating at all.

Algorithms are like machines. Data goes in, the algorithm does some work, and data comes out. The Elliptic Curve Digital Signature Algorithm (ECDSA) is all of the “y = mx + b” mathematics that goes into creating Bitcoin key pairs.

Key and signature-size comparison to DSA

As with elliptic-curve cryptography in general, the bit size of the public key believed to be needed for ECDSA is about twice the size of the security level (in bits). For example, at a security level of 80 bits (meaning an attacker requires a maximum of about {\displaystyle 2^{80}} operations to find the private key), the size of an ECDSA public key would be 160 bits, whereas the size of a Digital Signature Algorithm (DSA) public key would be at least 1024 bits.

On the other hand, the signature size is the same for both DSA and ECDSA: apx. {\displaystyle 4t} bits, where {\displaystyle t} is the security level measured in bits (about 320 bits for a security level of 80 bits).

ECDSA is a process that uses an elliptic curve and a finite field to “sign” data. In practical terms, it’s like drawing a big squiggly line on a graph within certain limits. The line is an elliptic curve:

The finite field is a graph or cartesian plane (i.e. the thing our math teachers made us draw the y = mx + b lines on). Finite fields are modular, therefore, points falling outside the size of the graph wrap around until they do.

To create a new key pair, the elliptic curve is plotted across the finite field. A line is drawn across the curve such that it intersects three points on the curve. Bitcoin defines the formula for the curve and the parameters of the field so that every user has the same graph.

.

The parameters used in Bitcoin’s elliptic curve and finite field are defined as secp256k1.

A private key is any number between 1 and

1852673427797059126777135760139006525645401028465198470121682610264290583909392 or

FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 or

11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110101110101010111011011100111001101010111101001000101000000011101110111111110100100101111010001100110100000011011001000001010000010000

Between 1 and 2^256. The spot where the line originates on the graph is the base point. Multiply the base point by the private key and you have a public key. The base point does not change, one public key maps to one private key.

This part is important. Bitcoin has an enormous field.

There are 10^82 atoms in the universe. If you made the entire Universe our finite field and drew a giant elliptic curve through it, each “point” in the universe would be about 300 square atoms. At that size, each cell in your body takes up the space of 1,150,000,000 Bitcoin key pairs.

10^82 / 2^256 = 86362 sqrt(86362) ~ 300 10^14 / 86362 = 1.15 * 10^9

Trying to brute-force every private key would be like mapping out every 300 square atom block in the universe. Yeah, that’s a silly thing to do.

There’s more! There’s something called Landauer’s principle that talks about the theoretical smallest amount of energy required to store one bit of data. There’s a lot more math involved, and the laws of thermodynamics come into play.

In short, here is an ancient chart:

Let’s just say the heat death of the universe is in 10^120 years. A 25 GPU password cracker does about 350,000,000,000 hashes a second. It’s not the same algorithm, but let’s pretend we have oclVanityGen commanding those 25 GPUs and for fantasy’s sake say it goes just as fast.

1852673427797059126777135760139006525645401028465198470121682610264290583909392 / 350,000,000 = 5293352650848740362220387886111447216129717224100000000000000000000000 years or 5 * 10^69 years (and about 4000 years to calculate 1 human worth of private keys).

There’s a possibility of seeing a completely random Big Bang happening in 10^59 years. By that time, humans will have transcended physical form and money will be indistinguishable from the tools of cavemen – if it is remembered at all.

What is a Vanitygen

Vanitygen is a command-line vanity bitcoin address generator. If you're tired of the random, cryptic addresses generated by regular bitcoin clients, you can use vanitygen to create a more personalized address. It adds a unique flair for when you tell people to send bitcoins to 1stDownqyMHHqnDPRSfiZ5GXJ8Gk9dbjO! Alternatively, vanitygen can be used to generate random addresses offline.

Vanitygen accepts as input a pattern, or list of patterns, to search for and produces a list of addresses and private keys.

Vanitygen's search is probabilistic and the amount of time required to find a given pattern depends on how complex the pattern is, the speed of your computer, and whether you get lucky.

The example below illustrates a session of vanitygen. It is typical and takes about 10 secs to finish, using a Core 2 Duo E6600 CPU on x86-64 Linux:

Bitcoin Addresses

A Bitcoin Address looks like this: 181TK6dMSy88SvjN1mmoDkjB9TmvXRqCCv

The address is not a public key. An address is a RIPEMD-160 hash of an SHA256 hash of a public key. SHA256 and RIPEMD-160 are also algorithms. Unlike ECDSA, which is used to generate key pairs, RIPEMD-160 generates a hash. Think of an algorithm as a machine. You put in “stuff” and, hopefully, new “stuff” comes out.

A simple example of a hash:

Every letter has a value of its position in the alphabet. A = 1; B = 2, etc.

Our hash algorithm is this: for i=0 to len(word): h = h + (i + letter_value)

So for the word “ABC” using our hash would be:

Loop for ‘A’ h = 0 + (0 + 1) Loop ‘B’ h = 1 + (1 + 2) ‘C’ h = 4 + (2 + 3) h = 9

‘ABC’ hashes to 9.

Of course, RIPEMD is much more sophisticated. RIPEMD uses your public key to create a hash. A bitcoin address is smaller than a public key. This introduces another term, collisions.

A collision is when two unique inputs give the same output in a hash algorithm. In the above example, the word ‘C’ has the same output as ‘AA’. Using enormous numbers and a strong algorithm reduces collisions. But, for Bitcoin, it’s because we’re turning large numbers into smaller numbers.

For Bitcoin, there are so many possible keys that collisions are astronomically unlikely. Furthermore, since there are only 21M bitcoins only a very minuscule fraction of keys can even claim a balance. So, even if someone were to generate a key pair that collides with another (an astronomical feat), the other key is very likely to not have a balance.

How It Works

Your private key (i.e. the key that unlocks funds owed to you in the Bitcoin blockchain) is kept secret.

Bitcoin has a scripting system used to define the parameters necessary to spend bitcoins. When you build a transaction or reference previous transactions you’ve received, it contains a script with your private key’s signature and the matching public key.

This is used to prove the provided public key matches the private key used to make the signature.

If that public key hashes (RIPEMD160) to the Bitcoin Address in a previously unclaimed transaction, it can be spent. That’s a high-level view of some of the ways Bitcoin uses cryptography.