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

[Eric Rescorla <[e-mail]>]

On Mon, Mar 4, 2024 at 11:14 AM Simon Friedberger <[e-mail]> wrote:

> I am, of course, in favor of reducing complexity, however I am weakly
> against dropping it. My main concerns are:
>
>    1. The texts are written and the protocols are implemented. We can
>    reduce the complexity but we would also be throwing away a lot of effort
>    which already went into this.
>    2. We don't really know how Poplar and Mastic compare. 50% report size
>    overhead would be quite a lot given the scale that these things are
>    designed for. I think we should do some benchmarking before making this
>    decision.
>    3. Similarly, we don't have a good grasp on what we can do with VDAFs
>    and DAP and how much power we would lose by reducing preparation to one
>    round. Is Prio+ better for some use-cases? We certainly could do much more
>    powerful MPC with multiple rounds.
>
> We should leave the standards as is until we have better evidence to
> support a decision.
> If implementations want to remove the code they can always do so anyway.
>

I agree with Simon.

I would also note that this is not really a decision for CFRG, whose job,
at some level, is to deliver what the IETF needs. I see PPM is CCed on this
e-mail, so I'd encourage there to be a discussion in the PPM meeting

-Ekr


>
> So, I'm with Tim.
>
> MfG,
> Simon
>
>
>
> On Mon, Mar 4, 2024 at 6:36 PM Brandon Pitman <bran=
> [e-mail]> wrote:
>
>> 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
>>>
>> --
>> Ppm mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/ppm
>>
> --
> Ppm mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/ppm
>