In a previous post, we looked at the two major challenges developers encounter when developing Zero-Knowledge Proofs: performance and programmability. In this post, we will tackle this by developing a library of “zkGadgets” for Zokrates: a library of common aggregation operations, implemented efficiently for use in ZKPs. The gadgets are open sourced on GitHub.

What is a zkGadget?

A gadget is a small, specialized, and efficient “proof component” that can be composed and re-used as part of a larger proof. This is inspired by the definition of gadgets by Campanelli et al..

In our case, a gadget consists of:

  • some computation that runs in the proof,
  • some computation that happens before the proof (e.g. to pre-compute a value),
  • some computation outsourced to the verifier (e.g. to verify some condition).

Below, we will illustrate this using two examples: calculating the median and the standard deviation.

Median: sorting outside proof

As a first example, imagine that we want to calculate a median in a ZKP. The prover wants to keep the full input list secret, and only wants to expose the median; the verifier on the other hand needs to be sure the median was calculated correctly. Hence, such a program will typically commit to the input data using a hash and then proceed to calculate the median.

Sorting in the ZKP is prohibitively expensive, as it requires a comparison network. Instead, we developed a gadget that pre-sorts the median outside the proof and just checks whether it was sorted correctly in the proof. Thus, the code in the proof looks like this:

def median<N>(u64[N] vals, u32 n) -> u64 {
  for u32 i in 1..N {
    assert(vals[i - 1] <= vals[i]);
  }
  u32 i = n / 2;
  return (n % 2 == 0) ? (vals[i - 1] + vals[i]) / 2 : vals[i];
}

This function checks that the input is sorted and then returns the middle result. Note that it is also necessary for the verifier to check whether all values were included (e.g. using message IDs).

We also use the technique of pre-sorting the list to implement functions that take the minimum, maximum, percentiles, etc. We also have a function that returns all distinct elements in a list that relies on the same technique.

Standard deviation: calculating a square root

Another useful function is the standard deviation. This requires calculating the variance and taking the square root. However, calculating a square root in a ZKP is expensive. It is much cheaper to calculate it outside the proof and verify its correctness in the proof, which only requires a multiplication.

The function to calculate the standard deviation then looks like this:

def stddev<N>(u64[N] vals, u64 stddev) -> u64 {
  u64 var = variance(vals);
  assert(stddev * stddev <= var);
  assert((stddev + 1) * (stddev + 1) > var);
  return stddev;
}

The prover must pass in the values as well as the standard deviation that was pre-computed. The function then calculates the variance and checks that the pre-computed standard deviation is correct. The standard deviation may be passed in as a private input.

Note that this requires the prover to calculate the variance twice: once outside the proof to then take the square root to get the standard deviation, and again in the proof to prove that the root of the correct value was calculated. Even though the variance is calculated twice, this is still more efficient than calculating a square root in the proof.

Gadget library

We have developed a library of such gadgets, summarized in the following table. We support all aggregation functions supported by Apache Flink (used by AWS), except those that work on strings or JSON, as well as a few additional functions (median, top/bottom N, any/every).

Operation Type signature Google Azure Flink Complexity
Count []u64 -> u32 ✅ ✅ ✅ $O(1)$
Count distinct []u64 -> u32 ❌ ✅ ✅ $O(n)$
Collect distinct []u64 -> []u64 ❌ ❌ ✅ $O(n)$
Sum []u64 -> u64 ✅ ✅ ✅ $O(n)$
Max, min []u64 -> u64 ✅ ✅ ✅ $O(n)$
Average []u64 -> u64 ✅ ✅ ✅ $O(n)$
Variance (population, sample) []u64 -> u64 ❌ ✅ ✅ $O(n)$
Std dev (population, sample) []u64 -> u64 ❌ ✅ ✅ $O(n)$
Median []u64 -> u64 ❌ ❌ ❌ $O(n)$
Top N, bottom N []u64 -> []u64 ❌ ✅ ❌ $O(n)$
Top distinct N, bottom distinct N []u64 -> []u64 ❌ ❌ ❌ $O(n)$
Rank []u64 -> u32 ❌ ❌ ✅ $O(n)$
Dense rank []u64 -> u32 ❌ ❌ ✅ $O(n)$
Percent rank []u64 -> u32 ❌ ❌ ✅ $O(n)$
Cume dist []u64 -> u32 ❌ ❌ ✅ $O(n)$
Row number []u64 -> u32 ❌ ❌ ✅ $O(n)$
Ntile []u64 -> u64 ❌ ❌ ✅ $O(n)$
Percentile []u64 -> u64 ❌ ✅ ✅ $O(n)$
First, last []u64 -> u64 ❌ ✅ ✅ $O(1)$
Lead, lag []u64 -> u64 ❌ ❌/✅ ✅ $O(n)$
Any, every []bool -> bool ❌ ❌ ❌ $O(n)$
Bitwise AND, OR, XOR []bitmap -> bitmap ❌ ✅ ❌ $O(n)$
❌ List agg ([]string, string) -> string ❌ ❌ ✅
❌ JSON object agg [](string, T) -> JSON ❌ ❌ ✅
❌ JSON array agg []T -> JSON ❌ ❌ ✅

Our library relies on a few tricks:

  • Zero-padded lists, because they must have a static size.
  • Sorting outside proof for median and many others.
  • As there is no while loop, we always loop over the whole list and only update when needed.
  • The square root (e.g. std dev) is calculated outside the proof and checked in proof.
  • As ZoKrates only supports integers, we use some tricks like delaying divisions until the end (variance) or multiplying percentiles by 100.

Limitations

There are a few limitations to our approach:

  • We leak some additional data, for instance the order of the values of messages. (If messages have a public ID and a secret value, and they are pre-sorted, the IDs are leaked in the order of the values.) This may not be obvious to the user.
  • Even though we implement a bunch of statistical functions, they only work on integers as ZoKrates has no support for floating-point numbers.
  • Our current implementation is for ZoKrates. RISC-Zero, Nexus, and Jolt are (more recent) platforms for ZKPs that allows proofs to be implemented Rust and rely on different proof techniques. These support floating-point operations and have quite different performance characteristics. Some of our optimizations will still work in this setting (e.g. pre-sorting), but there may also be new opportunities.

Furthermore, in the future we could add some additional gadgets for common streaming operations. In particular parsing JSON (or Protobuf or other data formats) would be useful. We could build a small compiler that, from a schema of the message, automatically builds a proof that checks that the message is well-formed and extracts the relevant fields.

Conclusion

In the end, using these gadgets a developer can build an application in ZK, by combining the gadgets that are implemented in an efficient and secure way, and without needing to re-invent the wheel every time.

The gadgets are open sourced on GitHub.

In the longer term, we could also create a compiler that takes a SQL query (or a dataflow script) and compiles it to a ZKP. This would allow developers to write their queries in a simple, high-level language and then have them executed in a ZKP, without needing to know the intricacies of ZKPs but still benefiting from their confidentiality and integrity properties.

References