Algorithms: THE Math 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. ECDSA is all of the “y = mx + b” mathematics that goes into creating Bitcoin key pairs.

As Erik explains,

[ECDSA]… a process that uses an elliptic curve and a finite field to “sign” data

He does a great job of defining the math. In practical terms, we’re drawing a big squiggly line on a graph within certain limits.

The line is an elliptic curve:

elliptic_curve_commmons

Also practically, the finite field is a graph or cartesian plane. The thing our math teachers made us draw the y = mx + b lines on. Finite fields are modular. Points that fall 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
1111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111110101110101010111011
0111001110011010101111010010001010000000111011101111111101001001011110100
01100110100000011011001000001010000010000

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 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

That’s alotta keys

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 a bit of data. There’s a lot more of math involved, and I’m pretty sure the laws of thermodynamics come into play.

In short, here is an ancient chart:

How many Bitcoin Addresses are there?

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 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.

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

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. 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 Actually 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.

Bitcoin Monetary Inflation Schedule

This interactive chart visualizes the monetary inflation schedule used in Bitcoin.

For more info, visit: https://en.bitcoin.it/wiki/Controlled_supply

The image below is a bitmap version of the original plot.ly chart. The chart is being hosted on Github Pages in order to avoid plot.ly’s 500-views-per-day limitation.

chart embed

===

Currency with Finite Supply

Block reward halving

Controlled supply

Bitcoins are created each time a user discovers a new block. The rate of block creation is adjusted every 2016 blocks to aim for a constant two week adjustment period (equivalent to 6 per hour.) The number of bitcoins generated per block is set to decrease geometrically, with a 50% reduction every 210,000 blocks, or approximately four years. The result is that the number of bitcoins in existence is not expected to exceed 21 million.[2] Speculated justifications for the unintuitive value “21 million” are that it matches a 4-year reward halving schedule; or the ultimate total number of Satoshis that will be mined is close to the maximum capacity of a 64-bit floating point number. Satoshi has never really justified or explained many of these constants.

ControlledSupply.png

This decreasing-supply algorithm was chosen because it approximates the rate at which commodities like gold are mined. Users who use their computers to perform calculations to try and discover a block are thus called Miners.

Projected Bitcoins Short Term

This chart shows the number of bitcoins that will exist in the near future. The Year is a forecast and may be slightly off.

Date reached Block Reward Era BTC/block Year (estimate) Start BTC BTC Added End BTC BTC Increase End BTC % of Limit
2009-01-03 0 1 50.00 2009 0 2625000 2625000 infinite 12.500%
2010-04-22 52500 1 50.00 2010 2625000 2625000 5250000 100.00% 25.000%
2011-01-28 105000 1 50.00 2011* 5250000 2625000 7875000 50.00% 37.500%
2011-12-14 157500 1 50.00 2012 7875000 2625000 10500000 33.33% 50.000%
2012-11-28 210000 2 25.00 2013 10500000 1312500 11812500 12.50% 56.250%
2013-10-09 262500 2 25.00 2014 11812500 1312500 13125000 11.11% 62.500%
2014-08-11 315000 2 25.00 2015 13125000 1312500 14437500 10.00% 68.750%
2015-07-29 367500 2 25.00 2016 14437500 1312500 15750000 9.09% 75.000%
2016-07-09 420000 3 12.50 2016 15750000 656250 16406250 4.17% 78.125%
2017-06-23 472500 3 12.50 2018 16406250 656250 17062500 4.00% 81.250%
525000 3 12.50 2019 17062500 656250 17718750 3.85% 84.375%
577500 3 12.50 2020 17718750 656250 18375000 3.70% 87.500%
630000 4 6.25 2021 18375000 328125 18703125 1.79% 89.063%
682500 4 6.25 2022 18703125 328125 19031250 1.75% 90.625%
735000 4 6.25 2023 19031250 328125 19359375 1.72% 92.188%
787500 4 6.25 2024 19359375 328125 19687500 1.69% 93.750%

* In Block 124724, user midnightmagic mined a solo block to himself which underpaid the reward by a single Satoshi and simultaneously destroyed the block’s fees. This the the only known reduction in the total mined supply of Bitcoin. Therefore, from block 124724 onwards, all total supply estimates must technically be reduced by 1 Satoshi.

Projected Bitcoins Long Term

Supply timeline estimation

Because the number of bitcoins created each time a user discovers a new block – the block reward – is halved based on a fixed interval of blocks, and the time it takes on average to discover a block can vary based on mining power and the network difficulty, the exact time when the block reward is halved can vary as well. Consequently, the time the last Bitcoin will be created will also vary, and is subject to speculation based on assumptions.

If the mining power had remained constant since the first Bitcoin was mined, the last Bitcoin would have been mined somewhere near October 8th, 2140. Due to the mining power having increased overall over time, as of block 367,500 – assuming mining power remained constant from that block forward – the last Bitcoin will be mined on May 7th, 2140.

As it is very difficult to predict how mining power will evolve into the future – i.e. whether technological progress will continue to make hardware faster or whether mining will hit a a technological wall; or whether or not faster methods of SHA2 calculation will be discovered – putting an exact date or even year on this event is difficult.

The total number of bitcoins, as mentioned earlier, has an asymptote at 21 million, due to a technical limitation in the data structure of the blockchain – specifically the integer storage type of the transaction output, this exact value would have been 20,999,999.9769 bitcoin. Should this technical limitation be adjusted by changing the width of the field, the total number will still only approach or be a maximum of 21 million.

Block Reward Era BTC/block Start BTC BTC Added End BTC BTC Increase End BTC % of Limit
0 1 50.00000000 0.00000000 10500000.00000000 10500000.00000000* infinite 50.00000006%
210000 2 25.00000000 10500000.00000000 5250000.00000000 15750000.00000000 50.00000000% 75.00000008%
420000 3 12.50000000 15750000.00000000 2625000.00000000 18375000.00000000 16.66666667% 87.50000010%
630000 4 6.25000000 18375000.00000000 1312500.00000000 19687500.00000000 7.14285714% 93.75000010%
840000 5 3.12500000 19687500.00000000 656250.00000000 20343750.00000000 3.33333333% 96.87500011%
1050000 6 1.56250000 20343750.00000000 328125.00000000 20671875.00000000 1.61290323% 98.43750011%
1260000 7 0.78125000 20671875.00000000 164062.50000000 20835937.50000000 0.79365079% 99.21875011%
1470000 8 0.39062500 20835937.50000000 82031.25000000 20917968.75000000 0.39370079% 99.60937511%
1680000 9 0.19531250 20917968.75000000 41015.62500000 20958984.37500000 0.19607843% 99.80468761%
1890000 10 0.09765625 20958984.37500000 20507.81250000 20979492.18750000 0.09784736% 99.90234386%
2100000 11 0.04882812 20979492.18750000 10253.90520000 20989746.09270000 0.04887585% 99.95117198%
2310000 12 0.02441406 20989746.09270000 5126.95260000 20994873.04530000 0.02442599% 99.97558604%
2520000 13 0.01220703 20994873.04530000 2563.47630000 20997436.52160000 0.01221001% 99.98779307%
2730000 14 0.00610351 20997436.52160000 1281.73710000 20998718.25870000 0.00610426% 99.99389658%
2940000 15 0.00305175 20998718.25870000 640.86750000 20999359.12620000 0.00305194% 99.99694833%
3150000 16 0.00152587 20999359.12620000 320.43270000 20999679.55890000 0.00152592% 99.99847420%
3360000 17 0.00076293 20999679.55890000 160.21530000 20999839.77420000 0.00076294% 99.99923713%
3570000 18 0.00038146 20999839.77420000 80.10660000 20999919.88080000 0.00038146% 99.99961859%
3780000 19 0.00019073 20999919.88080000 40.05330000 20999959.93410000 0.00019073% 99.99980932%
3990000 20 0.00009536 20999959.93410000 20.02560000 20999979.95970000 0.00009536% 99.99990468%
4200000 21 0.00004768 20999979.95970000 10.01280000 20999989.97250000 0.00004768% 99.99995236%
4410000 22 0.00002384 20999989.97250000 5.00640000 20999994.97890000 0.00002384% 99.99997620%
4620000 23 0.00001192 20999994.97890000 2.50320000 20999997.48210000 0.00001192% 99.99998812%
4830000 24 0.00000596 20999997.48210000 1.25160000 20999998.73370000 0.00000596% 99.99999408%
5040000 25 0.00000298 20999998.73370000 0.62580000 20999999.35950000 0.00000298% 99.99999706%
5250000 26 0.00000149 20999999.35950000 0.31290000 20999999.67240000 0.00000149% 99.99999855%
5460000 27 0.00000074 20999999.67240000 0.15540000 20999999.82780000 0.00000074% 99.99999929%
5670000 28 0.00000037 20999999.82780000 0.07770000 20999999.90550000 0.00000037% 99.99999966%
5880000 29 0.00000018 20999999.90550000 0.03780000 20999999.94330000 0.00000018% 99.99999984%
6090000 30 0.00000009 20999999.94330000 0.01890000 20999999.96220000 0.00000009% 99.99999993%
6300000 31 0.00000004 20999999.96220000 0.00840000 20999999.97060000 0.00000004% 99.99999997%
6510000 32 0.00000002 20999999.97060000 0.00420000 20999999.97480000 0.00000002% 99.99999999%
6720000 33 0.00000001 20999999.97480000 0.00210000 20999999.97690000 0.00000001% 100.00000000%
6930000 34 0.00000000 20999999.97690000 0.00000000 20999999.97690000 0.00000000% 100.00000000%

Note: The number of bitcoins are presented in a floating point format. However, these values are based on the number of satoshi per block originally in integer format to prevent compounding error.

* In block 124724, user midnightmagic solo mined a block which caused one less Satoshi to be created than would otherwise have come into existence. Therefore, all calculations from this block onwards must now, to be accurate, include this underpay in total Bitcoins in existence.

Advertisements