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

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=40cloudflare.com@dmarc.ietf.org> 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 <cpatton@cloudflare.com <mailto:cpatton@cloudflare.com>>
> Date: Mon, Mar 4, 2024 at 8:07 AM
> Subject: Next steps for heavy hitters with VDAFs
> To: CFRG <cfrg@irtf.org <mailto:cfrg@irtf.org>>
> 
> 
> 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
> Ppm@ietf.org
> https://www.ietf.org/mailman/listinfo/ppm