verifiable 0.3.0

use alloc::{borrow::Cow, rc::Rc, vec};
use core::{marker::PhantomData, ops::Range};

pub use ark_vrf;

use ark_serialize::{CanonicalDeserialize, CanonicalSerialize, Valid};
use ark_vrf::{
	VrfIo,
	reexports::ark_ec::AffineRepr,
	ring::{RingContext, RingSuite, Verifier},
};
use bounded_collections::{BoundedVec, Get};
use parity_scale_codec::{Decode, Encode};
use scale_info::TypeInfo;

use super::*;

pub mod bandersnatch;

/// Uncompressed encoding mode for SCALE codec round-trips.
/// Validation is enabled to reject malformed data that could trigger panics
/// in downstream cryptographic operations.
const UNCOMPRESSED: ark_scale::Usage =
	ark_scale::make_usage(ark_serialize::Compress::No, ark_serialize::Validate::Yes);

/// Uncompressed encoding mode without curve-point validation. Used by the
/// [`DecodeUnchecked`] entry points for decoding values from trusted sources
/// where the validation cost has already been paid on the way in.
const UNCOMPRESSED_UNCHECKED: ark_scale::Usage =
	ark_scale::make_usage(ark_serialize::Compress::No, ark_serialize::Validate::No);

pub use crate::DecodeUnchecked;

/// Domain sizes for the PCS (Polynomial Commitment Scheme).
///
/// This determines the maximum ring size that can be supported for a ring suite.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Encode, Decode, TypeInfo, DecodeWithMemTracking)]
pub enum RingDomainSize {
	/// Domain size 2^11 (max 255 members)
	Domain11,
	/// Domain size 2^12 (max 767 members)
	Domain12,
	/// Domain size 2^16 (max 16127 members)
	Domain16,
}

impl TryFrom<u32> for RingDomainSize {
	type Error = ();
	fn try_from(value: u32) -> Result<Self, Self::Error> {
		Self::VARIANTS
			.iter()
			.copied()
			.find(|d| d.value() == value)
			.ok_or(())
	}
}

impl RingDomainSize {
	/// All variants, in declaration order. Reuse this instead of redefining
	/// the array at call sites.
	pub const VARIANTS: [Self; 3] = [Self::Domain11, Self::Domain12, Self::Domain16];

	/// Returns the domain size as a power of 2.
	pub const fn as_power(self) -> u32 {
		match self {
			RingDomainSize::Domain11 => 11,
			RingDomainSize::Domain12 => 12,
			RingDomainSize::Domain16 => 16,
		}
	}

	/// Returns the actual PCS domain size (2^power).
	pub const fn value(self) -> u32 {
		1 << self.as_power()
	}

	/// The max ring that can be handled for both sign/verify at this domain size.
	pub const fn max_ring_size<S: RingSuite>(self) -> usize {
		ark_vrf::ring::max_ring_size_from_pcs_domain_size::<S>(self.value() as usize)
	}
}

/// Trait for providing pairing-curve-specific ring data.
///
/// All RingSuites that use the same pairing curve can share the same data provider.
/// For example, all suites using BLS12-381 (like Bandersnatch) use `Bls12_381Params`.
pub trait RingCurveParams {
	/// Raw SRS data (powers of tau).
	#[cfg(feature = "prover")]
	fn srs_raw() -> &'static [u8];

	/// Ring builder params for a given domain size.
	#[cfg(any(feature = "std", feature = "builder-params"))]
	fn ring_builder_params(domain: RingDomainSize) -> &'static [u8];

	/// Empty ring commitment data for a given domain size.
	fn empty_ring_commitment(domain: RingDomainSize) -> &'static [u8];
}

/// Ring data for suites using BLS12-381 pairing (e.g., Bandersnatch curves).
pub struct Bls12_381Params;

impl RingCurveParams for Bls12_381Params {
	#[cfg(feature = "prover")]
	fn srs_raw() -> &'static [u8] {
		include_bytes!("data/bls12-381/srs-uncompressed.bin")
	}

	#[cfg(any(feature = "std", feature = "builder-params"))]
	fn ring_builder_params(domain: RingDomainSize) -> &'static [u8] {
		match domain {
			RingDomainSize::Domain11 => {
				include_bytes!("data/bls12-381/ring-builder-params-domain11.bin")
			}
			RingDomainSize::Domain12 => {
				include_bytes!("data/bls12-381/ring-builder-params-domain12.bin")
			}
			RingDomainSize::Domain16 => {
				include_bytes!("data/bls12-381/ring-builder-params-domain16.bin")
			}
		}
	}

	fn empty_ring_commitment(domain: RingDomainSize) -> &'static [u8] {
		match domain {
			RingDomainSize::Domain11 => include_bytes!("data/bls12-381/ring-builder-domain11.bin"),
			RingDomainSize::Domain12 => include_bytes!("data/bls12-381/ring-builder-domain12.bin"),
			RingDomainSize::Domain16 => include_bytes!("data/bls12-381/ring-builder-domain16.bin"),
		}
	}
}

/// Construct ring setup from the suite's SRS data.
#[cfg(feature = "prover")]
pub fn make_ring_setup<S: RingSuiteExt>(
	domain_size: RingDomainSize,
) -> ark_vrf::ring::RingSetup<S> {
	let data = S::CurveParams::srs_raw();
	let pcs_params =
		ark_vrf::ring::PcsParams::<S>::deserialize_uncompressed_unchecked(data).unwrap();
	let ring_size = domain_size.max_ring_size::<S>();
	ark_vrf::ring::RingSetup::<S>::from_pcs_params(ring_size, pcs_params).unwrap()
}

/// Get ring builder params for the given domain size.
/// Only available with the `builder-params` or `std` features.
#[cfg(any(feature = "std", feature = "builder-params"))]
pub fn ring_verifier_builder_params<S: RingSuiteExt>(
	domain_size: RingDomainSize,
) -> ark_vrf::ring::RingBuilderPcsParams<S> {
	let data = S::CurveParams::ring_builder_params(domain_size);
	ark_vrf::ring::RingBuilderPcsParams::<S>::deserialize_uncompressed_unchecked(data).unwrap()
}

/// Construct ring context for the given domain size.
pub fn make_ring_context<S: RingSuiteExt>(domain_size: RingDomainSize) -> RingContext<S> {
	let ring_size = domain_size.max_ring_size::<S>();
	RingContext::<S>::new(ring_size)
}

/// Trait for caching ring context.
pub trait VerifierCache<S: RingSuiteExt> {
	/// Get or construct ring context for the given domain size.
	///
	/// The default implementation reconstructs an owned context on every
	/// call; cache implementations should override this and serve a borrow
	/// of a value constructed once per domain.
	fn ring_context(domain_size: RingDomainSize) -> Cow<'static, RingContext<S>> {
		Cow::Owned(make_ring_context(domain_size))
	}

	/// The canonical KZG (PCS) verifier params for this suite, used to rebuild
	/// the ring verifier key from a member set's commitment in
	/// `validate`/`batch_validate`.
	///
	/// The value is domain-size independent so there is a single canonical
	/// value per suite. The default implementation recomputes it from the
	/// embedded empty-ring data on every call; cache implementations should
	/// override this and serve a value computed once.
	fn verifier_params() -> ark_vrf::ring::PcsVerifierParams<S> {
		make_canonical_pcs_vk::<S>()
	}

	/// The empty-ring [`MembersSet`] for the given domain size, as used by
	/// `GenerateVerifiable::start_members`.
	///
	/// Returned by value since callers mutate it. The default implementation
	/// deserializes the embedded empty-ring data on every call; cache
	/// implementations should override this and serve a clone of a value
	/// deserialized once per domain.
	fn empty_members_set(domain_size: RingDomainSize) -> MembersSet<S> {
		make_empty_members_set(domain_size)
	}
}

/// Deserialize the empty-ring [`MembersSet`] from the suite's embedded data
/// for the given domain size.
pub fn make_empty_members_set<S: RingSuiteExt>(domain_size: RingDomainSize) -> MembersSet<S> {
	let data = S::CurveParams::empty_ring_commitment(domain_size);
	MembersSet::deserialize_uncompressed_unchecked(data).expect("embedded empty-ring data is valid")
}

/// Trait for caching ring setup.
#[cfg(feature = "prover")]
pub trait ProverCache<S: RingSuiteExt> {
	/// Get or construct ring setup for the given domain size.
	///
	/// The default implementation reconstructs an owned setup on every call;
	/// cache implementations should override this and serve a borrow of a
	/// value constructed once per domain.
	fn ring_setup(domain_size: RingDomainSize) -> Cow<'static, ark_vrf::ring::RingSetup<S>> {
		Cow::Owned(make_ring_setup::<S>(domain_size))
	}
}

/// Null params cache: always reconstructs values without caching.
pub type NullCache = ();

#[cfg(feature = "prover")]
impl<S: RingSuiteExt> ProverCache<S> for NullCache {}

impl<S: RingSuiteExt> VerifierCache<S> for NullCache {}

/// Fixed-size byte array used to represent a serialized cryptographic object
/// (public key, proof, or signature).
pub trait FixedBytes:
	Clone
	+ Eq
	+ FullCodec
	+ DecodeWithMemTracking
	+ core::fmt::Debug
	+ TypeInfo
	+ MaxEncodedLen
	+ AsRef<[u8]>
	+ AsMut<[u8]>
{
	/// The zero (all-bytes-zero) value, used as an initial buffer for serialization.
	const ZERO: Self;
}
impl<const N: usize> FixedBytes for [u8; N] {
	const ZERO: Self = [0; N];
}

/// Trait providing suite-specific byte array types for ring VRF operations.
///
/// This trait defines the concrete array types used for serialized forms of
/// public keys, proofs, and signatures. Each suite specifies its own sizes.
pub trait RingSuiteExt: RingSuite + Debug + 'static {
	/// VRF input domain separator.
	///
	/// Used to construct the VRF input from context/message data.
	/// Each suite should use a unique domain separator to avoid cross-suite collisions.
	const VRF_INPUT_DOMAIN: &[u8];

	/// Encoded size of a public key.
	const PUBLIC_KEY_SIZE: usize;
	/// Encoded size of MembersSet (Intermediate).
	const MEMBERS_SET_SIZE: usize;
	/// Encoded size of MembersCommitment (Members).
	const MEMBERS_COMMITMENT_SIZE: usize;
	/// Encoded size of StaticChunk (G1 point).
	const STATIC_CHUNK_SIZE: usize;
	/// Encoded size of Signature.
	const SIGNATURE_SIZE: usize;
	/// Compressed size of `ark_vrf::ring::Proof<S>`.
	const RING_PROOF_SIZE: usize;
	/// Compressed size of a single `ark_vrf::Output<S>`.
	const VRF_OUTPUT_SIZE: usize;

	/// Byte array type for encoded public keys.
	type PublicKeyBytes: FixedBytes;
	/// Byte array type for plain VRF signatures.
	type SignatureBytes: FixedBytes;

	/// The curve static data provider for this suite.
	type CurveParams: RingCurveParams;

	/// Cache strategy for ring context (verifier).
	type VerifierCache: VerifierCache<Self>;

	/// Cache strategy for ring setup (prover).
	#[cfg(feature = "prover")]
	type ProverCache: ProverCache<Self>;
}

/// Serialized ring VRF signature size for a given number of contexts.
pub const fn ring_signature_size<S: RingSuiteExt>(contexts_count: u8) -> usize {
	S::RING_PROOF_SIZE + 1 + contexts_count as usize * S::VRF_OUTPUT_SIZE
}

/// [`Get<u32>`] implementation that computes the maximum proof byte length for a suite.
///
/// Used as the bound for `BoundedVec<u8, MaxRingVrfSignatureLen<S>>`.
pub struct MaxRingVrfSignatureLen<S: RingSuiteExt>(PhantomData<S>);

impl<S: RingSuiteExt> Get<u32> for MaxRingVrfSignatureLen<S> {
	fn get() -> u32 {
		ring_signature_size::<S>(MAX_CONTEXTS as u8) as u32
	}
}

macro_rules! impl_common_traits {
	($type_name:ident<S: $bound:path>, $size_expr:expr) => {
		impl_common_traits!($type_name<S: $bound>);

		impl<S: $bound> scale::MaxEncodedLen for $type_name<S> {
			fn max_encoded_len() -> usize {
				$size_expr
			}
		}

		impl<S: $bound> ark_scale::ArkScaleMaxEncodedLen for $type_name<S> {
			fn max_encoded_len(_compress: ark_serialize::Compress) -> usize {
				$size_expr
			}
		}

		impl<S: $bound + 'static> scale_info::TypeInfo for $type_name<S> {
			type Identity = Self;
			fn type_info() -> scale_info::Type {
				let mut info = <ark_scale::ArkScale<Self, { UNCOMPRESSED }>>::type_info();
				info.path = scale_info::Path::new(stringify!($type_name), module_path!());
				info
			}
		}
	};
	($type_name:ident<S: $bound:path>) => {
		impl<S: $bound> Decode for $type_name<S> {
			fn decode<I: ark_scale::scale::Input>(
				input: &mut I,
			) -> Result<Self, ark_scale::scale::Error> {
				let a: ark_scale::ArkScale<Self, { UNCOMPRESSED }> =
					<ark_scale::ArkScale<Self, { UNCOMPRESSED }> as ark_scale::scale::Decode>::decode(
						input,
					)?;
				Ok(a.0)
			}

			fn skip<I: ark_scale::scale::Input>(
				input: &mut I,
			) -> Result<(), ark_scale::scale::Error> {
				<ark_scale::ArkScale<Self, { UNCOMPRESSED }> as ark_scale::scale::Decode>::skip(input)
			}

			fn encoded_fixed_size() -> Option<usize> {
				<ark_scale::ArkScale<Self, { UNCOMPRESSED }> as ark_scale::scale::Decode>::encoded_fixed_size()
			}
		}

		impl<S: $bound> Encode for $type_name<S> {
			fn size_hint(&self) -> usize {
				let a: ark_scale::ArkScaleRef<Self, { UNCOMPRESSED }> = ark_scale::ArkScaleRef(self);
				a.size_hint()
			}

			fn encode_to<O: ark_scale::scale::Output + ?Sized>(&self, dest: &mut O) {
				let a: ark_scale::ArkScaleRef<Self, { UNCOMPRESSED }> = ark_scale::ArkScaleRef(self);
				a.encode_to(dest)
			}

			fn encode(&self) -> alloc::vec::Vec<u8> {
				let a: ark_scale::ArkScaleRef<Self, { UNCOMPRESSED }> = ark_scale::ArkScaleRef(self);
				a.encode()
			}

			fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
				let a: ark_scale::ArkScaleRef<Self, { UNCOMPRESSED }> = ark_scale::ArkScaleRef(self);
				a.using_encoded(f)
			}

			fn encoded_size(&self) -> usize {
				let a: ark_scale::ArkScaleRef<Self, { UNCOMPRESSED }> = ark_scale::ArkScaleRef(self);
				a.encoded_size()
			}
		}

		impl<S: $bound> scale::EncodeLike for $type_name<S> {}

		impl<S: $bound> core::cmp::PartialEq for $type_name<S> {
			fn eq(&self, other: &Self) -> bool {
				self.encode() == other.encode()
			}
		}

		impl<S: $bound> core::cmp::Eq for $type_name<S> {}

		impl<S: $bound> DecodeWithMemTracking for $type_name<S> {}

		impl<S: $bound> DecodeUnchecked for $type_name<S> {
			fn decode_unchecked<I: ark_scale::scale::Input>(
				input: &mut I,
			) -> Result<Self, ark_scale::scale::Error> {
				let a: ark_scale::ArkScale<Self, { UNCOMPRESSED_UNCHECKED }> =
					<ark_scale::ArkScale<Self, { UNCOMPRESSED_UNCHECKED }> as ark_scale::scale::Decode>::decode(
						input,
					)?;
				Ok(a.0)
			}
		}
	};
}

/// Intermediate state while building a ring member set.
///
/// Wraps a [`ark_vrf::ring::VerifierKeyBuilder`] and accumulates members via
/// [`GenerateVerifiable::push_members`]. Finalized into a [`MembersCommitment`]
/// via [`GenerateVerifiable::finish_members`].
#[derive(CanonicalDeserialize, CanonicalSerialize, Clone)]
pub struct MembersSet<S: RingSuiteExt>(pub(crate) ark_vrf::ring::VerifierKeyBuilder<S>);

impl_common_traits!(MembersSet<S: RingSuiteExt>, S::MEMBERS_SET_SIZE);

impl<S: RingSuiteExt> core::fmt::Debug for MembersSet<S> {
	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
		write!(f, "MembersSet")
	}
}

/// Finalized commitment to a set of ring members.
///
/// This is the compact representation used for proof verification. Produced by
/// [`GenerateVerifiable::finish_members`] from a [`MembersSet`].
///
/// The wrapped [`ark_vrf::ring::RingCommitment`] is only the commitment to the
/// ring's fixed columns; it does not carry a KZG verifier key. The trusted setup
/// the membership check runs under is never read from this value: verification
/// rebuilds the [`ark_vrf::ring::RingVerifierKey`] from this commitment and the
/// canonical KZG verifier key shipped with the suite, via
/// [`ark_vrf::ring::verifier_key_from_commitment`]. A member set decoded from an
/// untrusted source can therefore misstate membership but cannot influence the
/// cryptographic setup at all.
///
/// Whether the commitment honestly represents the claimed member set still
/// depends on it having been built from canonical SRS chunks; see the trust
/// requirement on [`GenerateVerifiable::push_members`]. A commitment computed
/// under a different SRS is not a separate concern here: paired with the
/// canonical KZG key at verification time it simply fails the pairing check.
#[derive(CanonicalDeserialize, CanonicalSerialize, Clone)]
pub struct MembersCommitment<S: RingSuiteExt>(pub(crate) ark_vrf::ring::RingCommitment<S>);

impl_common_traits!(MembersCommitment<S: RingSuiteExt>, S::MEMBERS_COMMITMENT_SIZE);

impl<S: RingSuiteExt> core::fmt::Debug for MembersCommitment<S> {
	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
		write!(f, "MembersCommitment")
	}
}

pub(crate) type PublicKey<S> = ark_vrf::Public<S>;

/// Decode a member public key, rejecting the neutral element.
///
/// The identity passes the subgroup check but has no affine coordinates, so the
/// ring backend's `xy().unwrap()` would panic on it during construction. Reject it
/// here so `is_member_valid` and the construction paths agree.
fn decode_member<S: RingSuiteExt>(bytes: &[u8]) -> Result<PublicKey<S>, Error> {
	let pk = PublicKey::<S>::deserialize_canonical(bytes).map_err(|_| Error::InvalidMember)?;
	if pk.0.xy().is_none() {
		return Err(Error::InvalidMember);
	}
	Ok(pk)
}

/// A chunk of the ring builder's static data (a G1 affine point).
///
/// Used by the `lookup` function in [`GenerateVerifiable::push_members`] to supply
/// precomputed SRS points needed to update the ring commitment.
///
/// Decoding validates that the point is on-curve and in the correct subgroup, but cannot
/// establish that it is the canonical SRS point for its index: that reference is the full
/// ring builder params, which is exactly the data externalized through `lookup`. The
/// integrity of the chunk store is therefore the caller's responsibility; see
/// [`GenerateVerifiable::push_members`].
#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
pub struct StaticChunk<S: RingSuiteExt>(pub ark_vrf::ring::G1Affine<S>);

impl_common_traits!(StaticChunk<S: RingSuiteExt>, S::STATIC_CHUNK_SIZE);

/// State produced by [`GenerateVerifiable::open`] and consumed by [`GenerateVerifiable::create`].
///
/// Contains the prover's position in the ring and the keying material needed to
/// generate a ring VRF proof. This is serializable so it can be transferred to
/// an offline/air-gapped signing device.
#[derive(CanonicalSerialize, CanonicalDeserialize, Clone)]
pub struct ProverState<S: RingSuiteExt> {
	pub(crate) domain_size: u32,
	pub(crate) prover_idx: u32,
	pub(crate) prover_key: ark_vrf::ring::RingProverKey<S>,
}

impl_common_traits!(ProverState<S: RingSuiteExt>);

impl<S: RingSuiteExt> core::fmt::Debug for ProverState<S> {
	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
		write!(f, "ProverState")
	}
}

/// VRF outputs within a ring signature.
///
/// Holds one output per context. Backed by a [`ContextVec`] — inline for small
/// counts, heap-allocated only beyond the inline capacity.
///
/// The wire format is a `u8` length prefix followed by the outputs.
struct RingVrfOutputs<S: RingSuiteExt>(ContextVec<ark_vrf::Output<S>>);

impl<S: RingSuiteExt> ark_serialize::Valid for RingVrfOutputs<S> {
	fn check(&self) -> Result<(), ark_serialize::SerializationError> {
		ark_vrf::Output::<S>::batch_check(self.0.iter())
	}
}

impl<S: RingSuiteExt> CanonicalSerialize for RingVrfOutputs<S> {
	fn serialize_with_mode<W: ark_serialize::Write>(
		&self,
		mut writer: W,
		compress: ark_serialize::Compress,
	) -> Result<(), ark_serialize::SerializationError> {
		let slice = self.0.as_slice();
		(slice.len() as u8).serialize_with_mode(&mut writer, compress)?;
		for output in slice {
			output.serialize_with_mode(&mut writer, compress)?;
		}
		Ok(())
	}

	fn serialized_size(&self, compress: ark_serialize::Compress) -> usize {
		let slice = self.0.as_slice();
		let item_size = slice
			.iter()
			.next()
			.map_or(0, |o| o.serialized_size(compress));
		1 + slice.len() * item_size
	}
}

impl<S: RingSuiteExt> CanonicalDeserialize for RingVrfOutputs<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 len = u8::deserialize_with_mode(&mut reader, compress, validate)?;
		if len as usize > MAX_CONTEXTS {
			return Err(ark_serialize::SerializationError::InvalidData);
		}
		let mut outputs = ContextVec::with_capacity(len as usize);
		for _ in 0..len {
			outputs.push(ark_vrf::Output::<S>::deserialize_with_mode(
				&mut reader,
				compress,
				ark_serialize::Validate::No,
			)?);
		}
		if matches!(validate, ark_serialize::Validate::Yes) {
			ark_vrf::Output::<S>::batch_check(outputs.iter())?;
		}
		Ok(Self(outputs))
	}
}

#[derive(CanonicalSerialize, CanonicalDeserialize)]
struct RingVrfSignature<S: RingSuiteExt> {
	proof: ark_vrf::ring::Proof<S>,
	outputs: RingVrfOutputs<S>,
}

#[derive(CanonicalSerialize, CanonicalDeserialize)]
struct PlainSignature<S: RingSuiteExt> {
	proof: ark_vrf::thin::Proof<S>,
}

/// Extension to [`CanonicalDeserialize`] that decodes from a byte slice and
/// rejects any trailing bytes, enforcing a canonical encoding.
///
/// Without this check, valid leading bytes followed by garbage would deserialize
/// successfully, allowing callers to construct multiple distinct byte arrays
/// that decode to the same value (signature/proof malleability).
trait CanonicalDeserializeExt: CanonicalDeserialize {
	fn deserialize_canonical(bytes: &[u8]) -> Result<Self, Error> {
		let mut cursor = bytes;
		let value = Self::deserialize_compressed(&mut cursor).map_err(|_| Error::DecodeError)?;
		if !cursor.is_empty() {
			return Err(Error::DecodeError);
		}
		Ok(value)
	}
}

impl<T: CanonicalDeserialize> CanonicalDeserializeExt for T {}

#[inline(always)]
fn make_alias<S: RingSuiteExt>(output: &ark_vrf::Output<S>) -> Alias {
	output.hash::<32>()
}

/// Recover the canonical KZG (PCS) verifier params from the suite's embedded
/// empty-ring data.
///
/// The value is domain-size independent: the raw KZG key is `(g1, g2, tau*g2)`
/// taken from the suite's shipped (Zcash ceremony) SRS, and domain-size
/// truncation does not touch those points. The claim is pinned by tests in the
/// `bandersnatch` module.
pub fn make_canonical_pcs_vk<S: RingSuiteExt>() -> ark_vrf::ring::PcsVerifierParams<S> {
	// The embedded empty-ring builder carries the canonical params by
	// construction; any domain yields the same value, so use the first.
	RingVrfVerifiable::<S>::start_members(RingDomainSize::VARIANTS[0])
		.0
		.pcs_verifier_params()
}

/// Build the ring [`ark_vrf::ring::RingVerifier`] for a member set.
///
/// The verifier key is rebuilt from the member set's commitment and the
/// canonical KZG verifier key shipped with the suite, then bound to the ring
/// context for `config`. The KZG key is always the suite's canonical one, never
/// anything carried by the (untrusted) member set, so there is nothing to pin: a
/// commitment built under a foreign SRS just fails the downstream pairing check.
fn make_ring_verifier<S: RingSuiteExt>(
	config: RingDomainSize,
	members: &MembersCommitment<S>,
) -> ark_vrf::ring::RingVerifier<S> {
	let verifier_key = ark_vrf::ring::verifier_key_from_commitment::<S>(
		members.0.clone(),
		S::VerifierCache::verifier_params(),
	);
	S::VerifierCache::ring_context(config).ring_verifier(verifier_key)
}

/// Per-item state retained during batch accumulation, so that a failed
/// combined check can be attributed by re-verifying sub-batches without
/// re-parsing the proofs. `verifier` is a handle to the ring verifier of the
/// item's run, shared with the other items of the same ring; `index` is the
/// item's position in the caller's slice (and in the results).
struct BatchEntry<'a, S: RingSuiteExt> {
	index: usize,
	verifier: Rc<ark_vrf::ring::RingVerifier<S>>,
	io: VrfIo<S>,
	message: &'a [u8],
	proof: ark_vrf::ring::Proof<S>,
}

fn verify_sub_batch<S: RingSuiteExt>(entries: &[BatchEntry<'_, S>]) -> bool {
	let mut batch = ark_vrf::ring::BatchVerifier::<S>::new(&entries[0].verifier);
	for entry in entries {
		batch
			.push(&entry.verifier, entry.io, entry.message, &entry.proof)
			.expect("push succeeded for the same arguments in the full batch");
	}
	batch.verify().is_ok()
}

/// Attribute a failed combined check to the responsible items.
///
/// The combined check is a single randomized linear combination and cannot say
/// which item broke it, so `entries` (known to fail as a batch) is bisected,
/// descending only into failing halves: `k` bad items among `n` cost
/// `O(k*log(n/k))` sub-batch checks instead of `n` individual verifications.
fn attribute_batch_failure<S: RingSuiteExt>(
	entries: &[BatchEntry<'_, S>],
	results: &mut [Result<Alias, Error>],
) {
	// Work list of sub-batches known to fail as a batch.
	let mut failing = vec![entries];
	while let Some(entries) = failing.pop() {
		if let [entry] = entries {
			results[entry.index] = Err(Error::VerificationFailed);
			continue;
		}
		let (left, right) = entries.split_at(entries.len() / 2);
		let left_ok = verify_sub_batch(left);
		if !left_ok {
			failing.push(left);
		}
		// A batch of valid proofs always passes (completeness is deterministic),
		// so a failing set with a passing left half pins the failure on the
		// right half: checking it would be redundant.
		if left_ok || !verify_sub_batch(right) {
			failing.push(right);
		}
	}
}

// Multi-ring batch accumulation shared by `batch_validate` and
// `batch_validate_per_item`: each proof enters a single combined check via a
// `RingVerifier` built from its own ring, the KZG SRS being the only shared
// requirement. Returns the combined verifier, `None` when nothing entered it.
//
// `sink` gets one outcome per item, in input order: `Ok` carries the alias
// (provisional until the combined check passes) and the item's `BatchEntry`;
// `Err` reports an item that never entered the batch. `exit_on_first_error`
// stops accumulation at the first `Err`.
fn accumulate_batch<'a, S: RingSuiteExt>(
	proofs: &'a [BatchProofItemFor<RingVrfVerifiable<S>>],
	exit_on_first_error: bool,
	mut sink: impl FnMut(Result<(Alias, BatchEntry<'a, S>), Error>),
) -> Option<ark_vrf::ring::BatchVerifier<S>> {
	let mut verifier: Option<Rc<ark_vrf::ring::RingVerifier<S>>> = None;
	let mut last_ring: Option<(RingDomainSize, &MembersCommitment<S>)> = None;
	// Seeded lazily from the first item's verifier; the KZG verifier key it
	// extracts is shared by every ring regardless of domain size.
	let mut batch_verifier: Option<ark_vrf::ring::BatchVerifier<S>> = None;
	let mut process_item = |index, item: &'a BatchProofItemFor<RingVrfVerifiable<S>>| {
		let BatchProofItem {
			proof,
			config,
			members,
			context,
			message,
		} = item;

		let signature = RingVrfSignature::<S>::deserialize_canonical(proof.as_slice())?;

		let outputs = signature.outputs.0.as_slice();
		if outputs.len() != 1 {
			// The batch verifier only supports single-context proofs.
			return Err(Error::Unsupported);
		}
		let output = outputs[0];

		if last_ring != Some((*config, members)) {
			verifier = Some(Rc::new(make_ring_verifier::<S>(*config, members)));
			last_ring = Some((*config, members));
		}
		let verifier = verifier
			.as_ref()
			.expect("set on the first item and on each ring change");

		let input_msg = [S::VRF_INPUT_DOMAIN, context.as_slice()].concat();
		let input = ark_vrf::Input::<S>::new(&input_msg[..]).expect("H2C can't fail here");
		let io = VrfIo { input, output };

		let batch_verifier =
			batch_verifier.get_or_insert_with(|| ark_vrf::ring::BatchVerifier::<S>::new(verifier));
		batch_verifier
			.push(verifier, io, message, &signature.proof)
			.map_err(|_| Error::VerificationFailed)?;

		Ok((
			make_alias(&output),
			BatchEntry {
				index,
				verifier: verifier.clone(),
				io,
				message,
				proof: signature.proof,
			},
		))
	};

	for (index, item) in proofs.iter().enumerate() {
		let outcome = process_item(index, item);
		let failed = outcome.is_err();
		sink(outcome);
		if failed && exit_on_first_error {
			break;
		}
	}
	batch_verifier
}

/// Generic ring VRF implementation parameterized over the ring suite.
///
/// The curve params provider is obtained from `S::CurveParams`.
pub struct RingVrfVerifiable<S: RingSuiteExt>(PhantomData<S>);

impl<S: RingSuiteExt> GenerateVerifiable for RingVrfVerifiable<S> {
	type Secret = ark_vrf::Secret<S>;
	type Commitment = ProverState<S>;
	type Members = MembersCommitment<S>;
	type Intermediate = MembersSet<S>;
	type Member = S::PublicKeyBytes;
	type Proof = BoundedVec<u8, MaxRingVrfSignatureLen<S>>;
	type Signature = S::SignatureBytes;
	type StaticChunk = StaticChunk<S>;
	type Config = RingDomainSize;

	fn start_members(config: Self::Config) -> Self::Intermediate {
		S::VerifierCache::empty_members_set(config)
	}

	fn push_members(
		intermediate: &mut Self::Intermediate,
		members: impl Iterator<Item = Self::Member>,
		lookup: impl Fn(Range<usize>) -> Result<Vec<Self::StaticChunk>, ()>,
	) -> Result<(), Error> {
		let mut keys = vec![];
		for member in members {
			let pk = decode_member::<S>(member.as_ref())?;
			keys.push(pk.0);
		}
		let loader = |range: Range<usize>| {
			let expected = range.len();
			let items = lookup(range)
				.ok()?
				.into_iter()
				.map(|c| c.0)
				.collect::<Vec<_>>();
			// Guard against a `lookup` that returns the wrong number of chunks: the
			// backend only `debug_assert`s the length, so in release a mismatch would
			// reach the MSM and panic. Returning `None` surfaces `Error::LookupFailed`.
			(items.len() == expected).then_some(items)
		};
		intermediate
			.0
			.append(&keys[..], loader)
			.map_err(|e| match e {
				ark_vrf::Error::SrsLookupFailed => Error::LookupFailed,
				ark_vrf::Error::RingCapacityExceeded => Error::SetFull,
				// The only other failure `append` reports is `InvalidData`, raised for a
				// key the backend cannot map to Twisted Edwards form.
				_ => Error::InvalidMember,
			})
	}

	fn finish_members(intermediate: Self::Intermediate) -> Self::Members {
		let verifier_key = intermediate.0.finalize();
		MembersCommitment(verifier_key.commitment())
	}

	fn new_secret(entropy: Entropy) -> Self::Secret {
		Self::Secret::from_seed(entropy)
	}

	fn member_from_secret(secret: &Self::Secret) -> Self::Member {
		let mut bytes = S::PublicKeyBytes::ZERO;
		secret
			.public()
			.serialize_compressed(bytes.as_mut())
			.expect("fixed-size buffer is large enough");
		bytes
	}

	fn validate_multi_context(
		config: Self::Config,
		proof: &Self::Proof,
		members: &Self::Members,
		contexts: &[&[u8]],
		message: &[u8],
	) -> Result<AliasVec, Error> {
		let ring_verifier = make_ring_verifier::<S>(config, members);

		let signature = RingVrfSignature::<S>::deserialize_canonical(proof.as_slice())?;

		let outputs = signature.outputs.0.as_slice();
		if contexts.len() != outputs.len() {
			return Err(Error::ContextCountMismatch);
		}

		let (ios, aliases): (ContextVec<_>, AliasVec) = contexts
			.iter()
			.zip(outputs.iter().copied())
			.map(|(ctx, output)| {
				let input_msg = [S::VRF_INPUT_DOMAIN, ctx].concat();
				let input = ark_vrf::Input::<S>::new(&input_msg[..]).expect("H2C can't fail here");

				let io = VrfIo { input, output };
				let alias = make_alias(&output);

				(io, alias)
			})
			.collect();

		ark_vrf::Public::<S>::verify(ios, message, &signature.proof, &ring_verifier)
			.map_err(|_| Error::VerificationFailed)?;

		Ok(aliases)
	}

	// All-or-nothing: any per-item error or a failed combined check rejects the
	// whole batch, so accumulation exits at the first error; the aliases are
	// collected directly and nothing is retained for attribution, whose cost is
	// never paid. See `accumulate_batch`.
	fn batch_validate(proofs: &[BatchProofItemFor<Self>]) -> Result<Vec<Alias>, Error> {
		let mut aliases = Vec::with_capacity(proofs.len());
		let mut first_error = None;
		let batch_verifier = accumulate_batch::<S>(proofs, true, |outcome| match outcome {
			Ok((alias, _)) => aliases.push(alias),
			Err(error) => first_error = Some(error),
		});
		if let Some(error) = first_error {
			return Err(error);
		}
		if let Some(batch_verifier) = batch_verifier {
			batch_verifier
				.verify()
				.map_err(|_| Error::VerificationFailed)?;
		}
		Ok(aliases)
	}

	// Per-item: entries are captured during accumulation so that, when the
	// combined check fails, `attribute_batch_failure` can bisect the batch
	// without re-parsing the proofs; the all-valid fast path stays a single
	// combined check. See `accumulate_batch`.
	fn batch_validate_per_item(proofs: &[BatchProofItemFor<Self>]) -> Vec<Result<Alias, Error>> {
		let mut results = Vec::with_capacity(proofs.len());
		let mut entries = Vec::with_capacity(proofs.len());
		let batch_verifier = accumulate_batch::<S>(proofs, false, |outcome| match outcome {
			Ok((alias, entry)) => {
				results.push(Ok(alias));
				entries.push(entry);
			}
			Err(error) => results.push(Err(error)),
		});
		if !entries.is_empty()
			&& batch_verifier
				.expect("initialized when the first entry was pushed")
				.verify()
				.is_err()
		{
			attribute_batch_failure(&entries, &mut results);
		}
		results
	}

	#[cfg(feature = "prover")]
	fn open(
		config: Self::Config,
		member: &Self::Member,
		members: impl Iterator<Item = Self::Member>,
	) -> Result<Self::Commitment, Error> {
		let pks = members
			.map(|m| decode_member::<S>(m.as_ref()).map(|pk| pk.0))
			.collect::<Result<Vec<_>, _>>()?;
		let member = decode_member::<S>(member.as_ref())?;
		let prover_idx = pks
			.iter()
			.position(|&m| m == member.0)
			.ok_or(Error::NotInRing)? as u32;
		let prover_key = S::ProverCache::ring_setup(config)
			.prover_key(&pks)
			.map_err(|e| match e {
				ark_vrf::Error::RingCapacityExceeded => Error::SetFull,
				// The only other failure `prover_key` reports is `InvalidData`, raised
				// for a key the backend cannot map to Twisted Edwards form.
				_ => Error::InvalidMember,
			})?;
		Ok(ProverState {
			domain_size: config.value(),
			prover_idx,
			prover_key,
		})
	}

	#[cfg(feature = "prover")]
	fn create_multi_context(
		commitment: Self::Commitment,
		secret: &Self::Secret,
		contexts: &[&[u8]],
		message: &[u8],
	) -> Result<(Self::Proof, AliasVec), Error> {
		use ark_vrf::ring::Prover;
		if contexts.len() > MAX_CONTEXTS {
			return Err(Error::TooManyContexts);
		}
		let domain_size =
			RingDomainSize::try_from(commitment.domain_size).map_err(|_| Error::DecodeError)?;
		let ring_setup = S::ProverCache::ring_setup(domain_size);
		if commitment.prover_idx >= ring_setup.max_ring_size() as u32 {
			return Err(Error::NotInRing);
		}

		let ring_prover =
			ring_setup.ring_prover(commitment.prover_key, commitment.prover_idx as usize);

		let (ios, aliases, outputs): (ContextVec<_>, AliasVec, ContextVec<_>) = contexts
			.iter()
			.map(|ctx| {
				let input_msg = [S::VRF_INPUT_DOMAIN, ctx].concat();
				let input = ark_vrf::Input::<S>::new(&input_msg[..]).expect("H2C can't fail here");
				let preout = secret.output(input);
				let alias = make_alias(&preout);

				let io = VrfIo {
					input,
					output: preout,
				};

				(io, alias, preout)
			})
			.collect();

		let proof = secret.prove(ios, message, &ring_prover);

		let signature = RingVrfSignature::<S> {
			outputs: RingVrfOutputs(outputs),
			proof,
		};

		let mut buf = vec![];
		signature
			.serialize_compressed(&mut buf)
			.map_err(|_| Error::DecodeError)?;

		let buf = BoundedVec::try_from(buf).map_err(|_| Error::DecodeError)?;
		Ok((buf, aliases))
	}

	fn alias_in_context(secret: &Self::Secret, context: &[u8]) -> Result<Alias, Error> {
		let input_msg = [S::VRF_INPUT_DOMAIN, context].concat();
		let input = ark_vrf::Input::<S>::new(&input_msg[..]).expect("H2C can't fail here");
		let output = secret.output(input);
		let alias = make_alias(&output);
		Ok(alias)
	}

	fn is_member_valid(member: &Self::Member) -> bool {
		decode_member::<S>(member.as_ref()).is_ok()
	}

	fn sign(secret: &Self::Secret, message: &[u8]) -> Result<Self::Signature, Error> {
		use ark_vrf::thin::Prover;
		let proof = secret.prove([], message);
		let signature = PlainSignature::<S> { proof };
		let mut raw = S::SignatureBytes::ZERO;
		signature
			.serialize_compressed(raw.as_mut())
			.map_err(|_| Error::DecodeError)?;
		Ok(raw)
	}

	fn verify_signature(
		signature: &Self::Signature,
		message: &[u8],
		member: &Self::Member,
	) -> bool {
		use ark_vrf::thin::Verifier;
		let Ok(signature) = PlainSignature::<S>::deserialize_canonical(signature.as_ref()) else {
			return false;
		};
		let Ok(public) = decode_member::<S>(member.as_ref()) else {
			return false;
		};
		public.verify([], message, &signature.proof).is_ok()
	}
}