Scholarlink

Incrementally verifiable computation (IVC) [Valiant, TCC’08] allows one to iteratively prove that a configuration \(x_0\) reaches another configuration \(x_T\) after repeated applications of a (possibly non-deterministic) transition function \(\mathcal {M}\) . The key requirement is that the size of the proof and the time to update the proof is sublinear in the number of steps T. IVC has numerous applications, notably including proving correctness of virtual machine executions in blockchains. Currently, IVC for \(\textsf{NP}\) is only known to exist in non-standard idealized models, or based on knowledge assumptions. No constructions are known from standard assumptions, or even in the random oracle model. Furthermore, as observed in prior works, since IVC for \(\textsf{NP}\) implies adaptive succinct non-interactive arguments for \(\textsf{NP}\) , the work of Gentry-Wichs [STOC’11] seemingly poses barriers to constructing IVC for \(\textsf{NP}\) from falsifiable assumptions. In this work, we observe that the Gentry-Wichs barrier can be overcome for IVC for NP. We show the following two results:

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Incrementally Verifiable Computation for NP from Standard Assumptions

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Pratish Datta,
  • Abhishek Jain,
  • Zhengzhong Jin,
  • Alexis Korb,
  • Surya Mathialagan,
  • Amit Sahai

摘要

Incrementally verifiable computation (IVC) [Valiant, TCC’08] allows one to iteratively prove that a configuration \(x_0\) reaches another configuration \(x_T\) after repeated applications of a (possibly non-deterministic) transition function \(\mathcal {M}\) . The key requirement is that the size of the proof and the time to update the proof is sublinear in the number of steps T. IVC has numerous applications, notably including proving correctness of virtual machine executions in blockchains. Currently, IVC for \(\textsf{NP}\) is only known to exist in non-standard idealized models, or based on knowledge assumptions. No constructions are known from standard assumptions, or even in the random oracle model. Furthermore, as observed in prior works, since IVC for \(\textsf{NP}\) implies adaptive succinct non-interactive arguments for \(\textsf{NP}\) , the work of Gentry-Wichs [STOC’11] seemingly poses barriers to constructing IVC for \(\textsf{NP}\) from falsifiable assumptions. In this work, we observe that the Gentry-Wichs barrier can be overcome for IVC for NP. We show the following two results: