Skip to content

Instantly share code, notes, and snippets.

@oleganza
Last active October 14, 2024 19:22
Show Gist options
  • Save oleganza/8cc921e48f396515c6d6 to your computer and use it in GitHub Desktop.
Save oleganza/8cc921e48f396515c6d6 to your computer and use it in GitHub Desktop.
Proof that Proof-of-Work is the only solution to Byzantine Generals' problem

In reply to "@Vlad_Roberto: No, not a programmer. I just know there's better ways to doing anything without massive energy consumption & Banks."

The problem of blockchain synchronization is the following:

Imagine you are sitting in a bunker. You have no idea what people are out there and what are their intentions. You only receive some incoming messages from strangers that may contain anything. They can be just random garbage or deliberately crafted messages to confuse you or lie to you. You never know. You cannot trust anyone.e

The problem of "money" or any other "social contract" is that everyone should be able to know what the majority agrees to without trusting some intermediaries (otherwise they can easily obuse their special position). If everyone votes for "X", then you sitting in a bunker must somehow independently figure out that all those other people indeed voted for "X" and not for "Y" or "Z". But remember: you cannot trust anyone's message and messages are the only thing you get from the outside world.

When two propositions arrive into your bunker, "X" and "Y", we have no trusted reference point to figure out which one is supported by the majority of other people. We only have "data in itself" to judge which one we should choose as the main one. To make things simpler we are not trying to apply subjective judgement to either proposition, but only trying to make everyone agree to a single option. In case of Bitcoin it is a reasonable assumption: everyone is owner of their money, so no one really cares which version of the history is chosen as long as their own balance is respected.

So how X should be distinct from Y that we know for sure that no one can accidentally choose Y, Z or W? First property: this data should be "recent". So we know that we are not sitting on some old agreement while everyone else has moved onto something else. Second property: any "recent" alternative should be impossible to produce. Because if it was possible to produce, then there is always a chance that some number of people could see it and accept that alternative. And you have no way to estimate how many such alternatives exist and how many people accepted it (because you are sitting in a bunker and you cannot trust incoming messages or know how many message did you miss).

How do we define "impossible"? It means either of two things: either it is logically impossible, or it is practically (economically) impossible. If it is logically impossible, than we can know all future agreements in advance (like a deterministic chain of numbers), just by using induction. But this does not work because we'd have to have some agreement about starting point in the first place. So we end up with requiring practical impossibility. In other words we need the following:

"Message X should be provably recent and alternatives should be practically impossible to produce."

Practical impossibility can be reframed in terms of "opportunity cost": there are limited physical resources and those should have been largely allocated to X than to Y so we can see that X sucked in all resources from any alternatives. Because if it didn't, then there is a huge uncertainty about whether remaining resources are used for alternative Y or they do not interfere with the voting process. Is it possible that X did not suck in a lot of resources while alternatives are still not possible? Then it would mean that X logically follows from whatever previous state of the system and there is no voting process needed.

Therefore: message X should be provably recent and should have employed provably big amount of resources, big enough that there are not enough resources left for any alternative Y to produce in a reasonably short time frame. Also, the message X should be always "recent" and always outcompete any alternative. Because we cannot reliably compare "old" messages: is Y an "old" one that was just delivered now, or was it produced just now after resources spent on X were released?

This logically leads us to the following: we should accept only the messages with the biggest Proof-of-Work attached, and that proof-of-work should be the greatest possible ever, so there would not be any possibility for any alternative to be produce in the short window of time. And that proof-of-work must be constantly reinforced or the value of previous consensus begins to fade quickly as the opportunity for alternatives grows.

Expensive, highly specialized computer farms is the most reliable way to achieve consensus. If we were to use non-specialized resources, it would be harder to gauge whether the majority of them are indeed used for proof-of-work computations. By observing that enormous amount of work happens in a very specific, easy-to-observe part of the economy, we can estimate how expensive it is to produce an alternative, equally difficult message. In case of Bitcoin mining farms, such an alternative would require a very expensive and complex production chain, requring either outcompeting other firms that use chip foundries or building single use datacenters in the most cost-effective locations on the planet (with the cheapest electricity, coldest weather, low latency connectivity etc.)

Conclusion.

If achieving consensus in a non-trust manner is ever possible in practice, then it is only possible with a Proof-of-Work scheme and highly specialized expensive production chains. Also, consensus is only valuable for a short period of time so it must be constantly reinforced.

@jvans1
Copy link

jvans1 commented Dec 17, 2017

This is a good description of why proof of work is valuable but you're making a few assumptions here.

  1. Single nodes must always accept the correct value
  2. There is no further communication after messages X and Y are received.

Assumption 1 ignores the possibility of single nodes accepting incorrect states temporarily before the network as a whole settles on a correct value which would be mitigated by assumption 2. Distributed consensus algorithms are quite chatty and account for temporarily incorrect states. Non-byzantine consensus is hard enough and I do agree that in practice POW is very effective. I don't think this precludes the possibility of finding consensus in a byzantine system though.

@hudon
Copy link

hudon commented May 14, 2018

"we should accept only the messages with the biggest Proof-of-Work attached"

This is not how Bitcoin works, historically. In 2013, when the chain forked, Luke and Pieter commanded the miners to stop mining the chain with the most amount of work and mine the minority chain instead, thus orphaning the longest chain.

Anyone who accepted Bitcoin on the longest chain during the fork potentially lost money + a central authority was required to tell everyone which messages were valid and which were not, irrespective of the attached proof-of-work.

Truth is: when consensus rules change between 2 messages, whether intentionally or unintentionally, "biggest proof-of-work" is ignored and only the "valid" message is considered. The validity rules come from an oracle (the developers), not from a decentralized protocol. Satoshi maybe thought it was possible to set in stone the consensus rules, because that's the only way to resolve this issue. Unfortunately, a system with immutable consensus rules is impractical and ultimately useless the moment a consensus bug is found.

Satoshi was wrong about PoW alone being useful to have a global money, plus PoW uses a shit-ton of electricity compared to trust-based systems. Let's move on.

further reading:
https://freedom-to-tinker.com/2015/07/28/analyzing-the-2013-bitcoin-fork-centralized-decision-making-saved-the-day/

https://digiconomist.net/bitcoin-energy-consumption

https://www.tse-fr.eu/sites/default/files/TSE/documents/doc/wp/2017/wp_tse_817.pdf

@JavierGonzalez
Copy link

JavierGonzalez commented May 14, 2018

Satoshi wasn't wrong.

The miners are the executive power of Bitcoin.
Together -as an entity- they form an authority.
But it is not centralized.

Pools aren't miners. They are only representatives of the true owners of hashpower.
The miners are the ones who have invested in the hardware and pay the bills.
There are tens of thousands of miners participating 24/7.

Centralized, vertical and authoritarian are the devs (well named the oracle).
But no miner can control most of the hashpower.

Bitcoin's energy consumption is well spent.
It's the size of the lock.
It's the security of the project.
Necessary to resist multiple hostile states.
Burning coal or renewable energy is not a Bitcoin issue.

The miners -in a consensus and acting in coordination- can use their hashpower to neutralize any minority blockchain by mining legitimate empty blocks.

They can really decide what blockchain is Bitcoin.
The hashpower is to fire devs.

I liked the article, thank you.

More info:
http://virtualpol.com/Miners_are_the_executive_power_of_Bitcoin_EN.pdf

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment