Very nice! A tl;dr with spoilers -- for a typical compression algorithm C(x), applying it over and over again C(x), C(C(x)), C(C(C(x))), ... we would quickly ar

Very nice! A tl;dr with spoilers -- for a typical compression algorithm C(x), applying it over and over again C(x), C(C(x)), C(C(C(x))), ... we would quickly arrive at an input for which the compressed length increases. Here the author proposes C(x) which either equals x (no compression), or encodes a normal compression (e.g. gzip) plus a MAC'd counter. Applying C(x) on the latter case again would simply increment the counter, so an adversary who only issues a bounded number of compression requests gets "stuck" on a chain that contains no contradiction. (The attacker could try to get to y = C(x) with a large counter value without compressor's help but that requires predicting the MAC which is infeasible.) The requirement for C and D to share a secret (here, a MAC key) can be removed by replacing MAC with a VDF proof that you spent O(counter) sequential time producing the compressed output, so a computationally bounded attacker can't overflow the counter (in practice, 128 bit counter requiring ~2^128 time) and disprove the paradox.