star_sharks/
share_ff.rs

1use alloc::vec::*;
2use core::convert::TryFrom;
3use core::convert::TryInto;
4
5#[cfg(feature = "fuzzing")]
6use arbitrary::{Arbitrary, Unstructured};
7
8#[cfg(feature = "zeroize_memory")]
9use zeroize::Zeroize;
10
11use crate::ff::*;
12
13pub const FIELD_ELEMENT_LEN: usize = 24;
14
15#[cfg_attr(feature = "fuzzing", derive(Arbitrary))]
16#[cfg_attr(feature = "zeroize_memory", derive(Zeroize))]
17#[derive(PrimeField)]
18// 2^128 + 12451 (https://eprint.iacr.org/2011/326)
19#[PrimeFieldModulus = "340282366920938463463374607431768223907"]
20#[PrimeFieldGenerator = "3"]
21#[PrimeFieldReprEndianness = "little"]
22pub struct Fp([u64; 3]);
23
24impl From<Fp> for Vec<u8> {
25  fn from(s: Fp) -> Vec<u8> {
26    s.to_repr().as_ref().to_vec()
27  }
28}
29
30impl From<Fp> for Vec<u64> {
31  fn from(s: Fp) -> Vec<u64> {
32    s.0.to_vec()
33  }
34}
35
36// Finds the [root of the Lagrange polynomial](https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing#Computationally_efficient_approach).
37// The expected `shares` argument format is the same as the output by the `get_evaluator´ function.
38// Where each (key, value) pair corresponds to one share, where the key is the `x` and the value is a vector of `y`,
39// where each element corresponds to one of the secret's byte chunks.
40pub fn interpolate(shares: &[Share]) -> Result<Vec<u8>, &'static str> {
41  if shares.is_empty() {
42    return Err("Need at least one share to interpolate");
43  }
44  let res: Vec<Vec<u8>> = (0..shares[0].y.len())
45    .map(|s| {
46      let e: Fp = shares
47        .iter()
48        .map(|s_i| {
49          let f: Fp = shares
50            .iter()
51            .filter(|s_j| s_j.x != s_i.x)
52            .map(|s_j| s_j.x * (s_j.x - s_i.x).invert().unwrap())
53            .fold(Fp::ONE, |acc, x| acc * x); // take product of all fractions
54          f * s_i.y[s]
55        })
56        .fold(Fp::ZERO, |acc, x| acc + x); // take sum of all field elements
57      Vec::from(e) // turn into byte vector
58    })
59    .collect();
60  Ok(
61    res
62      .iter()
63      .fold(Vec::new(), |acc, r| [acc, r.to_vec()].concat()),
64  )
65}
66
67// Generates `k` polynomial coefficients, being the last one `s` and the
68// others randomly generated in the field.
69// Coefficient degrees go from higher to lower in the returned vector
70// order.
71pub fn random_polynomial<R: rand::Rng>(s: Fp, k: u32, rng: &mut R) -> Vec<Fp> {
72  let k = k as usize;
73  let mut poly = Vec::with_capacity(k);
74  for _ in 1..k {
75    poly.push(Fp::random(&mut *rng));
76  }
77  poly.push(s);
78
79  poly
80}
81
82// Returns an iterator over the points of the `polys` polynomials passed as argument.
83// Each item of the iterator is a tuple `(x, [f_1(x), f_2(x)..])` where eaxh `f_i` is the result for the ith polynomial.
84// Each polynomial corresponds to one byte chunk of the original secret.
85pub fn get_evaluator(polys: Vec<Vec<Fp>>) -> Evaluator {
86  Evaluator { polys, x: Fp::ZERO }
87}
88
89#[derive(Debug)]
90pub struct Evaluator {
91  polys: Vec<Vec<Fp>>,
92  x: Fp,
93}
94
95impl Evaluator {
96  fn evaluate(&self, x: Fp) -> Share {
97    Share {
98      x,
99      y: self
100        .polys
101        .iter()
102        .map(|p| p.iter().fold(Fp::ZERO, |acc, c| acc * x + c))
103        .collect(),
104    }
105  }
106
107  pub fn gen<R: rand::Rng>(&self, rng: &mut R) -> Share {
108    let rand = Fp::random(rng);
109    self.evaluate(rand)
110  }
111}
112
113// Implement `Iterator` for `Evaluator`.
114// The `Iterator` trait only requires a method to be defined for the `next` element.
115impl Iterator for Evaluator {
116  type Item = Share;
117
118  fn next(&mut self) -> Option<Share> {
119    self.x += Fp::ONE;
120    Some(self.evaluate(self.x))
121  }
122}
123
124/// A share used to reconstruct the secret. Can be serialized to and from a byte array.
125#[derive(Debug, Clone, Eq, PartialEq)]
126#[cfg_attr(feature = "zeroize_memory", derive(Zeroize))]
127pub struct Share {
128  pub x: Fp,
129  pub y: Vec<Fp>,
130}
131
132/// Obtains a byte vector from a `Share` instance
133impl From<&Share> for Vec<u8> {
134  fn from(s: &Share) -> Vec<u8> {
135    let mut bytes = Vec::with_capacity((s.y.len() + 1) * FIELD_ELEMENT_LEN);
136    let repr = s.x.to_repr();
137    let x_coord = repr.as_ref().to_vec();
138    let y_coords = s
139      .y
140      .iter()
141      .map(|p| p.to_repr().as_ref().to_vec())
142      .fold(Vec::new(), |acc, r| [acc, r.to_vec()].concat());
143    bytes.extend(x_coord);
144    bytes.extend(y_coords);
145    bytes
146  }
147}
148
149/// Obtains a `Share` instance from a byte slice
150impl TryFrom<&[u8]> for Share {
151  type Error = &'static str;
152
153  fn try_from(s: &[u8]) -> Result<Share, Self::Error> {
154    if s.len() < FIELD_ELEMENT_LEN {
155      return Err(
156        "A Share must have enough bytes to represent a field element",
157      );
158    }
159    let xr = FpRepr(
160      s[..FIELD_ELEMENT_LEN]
161        .try_into()
162        // Slice into array only fails if the lengths don't match.
163        // The length we pass is fixed, so this will not panic based
164        // on the input data from the caller and unwrap is safe.
165        .expect("byte slice should be the right size for an x coordinate"),
166    );
167    let x = Option::from(Fp::from_repr(xr))
168      .ok_or("Failed to create field element from x representation")?;
169
170    let y_bytes = &s[FIELD_ELEMENT_LEN..];
171    let y_count = y_bytes.len() / FIELD_ELEMENT_LEN;
172    let mut y = Vec::with_capacity(y_count);
173    for i in 0..y_count {
174      let fr = FpRepr(
175        y_bytes[i * FIELD_ELEMENT_LEN..(i + 1) * FIELD_ELEMENT_LEN]
176          .try_into()
177          .expect("byte slice should be the right size for a y coordinate"),
178      );
179      let f = Option::from(Fp::from_repr(fr))
180        .ok_or("Failed to create field element from y representation")?;
181      y.push(f);
182    }
183    Ok(Share { x, y })
184  }
185}
186
187/// Generate a Share from arbitrary input data.
188///
189/// The derived `Arbitary` trait impl just splats data directly
190/// into the `Fp` struct without checking that it's a valid field
191/// element, which violates the invariants of the type and leads
192/// to false panic reports from the fuzzer.
193///
194/// Implement the trait directly to ensure invalid values are
195/// not passed on to further code.
196#[cfg(feature = "fuzzing")]
197impl<'a> Arbitrary<'a> for Share {
198  fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
199    let count = u.arbitrary_len::<Fp>()?;
200    Share::try_from(u.bytes(count * FIELD_ELEMENT_LEN)?)
201      .map_err(|_| arbitrary::Error::IncorrectFormat)
202  }
203}
204
205#[cfg(test)]
206mod tests {
207  use super::{get_evaluator, interpolate};
208  use super::{Fp, Share, FIELD_ELEMENT_LEN};
209  use crate::ff::Field;
210  use alloc::{vec, vec::Vec};
211  use core::convert::TryFrom;
212  use rand_chacha::rand_core::SeedableRng;
213
214  fn fp_one() -> Fp {
215    Fp::ONE
216  }
217
218  fn fp_two() -> Fp {
219    fp_one().double()
220  }
221
222  fn fp_three() -> Fp {
223    fp_two() + fp_one()
224  }
225
226  #[test]
227  fn field_addition() {
228    let x = fp_one();
229    let y = fp_two();
230    let z = fp_three();
231    assert_eq!(x + y, z);
232  }
233
234  #[test]
235  fn field_mult() {
236    let x = fp_three();
237    let y = fp_one();
238    let z = fp_three();
239    assert_eq!(Vec::from(x * y) as Vec<u8>, Vec::from(z) as Vec<u8>);
240  }
241
242  #[test]
243  fn random_polynomial() {
244    let mut rng = rand_chacha::ChaCha8Rng::from_seed([0x90; 32]);
245    let poly = super::random_polynomial(fp_one(), 3, &mut rng);
246    assert_eq!(poly.len(), 3);
247    assert_eq!(poly[2], fp_one());
248  }
249
250  #[test]
251  fn evaluation() {
252    let iter =
253      get_evaluator(vec![vec![fp_three(), fp_two(), fp_three() + fp_two()]]);
254    let values: Vec<(Fp, Vec<Fp>)> = iter.take(2).map(|s| (s.x, s.y)).collect();
255    assert_eq!(
256      values,
257      vec![
258        (fp_one(), vec![Fp([12451u64, 18446744073709427106, 0])]),
259        (fp_two(), vec![Fp([12451u64, 18446744073709290145, 0])])
260      ]
261    );
262  }
263
264  #[test]
265  fn interpolation() {
266    let mut rng = rand_chacha::ChaCha8Rng::from_seed([0x90; 32]);
267    let poly = super::random_polynomial(fp_one(), 5, &mut rng);
268    let iter = get_evaluator(vec![poly]);
269    let shares: Vec<Share> = iter.take(5).collect();
270    let root = interpolate(&shares).unwrap();
271    let mut chk = vec![0u8; FIELD_ELEMENT_LEN];
272    chk[0] = 1u8;
273    assert_eq!(root, chk);
274  }
275
276  #[test]
277  fn vec_from_share() {
278    let share = Share {
279      x: fp_one(),
280      y: vec![fp_two(), fp_three()],
281    };
282    let bytes = Vec::from(&share);
283    let chk_bytes = test_bytes();
284    assert_eq!(bytes, chk_bytes);
285  }
286
287  #[test]
288  fn share_from_u8_slice() {
289    let share = Share::try_from(&test_bytes()[..]).unwrap();
290    assert_eq!(share.x, fp_one());
291    assert_eq!(share.y, vec![fp_two(), fp_three()]);
292  }
293
294  #[test]
295  fn share_from_u8_slice_without_y() {
296    let share = Share::try_from(&test_bytes()[..FIELD_ELEMENT_LEN]).unwrap();
297    assert_eq!(share.x, fp_one());
298    assert_eq!(share.y, vec![]);
299  }
300
301  #[test]
302  fn share_from_u8_slice_partial_y() {
303    let share =
304      Share::try_from(&test_bytes()[..FIELD_ELEMENT_LEN + 20]).unwrap();
305    assert_eq!(share.x, fp_one());
306    assert_eq!(share.y, vec![]);
307    let share =
308      Share::try_from(&test_bytes()[..FIELD_ELEMENT_LEN * 2 + 12]).unwrap();
309    assert_eq!(share.x, fp_one());
310    assert_eq!(share.y, vec![fp_two()]);
311  }
312
313  #[test]
314  fn share_from_short_u8_slice() {
315    let bytes = test_bytes();
316    assert!(Share::try_from(&bytes[0..FIELD_ELEMENT_LEN - 1]).is_err());
317    assert!(Share::try_from(&bytes[0..1]).is_err());
318  }
319
320  fn test_bytes() -> Vec<u8> {
321    let suffix = vec![0u8; FIELD_ELEMENT_LEN - 1];
322    let mut bytes = vec![1u8; 1];
323    bytes.extend(suffix.clone()); // x coord
324    bytes.extend(vec![2u8; 1]);
325    bytes.extend(suffix.clone()); // y coord #1
326    bytes.extend(vec![3u8; 1]);
327    bytes.extend(suffix); // y coord #2
328    bytes
329  }
330
331  #[test]
332  fn bad_share_bytes() {
333    let bytes: Vec<u8> = vec![
334      10u8, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 10, 0, 0, 0, 0, 0, 0,
335      10, 0, 0, 0, 0, 0,
336    ];
337    let _ = Share::try_from(bytes.as_slice());
338  }
339
340  #[test]
341  fn element_length() {
342    assert_eq!(FIELD_ELEMENT_LEN, core::mem::size_of::<Fp>());
343  }
344}
star_sharks/share_ff.rs

star_sharks/
share_ff.rs
