To the uninitiated, bitcoin solves the byzantine general's problem by having each "general" work on a mathematical problem that is known to take a certain average amount of time; and, when they solve the problem pass their solution onto the other generals who will then incorporate the answer to the previous problem into a new problem.
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
Bitcoin doesn't really solve the Byzantine General's Problem, as demonstrated by the March 2012 network split [1], which was later resolved by consensus between users (lead developers and biggest miners) using communication channels outside of the Bitcoin network.
A cursory look at your link reveals that it was caused by an incompatibility between different versions of the bitcoin client; the older client wouldn't accept blocks as large as the later one. People downgraded to the older version, and then "The network reached consensus and continued to operate as normal a few hours after the split."
So I guess you could say it only solves the problem when everybody's software implements the same protocol.
No, either version alone solved the problem just fine. It was just when some people had one version, and other people had another version, that the problem arose. The solution was actually to revert to the older version. The new version wasn't buggy, but had made a small and intentional change to the protocol.
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.
Right on. So basically, Bitcoin solved part of the problem. The bigger unsolved, ie. not automated, problem would be adaptive updating with care to the intricacies of the diff between old and new behavior. And security in the process to prevent a mutiny or hostile takeover in the vulnerable split state. Obviously updates can't be atomic with so many players.
This kind of topic is worthy of a thesis. Thoughts?
Yes, this is something above the Byzantine Generals Problem - that scenario didn't take into consideration, that the general's "agenda" is changing over time.
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.
I still don't understand how it solves it. I get that you can agree a time, but how does it solve the problem that each general needs to be certain that all the other generals are also certain? I may have seen a completed block chain for the attack and time, but how do I know all the other generals have also seen it? I know they signed part of it, but how do I know the completed chain then got back to them? If it didn't they're not going to attack and my army will be destroyed.
The time delay introduced by the proof of work is the key to all your questions.
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.
I still don't see the solution - doesn't any solution have to solve the problem of messages being lost?
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 basic idea is (based on Satoshi's explanation linked from a nearby comment) that each general i proposes some time T_i, where T_i - now > 2 hours and starts solving the problem using the value T_i. If it finds a block, it broadcasts it. After some time (e.g. after 2 hours if each block is expected to be mined in 10 minutes) there is an overwhelming probability that all generals have synchronized and are working on the problem with the same initial value T_n for some n (they synchronize by always working on the longest chain).
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 :)
Well if it doesn't fully solve the problem, does it solve it at all?
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.
Right, but the assumptions of the BG problem are also a bit harsh for the real world; network exhibits latency and/or splits, which are followed by joins. If two servers cannot communicate (ever again), then you have bigger problems than simply "synchronizing attacks". For the usual problems of varying latency and some dropped messages, the proof-of-work, coupled with a cryptographic authentication, will suffice for eventual consistency.
>I still don't see the solution - doesn't any solution have to solve the problem of messages being lost?
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.
As problems get more difficult, I think there will be less and less proof-of-work, and people will see less and less of an incentive to keep miners online. Doesn't this mean that security begins to break down as people give up on mining?
Miners are paid in two ways - from creating new bitcoins and from transaction fees. The transaction fees are small but add up to enough to make it worth mining.
I would like to warn those who don't know that the author of this post has vested interest in bitcoin. It doesn't mean anything per se, but you might want to take those articles with a grain of salt.
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.
Yes, our investment was very publicly disclosed on my blog, Coinbase's blog, and multiple news sites. Also, I was posting positive things on my blog about Bitcoin long before I (or a16z) had a financial interest.
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.
Yes, indeed. It is quite difficult to stay neutral when you invested into bitcoin. But it is also true the other way - some people have vested interest for bitcoin to not succeed, and are making statement to mainsteam media, which are not based on a rational understanding of this new technology.
We have noticed, and It lets you do a lot a previously impossible things in decentralized computing. Give folks a few more months to polish proof of concepts.
Bitcoin mining is wasteful compared to some of the alternatives, solving useful hard problems as proof of work (Primecoin) or using a proof of stake system to remove the need for relying so heavily on energy wasting mining (Peercoin).
From what I understand as a layman, it is overly generous to call the prime number sequences found by PrimeCoin "useful".
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?)
> I think proof-of-work cryptocoins are far less wasteful in toto than the current global banking system.
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'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.
There are curecoin and gridcoin, which base a large portion of mining profits off Boinc credits. Kinda defeats the point of being decentralized though...
The abstract says that "a practical general-purpose protocol for verifiable computation may be significantly closer to reality than previously realized". This should be interesting though, thanks for sharing!
You have a fair point, but I claim for a proof-of-work computation it might be good for it to be a bit unpractical. (Depending on the parameters, this paper is on my reading list but I haven't gone through it yet.) I think it's incredibly interesting also, in any case I hope you enjoy the paper :)
It's only wasteful if you consider that bitcoin is of no value.
If you only look at bitcoin as a money transfer system, requiring computationally difficult proofs is at the heart of what makes the system trustworthy.
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.
I'd imagine it'll have uses in future encryption potentially, but at the very least it has scientific value in progressing what we know and can prove about prime numbers. That's more useful than countless SHA-256 hashes. Securing the network and progressing science is greater than just securing the network; especially since doing so uses lots of real resources in terms of energy.
"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."
The problem with Peercoin is that it is centralized by the reliance on checkpoints. That makes it completely missing the point - after all you can have a centralized crypto-coin without mining at all. I am still waiting for a true decentralized proof of stake coin.
That's a protection against attacks until it grows big enough, so no it's not missing the point, the checkpoints are to be removed once it's safe to do so. Yes that makes it risky for now, but it will be decentralized completely soon.
"Before the Bitcoin protocol was invented, most computer scientists thought a system like Bitcoin was impossible because of a famous problem in computer science called the Byzantine Generals Problem." ... wait what?
To elaborate a little more, because there seems to be tons of discussion about this when there really shouldn't be.
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.
This section on the "costs" of mining bitcoin is well raised and relevant>Here is the passage:
<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.).
Bitcoin payment fees may be close to zero at the moment but that's only because miners get paid with newly-minted bitcoins.
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.
1. Those 10% are per year, not per transaction.
2. This kind of inflation is one of many factors that is already incorporated into the market value of Bitcoins.
This is a fantastic conceptual point - that the true cost of a system needs to include the infrastructure that creates the trust, and we have a complex and expensive legal, enforcement and legislative system creating the trust in our normal fiat based economy.
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.
Yes, but the purpose is not to 'escape' the infrastructure costs, but rather to 'optimize' them...by keeping them low. So, in a general sense, self-regulating features of an economy (eg, transparency) create a "remedy" for otherwise more expensive-to-monitor arrangements. By increasing the opporunity set of remedies, your system optimizes to a lower-cost-base. That is to say, a 'remediable' inefficiency is different than one which there is no better option. The idea is that credit cards are a net-postive addition vs cash, because they create benefits to the consumer. These benefits are also the reason why the merchants pay (rents) to the CC companies. The "lost business" would be greater than if they did not exist. But again, here you are seeing the level of CC payments is a function of value added and costs avoided. It is not the case that they are really a measurement of the governance costs of the network (ie, those are at once a subset--anti-fraud--and on the other mostly external and borne by others)
These are exactly the sorts of reasons why the more energy efficient Proof of Stake (PoS) was envisioned and implemented into several cryptocurrencies, like Peercoin and Novacoin.
You can't measure the bitcoin infrastructure cost by the fees the miners charge. Miners are mostly paid with newly generated coins. Credit card companies do no have the luxury to create new money, so of course they will charge higher fees.
I agree it's imprecise. But I'd argue the de facto fees in the existing system are much higher than 2.5%. The biggest cost are all the transactions that should happen but don't. Most merchants/payment companies block payments from dozens if not hundreds of countries due to fears of fraud.
That's only indirectly related to Bitcoin's use of proof of work, though. While Bitcoin's overall design has advantages and disadvantages w.r.t. security, I don't know why an irreversible version of the current system wouldn't similarly be able to reduce fees without needing to "waste" CPU power computing hashes.
I've been wondering about the impact on the network when the end of bitcoins that can be mined comes within sight. Is the computational load going to be taken over by centralized wallet stores like Coinbase?
It's supposed to be a limit function, right? Payout will be ever-decreasing, and difficulty will adjust to keep mining modestly profitable forever.
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.
> It's supposed to be a limit function, right? Payout will be ever-decreasing, and difficulty will adjust to keep mining modestly profitable forever.
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.
No, bitcoin doesn't have to keep climbing in value. The mining difficulty can be adjusted downwards as well as upwards, so even as payout decreases and/or BTC value drops, mining will remain modestly profitable.
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.
Huh? 1tb hdd was released in 2007, 2tb in 2009 and 4tb in 2011. Looks exactly like Moore's law to me though we've been set back by Thai floods of 2011.
Is there a good explanation on how bitcoin addresses the problem out there? I haven't come across a simple explanation that validates the approach (in my mind at least).
This doesn't answer your question specifically, but:
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.
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