DPZKShortProof.tex

%\section{Setting up \name{}} 
\section{\name: MPC-friendly Zero Knowledge Argument from Interactive
PCP}\label{sec:graphene}
In this section, we describe a sub-linear interactive zero-knowledge argument as
a public-coin IPCP. The IPCPs are special cases of more
general Interactive Oracle Proofs (IOP) ~\cite{BCS16}. In ~\cite{BCS16}, the
authors present a transformation (commonly referred to as ``BCS'' after the
authors) to compile a public-coin IOP into a non-interactive argument in the
Random Oracle Model. The transformation can be applied to our protocol to obtain
a publicly-verifiable non-interactive argument. Moreover, in distributed
setting, the aggregator $\Ag$ can apply the transformation on provers' messages
to output a non-interactive argument. 

%\commentA{this part should move to the DPZK part}To serve as a
%baseline for comparison, we also describe naive extensions of existing protocols
%such as Bulletproofs \cite{bulletproofs}, Spartan \cite{spartan}
%distributed prover setting. 
Our protocol proves membership in the $\npol$-complete
language specified by {\em rank one constraint system} (R1CS). An R1CS over a
field $\FF$ is specified by $M\times N$ matrices $A,B$ and $C$, where the
associated language $\mc{L}(A,B,C)$ consists of $\wit\in \FF^N$ such that
$A\wit\circ B\wit=C\wit$, where $\circ$ defines element-wise product. Several
recent zero knowledge constructions ~\cite{Groth16,aurora,marlin}, and 
circuit compilers such as ~\cite{zokrates} natively support the R1CS formulation. 
The arithmetic circuit representation can  be
expressed as an R1CS by introducing a constraint for each multiplication gate.
We follow the broad outline of the interactive PCP
construction in \cite{ligero} which includes: (i) extending the witness, denoted as extended witness, to the concatenation of values over all the wires in topological order of an arithmetic circuit  representing the statement   (ii) encoding the extended witness via suitable
error-correcting code, (iii) checking linear relations on the extended witness (for the values concerning the wires going into and coming out from the addition gates), and
(iv) checking quadratic relations on
the extended witness  (for the values concerning the wires going into and coming out from the multiplication gates). Both the linear and quadratic checks require sub-linear (oracle) access to the 
witness encoding.
However, one runs into 
challenges in converting the IPCP to a non-interactive
argument when the witness is distributed across several provers. The naive
approach of provers sharing their encoded witnesses with an aggregator, which
constructs the oracle breaches privacy among the provers, as these encodings
only support {\em bounded independence}, i.e, they maintain privacy only when a
bounded part of the witness is revealed. We overcome this, and several other
technical challenges in our construction. The core techniques behind our
construction are summarized below:
\begin{itemize}
\item We use homomorphic commitment over witness encoding and provide oracle
access to the commitment. This facilitates oracle realization through
aggregation.
\item We design protocols for checking linear and quadratic constraints
with oracle access to the commitment.
\item We come up with new witness encoding scheme, to facilitate smaller
argument size, and reduce communication amongst the provers during distributed proof
generation.
\end{itemize}
While our use of homomorphic commitments introduces expensive cryptographic
operations, we keep their usage strictly sub-linear. In particular, for an
argument size of $O(N^{1/c})$, the verifier 
incurs $O(N^{1-2/c})$ exponentiations. The prover incurs
$O(N/\log N)$ exponentiations essentially while
setting up the oracle. We report the concrete performance of our new zero
knowledge argument $\name$ in Section
\ref{sec:performancecompare}.

%\pnote{Overview of the protocol}