Crypto Forum                                                    H. Davis
Internet-Draft                                                   Seagate
Intended status: Informational                                 D. Mouris
Expires: 28 July 2025                                            Nillion
                                                               C. Patton
                                                              Cloudflare
                                                          N. G. Tsoutsos
                                                  University of Delaware
                                                         24 January 2025


                            The Mastic VDAF
                      draft-mouris-cfrg-mastic-04

Abstract

   This document describes Mastic, a two-party VDAF for the following
   secure aggregation task: each client holds an input string and an
   associated weight, and the data collector wants to aggregate the
   weights of all clients whose inputs begin with a prefix chosen by the
   data collector.  This functionality enables two classes of
   applications.  First, it allows grouping metrics by client attributes
   without revealing which clients have which attributes.  Second, it
   solves the weighted heavy hitters problem, where the goal is to
   compute the subset of inputs that have the highest total weight.

About This Document

   This note is to be removed before publishing as an RFC.

   Status information for this document may be found at
   https://datatracker.ietf.org/doc/draft-mouris-cfrg-mastic/.

   Discussion of this document takes place on the Crypto Forum Research
   Group mailing list (mailto:cfrg@ietf.org), which is archived at
   https://mailarchive.ietf.org/arch/search/?email_list=cfrg.  Subscribe
   at https://www.ietf.org/mailman/listinfo/cfrg/.

   Source for this draft and an issue tracker can be found at
   https://github.com/jimouris/draft-mouris-cfrg-mastic.

Status of This Memo

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






Davis, et al.             Expires 28 July 2025                  [Page 1]

Internet-Draft                   Mastic                     January 2025


   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 28 July 2025.

Copyright Notice

   Copyright (c) 2025 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  . . . . . . . . . . . . . . . . . . . . . . . .   3
   2.  Conventions and Definitions . . . . . . . . . . . . . . . . .   5
   3.  Specification of VIDPF  . . . . . . . . . . . . . . . . . . .   8
     3.1.  Key Generation  . . . . . . . . . . . . . . . . . . . . .  10
     3.2.  Key Evaluation  . . . . . . . . . . . . . . . . . . . . .  13
     3.3.  Auxiliary functions . . . . . . . . . . . . . . . . . . .  16
   4.  Specification of Mastic . . . . . . . . . . . . . . . . . . .  17
     4.1.  Sharding  . . . . . . . . . . . . . . . . . . . . . . . .  18
     4.2.  Preparation . . . . . . . . . . . . . . . . . . . . . . .  22
     4.3.  Validity of Aggregation Parameters  . . . . . . . . . . .  28
     4.4.  Aggregation . . . . . . . . . . . . . . . . . . . . . . .  29
     4.5.  Unsharding  . . . . . . . . . . . . . . . . . . . . . . .  29
     4.6.  Auxiliary Functions . . . . . . . . . . . . . . . . . . .  30
   5.  Security Considerations . . . . . . . . . . . . . . . . . . .  32
   6.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  32
   7.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  33
     7.1.  Normative References  . . . . . . . . . . . . . . . . . .  33
     7.2.  Informative References  . . . . . . . . . . . . . . . . .  33
   Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . .  34
   Motivating Applications . . . . . . . . . . . . . . . . . . . . .  34
     Network Error Logging . . . . . . . . . . . . . . . . . . . . .  34
     Attribute-Based Browser Telemetry . . . . . . . . . . . . . . .  36
   Modes of Operation  . . . . . . . . . . . . . . . . . . . . . . .  37



Davis, et al.             Expires 28 July 2025                  [Page 2]

Internet-Draft                   Mastic                     January 2025


     Weighted Heavy-Hitters  . . . . . . . . . . . . . . . . . . . .  37
       Different Thresholds  . . . . . . . . . . . . . . . . . . . .  38
     Attribute-based Metrics . . . . . . . . . . . . . . . . . . . .  38
     Plain Heavy-Hitters with VIDPF-Proof Aggregation  . . . . . . .  39
     Robustness Against a Malicious Aggregator . . . . . . . . . . .  41
   Test Vectors  . . . . . . . . . . . . . . . . . . . . . . . . . .  42
   Contributors  . . . . . . . . . . . . . . . . . . . . . . . . . .  42
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  42

1.  Introduction

   (RFC EDITOR: Remove this paragraph.)  The source for this draft and
   the reference code can be found at https://github.com/jimouris/draft-
   mouris-cfrg-mastic.

   The private "heavy hitters" problem is to compute the most popular
   input strings generated by clients without learning the inputs
   themselves.  For example, a browser vendor might want to know which
   websites are visited most frequently without learning which clients
   visited which websites.

   This problem can be solved by combining a binary search with a
   subroutine solving the simpler "prefix histogram" problem.  The goal
   of this problem is to count how many of the input strings begin with
   each of a sequence of candidate prefixes.  This problem can be solved
   using a Verifiable Distributed Aggregation Function, or VDAF [VDAF].

   The Poplar1 VDAF specified in Section 8 of [VDAF] describes how to
   distribute this computation amongst two aggregation servers such
   that, as long as one server is honest, no individual's input is
   observed in the clear.  At the same time, Poplar1 allows the servers
   to detect and remove any invalid measurements that would otherwise
   corrupt the computation.

   This document describes Mastic [MPDST25], a VDAF for the following,
   more general functionality: each client holds an input and an
   associated weight, and the data collector's goal is, for each
   candidate prefix, to aggregate the weights of all clients whose
   inputs have the prefix in common.  This functionality gives rise to
   two types of applications:

   1.  "weighted heavy hitters": Rather than compute the most frequent
       inputs, as in plain heavy hitters, the goal here is to compute
       the set of inputs with the highest total weight.  For example, a
       browser vendor might want to know which web pages have the
       highest average load time, perhaps indicating a performance issue
       in the browser.  Because weighted heavy hitters is more general,
       Mastic can be used as a drop-in replacement for Poplar1.  It is



Davis, et al.             Expires 28 July 2025                  [Page 3]

Internet-Draft                   Mastic                     January 2025


       is also more efficient, requiring just one round of communication
       for preparation (Section 5.2 of [VDAF]) compared to Poplar1's two
       rounds.

   2.  "attribute-based metrics": The Prio3 VDAF (Section 7 of [VDAF])
       can be used for a variety of aggregation tasks, ranging from
       simple summary statistics, like average or standard deviation, to
       more sophisticated representations of data, like histograms or
       linear regression.  In many situations, it is desirable to group
       such metrics by client attributes such as geolocation or user
       agent (Section 10.1.5 of [RFC9110]).  Mastic provides this
       functionality without revealing any client's attribute to the
       aggregation servers or data collector.

   The main component of Mastic is the Verifiable Incremental
   Distributed Point Function (VIDPF) of [MST24].  VIDPF extends IDPF
   (Section 8.3 of [VDAF]), the main building block of Poplar1.  Both
   IDPF and VIDPF are a form of function secret sharing [BGI15], where a
   client generates shares of a secret function F such that each server
   can compute shares of F(X) for a chosen X.  In our case, the function
   being shared is associated with a secret input string alpha and
   weight beta for which F(X) = beta for every prefix X of alpha and
   F(X) = 0 for every X this is not a prefix of alpha.  The scheme is
   verifiable in the sense that, for any two candidate prefixes of the
   same length, the servers can verify that at most one of them
   evaluates to beta and the other(s) evaluate(s) to 0.

   Mastic combines VIDPF with a method for checking that beta itself is
   a valid weight.  For example, if the weights represent page load
   times, it is important to make sure each weight is within a sensible
   range, say within seconds rather than hours or days.  Otherwise,
   misbehaving clients would be able to poison the computation by
   reporting out of range values.

   This range check is accomplished with the Fully Linear Proof (FLP)
   system of Section 7.3 of [VDAF].  An FLP allows properties of secret
   shared data to be validated without revealing the data itself.  In
   Mastic, the client generates an FLP of its beta's validity; when the
   servers are ready to evaluate the VIDPF, they first compute shares of
   beta and verify the FLP, which itself is secret shared.  Then the
   VIDPF ensures that the non-0 output of the point function is the same
   for each evaluation.

   This document specifies VIDPF in Section 3 and the composition of
   VIDPF and FLP into Mastic in Section 3.  The appendix includes
   supplementary material:





Davis, et al.             Expires 28 July 2025                  [Page 4]

Internet-Draft                   Mastic                     January 2025


   *  Appendix "Motivating Applications" discusses some use cases that
      motivated Mastic's functionality.

   *  Appendix "Modes of Operation" describes extensions and
      optimizations for Mastic, including a batched "preparation"
      (Section 5.2 of [VDAF]) mode of operation that reduces
      communication cost, and a 3-party variant of the protocol that
      ensures robustness against poisoning attacks in the presence of
      one malicious aggregation server.

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.

   This document uses the same conventions and definitions as Section 2
   of [VDAF].  The following terms as defined in therein: "Aggregator",
   "Client", "Collector", "aggregate result", "aggregate share",
   "aggregation parameter", "batch", "input share", "measurement",
   "output share", "prep message", "prep share", and "report".

   The following functions are as defined therein:

                 +===============+==========+============+
                 | Functionality | Type     | Definition |
                 +===============+==========+============+
                 | byte          | Function | Section 2  |
                 +---------------+----------+------------+
                 | cast          | Function | Section 2  |
                 +---------------+----------+------------+
                 | concat        | Function | Section 2  |
                 +---------------+----------+------------+
                 | front         | Function | Section 2  |
                 +---------------+----------+------------+
                 | range         | Function | Section 2  |
                 +---------------+----------+------------+
                 | to_le_bytes   | Function | Section 2  |
                 +---------------+----------+------------+
                 | xor           | Function | Section 2  |
                 +---------------+----------+------------+

                      Table 1: Common Functionalities.






Davis, et al.             Expires 28 July 2025                  [Page 5]

Internet-Draft                   Mastic                     January 2025


   Mastic also uses finite fields as specified in Section 6.1 of [VDAF].
   We usually denote a finite field by F and its Python class object, a
   subclass of Field, as field: type[F].  This document references the
   following operations on fields, defined in Section 6.1 of [VDAF]:

          +==================+=================+===============+
          | Functionality    | Type            | Definition    |
          +==================+=================+===============+
          | Field            | Constructor     | Section 6.1   |
          +------------------+-----------------+---------------+
          | field.encode_vec | Instance Method | Section 6.1.1 |
          +------------------+-----------------+---------------+
          | field.zeros      | Instance Method | Section 6.1   |
          +------------------+-----------------+---------------+
          | vec_add          | Function        | Section 6.1.1 |
          +------------------+-----------------+---------------+
          | vec_neg          | Function        | Section 6.1.1 |
          +------------------+-----------------+---------------+
          | vec_sub          | Function        | Section 6.1.1 |
          +------------------+-----------------+---------------+

                  Table 2: Finite Field Functionalities.

   Mastic uses the Fully Linear Proof (FLP) system specified in
   Section 7.3 of [VDAF].  The draft refers to the following methods on
   an instance flp of the class Flp defined in [VDAF]:

            +===============+=================+===============+
            | Functionality | Type --         | Definition    |
            +===============+=================+===============+
            | flp.decide    | Instance Method | Section 7.1   |
            +---------------+-----------------+---------------+
            | flp.decode    | Instance Method | Section 7.1.1 |
            +---------------+-----------------+---------------+
            | flp.encode    | Instance Method | Section 7.1.1 |
            +---------------+-----------------+---------------+
            | flp.prove     | Instance Method | Section 7.1   |
            +---------------+-----------------+---------------+
            | flp.query     | Instance Method | Section 7.1   |
            +---------------+-----------------+---------------+
            | flp.truncate  | Instance Method | Section 7.1.1 |
            +---------------+-----------------+---------------+
            | MEAS_LEN      | integer         | Section 7.3.2 |
            +---------------+-----------------+---------------+
            | OUTPUT_LEN    | integer         | Section 7.3.2 |
            +---------------+-----------------+---------------+

                    Table 3: FLP methods and parameters.



Davis, et al.             Expires 28 July 2025                  [Page 6]

Internet-Draft                   Mastic                     January 2025


   Mastic also uses eXtendable Output Functions (XOFs) as specified in
   Section 6.2 of [VDAF].  The following functionalities are as defined
   therein (xof denotes an instance of class Xof):

           +===================+=================+=============+
           | Functionality     | Type            | Definition  |
           +===================+=================+=============+
           | XofFixedKeyAes128 | Constructor     | Section 6.2 |
           +-------------------+-----------------+-------------+
           | XofTurboShake128  | Constructor     | Section 6.2 |
           +-------------------+-----------------+-------------+
           | xof.next          | Instance Method | Section 6.2 |
           +-------------------+-----------------+-------------+

                       Table 4: XOF Functionalities.

   Each invocation of a XOF is initialized with a domain separation tag.
   Each domain separation tag encodes the version of this document, the
   application context string (Section 4.1 of [VDAF]), and a
   distinguished byte identifying how the XOF output is used.  The tag
   may also encode a VDAF algorithm ID (Section 5 of [VDAF]).

   The version of this document is a byte denoted VERSION.  Its value
   SHALL be 0.

      NOTE We'll bump VERSION whenever we publish a draft with
      incompatible changes from the previous draft.

   Algorithms in the remainder will use the following algorithms:

   def dst(ctx: bytes, usage: int) -> bytes:
       return b'mastic' + byte(VERSION) + byte(usage) + ctx

   def dst_alg(ctx: bytes, usage: int, algorithm_id: int) -> bytes:
       return b'mastic'\
           + byte(VERSION) \
           + byte(usage) \
           + to_be_bytes(algorithm_id, 4) \
           + ctx

   When using Mastic or VIDPF, the length of the application context
   string (denoted ctx) MUST be in range [0, 2^16 - 12).

      NOTE This range was computed by taking the maximum size of the
      domain separation tag supported by both XofFixedKeyAes128 and
      XofTurboShake128 and subtracting the length of the prefix.





Davis, et al.             Expires 28 July 2025                  [Page 7]

Internet-Draft                   Mastic                     January 2025


   Finally, for completeness, we define some Python methods used in the
   remainder:

   *  bool(val: Any) -> bool converts a value val to a Boolean.

   *  bytearray(source: Union[str, bytes, bytearray, Iterable[int]]) ->
      bytearray returns a mutable sequence of bytes.

   *  bytes(source: Union[str, bytes, bytearray, Iterable[int]]) ->
      bytes returns a immutable sequence of bytes.

   *  len(obj: Sized) -> int returns the number of items in obj.  The
      object argument can be a sequence (e.g., string, list, or tuple)
      or a collection (e.g., dictionary, set).

   *  list.append(elem: Any) -> None adds a single element elem to the
      end of a list instance.

   *  list.copy() -> list returns a shallow copy of a list instance.

   *  set(iterable: Optional[Iterable] = None) -> set creates a new set
      object, which is an unordered collection of unique elements.  The
      optional iterable argument (e.g., list, tuple, or string) is used
      to initialize the set.  If no argument is provided, an empty set
      is created.

3.  Specification of VIDPF

   +=============+======================+=============================+
   | Parameter   | Description          | Value                       |
   +=============+======================+=============================+
   | KEY_SIZE:   | the size of each     | XofFixedKeyAes128.SEED_SIZE |
   | int         | VIDPF key            | (Section 6.2.2 of [VDAF])   |
   +-------------+----------------------+-----------------------------+
   | NONCE_SIZE: | the size of the      | KEY_SIZE                    |
   | int         | VIDPF nonce          |                             |
   +-------------+----------------------+-----------------------------+
   | RAND_SIZE:  | the number of random | 2 * KEY_SIZE                |
   | int         | bytes consumed by    |                             |
   |             | gen()                |                             |
   +-------------+----------------------+-----------------------------+
   | BITS: int   | bit length of the    | set by constructor          |
   |             | input string alpha   |                             |
   +-------------+----------------------+-----------------------------+
   | VALUE_LEN:  | length of beta       | set by constructor          |
   | int         |                      |                             |
   +-------------+----------------------+-----------------------------+
   | field:      | class object for the | set by constructor          |



Davis, et al.             Expires 28 July 2025                  [Page 8]

Internet-Draft                   Mastic                     January 2025


   | type[F]     | field (Section 6.1   |                             |
   |             | of [VDAF])           |                             |
   +-------------+----------------------+-----------------------------+

                        Table 5: VIDPF parameters.

      NOTE This specification is based on [MST24], which in turn draws
      on ideas from [CP22].  We don't yet have a concrete security
      analysis of the complete construction.  Some details are likely to
      change as a result of such analysis.

   This section specifies the Verifiable Incremental Distributed Point
   Function (VIDPF) of [MST24].  Its parameters are summarized in
   Table 5.

   VIDPF is a function secret sharing scheme [BGI15] for functions F for
   which:

   *  F(X) =betaifXis a prefix ofalpha`

   *  F(X) = field.zeros(VALUE_LEN) if x is not a prefix of alpha

   where alpha and beta are the input and encoded weight of a Client and
   field the finite field.  The scheme is designed to allow each
   Aggregator to compute a share of F(X) for any candidate prefix X
   without revealing any information about alpha or beta.  Furthermore,
   the output shares can be aggregated locally, allowing each Aggregator
   to compute a share of the total weight for all inputs that have X as
   a prefix.

   VIDPF comprises two algorithms.

   The key generation algorithm defined in Section 3.1 takes in a
   (alpha, beta) and the report nonce and outputs secret shares of F.
   The shares take the form of a pair of "keys", one for each
   Aggregator, and a sequence of "correction words" sent to both
   Aggregators.  We define correction words in the next section.

   The Aggregators evaluate a Client's VIDPF on a sequence of candidate
   prefixes.  Imagine arranging these prefixes in a binary tree where
   each path from the root corresponds to a prefix X and each node
   corresponds to a payload F(X).  We refer to this as the "prefix
   tree".

   The key evaluation algorithm defined in Section 3.2 takes in the
   correction words, the Aggregator's key, the sequence of candidate
   prefixes, and the nonce associated with the Client's report.  It the
   Aggregator's share of the prefix tree.



Davis, et al.             Expires 28 July 2025                  [Page 9]

Internet-Draft                   Mastic                     January 2025


      TODO Define the "node proofs".

3.1.  Key Generation

   The VIDPF-key generation algorithm run by each Client is listed
   below.  The specification invokes auxiliary functions, namely
   extend(), convert(), and node_proof(), which are defined in
   Section 3.3.  Its inputs are the input string alpha, the encoded
   weight beta, the application context string ctx (Section 4.1 of
   [VDAF]), a public nonce of length NONCE_SIZE, and the randomness
   consumed by the algorithm of length RAND_SIZE.  Its outputs are the
   public sequence of "correction words", one for each level of the
   tree, and the secret keys, one for each Aggregator.

      TODO Give a high level overview of how IDPF works, in particular
      the seed/control-bit invariant for each level.  Define
      CorrectionWord and explain the role of correction words and define
      node proofs, which are unique to VIDPF.

      TODO Specify bounds on the inputs, namely that the nonce has to be
      random.  (This is inherited from IDPF security considerations.)

      TODO Explain functional differences between VIDPF and IDPF in
      Section 8 of [VDAF].  Namely, there is no distinction between
      inner and leaf nodes and the payload is supposed to be the same at
      each level.

   def gen(self,
           alpha: tuple[bool, ...],
           beta: list[F],
           ctx: bytes,
           nonce: bytes,
           rand: bytes,
           ) -> tuple[list[CorrectionWord], list[bytes]]:
       '''
       The VIDPF key generation algorithm.

       Returns the public share (i.e., the correction word for each
       level of the tree) and two keys, one for each aggregator.

       Implementation note: for clarity, this algorithm has not been
       written in a manner that is side-channel resistant. To avoid
       leaking `alpha` via a side-channel, implementations should avoid
       branching or indexing into arrays in a data-dependent manner.
       '''
       if len(alpha) != self.BITS:
           raise ValueError("alpha out of range")
       if len(beta) != self.VALUE_LEN:



Davis, et al.             Expires 28 July 2025                 [Page 10]

Internet-Draft                   Mastic                     January 2025


           raise ValueError("incorrect beta length")
       if len(nonce) != self.NONCE_SIZE:
           raise ValueError("incorrect nonce size")
       if len(rand) != self.RAND_SIZE:
           raise ValueError("randomness has incorrect length")

       keys = [rand[:self.KEY_SIZE], rand[self.KEY_SIZE:]]

       # [MST24, Fig. 15]: s0^0, s1^0, t0^0, t1^0
       seed = keys.copy()
       ctrl = [False, True]
       correction_words = []
       for i in range(self.BITS):
           idx = PrefixTreeIndex(alpha[:i+1])
           bit = alpha[i]

           # [MST24]: if x = 0 then keep <- L, lose <- R
           #
           # Implementation note: the value of `bit` is
           # `alpha`-dependent.
           (keep, lose) = (1, 0) if bit else (0, 1)

           # Extend: compute the left and right children the current
           # level of the tree. During evaluation, one of these children
           # will be selected as the next seed and control bit.
           #
           # [MST24]: s_0^L || s_0^R || t_0^L || t_0^R
           #          s_1^L || s_1^R || t_1^L || t_1^R
           (s0, t0) = self.extend(seed[0], ctx, nonce)
           (s1, t1) = self.extend(seed[1], ctx, nonce)

           # Compute the correction words for this level's seed and
           # control bit. Our goal is to maintain the following
           # invariant, after correction:
           #
           # * If evaluation is on path, then each aggregator will
           #   compute a different seed and their control bits will be
           #   secret shares of one.
           #
           # * If evaluation is off path, then the aggregators will
           #   compute the same seed and their control bits will be
           #   shares of zero.
           #
           # Implementation note: the index `lose` is `alpha`-dependent.
           seed_cw = xor(s0[lose], s1[lose])
           ctrl_cw = [
               t0[0] ^ t1[0] ^ (not bit),  # [MST24]: t_c^L
               t0[1] ^ t1[1] ^ bit,        # [MST24]: t_c^R



Davis, et al.             Expires 28 July 2025                 [Page 11]

Internet-Draft                   Mastic                     January 2025


           ]

           # Correct.
           #
           # Implementation note: the index `keep` is `alpha`-dependent,
           # as is `ctrl`.
           if ctrl[0]:
               s0[keep] = xor(s0[keep], seed_cw)
               t0[keep] ^= ctrl_cw[keep]
           if ctrl[1]:
               s1[keep] = xor(s1[keep], seed_cw)
               t1[keep] ^= ctrl_cw[keep]

           # Convert.
           (seed[0], w0) = self.convert(s0[keep], ctx, nonce)
           (seed[1], w1) = self.convert(s1[keep], ctx, nonce)
           ctrl[0] = t0[keep]  # [MST24]: t0'
           ctrl[1] = t1[keep]  # [MST24]: t1'

           # Compute the correction word for this level's payload.
           #
           # Implementation note: `ctrl` is `alpha`-dependent.
           w_cw = vec_add(vec_sub(beta, w0), w1)
           if ctrl[1]:
               w_cw = vec_neg(w_cw)

           # Compute the correction word for this level's node proof. If
           # evaluation is on path, then exactly one of the aggregatos
           # will correct their node proof, causing them to compute the
           # same node value. If evaluation is off path, then both will
           # correct or neither will; and since they compute the same
           # seed, they will again compute the same value.
           proof_cw = xor(
               self.node_proof(seed[0], ctx, idx),
               self.node_proof(seed[1], ctx, idx),
           )

           correction_words.append((seed_cw, ctrl_cw, w_cw, proof_cw))

       return (correction_words, keys)











Davis, et al.             Expires 28 July 2025                 [Page 12]

Internet-Draft                   Mastic                     January 2025


3.2.  Key Evaluation

   The VIDPF-key evaluation algorithm is listed below.  See Section 3.3
   for deferred auxiliary functions.  Its inputs are the Aggregator's ID
   (either 0 or 1), the correction words, the Aggregator's key, the
   level of the tree, the sequence of prefixes, and the nonce associated
   with the report.  Its outputs are the sequence of output shares for
   each prefix, and the evaluation proof.

      TODO Define PrefixTreeIndex and PrefixTreeEntry.

      TODO Say why we also visit the siblings of nodes in the prefix
      tree (it's needed for Mastic).






































Davis, et al.             Expires 28 July 2025                 [Page 13]

Internet-Draft                   Mastic                     January 2025


   def eval_next(self,
                   node: PrefixTreeEntry,
                   correction_word: CorrectionWord,
                   ctx: bytes,
                   nonce: bytes,
                   idx: PrefixTreeIndex,
                   ) -> PrefixTreeEntry:
       """
       Extend a node in the tree, select and correct one of its
       children, then convert it into a payload and the next seed.
       """
       (seed_cw, ctrl_cw, w_cw, proof_cw) = correction_word
       keep = int(idx.path[-1])

       # Extend.
       #
       # [MST24, Fig. 17]: (s^L, s^R), (t^L, t^R) = PRG(s^{i-1})
       (s, t) = self.extend(node.seed, ctx, nonce)

       # Correct.
       #
       # Implementation note: avoid branching on the value of control
       # bits, as its value may be leaked by a side channel.
       if node.ctrl:
           s[keep] = xor(s[keep], seed_cw)
           t[keep] ^= ctrl_cw[keep]

       # Convert and correct the payload.
       #
       # Implementation note: the conditional addition should be
       # replaced with a constant-time select in practice in order to
       # reduce leakage via timing side channels.
       (next_seed, w) = self.convert(s[keep], ctx, nonce)
       next_ctrl = t[keep]  # [MST24]: s^i, W^i, t'^i
       if next_ctrl:
           w = vec_add(w, w_cw)

       # Compute and correct the node proof.
       #
       # Implementation note: avoid branching on the control bit here.
       node_proof = self.node_proof(next_seed, ctx, idx)
       if next_ctrl:
           node_proof = xor(node_proof, proof_cw)

       return PrefixTreeEntry(next_seed, next_ctrl, w, node_proof)

   Evaluating the prefix tree, plus the sibling of each n ode in the
   prefix tree:



Davis, et al.             Expires 28 July 2025                 [Page 14]

Internet-Draft                   Mastic                     January 2025


   def eval_with_siblings(self,
                           agg_id: int,
                           correction_words: list[CorrectionWord],
                           key: bytes,
                           level: int,
                           prefixes: tuple[tuple[bool, ...], ...],
                           ctx: bytes,
                           nonce: bytes,
                           ) -> tuple[list[list[F]], PrefixTreeEntry]:
       """
       The VIDPF key evaluation algorithm.

       The return value consists of the weights for each candidate prefix and
       the root of the prefix tree. The prefix tree includes the prefixes and
       the siblings of each node visited.
       """
       if agg_id not in range(2):
           raise ValueError("invalid aggregator ID")
       if len(correction_words) != self.BITS:
           raise ValueError("corrections words has incorrect length")
       if level not in range(self.BITS):
           raise ValueError("level too deep")
       for prefix in prefixes:
           if len(prefix) != level + 1:
               raise ValueError("prefix with incorrect length")
       if len(set(prefixes)) != len(prefixes):
           raise ValueError("candidate prefixes are non-unique")

       # Evaluate our share of the prefix tree, including the sibling of each
       # node we visit.
       #
       # Implementation note: we can save computation by storing the tree
       # across `eval()` calls for the same report.
       root = PrefixTreeEntry.root(key, bool(agg_id))
       out_share = []
       for prefix in prefixes:
           n = root
           for (i, bit) in enumerate(prefix):
               idx = PrefixTreeIndex(prefix[:i+1])
               if n.left_child is None:
                   n.left_child = self.eval_next(n, correction_words[i], ctx,
                                                   nonce, idx.left_sibling())
               if n.right_child is None:
                   n.right_child = self.eval_next(n, correction_words[i], ctx,
                                                   nonce, idx.right_sibling())
               n = n.right_child if bit else n.left_child
           out_share.append(n.w if agg_id == 0 else vec_neg(n.w))




Davis, et al.             Expires 28 July 2025                 [Page 15]

Internet-Draft                   Mastic                     January 2025


       return (out_share, root)

   Obtaining our share of beta, the payload programmed into the prefix
   tree:

   def get_beta_share(
           self,
           agg_id: int,
           correction_words: list[CorrectionWord],
           key: bytes,
           ctx: bytes,
           nonce: bytes,
   ) -> list[F]:
       root = PrefixTreeEntry.root(key, bool(agg_id))
       left = self.eval_next(root, correction_words[0], ctx, nonce,
                             PrefixTreeIndex((False,)))
       right = self.eval_next(root, correction_words[0], ctx, nonce,
                              PrefixTreeIndex((True,)))
       beta_share = vec_add(left.w, right.w)
       if agg_id == 1:
           beta_share = vec_neg(beta_share)
       return beta_share

3.3.  Auxiliary functions

   def extend(self,
               seed: bytes,
               ctx: bytes,
               nonce: bytes,
               ) -> tuple[list[bytes], Ctrl]:
       '''
       Extend a seed into the seed and control bits for its left and
       right children in the VIDPF tree.
       '''
       xof = XofFixedKeyAes128(seed, dst(ctx, USAGE_EXTEND), nonce)
       s = [
           bytearray(xof.next(self.KEY_SIZE)),
           bytearray(xof.next(self.KEY_SIZE)),
       ]
       # Use the least significant bits as the control bit correction,
       # and then zero it out. This gives effectively 127 bits of
       # security, but reduces the number of AES calls needed by 1/3.
       t = [bool(s[0][0] & 1), bool(s[1][0] & 1)]
       s[0][0] &= 0xFE
       s[1][0] &= 0xFE
       return ([bytes(s[0]), bytes(s[1])], t)

   def convert(self,



Davis, et al.             Expires 28 July 2025                 [Page 16]

Internet-Draft                   Mastic                     January 2025


               seed: bytes,
               ctx: bytes,
               nonce: bytes,
               ) -> tuple[bytes, list[F]]:
       '''
       Convert a selected seed into a payload and the seed for the next
       level.
       '''
       xof = XofFixedKeyAes128(seed, dst(ctx, USAGE_CONVERT), nonce)
       next_seed = xof.next(XofFixedKeyAes128.SEED_SIZE)
       payload = xof.next_vec(self.field, self.VALUE_LEN)
       return (next_seed, payload)

   def node_proof(self,
                   seed: bytes,
                   ctx: bytes,
                   idx: PrefixTreeIndex) -> bytes:
       '''
       Compute the proof for this node.
       '''
       binder = \
           to_le_bytes(self.BITS, 2) + \
           to_le_bytes(idx.level(), 2) + \
           idx.encode()
       xof = XofTurboShake128(seed,
                               dst(ctx, USAGE_NODE_PROOF),
                               binder)
       return xof.next(PROOF_SIZE)

4.  Specification of Mastic

   An instance of Mastic is determined by a desired bit-length of the
   input, denoted BITS, and a validity circuit, an instance of Valid as
   defined in Section 7.3.2 of [VDAF].  The validity circuit is used to
   instantiate the FLP and defines the type of the weights generated by
   Clients and the type of the total weight for each prefix computed by
   the Collector.

   The Client's measurement has two components: the input string alpha:
   tuple[bool, ...] of length BITS and its weight.  The weight's type is
   denoted by W.  We use beta: list[F] to denote the encoded weight,
   obtained by invoking the FLP's encoder (Section 7.1.1 of [VDAF]).

   The aggregate result has type list[R], where R is likewise a type
   defined by the validity circuit.  Each element of this list
   corresponds to the total weight for one of the candidate prefixes.





Davis, et al.             Expires 28 July 2025                 [Page 17]

Internet-Draft                   Mastic                     January 2025


   The VIDPF is instantiated with bit length BITS, value length
   valid.MEAS_LEN, and field valid.field, where valid is the validity
   circuit.  We denote this instance of the VIDPF by vidpf.

   In the remainder, we write xof as shorthand for XofTurboShake128
   (Section 6.2.1 of [VDAF]).

   Mastic's implementation of the VDAF interface (Section 5 of [VDAF])
   is specified in the following sections.  Section 4.6 defines some
   auxiliary functions referenced in the sharding and preparation
   sections.

4.1.  Sharding

   The sharding algorithm takes in the measurement (the input and
   weight), the nonce, and the sharding randomness.  The size of the
   nonce is 16 bytes; the size of the randomness is vidpf.RAND_SIZE + 2
   * xof.SEED_SIZE, plus an additional xof.SEED_SIZE if the validity
   circuit takes joint randomness as input.

   The public share is the sequence of correction words output by the
   VIPDF key generation algorithm.  The contents of each input share,
   denoted MasticInputShare, depends on the Aggregator who receives it.
   We refer to the first Aggregator as the "Leader"; we refer to the
   second Aggregator as the "Helper".  The components of the input share
   are:

   1.  The Aggregator's VIDPF key share.

   2.  An optional FLP proof share, a vector of field elements.  This is
       set for the Leader only.

   3.  An optional seed.  This is always set for the Helper, who uses it
       to derive its FLP proof share.  This is set for the Leader of the
       circuit uses joint randomness.

   4.  The peer's FLP joint randomness seed, used to derive joint
       randomness for the FLP's validity circuit.  This is set for both
       the Leader and Helper only if joint randomness is required (i.e.,
       flp.JOINT_RAND_LEN > 0).

   The behavior of the sharding algorithm depends on whether the circuit
   requires joint randomness:








Davis, et al.             Expires 28 July 2025                 [Page 18]

Internet-Draft                   Mastic                     January 2025


   def shard(self,
               ctx: bytes,
               measurement: tuple[tuple[bool, ...], W],
               nonce: bytes,
               rand: bytes,
               ) -> tuple[list[CorrectionWord], list[MasticInputShare]]:
       if self.flp.JOINT_RAND_LEN > 0:
           return self.shard_with_joint_rand(
               ctx, measurement, nonce, rand)
       return self.shard_without_joint_rand(
           ctx, measurement, nonce, rand)

   When no FLP joint randomness is required, sharding involves the
   following steps:

   1.  Encode the weight weight as beta = [field(1)] +
       flp.encode(weight).  The prefix [field(1)], is used to count how
       many reports share a prefix in common and is usesd during
       unsharding.  More details in Section 4.5.

   2.  Generate the VIDPF correction words and keys for input alpha and
       beta as the payload.

   3.  Generate the FLP proof of validity for flp.encode(weight).

   4.  Compute the Leader's share of the proof.

      NOTE Each correction word has length flp.MEAS_LEN.  We could save
      a little bit of communication by truncating the weights according
      to flp.truncate().  However, we still need to encode the full
      weight at least once, either separately or at the first level of
      the VIDPF tree.  See issue #98 for details.

   The complete algorithm is listed below:

















Davis, et al.             Expires 28 July 2025                 [Page 19]

Internet-Draft                   Mastic                     January 2025


   def shard_without_joint_rand(
           self,
           ctx: bytes,
           measurement: tuple[tuple[bool, ...], W],
           nonce: bytes,
           rand: bytes,
   ) -> tuple[list[CorrectionWord], list[MasticInputShare]]:
       (vidpf_rand, rand) = front(self.vidpf.RAND_SIZE, rand)
       (prove_rand_seed, rand) = front(self.xof.SEED_SIZE, rand)
       (helper_seed, rand) = front(self.xof.SEED_SIZE, rand)
       assert len(rand) == 0  # REMOVE ME

       # Encode the inputs to VIDPF key generation. The output, denoted
       # `beta`, is a counter concatenated with the encoded weight.
       (alpha, weight) = measurement
       beta = [self.field(1)] + self.flp.encode(weight)

       # Generate VIDPF keys.
       (correction_words, keys) = \
           self.vidpf.gen(alpha, beta, ctx, nonce, vidpf_rand)

       # Generate FLP and split it into shares.
       prove_rand = self.prove_rand(ctx, prove_rand_seed)
       proof = self.flp.prove(beta[1:], prove_rand, [])
       helper_proof_share = self.helper_proof_share(ctx, helper_seed)
       leader_proof_share = vec_sub(proof, helper_proof_share)

       input_shares: list[MasticInputShare] = [
           (keys[0], leader_proof_share, None, None),
           (keys[1], None, helper_seed, None),
       ]
       return (correction_words, input_shares)

   When FLP joint randomness is required, the Client must compute it
   from the shares of beta sent to each Aggregator:

   1.  Encode the weight weight as beta = [field(1)] +
       flp.encode(weight).

   2.  Generate the VIDPF correction words and keys for alpha and beta.

   3.  Compute each Aggregator's FLP joint randomness part by hashing
       its share of beta with its FLP seed, its VIDPF key, and the VIDPF
       correction words.

   4.  Compute the FLP joint randomness seed by hashing the joint
       randomness parts.




Davis, et al.             Expires 28 July 2025                 [Page 20]

Internet-Draft                   Mastic                     January 2025


   5.  Derive the FLP joint randomness from the joint randomness seed.

   6.  Generate the FLP proof of beta's validity using the derived joint
       randomness.

   7.  Compute the Leader's share of the proof.

   The joint randomness is also needed to verify the FLP and must
   therefore be recomputed during preparation (Section 4.2).  To
   accomplish this, the Client includes in each Aggregator's input share
   the joint randomness part of its peer.

   The complete algorithm is listed below:

   def shard_with_joint_rand(
           self,
           ctx: bytes,
           measurement: tuple[tuple[bool, ...], W],
           nonce: bytes,
           rand: bytes,
   ) -> tuple[list[CorrectionWord], list[MasticInputShare]]:
       (vidpf_rand, rand) = front(self.vidpf.RAND_SIZE, rand)
       (prove_rand_seed, rand) = front(self.xof.SEED_SIZE, rand)
       (helper_seed, rand) = front(self.xof.SEED_SIZE, rand)
       (leader_seed, rand) = front(self.xof.SEED_SIZE, rand)
       assert len(rand) == 0  # REMOVE ME

       # Encode the inputs to VIDPF key generation. The output, denoted
       # `beta`, is a counter concatenated with the encoded weight.
       (alpha, weight) = measurement
       beta = [self.field(1)] + self.flp.encode(weight)

       # Generate VIDPF keys.
       (correction_words, keys) = \
           self.vidpf.gen(alpha, beta, ctx, nonce, vidpf_rand)

       # Generate FLP joint randomness.
       leader_beta_share = self.vidpf.get_beta_share(0, correction_words,
                                                       keys[0], ctx, nonce)
       helper_beta_share = self.vidpf.get_beta_share(1, correction_words,
                                                       keys[1], ctx, nonce)
       joint_rand_parts = [
           self.joint_rand_part(ctx, leader_seed, leader_beta_share[1:],
                                   nonce),
           self.joint_rand_part(ctx, helper_seed, helper_beta_share[1:],
                                   nonce),
       ]
       joint_rand = self.joint_rand(



Davis, et al.             Expires 28 July 2025                 [Page 21]

Internet-Draft                   Mastic                     January 2025


           ctx, self.joint_rand_seed(ctx, joint_rand_parts))

       # Generate FLP and split it into shares.
       prove_rand = self.prove_rand(ctx, prove_rand_seed)
       proof = self.flp.prove(beta[1:], prove_rand, joint_rand)
       helper_proof_share = self.helper_proof_share(ctx, helper_seed)
       leader_proof_share = vec_sub(proof, helper_proof_share)

       leader_joint_rand_part: Optional[bytes] = joint_rand_parts[0]
       helper_joint_rand_part: Optional[bytes] = joint_rand_parts[1]
       input_shares = [
           (keys[0], leader_proof_share, leader_seed, helper_joint_rand_part),
           (keys[1], None, cast(Optional[bytes],
               helper_seed), leader_joint_rand_part),
       ]
       return (correction_words, input_shares)

4.2.  Preparation

   Each Aggregator initializes preparation with: the verification key
   shared by both Aggregators; its own ID, either 0 for the Leader and 1
   for the Helper; the aggregation parameter; the report's nonce; the
   public share sent to each Aggregator; and the Aggregator's own input
   share.

   The aggregation parameter has the following components:

   1.  the level of the VIDPF being evaluated

   2.  the sequence of VIDPF prefixes being evaluated

   3.  an indication of whether to verify the FLP

   The FLP is verified exactly once, the first time the report is
   aggregated.  See Section 4.3.

   The outputs of the initialization algorithm include the Aggregator's
   prep state, denoted MasticPrepState, and its outbound prep share,
   denoted MasticPrepShare.  The prep share includes the Aggregator's
   FLP verifier share, joint randomness part, and VIDPF proof.  These
   are combined into the prep message in the next step.

   Preparation initialization involves the following steps:

   1.  Evaluate the VIDPF share on the sequence of prefixes, obtaining
       our share of the prefix tree.





Davis, et al.             Expires 28 July 2025                 [Page 22]

Internet-Draft                   Mastic                     January 2025


   2.  If applicable, run the FLP query generation algorithm on our
       share of the encoded weight to obtain our FLP verifier share.  If
       joint randomness is required, then compute our joint randomness
       part and derive the joint randomness seed using our peer
       Aggregator's part provided by the Client.  Note that the Client
       may have provided the wrong part, so we need to check that the
       seed was computed correctly before completing preparation.

   3.  Truncate each payload share according to the FLP encoding scheme
       and flatten them into a single vector of field elements.  This
       constitutes Mastic's output share.

   Moreover, when the Aggregators evaluate a Client's VIDPF, they verify
   three properties of the prefix tree:

   1.  One-hotness: at every level of the tree, at most one node has a
       non-zero payload.

   2.  Payload consistency: each payload is equal to the sum of the
       payloads of its children.  If one-hotness holds, then this
       ensures the payload is equal to beta for each node along the
       alpha path.

   3.  Counter consistency: the counter of the non-zero payload is equal
       to field(1).

      TODO Define the "evaluation proof".

   The complete algorithm is listed below:

   def prep_init(
           self,
           verify_key: bytes,
           ctx: bytes,
           agg_id: int,
           agg_param: MasticAggParam,
           nonce: bytes,
           correction_words: list[CorrectionWord],
           input_share: MasticInputShare,
   ) -> tuple[MasticPrepState, MasticPrepShare]:
       (level, prefixes, do_weight_check) = agg_param
       (key, proof_share, seed, peer_joint_rand_part) = \
           self.expand_input_share(ctx, agg_id, input_share)

       # Evaluate the VIDPF.
       (out_share, root) = self.vidpf.eval_with_siblings(
           agg_id,
           correction_words,



Davis, et al.             Expires 28 July 2025                 [Page 23]

Internet-Draft                   Mastic                     January 2025


           key,
           level,
           prefixes,
           ctx,
           nonce,
       )

       # Query the FLP if applicable.
       joint_rand_part = None
       joint_rand_seed = None
       verifier_share = None
       if do_weight_check:
           beta_share = self.vidpf.get_beta_share(agg_id, correction_words,
                                                   key, ctx, nonce)
           query_rand = self.query_rand(verify_key, ctx, nonce, level)
           joint_rand = []
           if self.flp.JOINT_RAND_LEN > 0:
               assert seed is not None
               assert peer_joint_rand_part is not None
               joint_rand_part = self.joint_rand_part(ctx, seed,
                                                       beta_share[1:], nonce)
               if agg_id == 0:
                   joint_rand_parts = [joint_rand_part, peer_joint_rand_part]
               else:
                   joint_rand_parts = [peer_joint_rand_part, joint_rand_part]
               joint_rand_seed = self.joint_rand_seed(ctx, joint_rand_parts)
               joint_rand = self.joint_rand(ctx, joint_rand_seed)
           verifier_share = self.flp.query(
               beta_share[1:],
               proof_share,
               query_rand,
               joint_rand,
               2,
           )

       # Payload and onehot checks.
       payload_check_binder = b''
       onehot_check_binder = b''
       assert root.left_child is not None
       assert root.right_child is not None
       q = [root.left_child, root.right_child]
       while len(q) > 0:
           (n, q) = (q[0], q[1:])

           if n.left_child is not None and n.right_child is not None:
               # Update payload check. The weight of each node should equal
               # the sum of its children.
               payload_check_binder += self.field.encode_vec(



Davis, et al.             Expires 28 July 2025                 [Page 24]

Internet-Draft                   Mastic                     January 2025


                   vec_sub(n.w, vec_add(n.left_child.w, n.right_child.w)))
               q += [n.left_child, n.right_child]

           # Update the onehot check.
           onehot_check_binder += n.proof

       payload_check = self.xof(
           b'',
           dst_alg(ctx, USAGE_PAYLOAD_CHECK, self.ID),
           payload_check_binder,
       ).next(PROOF_SIZE)

       onehot_check = self.xof(
           b'',
           dst_alg(ctx, USAGE_ONEHOT_CHECK, self.ID),
           onehot_check_binder,
       ).next(PROOF_SIZE)

       # Counter check: the first element of beta should equal 1.
       #
       # Each aggregator holds an additive share of the counter, so
       # we have aggregator 1 negate its share and add 1 so that they
       # both compute the same value for `counter`.
       w0 = root.left_child.w
       w1 = root.right_child.w
       counter_check = self.field.encode_vec(
           [w0[0] + w1[0] + self.field(agg_id)])

       # Evaluation proof: if both aggregators compute the same
       # value, then they agree on the onehot proof, the counter, and
       # the payload.
       eval_proof = self.xof(
           verify_key,
           dst_alg(ctx, USAGE_EVAL_PROOF, self.ID),
           onehot_check + counter_check + payload_check,
       ).next(PROOF_SIZE)

       # Concatenate the output shares into one aggregatable output,
       # applying the FLP truncation algorithm on each FLP measurement
       # share.
       truncated_out_share = []
       for val_share in out_share:
           truncated_out_share += [val_share[0]] + \
               self.flp.truncate(val_share[1:])

       prep_state = (truncated_out_share, joint_rand_seed)
       prep_share = (eval_proof, verifier_share, joint_rand_part)
       return (prep_state, prep_share)



Davis, et al.             Expires 28 July 2025                 [Page 25]

Internet-Draft                   Mastic                     January 2025


   Next, the Aggregators' prep shares are combined into the prep
   message, denoted MasticPrepMessage:

   1.  Check that both Aggregators computed the same VIDPF proof.  If
       so, then it is presumed that the output share is one-hot, has
       path consistency, and has counter consistency as defined in
       Section 3.

   2.  If applicable, combine the FLP verifier shares into the FLP
       verifier and run the FLP decision algorithm.  If successful, then
       it is presumed that the weight is valid.

   3.  If applicable, compute the FLP joint randomness seed from the
       parts.

   The prep message consists of the optional joint randomness seed.  The
   complete algorithm is listed below:


































Davis, et al.             Expires 28 July 2025                 [Page 26]

Internet-Draft                   Mastic                     January 2025


   def prep_shares_to_prep(
           self,
           ctx: bytes,
           agg_param: MasticAggParam,
           prep_shares: list[MasticPrepShare],
   ) -> MasticPrepMessage:
       (_level, _prefixes, do_weight_check) = agg_param

       if len(prep_shares) != 2:
           raise ValueError('unexpected number of prep shares')

       (eval_proof_0,
        verifier_share_0,
        joint_rand_part_0) = prep_shares[0]
       (eval_proof_1,
        verifier_share_1,
        joint_rand_part_1) = prep_shares[1]

       # Verify the VIDPF output.
       if eval_proof_0 != eval_proof_1:
           raise Exception('VIDPF verification failed')

       if not do_weight_check:
           return None
       if verifier_share_0 is None or verifier_share_1 is None:
           raise ValueError('expected FLP verifier shares')

       # Verify the FLP.
       verifier = vec_add(verifier_share_0, verifier_share_1)
       if not self.flp.decide(verifier):
           raise Exception('FLP verification failed')

       if self.flp.JOINT_RAND_LEN == 0:
           return None
       if joint_rand_part_0 is None or joint_rand_part_1 is None:
           raise ValueError('expected FLP joint randomness parts')

       # Confirm the FLP joint randomness was computed properly.
       prep_msg = self.joint_rand_seed(ctx, [
           joint_rand_part_0,
           joint_rand_part_1,
       ])
       return prep_msg








Davis, et al.             Expires 28 July 2025                 [Page 27]

Internet-Draft                   Mastic                     January 2025


   Finally, each Aggregator completes preparation by checking that the
   true FLP joint randomness seed is equal to the value they computed in
   the initialization step, prep_init().  This is only done if a weight
   check was required by the aggregation parameter and joint randomness
   was required by the FLP:

   def prep_next(self,
                   _ctx: bytes,
                   prep_state: MasticPrepState,
                   prep_msg: MasticPrepMessage,
                   ) -> list[F]:
       (truncated_out_share, joint_rand_seed) = prep_state
       if joint_rand_seed is not None:
           if prep_msg is None:
               raise ValueError('expected joint rand confirmation')

           if prep_msg != joint_rand_seed:
               raise Exception('joint rand confirmation failed')

       return truncated_out_share

4.3.  Validity of Aggregation Parameters

   To guarantee secure execution of Mastic, care must be taken in
   choosing the VIDPF prefixes and whether to verify the FLP.  In
   particular, it is only safe to consume the FLP once; and it is only
   safe to evaluate the VIDPF at most once at any given level of the
   tree.

      NOTE By "safe" we mean "covered by the analysis of [MPDST25]".  It
      could be that we have a little more wiggle room, but we're not
      certain.  If we find matching attacks, we should mention them in
      Section 5.

   We further restrict aggregation by requiring that the level strictly
   increases at each step:















Davis, et al.             Expires 28 July 2025                 [Page 28]

Internet-Draft                   Mastic                     January 2025


   def is_valid(self,
                   agg_param: MasticAggParam,
                   previous_agg_params: list[MasticAggParam],
                   ) -> bool:
       (level, _prefixes, do_weight_check) = agg_param

       # Check that the weight check is done exactly once.
       weight_checked = \
           (do_weight_check and len(previous_agg_params) == 0) or \
           (not do_weight_check and
               any(agg_param[2] for agg_param in previous_agg_params))

       # Check that the level is strictly increasing.
       level_increased = len(previous_agg_params) == 0 or \
           level > previous_agg_params[-1][0]

       return weight_checked and level_increased

4.4.  Aggregation

   Each output share consists of the truncated payload for each VIDPF
   prefix, flattened into a single vector.  Aggregation involves simply
   adding these up:

   def agg_init(self, agg_param: MasticAggParam) -> list[F]:
       (_level, prefixes, _do_weight_check) = agg_param
       agg = self.field.zeros(len(prefixes)*(1+self.flp.OUTPUT_LEN))
       return agg

   def agg_update(self,
                   agg_param: MasticAggParam,
                   agg_share: list[F],
                   out_share: list[F]) -> list[F]:
       return vec_add(agg_share, out_share)

   def merge(self,
               agg_param: MasticAggParam,
               agg_shares: list[list[F]]) -> list[F]:
       (_level, prefixes, _do_weight_check) = agg_param
       agg = self.agg_init(agg_param)
       for agg_share in agg_shares:
           agg = vec_add(agg, agg_share)
       return cast(list[F], agg)

4.5.  Unsharding

   The aggregate result consists of a list of total weights, each
   corresponding to one of the prefixes.  To compute it:



Davis, et al.             Expires 28 July 2025                 [Page 29]

Internet-Draft                   Mastic                     January 2025


   1.  Add up the aggregate shares.

   2.  For each prefix, decode the corresponding vector chunk using the
       FLP's decoding algorithm (Section 7.1.1 of [VDAF]).  This
       requires the prefix count, which is also encoded by the chunk.

   The complete algorithm is listed below:

   def unshard(self,
               agg_param: MasticAggParam,
               agg_shares: list[list[F]],
               _num_measurements: int,
               ) -> list[R]:
       agg = self.merge(agg_param, agg_shares)

       agg_result = []
       while len(agg) > 0:
           (chunk, agg) = front(self.flp.OUTPUT_LEN + 1, agg)
           meas_count = chunk[0].int()
           agg_result.append(self.flp.decode(chunk[1:], meas_count))
       return agg_result

4.6.  Auxiliary Functions

   def expand_input_share(
           self,
           ctx: bytes,
           agg_id: int,
           input_share: MasticInputShare,
   ) -> tuple[bytes, list[F], Optional[bytes], Optional[bytes]]:
       if agg_id == 0:
           (key, proof_share, seed, peer_joint_rand_part) = input_share
           assert proof_share is not None
       else:
           (key, _leader_proof_share, seed, peer_joint_rand_part) = input_share
           assert seed is not None
           proof_share = self.helper_proof_share(ctx, seed)
       return (key, proof_share, seed, peer_joint_rand_part)

   def helper_proof_share(self, ctx, seed: bytes) -> list[F]:
       return self.xof.expand_into_vec(
           self.field,
           seed,
           dst_alg(ctx, USAGE_PROOF_SHARE, self.ID),
           b'',
           self.flp.PROOF_LEN,
       )




Davis, et al.             Expires 28 July 2025                 [Page 30]

Internet-Draft                   Mastic                     January 2025


   def prove_rand(self, ctx: bytes, seed: bytes) -> list[F]:
       return self.xof.expand_into_vec(
           self.field,
           seed,
           dst_alg(ctx, USAGE_PROVE_RAND, self.ID),
           b'',
           self.flp.PROVE_RAND_LEN,
       )

   def joint_rand_part(
           self,
           ctx: bytes,
           seed: bytes,
           weight_share: list[F],
           nonce: bytes,
   ) -> bytes:
       return self.xof.derive_seed(
           seed,
           dst_alg(ctx, USAGE_JOINT_RAND_PART, self.ID),
           nonce + self.field.encode_vec(weight_share),
       )

   def joint_rand_seed(self, ctx: bytes, parts: list[bytes]) -> bytes:
       return self.xof.derive_seed(
           b'',
           dst_alg(ctx, USAGE_JOINT_RAND_SEED, self.ID),
           concat(parts),
       )

   def joint_rand(self, ctx: bytes, seed: bytes) -> list[F]:
       return self.xof.expand_into_vec(
           self.field,
           seed,
           dst_alg(ctx, USAGE_JOINT_RAND, self.ID),
           b'',
           self.flp.JOINT_RAND_LEN,
       )

   def query_rand(self,
                  verify_key: bytes,
                  ctx: bytes,
                  nonce: bytes,
                  level: int) -> list[F]:
       return self.xof.expand_into_vec(
           self.field,
           verify_key,
           dst_alg(ctx, USAGE_QUERY_RAND, self.ID),
           nonce + to_le_bytes(level, 2),



Davis, et al.             Expires 28 July 2025                 [Page 31]

Internet-Draft                   Mastic                     January 2025


           self.flp.QUERY_RAND_LEN,
       )

5.  Security Considerations

   Mastic inherits its security considerations from Section 9 of [VDAF].
   A security analysis of Mastic is provided in [MPDST25].

      TODO Contrast with Poplar1, especially Section 9.4.2 of [VDAF]
      ("Safe Usage of IDPF Outputs").  In particular, it's perfectly
      safe to use Mastic's intermediate outputs.

6.  IANA Considerations

   IANA is requested to add new identifiers to the "Verifiable
   Distributed Aggregation Functions (VDAF)" registry, that is described
   in Section 10 of [VDAF].  The new entries to the VDAF Identifier
   registry are as follows:

       +============+========================+======+=============+
       | Value      | Scheme                 | Type | Reference   |
       +============+========================+======+=============+
       | 0xFFFF0001 | MasticCount            | VDAF | Section 4   |
       |            |                        |      | of RFC XXXX |
       +------------+------------------------+------+-------------+
       | 0xFFFF0002 | MasticSum              | VDAF | Section 4   |
       |            |                        |      | of RFC XXXX |
       +------------+------------------------+------+-------------+
       | 0xFFFF0003 | MasticSumVec           | VDAF | Section 4   |
       |            |                        |      | of RFC XXXX |
       +------------+------------------------+------+-------------+
       | 0xFFFF0004 | MasticHistogram        | VDAF | Section 4   |
       |            |                        |      | of RFC XXXX |
       +------------+------------------------+------+-------------+
       | 0xFFFF0005 | MasticMultihotCountVec | VDAF | Section 4   |
       |            |                        |      | of RFC XXXX |
       +------------+------------------------+------+-------------+

          Table 6: Additional codepoints for the VDAF Identifier
                                Registry.

      TODO The codepoints in this section are from the private codepoint
      range and are used for testing purposes.  We will update this
      table with the codepoints assigned by IANA.

   (RFC EDITOR: Please replace "RFC XXXX" above with the RFC number
   assigned to this document.)




Davis, et al.             Expires 28 July 2025                 [Page 32]

Internet-Draft                   Mastic                     January 2025


7.  References

7.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/rfc/rfc2119>.

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

   [VDAF]     Barnes, R., Cook, D., Patton, C., and P. Schoppmann,
              "Verifiable Distributed Aggregation Functions", Work in
              Progress, Internet-Draft, draft-irtf-cfrg-vdaf-14, 10
              January 2025, <https://datatracker.ietf.org/doc/html/
              draft-irtf-cfrg-vdaf-14>.

7.2.  Informative References

   [BGI15]    Boyle, E., Gilboa, N., and Y. Ishai, "Function Secret
              Sharing", EUROCRYPT 2015 , 2015,
              <https://www.iacr.org/archive/
              eurocrypt2015/90560300/90560300.pdf>.

   [CP22]     de Castro, L. and A. Polychroniadou, "Lightweight,
              Maliciously Secure Verifiable Function Secret Sharing",
              EUROCRYPT 2022 , 2022,
              <https://iacr.org/cryptodb/data/paper.php?pubkey=31935>.

   [DAP]      Geoghegan, T., Patton, C., Rescorla, E., and C. A. Wood,
              "Distributed Aggregation Protocol for Privacy Preserving
              Measurement", Work in Progress, Internet-Draft, draft-
              ietf-ppm-dap-07, 14 September 2023,
              <https://datatracker.ietf.org/doc/html/draft-ietf-ppm-dap-
              07>.

   [MPDST25]  Mouris, D., Patton, C., Davis, H., Sarkar, P., and N. G.
              Tsoutsos, "Mastic: Private Weighted Heavy-Hitters and
              Attribute-Based Metrics", PETS 2025 , 2025,
              <https://ia.cr/2024/221>.

   [MST24]    Mouris, D., Sarkar, P., and N. G. Tsoutsos, "PLASMA:
              Private, Lightweight Aggregated Statistics against
              Malicious Adversaries", PETS 2024 , 2024,
              <https://ia.cr/2023/080>.




Davis, et al.             Expires 28 July 2025                 [Page 33]

Internet-Draft                   Mastic                     January 2025


   [RFC9110]  Fielding, R., Ed., Nottingham, M., Ed., and J. Reschke,
              Ed., "HTTP Semantics", STD 97, RFC 9110,
              DOI 10.17487/RFC9110, June 2022,
              <https://www.rfc-editor.org/rfc/rfc9110>.

   [RZCGP24]  Rathee, M., Zhang, Y., Corrigan-Gibbs, H., and R. A. Popa,
              "Private Analytics via Streaming, Sketching, and Silently
              Verifiable Proofs", IEEE S&P 2024 , 2024,
              <https://eprint.iacr.org/2024/666>.

   [SHS]      "Secure hash standard", National Institute of Standards
              and Technology (U.S.), DOI 10.6028/nist.fips.180-4, 2015,
              <https://doi.org/10.6028/nist.fips.180-4>.

   [W3C23]    W3C Working Group, "Network Error Logging", 2023,
              <https://www.w3.org/TR/network-error-logging>.

Acknowledgments

   The Network Error Logging and Attribute-Based Browser Telemetry
   applications (discussed next in section Appendix "Motivating
   Applications") were first described to the authors by the PPM working
   group at IETF.  The authors would like to thank Suleman Ahmad and
   Simon Friedberger for their help in fleshing out the details.
   Dimitris Mouris and Nektarios Georgios Tsoutsos would like to
   acknowledge the support of the National Science Foundation (Award
   2239334).

Motivating Applications

   The design of Mastic is informed primarily by two use cases, which we
   describe here.

Network Error Logging

   Network Error Logging (NEL) is a mechanism used by web browsers to
   report errors that occur while attempting to establish a connection
   to a server [W3C23].  Some of these errors are visible to the server,
   but not all: failures in DNS, TCP, TLS, and HTTP can occur without
   the server having any visibility into the issue.  A small amount of
   connection errors is expected, even under normal operating
   conditions; but a sudden, substantial increase in errors may be an
   indication of an outage, or a configuration issue impacting millions
   of users.  Without a reporting mechanism like NEL, these events would
   only manifest in the server's telemetry as a drop in overall traffic.






Davis, et al.             Expires 28 July 2025                 [Page 34]

Internet-Draft                   Mastic                     January 2025


   NEL is particularly important for content delivery networks that
   handle HTTP traffic for a large number of websites (typically
   millions).  A content delivery network acts as a reverse proxy
   between clients and origin servers that provides a layer of caching
   and security services, such as DDoS protection.

   Reports are comprised of the URL the client attempted to navigate to
   (e.g., "https://example.com"), the type of error that occurred, and
   metadata related to the attempt, such as the time that elapsed
   between when the connection attempt began and the error was observed
   (e.g., Section 7 of [W3C23]).  Clients may also report successful
   connection attempts to give the server a sense of the error rate.
   The exact client behavior is determined by the reporting policy
   specified by the server (see Section 5.1 of [W3C23]).

   NEL data is privacy-sensitive for two reasons.  First, it exposes
   information that the server would not otherwise have access to, which
   can be abused to probe the client's network configuration as
   described in Section 9 of [W3C23].  Second, for operational reasons,
   the reporting endpoint may be organizationally separated from the
   server (i.e., run on different cloud infrastructures), leading to an
   increased risk of the client's browsing history being exposed (e.g.,
   in a data breach).

   MPC helps mitigate these risks by revealing to the endpoint only the
   information it needs to fulfill its service level objectives.  This
   means, of course, we must be satisfied with limited functionality.
   Fortunately, Mastic allows us to preserve the most important
   functionality of NEL while minimizing privacy loss.

   Mastic can be applied to a simplified version of NEL where each
   client reports a tuple (dom, err) consisting of a domain name dom
   (e.g., "example.com") and a value err that represents an error (e.g.,
   "dns.unreachable") or an indication that no error occurred (e.g.,
   "ok").  Notably, this can be easily extended in Mastic to represent
   more elaborate metrics. e.g., where each weight includes the time it
   took each browser to report the error (and the aggregate is the
   average error reporting time), user agent (browser type and version),
   etc.  However, our main goal is to understand 1) the distribution of
   errors and 2) which domains are impacted.

   We expect there to be a large number of distinct domain names
   (millions in the case of content delivery networks) and only a small
   number of error variants (the NEL spec [W3C23] defines 30 variants).
   The following Mastic parameters are suitable for this application.






Davis, et al.             Expires 28 July 2025                 [Page 35]

Internet-Draft                   Mastic                     January 2025


   Each input would encode the domain dom encoded with a number of bits
   sufficient to uniquely represent most of the domains; and each weight
   would represent the error variant dom.  To compute the distribution
   of errors, we would encode each error variant as a distinct bucket of
   a histogram so that [1, 0, 0, ...] represents "ok", [0, 1, 0, ...]
   represents "dns.unreachable", and so on.  (See ection 6 of [W3C23].),
   This is similar to Prio3Histogram (Section 7 of [VDAF].)

Attribute-Based Browser Telemetry

   Web browsers collect telemetry generated by users as they navigate
   the web to gain insights into trends that guide product decisions.
   In many cases, Prio3 (Section 7 of [VDAF]) can be used to privately
   aggregate this telemetry.  However, this comes at the cost of
   flexibility.

   For example, Prio3 can be used to collect page load metrics from
   Browser for a list of known popular sites (e.g., "example.com").  The
   purpose of these metrics is to detect if changes to these sites cause
   regressions that might be correlated with an increased average load
   time or error rate.  A subtle, but important requirement for this
   system is the ability to break down the metrics by client attributes.
   Suppose for example that we want to aggregate by 1) the software
   version, and 2) the information about the client's location.

   Mastic provides a simple solution to this problem.  For the sake of
   presentation, we consider a simplified use case (the same approach
   can be applied to any aggregation task for which Prio3 (Section 7 of
   [VDAF]) is suitable).  Each client reports a tuple (ver, loc, site,
   time) where: ver is a string representing the client's software
   version (e.g., "Browser/122.0"); loc is a string encoding its country
   code (e.g., "GR", "US", "IN", etc.); site is one of a fixed set of
   sites (e.g., "example.com", "example.org", etc.); and time is the
   load time of the site in seconds.  The version and location are
   included in the Mastic input; the site and load time are encoded by
   the corresponding weight.  Notably, this is just one example of what
   Mastic can do; the same idea can be applied to other types of
   metrics.

   Compared to the private NEL application in Appendix "Network Error
   Logging", the number of possible inputs here is relatively small:
   there are less than 200 country codes and a handful of browser
   versions in wide use at any given time.  This means the aggregators
   can enumerate a set of inputs of interest and evaluate them
   immediately.  Consider the following parameters for Mastic, in its
   attribute-based metrics mode of operation Appendix "Attribute-based
   Metrics":




Davis, et al.             Expires 28 July 2025                 [Page 36]

Internet-Draft                   Mastic                     January 2025


   *  Attributes: Two-letter country codes can easily be encoded in 2
      bytes.  Likewise, the number of distinct browser versions is
      easily less than 2^16, so 2 bytes are sufficient.  Therefore, each
      attribute can be encoded with just 32 bits.

   *  Values: Similar to private NEL, each weight is a 0-vector except
      for a single 1 representing a bucket in a histogram.  We represent
      (site, time) as a histogram bucket as follows.  First, we quantize
      time (in seconds) into one of four buckets: [0, 0.1), [0.1, 1),
      [1, 5), and [5, inf).  Let 0 < t <= 4 denote the time bucket for
      time.  Next, suppose we wish to track metrics for 25 sites.  Let 0
      < s <= 25 denote the index of site in this list.  Then the index
      of 1 is simply t * s.

Modes of Operation

Weighted Heavy-Hitters

      NOTE See Appendix "Network Error Logging" for a motivating
      application and example_weighted_heavy_hitters_mode() in the
      reference implementation for an end-to-end example.

   The primary use case for Mastic is a variant of the heavy-hitters
   problem, in which the prefix counts are replaced with a notion of
   weight that is specific to some application.  For example, when
   measuring the performance of an ad campaign, it is useful to learn
   not only which ads led to purchases, but how much money was spent.

   To support this use case, we view the Client's alpha value as its
   measurement and the beta value as the measurement's "weight".  The
   range of valid values for beta are therefore determined by the FLP
   with which Mastic is instantiated.  Concretely, validity of beta is
   expressed by a validity circuit (Section 7.3.2 of [VDAF]).

   To compute the weighted heavy-hitters, the Collector and Aggregators
   proceed as described in Section 8 of [VDAF], except that the
   threshold represents a minimum weight rather than a minimum count.
   In addition:

   1.  The Aggregators MUST perform the range check (i.e., verify the
       FLP) at the first round of aggregation and remove any invalid
       reports before proceeding.

   2.  The level at which the reports are Aggregated MUST be strictly
       increasing.






Davis, et al.             Expires 28 July 2025                 [Page 37]

Internet-Draft                   Mastic                     January 2025


Different Thresholds

      NOTE For an end-to-end example, see
      example_weighted_heavy_hitters_mode_with_different_thresholds() in
      the reference implementation.

   So far, we have assumed that there is a single threshold for
   determining which prefixes are "heavy".  However, we can easily
   extend this to have different thresholds for different prefixes.
   There exist use-cases where prefixes starting with "000" may be
   significantly more popular than prefixes starting with "111".
   Setting a low threshold may result in an overwhelmingly big set of
   heavy hitters starting with "000", while setting a high threshold
   might prune anything starting with "111".  Consider the following
   examples:

   1.  Popular URLs: a.example.com receives a massive amount of traffic
       whereas b.example.com may have lower traffic.  To identify heavy-
       hitting search queries on a.example.com, the Aggregators should
       set a high threshold, while queries with different domain
       prefixes may require lower thresholds to be considered popular.

   2.  E-commerce: Grocery items are essential and have a high volume of
       sales.  In contrast, electronics, though popular, usually come
       with a higher price compared to groceries.  Meanwhile, luxury
       items command significantly higher prices but generally
       experience lower sales volumes.  To identify heavy-hitting
       grocery items on an e-commerce website, Aggregators could use
       different threshold for each of these categories.  These
       thresholds are set to ensure that only the top-selling grocery
       items qualify as heavy hitters while electronics and luxury items
       are also considered heavy hitters on their own categories.

   To tackle this, Mastic can allow different prefixes having different
   thresholds.  When a specific prefix does not have an associated
   threshold, we first search if any of its prefixes has a specified
   threshold, otherwise we use a default threshold.  For example, if the
   Aggregators have set the thresholds to be {"000": 10, "111": 2,
   "default": 5} and the search for prefix "01", then threshold 5 should
   be used.  However, if the Aggregators search for prefix "11101", then
   threshold 2 should be used.

Attribute-based Metrics

      NOTE See Appendix "Attribute-Based Browser Telemetry" for a
      motivating application and example_attribute_based_metrics_mode()
      in the reference implementation for an end-to-end example.




Davis, et al.             Expires 28 July 2025                 [Page 38]

Internet-Draft                   Mastic                     January 2025


   In this mode of operation, we take the beta value to be the Client's
   measurement and alpha to be an arbitrary "attribute".  For a given
   sequence of attributes, the goal of the Collector is to aggregate the
   measurements that share the same attribute.  This provides
   functionality similar to Prio3 [VDAF], except that the aggregate is
   partitioned by Clients who share some property.  For example, the
   attribute might encode the Client's user agent [RFC9110].

   Mastic requires each alpha to have the same length (Vidpf.BITS).
   Thus, it is necessary for each application to choose a scheme for
   encoding attributes as fixed-length strings.  The following scheme is
   RECOMMENDED.  Choose a cryptographically secure hash function, such
   as SHA256 [SHS], compute the hash of the Client's input string, and
   interpret each bit of the hash as a bit of the VIDPF index.

      TODO Are we comfortable recommending truncating the hash?
      Collisions aren't so bad since the Client can just lie about alpha
      anyway.  The main thing is to pick a value for BITS that is large
      enough to avoid accidental collisions.

   The Aggregators MAY aggregate a report any number times, but:

   1.  They MUST perform the range check (i.e., verify the FLP) the
       first time the reports are aggregated and remove any invalid
       reports before aggregating again.

   2.  The aggregation parameter MUST specify the last level of the
       VIDPF tree (i.e., level MUST be Vidpf.BITS-1).

      TODO Figure out if these requirements are strict enough.  We may
      need to tighten aggregation parameter validity if we find out that
      aggregating at the same level more than once is not safe.

Plain Heavy-Hitters with VIDPF-Proof Aggregation

      TODO Take "silently verifiable proofs" from [RZCGP24] into account
      here, which allows us to aggregate the FLPs as well.

   The total communication cost of using Mastic (or Poplar1 [VDAF]) for
   heavy hitters is O(num_measurements * Vidpf.BITS) bits exchanged
   between the Aggregators, where num_measurements is the number of
   reports being aggregated.  For plain heavy-hitters, this can be
   reduced to O(Vidpf.BITS) in the best case.








Davis, et al.             Expires 28 July 2025                 [Page 39]

Internet-Draft                   Mastic                     January 2025


   The idea is to take advantage of the feature of VIDPF evaluation
   whereby the Aggregators compute identical VIDPF proofs if and only if
   the report is valid.  This allows the proofs themselves to be
   aggregated: if each report in a batch of reports is valid, then the
   hash of their proofs will be equal as well; on the other hand, if one
   report is invalid, then the hash of the proofs will not be equal.

   To facilitate isolation of the invalid report(s), the proof strings
   are arranged into a Merkle tree.  During aggregation, the Aggregators
   interactively traverse the tree to detect the subtree(s) containing
   invalid reports and remove them from the batch.

      TODO Decide if we should spell this out in greater detail.  This
      feature is not compatible with [DAP]; if we wanted to extend DAP
      to support this, then we'd need to specify the wire format of the
      messages exchanged between the Aggregators.

   In the worst case, isolating invalid reports requires
   O(num_measurements * Vidpf.BITS) bits of communication and Vidpf.BITS
   many rounds of communication between the Aggregators.  However, this
   behavior would only be observed under attack conditions in which the
   vast majority of Clients are malicious.

   In the simple case where the beta value is a constant (e.g., 1) we
   can replace the FLP check with a simpler check.  FLPs are not
   compatible with proof aggregation the way VIDPFs are.  In order to
   perform the range check without FLPs, we use an extension of VIDPF
   described by [MST24].  The high-level idea here is that the
   Aggregators can evaluate the empty string and verify that they have
   shares of the constant beta.  Next, as described in Section 4, we use
   the "one-hot verifiability" and "path verifiability" checks to verify
   that each level is non-zero at only a single point and that the same
   constant beta is propagated down the tree correctly.  Note that this
   trick is not suitable for weighted heavy-hitters, since it expects
   that each beta value is constant (e.g., 1).

      TODO Proof aggregation could work with plain Mastic, but we would
      need to check the FLPs at the first round of aggregation, leading
      to best-case communication cost would be O(num_measurements +
      Vidpf.BITS).  This would be OK, but we would still want to support
      a mode for plain heavy-hitters that is as good as we can get.

      One idea is to always do the PLASMA 0/1 check alongside the FLP.
      This would be useful for another reason: Usually FLP decoding
      requires num_measurements as a parameter.  We currently don't
      support this because we currently don't have a pure counter as
      part of the VIDPF output.




Davis, et al.             Expires 28 July 2025                 [Page 40]

Internet-Draft                   Mastic                     January 2025


Robustness Against a Malicious Aggregator

   Next, we describe an enhancement that allows Mastic to achieve
   robustness in the presence of a malicious Aggregator.  The two-party
   Mastic (as well as Poplar1) is susceptible to additive attacks by a
   malicious Aggregator.  In more detail, if one of the Aggregators
   starts acting maliciously, they can arbitrarily add to the
   aggregation result (simply by adding to their own aggregation shares)
   without the honest Aggregator noticing.

   We can solve this problem in Mastic by using a technique from [MST24]
   that lifts the two-party semi-honest secure PLASMA to the three-party
   maliciously secure setting.  Rather than having two Aggregators as in
   the previous setting, this flavor involves three Aggregators, where
   every pair of Aggregators communicate over a different channel.  In
   essence, each pair of Aggregators will run one session of the VDAF
   with unique randomness but on the same Client measurement.  The
   following changes are necessary:

   1.  The Client needs to generate three pairs of VIDPF keys all
       corresponding to the same alpha and beta values.  We represent
       the keys based on the session as follows:

       1.  Session 0 (between Aggregators 0 and 1): key_01, key_10

       2.  Session 1 (between Aggregators 1 and 2): key_12, key_21

       3.  Session 2 (between Aggregators 2 and 0): key_20, key_02

       Each pair of Aggregators cannot check that the Client input is
       consistent across two sessions without the involvement of the
       third Aggregator.  To address this, we let two Aggregators (i.e.,
       Aggregators 0 and 1) to run all three sessions so that they can
       check that the Client input is consistent across three sessions.
       The third Aggregator (i.e., Aggregator 2) is involved as an
       attestator in two of the sessions.  The check involves field
       addition and subtraction and then hash comparisons.

   2.  The Client sends the following keys to the Aggregators:

       1.  Aggregator 0 receives: key_01, key_02, and key_21

       2.  Aggregator 1 receives: key_10, key_12, and key_20

       3.  Aggregator 2 receives: key_21 and key_20






Davis, et al.             Expires 28 July 2025                 [Page 41]

Internet-Draft                   Mastic                     January 2025


   3.  The Aggregators need to verify that the Client's input is
       consistent across the different sessions (i.e., that all the keys
       correspond to the same alpha and beta values).  Aggregators 0 and
       1 check that:

       1.  Their output shares of Session 0 minus their output shares of
           Session 1 are shares of zero

       2.  Their output shares of Session 1 minus their output shares of
           Session 2 are shares of zero.

       The subtraction is a local operation and verifying that two
       Aggregators possess a sharing of zero requires exchanging one
       hash.

   Using a third Aggregator, we can lift the security of Mastic from the
   semi-honest setting to malicious security.  While more complex to
   implement than 2-party Mastic, this mode allows achieves both privacy
   and robustness against a malicious Aggregator.

Test Vectors

   TODO

Contributors

   Pratik Sarkar
   Supra Research
   Email: pratik93@bu.edu


   David Cook
   ISRG
   Email: dcook@divviup.org


Authors' Addresses

   Hannah Davis
   Seagate
   Email: hannah.e.davis@seagate.com


   Dimitris Mouris
   Nillion
   Email: dimitris@nillion.com





Davis, et al.             Expires 28 July 2025                 [Page 42]

Internet-Draft                   Mastic                     January 2025


   Christopher Patton
   Cloudflare
   Email: chrispatton+ietf@gmail.com


   Nektarios G. Tsoutsos
   University of Delaware
   Email: tsoutsos@udel.edu











































Davis, et al.             Expires 28 July 2025                 [Page 43]