Incrementally Verifiable Computation via Rate-1 Batch Arguments
Omer Paneth, Rafael Pass
Abstract
Non-interactive delegation schemes enable producing succinct proofs (that can be efficiently verified) that a machine M transitions from c <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> to c <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> in a certain number of deterministic steps. We here consider the problem of efficiently merging such proofs: given a proof Π <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> that M transitions from c <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> to c <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> , and a proof Π <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> that M transitions from c <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> to c <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</inf> , can these proofs be efficiently merged into a single short proof (of roughly the same size as the original proofs) that M transitions from c <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> to c <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</inf> ? To date, the only known constructions of such a mergeable delegation scheme rely on strong non-falsifiable “knowledge extraction” assumptions. In this work, we present a provably secure construction based on the standard LWE assumption. As an application of mergeable delegation, we obtain a construction of incrementally verifiable computation (IVC) (with polylogarithmic length proofs) for any (unbounded) polynomial number of steps based on LWE; as far as we know, this is the first such construction based on any falsifiable (as opposed to knowledge-extraction) assumption. The central building block that we rely on, and construct based on LWE, is a rate-l batch argument (BARG): this is a non-interactive argument for NP that enables proving k NP statements $x_{1},\ldots, x_{k}$ with communication/verifier complexity m + o(m), where m is the length of one witness. rate-1 BARGs are particularly useful as they can be recursively composed a super-constant number of times.