use byteorder::LittleEndian;
use byteorder::WriteBytesExt;
use digest::Digest;
use serde::Deserialize;
use serde::Serialize;
use thiserror::Error;
extern crate alloc;
use alloc::vec;
use core::fmt::{Debug, Display, Formatter};
use std::collections::HashMap;
use crate::encoding::BinaryMarshaler;
use crate::encoding::MarshallingError;
use crate::group::HashFactory;
use crate::{cipher::Stream, Group, Point, Scalar};
type ScalarMap<GROUP> = HashMap<usize, <<GROUP as Group>::POINT as Point>::SCALAR>;
type PointMap<GROUP> = HashMap<usize, <GROUP as Group>::POINT>;
#[derive(Copy, Clone, Eq, PartialEq, Default, Serialize, Deserialize)]
pub struct PriShare<SCALAR> {
pub i: usize,
pub v: SCALAR,
}
impl<SCALAR: Scalar> Debug for PriShare<SCALAR> {
fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
f.debug_struct("PriShare").field("i", &self.i).finish()
}
}
impl<SCALAR: Scalar> Display for PriShare<SCALAR> {
fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
write!(f, "PriShare( index: {} )", self.i)
}
}
impl<SCALAR: Scalar> PriShare<SCALAR> {
pub fn hash<HASHFACTORY: HashFactory>(&self, s: HASHFACTORY) -> Result<Vec<u8>, PolyError> {
let mut h = s.hash();
self.v.marshal_to(&mut h)?;
h.write_u32::<LittleEndian>(self.i as u32)?;
Ok(h.finalize().to_vec())
}
}
#[derive(Clone, Default, Serialize, Deserialize, Eq, PartialEq)]
pub struct PriPoly<GROUP: Group> {
pub g: GROUP,
pub(crate) coeffs: Vec<<GROUP::POINT as Point>::SCALAR>,
}
impl<GROUP: Group> Debug for PriPoly<GROUP> {
fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
f.debug_struct("PriPoly").field("g", &self.g).finish()
}
}
impl<GROUP: Group> Display for PriPoly<GROUP> {
fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
write!(f, "PriPoly( group: {} )", self.g)
}
}
pub fn new_pri_poly<GROUP: Group, STREAM>(
group: GROUP,
t: usize,
s: Option<<GROUP::POINT as Point>::SCALAR>,
mut rand: STREAM,
) -> PriPoly<GROUP>
where
STREAM: Stream,
{
let mut coeffs: Vec<<GROUP::POINT as Point>::SCALAR> = vec![];
coeffs.push(match s {
Some(v) => v,
None => group.scalar().pick(&mut rand),
});
for _ in 1..t {
coeffs.push(group.scalar().pick(&mut rand));
}
PriPoly { g: group, coeffs }
}
pub fn coefficients_to_pri_poly<GROUP: Group>(
g: &GROUP,
coeffs: &[<GROUP::POINT as Point>::SCALAR],
) -> PriPoly<GROUP> {
PriPoly {
g: g.clone(),
coeffs: coeffs.to_vec(),
}
}
impl<GROUP: Group> PriPoly<GROUP> {
pub fn threshold(&self) -> usize {
self.coeffs.len()
}
pub fn secret(&self) -> <GROUP::POINT as Point>::SCALAR {
self.coeffs[0].clone()
}
pub fn eval(&self, i: usize) -> PriShare<<GROUP::POINT as Point>::SCALAR> {
let xi = self.g.scalar().set_int64(1 + i as i64);
let mut v = self.g.scalar().zero();
for j in (0..self.threshold()).rev() {
v = v * xi.clone();
v = v + self.coeffs[j].clone();
}
PriShare { i, v }
}
pub fn shares(&self, n: usize) -> Vec<Option<PriShare<<GROUP::POINT as Point>::SCALAR>>> {
let mut shares = Vec::with_capacity(n);
for i in 0..n {
shares.push(Some(self.eval(i)));
}
shares
}
pub fn add(&self, q: &PriPoly<GROUP>) -> Result<PriPoly<GROUP>, PolyError> {
if self.g.to_string() != q.g.to_string() {
return Err(PolyError::NoGroupsMatch);
}
if self.threshold() != q.threshold() {
return Err(PolyError::WrongCoefficientsNumber);
}
let mut coeffs = Vec::with_capacity(self.threshold());
for i in 0..self.threshold() {
coeffs.push(self.coeffs[i].clone() + q.coeffs[i].clone());
}
Ok(PriPoly {
g: self.g.clone(),
coeffs,
})
}
pub fn equal(&self, q: &PriPoly<GROUP>) -> Result<bool, PolyError> {
if self.g.to_string() != q.g.to_string() {
return Ok(false);
}
if self.coeffs.len() != q.coeffs.len() {
return Ok(false);
}
let mut b = true;
for i in 0..self.threshold() {
let pb = self.coeffs[i].marshal_binary()?;
let qb = q.coeffs[i].marshal_binary()?;
b &= pb.eq(&qb);
}
Ok(b)
}
pub fn commit(&self, b: Option<&GROUP::POINT>) -> PubPoly<GROUP> {
let mut commits = vec![];
for i in 0..self.threshold() {
commits.push(self.g.point().mul(&self.coeffs[i], b));
}
PubPoly {
g: self.g.clone(),
b: b.cloned(),
commits,
}
}
pub fn mul(&self, q: &Self) -> Self {
let d1 = self.coeffs.len() - 1;
let d2 = q.coeffs.len() - 1;
let new_degree = d1 + d2;
let mut coeffs = Vec::with_capacity(new_degree + 1);
for _ in 0..new_degree + 1 {
coeffs.push(self.g.scalar().zero());
}
for (i, cp) in self.coeffs.iter().enumerate() {
for (j, cq) in q.coeffs.iter().enumerate() {
let mut tmp = cp.clone();
tmp = tmp * cq.clone();
coeffs[i + j] = coeffs[i + j].clone() + tmp;
}
}
PriPoly {
g: self.g.clone(),
coeffs,
}
}
pub fn coefficients(&self) -> Vec<<GROUP::POINT as Point>::SCALAR> {
self.coeffs.clone()
}
}
pub fn recover_secret<GROUP: Group>(
g: GROUP,
shares: &[Option<PriShare<<GROUP::POINT as Point>::SCALAR>>],
t: usize,
n: usize,
) -> Result<<GROUP::POINT as Point>::SCALAR, PolyError> {
let (x, y) = xy_scalar(&g, shares, t, n);
if x.len() < t {
return Err(PolyError::NotEnoughSharesForSecret);
}
let mut acc = g.scalar().zero();
let mut num = g.scalar();
let mut den = g.scalar();
let mut tmp = g.scalar();
for (i, xi) in x.iter() {
let yi = &y[i];
num = num.set(yi);
den = den.one();
for (j, xj) in x.iter() {
if i == j {
continue;
}
num = num * xj.clone();
tmp = tmp.sub(xj, xi);
den = den * tmp.clone();
}
let num_clone = num.clone();
num = num.div(&num_clone, &den);
acc = acc + num.clone();
}
Ok(acc)
}
fn xy_scalar<GROUP: Group>(
g: &GROUP,
shares: &[Option<PriShare<<GROUP::POINT as Point>::SCALAR>>],
t: usize,
n: usize,
) -> (ScalarMap<GROUP>, ScalarMap<GROUP>) {
let mut sorted = Vec::with_capacity(n);
shares.iter().for_each(|share| {
if let Some(share) = share {
sorted.push(share);
}
});
sorted.sort_by(|i, j| i.i.cmp(&j.i));
let mut x = HashMap::new();
let mut y = HashMap::new();
for s in sorted {
let idx = s.i;
x.insert(idx, g.scalar().set_int64((idx + 1) as i64));
y.insert(idx, s.v.clone());
if x.len() == t {
break;
}
}
(x, y)
}
fn minus_const<GROUP: Group>(g: &GROUP, c: <GROUP::POINT as Point>::SCALAR) -> PriPoly<GROUP> {
let neg = g.scalar().neg(&c);
PriPoly {
g: g.clone(),
coeffs: vec![neg, g.scalar().one()],
}
}
pub fn recover_pri_poly<GROUP: Group>(
g: &GROUP,
shares: &[Option<PriShare<<GROUP::POINT as Point>::SCALAR>>],
t: usize,
n: usize,
) -> Result<PriPoly<GROUP>, PolyError> {
let (x, y) = xy_scalar(g, shares, t, n);
if x.len() != t {
return Err(PolyError::NotEnoughSharesForPublic);
}
let mut acc_poly = PriPoly {
g: g.clone(),
coeffs: vec![],
};
for j in x.keys() {
let mut basis = lagrange_basis(g, *j, x.clone());
for (i, _) in basis.coeffs.clone().iter().enumerate() {
basis.coeffs[i] = basis.coeffs[i].clone() * y[j].clone();
}
if acc_poly.coeffs.is_empty() {
acc_poly = basis;
continue;
}
acc_poly = acc_poly.add(&basis)?;
}
Ok(acc_poly)
}
impl<GROUP: Group> PriPoly<GROUP> {
pub fn string(&self) -> String {
let mut strs = Vec::with_capacity(self.coeffs.len());
for c in self.coeffs.clone() {
strs.push(format!("{c}"));
}
"[ ".to_string() + &strs.join(", ") + " ]"
}
}
#[derive(Clone, Copy, Default, Debug, Serialize, Deserialize, Eq, PartialEq)]
pub struct PubShare<POINT: Point> {
pub i: usize,
#[serde(deserialize_with = "POINT::deserialize")]
pub v: POINT,
}
impl<POINT: Point> Display for PubShare<POINT> {
fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
write!(f, "PubShare( index: {}, value: {} )", self.i, self.v)
}
}
impl<POINT: Point> PubShare<POINT> {
pub fn hash<HASHFACTORY: HashFactory>(&self, s: HASHFACTORY) -> Result<Vec<u8>, PolyError> {
let mut h = s.hash();
self.v.marshal_to(&mut h)?;
h.write_u32::<LittleEndian>(self.i as u32)?;
Ok(h.finalize().to_vec())
}
}
#[derive(Clone, Eq, PartialEq, Debug, Default, Serialize, Deserialize)]
pub struct PubPoly<GROUP: Group> {
g: GROUP,
b: Option<GROUP::POINT>,
commits: Vec<GROUP::POINT>,
}
impl<GROUP: Group> Display for PubPoly<GROUP> {
fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
write!(f, "PubPoly( group: {},", self.g,)?;
write!(f, " base_point:")?;
match self.b {
Some(ref base) => write!(f, " Some({}),", base),
None => write!(f, " None,"),
}?;
write!(f, " commits: [")?;
let commits = self
.commits
.iter()
.map(|c| c.to_string())
.collect::<Vec<_>>()
.join(", ");
write!(f, "{}] )", commits)
}
}
impl<GROUP: Group> PubPoly<GROUP> {
pub fn new(g: &GROUP, b: Option<GROUP::POINT>, commits: &[GROUP::POINT]) -> PubPoly<GROUP> {
PubPoly {
g: g.clone(),
b,
commits: commits.to_vec(),
}
}
}
impl<GROUP: Group> PubPoly<GROUP> {
pub fn info(&self) -> (Option<GROUP::POINT>, Vec<GROUP::POINT>) {
(self.b.clone(), self.commits.clone())
}
pub fn threshold(&self) -> usize {
self.commits.len()
}
pub fn commit(&self) -> GROUP::POINT {
self.commits[0].clone()
}
pub fn eval(&self, i: usize) -> PubShare<GROUP::POINT> {
let xi = self.g.scalar().set_int64(1 + (i as i64));
let mut v = self.g.point();
v = v.null();
for j in (0..=(self.threshold() - 1)).rev() {
let v_clone = v.clone();
v = v.mul(&xi, Some(&v_clone));
let v_clone = v.clone();
v = v.add(&v_clone, &self.commits[j]);
}
PubShare { i, v }
}
pub fn shares(&self, n: usize) -> Vec<Option<PubShare<GROUP::POINT>>> {
let mut shares = Vec::with_capacity(n);
for i in 0..n {
shares.push(Some(self.eval(i)));
}
shares
}
pub fn add(&self, q: &Self) -> Result<Self, PolyError> {
if self.g.to_string() != q.g.to_string() {
return Err(PolyError::NoGroupsMatch);
}
if self.threshold() != q.threshold() {
return Err(PolyError::WrongCoefficientsNumber);
}
let mut commits = vec![];
for i in 0..self.threshold() {
commits.push(self.g.point().add(&self.commits[i], &q.commits[i]));
}
Ok(PubPoly {
g: self.g.clone(),
b: self.b.clone(),
commits,
})
}
pub fn equal(&self, q: &PubPoly<GROUP>) -> Result<bool, PolyError> {
if self.g.to_string() != q.g.to_string() {
return Ok(false);
}
let mut b = true;
for i in 0..self.threshold() {
let pb = self.commits[i].marshal_binary()?;
let qb = q.commits[i].marshal_binary()?;
b &= pb.eq(&qb);
}
Ok(b)
}
pub fn check(&self, s: &PriShare<<GROUP::POINT as Point>::SCALAR>) -> bool {
let pv = self.eval(s.i);
let ps = self.g.point().mul(&s.v, self.b.as_ref());
pv.v.eq(&ps)
}
}
pub fn xy_commit<GROUP: Group>(
g: &GROUP,
shares: &[Option<PubShare<GROUP::POINT>>],
t: usize,
n: usize,
) -> (ScalarMap<GROUP>, PointMap<GROUP>) {
let mut sorted = Vec::with_capacity(n);
shares.iter().for_each(|share| {
if let Some(share) = share {
sorted.push(share);
}
});
sorted.sort_by(|i, j| i.i.cmp(&j.i));
let mut x = HashMap::new();
let mut y = HashMap::new();
for s in sorted {
let idx = s.i;
x.insert(idx, g.scalar().set_int64((idx + 1) as i64));
y.insert(idx, s.v.clone());
if x.len() == t {
break;
}
}
(x, y)
}
pub fn recover_commit<GROUP: Group>(
g: GROUP,
shares: &[Option<PubShare<GROUP::POINT>>],
t: usize,
n: usize,
) -> Result<GROUP::POINT, PolyError> {
let (x, y) = xy_commit(&g, shares, t, n);
if x.len() < t {
return Err(PolyError::NotEnoughtGoodPublics);
}
let mut num = g.scalar();
let mut den = g.scalar();
let mut tmp = g.scalar();
let mut acc = g.point().null();
let mut tmp_p = g.point();
for (i, xi) in x.iter() {
num = num.one();
den = den.one();
for (j, xj) in x.iter() {
if i == j {
continue;
}
num = num * xj.clone();
tmp = tmp.sub(xj, xi);
den = den * tmp.clone();
}
let num_clone = num.clone();
num = num.div(&num_clone, &den);
tmp_p = tmp_p.mul(&num, Some(&y[i]));
let acc_clone = acc.clone();
acc = acc.add(&acc_clone, &tmp_p);
}
Ok(acc)
}
pub fn recover_pub_poly<GROUP: Group>(
g: GROUP,
shares: &[Option<PubShare<GROUP::POINT>>],
t: usize,
n: usize,
) -> Result<PubPoly<GROUP>, PolyError> {
let (x, y) = xy_commit(&g, shares, t, n);
if x.len() < t {
return Err(PolyError::NotEnoughtGoodPublics);
}
let mut acc_poly = PubPoly::new(&g, None, &[]);
for (j, _) in x.iter().enumerate() {
let basis = lagrange_basis(&g, j, x.clone());
let tmp = basis.commit(Some(&y[&j]));
if acc_poly.commits.is_empty() {
acc_poly = tmp;
continue;
}
acc_poly = acc_poly.add(&tmp)?;
}
Ok(acc_poly)
}
fn lagrange_basis<GROUP: Group>(
g: &GROUP,
i: usize,
xs: HashMap<usize, <GROUP::POINT as Point>::SCALAR>,
) -> PriPoly<GROUP> {
let mut basis = PriPoly {
g: g.clone(),
coeffs: vec![g.clone().scalar().one()],
};
let mut den = g.scalar().one();
let mut acc = g.scalar().one();
for (m, xm) in xs.iter() {
if &i == m {
continue;
}
basis = basis.mul(&minus_const(g, xm.clone()));
den = den.sub(&xs[&i], xm); let den_clone = den.clone();
den = den.inv(&den_clone); acc = acc * den.clone(); }
for (i, _) in basis.coeffs.clone().iter().enumerate() {
basis.coeffs[i] = basis.coeffs[i].clone() * acc.clone();
}
basis
}
#[derive(Error, Debug)]
pub enum PolyError {
#[error("marshalling error")]
MarshallingError(#[from] MarshallingError),
#[error("io error")]
IoError(#[from] std::io::Error),
#[error("not enough good public shares to reconstruct secret commitment")]
NotEnoughtGoodPublics,
#[error("non-matching groups")]
NoGroupsMatch,
#[error("different number of coefficients")]
WrongCoefficientsNumber,
#[error("not enough shares to recover private polynomial")]
NotEnoughSharesForPublic,
#[error("not enough shares to recover secret")]
NotEnoughSharesForSecret,
}