use crate::blocks::VRFProof;
use crate::shim::clock::BLOCKS_PER_EPOCH;
use crate::utils::encoding::blake2b_256;
use num::{
bigint::{ParseBigIntError, Sign},
BigInt, Integer,
};
use once_cell::sync::Lazy;
use serde_tuple::{self, Deserialize_tuple, Serialize_tuple};
const PRECISION: u64 = 256;
const MAX_WIN_COUNT: i64 = 3 * BLOCKS_PER_EPOCH as i64;
fn parse(strings: &[&str]) -> Result<Vec<BigInt>, ParseBigIntError> {
strings
.iter()
.map(|s| {
let i: BigInt = s.parse()?;
Ok(i << (PRECISION - 128))
})
.collect()
}
static EXP_NUM_COEF: Lazy<Vec<BigInt>> = Lazy::new(|| {
parse(&[
"-648770010757830093818553637600",
"67469480939593786226847644286976",
"-3197587544499098424029388939001856",
"89244641121992890118377641805348864",
"-1579656163641440567800982336819953664",
"17685496037279256458459817590917169152",
"-115682590513835356866803355398940131328",
"340282366920938463463374607431768211456",
])
.unwrap()
});
static EXP_DENO_COEF: Lazy<Vec<BigInt>> = Lazy::new(|| {
parse(&[
"1225524182432722209606361",
"114095592300906098243859450",
"5665570424063336070530214243",
"194450132448609991765137938448",
"5068267641632683791026134915072",
"104716890604972796896895427629056",
"1748338658439454459487681798864896",
"23704654329841312470660182937960448",
"259380097567996910282699886670381056",
"2250336698853390384720606936038375424",
"14978272436876548034486263159246028800",
"72144088983913131323343765784380833792",
"224599776407103106596571252037123047424",
"340282366920938463463374607431768211456",
])
.unwrap()
});
fn expneg(x: &BigInt) -> BigInt {
let num = poly_val(&EXP_NUM_COEF, x);
let deno = poly_val(&EXP_DENO_COEF, x);
(num << PRECISION).div_floor(&deno)
}
fn poly_val(poly: &[BigInt], x: &BigInt) -> BigInt {
let mut poly_iter = poly.iter();
let mut res = poly_iter.next().cloned().unwrap_or_default();
for coeff in poly_iter {
res = ((res * x) >> PRECISION) + coeff;
}
res
}
#[inline]
fn lambda(power: &BigInt, total_power: &BigInt) -> BigInt {
((power * BLOCKS_PER_EPOCH) << PRECISION).div_floor(total_power)
}
struct Poiss {
lam: BigInt,
pmf: BigInt,
icdf: BigInt,
k: u64,
}
impl Poiss {
fn new(lambda: BigInt) -> Self {
let pmf = expneg(&lambda);
let icdf = (BigInt::from(1) << PRECISION) - &pmf;
Self {
lam: lambda,
pmf,
icdf,
k: 0,
}
}
fn next(&mut self) -> &BigInt {
self.k += 1;
self.pmf = self.pmf.div_floor(&BigInt::from(self.k));
self.pmf = (&self.pmf * &self.lam) >> PRECISION;
self.icdf -= &self.pmf;
&self.icdf
}
}
#[derive(
Clone, Debug, PartialEq, PartialOrd, Eq, Default, Ord, Serialize_tuple, Deserialize_tuple, Hash,
)]
pub struct ElectionProof {
pub win_count: i64,
pub vrfproof: VRFProof,
}
impl ElectionProof {
pub fn compute_win_count(&self, power: &BigInt, total_power: &BigInt) -> i64 {
let h = blake2b_256(self.vrfproof.as_bytes());
let lhs = BigInt::from_bytes_be(Sign::Plus, &h);
let lam = lambda(power, total_power);
let mut p = Poiss::new(lam);
let mut rhs = &p.icdf;
let mut j: i64 = 0;
while &lhs < rhs && j < MAX_WIN_COUNT {
rhs = p.next();
j += 1;
}
j
}
}
#[cfg(test)]
impl quickcheck::Arbitrary for ElectionProof {
fn arbitrary(g: &mut quickcheck::Gen) -> Self {
let fmt_str = format!("===={}=====", u64::arbitrary(g));
let vrfproof = VRFProof::new(fmt_str.into_bytes());
Self {
win_count: i64::arbitrary(g),
vrfproof,
}
}
}