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

[Christopher Patton <[e-mail]>]

Hi folks, I'll be giving and update on Mastic at CFRG on Monday:
https://datatracker.ietf.org/meeting/119/materials/slides-119-cfrg-next-steps-for-draft-mouris-cfrg-mastic

We'll spend some time discussing this question.
Chris P.

On Mon, Mar 4, 2024 at 6:58 PM Eric Rescorla <[e-mail]> wrote:

>
>
> On Mon, Mar 4, 2024 at 5:20 PM Christopher Patton <cpatton=
> [e-mail]> wrote:
>
>> Thanks PPM and CFRG, this has been helpful.
>>
>> So far it seems like there is a plurality in favor of adopting a separate
>> draft for Mastic and only consider dropping Poplar1 once we're more certain
>> about the trade-offs. It would be nice to hear from anyone who is strongly
>> opposed to this plan.
>>
>
> To restate what I think you said, I think it's fine to adopt Mastic. I
> would defer a decision on Poplar until after we know more.
>
> -Ekr
>
>>
>> One concern that's been brought up is the editorial effort required to
>> maintain both. Speaking as an editor of both Mastic and Poplar1, I think
>> there is likely to be some duplicative effort here: most of the low level
>> algorithmic bits these protocols have in common (i.e., IDPF) have been
>> stable for some time, but there are also some evolving security
>> considerations that apply to both (around safe usage of IDPF). I also
>> expect there to be some security considerations that apply to Poplar1, but
>> not Mastic.
>>
>> Chris P.
>>
>> On Mon, Mar 4, 2024 at 2:33 PM Shan Wang <shan_wang=
>> [e-mail]> wrote:
>>
>>> I'm in favour of either
>>> 1. Replace Poplar1 with Mastic in the base VDAF draft
>>> (draft-irtf-cfrg-vdaf).
>>> Or
>>> 4. Refactor the base draft so that it spells only the VDAF framework,
>>> adopt the Mastic draft, and adopt a new draft for Prio3.
>>>
>>> If we do 4. The we can cut an individual Poplar RFC too and anyone have
>>> implemented Poplar1 can refer to that standard.
>>>
>>> In my opinion, VDAF should define a common framework. We will have more
>>> algorithms in the future and they should be cut as individual drafts that's
>>> compatible with VDAF, rather than part of the VDAF text itself.
>>>
>>> Shan
>>>
>>>
>>> On 4 Mar 2024, at 16:13, 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
>>>
>> _______________________________________________
>> CFRG mailing list
>> [e-mail]
>> https://mailman.irtf.org/mailman/listinfo/cfrg
>>
>