Proof (of knowledge) of exponentiation

1. Proof of exponentiation

Proof of exponentiation是基于adaptive root assumption（充分必要条件）的。 特别适合当 x x x很大时，计算 r = x m o d l , u r r=x\ mod\ l,\ u^r r=x mod l, ur将大量节约verifier直接计算 u x u^x ux的时间。

借助Fiat-Shamir heuristic，可将上面的交互式PoE转化为NI-PoE： 对应在https://github.com/dignifiedquire/rust-accumulators/blob/master/src/proofs.rs中的实现为：

/// NI-PoE Prove
/// Assumes `u^x = w`
/// All operations are `mod n`.
pub fn ni_poe_prove(x: &BigUint, u: &BigUint, w: &BigUint, n: &BigUint) -> ExponentProof {
    debug_assert!(&u.modpow(x, n) == w, "invalid input");

    // l <- H_prime(x, u, w)
    let mut to_hash = x.to_bytes_be();
    to_hash.extend(&u.to_bytes_be());
    to_hash.extend(&w.to_bytes_be());

    let l = hash_prime::<_, Blake2b>(&to_hash);

    // q <- floor(x/l)
    let q = x.div_floor(&l);

    //Prover sends Q <- u^q ∈ G to the Verifier.
    u.modpow(&q, n)
}

/// NI-PoE Verify
/// Assumes `u^x = w`
/// All operations are `mod n`.
pub fn ni_poe_verify(
    x: &BigUint,
    u: &BigUint,
    w: &BigUint,
    q: &ExponentProof,
    n: &BigUint,
) -> bool {
    // l <- H_prime(x, u, w)
    let mut to_hash = x.to_bytes_be();
    to_hash.extend(&u.to_bytes_be());
    to_hash.extend(&w.to_bytes_be());

    let l = hash_prime::<_, Blake2b>(&to_hash);

    // r <- x mod l
    let r = x.mod_floor(&l);

    // Q^l u^r == w
    &((q.modpow(&l, &n) * &u.modpow(&r, &n)) % n) == w
}

// 基于hash值来获取prime数值。
// When the proofs are made non-interactive, using the
// Fiat-Shamir heuristic the challenge is generated by hashing the previous transcript

/// Hash the given numbers to a prime number.
/// Currently uses only 128bits.
pub fn hash_prime