1. xJsnark: A Framework for Efficient Verifiable Computation 2018 Oakland VerifiableComputation zkSNARK
    Ahmed Kosba, Charalampos Papamanthou and Elaine Shi
    [View PDF on cs.umd.edu]
    [Show BibTex Citation]

    author={A. {Kosba} and C. {Papamanthou} and E. {Shi}},
    booktitle={2018 IEEE Symposium on Security and Privacy (SP)},
    title={xJsnark: A Framework for Efficient Verifiable Computation},
    keywords={cloud computing;computational complexity;cryptography;data privacy;digital arithmetic;electronic money;optimisation;outsourcing;program compilers;protocols;theorem proving;cryptocurrency application;cloud application;primary metric;globally aware optimizations;long- integer arithmetic;short- integer arithmetic;ZeroCash;efficient verifiable computation;redundant computation;circuit minimization techniques;circuit-friendly algorithms;programming framework;xJsnark;suboptimal circuits;nonspecialist users;program-to-circuit transformation;high-level program;low-level development tools;outsourced computations;Logic gates;Optimization;Minimization;Program processors;Programming;Cryptography;Task analysis;Verifiable Computation},

Many cloud and cryptocurrency applications rely on verifying the integrity of outsourced computations, in which a verifier can efficiently verify the correctness of a computation made by an untrusted prover. State-of-the-art protocols for verifiable computation require that the computation task be expressed as arithmetic circuits, and the number of multiplication gates in the circuit is the primary metric that determines performance. At the present, a programmer could rely on two approaches for expressing the computation task, either by composing the circuits directly through low-level development tools; or by expressing the computation in a high-level program and rely on compilers to perform the program-to-circuit transformation. The former approach is difficult to use but on the other hand allows an expert programmer to perform custom optimizations that minimize the resulting circuit. In comparison, the latter approach is much more friendly to non-specialist users, but existing compilers often emit suboptimal circuits.

We present xJsnark, a programming framework for verifiable computation that aims to achieve the best of both worlds: offering programmability to non-specialist users, and meanwhile automating the task of circuit size minimization through a combination of techniques. Specifically, we present new circuit-friendly algorithms for frequent operations that achieve constant to asymptotic savings over existing ones; various globally aware optimizations for short- and long- integer arithmetic; as well as circuit minimization techniques that allow us to reduce redundant computation over multiple expressions. We illustrate the savings in different applications, and show the framework’s applicability in developing large application circuits, such as ZeroCash, while minimizing the circuit size as in low-level implementations.