Literally everything good that humans have produced are proof of work. Proof of stake is the rent seeking that comes afterwards.
> an ever-increasing difficulty in the case of Bitcoin (getting worse with time, on purpose)
This is not how Bitcoin's difficulty adjustment works. It increases/decreases with the value of the block reward. This is proportional to the value of bitcoin, transaction fees paid, and decreasing new bitcoin issuance. Bitcoin users pay miners for their PoW because they find the value of using such a system to be worth the cost.