Basic implementation of RSA Accumulator in rust

rust_rsa_accumulator.rs

// [dependencies]
// blake2b_simd = "1.0.1"
// num-bigint = "0.4.3"
// num-integer = "0.1.45"
// num-prime = { version = "0.4.3", features=["num-bigint"] }
// num-traits = "0.2.15"

use blake2b_simd;
use num_bigint::{BigInt, BigUint, Sign};
use num_integer::Integer;
use num_traits::{Num, One, Signed, Zero};
use std::ops::{Div, MulAssign, Rem, RemAssign};

/// Primality test
fn is_prime(n: &BigUint) -> bool {
    num_prime::nt_funcs::is_prime(n, None).probably()
}

/// Do a Blake2b hash and return result.
#[inline(always)]
fn blake2<const N: usize>(data: &[u8]) -> [u8; N] {
    blake2b_simd::Params::new()
        .hash_length(N)
        .hash(data)
        .as_bytes()
        .try_into()
        .expect("slice is always the necessary length")
}

/// Deterministically hash bytes to prime
fn hash_to_prime(data: &[u8]) -> BigUint {
    let mut hash: [u8; 32] = blake2(data);
    let mut num = BigUint::from_bytes_le(&hash);
    loop {
        if is_prime(&num) {
            return num;
        }
        hash = blake2(&hash);
        num = BigUint::from_bytes_le(&hash);
    }
}

pub fn bezoute_coefficients(a: &BigUint, b: &BigUint) -> (BigInt, BigInt) {
    let a = BigInt::from_biguint(Sign::Plus, a.clone());
    let b = BigInt::from_biguint(Sign::Plus, b.clone());
    let gcd = a.extended_gcd(&b);
    (gcd.x, gcd.y)
}

/// Calculate the modular inverse of `g`.
#[inline]
pub fn mod_inverse(g: &BigUint, n: &BigUint) -> Option<BigUint> {
    let g = BigInt::from_biguint(Sign::Plus, g.clone());
    let n = BigInt::from_biguint(Sign::Plus, n.clone());

    let gcd = g.extended_gcd(&n);

    if !gcd.gcd.is_one() {
        return None;
    }

    let x = if gcd.x.is_negative() {
        gcd.x + n
    } else {
        gcd.x
    };

    let (_, x) = x.into_parts(); // Convert BigInt to BigUint
    Some(x)
}

/// Digest (or accumulator) of a set
pub struct RsaDigest {
    acc: BigUint,
}

/// Proof that an element is in the accumulator set
pub struct MembershipProof<E: AsRef<[u8]>> {
    proof: BigUint,
    members: Vec<E>,
}

/// Proof that an element is not in the accumulator set
pub struct NonMembershipProof<E: AsRef<[u8]>> {
    d: BigUint,
    b: BigInt,
    element: E,
}

pub struct RsaAccumulatorProver {
    a0: BigUint,
    inverse_a0: BigUint,
    n: BigUint,
    product: BigUint,
}

impl RsaAccumulatorProver {
    pub fn new(a0: BigUint, n: BigUint) -> Result<Self, &'static str> {
        let Some(inverse_a0) = mod_inverse(&a0, &n) else {
            return Err("a0 and n must be coprimes");
        };
        Ok(Self {
            a0,
            inverse_a0,
            n,
            product: BigUint::one(),
        })
    }

    /// Returns `true` if the RSA set contains the prime value.
    fn contains_prime(&mut self, prime: &BigUint) -> bool {
        (&self.product).rem(prime).is_zero()
    }

    /// Returns `true` if the RSA set contains a value.
    pub fn contains<E: AsRef<[u8]>>(&mut self, element: E) -> bool {
        let prime = hash_to_prime(element.as_ref());
        self.contains_prime(&prime)
    }

    /// Adds a value to the RSA set.
    ///
    /// Returns whether the value was newly inserted. That is:
    ///
    /// - If the set did not previously contain this value, `true` is returned.
    /// - If the set already contained this value, `false` is returned.
    pub fn insert<E: AsRef<[u8]>>(&mut self, element: E) -> bool {
        let prime = hash_to_prime(element.as_ref());
        if self.contains_prime(&prime) {
            return false;
        }
        self.product.mul_assign(&prime);
        true
    }

    /// Removes a value from the set. Returns whether the value was
    /// present in the set.
    pub fn remove<E: AsRef<[u8]>>(&mut self, element: E) -> bool {
        let prime = hash_to_prime(element.as_ref());
        let (result, remainder) = (&self.product).div_rem(&prime);
        if !remainder.is_zero() {
            return false;
        }
        self.product = result;
        true
    }

    pub fn prove_membership<E: AsRef<[u8]>>(&self, members: Vec<E>) -> MembershipProof<E> {
        let primes_product = members
            .iter()
            .map(|e| hash_to_prime(e.as_ref()))
            .fold(BigUint::one(), |product, next| product * next);
        let exponent = (&self.product).div(&primes_product);
        MembershipProof {
            proof: self.a0.modpow(&exponent, &self.n),
            members,
        }
    }

    pub fn prove_non_membership<E: AsRef<[u8]>>(&self, element: E) -> NonMembershipProof<E> {
        let prime = hash_to_prime(element.as_ref());
        let (a, b) = bezoute_coefficients(&prime, &self.product);
        let d = match a.into_parts() {
            (Sign::Minus, positive_a) => self.inverse_a0.modpow(&positive_a, &self.n),
            (_, positive_a) => self.a0.modpow(&positive_a, &self.n),
        };

        NonMembershipProof { d, b, element }
    }

    pub fn digest(&self) -> RsaDigest {
        RsaDigest {
            acc: self.a0.modpow(&self.product, &self.n),
        }
    }
}

pub struct RsaAccumulatorVerifier {
    a0: BigUint,
    n: BigUint,
}

impl RsaAccumulatorVerifier {
    pub fn new(a0: BigUint, n: BigUint) -> Self {
        Self { a0, n }
    }

    pub fn verify_membership<E: AsRef<[u8]>>(
        &self,
        proof: &MembershipProof<E>,
        digest: &RsaDigest,
    ) -> bool {
        let product = proof
            .members
            .iter()
            .map(|e| hash_to_prime(e.as_ref()))
            .fold(BigUint::one(), |mut acc, next| {
                acc.mul_assign(&next);
                acc
            });
        let result = proof.proof.modpow(&product, &self.n);
        result.eq(&digest.acc)
    }

    pub fn verify_non_membership<E: AsRef<[u8]>>(
        &self,
        proof: &NonMembershipProof<E>,
        digest: &RsaDigest,
    ) -> bool {
        let prime = hash_to_prime(proof.element.as_ref());
        let second_power = match (proof.b.sign(), proof.b.magnitude()) {
            (Sign::Minus, positive_b) => {
                let Some(inverse_digest) = mod_inverse(&digest.acc, &self.n) else {
                    return false;
                };
                inverse_digest.modpow(positive_b, &self.n)
            }
            (_, positive_b) => digest.acc.modpow(positive_b, &self.n),
        };
        let mut result = proof.d.modpow(&prime, &self.n);
        result.mul_assign(&second_power);
        result.rem_assign(&self.n);
        result == self.a0
    }
}

impl From<&RsaAccumulatorProver> for RsaAccumulatorVerifier {
    fn from(prover: &RsaAccumulatorProver) -> Self {
        Self::new(prover.a0.clone(), prover.n.clone())
    }
}

fn main() {
    // Using a public known RSA instance with 2048bits from:
    // - https://rsa.cash/bounty-instances (Challenge 3 instance)
    // obs: RSA Accumulators can be build in a trustless setup using an different group
    let n = BigUint::from_str_radix("7efce54e174bb141d000b4375659f45ac1e3e9ccc1afcde85cc98b7b6ce626457361e90d1d9fe0af72ba63f3b0d20af8084bd6f981584af1e9197288811e72afaf488a1360e4d5d6f9b08220e16dd05860bd571e3171eb10dcc60241bf6f64cf03ddfb0556aa9a61e9850874e442564c020cf283813f5215d36281748b766ffa8a3486cd70686b5590d499a1a72d9baa87c0dc223c8f5b71d18fd24888b2872f0530be8cde0f7be8f591848bc210f2966dcaab6853d09bfd550ebdcd244c394cc83ac19ec75bf8b82774719555483cc2e3fbac3201c1aa518d25fdb37d50e56f3515ad5e4609d252fa7ded3b5123c0abc8a0ce137ef9989843d1452b87ccca6b", 16).unwrap();
    let a0 = BigUint::from(65537u32);

    // Create a prover and verifier
    let mut prover = RsaAccumulatorProver::new(a0, n).unwrap();
    let verifier = RsaAccumulatorVerifier::from(&prover);

    // Insert elements in the RSA Accumulator Set
    prover.insert("event 01");
    prover.insert("event 02");
    prover.insert("event 03");
    prover.insert("event 04");

    // Calculate the digest
    let digest = prover.digest();

    // Create and verify membership proof
    let membership_proof = prover.prove_membership(vec!["event 01", "event 02"]);

    // Verify the proof
    if verifier.verify_membership(&membership_proof, &digest) {
        println!(
            "Valid proof: The elements {:?} are in the set.",
            membership_proof.members
        );
    } else {
        println!("Invalid membership proof");
    }

    // Create non-membership proof
    let non_membership_proof = prover.prove_non_membership("event 05");

    // Verify non-membership proof
    if verifier.verify_non_membership(&non_membership_proof, &digest) {
        println!(
            "Valid proof: Element \"{}\" is not in the set.",
            non_membership_proof.element
        );
    } else {
        println!("Invalid non-membership proof");
    }
}