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

[Brandon Pitman <[e-mail]>]

As a DAP implementor, I am in favor of simplifying DAP/VDAF as much as
possible. With that in mind, I am in favor of removing Poplar1 in favor of
Mastic (i.e. any of outcomes #1, #2, or #4 -- I am agnostic on which of
these is the better course, but I suppose #2 is likely to require the least
amount of editorial work, though it might be useful to maintain one or
multiple concrete VDAFs in the VDAF draft itself). I do not see a reason to
maintain two VDAFs which solve roughly the same problem if one of them is
superior to the other, and I agree that lowered round complexity is a
compelling argument for Mastic. If we can conclude that Mastic is
practically superior to Poplar1, IMO we should remove Poplar1.

Also:
> c. If we remove Poplar1, then we could consider restricting the VDAF
syntax to 1 round for preparation.

I agree; the DAP specification & DAP implementations would be considerably
simplified if we were to restrict to 1-round VDAFs. There is quite a bit of
state-tracking complexity involved in multi-round VDAF handling which could
be dropped entirely in a single-round world. Unless there is a concrete
multi-round VDAF providing a great deal of value to the DAP/VDAF ecosystem,
I think this would be a very worthwhile change. If restricting VDAF to a
single round is considered controversial, another option would be to
restrict DAP to single-round VDAFs instead.

Thanks,
Brandon

On Mon, Mar 4, 2024 at 8:14 AM Christopher Patton <cpatton=
[e-mail]> wrote:

> 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.
> --
> Ppm mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/ppm
>