Efficient Layered Circuit for Verification of SHA3 Merkle Tree

Changchang Ding; Zheming Fu

Paper 2024/1212

Efficient Layered Circuit for Verification of SHA3 Merkle Tree

Changchang Ding, Indiana University Bloomington

Zheming Fu, China Reinsurance (Group) Corporation

Abstract

We present an efficient layered circuit design for SHA3-256 Merkle tree verification, suitable for a GKR proof system, that achieves logarithmic verification and proof size. We demonstrate how to compute the predicate functions for our circuit in $O(\log n)$ time to ensure logarithmic verification and provide GKR benchmarks for our circuit.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Contact author(s): dingchan @ iu edu
fuzm @ chinare com cn
History: 2024-07-29: revised; 2024-07-29: received; See all versions
Short URL: https://ia.cr/2024/1212
License: CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2024/1212,
      author = {Changchang Ding and Zheming Fu},
      title = {Efficient Layered Circuit for Verification of {SHA3} Merkle Tree},
      howpublished = {Cryptology ePrint Archive, Paper 2024/1212},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/1212}},
      url = {https://eprint.iacr.org/2024/1212}
}