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.