Is proof-of-work required in Bitcoin?

Question

It seems that the rationale behind the proof-of-work requirement in Bitcoin is that it creates trust in a decentralized trustless network by:

1. helping to reach consensus on which version of the blockchain is the correct one in case that there are multiple temporary competing forks.

2. making the accepted blockchain computationally immutable (irreversible).

Question: Why is proof-of-work required for creating trust?

If most users are honest, then they would voluntarily enforce the prohibition to rewrite the blockchain.

If most users are dishonest, they can still rewrite the blockchain, even with the proof-of-work requirement, not just by outperforming the honest miners, but even simply by creating a consensus to accept a new fork of the main blockchain as the correct version of the blockchain.

UPDATE: Here is the article I linked to in my question:

http://hackingdistributed.com/2014/06/19/bitcoin-and-voting-power/

Bitcoin and Voting Power

Emin Gün Sirer

June 19, 2014 at 05:56 PM

I see a common mistake in many discussions centered around Bitcoin involving voting power. Specifically, many people think that Bitcoin works kind of like a majority voting system, which it kind of does. They then go on to conflate mining power with voting power, and believe that someone with 51% mining power has ultimate say over the contents of the blockchain. In this blogpost, I want to clear up this misconception. The truth is that it is the Bitcoin users who wield ultimate power, and the miners' hashing power has absolutely no say in determining how the protocol evolves.

There are two kinds of "voting power" in Bitcoin: mining power and chain power, and the latter is what really matters because it, solely, on its own, determines how the Bitcoin protocol evolves. The best analogy I can come up with is from soccer: the owner of a soccer team seems all powerful and may appear to have total control over administrative decisions, but it's ultimately the fans who are fully in charge. Fans routinely kick out bad management, drive away players and override bad decisions by the seemingly powerful administration, for it is the fans' attention that the administration seeks.

In any case, let's not let too much anthropomorphizing get in the way; that's why most people get trapped into conflating these two concepts in the first place. Technically, there are two kinds of consensus decisions taking place in Bitcoin:

Mining Power

Miners engage in a process by which they append transactions to the end of an append-only log known as the blockchain. For this, they are amply rewarded with 25 BTC per block, plus all the transaction fees in this block. The process is carefully constructed to enable the majority to form behind a single, unforgeable blockchain. Any given miner can refuse to honor a block discovered by another miner, but if he's in the minority (<=49%) position, he will ultimately find himself being overtaken by the majority.

Among miners, an entity with 51% or more of the hashing power is in a privileged spot. He can engage in behaviors that are not available to minority miners.

But a >=51% miner does not get to rewrite the rules of Bitcoin. That's because mining power is different from, and is not at all correlated with, chain power.

Chain Power

The Bitcoin ecosystem consists of many people other than the miners who operate on the blockchain. In particular, every single Bitcoin user, every single person with a wallet, and every single merchant operates on the blockchain. They store their balances on the blockchain (or have an exchange store their balances somewhere on the blockchain). They use the blockchain to check the balances of people who are sending Bitcoins to them. They validate Bitcoins all the way back to their creation using the blockchain. Miners are part of this group, but they are just like every other user. Collectively, we'll call this group the Bitcoin community.

Everyone in the Bitcoin community gets a single vote, no more, no less, on what kind of a blockchain they will accept. Miners are subservient entities who must follow the decision of the Bitcoin community. They get one vote, along with everyone else. In fact, it is entirely possible for the Bitcoin community to completely change the rules that govern the maintenance of the blockchain, and do so without having any of the miners agree (this would be a mistake for political reasons, but the statement holds technically). The rules are determined entirely by what the buyers and sellers accept as the legitimate blockchain. Miners are subservient followers.

To illustrate, suppose that I, for whatever reason, decided to change the blockchain rules so that every new block generated after January 1st, 2016 shall have the number 42 at the top of every block. If I see a block after that date that does not have 42 on top, I discard it. Suppose that I could get merchants and wallet holders to agree to this pointless, but illustrative, change -- perhaps they also agree that 6*7 is a magical number and they want every block blessed by this magic. Then we'd just collectively refuse the blocks miners create without the magic number in them. The work that the miners would put into creating non-42-bearing blocks would be wasted, and their compensation, in Bitcoins, on a blockchain that none of us accept, would be worthless. New miners would emerge who place the magic number on every block, have their blocks recognized, and be able to redeem their block rewards at merchants who recognize the new blocks with 42 on top.

The basic way in which people exercise this power is by respecting, or ignoring, the blockchain. And the vote carries as much weight as what that user has to offer to the rest of the community. If the user is offering to buy a lot of other Bitcoins, or if he's a merchant like Overstock.com selling stuff that people want, then people will want their blockchain to be compatible with him, and he will have greater sway. The core devs working on the reference implementation play a critical role here, because they get to decide the de facto set of rules that everyone abides by.

Implications

This is a tremendously empowering situation. A 51% miner does not have 51% of the vote; in fact, GHash has just as much say over the contents of the blockchain as do I, or you, or anyone else. Miners derive their income from the buyers and sellers who recognize the blocks they create. This is why the behavior of a misbehaving miner is proscribed -- they could not, for instance, create 10 million Bitcoins out of the thin air, because no one would recognize those new rules. The blockchain is what we all say it is.

This is why regular users wield ultimate power in Bitcoin. It is the chain power that determines the shape of the blockchain, not mining power. Miners are followers, not leaders, in this game.

It is critical to keep these distinctions in mind as we think about the true source and distribution of power in the Bitcoin system. There are lots of fuzzy analogies for Bitcoin (and I'm guilty of using analogies wherever possible myself, because they do make the discourse more accessible, but they also lead some people astray), and if one's not careful, it's easy to end up conflating mining power, which corresponds to miner speed, with real power, which corresponds to having something people want, like cash to buy Bitcoins with or goods to sell for Bitcoin. It's the latter that counts and dictates all else.

Answer 1

Proof of work does not create trust. It creates incentive.

Miners are paid if their block is eventually part of the main version of history ("blockchain") that the network accepts. They must irrecoverably burn electricity in order to create blocks, which costs them money; money they only get paid for if their block "wins".

These factors together mean that miners have a strong incentive to cooperate with other miners, instead of having each try to construct their own version of history, because ultimately only one version will be accepted (ignoring things like intentional forks in the network).

Proof of work is also used for a much more logistical, but equally important purpose: denial of service protection. Because the minimum difficulty for a block scales with the network's hashrate, it is enormously expensive for someone to produce more blocks than (on average) 1 per 10 minutes. Without an objective measure of work like PoW (or central trusted set of parties) anyone could spam the network with an unboundedly large amount of blocks to validate.

Answer 2

If most users are honest, then they would voluntarily enforce the prohibition to rewrite the blockchain.

Without proof of work, this is just not possible. There would be no limit to the number of blocks that could be created at about the same time, there could be thousands of them created every minute. Different servers might receive them in different orders. And a server that was down for a day would have no way to know what to accept.

You need some way to agree on which of two or more equally good ways the system can make forward progress will be agreed upon. Proof of work is not the only way to do this, but you need some way.

In addition, there would be no way to do the initial distribution of the bitcoins as they're created.

Answer 3

Question: Why is proof-of-work required for creating trust?

If most users are honest, then they would voluntarily enforce the prohibition to rewrite the blockchain.

If everyone was honest, then we wouldn't need a blockchain system at all. We could all just trust one another to remember our account balances, and update them appropriately as we transact with one another throughout the day.

Unfortunately, not everyone is honest, and so we need a system that allows everyone to remain in consensus about the current state of the network (ie the allocation of coins). Creating a system that can do this without trusting some central authority is very difficult, as exemplified by the Byzantine generals problem.

Bitcoin's PoW system provides the incentives for miners to work on extending a single chain (rather than proposing alternate histories), and as others have written here, it crucially provides a mechanism of selecting which miner will add the next block to the network.

If most users are dishonest, they can still rewrite the blockchain, even with the proof-of-work requirement, not just by outperforming the honest miners, but even simply by creating a consensus to accept a new fork of the main blockchain as the correct version of the blockchain.

Based on the comments you have made, I think you have misinterpreted the article you linked to. That article uses very non-rigorous language to explain how the network reaches consensus at a high level, but upon more rigorous inspection it fails to provide a blueprint for an alternative system. '1 user = 1 vote' is a very simplified explanation of how the networks consensus rules are chosen, but it is the miners that must extend the chain according to these rules. A network of regular users (nodes) can all agree to follow some certain set of rules, but they cannot come to consensus on which chain to follow without PoW mining. I believe this is the source of your misunderstanding: the article is not suggesting that the network's nodes can continue to remain in consensus without the miners, it just provides a simplified explanation of how users define the rules which miners must adhere to.

Even if users collectively decide to enforce a new set of consensus rules, they will still require the PoW miners to create a blockchain for them. Without the PoW mining, users will be unable to reach consensus, because there will be no mechanism for agreeing upon which block will be the next block, or for mitigating against DoS attacks.

Answer 4

Suppose there's a zero proof-of-work cost. i.e., creating a block is free, computationally. (In practice, this is impossible, but please bear with me). If creating a valid block is free, then here's a way to "buy" something without actually spending any Bitcoin:

1. You buy something using bitcoin. The block recording the transaction is added to the blockchain.
2. You receive the item.
3. You mine a lot of blocks on before your transaction. Because this is much longer than the branch containing your transaction, this means that the branch that doesn't contain your transaction becomes the valid branch.

Thus, the transaction log blockchain won't actually contain the transaction where you sent the Bitcoin to buy something.

There are two ways to prevent this sort of attack:

1. You have an authoritative source that stores the transaction log, thus the new branch won't have been made valid. This method implies centralisation, which is contrary to the goal of a decentralised currency.
2. You make it infeasible for a single user to generate more blocks than the other users combined, and thus make the transaction log without the attacker losing money the valid log.

Enter proof-of-work. This is an attempt to use method 2 to prevent this attack. The system of users will be generating blocks. This takes a huge amount of processing power. In order to make more blocks than the system of users, the proof-of-work forces you to use more computational power than the rest of the system of users combined.

How about a timestamp?

A timestamp is easily forged. With the above attack, you could create a block with a timestamp before the "lose money" transaction. Then, the attacker could send the Bitcoin elsewhere (another one of his/her wallets), and the next block (the "lose money" transaction) would be invalid because it's saying "Take 0.1 bitcoin from X's empty wallet to give to Y."

Two methods of preventing this from happening:

1. The timestamp is verified by an authoritative source (which implies centralisation)
2. The timestamp is only valid if received a fixed (short) time after the timestamp (then the vendor only needs to wait for the required time to elapse, then the block is set in stone and is not in risk of invalidation).

There's a few problems with method 2. First, a blockchain requires all the blocks to be present in memory in order to figure out how much a given wallet contains. When you're reading the block from a log, how would you know if the block was received less that fixed time after the timestamp? The log could be falsified, unless there's an authoritative source or the log takes too much computational power to create by a single malicious user. The latter is guaranteed for any long blockchain with a strong proof-of-work.

Answer 5

The article linked argues that the end user controls the rules of BitCoin, much as the fans of a Soccer/Football team controls how the management of the team behaves.

The question argues that, because the majority of end users can change the rules, if a majority of end users are dishonest, the proof-of-work system becomes useless because the group of end users can rewrite the BitCoin system for their benefit. Furthermore, the question argues that if the majority of users are honest, they can maintain a consensus whether or not the proof-of-work system is present. Therefore, the question argues, since proof-of-work is useless if the majority of end users are honest, and it is useless if the majority of end users are dishonest, proof-of-work is in itself useless.

The question is a three part argument:

If:

1. A majority of end users being dishonest leads to them rewriting BitCoin to their benefit, and
2. A majority of end users being honest allows them to maintain consensus with or without proof-of-work,

Then:

3. Proof-of-work is useless

Though I disagree with the second point, the asker believes it true, and there has been a debate on this point ongoing since September 18, 2019 to at least October 7, 2019 in the linked chat room. Upon conclusion of this debate, this answer shall be edited to elucidate the reasoning behind why point 2 is or is not correct.

I also disagree with the first point. Here's why:

Let's assume that the dishonest majority came together and somehow came to an agreement on what the new rules of BitCoin would be. These new rules would be advantageous to all of them, of course. We'll liken these new rules to "drawing an evil moustache on the BitCoin", and we'll call the new system, with the new rules, MoustacheCoin.

If MoustacheCoin is beneficial to the dishonest majority at the expense of the recipient, then no one would want to sell anything for MoustacheCoin. MoustacheCoin would therefore have reduced purchasing power in comparison to BitCoin. If MoustacheCoin is beneficial to the dishonest majority at the expense of the sender, then no one would want to use MoustacheCoin to buy anything, and thus it would be useless. If MoustacheCoin were only beneficial to those in the founding dishonest majority, then no one new would join. Furthermore, it is axiomatic that MoustacheCoin would be not detrimental to the founding dishonest majority, because then that person would not be in the founding dishonest majority.

Therefore, MoustacheCoin would not be useful, due to either 1: having a reduced purchasing power in comparison to BitCoin, 2: no one being willing to buy anything with it, or 3: giving no competitive advantage against insiders, but outsiders don't want to join.

MoustacheCoin wouldn't even kill BitCoin, even if it remained nine times as popular as BitCoin. After all, even if nine of ten people prefer apples to oranges, there's still money to be made selling oranges.

And, as described above, there's no way MoustacheCoin would be as useful as BitCoin.

Therefore, point 1 in the argument is defeated; a majority of end users being dishonest would not lead to them rewriting BitCoin to their benefit.

If most users are honest, then as the system currently stands, proof-of-work is required to maintain consensus in the face of a dishonest minority. The asker disagrees (as of October 7), and a debate is ongoing.

The argument (as of October 7) appears to be currently deadlocked, with the state of the argument from this answerer's perspective being this:

BitCoin uses proof-of-work to prevent a double-spending attack, which can theoretically be overcome if an attacker controls more than half of the mining power in the network. The asker proposes an alternative system not including proof-of-work, instead relying on a voting scheme as detailed below:

1. Each user maintains a list of other known users and what it believes is the most updated chain.
2. If the user sees a new longer chain that is compatible with its "most updated chain", then the user's "most updated chain" becomes this new longer chain.
3. If the majority of the user's known users agree on a chain that is incompatible with the user's current chain, then the the user's "most updated chain" becomes this new chain.

Where compatible is defined as the shorter chain being a subset of the longer chain.

The objection that a human user can potentially forge a large number of false virtual users and thus "win the vote" to cause a double-spending attack has been raised.

The asker has responded that it is equivalently possible in BitCoin, an assertion that I strongly doubt.

It seems from the current state of the debate that this question is raised due to a misunderstanding of the article.

My interpretation of the article is this: BitCoin users have soft influence over the rules of the blockchain, because if they collectively decide to not recognise the rules and instead recognise a new set of rules, there is no value in for miners to follow the old set of rules. In this manner, it is entirely possible for the users of BitCoin to change the rules of BitCoin.

The interpretation of the asker seems to be more along these lines: BitCoin has a technical mechanism that allows a majority of users to change the rules. The asker seems to believe that this can lead to a potential attack where a majority of users (many of which can be controlled by a single natural person) can potentially compromise the network.

This debate is ongoing, and this answer will update at its conclusion.

Answer 6

Proof of work is not required, there are other algorithms such as proof of stake that are still decentralized (though I don't know how it works even though Ethereum wants to use proof of stake mining). The proof of work gives a block a difficulty, saying "there must be at least X zeroes in a block." (X does not have to be an integer, if it did, difficulty could only be adjusted on orders of two, four, or sixteen; right now it is a little above 16.8) This adding zeroes controls the number of problems that can be solved, and is usually on the order of hundreds or (lower) tens of hundreds per day. When there are more miners, the network responds relatively soon by raising difficulty (in less than 2 weeks), and when there are less, it also responds by doing the opposite (in possibly more than 2 weeks). The proof of work is like a lottery, and who solves the problem is randomly selected and is then awarded the prize through the coinbase. Proof of work is basically a verification mechanism that looks at the zeroes in a hash (work) and forces a certain number (minimum) to be zero.