Certainly the latter. I can imagine proof of space implemented by requiring nodes to store terabytes of random bytes, and compute the hash of specific subsets

Certainly the latter. I can imagine proof of space implemented by requiring nodes to store terabytes of random bytes, and compute the hash of specific subsets of this huge blob based on the last block in the ledger.