A simple counter-example comes to mind: rewriting history is trivial only if you want no central authority. Even if we lose the "decentralized consensus" aspec

A simple counter-example comes to mind: rewriting history is trivial only if you want no central authority. Even if we lose the "decentralized consensus" aspect with no PoW, it still can be advantageous. E.g.: simply having an authoritative server always responding with the latest block hash. The server is very lightweight (as in 80s microcontroller lightweight) and it can offload the actual blockchain handling to clients.