Comparing Vdaf::PrepareState in constant time

[tgeoghegan]

Users of prio need to compare various objects related to VDAFs such as Vdaf::PrepareState to one another. For example, to check whether a given state transition occurred as expected in a test, or to check whether a database row already contains some incoming value.

In test settings, it's probably fine to use derived PartialEq + Eq implementations which will boil down to comparing slices of bytes. But in other contexts, we need to make sure that comparisons are done in constant time.

We could address this by auditing the PartialEq implementations on each VDAF implementation's associated types, replacing them with hand-written, constant time verisons as needed. But the risk there is that new VDAFs will use derived PartialEq implementations that aren't constant time. So perhaps we would want to remove all PartialEq + Eq trait bounds and instead define some custom ConstantTimeEq trait.

Originally posted by @cjpatton in #683 (comment)

[branlwyd]

I think we don't actually need ReportAggregation to be PartialEq + Eq in non-test code; we could make a test-only (test-util-only?) PartialEq + Eq implementation that checks equality of the PrepareState by serializing it and checking equality of the serialized bytes. This would let us drop PartialEq + Eq from Vdaf::PrepareState, alleviating cjpatton's concern.

Other than test uses, we currently use the PartialEq + Eq bounds for:

• Checking if a report aggregation is at state START in the aggregation job driver. This could be replaced with a matches! check, which does not require PartialEq + Eq.
• Checking idempotency on repeated aggregation job PUTs, which checks equality of the report aggregations associated with the aggregation job. Instead, we could check equality of the report shares. (checking equality of the aggregation job itself will already detect an attempt to PUT an aggregation job that has already been stepped beyond the initial PUT, since aggregation jobs track the current round of aggregation)

[branlwyd]

Oof, the report share doesn't actually store the incoming input share (it only gets recorded to the report aggregations). So idempotency-checking aggregation jobs can't use the report shares.

However: checking the last_continue_request_hash included in AggregationJob would almost suffice to obviate checking the report aggregations at all (saving us from needing to read them, too)... except that we only set it for continuation requests. I think we could just change it to last_request_hash, start populating it on aggregate init requests too, and rely on it to determine if the aggregation job is the same.

[branlwyd]

I noticed the preexisting ReportAggregation/ReportAggregationState equality checks will also compare output shares, which (I believe) would have similar issues around non-constant-time comparisons.

Since PartialEq + Eq will soon be hidden behind #[cfg(test)], this doesn't matter too much to Janus -- but libprio-rs does derive PartialEq + Eq on the output share types (though this is not required by the trait's related-type definition). Should it perhaps not do so?

[divergentdave]

some custom ConstantTimeEq trait

We already depend on the subtle crate, so we could use subtle::ConstantTimeEq.