Add compression step in a verifiable way

[nuke-web3]

As data sizes for output ciphertext are expected to be on the order of a few MB, on the upper end, it may become impossible to post in full on a DA layer (Like Celestia) as the single blob size is limited, and ultimately only so much can fit in any block. (splitting & streaming the full data to DA over multiple blocks is of course possible, but ideally we would not need to build this solution out)

Considerations

There are a few ways to maintain the verifiability of the encryption while compressing it:

1. Run compression as a pre-process before publishing to zkVM
   • Not viable I think: there is no way to anchor to input plaintext in a verifiable way.
   • An option if we have a trusted signing party that attests to input being used, but that kinda defeats the point of doing verifiable encryption at all.
2. Run compression inside zkVM, so the output is verifiably correct
   • Adds potentially a very high amount of cycles & thus makes impractical to self-host the prover (that we require to keep the encryption key hidden)
   • Likely most efficient to compress then encrypt? Suspicion being there is a lot of 0s and repeated bytes in the input data, so higher compression ratio possible. Also reduces cycles in making the keystream & XOR
     • initial data compression test with gzip is ~30% of the original size.
3. Run compression as a post-process before publishing to DA
   • Requires verifiers to know a decompression step is needed to obtain ciphertext committed to in the proof receipt's journal.
   • Perhaps the receipt could include only a hash of ciphertext (if more performant) that verifiers can decomp + hash to check against

Probing chatGPT a bit:

Goal	Without Input	Without Decompression	Without ZKP	Is It Possible?
Prove that compressed blob corresponds to a specific input	✅	✅	❌	❌
Prove that compressed blob was signed by someone who had the input	✅	✅	✅	✅
Prove integrity of the compressed blob	✅	✅	✅	✅
Prove correctness of compression	✅	❌	✅ (ZKP)	✅ with ZKP

Research

We want the most performant cycle count option for doing compression in zkVM. Some options listed here: https://blog.logrocket.com/rust-compression-libraries/ and https://lib.rs/compression

• https://github.com/PSeitz/lz4_flex - perhaps lowest cycle count based on being one of the fastest compression tools (and very fast decompression)
• https://github.com/rust-lang/flate2-rs - the most popular, maintained by Rust-lang itself.
• https://github.com/dropbox/rust-brotli - higher compression, industry standard (more than Rust), but would be only viable outside zkVM (much higher cycles)

[nuke-web3]

Actually looking a bit more at logrocket - random bytes don't compress hardly at all (of course). Compressing ciphertext should be essentially worthless (if it's good encryption). 🤔

So likely we need to do verifiable compression to get any gains here. With the verifier running decryption before decompression.