A Gentle Introduction to DAP and Prio

The Distributed Aggregation Protocol (DAP) is really complicated. That complication is in support of a range of multi-party computation (MPC) capabilities. However, in practice it is used for far simpler tasks, like adding numbers.

This post provides an aggressively simplified summary of how DAP works in the modes that people use.

So, in the spirit of “the hardest problem in computer science is counting”, here’s to making adding up more complicated.

Adding numbers

All of the modes in DAP that people use add up numbers. That’s it.

This system is based on a design called “Prio” (paper), which was invented by Henry Corrigan-Gibbs and Dan Boneh. DAP supports other modes than Prio, but this post only looks at Prio.

The basic idea here is that many people have a number. The number might contain something that is private or sensitive, so they don’t want to share it. However, if their number was mixed into an average from many other people, and no longer associated with them, personally, maybe they would be happy to contribute.

DAP is a protocol for taking those numbers and adding them together. It computes the sum of the numbers it’s given.

The important property that DAP provides is that the numbers are never revealed to anyone. It does that with something called secret sharing.

How do you keep a value secret while adding it?

The way DAP does this is that it splits the entire system into two.

Each number is cut into two parts, each of which is effectively completely random. Only when they are put back together does the value make sense. The two parts are sent to two different servers.

Each server adds their parts together and then reports what they got. The client gets those two parts and can add them together to get the answer.

The way you “cut a number in half” is you make up a random number. That’s the first half. The other half is the real number, minus the random number.

$x \to {\begin{cases} r & \to sent to A \\ x - r & \to sent to B \end{cases}$

Each of these two values, on their own, is effectively random. You need both to get the real value. The real value is the two values added together, because the random values cancel out.

To make this work properly, it’s not possible to use normal numbers. You can’t just pick any random number and wing it, you have to work in a ring.

A ring is a closed loop on the number line where, if you run off the end, you wrap around to the other end.

For example, a ring could be all the single digit decimal numbers: ${0, 1, 2, 3, \dots, 8, 9}$ .

The random number is any value from the ring. When you calculate $x - r$ and it goes negative, add 10; similarly, if the result is greater than 10, subtract 10.

For example, say my value is 2 and I draw a random number of 4. The two values I end up with are 4 and 8. That’s because $2 - 4$ wraps around to 8 ( $2 - 4 + 10 = 8$ ). Add 4 and 8 and you get 12, which becomes the original value 2 …once you subtract 10 to keep it on the ring.

Continuing the above example, showing the internal numbers:

Though this looks a bit weird, I promise that I really did generate random numbers for the top block. Not every value ends up being 7 (sometimes it’s 4).

Adding numbers without seeing them

When the two DAP services receive their half the number, they can each add the pieces they have.

The final value each produces is still effectively random – each of them is adding up random numbers – but the sum of those two values is the result! All the randomness cancels out.

$\begin{aligned} S_{a} & = \sum_{i} r_{i} \\ S_{b} & = \sum_{i} x_{i} - r_{i} \\ S_{a} + S_{b} & = \sum_{i} r_{i} + \sum_{i} x_{i} - r_{i} \\ = \sum_{i} x_{i} \end{aligned}$

At this point, the only trick you need to be aware of is that your ring needs to be big enough to hold the answer. If you have a ring of size 10 and your answer is 72, you will get 2 out the other end, losing the 70 part.

In practice, DAP uses very big rings, so this is unlikely to be a problem.

Handling bad inputs?

Unfortunately, DAP has to handle cases where people want to spoil the results. This is where it gets complicated, so I won’t go into too much detail.

If your ring is really big, someone submitting a number could pick any value in that range. That could spoil your results by producing a final sum that is absurdly large or, by overflowing the ring, a value that cancels out what other people submit, resulting in a value that is far too small.

The truly clever part of Prio is in how it handles this. Each client provides a proof that their value is “valid”, without revealing that value.

I won’t go into detail, because this is supposed to be an easy introduction. It boils down to a fairly straightforward application of polynomials, but it’s too much detail for this post.

Prio schemes in DAP

Right now DAP has 6 modes or schemes that are based on Prio.

In Prio3Count each input is a 0 or a 1. As the name implies, this is for counting only. The exposure notification system developed by Apple and Google used something like this. People who were exposed would submit a 1, everyone else submits 0, and the sum is a count of the number of people who were exposed.
Prio3Sum adds up any single number, up to a chosen maximum. This can be used to do things like calculate an average.
Prio3SumVec adds up a set of numbers one by one, where each value is capped to a chosen maximum. This is basically multiple copies of Prio3Sum at the same time, all with the same maximum.
Prio3L1BoundSum adds up a set of numbers, where the sum of the values in the set is capped to a chosen maximum. This is used in the attribution API.
Prio3Histogram adds up a vector, or set of numbers, where all the values must be zero, except any one value, which has to be 1. This can be used to count things in categories, such as how many people earn money in different ranges.
Prio3MultihotCountVec is a version of Prio3Histogram where all the values are 0 or 1, but the number of 1s cannot be more than a chosen cap.

So, while the Prio design can do a lot more, the practical applications all boil down to adding up.

Sounds expensive

In practice, Prio is pretty cheap to operate. It’s more expensive than adding raw numbers for sure, but the price of protecting sensitive inputs is not crazy.

Checking the proof that the input is valid costs a little bit, but the proofs are tiny and modern computers are fast.

The most expensive part is that each server needs to check that the same value is only added up once. With lots and lots of numbers, tracking them all can get a bit tricky.

Applications of Prio

DAP with Prio is useful for adding up numbers, where the individual numbers might be private or sensitive or just a little bit embarrassing.

If many people have somewhat sensitive information, you might want to provide them some assurance that sharing their number won’t get back to them somehow. DAP provides that assurance. A few examples are listed above.

DAP also pairs really nicely with differential privacy, for added privacy protection.

The only condition is that you have to trust one or other of the two services. If they both go rogue and conspire, they can recover the values. So, ultimately, this is probably not something you want to use for real secrets.

Reputable services, such as Divvi Up, which is run by the non-profit that also operate Let’s Encrypt, are unlikely to risk their good reputation that way.

Hopefully, this is enough information to help you understand what Prio and DAP are for.