The way I understand how proof of work (PoW) works is this: its fundamental goal is to prevent cheating, or creating an inconsistent view of the distributed ledger.
Imagine a double spend scenario - where in participant A has only 1 BC to spend. But, he creates two independent transactions or "spends" each with 1 BC. He then presents each spend transaction to two different parties B and C as valid payments. Since there is no notion of serialization of transactions (as one would have in a centralized database with atomic commits), it is possible that some participants in the network have recorded A's payment to B first, while others have recorded A's payment to C first. At the same time, some will end up rejecting the latter payment (since A has only 1 BC to spend).
In the ideal world, if both transactions can be strictly serialized (as, for example - A's payment to B will be recorded in the distributed ledger before A's duplicate payment to C might be recorded), there will be no need for distributed consensus. In an ideal world, where in the transactions can be time-stamped using a "central" clock visible to every participant, we would have an easy solution.
The PoW process solves this problem algorithmically by forcing a non trivial finite delay for submitting and committing a block a transactions. In the bitcoin scheme, where transactions must be committed in a block level granularity, A's double spend transaction has two possibilities:
- Either both transactions are grouped together in the same block,
- Or, they are grouped in different blocks.
In the latter case, the inconsistency is easily detected and flagged. In the former case also, it is easy to detect the inconsistency & flag the same - but it is possible to do so only when both transactions (the good one and the bad one) are grouped in the same block. This is not possible if either the block sizes are too small or can be committed by the nodes very quickly. This is where PoW comes handy - it forces enough time to elapse in order compose a new block and have it committed by all participants.
The question that was not clear to me is this: Bitcoin uses a certain variation of computing the pre-image of a SHA-256 hash value. Since the purpose of PoW is only to delay the creation of new blocks by a sufficient time lag, this puzzle to solve could be anything - as for example, solving a 16-queens placement problem on a chess board, or something like that. It is not clear if the puzzle really needs to have a correlation with the actual data in the block being committed.