The PREAMBLE VDAF

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶

This Internet-Draft will expire on 3 May 2027.¶

Copyright Notice

Copyright (c) 2026 IETF Trust and the persons identified as the document authors. All rights reserved.¶

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.¶

Table of Contents

1. Introduction

(RFC EDITOR: Remove this paragraph.) The source for this draft and the reference code can be found at https://github.com/markblunk/draft-apple-cfrg-vdaf-preamble.¶

Prio3 [VDAF] is a widely deployed protocol used in the aggregation of federated statistics: each client secret-shares a measurement (such as a binary value or a vector of integers) among a set of Aggregators, who jointly verify that it is well-formed before contributing its shares to an aggregate. PINE [PINE] adapts this same approach to federated machine learning, where each client's measurement is instead a gradient, and the Aggregators additionally verify that its L2 norm is bounded, so that no one client's update can disproportionately affect the trained model. In both constructions, the cost of sharding, verifying, and aggregating a measurement scales linearly with its dimension and can become impractical for vectors of large dimension, for example, in the millions.¶

Verifiable Distributed Point Functions (VDPF), as defined in [DP22] address this issue for a different class of high-dimensional problems. Poplar1 (Section 8 of [VDAF]) and Mastic [Mastic] use a similar functionality to let a client secret-share a single point in a large domain (such as the location of a heavy hitter input for Poplar1, or an input together with an associated weight for Mastic), so that the verification and aggregation cost is governed by the depth of the distributed point function's evaluation tree rather than by the size of the domain itself.¶

This document describes PREAMBLE, a two-party Verifiable Distributed Aggregation Function (VDAF) that combines both ideas, following [PREAMBLE], to aggregate block-sparse vectors. Under this approach, a client's measurement, a vector of large dimension, is divided into fixed-size blocks, at most one of which may be nonzero. PREAMBLE secret-shares this measurement without revealing which block is nonzero or what it contains. It also provides a proof to verify that 1) at most one block is nonzero; and 2) the contents of that block satify a property that can be checked by an associated Fully Linear Proof (FLP) supplied as a parameter (see Section 7 of [VDAF]). Section Section 5 specifies this generic composition of VDPF and FLP, and Section 5.9 instantiates it with concrete FLPs. PREAMBLE's communication cost scales with the block size and the depth of the VDPF's tree (logarithmic in the number of blocks) rather than with the dimension of the vector itself. The server-side cost of verification and aggregation still scales linearly with the dimension.¶

For example, consider a service that reports what kinds of photos people take at popular locations. The map is divided into a grid of about a million (2^20) tiles, and each tile is assigned a block of 100 counters, one per photo category such as sky, person, or recreation, for a total dimension of roughly 100 million. Because the photos a client contributes in one collection period tend to be taken in one geographic tile, its measurement touches a small number of indices that could be contained in a small block: the block index identifies the tile, and the block content records which categories appear there, which a multihot FLP can limit to a small number. With PREAMBLE, the client's upload is dominated by the 100-entry block and grows only logarithmically with the number of blocks (the 20 levels of the VDPF tree). The Aggregators' verification work, by contrast, still grows linearly with the dimension: they must evaluate the VDPF down to every leaf and expand the secret shares of every coordinate there, before summing the blocks elementwise and running the FLP on the sum.¶

Another example comes from distributed model training, where each client contributes a locally computed gradient. For models with millions or hundreds of millions of parameters, the communication cost of sending a dense gradient is prohibitive. Recent work shows while model training is global over all parameter each individual client need only share the training result on a subset of the parameters. PREAMBLE suits this setting, especially when a regularity condition, such as a bounded Euclidean (L2) norm, is also enforced on the nonzero block.¶

2. Conventions and Definitions

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶

• Clients, Aggregators, and Collectors from Section 3 of [VDAF].¶

• Auxiliary functions from Section 2 of [VDAF].¶