Re: [Ppm] Fwd: Next steps for heavy hitters with VDAFs
Syed Suleman Ahmad <suleman.ietf@gmail.com> Mon, 04 March 2024 19:29 UTC
Return-Path: <suleman.ietf@gmail.com>
X-Original-To: ppm@ietfa.amsl.com
Delivered-To: ppm@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id DB028C14F61A for <ppm@ietfa.amsl.com>; Mon, 4 Mar 2024 11:29:58 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -7.094
X-Spam-Level:
X-Spam-Status: No, score=-7.094 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-5, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_KAM_HTML_FONT_INVALID=0.01, T_SCC_BODY_TEXT_LINE=-0.01, URIBL_BLOCKED=0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001] autolearn=unavailable autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([50.223.129.194]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id fucwvZVGbX3W for <ppm@ietfa.amsl.com>; Mon, 4 Mar 2024 11:29:53 -0800 (PST)
Received: from mail-lf1-x129.google.com (mail-lf1-x129.google.com [IPv6:2a00:1450:4864:20::129]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A208DC151070 for <ppm@ietf.org>; Mon, 4 Mar 2024 11:29:53 -0800 (PST)
Received: by mail-lf1-x129.google.com with SMTP id 2adb3069b0e04-513173e8191so5942955e87.1 for <ppm@ietf.org>; Mon, 04 Mar 2024 11:29:53 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1709580592; x=1710185392; darn=ietf.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=eGt1smLzQx8jNqbmuZ3PTWNkinh+N7ZtQS7ga+ZaK1w=; b=aXevaUZgidkWs3Clj76jvxuVzulh4Vv8hLZ82LmVg8/d9PleiS1UHcTf+gZwLqX1a1 PI+yX5Z6TL1v/E/5R4mrXk9zMrsco5XWqWaHwDX4yRiPpOQ8NBs4MMLDRpAOwQ0aHqeJ M7O0F80kISGbhS+RWmgQXeu1am3jyWX7ksF9tCUllNlAjtmAvNhVFUXrHpglQh7r+KuC XJJXj3fxzuxpkp2BgQO6QYY2szaQuDZkARLorRm8O0e9dqYhltJ/WGXqZVm3WGqd+hlt pLnHaaqkXnQ55qauI0xuUoxjNd0o6128cKNd1ubCwQFDd0Divk2ylE6/FCQkqTwC9Q8N VKUg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1709580592; x=1710185392; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=eGt1smLzQx8jNqbmuZ3PTWNkinh+N7ZtQS7ga+ZaK1w=; b=ZaYNm8Bn28xJ2QB2xmhQGnqifdlRSFHTu5J+Y4JeWijrGYMA/FxUqRYj4Y66xoEgx+ ZBmaNzPE3Jrn7UZJd/H4Lax9K7On5YxpZfIluBib+kAHv6O/rKHEtOP//nOwcM4isa/L 9g58242bb5Kd67HwWX+Sk1Djh4mlcH8ovyAYPIYzadQx68ynZ47Y2PywhnLUpv3Gpqt6 qzPI8/PclSLEcdhRwvJ1Y2aJ1wMf2op02hM9NeLhnYa/A+GDA37qyAA5h5i12WMz672e vH41UuqKF77KWN2h0CUyBLpG+sBOBYsi8/YKwzJ7+52nLrdAjfySydSY3fjK3VMmPZky bajA==
X-Forwarded-Encrypted: i=1; AJvYcCW6p5pu49XAYLZKd4aRERr4m1qYIaiYo66OmngqboJyekpufbR/QgoCUGS6PabmDiSzNK7SExnsdXCk9gA=
X-Gm-Message-State: AOJu0YzKqRjrSxBq+ETPxOYjohuObzJZYffR81RA4LXHwMmpnFAeRZMY ubbGt/M/WL+cn7EgLjutdYGQ/1+D/OvhUESigAD+pFPLjxUHklqeOCqYyRO0DHHb34PFM6K6BGr yOMD38CvLTfT8yIZrZGZfC6Q1Kza4xHSDtZw=
X-Google-Smtp-Source: AGHT+IHlxk+/Txlb+T+dxvXQn5sTBBlsGlmoxvUP2QqDhwF0McokFT6szSMOBOj7VFdFB33UttkMzVHDbTwOzV5Kcxk=
X-Received: by 2002:ac2:44cd:0:b0:513:315e:a6d1 with SMTP id d13-20020ac244cd000000b00513315ea6d1mr5821332lfm.66.1709580591293; Mon, 04 Mar 2024 11:29:51 -0800 (PST)
MIME-Version: 1.0
References: <CAG2Zi23iR68MTLnW-onPhfq4rKmeYqgdsE4h_nem2iWFrVLqdw@mail.gmail.com> <CAG2Zi231jVNBvN7vZ6Uz2uTLd7JyS2-hpERUYrkQf1w-KxJtCQ@mail.gmail.com> <CALbTCT3W=JJFSZBOjs2pwiSnyUEwS4ur8roknRrbQUAf8QQG9w@mail.gmail.com> <CAGkoAS05FqFgSyXXH4cgzs98ASgP0b91-YSWZTHeKK-1Xer8qw@mail.gmail.com>
In-Reply-To: <CAGkoAS05FqFgSyXXH4cgzs98ASgP0b91-YSWZTHeKK-1Xer8qw@mail.gmail.com>
From: Syed Suleman Ahmad <suleman.ietf@gmail.com>
Date: Mon, 04 Mar 2024 13:29:39 -0600
Message-ID: <CADhrA--0bvpQW41jLbLtRDGiETJ43fdD2oVv1PaEgOMjiqG-qw@mail.gmail.com>
To: Simon Friedberger <simon@mozilla.com>
Cc: Brandon Pitman <bran=40divviup.org@dmarc.ietf.org>, Christopher Patton <cpatton=40cloudflare.com@dmarc.ietf.org>, ppm <ppm@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000dbeb550612dabf3d"
Archived-At: <https://mailarchive.ietf.org/arch/msg/ppm/tW-x4UBlM4Y9XuGUNu-XejfToVM>
Subject: Re: [Ppm] Fwd: Next steps for heavy hitters with VDAFs
X-BeenThere: ppm@ietf.org
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: Privacy Preserving Measurement technologies <ppm.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/ppm>, <mailto:ppm-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/ppm/>
List-Post: <mailto:ppm@ietf.org>
List-Help: <mailto:ppm-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/ppm>, <mailto:ppm-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 04 Mar 2024 19:29:58 -0000
I would prefer removing Poplar1 from the base draft as Mastic seems to be a drop-in replacement for it. Mastic seems to cover Poplar1’s main use case with far lesser implementation complexity (it would be great to see more benchmarking though) – so I don't see value in providing an example of Poplar1 in the VDAF base draft that already has a superior alternative (an implementer would go for the option that is more lighter and maintainable). My support would be for option 1 or 4 i.e. preferring simplicity in the design. +1 to Brandon. ~ Suleman On Mon, Mar 4, 2024 at 1:14 PM Simon Friedberger <simon@mozilla.com> 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. > > So, I'm with Tim. > > MfG, > Simon > > > > On Mon, Mar 4, 2024 at 6:36 PM Brandon Pitman <bran= > 40divviup.org@dmarc.ietf.org> 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= >> 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> >>> Date: Mon, Mar 4, 2024 at 8:07 AM >>> Subject: Next steps for heavy hitters with VDAFs >>> To: CFRG <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 >>> >> -- >> Ppm mailing list >> Ppm@ietf.org >> https://www.ietf.org/mailman/listinfo/ppm >> > -- > Ppm mailing list > Ppm@ietf.org > https://www.ietf.org/mailman/listinfo/ppm >
- [Ppm] Fwd: Next steps for heavy hitters with VDAFs Christopher Patton
- Re: [Ppm] Fwd: Next steps for heavy hitters with … Brandon Pitman
- Re: [Ppm] Fwd: Next steps for heavy hitters with … Simon Friedberger
- Re: [Ppm] Fwd: Next steps for heavy hitters with … Syed Suleman Ahmad
- Re: [Ppm] Fwd: Next steps for heavy hitters with … Eric Rescorla
- Re: [Ppm] Fwd: Next steps for heavy hitters with … Christopher Patton
- Re: [Ppm] Next steps for heavy hitters with VDAFs Shan Wang
- Re: [Ppm] Next steps for heavy hitters with VDAFs Christopher Patton
- Re: [Ppm] [CFRG] Next steps for heavy hitters wit… Eric Rescorla
- Re: [Ppm] [CFRG] Next steps for heavy hitters wit… Christopher Patton
- Re: [Ppm] [CFRG] Next steps for heavy hitters wit… Christopher Patton