vSQL: Verifying Arbitrary SQL Queries over
Dynamic Outsourced Databases
Yupeng Zhang∗ , Daniel Genkin†,∗ , Jonathan Katz∗ , Dimitrios Papadopoulos‡,∗ and Charalampos Papamanthou∗∗ University of Maryland† University of Pennsylvania‡ Hong Kong University of Science and Technology

Email: {zhangyp,cpap}@umd.edu, danielg3@cis.upenn.edu, jkatz@cs.umd.edu, dipapado@cse.ust.hk
Abstract—Cloud database systems such as Amazon RDS or
Google Cloud SQL enable the outsourcing of a large database toa server who then responds to SQL queries. A natural problem
here is to efficiently verify the correctness of responses returnedby the (untrusted) server. In this paper we present vSQL, anovel cryptographic protocol for publicly verifiable SQL queries
on dynamic databases. At a high level, our construction relies on
two extensions of the CMT interactive-proof protocol [Cormode
et al., 2012]: (i) supporting outsourced input via the use of apolynomial-delegation protocol with succinct proofs, and (ii) supporting auxiliary input (i.e., non-deterministic computation) efficiently. Compared to previous verifiable-computation systems
based on interactive proofs, our construction has verification cost
polylogarithmic in the auxiliary input (which for SQL queries
can be as large as the database) rather than linear.
In order to evaluate the performance and expressiveness ofour scheme, we tested it on SQL queries based on the TPC-H
benchmark on a database with 6 × 106 rows and 13 columns.
The server overhead in our scheme (which is typically themain bottleneck) is up to 120× lower than previous approaches
based on succinct arguments of knowledge (SNARKs), andmoreover we avoid the need for query-dependent pre-processing
which is required by optimized SNARK-based schemes. In ourconstruction, the server/client time and the communication costare comparable to, and sometimes smaller than, those of existingcustomized solutions which only support specific queries.

I. I NTRODUCTION
All major cloud providers offer Database-as-a-Service solutions that allow companies and individuals (clients) to alleviate
storage costs and achieve resource elasticity by delegatingstorage and maintenance of their data to a cloud server.
A client can then query and/or update its data using, e.g.,standard SQL queries. Outsourcing data in this way, however,
introduces new security challenges: in particular, the client
may need to ensure the integrity of the results returned by theserver. Providing such a guarantee is important if the client
does not trust the server, or even if the client is concerned
about the possibility of server errors or external compromise.
Prior works1 on verifiable computation/outsourcing andauthenticated data structures address exactly this problem (seeSection I-D for a detailed discussion), but have significant
drawbacks. Generic solutions (e.g., SNARKs) can be used
to verify arbitrary computations, but impose an unacceptable
overhead at the server. Function-specific schemes (e.g., authenticated data structures) target specific classes of computations
and can be much more efficient than generic solutions; how1 We assume no trusted hardware, nor are we willing to assume multiple,
non-colluding servers (as required by [22]).

ever, they suffer from limited expressiveness, and in particularthey cannot handle a wide range of SQL queries.
A. Our Results
In this work we present vSQL, a system for verifiable SQL
queries. vSQL allows a client who owns a relational databaseto outsource it to an untrusted server while storing only a small
digest locally. Later, the client can issue arbitrary SQL queries
to the server, who returns the query’s result. (In the case of
an update query, the result is an updated digest.) The client
can then verify the validity of the result using an interactive
protocol with the server; if the result returned by the server isincorrect, the client will reject with overwhelming probability.
vSQL overcomes the drawbacks of existing works. It ishighly expressive, supporting any computation expressed as
an arithmetic circuit (which in particular means arbitrary
SQL queries, including updates) efficiently. We empiricallydemonstrate vSQL’s concrete performance and expressivenessusing the TPC-H [7] benchmark, and find that the server-side
computation (which is usually the limiting factor in verifiablecomputation schemes) is 5–120× better for vSQL than it is inhighly optimized libsnark-based constructions [4] (that further
require query-dependent preprocessing), and comparable to or
better than a state-of-the-art database-delegation scheme [60]that only supports a limited subset of SQL.
At a high level, vSQL gains efficiency by combining
two different approaches. First, vSQL uses a highly efficient
information-theoretic interactive proof system [25] for delegating computations expressed as arithmetic circuits. This reduces
the number of cryptographic operations performed by theserver from linear in the circuit size to linear in the lengths ofthe circuit’s inputs and outputs. Second, vSQL supports nondeterministic computation by allowing the server to provide
auxiliary inputs to the circuit. We achieve this by using a novel
scheme for verifiable polynomial delegation with knowledgeextraction properties, improving previous results [56]. To thebest of our knowledge, our protocol is the first implementationof an argument system that supports general non-deterministic
computations and simultaneously achieves the following two
properties: (1) the number of cryptographic operations performed by the prover depends linearly on the circuit’s input
and output size, and (2) the total prover time is quasilinear in
the size of the evaluated circuit. In addition, vSQL benefits
from several performance optimizations that improve both theserver’s and client’s concrete efficiency (see Section VI). We
describe our techniques in further detail next.

B. Our Techniques
Reducing Cryptographic Overhead. A key building blockof vSQL is the information-theoretic interactive proof system
due to Cormode et al. [25] (the CMT protocol) that allows
a client to verify that y = C(x) for some circuit C andinput x known to the client. It is natural in our setting to let
x be the client’s data, and to let C be a circuit corresponding
to the client’s query. While this is a good starting point for
reducing the number of cryptographic operations (since the
CMT protocol is information-theoretic), in our setting wecannot directly apply the CMT protocol since our goal is to
avoid requiring the client to store its data x.
Supporting Delegated Inputs. We observe that at the last
step of the CMT protocol it is sufficient for the client tobe able to evaluate a certain multivariate polynomial px that
depends on x (but not on C) at a random point. We develop
a new polynomial-delegation scheme that allows the client tooutsource px itself; i.e., it enables the client to store a shortdigest comx of px that can be used to verify claimed results
about the evaluation of px on points of the client’s choice.
This allows the client to delegate its input to the untrusted
server while still being able to execute the CMT verifier.
Supporting Auxiliary Inputs. In order to leverage theefficiency improvements provided by non-determinism, we
extend the CMT protocol to support server-provided auxiliary
inputs. (This allows the server to prove that there exists w
such that y = C(x, w).) A straightforward approach forachieving this [56] is to have the server provide the entire
auxiliary input to the client. However, we show that whenevaluating SQL queries it is possible that the auxiliary inputthat is necessary in order to reduce the size of the circuit
being evaluated is as large as the database itself; in thatcase, the naive approach of sending the auxiliary input tothe client is inefficient. Instead, we have the server provide a
succinct commitment to the auxiliary input which will be usedby the CMT verifier. To instantiate this approach efficiently,
we use the polynomial-delegation scheme described above,augmented with a knowledge-extraction property (which is
required for extracting a cheating server’s auxiliary input).
Supporting Efficient Updates. We also build on the above
techniques to handle arbitrary updates efficiently, somethingthat is notoriously hard for previous approaches to verifiable
computation. Say the client wants to apply an update given bya circuit C, and let x0 = C(x). Obviously, having the server
send the result x0 to the client is impractical. To avoid this, wefirst observe that the client need not learn x0 in order to verify
future queries about x0 ; rather, it is sufficient for the client tolearn comx0 . At this point, we could just extend C to a circuit
C 0 that also includes the computation of comx0 and handle
updates the same way we handle queries but this would impose
an additional cost as it would result in a increased circuit
size. Instead, we further observe that this is not necessary: inorder to run the CMT verifier for circuit C, the client need
not know the output (x0 in this case) explicitly; as with the
input, it is enough to be able to evaluate the corresponding

multivariate polynomial px0 at a random point. For this, we
can again use our polynomial-delegation scheme to have theserver first provide the commitment comx0 to the client andthen provably evaluate px0 at a point chosen by the latter,
which is sufficient to prove that comx0 is the new digest.
Eliminating Interaction. Our approach uses the CMT protocol and thus inherits its need for interaction. While this is not amajor barrier (as demonstrated by our experimental evaluationin Section VII), we remark that interaction can be avoidedusing the Fiat-Shamir approach in the random-oracle model.
C. Outline
In Section II we establish notation and introduce the necessary
background. Section III presents our verifiable polynomialdelegation protocol, which is used as a building block forour main construction. We introduce our security definitionin Section IV, and the vSQL construction satisfying this definition in Section V. We discuss a series of optimizations that
improve the performance of our construction in Section VI. In
Section VII we provide a detailed experimental evaluation of
our system. We conclude in Section VIII.
D. Related Work
Verifiable outsourcing of data has been studied from multiple
perspectives, and under various names. Work on authenticated data structures typically focuses on handling only aspecific class of computations on outsourced data, e.g., range
queries [43], [47], joins [59], [62], [30], pattern matching [27],[48], set operations [50], [21], [41], polynomial evaluation [9],graph queries [35], [61], and search problems [45], [46].
The most relevant point of comparison to our work is IntegriDB [60], which supports a subset of SQL. In Section VII,
we show that vSQL is significantly more expressive thanIntegriDB while enjoying comparable efficiency.
Arbitrary computations on outsourced data can be handled
by schemes for verifiable delegation of computation [31], [24].
State-of-the-art systems [10], [51], [26], [52], [57] can handle arbitrary non-deterministic arithmetic circuits by relying
on succinct arguments of knowledge (SNARKs) [14], [32].
SNARKs provide an efficiently verifiable, constant-size proof
for the correct evaluation of a circuit. The major disadvantage
of SNARK-based approaches is the extremely high provertime they currently impose (cf. Section VII). In addition, thefastest existing implementations of SNARKs assume a circuitspecific preprocessing step, something that is not practical(and may be impossible) in a scenario where multiple queries
that cannot be predicted in advance will be made on a given
database. Finally, we remark that the systems mentioned above
are all “natively” designed to support verification only when
the input is known to the client. Support for outsourced data
can be handled by having the client compute a succinct hashof its data, and then verifying the hash computation alongwith verification of the result. However, this adds additional
overhead as the hash computation needs to either be computed
as part of the arithmetic circuit [19], or checked by an externalmechanism [8], [28]. Alternatively, one could hard-code thedatabase into the circuit being evaluated, but then the circuitspecific preprocessing needs to be executed after each database
update. In Section VII, we show that vSQL has significantly
better prover time than SNARK-based approaches.
While some other works also aim at verifying arbitrarycomputations over remotely stored data [23], [17], [38], [20],these approaches are only of theoretical interest at this point.
Interactive proofs were introduced by Goldwasser et al. [34],and have been studied extensively in complexity theory.
More recently, prover-efficient interactive proofs for log-depth
circuits were introduced in [33]. Subsequent works have
optimized and implemented this protocol, demonstrating thepotential of interactive proofs for practical verifiable computation [25], [54], [56].
II. P RELIMINARIES
A. SQL Queries
Structured Query Language (SQL) is a very popular programming language designed for querying and managing relational
database systems. It operates on databases that consist ofcollections of two-dimensional matrices called tables. In thefollowing, we briefly present the general structure of suchqueries and provide concrete examples for common types.
In SQL, a simple query begins with the keyword SELECT
followed by a function A(col1 , . . .) and then the keyword
FROM followed by a number of tables, where A is definedover (a subset of) the columns of the specified tables. Thissequence of clauses and expressions dictates the output of thequery. Following these, there is a WHERE clause followed bya sequence of predicates connected by logical operators (e.g,AND, OR, NOT) that restrict the rows used when computing theoutput. The above is best illustrated by a series of examples.
Consider a database consisting of tables T1 and T2 :T1 :row id
1
2
3
4
5

T2 :

employee id
2019
1905
1908
2117
2003

row id
1
2
3
4
5
6

name
John
Kate
Lisa
Leo
Alice

employee id
1905
1906
1908
2003
2022
2117

age
28
31
44
23
29

salary45,00055,00070,00039,00034,000department
Sales
Sales
HR
R&D
HR
R&D

The first example we provide is a SQL range query which isused to select rows for which particular values fall within aset of specified ranges. The conditions may be defined overmultiple columns, in which case we refer to it as a multidimensional range query. For example, the query “SELECT∗FROM T1 WHERE age < 35 AND salary > 40, 000” is a
two-dimensional range query that returns the following table.
row id12

employee id
2019
1905

name
John
Kate

age
28
31

salary45,00055,000A FROM clause can be followed by JOIN sub-clauses thatare used to combine multiple tables based on common values
in specific columns. An example of such a JOIN query is“SELECT T1 .name, T2 .department FROM T1 JOIN T2 ON
T1 .employee id = T2 .employee id,” which returns:
name
Kate
Lisa
Alice

department
Sales
HR
R&D

The result of any SQL query is itself a table to which another SQL query can be applied. In other words, a SQL query
may be composed of several sub-queries. SQL also provides
queries for adding, updating, and deleting data from a SQL
database. Data-manipulation queries start with an INSERT,
DELETE, or UPDATE clause followed by a table identifier,a series of values, and (optionally) a sequence of WHERE
clauses. For example, the query “DELETE FROM T2 WHERE
department = Sales” deletes the first two rows from T2 . Finally, there are queries that manipulate the database structure,e.g, by adding new columns or creating a new table.
Note that a common theme of the examples presented aboveis that they process each row of some table independently,
performing a specific operation (e.g., comparing values fromgiven columns with a specified range) on each row. In Section V, we discuss how this structure can be leveraged to
improve efficiency in our setting.
B. Interactive Proofs
An interactive proof [34] is a protocol that allows a prover P
to convince a verifier V of the validity of some statement. We
phrase this in terms of P trying to convince V that f (x) = 1,
where f is fixed and x is the common input. Of course, aninteractive proof in this sense is only interesting if the running
time of V is less than the time to compute f .
Definition 1. Let f be a boolean function. A pair of interactive
algorithms (P, V) is an interactive proof for f with soundness if the following holds.
Completeness. For every x such that f (x) = 1 it holds
that Pr[hP, Vi(x) = accept] = 1.
∗
• -Soundness. For any x with f (x) 6= 1 and any P it∗
holds that Pr[hP , Vi(x) = accept] ≤ .

•

Note that the above can be easily extended to prove thatg(x) = y (where x, y are common input) by considering thefunction f defined as f (x, y) = 1 iff g(x) = y.
The Sum-Check Protocol. A fundamental interactive protocol that serves as an important building block for our work is
the sum-check protocol [44]. Here, the common input of theprover and verifier is an `-variate polynomial g(x1 , . . . , x` )over a field F; the prover’s goal is to convince the verifier that
X
X
X
H=
...
g(b1 , b2 , . . . , b` ) .
b1 ∈{0,1} b2 ∈{0,1}b` ∈{0,1}

Note that direct computation of H by V requires at least 2`
work. Using the sum-check protocol, the verifier’s computation

is exponentially smaller. The protocol proceeds in ` rounds,
as follows. In the first round, the prover sends the univaridef P
ate polynomial g1 (x1 ) =b2 ,...,b` ∈{0,1} g(x1 , b2 , . . . , b` );the verifier checks that the degree of g1 is at most thedegree of x1 in g, and that H = g1 (0) + g1 (1); it rejects
if these do not hold. Next, V sends a uniform challengedefrP
1 ∈ F. In the ith round P sends the polynomial gi (xi ) =bi+1 ,...,b` ∈{0,1} g(r1 , . . . , ri−1 , xi , bi+1 , . . . , b` ). The verifierchecks the degree of gi and verifies that gi−1 (ri−1 ) = gi (0) +gi (1); if so, it sends a uniform ri ∈ F to the prover. After the
final round, V accepts only if g(r1 , . . . , r` ) = g` (r` ).
The degree of each monomial in g is the sum of the powersof its variables; the total degree of g is the maximum degreeof any of its monomials. We have [44]:Theorem 1. For any `-variate, degree-d polynomial g overF, the sum-check P
protocol is an
Pinteractive proof for the(no-input) function b1 ∈{0,1} . . . b` ∈{0,1} g(b1 , . . . , b` ) withsoundness d · `/|F|.
C. Multilinear Extensions
Let V : {0, 1}` → F be a function. Then there exists a unique`-variate polynomial Ṽ : F` → F, called the multilinear
extension of V , with the properties that (1) Ṽ has degree
at most 1 in each variable and (2) Ṽ (x) = V (x) for allx ∈ {0, 1}` . Note that Ṽ can be defined as`
X Y
Xbi (xi ) · V (b),(1)
Ṽ (x1 , . . . , x` ) =b∈{0,1}` i=1

where bi is the ith bit of b, and we set X1 (xi ) = xi andX0 (x) = 1 − xi .

Multilinear Extensions of Arrays.
An array A =(a0 , . . . , an−1 ) ∈ Fn , where for simplicity we assume n is a
power of 2, can be viewed as the function A : {0, 1}log n → Fsuch that A(i) = ai for 0 ≤ i ≤ n − 1 (where i is expressedin binary). In the sequel, abuse this terminology and use a
multilinear extension Ã of an array A. A useful property ofmultilinear extensions of arrays is the ability to efficiently
combine two multilinear extensions. That is, let A1 , A2 be
two equal-length arrays, and let A = A1 ||A2 be theirconcatenation. Then Ã(x1 , . . . , xlog n+1 ) can be computed as(1 − x1 )Ã1 (x2 , . . . , xlog n+1 ) + x1 Ã2 (x2 , . . . , xlog n+1 ), i.e.,
as a linear combination of the evaluations of the multilinear
extensions of the smaller arrays. More generally, in the caseof m equal-length arrays A0 , . . . , Am−1 (where m is a powerof 2) the multilinear extension of Ã = A0 || . . . ||Am−1 can beevaluated on a point (x1 , . . . , xlog(nm) ) as
m−1
X log
Ym
i=0 j=1

Xij (xj )Ãi (xlog m+1 , . . . , xlog(nm) )(2)

where ij is the jth bit of i and Xij (xj ) is defined as above.
D. The CMT Protocol
Cormode et al. [25], building on work of Goldwasser et
al. [33], show an efficient interactive proof (that we call the

CMT protocol) for a certain class of functions. The CMT
protocol serves as the starting point for our scheme.
High-Level Overview. Let C be a depth-d arithmetic circuit
over a finite field F that is layered, i.e., for which each gate of
C is associated with a layer, and the output wire from a gate atlayer i can only be an input wire to a gate at level i − 1. The
CMT protocol processes the circuit one layer at a time, startingfrom layer 0 (that contains the output wires) and ending at
layer d (that contains the input wires). The prover P starts byproposing a value y for the output of the circuit on input x.
Then, in the ith round, P reduces a claim (i.e., an algebraicstatement) about the values of the wires in layer i to a claim
about the values of the wires in layer i + 1. The protocol
terminates with a claim about the wire values at layer d (i.e.,
the input wires) that can be checked directly by the verifier V
who knows the input x. If that check succeeds, then V accepts.
Notation. Before describing the protocol more formally we
introduce some additional notation. Let Si be the number ofgates in the ith layer and set si = dlog Si e so si bits suffice
to identify each gate at the ith layer. The evaluation of C on
an input x assigns in a natural way a value in F to each gate
in the circuit. Thus, for each layer i we can define a function
Vi : {0, 1}si → F that takes as input a gate g and returns
its value (and returns 0 if g does not correspond to a validgate). Using this notation, Vd corresponds to the input of thecircuit, i.e., x. Finally, we define for each layer i two booleanfunctions addi , multi , which we refer to as wiring predicates,
as follows: addi : {0, 1}si−1 +2si → {0, 1} takes as input threegates g1 , g2 , g3 , where g1 is at layer i − 1 and g2 , g3 are atlayer i, and returns 1 if and only if g1 is an addition gate
whose input wires are the output wires of gates g2 and g3 . (Wedefine multi for multiplication gates analogously.) The valueof a gate g at layer i < d can thus be recursively computed asX
Vi (g) =addi+1 (g, u, v) · (Vi+1 (u) + Vi+1 (v))
u,v∈{0,1}si+1+ multi+1 (g, u, v) · (Vi+1 (u) · Vi+1 (v)) .
Protocol Details. One idea is for V to verify that y = C(x)by checking that Vi (g) is computed correctly for each gate g ineach layer i. Since Vi (g) can be expressed as a summation, this
could be done using the sum-check protocol from Section II-B.
However, the sum-check protocol operates on polynomials
defined over F and therefore we need to replace terms with
their multilinear extensions. That is:Xfi,z (g, u, v)(3)Ṽi (z) =g∈{0,1}sisu,v∈{0,1} i+1

def

=

X
g∈{0,1}sisu,v∈{0,1} i+1


˜ i+1 (g, u, v) · (Ṽi+1 (u)β̃i (z, g) · add
˜ i+1 (g, u, v) · (Ṽi+1 (u) · Ṽi+1 (v)) ,+ Ṽi+1 (v)) + mult˜ i (resp., mult˜ i ) is the multilinear extension of addi
where add
(resp., multi ) and β̃i is the multilinear extension of the selector
function that takes two si -bit inputs a, b and outputs 1 if a = b

Construction 1 (CMT protocol). Let F be a prime-order field, and let C : Fn → Fk be a depth-d layered arithmetic circuit. P and V hold x, y, andP wants to convince V that y = C(x). To do so:1) Let V0 : {0, 1}dlog ke → F be such that V0 (j) equals the jth element of y. Verifier V chooses uniform r0 ∈ Fdlog ke and sends it to P. Both parties
set a0 = Ṽ0 (r0 ).
2) For i = 1, . . . , d:a) P and V run the sum-check protocol for value ai−1 and polynomial fi−1,ri−1 as per Equation (3). In the last step of that protocol, P provides(v1 , v2 ) for which it claims v1 = Ṽi (q1 ) and v2 = Ṽi (q2 ).
b) Let γ : F → Fsi be the line with γ(0) = q1 and γ(1) = q2 . Then P sends the degree-si polynomial h(x) = Ṽi (γ(x)). Next, V verifies thath(0) = v1 and h(1) = v2 , and rejects if not. Then V chooses uniformly at random ri0 ∈ F, sets ri = γ(ri0 ), ai = h(ri ) and sends them to P.
3) V accepts iff ad = Ṽd (rd ), where Ṽd is the multilinear extension of the polynomial representing the input x.

and 0 otherwise.2 However, this approach would incur a cost to
the verifier larger than the cost of evaluating C, as it requires
one execution of the sum-check protocol per gate.
Instead, by leveraging the recursive form of Ṽi , correctnessof the circuit evaluation can be checked with a single executionof the sum-check protocol for each layer i, as follows. Assume
for simplicity that the output of the circuit is a single value.
The interaction begins at level 0, with the prover claiming thaty = Ṽ0 (0) (i.e., the circuit’s output) for some value y. The twoparties then execute the sum-check protocol for the polynomial
f0,0 in order to check this claim. Recall that, at the end of thisexecution, V is supposed to evaluate f0,0 at a random pointρ ∈ Fs0 +2s1 (the randomness generated by the sum-checkverifier). Since f0,0 depends on Ṽ1 (u) and Ṽ1 (v), in this case
V has to evaluate Ṽ1 on the random points q1 , q2 ∈ Fs1 whereq2 consists of the last s1 entries of ρ, and q1 from the previous
s1 ones. If the verifier had access to all the correct gate values
at layer 1, he could compute these evaluations himself. Since
he does not, however, he must rely on the prover to provide
him with these evaluations, say v1 , v2 . This effectively reduces
the validity of the original claim that y = Ṽ0 (0) to the validityof the two claims that Ṽ1 (q1 ) = v1 and Ṽ1 (q2 ) = v2 . The twoparties can now execute the sum-check protocol for these two
claims. By repeatedly applying this idea, the final claim by theprover will be stated with respect to Ṽd (i.e., the multilinear
extension of the circuit’s input), which can be checked locallyby the verifier who has the input x.
Unfortunately, this approach still potentially requires 2d
executions of the sum-check protocol, since the number ofclaims being verified doubles with each level.
Condensing to a Single Evaluation Per Layer. Efficiency
can be improved by reducing the proof that v1 = Ṽ1 (q1 ) and
v2 = Ṽ1 (q2 ) to a single sum-check execution, as follows. Let
γ : F → Fs1 be the unique line with γ(0) = q1 and γ(1) = q2 .
The prover sends a degree-s1 polynomial h that is supposed
to be Ṽ1 (γ(x)), i.e., the restriction of Ṽ1 to the line γ. The
verifier checks that h(0) = v1 and h(1) = v2 , and then picks
a new random point r10 ∈ F and initiates a single invocationof the sum-check protocol to verify that Ṽ1 (γ(r10 )) = h(r10 ).
Proceeding in this way, it is possible to obtain a protocol thatuses only O(d) executions of the sum-check protocol.
2 Although using β̃ is not strictly necessary [55], we use it in our implementation because it improves efficiency when C is composed of many parallel
copies of a smaller circuit C 0 (as is the case for standard SQL queries).

We assumed so far that there is a single output value y.
Larger outputs can be handled efficiently [56] by adapting theabove approach so that the initial claim by the prover is stateddirectly about the multilinear extension of the claimed output.
The CMT protocol is formally described in Construction 1.3
Theorem 2 ([33], [25], [56], [54]). Let C : Fn → Fk
be a depth-d layered arithmetic circuit. Construction 1 isan interactive proof for the function computed by C withsoundness O(d · log S/|F|), where S is the maximal number ofgates per circuit layer. It uses O(d log S) rounds of interaction,
˜ i and mult˜ iand the running time of P is O(|C| log S). If add
are computable in time O(polylog S) for all layers i ≤ d, thenthe running time of the verifier V is O(n + k + d · polylog S).
The following remark will be particularly useful for us in
the context of evaluating circuits representing SQL queries.
Remark 1 ([54]). If C can be expressed as a compositionof (i) parallel copies of a layered circuit C 0 whose maximum
number of gates at any layer is S 0 , and (ii) a subsequent“aggregation” layered circuit C 00 of size O(|C|/ log |C|), therunning time of P is reduced to O(|C| log |S 0 |).4
E. Bilinear Pairings
We denote by bp := (p, G, GT , e, g) ← BilGen(1λ ) thegeneration of parameters for a bilinear map,5 where λ is the
security parameter, G, GT are two groups of order p (with pa λ-bit prime), g ∈ G is a generator, and e : G × G → GT
is a bilinear map. In Appendix A we present the assumptions
necessary for proving the security of our scheme.
III. V ERIFIABLE P OLYNOMIAL D ELEGATIONAs a key part of our main construction, we use a new scheme
for verifiable polynomial delegation that allows a client tooutsource storage of a multivariate polynomial f to a server
while retaining only a short commitment com. The server can
3 Throughout the paper, when reporting asymptotic complexities we omita factor that is polylogarithmic in the field/blinear group size, implicitly
assuming all operations take constant time.
4 Note that the bound on the running time of V can also be improved if
one makes stronger assumptions about the “regularity” of C 00 . Many common
SQL queries satisfy this condition (e.g., return the average of a range query).
5 For simplicity of exposition we assume symmetric (Type I) pairings. Our
treatment can be extended to asymmetric pairings, which are what we use in
our implementation for better efficiency.

Construction 2 (Verifiable Polynomial Delegation). Let F be a prime-order finite field, ` be a variable parameter, and d be a degree parameter suchthat O( `+`d) is polynomial in λ. Consider the following verifiable delegation protocol that supports the family F of all `-variate polynomials of`dvariable-degree d over F.
QQ
1) KeyGen(1λ , `, d): Run bp ← BilGen(1λ ). Select uniform α, s1 , . . . , s` ∈ F and compute P = {g i∈W si , g α· i∈W si }W ∈W`,d . The publicparameters are pp = (bp, P, g α ).
2) Commit(f, pp): Compute c1 = g f (s1 ,...,s` ) and c2 = g α·f (s1 ,...,s` ) , and output the commitment com = (c1 , c2 ).
3) Evaluate(f, t, r, pp): On input t = (t1 , . . . , t` ) and random challenge r = (r1 , . . . , r`−1 ), compute y = f (t). Using Lemma 1 compute polynomialq` (x` ) and polynomials qi (xi , . . . , x` ) for i = 1, . . . , ` − 1, such that`−1X
f (x1 , . . . , x` ) − f (t1 , . . . , t` ) = (x` − t` ) · q` (x` ) +(ri · (xi − ti ) + xi+1 − ti+1 ) · qi (xi , . . . , x` ).
i=1

Output y and the proof π := (g q1 (s1 ,...,s` ) , . . . , g q`−1 (s1 ,...,s` ) , q` ).
Q?
ri (si −ti )+si+1 −ti+1 , π ) and
4) Ver(com, y, t, π, r, pp): Parse the proof π as (π1 , . . . , π`−1 , qn ). If e(c1 /g y , g) = e(g s` −t` , g q` (s` ) ) · `−1ii=1 e(ge(c1 , g α ) = e(c2 , g), output accept else, output reject.

Definition 2. Let F be a finite field, F be a family of `-variate polynomials over F, and d be a variable-degree parameter.
(KeyGen, Commit, Evaluate, Ver) constitute a verifiable polynomial-delegation protocol for F if:
Perfect Completeness. For any polynomial f ∈ F , if pp ← KeyGen(1λ , `, d) and com ← Commit(f, pp), then for any t ∈ F` and r ∈ F` if(y, π) ← Evaluate(f, t, r, pp) then (1) y = f (t) and (2) Ver(com, t, y, π, r, pp) =accept.
• Soundness. For any PPT adversary A the following is negligible:pp ← KeyGen(1λ , `, d); (f ∗ , t∗ ) ← A(1λ , pp);
Ver(com, t∗ , y ∗ , π ∗ , r, pp) = accept:
Pr∗ 6= f ∗ (t∗ ) ∧ f ∗ ∈ F
∗
`
∗
∗
λ
∗
∧y
com ← Commit(f , pp); r ← F ; (y , π ) ← A(1 , pp, f , r)•

(KeyGen, Commit, Evaluate, Ver) is an extractable, verifiable polynomial-delegation protocol if it additionally satisfies the following:•

Knowledge Soundness. For any PPT adversary A there exists a polynomial-time algorithm E with access to A0 s random tape, such that the following
probability is negligible:pp ← KeyGen(1λ , `, d); (com∗ , t∗ ) ← A(1λ , pp); f 0 ← E(1λ , pp);
Ver(com∗ , t∗ , y ∗ , π ∗ , r, pp) = accept ∧
Pr
:
∗
∗
0
∗
0
(com 6= com ∨ y 6= f (t ) ∨ f ∈/ F)r ← F` ; (y ∗ , π ∗ ) ← A(1λ , pp, r); com ← Commit(f 0 , pp)then respond to requests for the correct evaluation of f on
various points, along with a proof of correctness of the result.
There are several works in the literature addressing thisproblem [39], [13], [29], [49]. Our construction extends thescheme of Papamanthou et al. [49] (which itself extends priorwork [39] to the multivariate case) in order to achieve a“knowledge” property, i.e., to ensure that if the server cancorrectly prove that y is the correct output relative to com forsome input t, then the server in fact knows a polynomial f ofthe correct degree for which f (t) = y. Thus, our construction
can be viewed as a special-purpose SNARK for polynomial
evaluation. The modifications to the prior scheme are relatively
small: we change the commitment to contain two groupelements with “related” exponents (instead of containing one
group element), and change the verification algorithm correspondingly. In the following, we define the variable-degree ofa multivariate polynomial f be the maximum degree of f inany of its variables, and use W`,d to denote the collection of
all multisets of {1, . . . , `} for which the multiplicity of any
element is at most d. Our polynomial-delegation protocol ispresented in Construction 2 and relies on the following lemma.
Lemma 1 ([49]). Let f : F` → F be a polynomial of variable
degree d. For all t ∈ F` and all r1 , . . . , r`−1 ∈ F \ {0}, there
exist efficiently computable polynomials q1 , . . . , q` such that:`−1X
f (x)−f (t) =[ri (xi −ti )+xi+1 −ti+1 ]qi (x)+(x` −t` )q` (x` )We define (extractable) verifiable polynomial delegation in
Definition 2. A proof of the following appears in the fullversion of the paper.
Theorem 3. Under Assumption 1, Construction 2 is a verifiable polynomial-delegation protocol. Moreover, under Assumptions 1 and 2, it is an extractable, verifiable polynomialdelegation
 protocol. Algorithms KeyGen,
Commit run in time`+`dO( `+`d),Evaluate
in
time
O(`d
`d
`d ), and Ver in timeO(` + d). The commitment produced by Commit consists ofO(1) group elements, and the proof produced by Evaluateconsists of O(`) elements of G and O(d) elements of F.
In the context of our verifiable database system (Section V),
our verifiable polynomial-delegation protocol will be used in
two ways. First, the database owner will use it to commit
to its database; all subsequent proofs will be formulated withrespect to that commitment. Queries may possibly be evaluatedon additional auxiliary inputs (beyond the client’s database)generated by the server. In this case the server will produce
commitments to these inputs and the proof will be formulatedwith respect to both the original database commitment andthese additional commitments. In the former case, the necessary security property is soundness alone; in the second case(since the commitment comes from the untrusted server), we
need the stronger notion of knowledge soundness.
IV. M ODEL

i=1

where qn is a univariate polynomial of degree at most d, andti is the ith element of t.

In this section, we present our security definition for a verifiable database system, viewed as a two-party protocol run

Definition 3. A verifiable database system for database class D and query class Q = U ∪ S (where U denotes update queries and S denotes selection
queries), is a tuple of algorithms defined as follows:
1) Setup takes as input 1λ , a database D ∈ D and outputs a digest δ and public parameters pp.
2) Evaluate is an interactive protocol run between two probabilistic polynomial-time algorithms C and S on common input a digest δ, a query Q ∈ Q,
and public parameters pp. Moreover, S holds database D. If Q ∈ S, then at the end of the protocol C either outputs a result y (and accepts) or
rejects. If Q ∈ U , then at the end of the protocol C outputs a new digest δ 0 (and accepts), or rejects.
Denote by Q(D) the evaluation of query Q on database D. We require that Setup and Evaluate have the following properties.
•

Perfect Completeness. For any λ, any D0 ∈ D, any t ≥ 0, and any queries Q1 , . . . , Qt ∈ Q and Q∗ ∈ S, we require that y = Q∗ (Dt ) in thefollowing experiment:– Setup is invoked on the input (1λ , D0 ) and outputs (δ0 , pp).
– For 1 ≤ i ≤ t, do: S and C run Evaluate on inputs (Qi , δi−1 , Di−1 , pp) and (Qi , δi−1 , pp), respectively. If Qi ∈ U , let δi denote the output
of C and set Di = Qi (Di−1 ); otherwise, set δi = δi−1 and Di = Di−1 .
– S and C run Evaluate on inputs (Q∗ , δt , Dt , pp) and (Q∗ , δt , pp), respectively. Let y denote the output of C.

•

Soundness. For any t and polynomial-time attacker S∗ , the probability that S∗ succeeds in the following experiment is negligible:
1) S∗ (1λ ) outputs D0 ∈ D .
2) Setup(1λ , D0 ) outputs (δ0 , pp).
3) For 1 ≤ i ≤ t, do: S∗ outputs Qi . Then S∗ and C run Evaluate on inputs (Qi , δi−1 , Di−1 , pp) and (Qi , δi−1 , pp), respectively. If C rejects,
the experiment ends. If C accepts and Qi ∈ U , let δi denote the output of C and set Di = Qi (Di−1 ); otherwise, set δi = δi−1 and Di = Di−1 .
4) S∗ outputs Q∗ ∈ S. Then S∗ and C run Evaluate on inputs (Q∗ , δt , Dt , pp) and (Q∗ , δt , pp), respectively. Let y denote the output of C. We saythat S∗ succeeds if C accepts with output y, but y 6= Q∗ (Dt ).

between a client that owns a database D which it wishes
to outsource to a remote server. In a setup phase, the clientcomputes a short digest of D, which it stores locally, anduploads D to the server. Subsequently, he issues queries
about the data or requests to update the data, which areprocessed by the server. Each query evaluation is executedby an interactive protocol between the two parties, at theend of which the client either accepts the returned output or
rejects it. Informally, the required security property is that nocomputationally bounded adversarial server can convince theclient into accepting a false result. This is defined formallyin Definition 3. To simplify notation, we do not distinguishbetween verification parameters (that are stored by the clientand should be succinct) and proof-computation parameters(stored by the server).
Supporting Database Size Increases. For some constructions (including ours), the size of the public parameters pp may
depend on the database size. If the database size increases(as a result of updates), it may be necessary to extend pp;
there are various ways this can be done. For instance, thedatabase owner can choose an upper bound for the databasesize, and generate a long-enough pp during the setup phase.
Alternatively, the owner may maintain some (succinct) trapdoor information that allows it to extend pp as needed.
Efficiency Considerations. One important aspect of a verifiable database system is efficiency; a trivial approach is totransmit D for each query and have the client evaluate it
himself. Therefore, a basic efficiency requirement is that thecommunication between client and server for query evaluation
should be sublinear in the database size |D|. Also importantis the client’s computational cost for, which should ideally besmaller than evaluating the query (so the client can benefit not
only from delegation of its storage but also from delegation of
its computation). A final efficiency metric is the computational
overhead of the server, which should ideally be asymptoticallythe same as the cost of evaluating the query.

V. T HE V SQL P ROTOCOL
A. High-Level Description
In this section, we present our construction of a verifiabledatabase system. As mentioned above, our protocol uses
the CMT protocol [25] as presented in Section II-D, as
well as our verifiable polynomial-delegation protocol from
Section III. In the sequel we refer to the prover and verifier of the CMT protocol as (P cmt , V cmt ), and we referto the algorithms of our polynomial-delegation protocol as(KeyGen, Commit, Evaluate, Ver).
Preprocessing Phase. At a high level, we combine the CMT
protocol and our polynomial delegation scheme as follows.
Initially, the client views its database D as an array of |D|elements (where |D| is equal to number of rows times numberof columns) and computes the multilinear extension D̃ as
in Section II-C.6 Note that the number of variables in D̃ islogarithmic in the total size of D. Next, the client generates
a commitment com to D̃ using our polynomial-delegation
protocol, stores com locally, and uploads D to the untrusted
server. We stress that this phase does not depend on any
specific queries the client may choose to issue later.
Query Evaluation Phase. All subsequent queries are validated by running a modified version of the CMT protocol
between the client and the server. Our main observation is thatin the last step of the CMT protocol, V cmt needs to evaluateD̃ at a random point. Since the client no longer knows D̃,the client needs to rely on the untrusted server to provide thisvalue. In order to ensure the correctness of the value provided
by the server, the client and server use our polynomialdelegation protocol relative to the commitment com that theclient holds. The client accepts the answer returned by theserver to its original query only if both Ver and V cmt accept.
6 This can be done by concatenating the |D| elements of the database into asingle array of length |D|, by sorting them first by row and then by column.

Construction 3. Let λ be a security parameter, let D be a database and let F be a prime-order field with |F| exponential in λ.
Setup Phase. On input 1λ and a database D ∈ D, the client picks a parameter N ≥ |D| such that N ∈ O(|D|), which denotes an upper bound on
the size of databases (in terms of values in the database) that can be supported, and sets n = dlog N e. Let D̃ denote the multilinear extension of D. The
client runs KeyGen(1λ , n, 1) to compute public parameters pp, and Commit(D̃, pp) to compute commitment com on D̃. It then sends (D, pp, com)
to the server and stores (pp, com).
Evaluation Phase. Let (x0 , . . . , xN −1 ) be the current version of the database D stored by the server and let com be the commitment stored byboth client and server. Given a query Q ∈ Q, let C be a depth-d circuit over F that evaluates Q on input D and (possibly empty) auxiliary input
B ∈ F|B| . Assume w.l.o.g. that |B| = (2m − 1) · N for some integer m. Partition the input of C into 2m arrays (B1 , . . . , B2m ) each of size N with
B1 corresponding to D and the rest corresponding to the auxiliary input. Finally, let B̃1 , . . . , B̃2m denote the corresponding multilinear extensions of
B1 , . . . , B2m where B̃1 = D̃.
• If Q is a selection query, the two parties then interact as follows:
1) S computes the necessary auxiliary input B2 , . . . , B2m , and runs Commit(B̃i , pp) for 2 ≤ i ≤ 2m to obtain values com2 , . . . , com2m , which
it sends to C.
2) C runs V cmt,1+2 and S runs P cmt to evaluate C(B1 , . . . , B2m ). If V cmt,1+2 rejects at any point, C outputs reject. Otherwise, let rd , ad be
the final values returned by V cmt,1+2 . Let Ṽd be the multilinear extension of the input layer of C. At this point, C must verify that Ṽd (rd ) = ad ,which is done as follows.
m3) C sends to S values ρ(1) , . . . , ρ(2 ) ∈ Fn−1 chosen uniformly at random.
4) S parses rd as rd := (κ1 , . . . , κm+n ) and defines rd0 := (κm+1 , . . . , κm+n ). S then sends to C the evaluations (v1 , . . . , v2m ) of polynomialsB̃1 (rd0 ), . . . , B̃2m (rd0 ) along with corresponding proofs πi computed by Evaluate(B̃i , rd0 , ρ(i) , pp), for all 1 ≤ i ≤ 2m .
5) C runs Ver(comi , rd0 , vi , πi , ρ(i) , pp) for 1 ≤ i ≤ 2m . If any execution outputs reject, C outputs reject. Otherwise, C defines rd00 := (κ1 , . . . , κm )and computes Ṽd (rd ) by combining values v1 , . . . , v2m as per Equation II-C-(2). If Ṽd (rd ) 6= ad , C outputs reject, otherwise accept.
6) The output of S is set to C(B1 , . . . , B2m ).
• If Q is an update query, the two parties then interact as follows:
1) S computes the necessary auxiliary input B2 , . . . , B2m , and runs Commit(B̃i , pp) for 2 ≤ i ≤ 2m computing values com2 , . . . , com2m .
Moreover, it computes the multilinear extension Ṽout of the output of C(B1 , . . . , B2m ) and runs Commit(Ṽout , pp) to compute output commitment
comout . Finally, it sends comout , com2 , . . . , com2m to C.
2) C chooses r0 ∈ Fn , (the output of C is the entire new database which by assumption is at most N therefore its multilinear extension operates on
n = log N elements), and sends it to the server along with a uniform value ρout ∈ Fn−1 .
3) S responds with a0 = Ṽout (r0 ) and corresponding proof πout computed with Evaluate(Ṽout , r0 , ρout , pp).
4) C runs Ver(comout , r0 , a0 , πout , ρout , pp) and rejects if it outputs reject. Otherwise, C runs V cmt,2 while S runs P cmt,2 on common input
r0 , a0 . If V cmt,2 rejects at any point, C outputs reject. Otherwise, let rd , ad be the final values returned by V cmt,2 . Let Ṽd be the multilinear
extension of the input layer of C. At this point, C must verify that Ṽd (rd ) = ad . This is achieved by having C and S perform steps 3–5 from above.
5) The output of S is set to C(B1 , . . . , B2m ) and comout . If C accepts, it sets com ← comout .

B. Adapting the CMT protocol to SQL queries
In this section we discuss how we address various difficulties
that arise when applying our protocol to SQL queries.
Supporting Comparisons. Since our approach utilizes the
CMT scheme, queries need to be encoded as arithmetic
circuits. One side effect of this is that non-arithmetic gates,
such as a comparisons, cannot be handled directly. One way
to handle comparisons in arithmetic circuits is to decompose
the inputs into their bit-level representations, perform thecomparison in binary, and then “glue” the results back together
into a single element. This is inefficient since it requires many
bit-decomposition operations as well as a complicated binary
comparison circuit.
One way to reduce the overhead induced by arithmetic
circuits is to allow the circuit to use additional “advice”
provided by the server in the form of auxiliary inputs, i.e.,
to add support for non-deterministic computations. (So, forexample, rather than compute the bit decomposition of an
input directly, we can instead have the server provide thebit decomposition and then only use the circuit to verify
that the given bit decomposition is correct. We highlightother efficiency benefits of this approach in Section VI-A.)
Unfortunately, the CMT protocol does not naturally support
such auxiliary input.
Supporting Auxiliary Inputs.
Previous CMT-based
works [56] addressed this issue by having the CMT prover
provide the entire auxiliary input to the verifier, effectively

treating the witness as part of the verifier’s input. While thisworks, it is only effective when the size of the auxiliary input
is small compared to the input size. For vSQL, however, we
would like to support auxiliary input whose size is comparable
to the size of the entire database.
Our main observation is that in order to successfully execute
the CMT protocol, all the verifier needs for the input gates(including both the real input and the auxiliary input) is to beable to evaluate the multilinear extension polynomial of the
inputs on a random point. Thus, instead of transmitting theentire auxiliary input to the verifier, the prover can commit
to the multilinear extension of the auxiliary input using ourverifiable polynomial-delegation protocol. To see how thisworks, assume the auxiliary input is the same size as the
database. At the last step of the interactive proof protocol,
the client will request the evaluations of the two polynomials(one for the database and one for the auxiliary input) at thesame random point. The server then responds with the values
and their corresponding proofs. Due to the additive property ofmultilinear extensions, the client can then combine these twovalues in order to reconstruct the evaluation of the multilinear
extension of the entire input to the circuit, as described in
Section II-C. Moreover, since the polynomial commitment isbinding, the client can be sure that the server’s response does
not depend on the random point chosen by the client, thus
preserving the soundness of the interactive-proof protocol.
More generally, this can be applied to any query (even thosethat require auxiliary inputs larger than the database size) byadding sufficient “padding” such that the total circuit input size
(database plus auxiliary input) is a power-of-two multiple ofthe database size (e.g., if auxiliary input is 2 · |D|, it should be
padded with |D| dummy values, thus making the total circuit
input size 4·|D|). The server provides a separate commitment,
evaluation and proof for each database-length “chunk” of theauxiliary input and the evaluation of the multilinear extensionof the entire input is calculated by the client by applying
Equation II-C-(2).
Supporting Expressive Updates. A common problem ofexisting dynamic authenticated data structures (e.g., [47], [60])is that they support limited types of updates: element insertions
and deletions. Thus, they cannot handle general updates thatcan be expressed as SQL queries themselves, e.g., the query
UPDATE Employees; SET Salary = 45000; WHERE Age = 33.
The main reason such update queries are hard to handle
is that the client must eventually compute the corresponding
updated database commitment. Without access to the database,it must again rely on the untrusted server to provide thisnew commitment. SNARK-based constructions can support
expressive updates by including the commitment computationin the circuit. However, this would considerably increase theprover’s overhead. Our approach avoids this cost by separating
the computation of the update from its verification. First, theserver computes the updated database normally, and commits
to the multilinear extension of the result using our verifiable
polynomial delegation scheme. The client and server thenverify that the update was performed correctly by running the
CMT protocol on the circuit that performs the update. In order
to initiate the CMT protocol, the client needs to compute themultilinear extension of the updated database (which is here
the circuit’s output) and evaluate it on a random point. This
would naively require transmitting the entire updated databaseback to the client. Instead, we rely on the server to computethe evaluation for the client, and verify this value using ourverifiable polynomial-delegation scheme. Once this is done,
the remainder of the CMT evaluation proceeds normally.
Exploiting SQL Query Structure. Our construction can beapplied to verify the computation of any arithmetic circuit,which clearly includes SQL queries. But the specific structureof SQL queries allows for additional efficiency improvements.
Concretely, most “natural” SQL queries specify some computation that is applied independently to every database row,followed by a final aggregation/post-processing phase. Thus,
the arithmetic circuit C that corresponds to the entire SQL
query can be written as a sequence of parallel copies of asmaller circuit C 0 corresponding to the single-row logic, where
inputs to C are wired directly to the appropriate copy of C 0 ,and the outputs of the copies of C 0 are wired into a (small)post-processing circuit C 00 . We can thus rely on Remark 1 toimprove the prover’s efficiency.
C. Our Construction
Before describing our construction, we introduce some notation. The client in our construction will be running a modified

version of V cmt that selectively executes some of the threesteps of Construction 1. Let V cmt,1+2 denote a version of theverifier V cmt that only runs the first two steps in Construction 1 and then outputs rd , ad , omitting step 3. Likewise, let
V cmt,2 denote the restricted version of V cmt that on input
r0 , a0 runs only the second step, again outputting rd , ad , andP cmt,2 the similar restricted version of P cmt that runs thesecond step on input r0 , a0 .
Our main construction is given as Construction 3. A proofof the following appears in the full version of the paper.
Theorem 4. If Construction 2 is an extractable, verifiable
polynomial-delegation protocol, then Construction 3 is a verifiable database system for SQL queries.
If Construction 3 is executed on a database D with |D|values, to evaluate a query expressed as a non-deterministic,
depth-d arithmetic circuit C with at most S gates per layer,that consists of parallel copies of a circuit C 0 with at most S 0
gates per layer, followed by a post-processing circuit C 00 of
size O(|C|/ log |C|), and with auxiliary input B, then
1) The running time of Setup is O(|D|).
2) Evaluate requires O(d log S) rounds of interaction.
3) The running time of C is O(k + d · polylog(S) + log(|B| +|D|)), where k is the size of the result for selection queries
and k is O(log |D0 |) for updates (D0 is the output size).
4) The running time of S is O(|C| · log S 0 + (|B| + |D|) ·log(|B| + |D|)).
Local State at the Client. For simplicity, in our description
we assume the client stores the entire public parameters pp,
which are as large as D. However, in practice the client only
needs to store n terms from pp, specifically all terms g τi fori ≤ 1 ≤ n, that are necessary for verifying the evaluationof the multilinear extensions it receives from the server using
our verifiable polynomial-delegation protocol. We also notethat verification does not require any trapdoor information, andtherefore our scheme has public verifiability: namely, anyone
with access to the database commitment produced by the client
and the public parameters can issue and verify queries.
Handling Unbounded Database Size. For simplicity, we
assume that the size of the database will never exceed thebound N . In practice, this can achieved by picking N large
enough. Note however, that this is not a limitation of our construction: a client that stores the n trapdoor values s1 , . . . , snof the verifiable polynomial-delegation scheme can computeadditional elements, as needed, in case the database size
exceeds N . Moreover, our construction has the nice featurethat the work required by the client and the server at any
given time only depends on the size of the actual databaseand not the upper bound N .
VI. P ERFORMANCE O PTIMIZATIONSIn this section, we present a number of optimizations that weapply to the evaluation phase. In particular, we leverage theability of our scheme to efficiently handle auxiliary inputs inorder to: (i) achieve faster equality testing (which is useful forselection queries), (ii) allow for input/output gates at arbitrarylayers of the circuit with minimal overhead, and (iii) verify the
results of set intersections using a smaller number of gates(which is useful for join queries). Finally, we discuss how
simple updates (that consist of assigning values to unused table
cells) can be verified using one round of interaction.
Most of the optimizations discussed below exploit various
techniques for constructing efficient representations of computations commonly when answering SQL queries. These techniques include modifying the queries’ circuit representations
in order to utilize auxiliary inputs, encoding some of the querycomputations directly as polynomials, and utilizing interactionin order to reduce the circuit size. Since these modifications
are applied directly to the underlying circuit being computed,
security when using these optimizations follows readily fromsecurity of our protocol.
A. Optimizing Equality Testing
A very common subroutine used in both selection and joinqueries is testing whether two values are equal, which can be
reduced to testing whether their difference is 0. Here we show
how we can efficiently perform such zero tests using auxiliary
input provided by the prover.
Optimized Zero Testing. Ideally, we would like a smallarithmetic circuit that takes as input a field element x andoutputs x0 = 0 if x = 0 and x0 = 1 otherwise. It is wellknown [25] that, by relying on Fermat’s little theorem, thiscan be done by computing x0 = xp−1 (where p is the fieldsize). This approach is relatively expensive, however, since it
requires a circuit of size and depth O(log p). Instead, we will
construct a non-deterministic circuit for this task that has two
outputs x0 , z and satisfies the following: x = 0 iff there is an
auxiliary input y such that x0 = 0 and z = 0; also, x 6= 0
iff there is an auxiliary input y such that x0 = 1 and z = 0.
Thus, the rest of the computation can use x0 , and the client
will additionally verify that z = 0.
We can achieve the above by computing x0 = xy andz = x · (1 − xy). Note that setting y = x−1 if x 6= 0
(and setting y arbitrarily otherwise) yields correct values forx0 and z. Moreover, if x = 0 then x0 = z = 0 for any
choice of y, and if x 6= 0 then the only way to force z = 0
is to set x0 = 1. We note that the same high-level idea has
appeared before (e.g., [53], [51]) in the context of SNARKs
that are defined based on constraint systems. In our case,
the CMT protocol only supports the evaluation of arithmetic
circuits (and not constraint systems), and so we need a slightly
different technique.
Enforcing Zero Values. A trivial implementation of theabove would require the server to send all the x0 , y values
to the client, resulting in the client performing work linear in
the number of zero tests. Since zero testing may be done atleast once per database row, this will lead to large overheads.
Instead (cf. Figure 1), we split the computation into twoparts: (i) a circuit C1 that computes z = x(1 − xy), and (ii) a
circuit C2 that evaluates the SQL query using the result of theLayer 3x1

y1

. . . xM

yM

Layer 2

R

⇥

R

⇥

Layer 1

R

1

R

1

Layer 0

C1

⇥

...

⇥

C2
Fig. 1. Zero testing. If zi = 0 then the input to C2 is a 0/1 value indicating
whether xi is zero.
z1

zM

zero test (i.e., x0 = xy). Without loss of generality, we assume
the result of the zero test is used at the input layer of C2 , asshown in Figure 1. The client and the server will run two
separate interactive proof protocols for C1 and C2 . First, theprotocol for C2 is executed up to one layer before its input
layer (i.e., the client and server pause before proceeding to
its input layer). After that, the protocol for C1 is initiated.
Note that the honest prover does not need to send any of
the outputs of C1 to the verifier since the verifier knows allof them are supposed to be 0. Moreover, in order to initiate
the execution of this protocol, the verifier needs to computethe multilinear extension of the outputs of C1 evaluated at a
random point. Since the multilinear extension of the 0-vector
is the 0-polynomial, this step is free. Once the interactive
protocol for C1 finishes layer 1, the verifier uses the samerandomness for the next layer of both circuits (layer 2 of C1
and the input layer of C2 , which have the same values).7 This
reduces the claims in both executions to a single evaluationof the multilinear extension of the joint input for that layer.
Finally, layer 3 (the input layer) of C1 is verified normally. In
this way, the prover’s overhead for zero testing is only linear in
the size of C1 , which only has 3 layers. The verifier’s overhead
is only polylogarithmic in the size of C1 .
In our experiments (where dlog pe = 254), the above zero
testing and enforcement method yield an 80× speedup for bothprover and verifier compared to the deterministic approach
using Fermat’s little theorem.
Handling Conjunctions and Disjunctions.
In multidimensional SQL selection queries, AND or OR operators
are applied on the results of multiple selection clauses overdifferent columns, and thus the number of zero tests required
potentially grows with the number of columns. But notethat OR clauses can be trivially reduced to a single zero
test; e.g., testing x1 = 0 ∨ x2 = 0 reduces to testingx1 x2 = 0. We further observe that AND clauses can also be
reduced to a single zero test if the input values are known
top
be in a bounded range.
p For example, if it is known that
− p/2 < x1 , x2 < p/2 then we may reduce evaluating
the conjunction x1 = 0 ∧ x2 = 0 to evaluating whether
x21 + x22 = 0. In particular, if all values in question are
32 bits long and p is a 254-bit value, then we can test
conjunctions involving up to 2189 values using just a single
zero test. Alternatively, we can handle conjunctions using
7 Using the same randomness for both C and C does not affect the12
soundness of the CMT protocol here.

packing: e.g., if x1 , x2 are 32-bit values (and |p| > 64) thentesting whether x1 = 0 ∧ x2 = 0 is equivalent to testingwhether 232 x1 + x2 = 0. These approaches ensure the numberof required auxiliary inputs (as well as the size of the zerotest circuit) for a multi-dimensional selection query depends
linearly on the number of rows in the table and is almost
independent of the number of columns involved in the query.
B. Supporting Inputs/Outputs at Arbitrary Circuit Layers
So far, we have assumed that the circuit being computed takes
all its inputs at the same layer, and produces all its outputs
at the same layer. This is without loss of generality since
one can always define a “relay” gate that simply passes its
input to the next layer. In practice however, such relay gateswill contribute some cost to the execution of the interactiveproof protocol [56]. For many natural SQL queries, this mighteven result in a highly inefficient circuit where most gates arerelay gates. For example, consider an SQL query of the form
SELECT ∗ FROM T WHERE coli = x. A circuit for evaluating
this query takes the entire table as input, but only values
from the ith column are involved in the selection process. All
the other values, from all other columns, are simply relayed
between the various circuit layers.
Avoiding Relaying the Inputs. We now describe a techniquethat avoids relay gates by leveraging the property of themultilinear extension described in Section II-C. Concretely,
consider a circuit C such that some internal layer k operates
on 2M values with m = dlog M e. Assume the second half(denoted by B) of the 2M values are “fresh inputs” (these
may either be from the database itself, or auxiliary input
from the prover), while the first half (denoted by A) comefrom layer k + 1. Before running the CMT protocol for C,
the verifier holds the commitment (either obtained from thepreprocessing or received from the server) to the multilinear
extension, ṼkB , of the fresh inputs to the kth layer. Next, during
the execution of the CMT protocol, the client receives theevaluation of the multilinear extension of the values at layer k,i.e., Ṽk (r1 , . . . , rm+1 ), at some random point (r1 , . . . , rm+1 )as before. As only the first M wires (corresponding to A)
are connected to layer k + 1, the client needs to obtain theevaluation of the multilinear extension (denoted by ṼkA ) of
the first M values, at a random point and use it to continue
the CMT protocol for layer k + 1.
This is done as follows. By Equation 2 in Section II-C,
we have Ṽk (r1 , . . . , rm+1 ) = (1 − r1 )ṼkA (r2 , . . . , rm+1 ) +r1 · ṼkB (r2 , . . . , rm+1 ). Since B are all input gates,
the client can request the evaluation of ṼkB at point(r2 , . . . , rm+1 ) along with a corresponding proof(using the verifiable polynomial-delegation protocol).
Next,
the client computes ṼkA (r2 , . . . , rm+1 )=BṼk (r1 , . . . , rm+1 ) − r1 · Ṽk (r2 , . . . , rm+1 ) /(1 − r1 ),obtaining an evaluation of ṼkA at the random point(r2 , . . . , rm+1 ). The client then uses it to continue theexecution of the CMT protocol for layer k + 1 as usual.

We note that similar optimizations can be performed inorder to avoid relying output gates as well.
Generalizations. For both inputs and outputs, using Equation 2 allows us to avoid relaying a number of input and theoutput gates. We notice that the number of input (resp. output)
gates does not have to be half of the total number of gates in
the layer, but can be any fraction 1/m0 such that m0 is a powerof 2. Moreover, while we described the solution assuming thatthe “fresh” inputs at some layer are all in the second halfof the inputs to that layer, this is not required. With small
modifications we can accommodate more complicated wiring
patterns, e.g., the case where odd wires are routed from theprevious layer and even wires are fresh inputs to the circuit.
C. Verifying Set Intersections
A join operation requires computing the intersection of twolarge sets of column values (assuming for now there are no
duplicates). The naive way to compute the intersection of two
N -element sets, where each element is represents using z bits,
requires a circuit that performs N 2 equality tests on z-bit
inputs. We describe here several ways this can be improved.
A Sorting-Based O(zN log2 N ) Solution. An asymptotic
improvement can be obtained by first sorting the 2N elements,
and then comparing consecutive elements in the sorted result.
Sorting can be done using O(N log2 N ) comparator gadgetsof width z, resulting in a circuit of size O(zN log2 N ) overall.
The concrete overhead of this approach is high, as eachcomparator must be implemented by decomposing the inputs
to their bit-level representations.
A Routing-Based O(zN + N log N ) Solution. Prior
literature on SNARKs [10] improves the above by relying on
auxiliary input from the prover to replace sorting networks
with switching networks that can induce arbitrary permutations
on N elements. Using this approach, the server will simply
specify the permutation that sorts the elements; the client canverify that the elements are sorted in linear time. Switching
networks can be built using O(N log N ) gadgets that swap
their inputs if an auxiliary bit is set to 1. The total complexityof this approach is O(zN + N log N ).
An O(zN ) Interactive Solution. In our setting, where
we have interaction, we can do better. We simply have theserver provide the sorted list x01 , . . . , x02N corresponding tothe original items x1 , . . . , x2N . The client can verify that the
new list is sorted in O(N ) time, so all that remains is for theclient to verify that it is a permuted version of the originallist. This can be done by having the server commit to the
new values (as part of the auxiliary input he computes) using
our verifiable polynomial-delegation scheme. The client thenchooses and sends to the server a uniform value r, and bothpartiesthen run anproof protocol to verify that
QN
QNinteractive0
i=1 (xi − r) −i=1 (xi − r) = 0. Overall, this approachrequires O(zN ) auxiliary inputs and gates.
Sorting 0 Values. The concrete cost can be further reduced
as follows. In case many of the elements are 0, after thesorting step they will be pushed to the front of the auxiliaryinput array (assuming, for simplicity, that all values are
non-negative). Instead of providing one auxiliary input perelement, it suffices for the prover to tell the verifier thenumber of non-zero elements, and only provide auxiliary
inputs for those. For example, assume only the last 1/mof elements are non-zero (where m is a power of 2), using
Equation 2 in Section II-C, the evaluation of the multilinear
extension for all elements at point r = (r1 , . . . , rlog(mn) )is Ṽ (r) = r1 . . . rlog m Ṽm (rlog m+1 , . . . , rlog mn ), where Ṽmis the multilinear extension of the non-zero elements. Thus,
the size of the auxiliary input and the number of necessary
comparisons only depend on the number of non-zero elements(as opposed to the total number of elements).
In the context of SQL queries, the scenario above is very
common. Consider a query where a join clause is applied on
the result of two range queries. It is often the case that onlya small portion of rows in the table fall within the bounds
imposed by the latter. Therefore, after evaluating the range
selection, the values in these rows will be propagated throughthe circuit, while the values in all other rows will effectively be
set to 0. The join query (and therefore the sorting) will then be
applied on this result which has the property that many of its
elements are 0. Thus the above optimization can significantly
lower the join evaluation cost in this case.
Sorting Multiple Columns. Another challenge arises when
the output of a join query includes more than just the reference
column, e.g., SELECT ∗ FROM T1 ,T2 , WHERE T1 .coli =T2 .colj . In this case, in order to compute the set intersection
using the above interactive method, the verifier must makesure that the prover permuted all of the columns of T1 (resp.,
T2 ) with the same permutation used for coli (resp., colj ).
We achieve this using the following packing technique.
Assume for simplicity that each database row has twocolumns with values xi , yi respectively, and that the elements are arranged as tuples (x1 , y1 ), · · · , (xN , yN ). Suppose
the elements xi , yi have length at most z bits, with z <blog pc/2. To sort both columns based on the xi values, we
ask the server to provide auxiliary inputs (a1 , . . . , a2N ) =(xπ(1) , yπ(1) , · · · , xπ(N ) , yπ(N ) ), such that the {xπ(i) } aresorted and the {yπ(i) } are permuted by the same permutation.
The client then chooses and sends to the server two random
values r1 , r2 , and both parties run the interactive proof protocol described above for the following three checks:
QN
Q2N
1) i=1 (xi − r1 )(yi − r1 ) − i=1 (ai − r1 ) = 0;QN
QN2) i=1 (bi − r2 ) − i=1 (b0i − r2 ) = 0, where bi = xi + yi 2z
and b0i = a2i−1 + a2i 2z ;3) (a1 , a3 , . . . , a2N −1 ) are sorted.
The first check guarantees that ai s are a permutation of xi , yi s,
which also implies that ai s have length at most z bits. Now
as xi , yi , ai s all have length at most z bits, the second checkguarantees that ∃π : a2i−1 = xπ(i) and a2i = yπ(i) (note that
we cannot omit the first check as there exist ai s with morethan z bits that can pass the second check ). This, together
with the last check, guarantees xπ(i) s are sorted and yπ(i) sare permuted by the same permutation.
The technique generalizes naturally to sort multiple columns
based on a reference column. As long as the packing result
does not overflow in Fp , we can pack all the columns.
Otherwise, we can duplicate the reference column, perform
a separate packing of subsets of columns, and sort themseparately. In particular, assuming z = 32 and p is 254 bits
long, we can pack up to 7 columns in a single field element.
Handling Duplicate Values. Finally, if there are duplicate
values in the reference columns, the result of a join query
can no longer be described as a set intersection. In this case,a pairwise comparison of the elements of the two columns,
viewed as multisets, provides the correct result but the cost isquadratic in the number of database rows. Instead we can do
the following. First, we extract the unique values from each
multiset (using a linear-size circuit as described in [54]). Then
we compute the intersection of the resulting sets with ourprevious technique for the case of no duplicates. Following
this, we apply again the same technique to intersect thisintersection with each of the original multisets. This returns
two multisets such that: (i) each of them contains exactly thoseelements that appear in both original multisets, and (ii) every
element appears in each multiset exactly the same amount oftimes as it appeared in the the corresponding original multiset.
Finally, the join result can be computed with a pair-wisecomparison of the elements of these two multisets. Note thatthe cost for this final step is asymptotically optimal as it isexactly the same as simply parsing the join’s output.
D. Efficient Value Insertions
As explained above, our construction can handle any update
query by having the server evaluate the update-query circuitand then commit to the output as the new digest. For simple
updates such as adding/subtracting a constant from an element,
we have a much simpler mechanism. By utilizing the closed
form of the multilinear extension, in order to add a constantv to the bth entry in the database, the multilinear extension of
the database is increased by Xb (x1 , · · · , xn )v (as defined in
Equation 1). Therefore, the client only needs to multiply thecommitment of the database by g Xb (x1 ,··· ,xn )v = pvb , where
pb is the bth element of the public key P. In practice, as thesize of P is linear in the size of the database, the client canoutsource its storage to the server and obtain an authenticatedvalue of pb using a Merkle hash tree or digital signatures. Thus,
simple updates of this form can be handled with one round ofinteraction, and the running time for both parties is logarithmic
in the database size using a Merkle tree, or constant using
a digital signature scheme. The update above also captures
inserting a new element/row to the database, which is adding
their values to previously unused cells.
VII. E MPIRICAL E VALUATION
A. Experimental Setup
Software. We implemented our constructions (including thecircuit generator, CMT protocol, and polynomial-delegation

1. SELECT n name, SUM(l extendedprice*(1-l discount))
2. AS revenue
3. FROM customer, orders, lineitem, supplier, nation, region
4. WHERE c custkey = o custkey AND l orderkey = o orderkey
5.
AND l suppkey = s suppkey AND c nationkey = n nationkey
6. AND n regionkey = r regionkey AND r name = ’MIDDLE EAST’
7.
AND o orderdate >= date ‘1997-01-01’
8.
AND o orderdate < date ‘1997-01-01’+interval ’1’ year
9. GROUP BY n name
10. ORDER BY (revenue) DESC;
Fig. 2. Query #5 of the TPC-H benchmark.

protocol) in C++, and compiled it with g++ 4.8.4. We use the
NTL library [5] for number-theoretic operations, and SHA256 in OpenSSL [6] for hashing (in order to instantiate a
random oracle). For the bilinear pairing we use the ate-paring
library [1] on a 254-bit elliptic curve. The EMP toolkit [58]was used for the network I/O between the server and the client.
Hardware and Network. Our experiments were executedon two Amazon EC2 c4.8xlarge machines running Linux
Ubuntu 14.04, with 60GB of RAM and Intel Xeon E5-2666v3
CPUs with 36 virtual cores running at 2.9 GHz. For the
WAN experiments, we used machines hosted in two different
regions, one in the US East and the other in the US West.
The average network delay was measured at 72ms and the
bandwidth was 9MB/s. For each data point, we collected 10
experimental results and report their average.
B. Benchmark Dataset
Database Setup. We evaluate performance using the TPCH benchmark [7], which contains 8 synthetic tables and 22
SQL queries and is widely used by the database community
for performance evaluation. We represented decimal numbers,
dates, and categorical strings in the tables as elements in thefield used by our constructions. In our experimental evaluations, we do not consider substring or wildcard queries, and thecorresponding columns were discarded. The TPC-H database
contains tables of various sizes. The two largest tables usedin our experiments contained 6 million rows and 13 columns
and 0.8 million rows and 4 columns, respectively.
TPC-H Queries. We tested five TPC-H queries: query #2,#5, #6, #15, and #19. As a representative example, query#5 is shown in Figure 2. It gives an example of multi-way
join queries on different columns of different tables. subquery in line 6 is a selection query on table region, and thequery in lines 7–8 is a range query on table order. Lines
4–6 consist of join queries among tables customer, order,
lineitem, supplier, nation, region. In line 1, the result is
projected to three columns, two of which are aggregated.
Finally, in lines 9–10, the aggregated values are summed foreach unique value of n name, and sorted based on n namein descending order.
Query #2 is a nested query. The inner query consists of a 4way join followed by a MIN query, resulting in a single value.
The outer query consists of selection queries, where the resultof the inner query is used as a constraint, followed by a 4way join and projections. Query #6 is a simple 3-dimensional
range query followed by an aggregation. Query #19 consistsof range and selection queries on two tables, followed by asingle join query and an aggregation. Query #15 creates a newtable that is the result of a one-dimensional range query anda SUM query. All the other queries in TPC-H are variants ofthese five queries with different dimensions and constraints.
Query Representation and Field Sizes. For every TPCH query we implemented a circuit generator that takes as
input the database size and outputs an arithmetic circuit forevaluating the specified query on a database of that size, using
the optimizations described in Section VI (when possible).
We implemented both the CMT protocol (Construction 1) andthe verifiable polynomial-delegation protocol (Construction 2)
using a prime-order field with a 254-bit prime.
C. Performance Comparison: Selection Queries
We compare the performance of our construction with prior
work, including IntegriDB [60], a special purpose system
optimized for a class of SQL queries, and libsnark [4], thestate-of-the-art general-purpose SNARK implementation. We
also against (non-verifiable) SQL, based on MySQL. Below,
we report the results on queries #2, #5, #6, and #19.
For IntegriDB, we downloaded the implementation from [2]and executed it on our machine. For libsnark, we estimated theperformance as follows. For each query, we first produced its
circuit representation the jSNARK compiler [3], hardcodeding
the TPC-H dataset in the circuit. This resulted in a circuit
which takes as inputs the values used in selection and range
queries. We then constructed a SNARK using libsnark forthis circuit, and report its performance. We note that thisapproach of hardcoding the database and the query into thecircuit yields a preprocessing phase whose results are only
useful for that specific query and database. In particular,
the results of the preprocessing phase cannot be reused forother queries or databases, or even an updated version of thedatabase. Although clearly unrealistic, this approach gives alower bound on the server time when using a SNARK-based
approach.8 Even with this more efficient approach, we were
not able to generate SNARKs for circuits containing morethan 220 multiplication gates (see Table 7 for the circuit sizesof the queries we used in our evaluation). Therefore, forexperiments requiring larger circuits, we estimated the cost
assuming the prover time grows linearly in the circuit size
(this is, again, an underestimate since the prover time actually
grows quasilinearly in the circuit size).
Setup Phase. The setup phases in both IntegriDB and vSQL
are query independent and thus need to be executed only once,
after which any supported queries can be handled. We run
the setup phases of both IntegriDB and vSQL on all eight
TPC-H tables. The setup for vSQL took about 2,467 seconds.
For IntegriDB, the setup phase could not be completed on theentire TPC-H database due to excessive memory consumption.
Our estimate for the setup phase of IntegriDB was about
8 It is possible to use SNARKs that support arbitrary queries by constructing
a SNARK for a universal circuit [12] and supporting delegation of storage [28], [19]. However, these approaches introduce additional overhead.

Query
#19
#6
#5
#2

IntegriDB
ServerClient6,376s232ms
1,818s
74ms
7
7
7
7

SNARKsServer∗Client∗196,000s
6ms
19,000s
6ms
615,000s
110ms
58,000s
40ms

Server
4,892s3,851s5,069s2,346sClient
162ms
129ms
398ms
508ms

vSQL (ours)
Total (WAN)
4,957s3,869s5,278s2,559sMySQL
Total (NI)4,892s3,851s5,069s2,346s

0.67s
3.92s
4.16s
2.96s

Fig. 3. Comparison of server and client times for evaluating queries using IntegriDB, a SNARK-based approach, our construction, and plain SQL (based on
MySQL). (See text for details.) The numbers in columns marked by * are estimated.
7 denotes an unsupported query.
.

350,000 seconds. Our construction is about 121× faster thanIntegriDB because the complexity of our setup phase is linear
in the number of columns compared to quadratic in IntegriDB.
For libsnark, the setup time depends on the query. The
fastest setup time, for query #6, is estimated to take 36,000
seconds, which is an order-of-magnitude slower than vSQL.
Running setup for all four queries is estimated to require about
1.7 · 107 seconds (roughly 197 days).
Evaluation Phase. The results of the evaluation phase aresummarized in Table 3. The numbers reported in the “Server”
column reflect the computation time required for the server toevaluate the SQL query and produce a valid proof; those in
the “Client” column reflect the time for the client to verify
the proof. For vSQL, in the “Total (WAN)” column we also
report the total end-to-end time which includes the overhead
due to communication between the client and server overa WAN network. For comparison, the total time for IntegriDB
and SNARKs (which are non-interactive) is essentially thesame as the server time, since the client time is negligible.
Note, however, that vSQL can be made non-interactive inthe random oracle model, virtually eliminating the cost ofinteraction at the negligible expense of a small number of
SHA-256 computations. We report the performance of thisnon-interactive mode, including the SHA-256 computation
time, under “Total (NI).”
Evaluation Phase: vSQL vs. IntegriDB. As shown in
Table 3, IntegriDB can only support queries #19 and #6,
compared with vSQL which can support all TPC-H queries.
While being more expressive, the running times of vSQL’sclient and server are on the same order of magnitude as thoseof IntegriDB; in fact, for query #19, vSQL’s server (resp.,client) outperforms that of IntegriDB by about 23% (resp.,30%). We observe also that the cost of interaction for vSQL
(even over a WAN) is small, mainly because prover time isby far the dominating cost.
Evaluation Phase: vSQL vs. SNARKs. Compared tolibsnark, the server time of our constructions is significantly
faster (ranging from 5× for query #6 to 120× for query #5). Ata high level, the better performance of vSQL is a consequenceof two features. First, our construction is mostly informationtheoretic and the number of (relatively slow) cryptographic
operations it requires is linear in the input and output length,
whereas SNARK-based approaches require a number of cryptographic operations linear in the circuit size. In addition, as
described in Section VI, our construction leverages interaction
and auxiliary input to reduce the size of a query’s circuit
representation. Verification when using a SNARK-based ap-

proach is faster than in vSQL since it requires only a numberof cryptographic operations linear in the output length. In
practice, however, the difference is at most 0.5sec which we
consider negligible for most applications. We stress that all
numbers reported for libsnark are underestimations since they
assume the database and queries are fixed in advance. We
expect our construction’s improvement to be even more significant compared to more general SNARK-based systems that
support arbitrary queries and dynamic outsourced databases(see discussion below).
Communication. For libsnark-based systems, the additional
communication required for the proof is always constant (e.g.,
288 bytes). For IntegriDB and vSQL the communication
required in all experiments was under half a megabyte. We
consider this to be negligible in practice for modern networks
and thus omit additional details.
Comparison with Other SNARK-based Systems. SNARKs
can be used for verifiable computation in various ways otherthan the one we used for our comparison.
Exploiting Structured Computations via Bootstrapping. Geppetto [26] takes a complex computation and splits it into
smaller building blocks, each represented as a “small” circuit.
Each such circuit can then be pre-processed with a SNARK
separately. In the context of SQL queries, the natural way tosplit the computation is by having one small circuit that operates on a single row, and then applying that circuit iteratively toeach row in the database. An additional SNARK is then neededto aggregate and verify the outputs of all the smaller SNARKs
into a single succinct proof, in a “bootstrapping” step. In
practice, Geppetto has the potential to significantly reduce thepreprocessing time and memory consumption since the same
small circuit is used throughout the query evaluation. However,
the total prover time to execute the smaller SNARK on every
row is similar to that of the single large SNARK we used as ourbenchmark, as the total number of exponentiations is linear in
the total number of multiplication gates and breaking a large
circuit into multiple smaller ones does not reduce that. Our
results already show that the prover time in that case is up to
2 orders of magnitude slower than for vSQL. Additionally, thebootstrapping phase requires approximately 30,000–100,000
gates per instance of the smaller circuit [26, Section 7.3.1].
Applying this to a table with 6 million rows (as in the TPC-H
dataset) will thus introduce an additional overhead of 1.4–
4.8 × 107 s for the prover, based on our estimations withlibsnark (which is itself an underestimate as the bootstrapping
phase operates over a larger and less efficient elliptic curve).
Memory Delegation via Hash Functions. Pantry [19] canTotal (WAN)
2,106.9s

Total (RO)2,050.8s

Comm.
85.7KB

Fig. 4. Performance of our construction on TPC-H query #15, creating a newtable from table lineitem.

be used to outsource memory by implementing a Merkle
hash tree on top of Pinocchio [51]. The consistency of eachmemory read/write access must be proven by checking thecorresponding Merkle path as part of the SNARK that evaluates the query. This approach has the benefit of allowing
the verifiable evaluation of RAM programs on outsourced
memory (as opposed to expressing the computation directly asa circuit). For SQL queries, assuming the existence of pre-built
database indices (as is typically the case with modern databasemanagement systems), there are programs that can evaluate
certain queries in time sublinear in the database size. (E.g.,
assuming the existence of a search tree that stores the orderedelement values at its connected leaves, a simple 1-D range
query can be evaluated in time logarithmic in the database sizeand linear in the result.) Thus, for specific queries for whichsuch indices can be built, Pantry can in theory outperform
vSQL. Regarding the specific queries we evaluated here, wenote that the number of memory accesses would still be verylarge even with the help of pre-built indices. The simplest
TPC-H query we tested is query #6, which is a 3-dimensional
range query followed by a summation. Assuming a searchtree is built for each dimension and each 1-D range query has
a 1% selectivity (which is well below the selectivity in our
experiments), getting the result of each dimension requires
60,000 memory accesses. In practice, the concrete cost ofproving the correctness of each memory access would beapproximately 2.5s, using a SNARK-friendly algebraic hashfunction [40] for 106 4-byte memory blocks. Therefore, justverifying the memory accesses for query #6 would take around
450,000s (5 days) in this case.
Finally, in contrast to vSQL, both approaches require aquery-specific setup phase that can only be avoided if one
uses a universal circuit [12] or proof-bootstrapping [11], butthese techniques incur considerable additional overheads.
D. Performance Comparison: Update Queries
We test the performance of vSQL on a CREATE query (query#15 in TPC-H). As shown in Table 4, the communication
required is only 85.7KB, even though the newly createdtable is itself more than 1MB in size. IntegriDB cannot
directly support such expressive updates. The only solution for
IntegriDB would be for the client to download the entire newtable, verify its correctness, and preprocess it from scratch.
Next we look at updates that can be supported by IntegriDB, in particular inserting a new row. In this case, vSQL
outperforms IntegriDB since the total time for inserting a
row into the lineitem table in TPC-H is only 5.2ms using
vSQL vs. 1.46s using IntegriDB. This is because the vSQL
client only needs to verify the corresponding elements ofthe public parameters using a Merkle-tree proof and thenperform one exponentiation per column. For IntegriDB, therequired number of exponentiations is quadratic in the number

104
103

query #6
query #5
query #19

Client time (ms)Client85ms

Server time (s)Server
2,049.9s

400
300

102

query #6
query #5
query #19

200

101

100

100
6 × 103 6 × 104 6 × 105 6 × 106
Table size0

6 × 103 6 × 104 6 × 105 6 × 106
Table size

Fig. 5. Performance of vSQL for three TPC-H queries as a function of thenumber of rows in the largest table involved in the query.
Query
#15
#2
#6
#5
#19

# of Inputs
12,002,430
17,840,340
24,004,860
31,397,075
32,406,075

Time (sec)
1,405
1,990
2,715
3,509
3,695

Time/Input (ms)0.11710.11150.11300.11180.1140Fig. 6. Prover time for our polynomial-delegation scheme. The number of
inputs includes both the database and the prover’s auxiliary inputs.

of columns and logarithmic in the number of rows.
In order for a SNARK-based system to support updates,
it must offer a way to check the validity of a new databasedigest returned by the prover. The standard way of doing thisis by incorporating the digest computation in the circuit thatis evaluated, which introduces a huge cost in practice. Morerecent approaches can achieve this via an external mechanismthat is not part of the circuit of the SNARK (e.g., [8], [28]).
Note however, that at the very least the update circuit mustbe evaluated and the SNARK proof must be computed by
the prover. According to our performance comparison in theprevious section, this already takes more time than vSQL.
E. Scalability of Our Construction
In this section, we evaluate the performance of our constructions as a function of the database size. To that end, we run
our construction on the largest three of the previous queries
and scale the number of rows in the largest participating tablefrom 6,000 to 6,000,000.
Server Time. As shown in Figure 5, the server performancefor query evaluation scales almost linearly with the size of thelargest table, matching the theoretical analysis of Theorem 4.
Client Time. Figure 5 shows that the client’s verification time
grows logarithmically with the number of rows in the largest
table participating in a query (note the logarithmic scale of thehorizontal axis). This again matches Theorem 4.
F. Microbenchmarks
In addition to evaluating vSQL’s end-to-end performance, we
also report the performance of vSQL’s main components.
Performance of the Polynomial-Delegation Scheme. Table 6 shows the prover time for our implementation of thepolynomial-delegation scheme (Construction 2). The prover
spends about 0.11ms per input, which is the same orderof magnitude as SNARK-based schemes. Preprocessing forour polynomial-delegation scheme (which is the only part ofour construction that requires preprocessing) took only 2,467
seconds for 95,525,880 inputs (25.8µs per gate).

Query
#2
#15
#6
#19
#5

# of Gates
198,646,335
367,495,719
704,643,060
801,374,196
945,828,996

Time (sec)
356
646
1,137
1,198
1,560

Time/Gate (µs)
1.79
1.76
1.61
1.49
1.65

Fig. 7. Prover time for our implementation of the CMT protocol.

Performance of the CMT Protocol. Table 7 shows theperformance of our implementation of the CMT protocol. As
can be seen, the average time required per gate is about 1.7µs.
VIII. C ONCLUSION
In this work we show how to extend the CMT protocol usinga polynomial-delegation protocol to efficiently support outsourced data as well as auxiliary inputs (i.e., non-deterministic
computations). We then incorporate this new construction into
vSQL, a verifiable database system that can support arbitrary
SQL queries, including updates. Compared to previous generalapproaches, vSQL offers significantly faster evaluation time
for the server as it requires cryptographic work linear in thesize of the query’s inputs and outputs (and independent of thesize of the query’s circuit representation). Our experimental
evaluation demonstrates that in practice this results in a
concrete speedup for the server of up to 120× compared to a
SNARK-based approach, with negligibly larger overhead forthe client. The overall performance of vSQL is comparable to,and sometimes better than, that of IntegriDB, a state-of-the-art
scheme that only supports (and is optimized for) a restrictedsubclass of SQL.
Limitations and Future Work. Our main construction can
support the delegation of any computation that can be represented as a non-deterministic arithmetic circuit, which theoretically includes all possible SQL queries. For many common
operations (such as joins and comparisons), vSQL includes
specific optimizations which reduce the overall circuit size.
vSQL also benefits from the structure of most SQL queries,
which can be viewed as applying the same computation to
every row in a table. In general, however, our optimizations do
not apply to all possible SQL queries. In particular, since somevariants of the SQL language are Turing complete [42], general(and relatively inefficient) reductions from Turing machines
to circuits are required to support them. Moreover, additional
work is needed to handle some operations that arise in many“natural” SQL queries, most prominent of which are substring
and wildcard queries. We leave the task of handling suchqueries efficiently for future work.
ACKNOWLEDGMENTS
We thank the anonymous reviewers for their comments, andAndrew Miller for shepherding the paper. This work was
supported in part by NSF awards #1514261 and #1526950,
financial assistance award 70NANB15H328 from the U.S.
Department of Commerce, National Institute of Standards andTechnology, the Rothschild foundation, and the Warren Center
for Network and Data Sciences.

R EFERENCES[1] Ate pairing. https://github.com/herumi/ate-pairing.
[2] Integridb. https://github.com/integridb/Code.
[3] jsnark. https://github.com/akosba/jsnark.
[4] libsnark. https://github.com/scipr-lab/libsnark.
[5] NTL library. http://www.shoup.net/ntl/.
[6] OpenSSL toolkit. https://www.openssl.org/.
[7] TPC-H benchmark. http://www.tpc.org/tpch/.
[8] BACKES , M., BARBOSA , M., F IORE , D., AND R EISCHUK , R. M.
ADSNARK: Nearly practical and privacy-preserving proofs on authenticated data. In S&P 2015, pp. 271–286.
[9] BACKES , M., F IORE , D., AND R EISCHUK , R. M. Verifiable delegationof computation on outsourced data. In CCS 2013, pp. 863–874.
[10] B EN -S ASSON , E., C HIESA , A., G ENKIN , D., T ROMER , E., AND
V IRZA , M. SNARKs for C: Verifying program executions succinctly
and in zero knowledge. In CRYPTO 2013. pp. 90–108.
[11] B EN -S ASSON , E., C HIESA , A., T ROMER , E., AND V IRZA , M. Scalable
zero knowledge via cycles of elliptic curves. In CRYPTO 2014. pp. 276–
294.
[12] B EN -S ASSON , E., C HIESA , A., T ROMER , E., AND V IRZA , M. Succinct
non-interactive zero knowledge for a von Neumann architecture. In
USENIX Security 2014.
[13] B ENABBAS , S., G ENNARO , R., AND VAHLIS , Y. Verifiable delegationof computation over large datasets. In CRYPTO 2011, pp. 111–131.
[14] B ITANSKY, N., C ANETTI , R., C HIESA , A., AND T ROMER , E. Fromextractable collision resistance to succinct non-interactive arguments ofknowledge, and back again. In ITCS 2012, pp. 326–349.
[15] B ITANSKY, N., C ANETTI , R., PANETH , O., AND ROSEN , A. On theexistence of extractable one-way functions. STOC 2014, pp. 505–514.
[16] B ONEH , D., AND B OYEN , X. Short signatures without random oracles.
In EUROCRYPT 2004, pp. 56–73.
[17] B OYLE , E., G OLDWASSER , S., AND I VAN , I. Functional signatures andpseudorandom functions. In PKC 2014, pp. 501–519.
[18] B OYLE , E., AND PASS , R. Limits of extractability assumptions with
distributional auxiliary input. In ASIACRYPT 2015, pp. 236–261.
[19] B RAUN , B., F ELDMAN , A. J., R EN , Z., S ETTY, S., B LUMBERG , A. J.,
AND WALFISH , M. Verifying computations with state. In SOSP 2013,
pp. 341–357.
[20] C ANETTI , R., C HEN , Y., H OLMGREN , J., AND R AYKOVA , M. Adaptive
succinct garbled RAM or: How to delegate your database. In TCC 2016B, pp. 61–90.
[21] C ANETTI , R., PANETH , O., PAPADOPOULOS , D., AND T RIANDOPOU LOS , N. Verifiable set operations over outsourced databases. In PKC
2014, pp. 113–130.
[22] C ANETTI , R., R IVA , B., AND ROTHBLUM , G. N. Practical delegationof computation using multiple servers. In CCS 2011, pp. 445–454.
[23] C ATALANO , D., F IORE , D., G ENNARO , R., AND N IZZARDO , L. Generalizing homomorphic MACs for arithmetic circuits. In PKC 2014,
pp. 538–555.
[24] C HUNG , K., K ALAI , Y. T., L IU , F.-H., AND R AZ , R. Memory
delegation. In CRYPTO 2011, pp. 151–168.
[25] C ORMODE , G., M ITZENMACHER , M., AND T HALER , J. Practicalverified computation with streaming interactive proofs. In ITCS 2012,
pp. 90–112.
[26] C OSTELLO , C., F OURNET, C., H OWELL , J., KOHLWEISS , M.,
K REUTER , B., NAEHRIG , M., PARNO , B., AND Z AHUR , S. Geppetto:
Versatile verifiable computation. In S&P 2015, pp. 253–270.
[27] D EVANBU , P., G ERTZ , M., K WONG , A., M ARTEL , C., N UCKOLLS , G.,
AND S TUBBLEBINE , S. G. Flexible authentication of XML documents.
In CCS 2001, pp. 136–145.
[28] F IORE , D., F OURNET, C., G HOSH , E., KOHLWEISS , M., O HRIMENKO ,O., AND PARNO , B. Hash first, argue later: Adaptive verifiable
computations on outsourced data. Cryptology ePrint Archive, 2016.
[29] F IORE , D., AND G ENNARO , R. Publicly verifiable delegation of large
polynomials and matrix computations, with applications. In CCS 2012,
pp. 501–512.
[30] F OURNET, C., KOHLWEISS , M., DANEZIS , G., AND L UO , Z. ZQL: A
compiler for privacy-preserving data processing. In USENIX Security
2013, pp. 163–178.
[31] G ENNARO , R., G ENTRY, C., AND PARNO , B. Non-interactive verifiable
computing: Outsourcing computation to untrusted workers. In CRYPTO
2010, pp. 465–482.

[32] G ENNARO , R., G ENTRY, C., PARNO , B., AND R AYKOVA , M. Quadratic
span programs and succinct NIZKs without PCPs. In EUROCRYPT
2013, pp. 626–645.
[33] G OLDWASSER , S., K ALAI , Y. T., AND ROTHBLUM , G. Delegating
computation: interactive proofs for muggles. In STOC 2008, pp. 113–
122.
[34] G OLDWASSER , S., M ICALI , S., AND R ACKOFF , C. The knowledge
complexity of interactive proof-systems. In STOC 1985, pp. 291–304.
[35] G OODRICH , M. T., TAMASSIA , R., AND T RIANDOPOULOS , N. Efficient authenticated data structures for graph connectivity and geometricsearch problems. Algorithmica 60, 3 (2011), 505–552.
[36] G ROTH , J. On the size of pairing-based non-interactive arguments. In
EUROCRYPT 2016, pp. 305–326.
[37] G ROTH , J. Short pairing-based non-interactive zero-knowledge arguments. In ASIACRYPT 2010, pp. 321–340.
[38] K ALAI , Y. T., AND PANETH , O. Delegating RAM computations. In
TCC 2016-B,, pp. 91–118.
[39] K ATE , A., Z AVERUCHA , G. M., AND G OLDBERG , I. Constant-sizecommitments to polynomials and their applications. In ASIACRYPT
2010, pp. 177–194.
[40] KOSBA , A., Z HAO , Z., M ILLER , A., Q IAN , Y., C HAN , H., PAPAMAN THOU , C., PASS , R., ABHI SHELAT, AND S HI , E. C∅c∅: A framework
for building composable zero-knowledge proofs. Cryptology ePrint
Archive, Report 2015/1093, 2015. http://eprint.iacr.org/2015/1093.
[41] KOSBA , A. E., PAPADOPOULOS , D., PAPAMANTHOU , C., S AYED ,M. F., S HI , E., AND T RIANDOPOULOS , N. TRUESET: Faster verifiable
set computations. In USENIX Security 2014, pp. 765–780.
[42] L AW, Y.-N., WANG , H., AND Z ANIOLO , C. Query languages anddata models for database sequences and data streams. In VLDB 2004,
pp. 492–503.
[43] L I , F., H ADJIELEFTHERIOU , M., KOLLIOS , G., AND R EYZIN , L.
Dynamic authenticated index structures for outsourced databases. In
SIGMOD 2006, pp. 121–132.
[44] L UND , C., F ORTNOW, L., K ARLOFF , H., AND N ISAN , N. Algebraic
methods for interactive proof systems. J. ACM 39, 4 (1992), 859–868.
[45] M ARTEL , C., N UCKOLLS , G., D EVANBU , P., G ERTZ , M., K WONG , A.,
AND S TUBBLEBINE , S. G. A general model for authenticated data
structures. Algorithmica 39, 1 (2004), 21–41.
[46] M ILLER , A., H ICKS , M., K ATZ , J., AND S HI , E. Authenticated data
structures, generically. In POPL 2014, pp. 411–423.
[47] PAPADOPOULOS , D., PAPADOPOULOS , S., AND T RIANDOPOULOS , N.
Taking authenticated range queries to arbitrary dimensions. In CCS
2014, pp. 819–830.
[48] PAPADOPOULOS , D., PAPAMANTHOU , C., TAMASSIA , R., AND
T RIANDOPOULOS , N. Practical authenticated pattern matching with
optimal proof size. VLDB 2015, 750–761.
[49] PAPAMANTHOU , C., S HI , E., AND TAMASSIA , R. Signatures of correctcomputation. In TCC 2013, pp. 222–242.
[50] PAPAMANTHOU , C., TAMASSIA , R., AND T RIANDOPOULOS , N. Optimal verification of operations on dynamic sets. In CRYPTO 2011,
pp. 91–110.
[51] PARNO , B., H OWELL , J., G ENTRY, C., AND R AYKOVA , M. Pinocchio:
Nearly practical verifiable computation. In S&P 2013, pp. 238–252.
[52] S ETTY, S., B RAUN , B., V U , V., B LUMBERG , A. J., PARNO , B., AND
WALFISH , M. Resolving the conflict between generality and plausibility
in verified computation. In EuroSys 2013, pp. 71–84.
[53] S ETTY, S. T. V., V U , V., PANPALIA , N., B RAUN , B., B LUMBERG ,A. J., AND WALFISH , M. Taking proof-based verified computation a
few steps closer to practicality. In USENIX Security Symposium 2012,
pp. 253–268.
[54] T HALER , J. Time-optimal interactive proofs for circuit evaluation. In
CRYPTO 2013, pp. 71–89.
[55] T HALER , J. A note on the GKR protocol, 2015. Available at http://people.cs.georgetown.edu/jthaler/GKRNote.pdf.
[56] V U , V., S ETTY, S., B LUMBERG , A. J., AND WALFISH , M. A hybridarchitecture for interactive verifiable computation. In S&P 2013,
pp. 223–237.
[57] WAHBY, R. S., S ETTY, S. T. V., R EN , Z., B LUMBERG , A. J., AND
WALFISH , M. Efficient RAM and control flow in verifiable outsourced
computation. In NDSS 2015.
[58] WANG , X., M ALOZEMOFF , A. J., AND K ATZ , J. EMP-toolkit: Efficient
multiparty computation toolkit. https://github.com/emp-toolkit.

[59] YANG , Y., PAPADIAS , D., PAPADOPOULOS , S., AND K ALNIS , P. Authenticated join processing in outsourced databases. In SIGMOD 2009,
pp. 5–18.
[60] Z HANG , Y., K ATZ , J., AND PAPAMANTHOU , C. IntegriDB: Verifiable
SQL for outsourced databases. In CCS 2015, pp. 1480–1491.
[61] Z HANG , Y., PAPAMANTHOU , C., AND K ATZ , J. Alitheia: Towards
practical verifiable graph processing. In CCS 2014, pp. 856–867.
[62] Z HENG , Q., X U , S., AND ATENIESE , G. Efficient query integrity foroutsourced dynamic databases. In CCSW 2012, pp. 71–82.

A PPENDIX A
B ILINEAR A SSUMPTIONS
We rely on the following assumptions. Let PPT stand for“probabilistic polynomial-time.” To prove security of ourconstruction, we use the following assumptions:
Assumption 1 ([16] (q-Strong Diffie-Hellman)). For any PPTadversary A, the following probability is negligible:
bp ← BilGen(1λ );1RPr : (x, e(g, g) τ +x ) ← A(1λ , σ) τ ← Z∗p ;ττq
σ = (bp, g , . . . , g )Let W`,d denote the set of all multisets of {1, . . . , `} inwhich the multiplicity of any element is at most d.
The next assumption states the following. Assume a polynomial time algorithm that receives as input two orderedsequences of elements of G such that each element contains in
the exponent a multivariate monomial with at most ` variables
and of degree at most ` · d, for some d, and for every orderedpair of elements (across the two sequences) it holds that theelements differ in the exponent by a fixed multiplicative factor
α. Then, if the party outputs a new such pair of elements thatdiffer in the exponent by α, then it must hold that the first ofthese two elements was computed as a linear combination of
the elements of the first sequence (and likewise for the second
and the same linear combination). This fact is captured by theexistence of a polynomial-time extractor that, upon the same
input outputs this linear combination.
Assumption 2 ((d, `)-Power Knowledge of Exponent). For
any PPT adversary A there is a polynomial-time algorithm E(running on the same random tape) such that for all benign
auxiliary inputs z ∈ {0, 1}polyλ the following probability is
negligible:
bp ← BilGen(1λ );Re(h, g α ) = e(h̃, g) 
, α ← Z∗p , τ0 = 1;
 τ1 , . . . , τ`Q


∧ Q


σ1 = {g Qi∈W τi }W ∈W`,d ;YaW i∈W τi Pr  σ2 = {g α· i∈W τi }W ∈W`,d ; :

g


α


σ
=
(bp,
σ
,
σ
,
g
);
W ∈W`,d12 G × G 3 (h, h̃) ← A(1λ , σ, z);6= h(a0 , . . . , a|W`,d | ) ← E(1λ , σ, z)
The above is a knowledge-type assumption that is a direct
generalization of Groth’s q-PKE assumption [37] for the caseof multivariate polynomials. In fact, q-PKE is by definition
the same as (1, q)-PKE,
using our notation. Note that W`,d

has size O( `+`d`d ). In our construction, we will be using
this assumption for the case where d is constant and ` is

logarithmic in the database size. The results of [18], [15] show
the impossibility of knowledge assumptions with respect toarbitrary auxiliary inputs. In the above definition we use thenotion of a benign auxiliary input (or, alternatively, a benign
state generator), similar to [26], [36], [28], to refer to auxiliary
inputs that make extraction possible, avoiding these negative
results. Concretely, our proofs hold assuming the auxiliary
input of the extractor comes from a benign distribution.