8 ms·
Bitcoin and the Byzantine Generals Problem
- gnaritas 13y agoBitcoin 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).
- lukifer 13y agoFrom 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?) Note also that intentional wastefulness shows up frequently in nature: costly signals are honest signals. http://en.wikipedia.org/wiki/Signalling_theory#Costly_signalling_and_Fisherian_diploid_dynamics http://en.wikipedia.org/wiki/Signalling_theory#Costly_signal...
- gnaritas 13y ago> 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.
- lukifer 13y ago> one has to think there are useful hard problems to solve rather than just banging out SHA-256 hashes over and over. 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.
- 3rd3 13y agoWhat about Primecoin?
- lukifer 13y agoSee the discussion above. :) Prime number sequences are unlikely to be "useful" in the same sense as protein folding.
- reginaldjcooper 13y agoUnless I am mistaken, you can verify arbitrary computations[0]. [0] http://arxiv.org/abs/1105.2003 http://arxiv.org/abs/1105.2003
- lukifer 13y agoThe 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!
- tlrobinson 13y agoIs the Primecoin proof of work actually useful?
- gnaritas 13y agoI'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.
- jnbiche 13y agoHow does it progress what we know about prime numbers?
- gnaritas 13y agoFrom https://github.com/primecoin/primecoin/wiki/FAQ https://github.com/primecoin/primecoin/wiki/FAQ "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."
- Renaud 13y agoIt'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.
- zby 13y agoThe 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.
- gnaritas 13y agoThat'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.
- Rhapso 13y agoWe 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.
- cdixon 13y agoWe (a16z) would love to see more innovation along these lines and would be excited to try to help.
- Buge 13y agoYou 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.
- cdixon 13y agoI 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.
- comex 13y agoThat'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.
- krakensden 13y agoI'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?
- sliverstorm 13y agoIt'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.
- eof 13y agoTo 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
- tomp 13y agoBitcoin 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. [1]: http://en.wikipedia.org/wiki/History_of_Bitcoin#The_fork_of_March_2013 http://en.wikipedia.org/wiki/History_of_Bitcoin#The_fork_of_...
- DennisP 13y agoA 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.
- goldenkey 13y agoSo we could say, the newest version of the bitcoin software correctly solves the Byzantine General problem, though older versions faltered. 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.
- buluzhai 13y agohere is a post talk about it http://expectedpayoff.com/blog/2013/03/22/bitcoin-and-the-byzantine-generals-problem/ http://expectedpayoff.com/blog/2013/03/22/bitcoin-and-the-by...
- akandiah 13y agoIs 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).
- meowface 13y agoThis 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. See more here: http://bitcoin.stackexchange.com/questions/658/what-can-an-attacker-with-51-of-hash-power-do http://bitcoin.stackexchange.com/questions/658/what-can-an-a...
- kolev 13y agoI also wonder what impact Quantum Computing would have on Bitcoin. I'm pretty sure NSA uses it already.
- ObnoxiousJul 13y agowell the fiducial (fiduceo I believe in latin) which people believe to have value (hash of hash of ...) requires a lot of computation thus electricity thus resources. Whatever brainwashed geeks thinks computer industry is already using a lot of it, I am pretty confident people would be the surprised at the Total (Real) Cost of Ownership of a bitcoin, and I am absolutely not convinced it beats real money on the long run. And, subsidiary question: will this money scale (in cost of energy)?
- throwawayforhn 13y agoI 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. Make us long time holders rich.
- cdixon 13y agoYes, 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.
- greyman 13y ago> I don't think people should buy Bitcoins for speculative purposes. Why not, if you suppose that its price will go up?
- pmarca 13y agoThat's a brave stand for a throwaway account!
- greyman 13y agoYes, 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.
- 001sky 13y agoThis 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.).
- jackgavigan 13y agoBitcoin 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]: http://blockexplorer.com/q/totalbc http://blockexplorer.com/q/totalbc
- synchronise 13y agoThese 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.
- swswsw 13y agoAt first glance, mining appears to use a lot of energy. But it has a very important property: mining is "fair" in money generation. And being fair may be much more important than the energy consumed.
- wmf 13y agoDepends how you define fair, I guess. Many people complain about the effects of a fixed block reward with ever-increasing difficulty.
- reillyse 13y ago"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?
- andybak 13y agoMaybe you should explain specifically what you find difficult to understand in that quoted sentence?
- deleted 13y ago[deleted]
- reillyse 13y agoTo 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.