TY - GEN
T1 - Proofs for Deep Thought
T2 - 30th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2024
AU - Bünz, Benedikt
AU - Chen, Jessica
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.
PY - 2025
Y1 - 2025
N2 - An important part in proving machine computation is to prove the correctness of the read and write operations performed from the memory, which we term memory-proving. Previous methodologies required proving Merkle Tree openings or multi-set hashes, resulting in relatively large proof circuits. We construct an efficient memory-proving Incrementally Verifiable Computation (IVC) scheme from accumulation, which is particularly useful for machine computations with large memories and deterministic steps. In our scheme, the IVC prover PIVC has cost entirely independent of the memory size T and only needs to commit to approximately 15 field elements per read/write operation, marking a more than 100X improvement over prior work. We further reduce this cost by employing a modified, accumulation-friendly version of the GKR protocol. In the optimized version, PIVC only needs to commit to 6 small memory-table elements per read/write. If the table stores 32-bit values, then this is equivalent to committing to less than one single field element per read and write. Our modified GKR protocol is also valuable for proving other deterministic computations within the context of IVC. Our memory-proving protocol can be extended to support key-value stores.
AB - An important part in proving machine computation is to prove the correctness of the read and write operations performed from the memory, which we term memory-proving. Previous methodologies required proving Merkle Tree openings or multi-set hashes, resulting in relatively large proof circuits. We construct an efficient memory-proving Incrementally Verifiable Computation (IVC) scheme from accumulation, which is particularly useful for machine computations with large memories and deterministic steps. In our scheme, the IVC prover PIVC has cost entirely independent of the memory size T and only needs to commit to approximately 15 field elements per read/write operation, marking a more than 100X improvement over prior work. We further reduce this cost by employing a modified, accumulation-friendly version of the GKR protocol. In the optimized version, PIVC only needs to commit to 6 small memory-table elements per read/write. If the table stores 32-bit values, then this is equivalent to committing to less than one single field element per read and write. Our modified GKR protocol is also valuable for proving other deterministic computations within the context of IVC. Our memory-proving protocol can be extended to support key-value stores.
KW - Accumulation Scheme
KW - Incrementally Verifiable Computation
KW - Proof system
UR - http://www.scopus.com/inward/record.url?scp=85213322388&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85213322388&partnerID=8YFLogxK
U2 - 10.1007/978-981-96-0935-2_9
DO - 10.1007/978-981-96-0935-2_9
M3 - Conference contribution
AN - SCOPUS:85213322388
SN - 9789819609345
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 269
EP - 301
BT - Advances in Cryptology – ASIACRYPT 2024 - 30th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
A2 - Chung, Kai-Min
A2 - Sasaki, Yu
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 9 December 2024 through 13 December 2024
ER -