Lightweight Instance Batch Schemes Towards Prover-Efficient Decentralized Private Computation

Batch schemes provide a way to amortize the cost of NP verifiers across multiple instances. In this work, we introduce an instance batch scheme that allows a prover to iteratively prove the correctness of multiple executions of a function F. For N instance-witness tuples where each represents one correct execution of F on given inputs, our scheme could batch them into two tuples and therefore reduce the task of verifying these tuples into the task of verifying only two tuples. Specifically, the prover complexity is O(N) multi-exponentiations of size |F|, the verifier complexity is O(|F|) field multiplications, and the proof size is O(|F|) field elements, where |F| denotes the size of F. Moreover, we provide a technique that allows multiple provers to generate a proof parallelly, which would accelerate the proof generation process in practice.    We apply our batch scheme to the Decentralized Private Computation (DPC) scenario and implement this application. The benchmark results show that the proving time has been reduced by approximately 9%∼11% compared with the state-of-the-art DPC scheme.