Skip to main content
With the ADS architecture in place, we can now conduct queries on the zkDB. Let’s explore how this is done. Note that all queries return the count for the number of satisfying users (or number of rows) in the database. This is for privacy reasons, we will not return actual user data.

​
Anatomy of a Query

A query is a request for information from the database. More importantly, we can construct virtually any query we would like from a few basic operations.
  • Set membership: a∈{b1,b2,…,bn}a\in \{b_1, b_2, \ldots, b_n\}
  • Set non-membership: a∉{b1,b2,…,bn}a\notin \{b_1, b_2, \ldots, b_n\}
  • Intersection: {a}∧{b}={a1,a2,…,am}∩{b1,b2,…,bn}\{a\}\land \{b\} = \{a_1, a_2, \ldots, a_m\} \cap \{b_1, b_2, \ldots, b_n\}
  • Union/Join: {a}∨{b}={a1,a2,…,am,b1,b2,…,bn}\{a\}\lor \{b\} = \{a_1, a_2, \ldots, a_m, b_1, b_2, \ldots, b_n\}
  • Sum: ∑iai\sum_i a_i
  • Count: ∣{a}∣|\{a\}|
  • Min, Max: min⁡({a}),max⁡({a}\min (\{a\}), \max (\{a\})
  • Mean, Median: mean({a}),median({a})\text{mean} (\{a\}), \text{median} (\{a\})
Using these we can conduct any user-data related query we would like. Moreover, we can represent this query in a specific way, namely as q1∨q2∨⋯∨qmq_1 \lor q_2 \lor \cdots \lor q_m where each qiq_i is of the form qi=c1∧c2∧⋯∧cl,q_i = c_1 \land c_2 \land \cdots \land c_l, and each cjc_j is set (non-)membership.

​
Query Engine

We have to do things in a certain order to ensure it is efficient and flexible.
1

Grab accumulators from ADS

Since our ADS has leaves with accumulators representing single values, we have to take them from the data structure one by one along with their Merkle proofs.
2

Conduct inner unions

In order to conduct ranges or set membership, we need to create a new accumulator that contains all values in the range or set. So grab each accumulator for each value in the range, and conduct a union on them (for the polynomials this is equivalent to the lcm operation).
3

Conduct intersections

After all the unions, we have union proofs, as well as the union accumulators. Now we can conduct the intersection proofs of each cj.c_j.
4

Conduct outer union

Now that we have some intersection accumulators and their proofs, we can conduct the outer union proof.
5

Property

Finally, we can conduct a property assessment of the accumulator, such as a count (the number of users in the accumulator), min, max, mean or median. We have subprotocols we can apply to the resulting accumulator from the previous step to get these values.
Verifiers can check the query by checking the proofs in iteration:
  1. Check the ADS proof to ensure the database is valid.
  2. Check the Merkle proofs to ensure that the accumulators were grabbed correctly.
  3. Check the inner union proofs to ensure that the unions were conducted correctly.
  4. Check the intersection proofs to ensure that the intersections were conducted correctly.
  5. Check the outer union proof to ensure that it was conducted correctly.
  6. Finally, check the property proof to ensure that the result is correct.
In the image below is a birdseye view of the process, assuming count as the property check. Query flow

​
Query Example

Let’s say we want to find all users with a Masters or PhD who live in London or Istanbul. Our query would be.
(education ∈\in {Masters, PhD}) ∧\land (location ∈\in {London, Istanbul})
To conduct this we would:
  1. Grab the accumulators for Masters and PhD, and conduct a union on them.
  2. Grab the accumulators for London and Istanbul, and conduct a union on them.
  3. Conduct an intersection on the two unions.
  4. Conduct the outer union on the intersection (in this case there is only one accumulator, so this step is redundant).
  5. Count the number of users that satisfy the query (this is the degree of the accumulator polynomial we just made).
If we wanted to include the outer union necessity, we could instead query for all users with a Masters or PhD who live in London or Istanbul, or users with a Masters in Hong Kong. This would be.
((education ∈\in {Masters, PhD}) ∧\land (location ∈\in {London, Istanbul})) ∨\lor ((education ∈\in {Masters}) ∧\land (location ∈\in {Hong Kong}))
⌘I