use std::borrow::Borrow;
use std::cmp::Ordering;
use std::fmt::{self, Debug, Formatter};
use std::hash::{Hash, Hasher};
use std::mem::size_of_val;
use std::{cmp, iter, ops};
use pairing::ff::Field;
use pairing::{CurveAffine, CurveProjective};
use rand::Rng;
use rand04_compat::RngExt;
use serde::{Deserialize, Serialize};
use super::super::error::{Error, Result};
use super::cmp_pairing::cmp_projective;
use super::into_fr::IntoFr;
use super::secret::{clear_fr, ContainsSecret, MemRange, Safe};
use super::{Fr, G1Affine, G1};
#[derive(Serialize, Deserialize, PartialEq, Eq)]
pub struct Poly {
#[serde(with = "super::serde_impl::field_vec")]
pub(super) coeff: Vec<Fr>,
}
impl Clone for Poly {
fn clone(&self) -> Self {
Poly::from(self.coeff.clone())
}
}
impl Debug for Poly {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
f.debug_struct("Poly").field("coeff", &"...").finish()
}
}
#[allow(clippy::suspicious_op_assign_impl)]
impl<B: Borrow<Poly>> ops::AddAssign<B> for Poly {
fn add_assign(&mut self, rhs: B) {
let len = self.coeff.len();
let rhs_len = rhs.borrow().coeff.len();
if rhs_len > len {
self.coeff.resize(rhs_len, Fr::zero());
}
for (self_c, rhs_c) in self.coeff.iter_mut().zip(&rhs.borrow().coeff) {
Field::add_assign(self_c, rhs_c);
}
self.remove_zeros();
}
}
impl<'a, B: Borrow<Poly>> ops::Add<B> for &'a Poly {
type Output = Poly;
fn add(self, rhs: B) -> Poly {
(*self).clone() + rhs
}
}
impl<B: Borrow<Poly>> ops::Add<B> for Poly {
type Output = Poly;
fn add(mut self, rhs: B) -> Poly {
self += rhs;
self
}
}
impl<'a> ops::Add<Fr> for Poly {
type Output = Poly;
fn add(mut self, rhs: Fr) -> Self::Output {
if self.is_zero() && !rhs.is_zero() {
self.coeff.push(rhs);
} else {
self.coeff[0].add_assign(&rhs);
self.remove_zeros();
}
self
}
}
impl<'a> ops::Add<u64> for Poly {
type Output = Poly;
fn add(self, rhs: u64) -> Self::Output {
self + rhs.into_fr()
}
}
impl<B: Borrow<Poly>> ops::SubAssign<B> for Poly {
fn sub_assign(&mut self, rhs: B) {
let len = self.coeff.len();
let rhs_len = rhs.borrow().coeff.len();
if rhs_len > len {
self.coeff.resize(rhs_len, Fr::zero());
}
for (self_c, rhs_c) in self.coeff.iter_mut().zip(&rhs.borrow().coeff) {
Field::sub_assign(self_c, rhs_c);
}
self.remove_zeros();
}
}
impl<'a, B: Borrow<Poly>> ops::Sub<B> for &'a Poly {
type Output = Poly;
fn sub(self, rhs: B) -> Poly {
(*self).clone() - rhs
}
}
impl<B: Borrow<Poly>> ops::Sub<B> for Poly {
type Output = Poly;
fn sub(mut self, rhs: B) -> Poly {
self -= rhs;
self
}
}
#[allow(clippy::suspicious_arithmetic_impl)]
impl<'a> ops::Sub<Fr> for Poly {
type Output = Poly;
fn sub(self, mut rhs: Fr) -> Self::Output {
rhs.negate();
self + rhs
}
}
impl<'a> ops::Sub<u64> for Poly {
type Output = Poly;
fn sub(self, rhs: u64) -> Self::Output {
self - rhs.into_fr()
}
}
#[allow(clippy::suspicious_arithmetic_impl)]
impl<'a, B: Borrow<Poly>> ops::Mul<B> for &'a Poly {
type Output = Poly;
fn mul(self, rhs: B) -> Self::Output {
let rhs = rhs.borrow();
if rhs.is_zero() || self.is_zero() {
return Poly::zero();
}
let n_coeffs = self.coeff.len() + rhs.coeff.len() - 1;
let mut coeffs = vec![Fr::zero(); n_coeffs];
let mut tmp = Safe::new(Box::new(Fr::zero()));
for (i, ca) in self.coeff.iter().enumerate() {
for (j, cb) in rhs.coeff.iter().enumerate() {
*tmp = *ca;
tmp.mul_assign(cb);
coeffs[i + j].add_assign(&*tmp);
}
}
Poly::from(coeffs)
}
}
impl<B: Borrow<Poly>> ops::Mul<B> for Poly {
type Output = Poly;
fn mul(self, rhs: B) -> Self::Output {
&self * rhs
}
}
impl<B: Borrow<Self>> ops::MulAssign<B> for Poly {
fn mul_assign(&mut self, rhs: B) {
*self = &*self * rhs;
}
}
impl ops::MulAssign<Fr> for Poly {
fn mul_assign(&mut self, rhs: Fr) {
if rhs.is_zero() {
self.zero_secret();
self.coeff.clear();
} else {
for c in &mut self.coeff {
Field::mul_assign(c, &rhs);
}
}
}
}
impl<'a> ops::Mul<&'a Fr> for Poly {
type Output = Poly;
fn mul(mut self, rhs: &Fr) -> Self::Output {
if rhs.is_zero() {
self.zero_secret();
self.coeff.clear();
} else {
self.coeff.iter_mut().for_each(|c| c.mul_assign(rhs));
}
self
}
}
impl ops::Mul<Fr> for Poly {
type Output = Poly;
fn mul(self, rhs: Fr) -> Self::Output {
let rhs = &rhs;
self * rhs
}
}
impl<'a> ops::Mul<&'a Fr> for &'a Poly {
type Output = Poly;
fn mul(self, rhs: &Fr) -> Self::Output {
(*self).clone() * rhs
}
}
impl<'a> ops::Mul<Fr> for &'a Poly {
type Output = Poly;
fn mul(self, rhs: Fr) -> Self::Output {
(*self).clone() * rhs
}
}
impl ops::Mul<u64> for Poly {
type Output = Poly;
fn mul(self, rhs: u64) -> Self::Output {
self * rhs.into_fr()
}
}
impl Drop for Poly {
fn drop(&mut self) {
self.zero_secret();
}
}
impl From<Vec<Fr>> for Poly {
fn from(coeff: Vec<Fr>) -> Self {
Poly { coeff }
}
}
impl ContainsSecret for Poly {
fn secret_memory(&self) -> MemRange {
let ptr = self.coeff.as_ptr() as *mut u8;
let n_bytes = size_of_val(self.coeff.as_slice());
MemRange { ptr, n_bytes }
}
}
impl Poly {
pub fn random<R: Rng>(degree: usize, rng: &mut R) -> Self {
Poly::try_random(degree, rng)
.unwrap_or_else(|e| panic!("Failed to create random `Poly`: {}", e))
}
pub fn try_random<R: Rng>(degree: usize, rng: &mut R) -> Result<Self> {
if degree == usize::max_value() {
return Err(Error::DegreeTooHigh);
}
let coeff: Vec<Fr> = rng.gen_iter04().take(degree + 1).collect();
Ok(Poly::from(coeff))
}
pub fn zero() -> Self {
Poly { coeff: vec![] }
}
pub fn is_zero(&self) -> bool {
self.coeff.iter().all(|coeff| coeff.is_zero())
}
pub fn one() -> Self {
Poly::constant(Fr::one())
}
pub fn constant(c: Fr) -> Self {
let fr_ptr = &c as *const Fr;
let poly = Poly::from(vec![c]);
clear_fr(fr_ptr);
poly
}
pub fn identity() -> Self {
Poly::monomial(1)
}
pub fn monomial(degree: usize) -> Self {
let coeff: Vec<Fr> = iter::repeat(Fr::zero())
.take(degree)
.chain(iter::once(Fr::one()))
.collect();
Poly::from(coeff)
}
pub fn interpolate<T, U, I>(samples_repr: I) -> Self
where
I: IntoIterator<Item = (T, U)>,
T: IntoFr,
U: IntoFr,
{
let convert = |(x, y): (T, U)| (x.into_fr(), y.into_fr());
let samples: Vec<(Fr, Fr)> = samples_repr.into_iter().map(convert).collect();
Poly::compute_interpolation(&samples)
}
pub fn degree(&self) -> usize {
self.coeff.len().saturating_sub(1)
}
pub fn evaluate<T: IntoFr>(&self, i: T) -> Fr {
let mut result = match self.coeff.last() {
None => return Fr::zero(),
Some(c) => *c,
};
let x = i.into_fr();
for c in self.coeff.iter().rev().skip(1) {
result.mul_assign(&x);
result.add_assign(c);
}
result
}
pub fn commitment(&self) -> Commitment {
let to_g1 = |c: &Fr| G1Affine::one().mul(*c);
Commitment {
coeff: self.coeff.iter().map(to_g1).collect(),
}
}
fn remove_zeros(&mut self) {
let zeros = self.coeff.iter().rev().take_while(|c| c.is_zero()).count();
let len = self.coeff.len() - zeros;
self.coeff.truncate(len);
}
fn compute_interpolation(samples: &[(Fr, Fr)]) -> Self {
if samples.is_empty() {
return Poly::zero();
}
let mut poly = Poly::constant(samples[0].1);
let mut minus_s0 = samples[0].0;
minus_s0.negate();
let mut base = Poly::from(vec![minus_s0, Fr::one()]);
for (ref x, ref y) in &samples[1..] {
let mut diff = *y;
diff.sub_assign(&poly.evaluate(x));
let base_val = base.evaluate(x);
diff.mul_assign(&base_val.inverse().expect("sample points must be distinct"));
base *= diff;
poly += &base;
let mut minus_x = *x;
minus_x.negate();
base *= Poly::from(vec![minus_x, Fr::one()]);
}
poly
}
pub fn reveal(&self) -> String {
format!("Poly {{ coeff: {:?} }}", self.coeff)
}
}
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
pub struct Commitment {
#[serde(with = "super::serde_impl::projective_vec")]
pub(super) coeff: Vec<G1>,
}
impl PartialOrd for Commitment {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(&other))
}
}
impl Ord for Commitment {
fn cmp(&self, other: &Self) -> Ordering {
self.coeff.len().cmp(&other.coeff.len()).then_with(|| {
self.coeff
.iter()
.zip(&other.coeff)
.find(|(x, y)| x != y)
.map_or(Ordering::Equal, |(x, y)| cmp_projective(x, y))
})
}
}
impl Hash for Commitment {
fn hash<H: Hasher>(&self, state: &mut H) {
self.coeff.len().hash(state);
for c in &self.coeff {
c.into_affine().into_compressed().as_ref().hash(state);
}
}
}
impl<B: Borrow<Commitment>> ops::AddAssign<B> for Commitment {
fn add_assign(&mut self, rhs: B) {
let len = cmp::max(self.coeff.len(), rhs.borrow().coeff.len());
self.coeff.resize(len, G1::zero());
for (self_c, rhs_c) in self.coeff.iter_mut().zip(&rhs.borrow().coeff) {
self_c.add_assign(rhs_c);
}
self.remove_zeros();
}
}
impl<'a, B: Borrow<Commitment>> ops::Add<B> for &'a Commitment {
type Output = Commitment;
fn add(self, rhs: B) -> Commitment {
(*self).clone() + rhs
}
}
impl<B: Borrow<Commitment>> ops::Add<B> for Commitment {
type Output = Commitment;
fn add(mut self, rhs: B) -> Commitment {
self += rhs;
self
}
}
impl Commitment {
pub fn degree(&self) -> usize {
self.coeff.len() - 1
}
pub fn evaluate<T: IntoFr>(&self, i: T) -> G1 {
let mut result = match self.coeff.last() {
None => return G1::zero(),
Some(c) => *c,
};
let x = i.into_fr();
for c in self.coeff.iter().rev().skip(1) {
result.mul_assign(x);
result.add_assign(c);
}
result
}
fn remove_zeros(&mut self) {
let zeros = self.coeff.iter().rev().take_while(|c| c.is_zero()).count();
let len = self.coeff.len() - zeros;
self.coeff.truncate(len)
}
}
pub struct BivarPoly {
degree: usize,
coeff: Vec<Fr>,
}
impl Clone for BivarPoly {
fn clone(&self) -> Self {
BivarPoly {
degree: self.degree,
coeff: self.coeff.clone(),
}
}
}
impl Drop for BivarPoly {
fn drop(&mut self) {
self.zero_secret();
}
}
impl Debug for BivarPoly {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
f.debug_struct("BivarPoly")
.field("degree", &self.degree)
.field("coeff", &"...")
.finish()
}
}
impl ContainsSecret for BivarPoly {
fn secret_memory(&self) -> MemRange {
let ptr = self.coeff.as_ptr() as *const Fr as *mut u8;
let n_bytes = size_of_val(self.coeff.as_slice());
MemRange { ptr, n_bytes }
}
}
impl BivarPoly {
pub fn random<R: Rng>(degree: usize, rng: &mut R) -> Self {
BivarPoly::try_random(degree, rng).unwrap_or_else(|e| {
panic!(
"Failed to create random `BivarPoly` of degree {}: {}",
degree, e
)
})
}
pub fn try_random<R: Rng>(degree: usize, rng: &mut R) -> Result<Self> {
let len = coeff_pos(degree, degree)
.and_then(|l| l.checked_add(1))
.ok_or(Error::DegreeTooHigh)?;
let poly = BivarPoly {
degree,
coeff: rng.gen_iter04().take(len).collect(),
};
Ok(poly)
}
pub fn degree(&self) -> usize {
self.degree
}
pub fn evaluate<T: IntoFr>(&self, x: T, y: T) -> Fr {
let x_pow = self.powers(x);
let y_pow = self.powers(y);
let mut result = Fr::zero();
for (i, x_pow_i) in x_pow.into_iter().enumerate() {
for (j, y_pow_j) in y_pow.iter().enumerate() {
let index = coeff_pos(i, j).expect("polynomial degree too high");
let mut summand = self.coeff[index];
summand.mul_assign(&x_pow_i);
summand.mul_assign(y_pow_j);
result.add_assign(&summand);
}
}
result
}
pub fn row<T: IntoFr>(&self, x: T) -> Poly {
let x_pow = self.powers(x);
let coeff: Vec<Fr> = (0..=self.degree)
.map(|i| {
let mut result = Fr::zero();
for (j, x_pow_j) in x_pow.iter().enumerate() {
let index = coeff_pos(i, j).expect("polynomial degree too high");
let mut summand = self.coeff[index];
summand.mul_assign(x_pow_j);
result.add_assign(&summand);
}
result
})
.collect();
Poly::from(coeff)
}
pub fn commitment(&self) -> BivarCommitment {
let to_pub = |c: &Fr| G1Affine::one().mul(*c);
BivarCommitment {
degree: self.degree,
coeff: self.coeff.iter().map(to_pub).collect(),
}
}
fn powers<T: IntoFr>(&self, x: T) -> Vec<Fr> {
powers(x, self.degree)
}
pub fn reveal(&self) -> String {
format!(
"BivarPoly {{ degree: {}, coeff: {:?} }}",
self.degree, self.coeff
)
}
}
#[derive(Debug, Clone, Eq, PartialEq)]
pub struct BivarCommitment {
pub(crate) degree: usize,
pub(crate) coeff: Vec<G1>,
}
impl Hash for BivarCommitment {
fn hash<H: Hasher>(&self, state: &mut H) {
self.degree.hash(state);
for c in &self.coeff {
c.into_affine().into_compressed().as_ref().hash(state);
}
}
}
impl PartialOrd for BivarCommitment {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(&other))
}
}
impl Ord for BivarCommitment {
fn cmp(&self, other: &Self) -> Ordering {
self.degree.cmp(&other.degree).then_with(|| {
self.coeff
.iter()
.zip(&other.coeff)
.find(|(x, y)| x != y)
.map_or(Ordering::Equal, |(x, y)| cmp_projective(x, y))
})
}
}
impl BivarCommitment {
pub fn degree(&self) -> usize {
self.degree
}
pub fn evaluate<T: IntoFr>(&self, x: T, y: T) -> G1 {
let x_pow = self.powers(x);
let y_pow = self.powers(y);
let mut result = G1::zero();
for (i, x_pow_i) in x_pow.into_iter().enumerate() {
for (j, y_pow_j) in y_pow.iter().enumerate() {
let index = coeff_pos(i, j).expect("polynomial degree too high");
let mut summand = self.coeff[index];
summand.mul_assign(x_pow_i);
summand.mul_assign(*y_pow_j);
result.add_assign(&summand);
}
}
result
}
pub fn row<T: IntoFr>(&self, x: T) -> Commitment {
let x_pow = self.powers(x);
let coeff: Vec<G1> = (0..=self.degree)
.map(|i| {
let mut result = G1::zero();
for (j, x_pow_j) in x_pow.iter().enumerate() {
let index = coeff_pos(i, j).expect("polynomial degree too high");
let mut summand = self.coeff[index];
summand.mul_assign(*x_pow_j);
result.add_assign(&summand);
}
result
})
.collect();
Commitment { coeff }
}
fn powers<T: IntoFr>(&self, x: T) -> Vec<Fr> {
powers(x, self.degree)
}
}
fn powers<T: IntoFr>(into_x: T, degree: usize) -> Vec<Fr> {
let x = into_x.into_fr();
let mut x_pow_i = Fr::one();
iter::once(x_pow_i)
.chain((0..degree).map(|_| {
x_pow_i.mul_assign(&x);
x_pow_i
}))
.collect()
}
pub(crate) fn coeff_pos(i: usize, j: usize) -> Option<usize> {
let (j, i) = if j >= i { (j, i) } else { (i, j) };
i.checked_add(j.checked_mul(j.checked_add(1)?)? / 2)
}
#[cfg(test)]
mod tests {
use std::collections::BTreeMap;
use super::{coeff_pos, BivarPoly, IntoFr, Poly};
use super::{Fr, G1Affine};
use pairing::ff::Field;
use pairing::CurveAffine;
use rand;
#[test]
fn test_coeff_pos() {
let mut i = 0;
let mut j = 0;
for n in 0..100 {
assert_eq!(Some(n), coeff_pos(i, j));
if i >= j {
j += 1;
i = 0;
} else {
i += 1;
}
}
let too_large = 1 << (0usize.count_zeros() / 2);
assert_eq!(None, coeff_pos(0, too_large));
}
#[test]
fn poly() {
let x_pow_3 = Poly::monomial(3);
let x_pow_1 = Poly::monomial(1);
let poly = x_pow_3 * 5 + x_pow_1 - 2;
let coeff: Vec<_> = [-2, 1, 0, 5].iter().map(IntoFr::into_fr).collect();
assert_eq!(Poly { coeff }, poly);
let samples = vec![(-1, -8), (2, 40), (3, 136), (5, 628)];
for &(x, y) in &samples {
assert_eq!(y.into_fr(), poly.evaluate(x));
}
let interp = Poly::interpolate(samples);
assert_eq!(interp, poly);
}
#[test]
fn distributed_key_generation() {
let mut rng = rand::thread_rng();
let dealer_num = 3;
let node_num = 5;
let faulty_num = 2;
let bi_polys: Vec<BivarPoly> = (0..dealer_num)
.map(|_| BivarPoly::random(faulty_num, &mut rng))
.collect();
let pub_bi_commits: Vec<_> = bi_polys.iter().map(BivarPoly::commitment).collect();
let mut sec_keys = vec![Fr::zero(); node_num];
for (bi_poly, bi_commit) in bi_polys.iter().zip(&pub_bi_commits) {
for m in 1..=node_num {
let row_poly = bi_poly.row(m);
let row_commit = bi_commit.row(m);
assert_eq!(row_poly.commitment(), row_commit);
for s in 1..=node_num {
let val = row_poly.evaluate(s);
let val_g1 = G1Affine::one().mul(val);
assert_eq!(bi_commit.evaluate(m, s), val_g1);
assert_eq!(bi_poly.evaluate(m, s), val);
}
let x_pow_2 = Poly::monomial(2);
let five = Poly::constant(5.into_fr());
let wrong_poly = row_poly.clone() + x_pow_2 * five;
assert_ne!(wrong_poly.commitment(), row_commit);
let received: BTreeMap<_, _> = [1, 2, 4]
.iter()
.map(|&i| (i, bi_poly.evaluate(m, i)))
.collect();
let my_row = Poly::interpolate(received);
assert_eq!(bi_poly.evaluate(m, 0), my_row.evaluate(0));
assert_eq!(row_poly, my_row);
sec_keys[m - 1].add_assign(&my_row.evaluate(Fr::zero()));
}
}
let mut sec_key_set = Poly::zero();
for bi_poly in &bi_polys {
sec_key_set += bi_poly.row(0);
}
for m in 1..=node_num {
assert_eq!(sec_key_set.evaluate(m), sec_keys[m - 1]);
}
let mut sum_commit = Poly::zero().commitment();
for bi_commit in &pub_bi_commits {
sum_commit += bi_commit.row(0);
}
assert_eq!(sum_commit, sec_key_set.commitment());
}
}