[Ppm] Fwd: Next steps for heavy hitters with VDAFs

[Christopher Patton <[e-mail]>]

Hi all, I'm cross-posting this message to the CFRG mailing list in the
hopes that folks who would like to implement heavy hitters in DAP will
weigh in. We definitely end to hear from implementers and potential
adopters.

Thanks,
Chris P.

---------- Forwarded message ---------
From: Christopher Patton <[e-mail]>
Date: Mon, Mar 4, 2024 at 8:07 AM
Subject: Next steps for heavy hitters with VDAFs
To: CFRG <[e-mail]>


Hi CFRG,

I've asked the chairs to spend some time at 119 discussing next steps for
Mastic:
https://datatracker.ietf.org/doc/html/draft-mouris-cfrg-mastic-02

The ideal outcome may not be to adopt this draft directly, but to merge it
with the existing VDAF draft (draft-irtf-cfrg-vdaf). Our goal for 119 is to
find consensus on a path forward.

Last time (118) we presented Mastic, a new VDAF that we pitched as a
drop-in replacement for Poplar1 (
https://datatracker.ietf.org/meeting/118/materials/slides-118-cfrg-mastic-vdaf).
Since the meeting we have been working on security analysis for Mastic.
The theorems in this paper claim that Mastic's composition of its
primitives (VIDPF, an extension of IDPF from draft-irtf-cfrg-vdaf) and FLP
(from draft-irtf-cfrg-vdaf) into a VDAF is secure. The concrete parameters
of VIDPF and FLP are subject to change as analysis continues, but the
overall composition seems to be sound:
https://eprint.iacr.org/2024/221

Mastic is also more efficient in terms of round complexity, is easier to
implement securely, and addresses use cases identified in the PPM WG for
which Poplar1 falls short. Overall, Mastic reflects improvements that have
been made to this paradigm (i.e., function secret sharing for heavy
hitters) since the Poplar paper appeared three years ago (
https://eprint.iacr.org/2021/017). The only potential advantage of Poplar1
is that, once we finalize the parameters of VIDPF, it may end up having a
lower bandwidth cost (at most 50% more, I suspect). However, speaking as an
implementer, the lower round complexity of Mastic over Poplar1 makes it the
far better option.

We (the Mastic designers) would like the CFRG to consider the following
outcomes:
1. Replace Poplar1 with Mastic in the base VDAF draft (draft-irtf-cfrg
-vdaf).
2. Adopt the Mastic draft (draft-mourics-cfrg-mastic) and remove Poplar1
from the base draft.
3. Adopt the Mastic draft, but keep Poplar1 in the base draft.
4. Refactor the base draft so that it spells only the VDAF framework, adopt
the Mastic draft, and adopt a new draft for Prio3. Note that there is one
primitive (FLP) that would be shared by both Mastic and Prio3.

Here are the main considerations we've heard while getting feedback on this
question.
a. Since the PPM WG can't finish its work until the base VDAF draft is
done, we should do everything we can to minimize time to RFC.
b. Recommending two protocols (Poplar1 and Mastic) for the same use case
(heavy hitters) is probably not a good idea, especially if one is clearly
superior to the other.
c. If we remove Poplar1, then we could consider restricting the VDAF syntax
to 1 round for preparation.
d. The base draft should use all features of the VDAF framework.
e. Poplar1 involves an MPC paradigm called "arithmetic sketching" (
https://eprint.iacr.org/2023/1012) that may be useful for future VDAFs and
thus worth specifying.

Thanks for your time and we're looking forward to 119,
Chris P.