How does a blockchain relying on PoW verify that a hash is computed using an algorithm and not made up by a human? How does a blockchain verify that the hash provided (the one with the leading zeros that is supposed to be unique, computed using lots of processing power) is indeed unique and that it wasn't just a random number some one came up with and then just added the expected leading zeros to it?
A Hash Function maps &quot;data of arbitrary size to fixed-size values&quot;. As an incredibly simple hash, consider a function only works on numbers and simply returns the last 3 (decimal) digits (ie., the 1s, 10s, and 100s places).
Using this simple hash, 5 would hash to 005, and 123,456 would hash to 456.
A Bitcoin block contains a handful of fields (source):

Version
Previous block hash
Merkle root
Time stamp
Difficulty bits
Nonce

All of those can be represented by numbers (the time stamp is Unix time (source), which means it's basically the number of seconds since 00:00:00 UTC on 1 January 1970).
Of those values, only the nonce can be freely changed without invalidating the block. The timestamp can take a range of values (roughly &quot;1 hour ago&quot; to &quot;2 hours from now&quot; (source)), and the version number has a great deal of flexibility (ibid). I'll focus on the nonce since that's the easiest for me to talk about.
Proof of work, in this simplified scenario, is accomplished by adding all of those numbers together and finding a nonce that results in the hash being 000. In this simplified scenario, that's trivial to do: you can just add the other numbers together, hash that partial sum, then set the nonce to 1,000 - that partial hash. So, it's not a very good hashing algorithm for this purpose.
Instead, Bitcoin uses SHA256. SHA256 has a couple of advantages which stem from its being a cryptographic hash function; the big three are that calculating the SHA256 hash of a given value is &quot;cheap&quot; but generating a value that will produce a given SHA256 hash is hard, and that tiny changes in the input will produce large changes in the output (the avalanche effect).
In fact, to the best of our collective knowledge, the only way to generate an input that produces a given SHA256 hash is to keep trying inputs until you find one that works.
So: unlike the simple hash at the beginning, we can't figure out what the nonce should be just by looking at the rest of the data. And, we can't just tweak the nonce to get the hash we want: the avalanche effect means that every small change to the input will have large changes to the output. Therefore, the only way to find a nonce that produces a valid SHA256 hash is to start at 0 and work up 'til a suitable nonce is found.
Once a suitable nonce is found, anyone can verify that the nonce/hash pair is valid by hashing the block with that nonce and seeing that the hash matches. This check can be done very quickly, and serves to prove that whoever found that nonce did the work.
The nonce is a 32-bit integer (source), which means that there are 4,294,967,295 (just under 4.3 billion) possible nonces. Compare that to the Powerball lottery, in which a single ticket has about a 1-in-300,000,000 chance of winning the jackpot, and it becomes clear how unlikely a randomly-chosen nonce is to be valid; even if there were thousands of nonces that could produce a SHA256 hash with enough leading zeroes, picking nonces at random would still be staggeringly unlikely.
Then, the time can take any value in a roughly 3-hour window and has second-resolution, so there are ~10,800 values it can take. The version has some limits, but it appears to be another 4-bit integer like the nonce; for rough calculations' sake, let's say it can take half of the possible values that the nonce can. That means that there are around 9e+22 (a 9 followed by 22 zeroes) possible combinations. There are about 200 billion stars in the milky way (source); that is, 200,000,000,000 or 2e+11. Finding a correct header randomly had odds in the realm of two people randomly choosing the same grain of sand from the whole of the galaxy.