ark_vrf/

ring.rs

//! # Ring VRF
//!
//! Anonymized ring VRF combining Pedersen VRF with the ring proof scheme derived
//! from [CSSV22](https://eprint.iacr.org/2022/1205). Proves that a single blinded
//! key is a member of a committed ring without revealing which one.
//!
//! This module is gated by the `ring` feature.
//!
//! ## Usage
//!
//! ```rust,ignore
//! use ark_vrf::suites::bandersnatch::*;
//! use ark_vrf::ring::Prover;
//!
//! const RING_SIZE: usize = 100;
//! let prover_key_index = 3;
//!
//! // Create a ring of public keys
//! let mut ring = (0..RING_SIZE)
//!     .map(|i| {
//!         let mut seed = [0u8; 32];
//!         seed[..8].copy_from_slice(&i.to_le_bytes());
//!         Secret::from_seed(seed).public().0
//!     })
//!     .collect::<Vec<_>>();
//! ring[prover_key_index] = public.0;
//!
//! // Initialize ring parameters
//! let ring_setup = RingSetup::from_seed(RING_SIZE, [0x42; 32]);
//! let ring_ctx = ring_setup.ring_context();
//!
//! // Proving
//! let prover_key = ring_setup.prover_key(&ring).unwrap();
//! let prover = ring_ctx.ring_prover(prover_key, prover_key_index);
//! let io = secret.vrf_io(input);
//! let proof = secret.prove(io, b"aux data", &prover);
//!
//! // Verification
//! use ark_vrf::ring::Verifier;
//! let verifier_key = ring_setup.verifier_key(&ring).unwrap();
//! let verifier = ring_ctx.ring_verifier(verifier_key);
//! let result = Public::verify(io, b"aux data", &proof, &verifier);
//!
//! // Efficient verification with commitment
//! let ring_commitment = verifier_key.commitment();
//! let reconstructed_key = ring_setup.verifier_key_from_commitment(ring_commitment);
//!
//! // Same, without the setup: the PCS verifier params are a few points,
//! // independent of ring size, and can be distributed separately.
//! let pcs_params = ring_setup.pcs_verifier_params();
//! let reconstructed_key =
//!     ark_vrf::ring::verifier_key_from_commitment::<BandersnatchSha512Ell2>(ring_commitment, pcs_params);
//! ```

use crate::*;
use ark_ec::{
    pairing::Pairing,
    twisted_edwards::{Affine as TEAffine, TECurveConfig},
};
use ark_std::ops::Range;
use pedersen::{PedersenSuite, Proof as PedersenProof};
use utils::te_sw_map::TEMapping;
use w3f_ring_proof as ring_proof;

/// Seed hashed to curve to produce [`RingSuite::ACCUMULATOR_BASE`] in built-in suites.
pub const ACCUMULATOR_BASE_SEED: &[u8] = b"ring-accumulator";

/// Seed hashed to curve to produce [`RingSuite::PADDING`] in built-in suites.
pub const PADDING_SEED: &[u8] = b"ring-padding";

/// Ring suite.
///
/// This trait provides the cryptographic primitives needed for ring VRF signatures.
/// All required bounds are expressed directly on the associated type for better ergonomics.
pub trait RingSuite:
    PedersenSuite<
    Affine: AffineRepr<BaseField: ark_ff::PrimeField, Config: TECurveConfig + Clone>
                + TEMapping<<Self::Affine as AffineRepr>::Config>,
>
{
    /// Pairing type.
    type Pairing: ark_ec::pairing::Pairing<ScalarField = BaseField<Self>>;

    /// Accumulator base.
    ///
    /// In order for the ring-proof backend to work correctly, this is required to be
    /// in the prime order subgroup.
    const ACCUMULATOR_BASE: AffinePoint<Self>;

    /// Padding point with unknown discrete log.
    const PADDING: AffinePoint<Self>;
}

/// KZG Polynomial Commitment Scheme.
pub type Kzg<S> = ring_proof::pcs::kzg::KZG<<S as RingSuite>::Pairing>;

/// KZG commitment.
pub type PcsCommitment<S> = <Kzg<S> as ring_proof::pcs::PCS<BaseField<S>>>::C;

/// KZG Polynomial Commitment Scheme parameters.
///
/// Basically powers of tau SRS.
pub type PcsParams<S> = ring_proof::pcs::kzg::urs::URS<<S as RingSuite>::Pairing>;

/// PCS parameters required by the verifier.
///
/// A few points extracted from the SRS, independent of ring size. Together
/// with a [`RingCommitment`] it is sufficient to reconstruct a
/// [`RingVerifierKey`] via [`verifier_key_from_commitment`], without access
/// to the full [`RingSetup`].
pub type PcsVerifierParams<S> = <PcsParams<S> as ring_proof::pcs::PcsParams>::RVK;

/// Polynomial Interactive Oracle Proof (IOP) parameters.
///
/// Basically all the application specific parameters required to construct and
/// verify the ring proof.
pub type PiopParams<S> = ring_proof::PiopParams<TEAffine<CurveConfig<S>>>;

/// Ring keys commitment.
pub type RingCommitment<S> = ring_proof::FixedColumnsCommitted<BaseField<S>, PcsCommitment<S>>;

/// Ring prover key.
pub type RingProverKey<S> = ring_proof::ProverKey<BaseField<S>, Kzg<S>, TEAffine<CurveConfig<S>>>;

/// Ring verifier key.
pub type RingVerifierKey<S> = ring_proof::VerifierKey<BaseField<S>, Kzg<S>>;

/// Ring prover.
pub type RingProver<S> = ring_proof::ring_prover::RingProver<BaseField<S>, Kzg<S>, CurveConfig<S>>;

/// Ring verifier.
pub type RingVerifier<S> =
    ring_proof::ring_verifier::RingVerifier<BaseField<S>, Kzg<S>, CurveConfig<S>>;

/// Multi-ring KZG batch verifier.
///
/// Accumulates ring proofs from one or more rings (sharing the same KZG SRS)
/// into a single batched pairing check.
pub type RingBatchVerifier<S> = ring_proof::multi_ring_batch_verifier::BatchVerifier<
    <S as RingSuite>::Pairing,
    ring_proof::ArkTranscript,
>;

/// Raw ring proof.
///
/// This is the primitive ring proof used in conjunction with Pedersen proof to
/// construct the actual ring vrf proof [`Proof`].
pub type RingBareProof<S> = ring_proof::RingProof<BaseField<S>, Kzg<S>>;

/// Ring VRF proof.
///
/// Two-part zero-knowledge proof with signer anonymity:
/// - `pedersen_proof`: Key commitment and VRF correctness proof
/// - `ring_proof`: Membership proof binding the commitment to the ring
///
/// Deserialization via [`CanonicalDeserialize`] includes subgroup checks for
/// curve points, so deserialized proofs are guaranteed to contain valid points.
#[derive(Clone, CanonicalSerialize, CanonicalDeserialize)]
pub struct Proof<S: RingSuite> {
    /// Pedersen VRF proof (key commitment and VRF correctness).
    pub pedersen_proof: PedersenProof<S>,
    /// Ring membership proof binding the key commitment to the ring.
    pub ring_proof: RingBareProof<S>,
}

/// Trait for types that can generate Ring VRF proofs.
pub trait Prover<S: RingSuite> {
    /// Generate a proof for the given VRF I/O pairs and additional data.
    ///
    /// Multiple I/O pairs are delinearized into a single merged pair before proving.
    fn prove(
        &self,
        ios: impl AsRef<[VrfIo<S>]>,
        ad: impl AsRef<[u8]>,
        prover: &RingProver<S>,
    ) -> Proof<S>;
}

/// Trait for entities that can verify Ring VRF proofs.
///
/// Verifies that a VRF output was correctly derived using a secret key
/// belonging to one of the ring's public keys, without revealing which one.
///
/// All curve points involved in verification (I/O pairs and proof points)
/// are assumed to be in the prime-order subgroup. This is guaranteed when
/// points are constructed through checked constructors ([`Input::from_affine`],
/// [`Output::from_affine`]) or through trusted operations like [`Input::new`]
/// (hash-to-curve) and [`Secret::vrf_io`]. Proof points are guaranteed valid
/// when deserialized via [`CanonicalDeserialize`] (which includes subgroup
/// checks) or produced by [`Prover::prove`].
///
/// Using unchecked constructors (e.g. [`Input::from_affine_unchecked`]) places
/// the burden of subgroup validation on the caller. Passing points with
/// cofactor components leads to undefined verification behavior.
pub trait Verifier<S: RingSuite> {
    /// Verify a proof for the given VRF I/O pairs and additional data.
    ///
    /// Multiple I/O pairs are delinearized into a single merged pair before verifying.
    ///
    /// Returns `Ok(())` if verification succeeds, `Err(Error::VerificationFailure)` otherwise.
    fn verify(
        ios: impl AsRef<[VrfIo<S>]>,
        ad: impl AsRef<[u8]>,
        sig: &Proof<S>,
        verifier: &RingVerifier<S>,
    ) -> Result<(), Error>;
}

impl<S: RingSuite> Prover<S> for Secret<S> {
    fn prove(
        &self,
        ios: impl AsRef<[VrfIo<S>]>,
        ad: impl AsRef<[u8]>,
        ring_prover: &RingProver<S>,
    ) -> Proof<S> {
        use pedersen::Prover as PedersenProver;
        let (pedersen_proof, secret_blinding) = <Self as PedersenProver<S>>::prove(self, ios, ad);
        let ring_proof = ring_prover.prove(secret_blinding);
        Proof {
            pedersen_proof,
            ring_proof,
        }
    }
}

impl<S: RingSuite> Verifier<S> for Public<S> {
    fn verify(
        ios: impl AsRef<[VrfIo<S>]>,
        ad: impl AsRef<[u8]>,
        proof: &Proof<S>,
        verifier: &RingVerifier<S>,
    ) -> Result<(), Error> {
        use pedersen::Verifier as PedersenVerifier;
        <Self as PedersenVerifier<S>>::verify(ios, ad, &proof.pedersen_proof)?;
        let key_commitment = proof
            .pedersen_proof
            .key_commitment()
            .into_te()
            .ok_or(Error::InvalidData)?;
        if !verifier.verify(proof.ring_proof.clone(), key_commitment) {
            return Err(Error::VerificationFailure);
        }
        Ok(())
    }
}

/// Lightweight ring proof context.
///
/// Contains only the PIOP parameters needed to construct prover and verifier
/// instances from pre-built keys, without the KZG SRS required for key generation.
///
/// Cheap to construct from a ring size alone via [`RingContext::new`], or
/// extractable from a [`RingSetup`] via [`RingSetup::ring_context`].
#[derive(Clone)]
pub struct RingContext<S: RingSuite> {
    /// PIOP parameters.
    pub piop_params: PiopParams<S>,
}

impl<S: RingSuite> RingContext<S> {
    /// Construct context for the given ring size.
    pub fn new(ring_size: usize) -> Self {
        Self::construct(ring_size, true)
    }

    /// Construct a context whose provers generate deterministic proofs.
    ///
    /// Column blinding is disabled: proofs are reproducible, thus NOT zero-knowledge,
    /// but remain valid for verifiers using a regular context for the same ring size.
    /// Useful for reproducible test vectors generation.
    pub fn new_without_blinding(ring_size: usize) -> Self {
        Self::construct(ring_size, false)
    }

    fn construct(ring_size: usize, blinding: bool) -> Self {
        let domain_size = piop_domain_size::<S>(ring_size);
        let mut domain =
            ring_proof::Domain::with_zk_rows(domain_size, ring_proof::piop::params::ZK_ROWS);
        if !blinding {
            domain = domain.without_blinding();
        }
        let piop_params = PiopParams::<S>::setup(
            domain,
            S::BLINDING_BASE
                .into_te()
                .expect("BLINDING_BASE must not be identity"),
            S::ACCUMULATOR_BASE
                .into_te()
                .expect("ACCUMULATOR_BASE must not be identity"),
            S::PADDING.into_te().expect("PADDING must not be identity"),
        );
        Self { piop_params }
    }

    /// The max ring size this context is able to handle.
    #[inline(always)]
    pub fn max_ring_size(&self) -> usize {
        self.piop_params.keyset_part_size
    }

    /// Create a prover instance for a specific position in the ring.
    pub fn ring_prover(&self, prover_key: RingProverKey<S>, key_index: usize) -> RingProver<S> {
        self.clone().into_ring_prover(prover_key, key_index)
    }

    /// Create a verifier instance from a verifier key.
    pub fn ring_verifier(&self, verifier_key: RingVerifierKey<S>) -> RingVerifier<S> {
        self.clone().into_ring_verifier(verifier_key)
    }

    /// Create a prover instance, consuming the context to avoid cloning.
    pub fn into_ring_prover(self, prover_key: RingProverKey<S>, key_index: usize) -> RingProver<S> {
        RingProver::<S>::init(
            prover_key,
            self.piop_params,
            key_index,
            ring_proof::ArkTranscript::new(S::SUITE_ID),
        )
    }

    /// Create a verifier instance, consuming the context to avoid cloning.
    pub fn into_ring_verifier(self, verifier_key: RingVerifierKey<S>) -> RingVerifier<S> {
        RingVerifier::<S>::init(
            verifier_key,
            self.piop_params,
            ring_proof::ArkTranscript::new(S::SUITE_ID),
        )
    }
}

/// Ring proof setup.
///
/// Contains the cryptographic parameters needed for ring proof key construction,
/// proving and verification:
/// - `pcs_params`: Polynomial Commitment Scheme parameters (KZG setup)
/// - `ring_ctx`: Ring context containing the PIOP parameters
#[derive(Clone)]
pub struct RingSetup<S: RingSuite> {
    /// PCS parameters.
    pub pcs_params: PcsParams<S>,
    /// Ring context (PIOP parameters).
    pub ring_ctx: RingContext<S>,
}

impl<S: RingSuite> core::ops::Deref for RingSetup<S> {
    type Target = RingContext<S>;

    fn deref(&self) -> &Self::Target {
        &self.ring_ctx
    }
}

impl<S: RingSuite> RingSetup<S> {
    /// Construct deterministic ring proof params for the given ring size.
    ///
    /// Creates parameters using a transcript-based RNG seeded with `seed`.
    pub fn from_seed(ring_size: usize, seed: [u8; 32]) -> Self {
        let mut t = S::Transcript::new(S::SUITE_ID);
        t.absorb_raw(&seed);
        let mut rng = t.to_rng();
        Self::from_rand(ring_size, &mut rng)
    }

    /// Construct random ring proof params for the given ring size.
    ///
    /// Generates a new KZG setup with sufficient degree to support the specified ring size.
    pub fn from_rand(ring_size: usize, rng: &mut impl ark_std::rand::RngCore) -> Self {
        use ring_proof::pcs::PCS;
        let max_degree = pcs_domain_size::<S>(ring_size) - 1;
        let pcs_params = Kzg::<S>::setup(max_degree, rng);
        Self::from_pcs_params(ring_size, pcs_params).expect("PCS params is correct")
    }

    /// Construct ring proof params from existing KZG setup.
    ///
    /// Truncates the setup if larger than needed, or returns an error if it is
    /// insufficient for the specified ring size.
    pub fn from_pcs_params(ring_size: usize, mut pcs_params: PcsParams<S>) -> Result<Self, Error> {
        let pcs_domain_size = pcs_domain_size::<S>(ring_size);
        if pcs_params.powers_in_g1.len() < pcs_domain_size || pcs_params.powers_in_g2.len() < 2 {
            return Err(Error::InvalidData);
        }
        // Keep only the required powers of tau
        pcs_params.powers_in_g1.truncate(pcs_domain_size);
        pcs_params.powers_in_g2.truncate(2);

        Ok(Self {
            pcs_params,
            ring_ctx: RingContext::new(ring_size),
        })
    }

    /// Create a prover key for the given ring of public keys.
    ///
    /// Returns `Error::InvalidData` if `pks` exceeds the max ring size.
    pub fn prover_key(&self, pks: &[AffinePoint<S>]) -> Result<RingProverKey<S>, Error> {
        if pks.len() > self.piop_params.keyset_part_size {
            return Err(Error::InvalidData);
        }
        let pks = TEMapping::to_te_slice(pks).ok_or(Error::InvalidData)?;
        Ok(ring_proof::index(&self.pcs_params, &self.piop_params, &pks).0)
    }

    /// Create a verifier key for the given ring of public keys.
    ///
    /// Returns `Error::InvalidData` if `pks` exceeds the max ring size.
    pub fn verifier_key(&self, pks: &[AffinePoint<S>]) -> Result<RingVerifierKey<S>, Error> {
        if pks.len() > self.piop_params.keyset_part_size {
            return Err(Error::InvalidData);
        }
        let pks = TEMapping::to_te_slice(pks).ok_or(Error::InvalidData)?;
        Ok(ring_proof::index(&self.pcs_params, &self.piop_params, &pks).1)
    }

    /// Create a verifier key from a precomputed ring commitment.
    ///
    /// The commitment can be obtained from an existing verifier key via
    /// [`RingVerifierKey::commitment`].
    pub fn verifier_key_from_commitment(
        &self,
        commitment: RingCommitment<S>,
    ) -> RingVerifierKey<S> {
        verifier_key_from_commitment::<S>(commitment, self.pcs_verifier_params())
    }

    /// Extract the PCS parameters required by the verifier.
    ///
    /// Small (a few points) and independent of ring size. Sufficient,
    /// together with a ring commitment, to reconstruct a verifier key via
    /// [`verifier_key_from_commitment`] without access to the full setup.
    pub fn pcs_verifier_params(&self) -> PcsVerifierParams<S> {
        use ring_proof::pcs::PcsParams;
        self.pcs_params.raw_vk()
    }

    /// Create a builder for incremental construction of the verifier key.
    pub fn verifier_key_builder(&self) -> (VerifierKeyBuilder<S>, RingBuilderPcsParams<S>) {
        type RingBuilderKey<S> =
            ring_proof::ring::RingBuilderKey<BaseField<S>, <S as RingSuite>::Pairing>;
        let piop_domain_size = piop_domain_size::<S>(self.piop_params.keyset_part_size);
        let builder_key = RingBuilderKey::<S>::from_srs(&self.pcs_params, piop_domain_size);
        let builder_pcs_params = RingBuilderPcsParams(builder_key.lis_in_g1);
        let builder = VerifierKeyBuilder::new(self, &builder_pcs_params);
        (builder, builder_pcs_params)
    }

    /// Get a reference to the lightweight [`RingContext`].
    pub fn ring_context(&self) -> &RingContext<S> {
        &self.ring_ctx
    }

    /// Get the padding point.
    ///
    /// This is a point of unknown dlog that can be used in place of any key during
    /// ring construction.
    #[inline(always)]
    pub const fn padding_point() -> AffinePoint<S> {
        S::PADDING
    }
}

/// Create a verifier key from a precomputed ring commitment and the PCS
/// verifier parameters.
///
/// Lightweight alternative to [`RingSetup::verifier_key_from_commitment`] for
/// verifier-only users: no SRS required. The parameters can be obtained once
/// via [`RingSetup::pcs_verifier_params`] and distributed independently.
///
/// Soundness rests on `pcs_params` matching the trusted setup the commitment
/// was produced under. Deserialization validates the points, but cannot tell
/// a legitimate setup from a malicious one: obtain the parameters from a
/// trusted source, not alongside untrusted proof data.
pub fn verifier_key_from_commitment<S: RingSuite>(
    commitment: RingCommitment<S>,
    pcs_params: PcsVerifierParams<S>,
) -> RingVerifierKey<S> {
    RingVerifierKey::<S>::from_commitment_and_kzg_vk(commitment, pcs_params)
}

impl<S: RingSuite> CanonicalSerialize for RingSetup<S> {
    fn serialize_with_mode<W: ark_serialize::Write>(
        &self,
        mut writer: W,
        compress: ark_serialize::Compress,
    ) -> Result<(), ark_serialize::SerializationError> {
        self.pcs_params.serialize_with_mode(&mut writer, compress)
    }

    fn serialized_size(&self, compress: ark_serialize::Compress) -> usize {
        self.pcs_params.serialized_size(compress)
    }
}

impl<S: RingSuite> CanonicalDeserialize for RingSetup<S> {
    fn deserialize_with_mode<R: ark_serialize::Read>(
        mut reader: R,
        compress: ark_serialize::Compress,
        validate: ark_serialize::Validate,
    ) -> Result<Self, ark_serialize::SerializationError> {
        let pcs_params = <PcsParams<S> as CanonicalDeserialize>::deserialize_with_mode(
            &mut reader,
            compress,
            validate,
        )?;
        let ring_size = max_ring_size_from_pcs_domain_size::<S>(pcs_params.powers_in_g1.len());
        Ok(Self {
            pcs_params,
            ring_ctx: RingContext::new(ring_size),
        })
    }
}

impl<S: RingSuite> ark_serialize::Valid for RingSetup<S> {
    fn check(&self) -> Result<(), ark_serialize::SerializationError> {
        self.pcs_params.check()
    }
}

/// Information required for incremental ring construction.
///
/// Basically the SRS in Lagrangian form.
/// Can be constructed via the `PcsParams::ck_with_lagrangian()` method.
#[derive(Clone, CanonicalSerialize, CanonicalDeserialize)]
pub struct RingBuilderPcsParams<S: RingSuite>(pub Vec<G1Affine<S>>);

// Under construction ring commitment.
type PartialRingCommitment<S> =
    ring_proof::ring::Ring<BaseField<S>, <S as RingSuite>::Pairing, TEAffine<CurveConfig<S>>>;

/// Builder for incremental construction of ring verifier keys.
///
/// Allows constructing a verifier key by adding public keys in batches,
/// which is useful for large rings or memory-constrained environments.
#[derive(Clone, CanonicalSerialize, CanonicalDeserialize)]
pub struct VerifierKeyBuilder<S: RingSuite> {
    partial: PartialRingCommitment<S>,
    pcs_params: PcsVerifierParams<S>,
}

/// Pairing G1 affine point type.
pub type G1Affine<S> = <<S as RingSuite>::Pairing as Pairing>::G1Affine;
/// Pairing G2 affine point type.
pub type G2Affine<S> = <<S as RingSuite>::Pairing as Pairing>::G2Affine;

/// Trait for accessing Structured Reference String entries in Lagrangian basis.
///
/// Provides access to precomputed SRS elements needed for efficient ring operations.
pub trait SrsLookup<S: RingSuite> {
    /// Look up a range of SRS elements. Returns `None` if the range is out of bounds.
    fn lookup(&self, range: Range<usize>) -> Option<Vec<G1Affine<S>>>;
}

impl<S: RingSuite, F> SrsLookup<S> for F
where
    F: Fn(Range<usize>) -> Option<Vec<G1Affine<S>>>,
{
    fn lookup(&self, range: Range<usize>) -> Option<Vec<G1Affine<S>>> {
        self(range)
    }
}

impl<S: RingSuite> SrsLookup<S> for &RingBuilderPcsParams<S> {
    fn lookup(&self, range: Range<usize>) -> Option<Vec<G1Affine<S>>> {
        if range.end > self.0.len() {
            return None;
        }
        Some(self.0[range].to_vec())
    }
}

impl<S: RingSuite> VerifierKeyBuilder<S> {
    /// Create a new empty ring verifier key builder.
    pub fn new(ring_setup: &RingSetup<S>, lookup: impl SrsLookup<S>) -> Self {
        let lookup = |range: Range<usize>| lookup.lookup(range).ok_or(());
        let pcs_params = ring_setup.pcs_verifier_params();
        let partial = PartialRingCommitment::<S>::empty(
            &ring_setup.piop_params,
            lookup,
            pcs_params.g1.into_group(),
        );
        VerifierKeyBuilder {
            partial,
            pcs_params,
        }
    }

    /// Get the number of remaining slots available in the ring.
    #[inline(always)]
    pub fn free_slots(&self) -> usize {
        self.partial.max_keys - self.partial.curr_keys
    }

    /// Get the PCS parameters required by the verifier.
    ///
    /// Same value as [`RingSetup::pcs_verifier_params`] for the setup this
    /// builder was created from.
    pub fn pcs_verifier_params(&self) -> PcsVerifierParams<S> {
        self.pcs_params.clone()
    }

    /// Add public keys to the ring being built.
    ///
    /// Returns `Err(available_slots)` if there's not enough space, or
    /// `Err(usize::MAX)` if the SRS lookup fails.
    pub fn append(
        &mut self,
        pks: &[AffinePoint<S>],
        lookup: impl SrsLookup<S>,
    ) -> Result<(), usize> {
        let avail_slots = self.free_slots();
        if avail_slots < pks.len() {
            return Err(avail_slots);
        }
        // Currently `ring-proof` backend panics if lookup fails.
        // This workaround makes lookup failures a bit less harsh.
        let segment = lookup
            .lookup(self.partial.curr_keys..self.partial.curr_keys + pks.len())
            .ok_or(usize::MAX)?;
        let lookup = |range: Range<usize>| {
            debug_assert_eq!(segment.len(), range.len());
            Ok(segment.clone())
        };
        let pks = TEMapping::to_te_slice(pks).ok_or(usize::MAX)?;
        self.partial.append(&pks, lookup);
        Ok(())
    }

    /// Complete the building process and create the verifier key.
    pub fn finalize(self) -> RingVerifierKey<S> {
        RingVerifierKey::<S>::from_ring_and_kzg_vk(&self.partial, self.pcs_params)
    }
}

type RingProofBatchItem<S> =
    ring_proof::multi_ring_batch_verifier::BatchItem<<S as RingSuite>::Pairing, CurveConfig<S>>;

/// Pre-processed data for a single ring proof awaiting batch verification.
pub struct BatchItem<S: RingSuite> {
    ring: RingProofBatchItem<S>,
    pedersen: pedersen::BatchItem<S>,
}

impl<S: RingSuite> BatchItem<S> {
    /// Prepare a proof for deferred batch verification.
    ///
    /// Performs the cheap per-proof work (hashing, transcript setup) without
    /// the expensive pairing and MSM checks. `verifier` must be the ring
    /// verifier the proof was produced against.
    ///
    /// Returns `Error::InvalidData` if the proof's key commitment cannot be
    /// converted (e.g. identity point on SW-form suites).
    pub fn new(
        verifier: &RingVerifier<S>,
        ios: impl AsRef<[VrfIo<S>]>,
        ad: impl AsRef<[u8]>,
        proof: &Proof<S>,
    ) -> Result<Self, Error> {
        let key_commitment = proof
            .pedersen_proof
            .key_commitment()
            .into_te()
            .ok_or(Error::InvalidData)?;
        let pedersen = pedersen::BatchItem::new(ios, ad, &proof.pedersen_proof);
        let ring = RingProofBatchItem::<S>::new(verifier, proof.ring_proof.clone(), key_commitment);
        Ok(Self { ring, pedersen })
    }
}

/// Batch verifier for ring VRF proofs.
///
/// Collects ring proofs from one or more rings (sharing the same KZG SRS)
/// and verifies them together, amortizing the cost of pairing checks and
/// multi-scalar multiplications.
///
/// The same subgroup membership assumptions as [`Verifier`] apply to all
/// points fed into the batch (I/O pairs and proof points).
pub struct BatchVerifier<S: RingSuite> {
    ring_batch: RingBatchVerifier<S>,
    pedersen_batch: pedersen::BatchVerifier<S>,
}

impl<S: RingSuite> BatchVerifier<S> {
    /// Create a new batch verifier seeded with the KZG SRS taken from `ring_verifier`.
    ///
    /// Any ring verifier sharing the same SRS can later be passed to
    /// [`Self::push`] or [`BatchItem::new`]; the verifier supplied here is
    /// only used to extract the KZG verifier key.
    pub fn new(ring_verifier: &RingVerifier<S>) -> Self {
        Self {
            ring_batch: RingBatchVerifier::<S>::new(
                ring_verifier.pcs_vk().clone(),
                ring_proof::ArkTranscript::new(S::SUITE_ID),
            ),
            pedersen_batch: pedersen::BatchVerifier::new(),
        }
    }

    /// Push a previously prepared item into the batch.
    pub fn push_prepared(&mut self, item: BatchItem<S>) {
        self.pedersen_batch.push_prepared(item.pedersen);
        self.ring_batch.push_prepared(item.ring);
    }

    /// Prepare and push a proof in one step.
    ///
    /// Returns `Error::InvalidData` if the proof's key commitment cannot be
    /// converted (e.g. identity point on SW-form suites).
    pub fn push(
        &mut self,
        verifier: &RingVerifier<S>,
        ios: impl AsRef<[VrfIo<S>]>,
        ad: impl AsRef<[u8]>,
        proof: &Proof<S>,
    ) -> Result<(), Error> {
        let item = BatchItem::new(verifier, ios, ad, proof)?;
        self.push_prepared(item);
        Ok(())
    }

    /// Verify all collected proofs in a single batch.
    ///
    /// Checks both the Pedersen proofs (via MSM) and the ring proofs (via pairing).
    /// Returns `Ok(())` if all proofs verify, `Err(VerificationFailure)` otherwise.
    pub fn verify(&self) -> Result<(), Error> {
        self.pedersen_batch.verify()?;
        self.ring_batch
            .verify()
            .then_some(())
            .ok_or(Error::VerificationFailure)
    }
}

/// Type aliases for the given ring suite.
#[macro_export]
macro_rules! ring_suite_types {
    ($suite:ident) => {
        #[allow(dead_code)]
        pub type PcsParams = $crate::ring::PcsParams<$suite>;
        #[allow(dead_code)]
        pub type PcsVerifierParams = $crate::ring::PcsVerifierParams<$suite>;
        #[allow(dead_code)]
        pub type PiopParams = $crate::ring::PiopParams<$suite>;
        #[allow(dead_code)]
        pub type RingContext = $crate::ring::RingContext<$suite>;
        #[allow(dead_code)]
        pub type RingSetup = $crate::ring::RingSetup<$suite>;
        #[allow(dead_code)]
        pub type RingProverKey = $crate::ring::RingProverKey<$suite>;
        #[allow(dead_code)]
        pub type RingVerifierKey = $crate::ring::RingVerifierKey<$suite>;
        #[allow(dead_code)]
        pub type RingCommitment = $crate::ring::RingCommitment<$suite>;
        #[allow(dead_code)]
        pub type RingProver = $crate::ring::RingProver<$suite>;
        #[allow(dead_code)]
        pub type RingVerifier = $crate::ring::RingVerifier<$suite>;
        #[allow(dead_code)]
        pub type RingProof = $crate::ring::Proof<$suite>;
        #[allow(dead_code)]
        pub type RingVerifierKeyBuilder = $crate::ring::VerifierKeyBuilder<$suite>;
        #[allow(dead_code)]
        pub type RingBatchItem = $crate::ring::BatchItem<$suite>;
        #[allow(dead_code)]
        pub type RingBatchVerifier = $crate::ring::BatchVerifier<$suite>;
    };
}

/// Domain size conversion utilities
///
/// The ring proof system operates with three related size parameters:
///
/// 1. `min_ring_size`: Number of keys that the ring should accomodate (user-facing parameter)
/// 2. `max_ring_size`: Max number of keys that the ring can accomodate
/// 3. `piop_domain_size`: Size of the PIOP (Polynomial IOP) domain
/// 4. `pcs_domain_size`: Size of the PCS (Polynomial Commitment Scheme) domain
///
/// Relationships:
///   piop_domain_size = (ring_size + PIOP_OVERHEAD).next_power_of_two()
///   pcs_domain_size  = 3 * piop_domain_size + 1
///   max_ring_size    = piop_domain_size - PIOP_OVERHEAD
///
/// where PIOP_OVERHEAD = 4 + MODULUS_BIT_SIZE accounts for:
///   - 3 points for zero-knowledge blinding
///   - 1 extra point used internally by the PIOP
///   - MODULUS_BIT_SIZE bits for blinding factor
///
/// Note: Multiple ring sizes map to the same domain sizes due to power-of-2 rounding.
/// For example, ring sizes 1-254 (with 254-bit scalar) all map to piop_domain_size=512
/// and pcs_domain_size=1537.
pub mod dom_utils {
    use super::*;

    /// Returns the actual ring capacity for a given minimum size requirement.
    ///
    /// Because domain sizes round up to powers of 2, allocating for `min_ring_size`
    /// keys typically provides capacity for more. This function returns that actual
    /// capacity: the largest ring size that uses the same domain as `min_ring_size`.
    ///
    /// Always returns a value `>= min_ring_size`.
    pub const fn max_ring_size<S: Suite>(min_ring_size: usize) -> usize {
        max_ring_size_from_piop_domain_size::<S>(piop_domain_size::<S>(min_ring_size))
    }

    /// PIOP overhead: accounts for 3 ZK blinding points + 1 internal point + scalar field bits.
    pub const fn piop_overhead<S: Suite>() -> usize {
        4 + ScalarField::<S>::MODULUS_BIT_SIZE as usize
    }

    /// PIOP domain size required to support the given ring size.
    ///
    /// Returns the smallest power of 2 that can accommodate `min_ring_capactity` members.
    /// This is the domain size used for polynomial operations in the ring proof and
    /// already accounts for the PIOP overhead.
    pub const fn piop_domain_size<S: Suite>(min_ring_capacity: usize) -> usize {
        (min_ring_capacity + piop_overhead::<S>()).next_power_of_two()
    }

    /// Maximum ring size supported by a given PIOP domain size.
    ///
    /// Returns the largest ring that fits in the domain.
    pub const fn max_ring_size_from_piop_domain_size<S: Suite>(piop_domain_size: usize) -> usize {
        piop_domain_size - piop_overhead::<S>()
    }

    /// PCS domain size required to support the given ring size.
    ///
    /// Returns `3 * piop_domain_size + 1`. This is the number of G1 elements required
    /// in the SRS (powers of tau) for the prover. The verifier only needs the PIOP domain size.
    pub const fn pcs_domain_size<S: Suite>(min_ring_size: usize) -> usize {
        pcs_domain_size_from_piop_domain_size(piop_domain_size::<S>(min_ring_size))
    }

    /// PCS domain size for a given PIOP domain size.
    ///
    /// Returns `3 * piop_domain_size + 1`.
    pub const fn pcs_domain_size_from_piop_domain_size(piop_domain_size: usize) -> usize {
        3 * piop_domain_size + 1
    }

    /// PIOP domain size extracted from a PCS domain size.
    ///
    /// Recovers the PIOP domain size from a PCS domain size. The ilog2 ensures we get
    /// a valid power of 2 even if the input wasn't properly constructed.
    pub const fn piop_domain_size_from_pcs_domain_size(pcs_domain_size: usize) -> usize {
        1 << ((pcs_domain_size - 1) / 3).ilog2()
    }

    /// Maximum ring size supported by a given PCS domain size.
    ///
    /// Composes `piop_domain_size_from_pcs_domain_size` and `max_ring_size_from_piop_domain_size`.
    pub const fn max_ring_size_from_pcs_domain_size<S: Suite>(pcs_domain_size: usize) -> usize {
        let piop_domain_size = piop_domain_size_from_pcs_domain_size(pcs_domain_size);
        max_ring_size_from_piop_domain_size::<S>(piop_domain_size)
    }
}
pub use dom_utils::*;

#[cfg(test)]
pub(crate) mod testing {
    use super::*;
    use crate::pedersen;
    use crate::testing::{self as common, CheckPoint, TEST_SEED};
    use ark_ec::{
        short_weierstrass::{Affine as SWAffine, SWCurveConfig},
        twisted_edwards::{Affine as TEAffine, TECurveConfig},
    };

    pub const TEST_RING_SIZE: usize = 8;

    const MAX_AD_LEN: usize = 100;

    fn find_complement_point<C: SWCurveConfig>() -> SWAffine<C> {
        use ark_ff::{One, Zero};
        assert!(!C::cofactor_is_one());
        let mut x = C::BaseField::zero();
        loop {
            if let Some(p) = SWAffine::get_point_from_x_unchecked(x, false)
                .filter(|p| !p.is_in_correct_subgroup_assuming_on_curve())
            {
                return p;
            }
            x += C::BaseField::one();
        }
    }

    pub trait FindAccumulatorBase<S: Suite>: Sized {
        const IN_PRIME_ORDER_SUBGROUP: bool;
        fn find_accumulator_base(data: &[u8]) -> Option<Self>;
    }

    impl<S, C> FindAccumulatorBase<S> for SWAffine<C>
    where
        C: SWCurveConfig,
        S: Suite<Affine = Self>,
    {
        const IN_PRIME_ORDER_SUBGROUP: bool = false;

        fn find_accumulator_base(data: &[u8]) -> Option<Self> {
            let p = S::data_to_point(data)?;
            let c = find_complement_point();
            let res = (p + c).into_affine();
            debug_assert!(!res.is_in_correct_subgroup_assuming_on_curve());
            Some(res)
        }
    }

    impl<S, C> FindAccumulatorBase<S> for TEAffine<C>
    where
        C: TECurveConfig,
        S: Suite<Affine = Self>,
    {
        const IN_PRIME_ORDER_SUBGROUP: bool = true;

        fn find_accumulator_base(data: &[u8]) -> Option<Self> {
            let res = S::data_to_point(data)?;
            debug_assert!(res.is_in_correct_subgroup_assuming_on_curve());
            Some(res)
        }
    }

    struct TestItem<S: RingSuite> {
        io: VrfIo<S>,
        ad: Vec<u8>,
        proof: Proof<S>,
    }

    impl<S: RingSuite> TestItem<S> {
        fn new(
            secret: &Secret<S>,
            prover: &RingProver<S>,
            rng: &mut dyn ark_std::rand::RngCore,
        ) -> Self {
            let input = Input::from_affine_unchecked(common::random_val(Some(rng)));
            let io = secret.vrf_io(input);
            let ad_len = common::random_val::<usize>(Some(rng)) % (MAX_AD_LEN + 1);
            let ad = common::random_vec(ad_len, Some(rng));
            let proof = secret.prove(io, &ad, prover);
            Self { io, ad, proof }
        }
    }

    #[allow(unused)]
    pub fn prove_verify<S: RingSuite>() {
        let rng = &mut ark_std::test_rng();
        let ring_setup = RingSetup::<S>::from_rand(TEST_RING_SIZE, rng);

        let secret = Secret::<S>::from_seed(TEST_SEED);
        let public = secret.public();

        let mut pks = common::random_vec::<AffinePoint<S>>(TEST_RING_SIZE, Some(rng));
        let prover_idx = 3;
        pks[prover_idx] = public.0;

        let ring_ctx = ring_setup.ring_context();
        let prover_key = ring_setup.prover_key(&pks).unwrap();
        let prover = ring_ctx.ring_prover(prover_key, prover_idx);

        let item = TestItem::<S>::new(&secret, &prover, rng);

        let verifier_key = ring_setup.verifier_key(&pks).unwrap();
        let verifier = ring_ctx.ring_verifier(verifier_key);
        let result = Public::verify(item.io, &item.ad, &item.proof, &verifier);
        assert!(result.is_ok());
    }

    /// N=3 multi proof via ring prove/verify.
    #[allow(unused)]
    pub fn prove_verify_multi<S: RingSuite>() {
        use ring::{Prover, Verifier};

        let rng = &mut ark_std::test_rng();
        let ring_setup = RingSetup::<S>::from_rand(TEST_RING_SIZE, rng);

        let secret = Secret::<S>::from_seed(TEST_SEED);
        let public = secret.public();

        let mut pks = common::random_vec::<AffinePoint<S>>(TEST_RING_SIZE, Some(rng));
        let prover_idx = 3;
        pks[prover_idx] = public.0;

        let ring_ctx = ring_setup.ring_context();
        let prover_key = ring_setup.prover_key(&pks).unwrap();
        let prover = ring_ctx.ring_prover(prover_key, prover_idx);

        let verifier_key = ring_setup.verifier_key(&pks).unwrap();
        let verifier = ring_ctx.ring_verifier(verifier_key);

        let mut ios: Vec<VrfIo<S>> = (0..3u8)
            .map(|i| {
                let input = Input::new(&[i + 1]).unwrap();
                secret.vrf_io(input)
            })
            .collect();
        ios.push(VrfIo {
            input: Input(S::Affine::generator()),
            output: Output(public.0),
        });

        let proof = secret.prove(&ios[..], b"bar", &prover);
        assert!(Public::verify(&ios[..], b"bar", &proof, &verifier).is_ok());

        // Tamper: wrong output on ios[1]
        let mut bad_ios = ios.clone();
        bad_ios[1].output = secret.output(ios[0].input);
        assert!(Public::verify(&bad_ios[..], b"bar", &proof, &verifier).is_err());

        // Tamper: wrong ad
        assert!(Public::verify(&ios[..], b"baz", &proof, &verifier).is_err());
    }

    #[allow(unused)]
    pub fn prove_verify_batch<S: RingSuite>() {
        use rayon::prelude::*;

        const BATCH_SIZE: usize = 3 * TEST_RING_SIZE;

        let rng = &mut ark_std::test_rng();
        let ring_setup = RingSetup::<S>::from_rand(TEST_RING_SIZE, rng);

        let secret = Secret::<S>::from_seed(TEST_SEED);
        let public = secret.public();

        let mut pks = common::random_vec::<AffinePoint<S>>(TEST_RING_SIZE, Some(rng));
        let prover_idx = 3;
        pks[prover_idx] = public.0;

        let ring_ctx = ring_setup.ring_context();
        let prover_key = ring_setup.prover_key(&pks).unwrap();
        let prover = ring_ctx.ring_prover(prover_key, prover_idx);

        // Generate proofs in parallel
        let batch: Vec<_> = (0..BATCH_SIZE)
            .into_par_iter()
            .map_init(ark_std::test_rng, |rng, _| {
                TestItem::<S>::new(&secret, &prover, rng)
            })
            .collect();

        let verifier_key = ring_setup.verifier_key(&pks).unwrap();
        let verifier = ring_ctx.ring_verifier(verifier_key);

        // Batch verify all proofs
        let mut batch_verifier = BatchVerifier::<S>::new(&verifier);
        let res = batch_verifier.verify();
        assert!(res.is_ok());

        // Prove incrementally constructed batches
        for item in batch.iter() {
            batch_verifier
                .push(&verifier, item.io, &item.ad, &item.proof)
                .unwrap();
            let res = batch_verifier.verify();
            assert!(res.is_ok());
        }

        println!("Batch size = {BATCH_SIZE}");

        println!("============================================================");

        let mut batch_verifier = BatchVerifier::<S>::new(&verifier);
        let start = std::time::Instant::now();
        common::timed("Proofs push", || {
            for item in batch.iter() {
                batch_verifier
                    .push(&verifier, item.io, &item.ad, &item.proof)
                    .unwrap();
            }
        });
        common::timed("Unprepared batch verification", || batch_verifier.verify());
        println!("Total time: {:?}", start.elapsed());

        println!("============================================================");

        let mut batch_verifier = BatchVerifier::<S>::new(&verifier);
        let start = std::time::Instant::now();
        let prepared = common::timed("Proofs prepare", || {
            batch
                .par_iter()
                .map(|item| BatchItem::<S>::new(&verifier, item.io, &item.ad, &item.proof).unwrap())
                .collect::<Vec<_>>()
        });
        common::timed("Proofs push prepared", || {
            prepared
                .into_iter()
                .for_each(|p| batch_verifier.push_prepared(p))
        });
        common::timed("Prepared batch verification", || batch_verifier.verify());
        println!("Total time: {:?}", start.elapsed());

        println!("============================================================");

        // Multi-ring batch: build a second ring sharing the same KZG SRS,
        // then aggregate proofs from both rings into a single batch verifier.
        let mut pks_b = common::random_vec::<AffinePoint<S>>(TEST_RING_SIZE, Some(rng));
        let prover_idx_b = 1;
        pks_b[prover_idx_b] = public.0;
        let prover_key_b = ring_setup.prover_key(&pks_b).unwrap();
        let prover_b = ring_ctx.ring_prover(prover_key_b, prover_idx_b);
        let verifier_key_b = ring_setup.verifier_key(&pks_b).unwrap();
        let verifier_b = ring_ctx.ring_verifier(verifier_key_b);

        let batch_b: Vec<_> = (0..TEST_RING_SIZE)
            .into_par_iter()
            .map_init(ark_std::test_rng, |rng, _| {
                TestItem::<S>::new(&secret, &prover_b, rng)
            })
            .collect();

        let mut batch_verifier = BatchVerifier::<S>::new(&verifier);
        for item in batch.iter() {
            batch_verifier
                .push(&verifier, item.io, &item.ad, &item.proof)
                .unwrap();
        }
        for item in batch_b.iter() {
            batch_verifier
                .push(&verifier_b, item.io, &item.ad, &item.proof)
                .unwrap();
        }
        common::timed("Multi-ring batch verification", || batch_verifier.verify())
            .expect("multi-ring batch verifies");

        // Negative case: pushing a ring-B proof against verifier_a must not
        // produce a batch that verifies. This guards against the per-item
        // verifier argument being silently ignored.
        let mut batch_verifier = BatchVerifier::<S>::new(&verifier);
        let item_b = &batch_b[0];
        batch_verifier
            .push(&verifier, item_b.io, &item_b.ad, &item_b.proof)
            .unwrap();
        assert!(
            batch_verifier.verify().is_err(),
            "ring-B proof must not verify against verifier_a"
        );
    }

    #[allow(unused)]
    pub fn padding_check<S: RingSuite>()
    where
        AffinePoint<S>: CheckPoint,
    {
        // Check that point has been computed using the magic spell.
        assert_eq!(S::PADDING, S::data_to_point(PADDING_SEED).unwrap());

        // Check that the point is on curve.
        assert!(S::PADDING.check(true).is_ok());
    }

    #[allow(unused)]
    pub fn accumulator_base_check<S: RingSuite>()
    where
        AffinePoint<S>: FindAccumulatorBase<S> + CheckPoint,
    {
        // Check that point has been computed using the magic spell.
        assert_eq!(
            S::ACCUMULATOR_BASE,
            AffinePoint::<S>::find_accumulator_base(ACCUMULATOR_BASE_SEED).unwrap()
        );

        // SW form requires accumulator seed to be outside prime order subgroup.
        // TE form requires accumulator seed to be in prime order subgroup.
        let in_prime_subgroup = <AffinePoint<S> as FindAccumulatorBase<S>>::IN_PRIME_ORDER_SUBGROUP;
        assert!(S::ACCUMULATOR_BASE.check(in_prime_subgroup).is_ok());
    }

    #[allow(unused)]
    pub fn verifier_key_from_commitment<S: RingSuite>() {
        let rng = &mut ark_std::test_rng();
        let ring_setup = RingSetup::<S>::from_rand(TEST_RING_SIZE, rng);

        let secret = Secret::<S>::from_seed(TEST_SEED);
        let public = secret.public();

        let mut pks = common::random_vec::<AffinePoint<S>>(TEST_RING_SIZE, Some(rng));
        let prover_idx = 3;
        pks[prover_idx] = public.0;

        let prover_key = ring_setup.prover_key(&pks).unwrap();
        let prover = ring_setup
            .ring_context()
            .ring_prover(prover_key, prover_idx);
        let item = TestItem::<S>::new(&secret, &prover, rng);

        let commitment = ring_setup.verifier_key(&pks).unwrap().commitment();

        // Round-trip the params to mimic a verifier-only user holding just
        // the serialized params, the ring commitment and the ring size.
        let mut buf = Vec::new();
        ring_setup
            .pcs_verifier_params()
            .serialize_compressed(&mut buf)
            .unwrap();
        let pcs_params = PcsVerifierParams::<S>::deserialize_compressed(&buf[..]).unwrap();

        let ring_ctx = RingContext::<S>::new(TEST_RING_SIZE);
        let verifier_key = super::verifier_key_from_commitment::<S>(commitment, pcs_params);
        let verifier = ring_ctx.ring_verifier(verifier_key);
        assert!(Public::verify(item.io, &item.ad, &item.proof, &verifier).is_ok());
    }

    #[allow(unused)]
    pub fn verifier_key_builder<S: RingSuite>() {
        use crate::testing::{random_val, random_vec};

        let rng = &mut ark_std::test_rng();
        let ring_setup = RingSetup::<S>::from_rand(TEST_RING_SIZE, rng);

        let secret = Secret::<S>::from_seed(TEST_SEED);
        let public = secret.public();
        let input = Input::from_affine_unchecked(common::random_val(Some(rng)));
        let io = secret.vrf_io(input);

        let ring_ctx = ring_setup.ring_context();
        let ring_size = ring_ctx.max_ring_size();
        let prover_idx = random_val::<usize>(Some(rng)) % ring_size;
        let mut pks = random_vec::<AffinePoint<S>>(ring_size, Some(rng));
        pks[prover_idx] = public.0;

        let prover_key = ring_setup.prover_key(&pks).unwrap();
        let prover = ring_ctx.ring_prover(prover_key, prover_idx);
        let proof = secret.prove(io, b"foo", &prover);

        // Incremental ring verifier key construction
        let (mut vk_builder, lookup) = ring_setup.verifier_key_builder();
        assert_eq!(vk_builder.free_slots(), pks.len());
        assert_eq!(
            vk_builder.pcs_verifier_params(),
            ring_setup.pcs_verifier_params()
        );

        let extra_pk = random_val::<AffinePoint<S>>(Some(rng));
        assert_eq!(
            vk_builder.append(&[extra_pk], |_| None).unwrap_err(),
            usize::MAX
        );

        while !pks.is_empty() {
            let chunk_len = 1 + random_val::<usize>(Some(rng)) % 5;
            let chunk = pks.drain(..pks.len().min(chunk_len)).collect::<Vec<_>>();
            vk_builder.append(&chunk[..], &lookup).unwrap();
            assert_eq!(vk_builder.free_slots(), pks.len());
        }
        // No more space left
        let extra_pk = random_val::<AffinePoint<S>>(Some(rng));
        assert_eq!(vk_builder.append(&[extra_pk], &lookup).unwrap_err(), 0);
        let verifier_key = vk_builder.finalize();
        let verifier = ring_ctx.ring_verifier(verifier_key);
        let result = Public::verify(io, b"foo", &proof, &verifier);
        assert!(result.is_ok());
    }

    pub fn domain_size_conversions<S: RingSuite>() {
        let overhead = piop_overhead::<S>();

        for ring_size in [1, 10, 200, 300, 500, 1000, 2000, 10000] {
            let piop_dom_size = piop_domain_size::<S>(ring_size);
            let pcs_dom_size = pcs_domain_size::<S>(ring_size);
            let max_ring_size = max_ring_size_from_piop_domain_size::<S>(piop_dom_size);

            assert!(piop_dom_size.is_power_of_two());
            assert_eq!(pcs_dom_size, 3 * piop_dom_size + 1);

            // piop_domain_size must fit ring_size + overhead
            assert!(piop_dom_size >= ring_size + overhead);
            // piop_domain_size is the smallest power of 2 that fits
            assert!(piop_dom_size / 2 < ring_size + overhead);
            // piop_dom_size is sufficient for max_ring_size
            assert_eq!(piop_dom_size, piop_domain_size::<S>(max_ring_size));
            // ring_size <= max_ring_size for the computed domain
            assert!(ring_size <= max_ring_size);

            // max_ring_size() helper equivalence
            assert_eq!(dom_utils::max_ring_size::<S>(ring_size), max_ring_size);
            // max_ring_size() is idempotent
            assert_eq!(dom_utils::max_ring_size::<S>(max_ring_size), max_ring_size);

            // Round-trip
            let piop_dom_rt = piop_domain_size_from_pcs_domain_size(pcs_dom_size);
            assert_eq!(piop_dom_size, piop_dom_rt);
            let pcs_dom_rt = pcs_domain_size_from_piop_domain_size(piop_dom_rt);
            assert_eq!(pcs_dom_size, pcs_dom_rt);

            let max_ring_from_pcs = max_ring_size_from_pcs_domain_size::<S>(pcs_dom_size);
            assert_eq!(max_ring_size, max_ring_from_pcs);

            // max_ring + 1 should require a larger piop domain
            let next_piop = piop_domain_size::<S>(max_ring_size + 1);
            assert!(next_piop > piop_dom_size,);
            assert!(next_piop.is_power_of_two());
        }

        // Test inverse with arbitrary PCS values (not necessarily properly constructed)
        // The inverse function should recover the largest valid piop that fits
        for pcs_dom_size in [1 << 11, 1 << 12, 1 << 14, 1 << 16] {
            let piop_dom = piop_domain_size_from_pcs_domain_size(pcs_dom_size);
            let max_ring = max_ring_size_from_pcs_domain_size::<S>(pcs_dom_size);

            assert!(piop_dom.is_power_of_two());
            // piop should satisfy: 3 * piop + 1 <= pcs
            assert!(3 * piop_dom < pcs_dom_size);
            // but 3 * (2 * piop) + 1 > pcs (piop is maximal)
            assert!(3 * (2 * piop_dom) + 1 > pcs_dom_size);
            // max_ring should map back to this piop
            assert_eq!(piop_domain_size::<S>(max_ring), piop_dom);
            // max_ring + 1 should require larger piop
            assert!(piop_domain_size::<S>(max_ring + 1) > piop_dom);
        }

        // Edge case: ring_size = 0 (degenerate but shouldn't panic)
        let piop_zero = piop_domain_size::<S>(0);
        assert!(piop_zero.is_power_of_two());
        assert_eq!(piop_zero, overhead.next_power_of_two());
    }

    #[macro_export]
    macro_rules! ring_suite_tests {
        ($suite:ty) => {
            mod ring {
                use super::*;

                #[test]
                fn prove_verify() {
                    $crate::ring::testing::prove_verify::<$suite>()
                }

                #[test]
                fn prove_verify_multi() {
                    $crate::ring::testing::prove_verify_multi::<$suite>()
                }

                #[test]
                fn prove_verify_batch() {
                    $crate::ring::testing::prove_verify_batch::<$suite>()
                }

                #[test]
                fn padding_check() {
                    $crate::ring::testing::padding_check::<$suite>()
                }

                #[test]
                fn accumulator_base_check() {
                    $crate::ring::testing::accumulator_base_check::<$suite>()
                }

                #[test]
                fn verifier_key_builder() {
                    $crate::ring::testing::verifier_key_builder::<$suite>()
                }

                #[test]
                fn verifier_key_from_commitment() {
                    $crate::ring::testing::verifier_key_from_commitment::<$suite>()
                }

                #[test]
                fn domain_size_conversions() {
                    $crate::ring::testing::domain_size_conversions::<$suite>()
                }

                $crate::test_vectors!($crate::ring::testing::TestVector<$suite>);
            }
        };
    }

    pub trait RingSuiteExt: RingSuite + crate::testing::SuiteExt {
        const SRS_FILE: &str;

        fn ring_setup() -> &'static RingSetup<Self>;

        #[allow(unused)]
        fn load_ring_setup() -> RingSetup<Self> {
            use ark_serialize::CanonicalDeserialize;
            use std::{fs::File, io::Read};
            let mut file = File::open(Self::SRS_FILE).unwrap();
            let mut buf = Vec::new();
            file.read_to_end(&mut buf).unwrap();
            let pcs_params =
                PcsParams::<Self>::deserialize_uncompressed_unchecked(&mut &buf[..]).unwrap();
            RingSetup::from_pcs_params(crate::ring::testing::TEST_RING_SIZE, pcs_params).unwrap()
        }

        #[allow(unused)]
        fn write_ring_setup(ring_setup: &RingSetup<Self>) {
            use ark_serialize::CanonicalSerialize;
            use std::{fs::File, io::Write};
            let mut file = File::create(Self::SRS_FILE).unwrap();
            let mut buf = Vec::new();
            ring_setup
                .pcs_params
                .serialize_uncompressed(&mut buf)
                .unwrap();
            file.write_all(&buf).unwrap();
        }
    }

    pub struct TestVector<S: RingSuite> {
        pub pedersen: pedersen::testing::TestVector<S>,
        pub ring_pks: [AffinePoint<S>; TEST_RING_SIZE],
        pub ring_pks_com: RingCommitment<S>,
        pub ring_proof: RingBareProof<S>,
    }

    impl<S: RingSuite> core::fmt::Debug for TestVector<S> {
        fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
            f.debug_struct("TestVector")
                .field("pedersen", &self.pedersen)
                .field("ring_proof", &"...")
                .finish()
        }
    }

    impl<S> common::TestVectorTrait for TestVector<S>
    where
        S: RingSuiteExt + std::fmt::Debug + 'static,
    {
        fn name() -> String {
            S::SUITE_NAME.to_string() + "_ring"
        }

        fn new(comment: &str, seed: &[u8; 32], alpha: &[u8], ad: &[u8]) -> Self {
            use super::Prover;
            let pedersen = pedersen::testing::TestVector::new(comment, seed, alpha, ad);

            let secret = Secret::<S>::from_scalar(pedersen.base.sk);
            let public = secret.public();

            let io = VrfIo {
                input: Input::<S>::from_affine_unchecked(pedersen.base.h),
                output: Output::from_affine_unchecked(pedersen.base.gamma),
            };

            let ring_setup = <S as RingSuiteExt>::ring_setup();

            use ark_std::rand::SeedableRng;
            let rng = &mut ark_std::rand::rngs::StdRng::from_seed([42; 32]);
            let prover_idx = 3;
            let mut ring_pks = common::random_vec::<AffinePoint<S>>(TEST_RING_SIZE, Some(rng));
            ring_pks[prover_idx] = public.0;

            // Blinding is disabled to make the proof reproducible
            let ring_ctx = RingContext::<S>::new_without_blinding(TEST_RING_SIZE);
            let prover_key = ring_setup.prover_key(&ring_pks).unwrap();
            let prover = ring_ctx.into_ring_prover(prover_key, prover_idx);
            let proof = secret.prove(io, ad, &prover);

            let verifier_key = ring_setup.verifier_key(&ring_pks).unwrap();
            let ring_pks_com = verifier_key.commitment();

            {
                // Just in case...
                let mut p = (Vec::new(), Vec::new());
                pedersen.proof.serialize_compressed(&mut p.0).unwrap();
                proof.pedersen_proof.serialize_compressed(&mut p.1).unwrap();
                assert_eq!(p.0, p.1);
            }

            Self {
                pedersen,
                ring_pks: ring_pks.try_into().unwrap(),
                ring_pks_com,
                ring_proof: proof.ring_proof,
            }
        }

        fn from_map(map: &common::TestVectorMap) -> Self {
            let pedersen = pedersen::testing::TestVector::from_map(map);

            let ring_pks = map.get::<[AffinePoint<S>; TEST_RING_SIZE]>("ring_pks");
            let ring_pks_com = map.get::<RingCommitment<S>>("ring_pks_com");
            let ring_proof = map.get::<RingBareProof<S>>("ring_proof");

            Self {
                pedersen,
                ring_pks,
                ring_pks_com,
                ring_proof,
            }
        }

        fn to_map(&self) -> common::TestVectorMap {
            let mut map = self.pedersen.to_map();
            map.set("ring_pks", &self.ring_pks);
            map.set("ring_pks_com", &self.ring_pks_com);
            map.set("ring_proof", &self.ring_proof);
            map
        }

        fn run(&self) {
            self.pedersen.run();

            let io = VrfIo {
                input: Input::<S>::from_affine_unchecked(self.pedersen.base.h),
                output: Output::from_affine_unchecked(self.pedersen.base.gamma),
            };
            let secret = Secret::from_scalar(self.pedersen.base.sk);
            let public = secret.public();
            assert_eq!(public.0, self.pedersen.base.pk);

            let ring_setup = <S as RingSuiteExt>::ring_setup();

            let prover_idx = self.ring_pks.iter().position(|&pk| pk == public.0).unwrap();

            // Blinding is disabled to reproduce the exact proof in the vector
            let ring_ctx = RingContext::<S>::new_without_blinding(TEST_RING_SIZE);
            let prover_key = ring_setup.prover_key(&self.ring_pks).unwrap();
            let prover = ring_ctx.ring_prover(prover_key, prover_idx);

            let verifier_key = ring_setup.verifier_key(&self.ring_pks).unwrap();
            let verifier = ring_ctx.ring_verifier(verifier_key);

            let proof = secret.prove(io, &self.pedersen.base.ad, &prover);

            {
                // Check if Pedersen proof matches
                let mut p = (Vec::new(), Vec::new());
                self.pedersen.proof.serialize_compressed(&mut p.0).unwrap();
                proof.pedersen_proof.serialize_compressed(&mut p.1).unwrap();
                assert_eq!(p.0, p.1);
            }

            {
                // Check if the (deterministic) ring proof matches
                let mut p = (Vec::new(), Vec::new());
                self.ring_proof.serialize_compressed(&mut p.0).unwrap();
                proof.ring_proof.serialize_compressed(&mut p.1).unwrap();
                assert_eq!(p.0, p.1);
            }

            assert!(Public::verify(io, &self.pedersen.base.ad, &proof, &verifier).is_ok());
        }
    }
}