diff options
Diffstat (limited to 'third_party/rust/prio/src/vdaf.rs')
| -rw-r--r-- | third_party/rust/prio/src/vdaf.rs | 437 |
1 files changed, 219 insertions, 218 deletions
diff --git a/third_party/rust/prio/src/vdaf.rs b/third_party/rust/prio/src/vdaf.rs index 1a6c5f0315..e5f4e14c5a 100644 --- a/third_party/rust/prio/src/vdaf.rs +++ b/third_party/rust/prio/src/vdaf.rs @@ -1,14 +1,16 @@ // SPDX-License-Identifier: MPL-2.0 //! Verifiable Distributed Aggregation Functions (VDAFs) as described in -//! [[draft-irtf-cfrg-vdaf-07]]. +//! [[draft-irtf-cfrg-vdaf-08]]. //! -//! [draft-irtf-cfrg-vdaf-07]: https://datatracker.ietf.org/doc/draft-irtf-cfrg-vdaf/07/ +//! [draft-irtf-cfrg-vdaf-08]: https://datatracker.ietf.org/doc/draft-irtf-cfrg-vdaf/08/ #[cfg(feature = "experimental")] use crate::dp::DifferentialPrivacyStrategy; #[cfg(all(feature = "crypto-dependencies", feature = "experimental"))] use crate::idpf::IdpfError; +#[cfg(all(feature = "crypto-dependencies", feature = "experimental"))] +use crate::vidpf::VidpfError; use crate::{ codec::{CodecError, Decode, Encode, ParameterizedDecode}, field::{encode_fieldvec, merge_vector, FieldElement, FieldError}, @@ -17,15 +19,16 @@ use crate::{ vdaf::xof::Seed, }; use serde::{Deserialize, Serialize}; -use std::{fmt::Debug, io::Cursor}; +use std::{error::Error, fmt::Debug, io::Cursor}; use subtle::{Choice, ConstantTimeEq}; /// A component of the domain-separation tag, used to bind the VDAF operations to the document /// version. This will be revised with each draft with breaking changes. -pub(crate) const VERSION: u8 = 7; +pub(crate) const VERSION: u8 = 8; /// Errors emitted by this module. #[derive(Debug, thiserror::Error)] +#[non_exhaustive] pub enum VdafError { /// An error occurred. #[error("vdaf error: {0}")] @@ -55,6 +58,15 @@ pub enum VdafError { #[cfg(all(feature = "crypto-dependencies", feature = "experimental"))] #[error("idpf error: {0}")] Idpf(#[from] IdpfError), + + /// VIDPF error. + #[cfg(all(feature = "crypto-dependencies", feature = "experimental"))] + #[error("vidpf error: {0}")] + Vidpf(#[from] VidpfError), + + /// Errors from other VDAFs. + #[error(transparent)] + Other(Box<dyn Error + 'static + Send + Sync>), } /// An additive share of a vector of field elements. @@ -67,18 +79,6 @@ pub enum Share<F, const SEED_SIZE: usize> { Helper(Seed<SEED_SIZE>), } -impl<F: Clone, const SEED_SIZE: usize> Share<F, SEED_SIZE> { - /// Truncate the Leader's share to the given length. If this is the Helper's share, then this - /// method clones the input without modifying it. - #[cfg(feature = "prio2")] - pub(crate) fn truncated(&self, len: usize) -> Self { - match self { - Self::Leader(ref data) => Self::Leader(data[..len].to_vec()), - Self::Helper(ref seed) => Self::Helper(seed.clone()), - } - } -} - impl<F: ConstantTimeEq, const SEED_SIZE: usize> PartialEq for Share<F, SEED_SIZE> { fn eq(&self, other: &Self) -> bool { self.ct_eq(other).into() @@ -130,16 +130,15 @@ impl<F: FieldElement, const SEED_SIZE: usize> ParameterizedDecode<ShareDecodingP } impl<F: FieldElement, const SEED_SIZE: usize> Encode for Share<F, SEED_SIZE> { - fn encode(&self, bytes: &mut Vec<u8>) { + fn encode(&self, bytes: &mut Vec<u8>) -> Result<(), CodecError> { match self { Share::Leader(share_data) => { for x in share_data { - x.encode(bytes); + x.encode(bytes)?; } + Ok(()) } - Share::Helper(share_seed) => { - share_seed.encode(bytes); - } + Share::Helper(share_seed) => share_seed.encode(bytes), } } @@ -158,9 +157,6 @@ impl<F: FieldElement, const SEED_SIZE: usize> Encode for Share<F, SEED_SIZE> { /// and [`Collector`], which define the roles of the various parties involved in the execution of /// the VDAF. pub trait Vdaf: Clone + Debug { - /// Algorithm identifier for this VDAF. - const ID: u32; - /// The type of Client measurement to be aggregated. type Measurement: Clone + Debug; @@ -188,17 +184,20 @@ pub trait Vdaf: Clone + Debug { + for<'a> ParameterizedDecode<(&'a Self, &'a Self::AggregationParam)> + Encode; + /// Return the VDAF's algorithm ID. + fn algorithm_id(&self) -> u32; + /// The number of Aggregators. The Client generates as many input shares as there are /// Aggregators. fn num_aggregators(&self) -> usize; /// Generate the domain separation tag for this VDAF. The output is used for domain separation /// by the XOF. - fn domain_separation_tag(usage: u16) -> [u8; 8] { + fn domain_separation_tag(&self, usage: u16) -> [u8; 8] { let mut dst = [0_u8; 8]; dst[0] = VERSION; dst[1] = 0; // algorithm class - dst[2..6].copy_from_slice(&(Self::ID).to_be_bytes()); + dst[2..6].copy_from_slice(&(self.algorithm_id()).to_be_bytes()); dst[6..8].copy_from_slice(&usage.to_be_bytes()); dst } @@ -211,7 +210,7 @@ pub trait Client<const NONCE_SIZE: usize>: Vdaf { /// /// Implements `Vdaf::shard` from [VDAF]. /// - /// [VDAF]: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vdaf-07#section-5.1 + /// [VDAF]: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vdaf-08#section-5.1 fn shard( &self, measurement: &Self::Measurement, @@ -247,7 +246,7 @@ pub trait Aggregator<const VERIFY_KEY_SIZE: usize, const NONCE_SIZE: usize>: Vda /// /// Implements `Vdaf.prep_init` from [VDAF]. /// - /// [VDAF]: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vdaf-07#section-5.2 + /// [VDAF]: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vdaf-08#section-5.2 fn prepare_init( &self, verify_key: &[u8; VERIFY_KEY_SIZE], @@ -262,29 +261,7 @@ pub trait Aggregator<const VERIFY_KEY_SIZE: usize, const NONCE_SIZE: usize>: Vda /// /// Implements `Vdaf.prep_shares_to_prep` from [VDAF]. /// - /// # Notes - /// - /// [`Self::prepare_shares_to_prepare_message`] is preferable since its name better matches the - /// specification. - /// - /// [VDAF]: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vdaf-07#section-5.2 - #[deprecated( - since = "0.15.0", - note = "Use Vdaf::prepare_shares_to_prepare_message instead" - )] - fn prepare_preprocess<M: IntoIterator<Item = Self::PrepareShare>>( - &self, - agg_param: &Self::AggregationParam, - inputs: M, - ) -> Result<Self::PrepareMessage, VdafError> { - self.prepare_shares_to_prepare_message(agg_param, inputs) - } - - /// Preprocess a round of preparation shares into a single input to [`Self::prepare_next`]. - /// - /// Implements `Vdaf.prep_shares_to_prep` from [VDAF]. - /// - /// [VDAF]: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vdaf-07#section-5.2 + /// [VDAF]: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vdaf-08#section-5.2 fn prepare_shares_to_prepare_message<M: IntoIterator<Item = Self::PrepareShare>>( &self, agg_param: &Self::AggregationParam, @@ -301,31 +278,7 @@ pub trait Aggregator<const VERIFY_KEY_SIZE: usize, const NONCE_SIZE: usize>: Vda /// /// Implements `Vdaf.prep_next` from [VDAF]. /// - /// # Notes - /// - /// [`Self::prepare_next`] is preferable since its name better matches the specification. - /// - /// [VDAF]: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vdaf-07#section-5.2 - #[deprecated(since = "0.15.0", note = "Use Vdaf::prepare_next")] - fn prepare_step( - &self, - state: Self::PrepareState, - input: Self::PrepareMessage, - ) -> Result<PrepareTransition<Self, VERIFY_KEY_SIZE, NONCE_SIZE>, VdafError> { - self.prepare_next(state, input) - } - - /// Compute the next state transition from the current state and the previous round of input - /// messages. If this returns [`PrepareTransition::Continue`], then the returned - /// [`Self::PrepareShare`] should be combined with the other Aggregators' `PrepareShare`s from - /// this round and passed into another call to this method. This continues until this method - /// returns [`PrepareTransition::Finish`], at which point the returned output share may be - /// aggregated. If the method returns an error, the aggregator should consider its input share - /// invalid and not attempt to process it any further. - /// - /// Implements `Vdaf.prep_next` from [VDAF]. - /// - /// [VDAF]: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vdaf-07#section-5.2 + /// [VDAF]: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vdaf-08#section-5.2 fn prepare_next( &self, state: Self::PrepareState, @@ -342,6 +295,7 @@ pub trait Aggregator<const VERIFY_KEY_SIZE: usize, const NONCE_SIZE: usize>: Vda /// Aggregator that implements differential privacy with Aggregator-side noise addition. #[cfg(feature = "experimental")] +#[cfg_attr(docsrs, doc(cfg(feature = "experimental")))] pub trait AggregatorWithNoise< const VERIFY_KEY_SIZE: usize, const NONCE_SIZE: usize, @@ -428,7 +382,7 @@ impl<F> From<Vec<F>> for OutputShare<F> { } impl<F: FieldElement> Encode for OutputShare<F> { - fn encode(&self, bytes: &mut Vec<u8>) { + fn encode(&self, bytes: &mut Vec<u8>) -> Result<(), CodecError> { encode_fieldvec(&self.0, bytes) } @@ -451,6 +405,12 @@ impl<F> Debug for OutputShare<F> { pub struct AggregateShare<F>(Vec<F>); +impl<F> From<Vec<F>> for AggregateShare<F> { + fn from(other: Vec<F>) -> Self { + Self(other) + } +} + impl<F: ConstantTimeEq> PartialEq for AggregateShare<F> { fn eq(&self, other: &Self) -> bool { self.ct_eq(other).into() @@ -498,7 +458,7 @@ impl<F: FieldElement> AggregateShare<F> { } impl<F: FieldElement> Encode for AggregateShare<F> { - fn encode(&self, bytes: &mut Vec<u8>) { + fn encode(&self, bytes: &mut Vec<u8>) -> Result<(), CodecError> { encode_fieldvec(&self.0, bytes) } @@ -507,151 +467,190 @@ impl<F: FieldElement> Encode for AggregateShare<F> { } } -#[cfg(test)] -pub(crate) fn run_vdaf<V, M, const SEED_SIZE: usize>( - vdaf: &V, - agg_param: &V::AggregationParam, - measurements: M, -) -> Result<V::AggregateResult, VdafError> -where - V: Client<16> + Aggregator<SEED_SIZE, 16> + Collector, - M: IntoIterator<Item = V::Measurement>, -{ +/// Utilities for testing VDAFs. +#[cfg(feature = "test-util")] +#[cfg_attr(docsrs, doc(cfg(feature = "test-util")))] +pub mod test_utils { + use super::{Aggregatable, Aggregator, Client, Collector, PrepareTransition, VdafError}; + use crate::codec::{Encode, ParameterizedDecode}; use rand::prelude::*; - let mut rng = thread_rng(); - let mut verify_key = [0; SEED_SIZE]; - rng.fill(&mut verify_key[..]); - - let mut agg_shares: Vec<Option<V::AggregateShare>> = vec![None; vdaf.num_aggregators()]; - let mut num_measurements: usize = 0; - for measurement in measurements.into_iter() { - num_measurements += 1; - let nonce = rng.gen(); - let (public_share, input_shares) = vdaf.shard(&measurement, &nonce)?; - let out_shares = run_vdaf_prepare( - vdaf, - &verify_key, - agg_param, - &nonce, - public_share, - input_shares, - )?; - for (out_share, agg_share) in out_shares.into_iter().zip(agg_shares.iter_mut()) { - // Check serialization of output shares - let encoded_out_share = out_share.get_encoded(); - let round_trip_out_share = - V::OutputShare::get_decoded_with_param(&(vdaf, agg_param), &encoded_out_share) - .unwrap(); - assert_eq!(round_trip_out_share.get_encoded(), encoded_out_share); - let this_agg_share = V::AggregateShare::from(out_share); - if let Some(ref mut inner) = agg_share { - inner.merge(&this_agg_share)?; - } else { - *agg_share = Some(this_agg_share); - } + /// Execute the VDAF end-to-end and return the aggregate result. + pub fn run_vdaf<V, M, const SEED_SIZE: usize>( + vdaf: &V, + agg_param: &V::AggregationParam, + measurements: M, + ) -> Result<V::AggregateResult, VdafError> + where + V: Client<16> + Aggregator<SEED_SIZE, 16> + Collector, + M: IntoIterator<Item = V::Measurement>, + { + let mut sharded_measurements = Vec::new(); + for measurement in measurements.into_iter() { + let nonce = random(); + let (public_share, input_shares) = vdaf.shard(&measurement, &nonce)?; + + sharded_measurements.push((public_share, nonce, input_shares)); } - } - for agg_share in agg_shares.iter() { - // Check serialization of aggregate shares - let encoded_agg_share = agg_share.as_ref().unwrap().get_encoded(); - let round_trip_agg_share = - V::AggregateShare::get_decoded_with_param(&(vdaf, agg_param), &encoded_agg_share) - .unwrap(); - assert_eq!(round_trip_agg_share.get_encoded(), encoded_agg_share); - } + run_vdaf_sharded(vdaf, agg_param, sharded_measurements) + } + + /// Execute the VDAF on sharded measurements and return the aggregate result. + pub fn run_vdaf_sharded<V, M, I, const SEED_SIZE: usize>( + vdaf: &V, + agg_param: &V::AggregationParam, + sharded_measurements: M, + ) -> Result<V::AggregateResult, VdafError> + where + V: Client<16> + Aggregator<SEED_SIZE, 16> + Collector, + M: IntoIterator<Item = (V::PublicShare, [u8; 16], I)>, + I: IntoIterator<Item = V::InputShare>, + { + let mut rng = thread_rng(); + let mut verify_key = [0; SEED_SIZE]; + rng.fill(&mut verify_key[..]); + + let mut agg_shares: Vec<Option<V::AggregateShare>> = vec![None; vdaf.num_aggregators()]; + let mut num_measurements: usize = 0; + for (public_share, nonce, input_shares) in sharded_measurements.into_iter() { + num_measurements += 1; + let out_shares = run_vdaf_prepare( + vdaf, + &verify_key, + agg_param, + &nonce, + public_share, + input_shares, + )?; + for (out_share, agg_share) in out_shares.into_iter().zip(agg_shares.iter_mut()) { + // Check serialization of output shares + let encoded_out_share = out_share.get_encoded().unwrap(); + let round_trip_out_share = + V::OutputShare::get_decoded_with_param(&(vdaf, agg_param), &encoded_out_share) + .unwrap(); + assert_eq!( + round_trip_out_share.get_encoded().unwrap(), + encoded_out_share + ); - let res = vdaf.unshard( - agg_param, - agg_shares.into_iter().map(|option| option.unwrap()), - num_measurements, - )?; - Ok(res) -} + let this_agg_share = V::AggregateShare::from(out_share); + if let Some(ref mut inner) = agg_share { + inner.merge(&this_agg_share)?; + } else { + *agg_share = Some(this_agg_share); + } + } + } -#[cfg(test)] -pub(crate) fn run_vdaf_prepare<V, M, const SEED_SIZE: usize>( - vdaf: &V, - verify_key: &[u8; SEED_SIZE], - agg_param: &V::AggregationParam, - nonce: &[u8; 16], - public_share: V::PublicShare, - input_shares: M, -) -> Result<Vec<V::OutputShare>, VdafError> -where - V: Client<16> + Aggregator<SEED_SIZE, 16> + Collector, - M: IntoIterator<Item = V::InputShare>, -{ - let input_shares = input_shares - .into_iter() - .map(|input_share| input_share.get_encoded()); - - let mut states = Vec::new(); - let mut outbound = Vec::new(); - for (agg_id, input_share) in input_shares.enumerate() { - let (state, msg) = vdaf.prepare_init( - verify_key, - agg_id, + for agg_share in agg_shares.iter() { + // Check serialization of aggregate shares + let encoded_agg_share = agg_share.as_ref().unwrap().get_encoded().unwrap(); + let round_trip_agg_share = + V::AggregateShare::get_decoded_with_param(&(vdaf, agg_param), &encoded_agg_share) + .unwrap(); + assert_eq!( + round_trip_agg_share.get_encoded().unwrap(), + encoded_agg_share + ); + } + + let res = vdaf.unshard( agg_param, - nonce, - &public_share, - &V::InputShare::get_decoded_with_param(&(vdaf, agg_id), &input_share) - .expect("failed to decode input share"), + agg_shares.into_iter().map(|option| option.unwrap()), + num_measurements, )?; - states.push(state); - outbound.push(msg.get_encoded()); - } + Ok(res) + } + + /// Execute VDAF preparation for a single report and return the recovered output shares. + pub fn run_vdaf_prepare<V, M, const SEED_SIZE: usize>( + vdaf: &V, + verify_key: &[u8; SEED_SIZE], + agg_param: &V::AggregationParam, + nonce: &[u8; 16], + public_share: V::PublicShare, + input_shares: M, + ) -> Result<Vec<V::OutputShare>, VdafError> + where + V: Client<16> + Aggregator<SEED_SIZE, 16> + Collector, + M: IntoIterator<Item = V::InputShare>, + { + let public_share = + V::PublicShare::get_decoded_with_param(vdaf, &public_share.get_encoded().unwrap()) + .unwrap(); + let input_shares = input_shares + .into_iter() + .map(|input_share| input_share.get_encoded().unwrap()); - let mut inbound = vdaf - .prepare_shares_to_prepare_message( - agg_param, - outbound.iter().map(|encoded| { - V::PrepareShare::get_decoded_with_param(&states[0], encoded) - .expect("failed to decode prep share") - }), - )? - .get_encoded(); - - let mut out_shares = Vec::new(); - loop { + let mut states = Vec::new(); let mut outbound = Vec::new(); - for state in states.iter_mut() { - match vdaf.prepare_next( - state.clone(), - V::PrepareMessage::get_decoded_with_param(state, &inbound) - .expect("failed to decode prep message"), - )? { - PrepareTransition::Continue(new_state, msg) => { - outbound.push(msg.get_encoded()); - *state = new_state - } - PrepareTransition::Finish(out_share) => { - out_shares.push(out_share); + for (agg_id, input_share) in input_shares.enumerate() { + let (state, msg) = vdaf.prepare_init( + verify_key, + agg_id, + agg_param, + nonce, + &public_share, + &V::InputShare::get_decoded_with_param(&(vdaf, agg_id), &input_share) + .expect("failed to decode input share"), + )?; + states.push(state); + outbound.push(msg.get_encoded().unwrap()); + } + + let mut inbound = vdaf + .prepare_shares_to_prepare_message( + agg_param, + outbound.iter().map(|encoded| { + V::PrepareShare::get_decoded_with_param(&states[0], encoded) + .expect("failed to decode prep share") + }), + )? + .get_encoded() + .unwrap(); + + let mut out_shares = Vec::new(); + loop { + let mut outbound = Vec::new(); + for state in states.iter_mut() { + match vdaf.prepare_next( + state.clone(), + V::PrepareMessage::get_decoded_with_param(state, &inbound) + .expect("failed to decode prep message"), + )? { + PrepareTransition::Continue(new_state, msg) => { + outbound.push(msg.get_encoded().unwrap()); + *state = new_state + } + PrepareTransition::Finish(out_share) => { + out_shares.push(out_share); + } } } - } - if outbound.len() == vdaf.num_aggregators() { - // Another round is required before output shares are computed. - inbound = vdaf - .prepare_shares_to_prepare_message( - agg_param, - outbound.iter().map(|encoded| { - V::PrepareShare::get_decoded_with_param(&states[0], encoded) - .expect("failed to decode prep share") - }), - )? - .get_encoded(); - } else if outbound.is_empty() { - // Each Aggregator recovered an output share. - break; - } else { - panic!("Aggregators did not finish the prepare phase at the same time"); + if outbound.len() == vdaf.num_aggregators() { + // Another round is required before output shares are computed. + inbound = vdaf + .prepare_shares_to_prepare_message( + agg_param, + outbound.iter().map(|encoded| { + V::PrepareShare::get_decoded_with_param(&states[0], encoded) + .expect("failed to decode prep share") + }), + )? + .get_encoded() + .unwrap(); + } else if outbound.is_empty() { + // Each Aggregator recovered an output share. + break; + } else { + panic!("Aggregators did not finish the prepare phase at the same time"); + } } - } - Ok(out_shares) + Ok(out_shares) + } } #[cfg(test)] @@ -663,20 +662,17 @@ where for<'a> T: ParameterizedDecode<(&'a V, &'a V::AggregationParam)>, { // Generate an arbitrary vector of field elements. - let g = F::one() + F::one(); - let vec: Vec<F> = itertools::iterate(F::one(), |&v| g * v) - .take(length) - .collect(); + let vec: Vec<F> = crate::field::random_vector(length).unwrap(); // Serialize the field element vector into a vector of bytes. let mut bytes = Vec::with_capacity(vec.len() * F::ENCODED_SIZE); - encode_fieldvec(&vec, &mut bytes); + encode_fieldvec(&vec, &mut bytes).unwrap(); // Deserialize the type of interest from those bytes. let value = T::get_decoded_with_param(&(vdaf, agg_param), &bytes).unwrap(); // Round-trip the value back to a vector of bytes. - let encoded = value.get_encoded(); + let encoded = value.get_encoded().unwrap(); assert_eq!(encoded, bytes); } @@ -741,6 +737,7 @@ mod tests { } #[cfg(feature = "test-util")] +#[cfg_attr(docsrs, doc(cfg(feature = "test-util")))] pub mod dummy; #[cfg(all(feature = "crypto-dependencies", feature = "experimental"))] #[cfg_attr( @@ -748,10 +745,14 @@ pub mod dummy; doc(cfg(all(feature = "crypto-dependencies", feature = "experimental"))) )] pub mod poplar1; -#[cfg(feature = "prio2")] -#[cfg_attr(docsrs, doc(cfg(feature = "prio2")))] +#[cfg(all(feature = "crypto-dependencies", feature = "experimental"))] +#[cfg_attr( + docsrs, + doc(cfg(all(feature = "crypto-dependencies", feature = "experimental"))) +)] pub mod prio2; pub mod prio3; -#[cfg(test)] -mod prio3_test; +#[cfg(any(test, feature = "test-util"))] +#[cfg_attr(docsrs, doc(cfg(feature = "test-util")))] +pub mod prio3_test; pub mod xof; |