{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T04:09:40Z","timestamp":1767931780642,"version":"3.49.0"},"reference-count":21,"publisher":"International Association for Cryptologic Research","issue":"4","license":[{"start":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T00:00:00Z","timestamp":1759881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,12,2]]},"abstract":"<jats:p>SNARKs enable compact proofs that an NP statement is true and that the prover knows a valid witness. They have become a key building block in modern smart contract applications, including rollups and privacy-focused cryptocurrencies. In the widely used Groth16 framework, however, long statements incur high costs. A common workaround is to pass the statement\u2019s hash to the SNARK and move the statement into the witness. The smart contract then hashes the statement first, and the circuit that is proven additionally checks consistency of the hash and the statement. Unfortunately, virtually any hash function is expensive to call either in a smart contract (in terms of gas) or in the proven circuit (in terms of prover time).<\/jats:p>\n                  <jats:p>We demonstrate a novel solution to this dilemma, which we call hybrid compression. Our method allows us to use two different hash functions\u2014one optimized for the proof circuit, and another optimized for on-chain verification\u2014thereby combining the efficiency advantages of both. We define a clean and simple security property of the two hash functions to which our security reduces in the standard model, namely, joint UHF hardness. We then show the plausibility of this assumption in the random oracle model. Our benchmarks show that it achieves near-optimal performance in both gas usage and prover time. As an example, compressing an 8 KB statement with our approach results in a 10-second prover time and a smart contract spending 270K gas, whereas the existing approaches either need a much longer proof generation (290 seconds for SHA-256 hashing) or a much more expensive contract (5M gas for Poseidon hashing). Along the way, we develop a two-party protocol of independent interest in communication complexity: an efficient deterministic method for checking input equality when the two parties do not share the same hash function.<\/jats:p>","DOI":"10.62056\/a60ljb0kr","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T23:39:47Z","timestamp":1767915587000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Data Matching in Unequal Worlds   and Applications to Smart Contracts"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-0347-3378","authenticated-orcid":false,"given":"Dmitry","family":"Khovratovich","sequence":"first","affiliation":[{"name":"Ethereum Foundation","place":["Switzerland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-4406-2991","authenticated-orcid":false,"given":"Mikhail","family":"Vladimirov","sequence":"additional","affiliation":[{"name":"ABDK Consulting","place":["Estonia"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4620-7264","authenticated-orcid":false,"given":"Benedikt","family":"Wagner","sequence":"additional","affiliation":[{"name":"Ethereum Foundation","place":["Switzerland"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"ref1:pertsev2019tornado","article-title":"Tornado cash privacy solution version 1.4","volume":"1","author":"Alexey Pertsev","year":"2019","journal-title":"Tornado cash privacy solution version"},{"key":"ref2:AC:Groth10a","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-642-17373-8_19","article-title":"Short Pairing-Based Non-interactive Zero-Knowledge\n  Arguments","volume":"6477","author":"Jens Groth","year":"2010"},{"key":"ref3:EC:Groth16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-662-49896-5_11","article-title":"On the Size of Pairing-Based Non-interactive Arguments","volume":"9666","author":"Jens Groth","year":"2016"},{"key":"ref4:cryptoeprint:2019\/953","volume-title":"PLONK: Permutations over Lagrange-bases for Oecumenical\n  Noninteractive arguments of Knowledge","author":"Ariel Gabizon","year":"2019"},{"key":"ref5:Era","volume-title":"ZkEVM Era","author":"Matter Labs","year":"2025"},{"key":"ref6:ZkTrueUp","volume-title":"ZkTrueUp protocol","author":"Term Structure Team","year":"2024"},{"key":"ref7:Railgun","volume-title":"Railgun protocol","author":"Railgun Team","year":"2025"},{"key":"ref8:ZKSync","volume-title":"ZkSync protocol","author":"Matter Labs","year":"2021"},{"key":"ref9:sha2","article-title":"Secure Hash Standard","author":"National Institute of Standards","year":"2002","journal-title":"Federal Information Processing Standards Publication\n  (FIPS)"},{"key":"ref10:USENIX:GKRRS21","first-page":"519","article-title":"Poseidon: A New Hash Function for Zero-Knowledge Proof\n  Systems","author":"Lorenzo Grassi","year":"2021"},{"key":"ref11:yao1979some","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/800135.804414","article-title":"Some Complexity Questions Related to Distributive Computing\n  (Preliminary Report)","author":"Andrew Chi-Chih Yao","year":"1979"},{"key":"ref12:arora2009computational","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity - A Modern Approach","author":"Sanjeev Arora","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521424264"},{"key":"ref13:DBLP:conf\/icalp\/HochS08","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1007\/978-3-540-70583-3_50","article-title":"On the Strength of the Concatenated Hash Combiner When All\n  the Hash Functions Are Weak","volume":"5126","author":"Jonathan J. Hoch","year":"2008"},{"key":"ref14:DBLP:conf\/eurocrypt\/LeurentW15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-662-46800-5_14","article-title":"The Sum Can Be Weaker Than Each Part","volume":"9056","author":"Ga\u00ebtan Leurent","year":"2015"},{"key":"ref15:DBLP:journals\/joc\/BaoDGLW20","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1007\/s00145-019-09328-w","article-title":"Generic Attacks on Hash Combiners","volume":"33","author":"Zhenzhen Bao","year":"2020","journal-title":"Journal of Cryptology"},{"key":"ref16:DBLP:books\/daglib\/0011756","isbn-type":"print","volume-title":"Communication complexity","author":"Eyal Kushilevitz","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521560672"},{"key":"ref17:rao2020communication","isbn-type":"print","volume-title":"Communication complexity: and applications","author":"Anup Rao","year":"2020","ISBN":"https:\/\/id.crossref.org\/isbn\/9781108671644"},{"key":"ref18:DBLP:conf\/crypto\/CohenN22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/978-3-031-15982-4_9","article-title":"Low Communication Complexity Protocols, Collision Resistant\n  Hash Functions and Secret Key-Agreement Protocols","volume":"13509","author":"Shahar P. Cohen","year":"2022"},{"key":"ref19:micronova","doi-asserted-by":"publisher","first-page":"1964","DOI":"10.1109\/SP61157.2025.00168","article-title":"MicroNova: Folding-Based Arguments with Efficient (On-Chain)\n  Verification","author":"Jiaxing Zhao","year":"2025"},{"key":"ref20:CCS:BelRog93","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1145\/168588.168596","article-title":"Random Oracles are Practical: A Paradigm for Designing\n  Efficient Protocols","author":"Mihir Bellare","year":"1993"},{"key":"ref21:C:KotPar23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1007\/978-3-031-38551-3_21","article-title":"Algebraic Reductions of Knowledge","volume":"14084","author":"Abhiram Kothapalli","year":"2023"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T23:40:42Z","timestamp":1767915642000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/4\/33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":21,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2026,1,8]]}},"URL":"https:\/\/doi.org\/10.62056\/a60ljb0kr","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"assertion":[{"value":"2025-10-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-4-70"}}