The Algorithms: Behind Bitcoin

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

Algorithms are like machines. Data goes in, and the algorithm does some work, and data comes out. 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 is 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, that is, about 320 bits for a security level of 80 bits.

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

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.

Bitcoin has an enormous field.

There are 10^82 atoms in the universe. If you made the entire Universe our finite field and you drew a giant elliptic curve through it, each “point” in the universe would 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.

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

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 oc lVanityGen commanding those 25 GPUs and for fantasy 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. Add unique flair when you tell people to send bitcoins to 1st Downqy MHHqnDPRSfiZ5GXJ8Gk9dbjO. 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 sec 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 an 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 like a machine. You put in “stuff” and, hopefully, new “stuff” comes out.

A simple example of a hash

1. Every letter has a value of its position in the alphabet. A = 1; B = 2, etc.
2. The hash algorithm is this:
3. for i=0 to length (word):
4. h = h + (i + letter_value)
5. So for the word “ABC” using our hash would be:
6. Loop for ‘A’
7. h = 0 + (0 + 1)
8. Loop ‘B’
9. h = 1 + (1 + 2)
10. ‘C’
11. h = 4 + (2 + 3)
12. h = 9

‘ABC’ hashes to 9. RIPEMD is much more sophisticated.

RIPEMD uses your public key to create a hash. A bitcoin address is smaller than a public key. That introduces another term, collisions. When two unique inputs give the same output in a hash algorithm, it’s called a collision. In the above example, the word ‘C’ has the same output as ‘AA’. Using an enormous numbers, and a strong algorithm reduces collisions. But for Bitcoin it’s because we’re turning large numbers in to 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 miniscule 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 likely wouldn’t have a balance.

How It Works

Your private key is kept secret. This is the key that unlocks funds owed to you in the Bitcoin block chain.

Bitcoin has a scripting system that is used to define the parameters necessary to spend bitcoins. When you build a transaction in addition to referencing 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.

Source : Erik Rykwalder