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

[Christopher Patton <[e-mail]>]

There wasn't any productive discussion about this at CFRG. Currently the
consensus is to seek adoption of the Mastic draft and consider dropping
Poplar1 later. We can bring it up for discussion at the next PPM meeting,
but if no one strongly objects, we'll ask the chairs to do an adoption call
of the next draft.

Thanks again everyone who chimed in.
Chris P.

On Thu, Mar 14, 2024 at 12:14 PM Christopher Patton <[e-mail]>
wrote:

> 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
>>>
>>