Repository: cloudflare/daphne
Pull request #636 (2024-07-08 20:15:30)

pine:  Represent norm bound as integer rather than float
Partially addresses #618.

Change the type of the `norm_bound` parameter of `Pine::new()` from `f64` and `u64`. The caller is expected to compute this as `b * 2^frac_bits`, where `b: 64` is the real-valued, L2-norm bound.

All parties must agree on the algorithm used to derive Pine's internal parameters from `norm_bound` parameter. Representing it this way is intended to the complexity of this algorithm.


Patch:
diff --git a/crates/daphne/src/pine/flp.rs b/crates/daphne/src/pine/flp.rs
index c0ea024..a79a41a 100644
--- a/crates/daphne/src/pine/flp.rs
+++ b/crates/daphne/src/pine/flp.rs
@@ -502,7 +502,7 @@ mod tests {
     use rand::prelude::*;
     use std::iter;
 
-    use crate::pine::Pine;
+    use crate::pine::{norm_bound_f64_to_u64, Pine};
 
     use super::*;
 
@@ -510,7 +510,8 @@ mod tests {
     fn encode_gradient() {
         let dimension = 10;
         let frac_bits = 4;
-        let pine = Pine::new_128(100.0, dimension, frac_bits, 4).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(100.0, frac_bits);
+        let pine = Pine::new_128(norm_bound, dimension, frac_bits, 4).unwrap();
 
         // We use whole numbers here so that we can test gradient decoding without losing any
         // precision.
@@ -551,7 +552,8 @@ mod tests {
     #[test]
     fn encode_wr_tests() {
         let mut rng = thread_rng();
-        let pine = Pine::new_128(10.0, 10, 15, 4).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(10.0, 15);
+        let pine = Pine::new_128(norm_bound, 10, 15, 4).unwrap();
         let gradient = iter::repeat_with(|| rng.gen_range(-0.1..0.1)).take(10);
 
         let (input, wr_test_results) = pine
@@ -597,28 +599,32 @@ mod tests {
     #[test]
     fn valid() {
         const DIM: usize = 1000;
-        let pine = Pine::new_128(1000.0, DIM, 15, 27).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(1000.0, 15);
+        let pine = Pine::new_128(norm_bound, DIM, 15, 27).unwrap();
         pine.run_valid_test_case((0..DIM).map(|i| i as f64 * 0.01));
     }
 
     #[test]
     fn valid_small_dimension() {
         const DIM: usize = 1;
-        let pine = Pine::new_128(1.0, DIM, 15, 4).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(1.0, 15);
+        let pine = Pine::new_128(norm_bound, DIM, 15, 4).unwrap();
         pine.run_valid_test_case([0.75].into_iter());
     }
 
     #[test]
     fn valid_negative_values() {
         const DIM: usize = 1337;
-        let pine = Pine::new_128(1000.0, DIM, 15, 4).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(1000.0, 15);
+        let pine = Pine::new_128(norm_bound, DIM, 15, 4).unwrap();
         pine.run_valid_test_case((0..DIM).map(|i| i as f64 * -0.01));
     }
 
     #[test]
     fn valid_random_values() {
         const DIM: usize = 1000;
-        let pine = Pine::new_128(100.0, DIM, 15, 99).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(100.0, 15);
+        let pine = Pine::new_128(norm_bound, DIM, 15, 99).unwrap();
         let mut rng = thread_rng();
         pine.run_valid_test_case(iter::repeat_with(|| rng.gen_range(-0.1..0.1)).take(DIM));
     }
@@ -626,7 +632,8 @@ mod tests {
     #[test]
     fn invalid_mutated_gradient() {
         const DIM: usize = 10;
-        let pine = Pine::new_128(100.0, DIM, 15, 4).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(100.0, 15);
+        let pine = Pine::new_128(norm_bound, DIM, 15, 4).unwrap();
         let (mut input, wr_test_results) = pine
             .flp
             .encode_with_wr_joint_rand([0.0; DIM].into_iter(), &Seed::generate().unwrap())
@@ -642,7 +649,8 @@ mod tests {
     #[test]
     fn invalid_mutated_sq_norm() {
         const DIM: usize = 10;
-        let pine = Pine::new_128(100.0, DIM, 15, 4).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(100.0, 15);
+        let pine = Pine::new_128(norm_bound, DIM, 15, 4).unwrap();
         let (mut input, wr_test_results) = pine
             .flp
             .encode_with_wr_joint_rand([0.0; DIM].into_iter(), &Seed::generate().unwrap())
@@ -662,7 +670,8 @@ mod tests {
     #[test]
     fn invalid_mutated_wr_result() {
         const DIM: usize = 10;
-        let pine = Pine::new_128(100.0, DIM, 15, 4).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(100.0, 15);
+        let pine = Pine::new_128(norm_bound, DIM, 15, 4).unwrap();
         let (mut input, wr_test_results) = pine
             .flp
             .encode_with_wr_joint_rand([0.0; DIM].into_iter(), &Seed::generate().unwrap())
@@ -683,7 +692,8 @@ mod tests {
     #[test]
     fn invalid_mutated_success_bit() {
         const DIM: usize = 10;
-        let pine = Pine::new_128(100.0, DIM, 15, 4).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(100.0, 15);
+        let pine = Pine::new_128(norm_bound, DIM, 15, 4).unwrap();
         let (mut input, wr_test_results) = pine
             .flp
             .encode_with_wr_joint_rand([0.0; DIM].into_iter(), &Seed::generate().unwrap())
@@ -705,7 +715,8 @@ mod tests {
     #[test]
     fn invalid_dot_prod_mismatch() {
         const DIM: usize = 10;
-        let pine = Pine::new_128(100.0, DIM, 15, 4).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(100.0, 15);
+        let pine = Pine::new_128(norm_bound, DIM, 15, 4).unwrap();
         let (mut input, wr_test_results) = pine
             .flp
             .encode_with_wr_joint_rand([0.1; DIM].into_iter(), &Seed::generate().unwrap())
diff --git a/crates/daphne/src/pine/mod.rs b/crates/daphne/src/pine/mod.rs
index cd14de1..1468ba6 100644
--- a/crates/daphne/src/pine/mod.rs
+++ b/crates/daphne/src/pine/mod.rs
@@ -48,7 +48,7 @@ pub type Pine128 = Pine<Field128>;
 impl Pine128 {
     /// Construct an instance of [`Pine128`] with the provided parameters.
     pub fn new_128(
-        norm_bound: f64,
+        norm_bound: u64,
         dimension: usize,
         frac_bits: usize,
         chunk_len: usize,
@@ -62,7 +62,7 @@ pub type Pine64 = Pine<Field64>;
 impl Pine64 {
     /// Construct an instance of [`Pine64`] with the provided parameters.
     pub fn new_64(
-        norm_bound: f64,
+        norm_bound: u64,
         dimension: usize,
         frac_bits: usize,
         chunk_len: usize,
@@ -106,7 +106,9 @@ impl<F: FftFriendlyFieldElement> Pine<F> {
     ///
     /// # Parameters
     ///
-    /// * `norm_bound`: Maximum L2-norm of each gradient
+    /// * `norm_bound`: Maximum L2-norm of each gradient, encoded as follows. Let `b: f64` denote
+    /// the desired L2-norm bound. We expect this parameter to be computed by multiplying `b` by
+    /// `2^frac_bits`, taking the floor, and converting to an integer.
     ///
     /// * `dimension`: Length of each gradient
     ///
@@ -120,13 +122,30 @@ impl<F: FftFriendlyFieldElement> Pine<F> {
     ///
     /// * `algorithm_id`: The VDAF algorithm ID.
     pub(crate) fn new(
-        norm_bound: f64,
+        norm_bound: u64,
         dimension: usize,
         frac_bits: usize,
         chunk_len: usize,
         num_proofs: u8,
         algorithm_id: u32,
     ) -> Result<Self, VdafError> {
+        if norm_bound == 0
+            || F::Integer::try_from(usize::try_from(norm_bound).map_err(|e| {
+                VdafError::Uncategorized(format!(
+                    "init failed: error while converting norm bound to usize: {e}"
+                ))
+            })?)
+            .map_err(|e| {
+                VdafError::Uncategorized(format!(
+                    "init failed: error while converting norm bound to field integer: {e}"
+                ))
+            })? > F::modulus() >> 1
+        {
+            return Err(VdafError::Uncategorized(
+                "init failed: norm bound must be positive".into(),
+            ));
+        }
+
         // 24 is the largest number of fractional bits that we know we can support.
         if frac_bits > 24 {
             return Err(VdafError::Uncategorized(
@@ -134,60 +153,45 @@ impl<F: FftFriendlyFieldElement> Pine<F> {
             ));
         }
 
-        let two_to_frac_bits = f64::from(1 << frac_bits);
-
         if dimension == 0 {
             return Err(VdafError::Uncategorized(
                 "init failed: 0-dimension inputs are invalid".into(),
             ));
         }
 
-        if norm_bound <= 0_f64 {
+        if frac_bits > 128 {
             return Err(VdafError::Uncategorized(
-                "init failed: norm bound must be positive".into(),
+                "init failed: number of fractional bits must not exceed 128".into(),
             ));
         }
 
-        if frac_bits > 128 {
+        let Some(sq_norm_bound_int) = norm_bound.checked_mul(norm_bound) else {
             return Err(VdafError::Uncategorized(
-                "init failed: number of fractional bits must not exceed 128".into(),
+                "init failed: squared norm is too large for u64".into(),
             ));
-        }
+        };
 
         let (sq_norm_bound, sq_norm_bits) = {
-            let norm_bound = f64_to_field(norm_bound, two_to_frac_bits)?;
-            let sq_norm_bound = norm_bound * norm_bound;
-
-            // Check if the square wraps around the field modulus.
-            if F::Integer::from(sq_norm_bound) < F::Integer::from(norm_bound) {
-                return Err(VdafError::Uncategorized(
-                    "init failed: squared norm bound exceeds field modulus".into(),
-                ));
-            }
-
-            let sq_norm_bound_int: u64 =
-                F::Integer::from(sq_norm_bound).try_into().map_err(|e| {
-                    VdafError::Uncategorized(format!(
-                        "init failed: failed to convert squared norm bound to u64: {e}"
-                    ))
-                })?;
             let sq_norm_bits = bits(sq_norm_bound_int);
+            let sq_norm_bound = usize::try_from(sq_norm_bound_int).map_err(|e| {
+                VdafError::Uncategorized(format!(
+                    "init failed: failed to convert squared norm bound to usize: {e}"
+                ))
+            })?;
+            let sq_norm_bound = F::Integer::try_from(sq_norm_bound).map_err(|e| {
+                VdafError::Uncategorized(format!(
+                    "init failed: failed to convert squared norm bound to field integer: {e}"
+                ))
+            })?;
+            let sq_norm_bound = F::from(sq_norm_bound);
             (sq_norm_bound, sq_norm_bits)
         };
 
         let (wr_test_bound, wr_test_bits) = {
-            let norm_bound_int: u64 = F::Integer::from(f64_to_field(norm_bound, two_to_frac_bits)?)
-                .try_into()
-                .map_err(|e| {
-                    VdafError::Uncategorized(format!(
-                        "init failed: failed to convert norm bound to u64: {e}"
-                    ))
-                })?;
-
             #[allow(clippy::cast_possible_truncation)]
             #[allow(clippy::cast_sign_loss)]
             let wr_test_bound_int =
-                (((norm_bound_int as f64) * ALPHA).ceil() as u64 + 1).next_power_of_two();
+                (((norm_bound as f64) * ALPHA).ceil() as u64 + 1).next_power_of_two();
             let wr_test_bits = bits(2 * wr_test_bound_int - 1);
             let wr_test_bound = usize::try_from(wr_test_bound_int).map_err(|e| {
                 VdafError::Uncategorized(format!(
@@ -309,6 +313,15 @@ fn chunk_count(chunk_length: usize, length: usize) -> usize {
     (length + chunk_length - 1) / chunk_length
 }
 
+#[cfg(test)]
+fn norm_bound_f64_to_u64(norm_bound: f64, frac_bits: usize) -> u64 {
+    let two_to_frac_bits = f64::from(1 << frac_bits);
+    let norm_bound = norm_bound * two_to_frac_bits;
+    let norm_bound = norm_bound.floor();
+    let norm_bound = norm_bound as u64;
+    norm_bound
+}
+
 pub mod flp;
 pub mod msg;
 #[cfg(test)]
@@ -533,7 +546,7 @@ mod tests {
             },
         ] {
             let pine = Pine::new_128(
-                t.norm_bound,
+                norm_bound_f64_to_u64(t.norm_bound, t.frac_bits),
                 10, // not used by test
                 t.frac_bits,
                 1, // not used by tests
diff --git a/crates/daphne/src/pine/vdaf.rs b/crates/daphne/src/pine/vdaf.rs
index b5970c3..39519e6 100644
--- a/crates/daphne/src/pine/vdaf.rs
+++ b/crates/daphne/src/pine/vdaf.rs
@@ -594,14 +594,15 @@ mod tests {
         },
     };
 
-    use crate::pine::{msg, vdaf::PineVec, Pine};
+    use crate::pine::{msg, norm_bound_f64_to_u64, vdaf::PineVec, Pine};
 
     use assert_matches::assert_matches;
 
     #[test]
     fn run_128() {
         let dimension = 100;
-        let pine = Pine::new_128(1000.0, dimension, 15, 4).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(1000.0, 15);
+        let pine = Pine::new_128(norm_bound, dimension, 15, 4).unwrap();
         let result = run_vdaf(
             &pine,
             &(),
@@ -620,7 +621,8 @@ mod tests {
     #[test]
     fn run_64() {
         let dimension = 100;
-        let pine = Pine::new_64(1000.0, dimension, 15, 100).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(1000.0, 15);
+        let pine = Pine::new_64(norm_bound, dimension, 15, 100).unwrap();
         let result = run_vdaf(
             &pine,
             &(),
@@ -641,7 +643,8 @@ mod tests {
     fn aggregate() {
         let dimension = 100;
         let reports = 5;
-        let pine = Pine::new_128(1000.0, dimension, 15, 100).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(1000.0, 15);
+        let pine = Pine::new_128(norm_bound, dimension, 15, 100).unwrap();
 
         let mut out_shares_0 = Vec::new();
         let mut out_shares_1 = Vec::new();
@@ -674,7 +677,8 @@ mod tests {
     #[test]
     fn prep_failure_mutated_pub_share_wr_joint_rand() {
         let dimension = 100;
-        let pine = Pine::new_128(1000.0, dimension, 15, 4).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(1000.0, 15);
+        let pine = Pine::new_128(norm_bound, dimension, 15, 4).unwrap();
 
         let nonce = [0; 16];
         let (mut public_share, input_shares) = pine.shard(&vec![1.0; dimension], &nonce).unwrap();
@@ -693,7 +697,8 @@ mod tests {
     #[test]
     fn prep_failure_mutated_pub_share_vf_joint_rand() {
         let dimension = 100;
-        let pine = Pine::new_128(1000.0, dimension, 15, 4).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(1000.0, 15);
+        let pine = Pine::new_128(norm_bound, dimension, 15, 4).unwrap();
 
         let nonce = [0; 16];
         let (mut public_share, input_shares) = pine.shard(&vec![1.0; dimension], &nonce).unwrap();
@@ -712,7 +717,8 @@ mod tests {
     #[test]
     fn prep_failure_mutated_input_share_proof() {
         let dimension = 100;
-        let pine = Pine::new_128(1000.0, dimension, 15, 4).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(1000.0, 15);
+        let pine = Pine::new_128(norm_bound, dimension, 15, 4).unwrap();
 
         let nonce = [0; 16];
         let (public_share, mut input_shares) = pine.shard(&vec![1.0; dimension], &nonce).unwrap();
@@ -731,7 +737,8 @@ mod tests {
     #[test]
     fn prep_failure_mutated_input_share_meas() {
         let dimension = 100;
-        let pine = Pine::new_128(1000.0, dimension, 15, 4).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(1000.0, 15);
+        let pine = Pine::new_128(norm_bound, dimension, 15, 4).unwrap();
 
         let nonce = [0; 16];
         let (public_share, mut input_shares) = pine.shard(&vec![1.0; dimension], &nonce).unwrap();
diff --git a/crates/daphne/src/vdaf/pine.rs b/crates/daphne/src/vdaf/pine.rs
index 3c24e6e..29c5371 100644
--- a/crates/daphne/src/vdaf/pine.rs
+++ b/crates/daphne/src/vdaf/pine.rs
@@ -15,56 +15,17 @@ use prio::{codec::ParameterizedDecode, field::FftFriendlyFieldElement, vdaf::Agg
 use serde::{Deserialize, Serialize};
 
 /// [Pine](crate::pine::Pine) parameters.
-#[derive(Clone, Copy, Debug, Deserialize, Serialize)]
+#[derive(Clone, Copy, Debug, Deserialize, Eq, Hash, Ord, PartialEq, PartialOrd, Serialize)]
 #[serde(rename_all = "snake_case")]
 #[cfg_attr(any(test, feature = "test-utils"), derive(deepsize::DeepSizeOf))]
 pub struct PineConfig {
-    pub norm_bound: f64,
+    pub norm_bound: u64,
     pub dimension: usize,
     pub frac_bits: usize,
     pub chunk_len: usize,
     pub var: PineVariant,
 }
 
-impl PartialEq for PineConfig {
-    fn eq(&self, other: &Self) -> bool {
-        self.norm_bound.total_cmp(&other.norm_bound).is_eq()
-            && self.dimension == other.dimension
-            && self.frac_bits == other.frac_bits
-            && self.chunk_len == other.chunk_len
-            && self.var == other.var
-    }
-}
-
-impl Eq for PineConfig {}
-
-impl Ord for PineConfig {
-    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
-        self.norm_bound
-            .total_cmp(&other.norm_bound)
-            .then(self.dimension.cmp(&other.dimension))
-            .then(self.frac_bits.cmp(&other.frac_bits))
-            .then(self.chunk_len.cmp(&other.chunk_len))
-            .then(self.var.cmp(&self.var))
-    }
-}
-
-impl PartialOrd for PineConfig {
-    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
-        Some(self.cmp(other))
-    }
-}
-
-impl std::hash::Hash for PineConfig {
-    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
-        self.norm_bound.to_bits().hash(state);
-        self.dimension.hash(state);
-        self.frac_bits.hash(state);
-        self.chunk_len.hash(state);
-        self.var.hash(state);
-    }
-}
-
 impl std::fmt::Display for PineConfig {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         let PineConfig {
@@ -278,7 +239,7 @@ mod test {
     async fn roundtrip_128(version: DapVersion) {
         let mut t = AggregationJobTest::new(
             &VdafConfig::Pine(PineConfig {
-                norm_bound: 1.0,
+                norm_bound: 32_000,
                 dimension: 1_000,
                 frac_bits: 20,
                 chunk_len: 50,


Test patch:
diff --git a/crates/daphne/src/pine/test_vec/mod.rs b/crates/daphne/src/pine/test_vec/mod.rs
index b142c25..17c5720 100644
--- a/crates/daphne/src/pine/test_vec/mod.rs
+++ b/crates/daphne/src/pine/test_vec/mod.rs
@@ -176,14 +176,15 @@ impl<F: FftFriendlyFieldElement> Pine<F> {
 mod tests {
     use super::*;
 
-    use crate::pine::Pine;
+    use crate::pine::{norm_bound_f64_to_u64, Pine};
 
     #[test]
     fn run_64() {
         let test_vec =
             serde_json::from_str::<TestVec>(include_str!("00/Pine_Field64.json")).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(test_vec.l2_norm_bound, test_vec.num_frac_bits);
         Pine::new_64(
-            test_vec.l2_norm_bound,
+            norm_bound,
             test_vec.dimension,
             test_vec.num_frac_bits,
             test_vec.chunk_length,
@@ -196,8 +197,9 @@ mod tests {
     fn run_128() {
         let test_vec =
             serde_json::from_str::<TestVec>(include_str!("00/Pine_Field128.json")).unwrap();
+        let norm_bound = norm_bound_f64_to_u64(test_vec.l2_norm_bound, test_vec.num_frac_bits);
         Pine::new_128(
-            test_vec.l2_norm_bound,
+            norm_bound,
             test_vec.dimension,
             test_vec.num_frac_bits,
             test_vec.chunk_length,