It seems that the rationale behind the proof-of-work requirement in Bitcoin is that it creates trust in a decentralized trustless network by:
helping to reach consensus on which version of the blockchain is the correct one in case that there are multiple temporary competing forks.
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:
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:
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.
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.
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.