In my TPAC open topic session on Future Proofing (
https://www.w3.org/2024/09/24-did-minutes.html#t11) I mentioned that there
now existed zk-proofs that can do large merkle-trees in <100 bytes.
One variant in production is the "verkle" tree:
https://ethereum.org/en/roadmap/verkle-trees/
I spoke to one of the BLAKE3 cryptographers that said there has been
considerable advancement since verkle-trees. I couldn't find the exact
paper for his version as the original website now 404s, but I did find
description of it at the end of his talk at:
https://www.aumasson.jp/data/talks/safe-hash.pdf
In an old email to the author, as we are considering (long-term) using one
of these for Gordian Envelope instead of our current SHA-256 hash tree, he
said:
> You may however find ZK-friendly hashes that are also pretty fast in
"vanilla" mode, such as Reinforced Concrete (RC). I think one of the use
cases the paper cites is the kind of privacy-preserving system you
describe, see https://eprint.iacr.org/2021/1038. I'm currently working
(with the RC team) on a variant of (RC) that would be even faster.
I've sent an inquiry to the author for any updates, and his "even faster"
variant.
-- Christopher Allen