In proof of work, miners repeatedly hash a candidate block with a changing nonce until the output falls below a target set by mining-difficulty. Finding one is pure luck weighted by hash-rate; verifying one is instant, which is what makes the scheme work.
The security argument is economic. Rewriting past blocks means redoing all that electricity faster than the honest network produces new blocks, so attacks cost real money per hour they continue.
The criticisms are real too: energy use is large, and mining concentrates where power is cheapest. That concentration is a risk factor, not a settled debate, and it is one reason many newer chains use proof-of-stake instead.
Related: hash-rate, mining-difficulty, block-reward, proof-of-stake