Bitcoin and the Byzantine Generals Problem
nonchalantrepreneur.com
nonchalantrepreneur.com
The "consensus" is intrinsically linked to the "math problem" so that the generals will always "trust" the chain-of-answers which is the longest; as it would be impractical / impossible for an attacker to counterfeit the long-chain-of-answers.
Bitcoin uses sha256(sha256( x )) < `target` as its "math problem" where X contains the a hash of the previous "consensus" and new transactions which should become part of the new "consensus". `target` is adjusted over time
[1]: http://en.wikipedia.org/wiki/History_of_Bitcoin#The_fork_of_...
So I guess you could say it only solves the problem when everybody's software implements the same protocol.
And this could be the case ad infinitum if the protocol needs to be changed due to newly discovered flaws.
In summary, unless there are no bugs in your p2p software, it's very hard to solve the Byzantine General problem without outside consensus.
So what it showed was that it's hard to reach consensus between two groups who aren't running the same protocol. Bitcoin is pretty conservative about protocol changes for this reason, though they've worked on getting better at managing it.
This kind of topic is worthy of a thesis. Thoughts?
Another interesting angle is, that in case of Bitcoin, both groups have vested interest to cooperate with the other group and having the matter resolved as soon as possible; that's what actually happened in March. It seems to me like a variant of the "Prisoner's dilemma".
This is what I think that the "hostile takeover" is highly unlikely (in Bitcoin scenario), since that would very quickly brought the BTC value down. So like in the Prisoner's dilemma, both groups will become silent and cooperate, rather than "betray" the other.
Here I dug up the explanation of the Satoshi himself:
http://www.mail-archive.com/cryptography@metzdowd.com/msg099...
Imagine 10 generals in the network all trying to agree on a time of attack. Each simultaneously sends 9 couriers to the other generals suggesting an attack time. That's 90 couriers with 10 different messages all pinging around the system simultaneously. Each general receives 9 messages at roughly the same time, and either has to choose one to sign and rebroadcast, or cheat and sign multiple and rebroadcast them. There are too many options available at any given time, and odds of reaching consensus aren't good.
However, by introducing a time delay you slow the rate of message passing enough to be manageable - now's there's only 9 couriers and 1 message pinging around the system at the same time. All nodes in the network work the same problem, but only one will find a solution first and broadcast it, and with the time delay there's enough time for that solution to disseminate through most of the network before another node discovers another solution and broadcasts it. By the time the second and subsequent solutions are found, the the first has disseminated to enough nodes that they've already incorporated it into the next proof-of-work, and reject subsequent solutions to the prior PoW.
Say that after some time a block that is long enough is made by some general A and is distributed to generals B and C. General D doesn't get it though - his messenger is killed in transit. He helped make an earlier block, but has never seen the fully completed block.
How do the other generals know that he hasn't got the final block that is long enough?
Or is it just the case that a majority of generals know when to attack? I thought it had to be all of them, but maybe that's the two-general problem and Byzantine-general's is an easier problem. I was pretty sure there were multiple good proofs of the impossibility of a solution.
The key point is that after 2 hours, all of the generals can independently assess, by examining the previously mined blocks in the chain they are working on, how much CPU was spent working on the solution, and can "see" how many nodes are in the network, and hence can see if all the nodes have worked on this solution (if yes, they all know of the arranged time of attack).
This doesn't fully solve the problem (one general could be rouge, or one might be killed just before the attack, ...) but it at least raises the chances :)
That's the thing about BG; you can keep increasing the chances, but if your requirement is that you must be certain that all the other generals will attack, and at the same time, then we know of no solution. We also have more than one good proof that this is impossible.
I think what happens here is that any node that doesn't get the message due to lost message, does not advance to the next block, and hence is working on a shorter chain than the nodes that got the message. Eventually it will receive another message with a longer chain and be forced to abandon its own work and adopt the new longer chain. It's highly improbable that nodes working on shorter chains could ever catch up to those working on the longest version.
There may be some threshold of lost messages where the system begins to break down, but assuming no intelligent attacker is behind it and the losses are random, they affect the whole system, not just the prime chain. The shorter chains would be roughly equally affected.
>How do the other generals know that he hasn't got the final block that is long enough?
He keeps working on whatever he has until he receives a longer blockchain from neighbors, which forces him to abandon his shorter one and start working on the longer one right away.
>Or is it just the case that a majority of generals know when to attack? I thought it had to be all of them, but maybe that's the two-general problem and Byzantine-general's is an easier problem.
Eventually it is all of them. The big difference between bitcoin and the theoretical BGP or TGP is that the theoretical problems have an end state where it is simply good enough for a majority to decide on an attack time, they attack, win, share the spoils, and the process is over. Simple majority is all that was needed.
Bitcoin takes that a step further and never stops. As soon as it reaches a simple majority decision, all nodes abandon their own work and adapt that decision - the longest blockchain - as soon as they receive it, and the process starts over from that new point. Each solution creates a longer blockchain, which forces unaninimity.
So this is how it goes. a16z invests in Coinbase, so cdixon posts supportive posts regarding bitcoin.
We can now safely expect more and more HN readers to buy bitcoins because of the fear of missing the bitcoin train, and bitcoin detractors will soon look like iPhone detractors in 2007. That means that no matter what the value of bitcoin is, you should buy some, because the whole SV is soon going to be on it.
For the fist time on HN, a significant part of what hits the front page are posts about an asset that you can buy simply, and will likely make you a millionaire in a couple of years without creating any value. This is as great as it is sad. Enjoy it.
Make us long time holders rich.
I am interested in Bitcoin as a new payment system / economic protocol for the Internet. I don't think people should buy Bitcoins for speculative purposes. On the other hand I'd love to see more developers build things on top of the Bitcoin protocol. My job is to invest in new technologies and I believe Bitcoin is one of the most interesting new technologies in the past 20 years.
Why not, if you suppose that its price will go up?
I do think that a hybrid proof-of-stake system is probably superior and more efficient. But bear in mind that capitalism involves lots of waste, from high-frequency trading, to plastic doodads that wind up in the trash, to the vast majority of advertising and marketing.
I'm absolutely in favor of a Star Trek / Buckminster Fuller neo-communism, if it can be achieved. In the meantime, we have to fail forward and innovate as best we can, and I think proof-of-work cryptocoins are far less wasteful in toto than the current global banking system. (What do you think it took in terms of energy and waste products to manufacture and distribute the dollars in your wallet?)
Note also that intentional wastefulness shows up frequently in nature: costly signals are honest signals. http://en.wikipedia.org/wiki/Signalling_theory#Costly_signal...
Maybe, maybe not, I don't think anyone's crunched enough numbers to make a reasonable measure of that yet.
> (What do you think it took in terms of energy and waste products to manufacture and distribute the dollars in your wallet?)
I doubt either of us know.
I'm a Bitcoin supporter, but one has to think there are useful hard problems to solve rather than just banging out SHA-256 hashes over and over. If that's true at all, then Bitcoin is wasteful.
I sincerely hope that a truly useful proof-of-work can be discovered. It would be a very big deal.
The problem is, the work has to be reliably verifiable, and easier to verify than just doing the work over again, which is why hashes are a good fit.
There are curecoin and gridcoin, which base a large portion of mining profits off Boinc credits. Kinda defeats the point of being decentralized though...
"Primecoin network searches for special prime number chains known as Cunningham chains and bi-twin chains. The distribution of these prime chains are not well-understood currently as even for its simplest case twin primes their infinite existence is not proven. The distribution of primes has been one of the most important discoveries in arithmetic, and the study of prime chains traces its lineage to the work of Riemann and prime number theorem, with connections to the deeper nature of the seemingly random pattern of prime distribution. Prime distribution is not just an abstract interest of mathematicians. Riemann's study revealed connections between Riemann zeta function and prime distribution, whereas later on Riemann zeta function has been shown to be highly relevant in other scientific disciplines such as physics, thus the study of prime distribution is an important part of the foundation of modern sciences."
Do we think the same when we talk about all the vast amounts of energy and money spent trying to secure bank transactions? It's only a waste of money and energy if you consider that these things have no value.
Even if we only consider the protection of physical money and valuables: how much energy is spent in making these vaults? How much money does it cost to protect them? It's only worth it if you consider that what they protect is more valuable than the cost of protecting them. In the end, whatever is in that vault is just made of bits of metal and dead tree pulp.
Here is a probabilistic solution to the problem.
1) Each General sends n messages to all the other generals. 2) After a time period y all the generals count their messages and decide how to act.
3) This is not a "solution" to the original problem. If we lose sufficient messages we may "attack" at the wrong time. However it is a probabilistic solution because as n & y increase we are less likely to make the wrong decision.
There are lots of known probabilistic solutions and while I'm a fan of the Bitcoin Protocol the existence of another doesn't change anything for computer scientists.
<One thing I haven’t seen emphasized, however, is the extent to which the whole concept of having to “mine” Bitcoins by expending real resources amounts to a drastic retrogression — a retrogression that Adam Smith would have scorned.>
This he calls out as completely misplaced:
How much does the existing banking/payment infrastructure cost? One reasonable measure are the fees charged. Standard online payment fees are 2.5%, not including the added costs fraud (chargebacks plus transactions blocked out of fear of fraud).
And he's right. but The real cost of running a market is not, however a bid-ask spread. And he gets at the point, but its not clear, here:
Bitcoin payment fees are close to zero and fraud is impossible since Bitcoin is a bearer instrument.
The [true costs] of running a market are thos that instill [trust] in the market system. That is, what is commonly called "transaction costs" in economics. But these are not literal costs, which tend to be rent-extraction wherein the transaction is merely instrumental to effect a scaling biz model.[1] The true transaction cost of "effective honesty" are to be found in "governance costs", that is...the cost of lawyers. And thus more generally, and indirectly, the primary purpose of government (eg schooling, police, courts, national defense). So, it is worth putting in context the "cost" of mining bitcoins here. The "innovation" that is provided is provided also at this seperate level of abstraction, far away from the "overhead" style transaction costs in a literal definition. And to the authors point, these are both measurable and large; such an innovation thus actualy saves wated resources that would otherwise be deployed (think of all the energy spent on anti-spam and anti fraud by CCs...that 2.X is ~mostly profits tho).
In any event, interesting topic and interesting post. And I think he intuits the right answer, but the exact words put forth sort of murky the point abit, IMHO.
[1] eg 7% of an IPO to a Bank, X% to your real estate broker, 1/8 of a point in a pre-decimalized stock market, 2.x% on a credit or paypal transaction.).
As I write this, there are 12,130,075 bitcoins in existence[1]. Over the coming year, approximately 1,314,000 bitcoins will be "minted" (25 new bitcoins every ten minutes). If Bitcoin were a real currency, that would equate to an inflation rate in excess of 10%. So, in effect, every bitcoin owner would be paying 10% of their Bitcoin wealth for "free" payments, whether or not they actually make/receive any payments or not.
However, to be useful, while bitcoin can replace some of parts of this, there is still the need to be able to enforce contracts made using bitcoin, so a bitcoin economy would need to reuse much of that infrastructure.
Besides, it's not particularly relevant, because for most people, escaping the costs of the infrastructure that creates trust in our fiat economy is not practical, while escaping the costs of the infrastructure that creates trust in bitcoin is trivial - just don't use it.
What I wonder about is the size of the blockchain. Bitcoin is young and fringe, and the blockchain is already several gigabytes. What happens when everyone and their brother uses Bitcoin, every day? How large will a few decades of frequent, widespread global usage make the blockchain?
Supposedly VISA processed 20 billion transactions in 2006. To my knowledge bitcoin transaction occupies ballpark 1kB in the blockchain; that's 20-100TB/year, and it could be even larger when you add money-moving transactions. That storage need can be met, but only by people making a big investment in the network- in other words, centralizing the trust of the network to players with deep pockets and compromising one of the original goals of BTC.
1) Developer's are working on software to prune the transaction tree so miners only have to store the addresses that have nonzero balances.
2) Miners can increase their minimum transaction fees to cut down on transaction volume.
3) Moore's law (and similar) conspire to keep an ever-growing blockchain storable and manageable.
http://en.wikipedia.org/wiki/Mark_Kryder#Kryder.27s_Law
A PhysOrg.com article reports on a 2009 study by Mark Kryder. According to the report, if hard drives continue to progress at their current pace, then in 2020 a two-platter, 2.5-inch disk drive will be capable of storing more than 14 terabytes (TB) and will cost about $40.
This only works as long as bitcoin climbs in value vs the rest of the world, no? Wouldn't a long period of price stability break this down?
> What I wonder about is the size of the blockchain. Bitcoin is young and fringe, and the blockchain is already several gigabytes. What happens when everyone and their brother uses Bitcoin, every day? How large will a few decades of frequent, widespread global usage make the blockchain?
My theory is that it will force Bitcoin to slowly re-centralize, with people who provide web interfaces to wallets shouldering the majority of the burden.
Credit card companies? No. Banks? Yup. http://en.wikipedia.org/wiki/Fractional-reserve_banking#Mone...
For the Bitcoin network to properly operate, it requires at least 51% of the computing power of the network to be "good", well-behaving nodes. That 51% means 51% in terms of block-mining. So, computing power in this case means "ability to find plaintext that results in a certain double-SHA-256 digest".
Therefore, Bitcoin has not come across a completely rock-solid solution (as with many cryptographic protocols), because a determined attacker or group of attackers could theoretically achieve control of the network with sufficient computing power. At this stage though, it's difficult enough to basically be considered infeasible, unless a global superpower tried to tackle it.
See more here: http://bitcoin.stackexchange.com/questions/658/what-can-an-a...
mining is "fair" in money generation.