Bitcoin uses two rounds of SHA256 on the entire contents of each block (which includes a reference to the previous block) as well as a randomly varied nonce. When the result of those calculations are below a network-determined threshold it is considered to be a valid solution. These solutions are published along with the block as it is distributed to the network so finding the hash of old blocks is trivially easy, you just look them up. Verifying that the math was done correctly and that the result meets the criteria requires only a single iteration of sha256(sha256(block+nonce)) while finding the appropriate nonce the first time takes an absolutely insane number of attempts.

The insane number of attempts is necessarily because the output of sha256 is, effectively, pseudorandom and covers a huge space. The algorithm is deterministic, so sha256(x) will always have the same result, but the result is entirely unpredictable and minor changes in the value of x will dramatically...