Is the purpose of proof-of-work the immutability of the blockchain? I have a disagreement with a person: I believe that the primary and most important goal of including proof-of-work (and therefore the nonce) in a block is to make it hard for an attacker to change that block (and since we are talking about a chain the next ones) without committing enough resources to recalculate not only the current but also all the blocks after that. Without it the attacker could simply create forks of the blockchain without any problems (free).

He claims that it is a mechanism is there to solve the problem of determining representation in majority decision making. If the majority were based on one-IP-address-one-vote, it could be subverted by anyone able to allocate many IPs. Proof-of-work is essentially one-CPU-one-vote.

Who is more right?
Immutable transactions are a consequence of blockchain-based systems when the following are true:


There is a cost (in currency and in acquiring materials) of producing a block consistent with the rules of the protocol, and this cost cannot be circumvented
The cost is great enough where incurring this cost to increase the length of the blockchain is more profitable than incurring this cost to fork the blockchain
As part of the rules of the protocol, past transactions cannot be altered by future additional data


Proof of work fits into this because it is provably costly. It requires energy, and it also requires development time and materials to create machines that use this energy efficiently. This cost prevents forks from being supported, as you have limited energy and you can only use that energy once.

This contrasts with Proof of Stake, or an IP based voting system because a lack of energy requirement means that there an incentive to support all forks. This is referred to as the Nothing-at-stake problem.