[CFRG] Review of draft-irtf-cfrg-vdaf-15

[Julia Hesse <[e-mail]>]

Dear all,

this is a review of Verifiable Distributed Aggregation Functions 
draft-irtf-cfrg-vdaf-15. I did not implement the draft/check the test 
vectors.

Overall, an impressive amount of work went into this draft and it 
appears to be in a pretty mature state. Thanks to the authors for 
putting such an effort into it. I sort my comments into three 
categories, namely terminology, presentation, and general comments.

Terminology and typos
---------------------
- DAF in Section 4 is only computing the sum of the inputs. Hence the 
name Function appears too general, as it is "just" distributed 
aggregated summing. Could the paragraph be phrased more general, for 
arbitrary functions, and then say that the draft only considers sums?

- Section 1 explains the V=verifiability property of VDAFs and then says 
that it is referred to as "robustness". Why not call it verifiability, 
i.e., why having two different names for the same thing?

- Section 3: Figure 1 shows only "aggregate shares" while the text also 
talks about "output shares". I find the terminology confusing because 
the "output shares" seem to be an intermediate computation step and are 
not an output of the aggregator. Also, Figure 1 could be augmented to 
show all the objects mentioned in the text, such as output shares and 
public shares.

- I am not familiar with the terminology of "simulating a procedure over 
an insecure network", but if RFC readers usually are, this is fine. For 
me, it was confusing to read this instruction in Section 5.6 while also 
demanding the application to instantiate secure channels (end of 5.6).

- A DAF computes a function over many client reports. Hence in Table 1 
it should be "a report" or "each report", and not "the report" in the 
NONCE_SIZE row.

- Replace all occurrences of "we" (e.g., we obtain, we compute, the 
inputs we used) by prover/verifier/client/aggregator/etc., except for 
the ones that actually refer to the authors of the draft ;)

- Section 8: the Aggregators run VDAF - should be "run the Poplar1 VDAF" 
or just Poplar1

- Section 9: "a subset of Clients and Aggregators" should be "a subset 
of Clients and a subset of Aggregators", as otherwise, controlling e.g. 
all clients would be allowed.

- Section 9.1: rewrite to potentially many aggregators, or restrict to 
the case of Poplar1


Presentation
------------
- Section 1: explain in 1-2 sentences how Poplar1 if different from 
Poplar. Additionally, it should be briefly discussed in Section 9 how 
the changes affect the security analysis that was conducted for Poplar.

- Section 4, "For example, the aggregation parameter is used to 
represent the candidate prefixes in the Poplar1 VDAF" - at this point, 
where a reader might not be familiar with Poplar1 at all, so terms like 
candidate prefix are not known yet. Maybe replace by something more 
illustrative?


General
-------
- Section 4.1, daf.shard: this is an algorithm to be run locally by 
every user, and it requires a nonce as input which is then also sent to 
the aggregators. This nonce is a public nonce associated to a single 
report. The draft mandates generation through a CSPRNG, but a malicious 
client must not follow that instruction. What happens if two reports 
have the same nonce? In particular, this nonce seems to later also go 
into the computation of the joint randomness, so this is related also to 
the question of whether the randomness computation is robust against 
malicious clients who, e.g., replay nonces or choose them in another 
biased way.

- Section 5.2: the preparation seems to be executed on a per-client 
basis, if I understand correctly. Opposed to DAFs, where preparation is 
local, it seems that VDAFs require the application protocol to 
coordinate the preparation step such that aggregators are guaranteed to 
run it on the same client's input. This additional complexity does not 
seem to be explained in Section 5.2. It might be implicit in asking for 
equality of all public_share values, but such a check is meaningless 
because malicious clients can replay honest parties' public shares. So a 
lot of coordination from the application is required here that I could 
not find any mention of.

- "Achieving robustness without sacrificing privacy requires the servers 
to interact with one another over a number of rounds of communication" - 
is this obvious or backed up by a result from the literature?

- Equality check of joint randomness: In Section 7.2.2, it says that 
aggregators must check if they all computed the same proof randomness, 
to prevent the client from biasing the randomness. I do not see how an 
equality check prevents a malicious client from biasing: a malicious 
client could make *all* aggregators compute the same bad randomness. It 
is really malicious client security of the randomness generation 
procedure that is needed here. It should be explained in the security 
considerations whether there is a security result from the literature 
that covers this case.

- Robustness against dropped packages: It seems to me that a lost input 
share causes a failed validity check, so the schemes protect against 
that on the protocol level. An aggregator forgetting to include one of 
their input shares in the aggregate share causes the overall result to 
be wrong - this is essentially malicious aggregator behavior that both 
schemes do not protect against. A dropped aggregator share would also 
invalidate the overall result but can be protected against by the 
collector checking that they collected all shares, which is requested in 
the draft in terms of the collector ensuring that it has SHARES 
agg_shares going into unshard. Technically, it would be better to 
request that one agg_share received from each aggregator goes into 
unsharding (which then yields SHARES agg_shares in total). I was also 
unsure how to interpret the requirement of guaranteed delivery mandated 
in Section 9. Is that needed on top of, e.g., the checks for all shares 
to be there?

- Prio3 is a VDAF that follows the design principle of the original VDAF 
protocol by Corrigan-Gibbs et al, but using a ZK proof system from a 
work by Boneh et al. The interesting question is how this replacement 
affects the security. I do not find a paper in the literature that 
argues formally what properties a proof system has to have in order to 
yield a robust and private VDAF in Corrigan-Gibbs et al.'s construction. 
Instead, [DPRS23] directly proofs the security of Prio3. I spent a 
considerable amount of time with that paper and the analysis appears 
sound to me, although I was not able to fully understand all the 
details. It needs to be kept in mind that Prio3 is a very complex 
protocol, both to write down/implement and verify the security, and it 
was published (in form of early versions of this draft) not long ago. It 
is not unlikely that all of us overlook subtleties. This is not to 
recommend to stop working on this effort, of course. It is just 
something that adopters need to be aware of.

- Section 7.3.3 explains that the prove randomness is used to construct 
gadget polynomials, but that polynomial is also said to be the lowest 
degree polynomial that evaluates to a sequence of fixed points. That 
seems to be a unique polynomial, so where do we need randomness for this 
step?

- Section 9: "Uniqueness of the nonce is not sufficient because the 
verification key is controlled by the attacker" - I could not make sense 
out of this sentence. First, the link between the report nonces and the 
verification key is unclear to me. Second, how can the verification key 
be controlled by the attacker if the aggregators generate and distribute 
it over their secure and authenticated channels - aggregators are honest.

Best,
Julia