The beauty of MTP is that the miner allocates memory but not the verifier. However, the trade-off for that is the size of the proof.
Memory use by miners only, and not by verifiers, is common among asymmetric algorithms. Earlier ones,
like primecoin, Cuckoo Cycle, and Equihash do not require the big proofs that MTP requires, but only a
few hundred bytes.
Very cool and very interesting! I've always wondered why it never appears feasible to utilize a compression algorithm to shrink the size of the proof in this case, or compress data inside blocks in the case of btc.
I think the average data can be shrunk via compression is often by a factor of 1/3rd. From an amateur perspective, being able to fill roughly 3x the amount of data per size would seem to be a worthwhile approach. Especially as compression isn't particularly resource intensive, at least not in comparison to mining cryptographic functions. Adding a compression abstraction layer woudn't appear to bottleneck the process. But I would guess I'm missing some important point here as crypto engineers never seem to bother with compressing data?
Cryptographic data, such as hash outputs and elliptic curve points, look completely random and thus do not compress at all. These dominate the blockchain data, leaving only a small amount of compressibility in script bytecodes and counters and such.