Posts

Byzantine Generals Problem and The Double-Spend Debacle

avatar of @edicted
25
@edicted
·
·
0 views
·
7 min read

The Byzantine Generals Problem is a networking problem posed during the birth of the Internet itself. Yep, that's right... all the smarty-pants were thinking about this issue right from square one, and it was thought to be a problem that was literally IMPOSSIBLE to solve. Every year that it went unsolved, it was thought to be even more unsolvable than the year before. After all, if the top minds of the world couldn't crack it after all that time, surely it must be impossible!

Byzantine Generals Problem: Medium.com

It is a fictitious problem, but one of the hardest problems of all time. It was first referenced in the paper titled ‘The Byzantine Generals’ Problem’, published in 1982.

Imagine divisions of a Byzantine army, attacking a completely encircled city. To proceed, the generals of each division, who are dispersed around the city’s periphery, must agree on a battle plan. However, while some generals want to attack, others may want to retreat.

In the official description of the Byzantine Generals’ Problem (which you’ll find on page three of the aforementioned paper), there is a leader-follower set-up. In order to achieve consensus, the commanding general and every lieutenant must agree on the same decision.

Byzantine Fault Wikipedia

A Byzantine fault (also interactive consistency, source congruency, error avalanche, Byzantine agreement problem, Byzantine generals problem, and Byzantine failure) is a condition of a computer system, particularly distributed computing systems, where components may fail and there is imperfect information on whether a component has failed. The term takes its name from an allegory, the "Byzantine Generals Problem", developed to describe a situation in which, in order to avoid catastrophic failure of the system, the system's actors must agree on a concerted strategy, but some of these actors are unreliable.

Byzantine Generals Problem: Coincentral.com

The Byzantine Generals Problem is a term etched from the computer science description of a situation where involved parties must agree on a single strategy in order to avoid complete failure, but where some of the involved parties are corrupt and disseminating false information or are otherwise unreliable.

You’ve come at just the right time – we’ve got this city surrounded but have an unfortunately complicated logistics issue here. We have two armies, one on each side of the enemy city, and we need to attack at the same exact time. The city is strong enough to defend itself against one of our armies, but not strong enough to defend against two at the same time. If we don’t attack at the same time, we lose. And losing sucks.


Now clearly, this is not a problem based in reality.

It's an analogy.

This is a networking problem only. If we actually had an actual city surrounded we wouldn't be sending scouts through the middle of the city, and the city wouldn't allow anyone in or out during a siege to begin with. Coordinating an attack in real life is as easy as sounding a horn and making sure you can trust your allies.

Rather, this is a trust/reputation issue within the confines of a decentralized network. It's actually pretty impressive that people were even thinking about this stuff right from the beginning, and because the problem was so improbable to solve the entire Internet was centralized into the technocracy we see today.

When Satoshi Nakamoto published the whitepaper for Bitcoin, he was laughed off the damn stage. Those who were educated enough to even begin to understand what he was claiming knew that the whitepaper solved the impossible problem of the Byzantine Generals.

Because this was an impossible feat and Nakamoto was an anonymous entity, it's easy to see why it was so completely unbelievable that he had solved it. One would only expect the top minds in the world to come forward with a solve for this and take credit for it themselves. This is the kind of thing you win a Nobel Prize for, after all.

But she did solve it!

An ugly solve, but a solve nonetheless. Anyone with an interest in pure mathematics and definitive proofs would be repulsed by such a fumbling answer, but nobody said it had to be a good solution. It simply had to be good enough.

How? Mining.

Bitcoin mining is a lottery system that secures the network and expends energy in addition to requiring an overhead cost of hardware to mint the lottery tickets. This is how the unsolvable Byzantine Generals problem was solved. Again, it's an ugly solve, but it is a solve.

The reason this post is so appropriate is that I just recently talked about counterfeiting and how Bitcoin has solved that issue as well, which is much more impressive than the idea of a 21M coin token cap.

51% attack

This is the only thing that can break consensus and destroy the Bitcoin network. Even if this happened Bitcoin would have still solved the Generals problem, because this is the most obvious and allowable point of failure; if you can't trust more than half the network then the network is invalid to begin with. It's kind of like how Steem got attacked with sock-puppet witnesses and we had to fork to Hive to correct it. Pretty impressive when you actually think about it we are all still here to tell the tale.

So how is it done?

The 51% attack is also known as the double-spend attack. In order to achieve this attack, one must have enough hashpower to spend Bitcoin and then rollback the chain to a previous block and fork to a new chain. Sounds complicated? That's because it is! (Not really).

Imagine we controlled a huge majority of hashpower for any POW coin. Theoretically, we could mine two different blocks at the same block-height. This means we could mine two different blocks that have the same block number, effectively forking the entire network into two different chains.

How does the network know which fork to pick?

Usually mining software will follow the chain who's difficulty solved the hardest problem. In the context of Bitcoin, this means more leading zeros at the beginning of the block hash. The more leading zeros one randomly gets when constructing these lottery tickets, the harder the solve.

Therefore, if we were able to solve two different blocks for the name blocknum and spend our Bitcoin on both blocks we could theoretically spend our money twice to game the system. This is why centralized exchanges often require THREE "block confirmations", meaning the transaction in question is three blocks deep on the blockchain, which would be INCREADIBLY expensive and risky to double-spend once the transaction is buried that deep.

Why is it risky? Because the amount of energy and time you'd have to spend reversing 3 entire blocks is absolutely massive, and there's also no guarantee you'd get lucky enough to pull it off anyway. This is a lottery after all and block solves are 100% random. By the time you mined 3 blocks to take over the chain Bitcoin may have posted 3 more blocks, meaning you just wasted all your time and money and the chance of succeeding in this attack is even worse than before.

Orphaned blocks

This is the key to attacking the Bitcoin network or any POW coin. We must mine a fake block that we plan on being invalidated, spend our Bitcoin in exchange for something of value that can't be taken away from us (probably crypto), and then allow the block we mined to become invalidated by the other block. In essence, we'd create a temporary fork in the Bitcoin blockchain that would soon be destroyed and no one in the network would continue building from that orphaned block.

It becomes clear that even though this is a "counterfeit adjacent" problem, it is still not technically counterfeiting. This is because at the end of it all the Bitcoin network still has a cap of 21M coins and no extra Bitcoin has actually been minted, we were just sneaky enough to spend our money twice by orphaning the block in which we spent our money and received something of value in return.

How is this scam avoided?

Well, we do what centralized exchanges do: we wait. Every time a new block is created on the Bitcoin blockchain that makes all the older blocks even more secure than they were before (which is actually quite secure). Honestly, this isn't something people have to worry about unless they are accepting payment for a very large sum of money. In fact, vendors who accept Bitcoin or other POW coins as payment in the future will likely allow zero confirmations to occur just to speed things along.

That's right... even if a transaction has simply been broadcasted to the Internet and hasn't even been confirmed on a block yet, that still has pretty good security. Simply broadcasting the operation to the network is going to be good enough for small transactions, as the chance that people are going to try and game the system is pretty low.

Think about it this way: are you going to hire a security guard just because people are stealing from your store? What if the salary of the security guard is more expensive than simply letting a few bad apples steal from you? You're probably not going to engage in such a blatantly losing proposition unless "it's the principal of the thing" is what's driving the decision.

Similarly, why would anyone require Bitcoin confirmations to be secured on the blockchain when they can see that the operation has been broadcast immediately? What are the chances that one of your regulars would walk out of the store and invalidate the transaction before it was put on a block? Probably pretty low... and if they came back to your business you'd obviously have words. In addition, the Lightning Network may solve this problem entirely with instant and cheap transactions (again at the cost of security). Security is only required for huge amounts of money at one time.

Conclusion

So the next time someone tells you that Bitcoin is a bubble and it's value is founded on "nothing", you can tell them actually the value of Bitcoin is that it's literally impossible to counterfeit because it solved a math problem that was thought to be unsolvable for decades.

DECADES

1982-2009, 27 years: Just think about that for a tick. The Birth of Bitcoin was the birth of the decentralized Internet.
This will only be fully obvious in retrospect after it happens.
The value of such a thing is limitless and priceless beyond measure.

Posted Using LeoFinance Beta