Making dishonesty expensive
Proof of Work solves the agreement problem by making it costly to propose the next addition to the shared history. Participants, called miners, compete to solve a puzzle that requires enormous amounts of trial-and-error computation to solve but is cheap for everyone else to verify once solved. Whoever finds a valid solution first gets to add the next block, and the rest of the network checks the answer and moves on.
The puzzle itself carries no useful information, its only purpose is to force whoever wins the right to add a block to have spent real computational effort and real electricity doing it. That cost is the whole point. If someone wanted to rewrite past history, they would need to redo that expensive puzzle-solving for every block they wanted to change, and outpace all the honest miners doing the same work simultaneously, which becomes exponentially harder the further back they try to rewrite.