{"id":1137315,"date":"2025-04-22T14:11:54","date_gmt":"2025-04-22T21:11:54","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-research-item&#038;p=1137315"},"modified":"2025-04-22T14:11:54","modified_gmt":"2025-04-22T21:11:54","slug":"micronova-folding-based-arguments-with-efficient-on-chain-verification","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/micronova-folding-based-arguments-with-efficient-on-chain-verification\/","title":{"rendered":"MicroNova: Folding-based arguments with efficient (on-chain) verification"},"content":{"rendered":"<p>We describe the design and implementation of MicroNova, a folding-based recursive argument for producing proofs of incremental computations of the form <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mi>y<\/mi><mo>=<\/mo><msup><mi>F<\/mi><mrow><mo stretchy=\"false\">(<\/mo><mi>\u2113<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/msup><mo stretchy=\"false\">(<\/mo><mi>x<\/mi><mo stretchy=\"false\">)<\/mo><\/math>, where <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mi>F<\/mi><\/math> is a possibly non-deterministic computation (encoded using a constraint system such as R1CS), <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mi>x<\/mi><\/math> is the initial input, <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mi>y<\/mi><\/math> is the output, and <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mi>\u2113<\/mi><mo>><\/mo><mn>0<\/mn><\/math>. The proof of an <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mi>\u2113<\/mi><\/math>-step computation is produced step-by-step such that the proof size nor the time to verify it depends on <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mi>\u2113<\/mi><\/math>. The proof at the final iteration is then compressed, to achieve further succinctness in terms of proof size and verification time. Compared to prior folding-based arguments, a distinguishing aspect of MicroNova is the concrete efficiency of the verifier\u2014even in a resource-constrained environment such as Ethereum\u2019s blockchain. In particular, the compressed proof consists of <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mi>O<\/mi><mo stretchy=\"false\">(<\/mo><mi>log<\/mi><mo>\u2061<\/mo><mrow><mi>N<\/mi><\/mrow><mo stretchy=\"false\">)<\/mo><\/math> group elements and it can be verified with <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mi>O<\/mi><mo stretchy=\"false\">(<\/mo><mi>log<\/mi><mo>\u2061<\/mo><mrow><mi>N<\/mi><\/mrow><mo stretchy=\"false\">)<\/mo><\/math> group scalar multiplications and two pairing operations, where <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mi>N<\/mi><\/math> is the number of constraints for a single invocation of <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mi>F<\/mi><\/math>. MicroNova requires a universal trusted setup and can employ any existing setup material created for the popular KZG univariate polynomial commitment scheme. Finally, we implement and experimentally evaluate MicroNova. We find that MicroNova\u2019s proofs can be efficiently verified on the Ethereum blockchain with <math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mo>\u2248<\/mo><\/math>2.2M gas. Furthermore, MicroNova\u2019s prover incurs minimal overheads atop its baseline Nova\u2019s prover.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We describe the design and implementation of MicroNova, a folding-based recursive argument for producing proofs of incremental computations of the form y=F(\u2113)(x), where F is a possibly non-deterministic computation (encoded using a constraint system such as R1CS), x is the initial input, y is the output, and \u2113>0. The proof of an \u2113-step computation is [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"IEEE","msr_pages_string":"","msr_page_range_start":"","msr_page_range_end":"","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"Security and Privacy","msr_doi":"","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":null,"msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2025-5","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":0,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":null,"footnotes":""},"msr-research-highlight":[],"research-area":[13558],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[269148,269142],"msr-field-of-study":[246691],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-1137315","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-security-privacy-cryptography","msr-locale-en_us","msr-post-option-approved-for-river","msr-post-option-include-in-river","msr-field-of-study-computer-science"],"msr_publishername":"","msr_edition":"","msr_affiliation":"","msr_published_date":"2025-5","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"IEEE","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"url","viewUrl":"false","id":"false","title":"https:\/\/eprint.iacr.org\/2024\/2099.pdf","label_id":"243132","label":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[],"msr-author-ordering":[{"type":"text","value":"Jiaxing Zhao","user_id":0,"rest_url":false},{"type":"user_nicename","value":"Srinath Setty","user_id":33709,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Srinath Setty"},{"type":"user_nicename","value":"Weidong Cui","user_id":34789,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Weidong Cui"},{"type":"user_nicename","value":"Greg Zaverucha","user_id":31912,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Greg Zaverucha"}],"msr_impact_theme":[],"msr_research_lab":[199565],"msr_event":[],"msr_group":[398567],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1137315","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1137315\/revisions"}],"predecessor-version":[{"id":1137316,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1137315\/revisions\/1137316"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=1137315"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=1137315"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=1137315"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=1137315"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=1137315"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=1137315"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=1137315"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=1137315"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=1137315"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=1137315"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=1137315"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=1137315"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=1137315"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}