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:
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
FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
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:
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 =
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.
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)
h = 1 + (1 + 2)
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.
Currency with Finite 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. 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.
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|
* 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
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|
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.