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

[Simon Friedberger <[e-mail]>]

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.

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
>