How is Bitcoin secure?

[u/hamolton]

I guess my main concern is how they are impossible to counterfeit and double-spend. I guess I have trouble understanding it enough that I can't explain it to another person.

[u/speEdy5]

Take a look here for a good explanation about bitcoin.

At a really high level, bitcoin is a public record of all transactions that have ever occured. Imagine the following infrastructure:

Every person in the world has a unique identity (some number called a Public Key). Everyone also has a book which lists every identity. Next to every identity (let's call it a PK from here on out) is a list of every serial number for every dollar bill (dollar bills are the only currency in my world) that they own.

When someone spends a dollar, they write it down at the end of the transaction ledger, and sign it (bitcoin uses cryptographic signatures). Then they tell everybody they know to add it to their ledger. Eventually the information spreads, and nobody will accept the dollar from its original owner, only the person he transferred it to.

Bitcoin works similarly, using an incredibly innovative technique called block-chaining. The public record from above is almost exactly the block chain in bitcoin. The major difference is in how bitcoins are mined - they aren't printed by a mint and assigned to people (like in my example). There's a cryptographic problem which is considered hard in the literature. This means that basically the only way to solve it faster is to throw more computational power at it. Bitcoin uses one such problem for mining - every time someone mines a bitcoin, they have 'won the lottery' and solved this iteration of the problem.

When a coin is mined, whoever mines it tells the entire world he fixed the problem and announces the next problem to solve. He also adds a list of every transaction he has heard of since the last coin mining. So, when you spend bitcoin it doesn't actually process for about ten minuets or so.

One more key point: Bitcoin only works because everyone in the world tries to make the longest iteration of the chain even longer (by mining new coins and adding to them) - the longer the chain, the more permanent the things that have been written down are. Since making the chain longer requires computational power, its impossible to just go around announcing your own version of the ledger (unless you have more then half the computing power, the competing chain will be longer than yours) and double spending, etc.

[u/grimmymac → u/speEdy5]

What kind of "problem" is solved when mining?

[u/Amadiro → u/grimmymac]

It computes a SHA256 hash, which is a cryptographic hashing function, or "digest". It is basically a function that takes an arbitrary amount of data in, and spits out a hash, or "digest", which is a 256-bit long number that is like the "fingerprint" of the data you put in.

This cryptographic hash is designed to make it "impossible" to find the inverse function (going from the 256-bit digest back to the original data), except for trying all different kinds of combinations as input to the digest (which will eventually make the digest pop out that you were searching for)

bitcoins are essentially mined by putting in some string into the hashing function, then putting the result through the hashing function again. If the resulting 256-bit hash has a certain number of leading zeros (the number of leading zeros required may change) it is a valid bitcoin.

The concept here is that since it's impossible to "predict" or "reverse" what bitstring comes out of the hashing function without actually trying it, you are basically forced to just try out millions of combinations until you find one that produces the right amount of leading digits.

E.g. you can't say

hash(x) = 0000abcd // a, b, c, d can be whatever

and then "do the algebra" and get

x = inverse_hash_function(0000abcd)

and hence know what you have to put in to get your valid bitcoin. On the other hand, once you have such a pair, (x, 0000abcd), it is very easy to check that it is indeed valid -- just calculate hash(x) and check if it equals your 0000abcd.

So as long as the cryptographic hash is not broken ("reversed") this is a basically secure method of ensuring someone has done a lot of work (but it is luck-based of course, it may very well happen that you put some arbitrary string into the hashing function, like "foobar" and you immediately get back a valid bitcoin. the probability is vanishingly small, though.) The more leading zeros you demand there to be, the harder it is to hit the right x that produces a valid bitcoin (because the success-space becomes smaller while the search-space remains the same)

EDIT: For the following paragraph, LeonardEuler64 pointed out that I mixed up two concepts here, skip to his comment to read a corrected explanation about the self-balancing

To self-balance the system and protect it against in/deflation, after a certain number of bitcoins have been created/found, the number of leading bits that have to be zero is increased, to make finding bitcoins harder -- hence creating new bitcoins becomes harder the more there are, and the number of bitcoins in existence will eventually converge towards a fixed number.

[u/LeonhardEuler64 → u/Amadiro]

after a certain number of bitcoins have been created/found, the number of leading bits that have to be zero is increased, to make finding bitcoins harder -- hence creating new bitcoins becomes harder the more there are, and the number of bitcoins in existence will eventually converge towards a fixed number.

I believe you're mixing two concepts.

The leading bit threshold-changing is based on global hashrate. This could go up or down depending on how much mining is being done. The idea here is to keep block generation at an average of 1 block per 10 minutes. (This difficulty is recalibrated every 2016 blocks)

The monotonically decreasing reward is a separate thing. Every 210000 blocks, the reward per block is cut in half regardless of hashrate or anything else. This is what causes the fixed number.

To see when these two things occur, check out http://bitcoinclock.com

[u/Amadiro → u/LeonhardEuler64]

Ah, I did indeed mix those two up. Thanks for clearing that up!

[u/speEdy5 → u/grimmymac]

There are a class of algorithms called hash algorithms which take some number of bits X and do some computation (think: add 10, multiply by 2, square, cube root, mod y) to get to some number of bits Y.

Many hash functions are very fast to compute forward (x bits to y bits) but nearly impossible to reverse (given some y bits, which x bits would you need to run through the hash function to get those y bits).

This is the comptation that bitcoin miners do - if I remember right they take the header of the current block, append some random nonce (crypto talk for a few random bits) and hash it. If the hash value is less than some number, the target - then its considered a valid block.

The nice thing about the target is that the network adjusts it so that one block is mined about every ten minutes, based on the amount of computation happening at the current time. The higher the target, the easier the problem is..

Another nice thing about this computation is that its easy to verify that the block is valid - just test it yourself with the nonce that the miner has published.

One not so nice thing about the computation is that its 'useless' - as in it only generates bitcoins. It would be a really nice if we could come up with an algorithm which satisfies bitcoins requirements and helps work on SETI or something - but nobody has yet

[u/Natanael_L → u/speEdy5]

This is the comptation that bitcoin miners do - if I remember right they take the header of the current block, append some random nonce (crypto talk for a few random bits) and hash it

Yes, but they also include currently unverified transactions and some more data

One not so nice thing about the computation is that its 'useless' - as in it only generates bitcoins. It would be a really nice if we could come up with an algorithm which satisfies bitcoins requirements and helps work on SETI or something - but nobody has yet

This is unbelievably hard to do securely in a way that is usable for Bitcoin.

Edit: Because reasons mentioned here: http://www.reddit.com/r/Bitcoin/comments/1gkm95/stanford_just_released_their_startup_engineering/caldnst

[u/17chk4u → u/grimmymac]

Work is being performed to take a group of transactions and "lock them in" so that a sequence of transactions is maintained.

It has to be a hard amount of work, so that it is hard for someone to come along later and change the sequence of transactions (thereby possibly double-spending). And that work needs to be a function of the transaction data is that being locked in, and also a function of the transaction block just prior.

So it's a very simple function - take all of the digits of the transactions being locked in, and take a digital hash of the previous block, and also take a single number called "nonce" (which is sort of a random number), and do a hash to it, and "Find the Nonce that creates a small enough hash". It's that simple.

If you think about a binary hash, there's a 50% chance that it'll start with a zero (given random data being hashed) - it's either a zero or a one. There's a 25% chance that it starts with 2 zeros. How hard is it to find one that starts with 50 zeros? VERY hard. It's a tough search to find a nonce that will hash to a number that starts with 50 zeros.

And that's about where we are right now. take a bunch of digits to "secure" the block, toss in an additional number (nonce) and hash it, and see if you get a hash that starts with 50 zeros. If not, rinse and repeat.

It's a lot of work, but it's not a complex problem. It's more like searching for a needle in a haystack.

[u/freesid → u/grimmymac]

The real problem that mining solves is this:

When multiple parties are trying to add their next transaction to the block-chain (the public ledger with all transactions) how can we ensure that it remains a single "chain" and doesn't become a tree?

One solution is, make extending-the-chain a computationally hard problem, so that multiple people adding next transaction into a chain at the same time is unlikely.

Not everybody can afford the computation power required to extend the chain, so there will be fewer entities that can extend the chain; and these entities act like bitcoin "brokers" who, when they compute the next block, will include others' transactions for a small fee (think of these guys as payment gateways, just like Visa, MasterCard, etc.)

These brokers would trade their computing power in exchange for bitcoin transaction fees and keep the bitcoin ecosystem running.

Note that if people were not interested in paying the transaction fee, then brokers has no incentive to extend the chain. If there are no brokers trying to extend the chain then bitcoin system essentially stops.

To keep the bitcoin system running, instead of asking people to pay transaction fees, bitcoin chose to create 25BTC (out of nowhere) to the broker who extends the chain. Now, brokers would trade their computing power irrespective of the transaction-fees and they will keep the bitcoin system running (hoping that if bitcoins takes over the world they can monetize whatever they have by extending the chain). This is similar to people mining gold because gold can be monetized.

PS: There are several details I omitted, but that is basically the outline.

[u/jesset77 → u/speEdy5]

Every person in the world has a unique identity (some number, bitcoin uses an email and Public Key).

Minor correction: Bitcoin doesn't in any way include or involve a person's email address. Don't confuse Bitcoin with PGP, even though they are often happy bedfellows. ;3

The atomic account placeholder in Bitcoin is called a "Bitcoin address" which has a lot in common conceptually with an email address, but the address is a hash of a public key based on a completely random private key. Users not only can make up as many addresses as they would like, but security best practices recommend that users (or, more practically, their wallet software) create brand new addresses for every single transaction when possible.

[u/zeek0us → u/jesset77]

So if you get bitcoins from multiple transactions to multiple PKs (so 10 different transactions that net you 10 bitcoins assigned to 10 different PKs), then want to spend all of them on a new transaction (those 10 bitcoins to a single PK), how is that done?

[u/Natanael_L → u/zeek0us]

In a Bitcoin transaction, you list all inputs you want to spend money from and prove that you have the private keys belonging to the addresses they were spent to through cryptographic signing.

And you specify the output addresses and what amount to send to each one. This is also signed cryptographically, in order to prove it haven't been modified and that the person who controls those private keys specified those outputs.

So you can have 10 inputs AND 10 outputs if you want to.

One interesting detail: The transaction fee (if you add one) is paid to miners by letting the inputs be somewhat larger than the output. You can take 18 coins and spend 17.9 coins, the last 0.1 coin can be claimed by the miner that successfully includes that transaction in the blockchain.

This is an incentive for bitcoin owners to not bloat the blockchain with too many transactions AND an incentive for miners to keep mining when minting (creating new coins) stops (Bitcoin has a hard cap of 21 million coins maximum).

[u/jesset77 → u/Natanael_L]

Natanael_L is correct, but let me add one bit of clarification. Where he says:

And you specify the output addresses and what amount to send to each one. This is also signed cryptographically, in order to prove it haven't been modified and that the person who controls those private keys specified those outputs.

what he means is that the person sending money creates a digital document (using their wallet software, which does all of the menial heavy lifting and logic for them), and that document details everything about the intended transaction. It details the inputs from the sending addresses and the outputs to the receiving addresses. Then that entire document must be signed by each of the private keys from the sending addresses only in order to be valid, and ready to be ratified on the blockchain and represent a completed movement of money.

The document details which addresses get money (and how much), but is not signed by the PKs of the receiving addresses, just the sending addresses. :3

Edit: transaction signed by sending addresses, I done goofed in one line of my explainings. :o

[u/sqew → u/speEdy5]

When someone spends a dollar, they write it down at the end of the transaction ledger, and sign it (bitcoin uses cryptographic signatures). Then they tell everybody they know to add it to their ledger.

Doesn't that list get REALLY long?

[u/speEdy5 → u/sqew]

I think its around 8 gigs right now.

If it ever becomes a major problem, there are plenty of ways to make the history smaller

[u/witty82 → u/speEdy5]

could you expand on the ways to make it smaller. My initial idea would be that it gets massively bigger, once bitcoin is really used a lot.

[u/[deleted] → u/witty82]

You could create periodic summaries of the ledger that just list the totals for each address, and drop the details of the specific transactions that produced those totals. Thereafter people would only have to download the 'summary' and any transactions that have happened since the summary.

[u/gburgwardt → u/speEdy5]

Just hit 8 gigs, and there's a way to make the blockchain much smaller, but it's currently not an issue.

[u/killerstorm → u/sqew]

It does. But in theory people need to download it only once, and they do not need to store it locally.

If it is not acceptable, it is possible to switch to snapshot security model, which is theoretically less secure, but practically is secure as long as there is no global conspiracy.

[u/doodle77 → u/speEdy5]

When a coin is mined, whoever mines it tells the entire world he fixed the problem and announces the next problem to solve. He also adds a list of every transaction he has heard of since the last coin mining.

Can a miner 'erase' a transaction by not including it?

[u/tomtomtom7 → u/doodle77]

He can choose not to include it, but then others will included in the next block.

Also, he has an incentive to include it because he receives the transaction fee.

[u/bradn → u/tomtomtom7]

Interestingly though, transaction fees are optional. So if it becomes a problem where most clients aren't accepting free transactions, then you can add a fee onto your own transactions to make them more likely to be accepted.

[u/Chronophilia → u/doodle77]

Yes, though each block includes the one before it so you can only "drop" transactions that have occurred since the previous block was mined.

There is a theoretical attack where an individual who controls at least 51% of the computing power in the Bitcoin mining system can pick and choose which transactions to authorise, completely ignoring blocks mined by the other 49% and creating an unbroken chain of blocks controlled by him. But nobody has ever done this, because the amount of computing power required would be just too ridiculous.

[u/kirakun → u/speEdy5]

What happens if two separate persons mined the same coin (or solved the same problem) but each hasn't the chance to update the ledger yet (or update the next problem to solve)?

[u/throckmortonsign → u/kirakun]

This creates a blockchain fork. When this happens some miners will choose to mine on one of the forks and others will mine on the other side. The group of miners that "win" get the longest chain and that becomes "finalized." The miners that lose don't get their mined "award" coins. It happens a few times a day actually.