verifiable 0.3.0

// Unit tests use `std` unconditionally, so keep it linked for test builds of the
// no_std configurations (e.g. `no-std-prover` without `std`).
#![cfg_attr(all(not(feature = "std"), not(test)), no_std)]

// The ring proof's zero-knowledge blinding draws randomness via
// `getrandom_or_panic` deep in the proving stack. `std` wires it to the system
// RNG; `no-std-prover` wires it to `getrandom` (targets without an OS entropy
// source must register a `getrandom` custom backend, enforced at link time).
// Without either, a no_std build with `prover` compiles but panics at proof
// generation, so reject it here instead.
#[cfg(all(
	feature = "prover",
	not(feature = "std"),
	not(feature = "no-std-prover")
))]
compile_error!(
	"`prover` on a no_std target requires the `no-std-prover` feature. Without it the ring \
	 prover has no randomness source for the zero-knowledge blinding and panics during proof \
	 generation."
);

extern crate alloc;

use alloc::vec::Vec;

use core::{fmt::Debug, ops::Range};
use parity_scale_codec::{Decode, DecodeWithMemTracking, Encode, FullCodec, MaxEncodedLen};
use scale_info::*;
use smallvec::SmallVec;

#[cfg(feature = "mock")]
pub mod mock;
pub mod ring;

/// SCALE decoding that may skip backend-specific validation (e.g. arkworks
/// curve-point subgroup checks) for values arriving from a trusted source.
///
/// The default `Decode` impls for the ring types ([`ring::MembersSet`],
/// [`ring::MembersCommitment`], [`ring::StaticChunk`], [`ring::ProverState`])
/// validate every curve point — the right behaviour at trust boundaries
/// (extrinsic arguments, XCM payloads, anything crossing an untrusted edge).
/// Reading a value that was already validated on the way in repeats that work
/// for nothing.
///
/// Implementors expose a parallel `decode_unchecked` entry point that reads
/// the exact same bytes without revalidating. The supertrait [`Decode`]
/// expresses that the two paths share the same wire format; only the
/// validation policy differs.
///
/// The default method body just delegates to [`Decode::decode`], which is
/// the correct behaviour for types with no curve content. Backends
/// override with a validation-bypassing path; see
/// [`ring::impl_common_traits`].
///
/// Use only for values that were validated at their ingress point. Do not
/// call on data that arrives from an untrusted source.
pub trait DecodeUnchecked: Sized + Decode {
	fn decode_unchecked<I: parity_scale_codec::Input>(
		input: &mut I,
	) -> Result<Self, parity_scale_codec::Error> {
		Self::decode(input)
	}
}

// Fixed types:

/// Cryptographic identifier for a person within a specific application which deals with people.
/// The underlying crypto should guarantee that all `Alias` values used by a person to represent
/// themself for each `Context` are unlinkable from both their underlying `PersonalId` as well as
/// all other `Alias` values of theirs.
pub type Alias = [u8; 32];

/// Entropy supplied for the creation of a secret key.
pub type Entropy = [u8; 32];

/// Maximum number of contexts the library supports anywhere.
///
/// Wire-format hard limit, enforced by deserializers. Must fit in a `u8`
/// because wire formats encode the count with a single-byte length prefix.
pub const MAX_CONTEXTS: usize = 16;

const _: () = assert!(MAX_CONTEXTS <= u8::MAX as usize);

/// SmallVec sized for one element per context.
///
/// Inline storage covers the common case (up to 3 contexts per proof);
/// counts in 4..=[`MAX_CONTEXTS`] spill to the heap. Used wherever an
/// internal collection scales with the number of contexts (aliases, VRF
/// inputs, VRF outputs).
pub type ContextVec<T> = SmallVec<[T; 3]>;

/// Collection of aliases returned from the multi-context proof methods.
///
/// The single-context default wrappers (`validate`, `create`) rely on this
/// being inline for `N=1` to avoid heap allocation.
pub type AliasVec = ContextVec<Alias>;

/// Failure modes for the operations on [`GenerateVerifiable`].
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Error {
	/// Member bytes don't form a valid public key for this scheme.
	InvalidMember,
	/// Member set has reached capacity.
	SetFull,
	/// Lookup function failed while pushing members.
	LookupFailed,
	/// The prover key is not part of the ring (in `open`).
	NotInRing,
	/// The number of contexts exceeds [`MAX_CONTEXTS`].
	TooManyContexts,
	/// The proof's encoded output count does not match the supplied contexts.
	ContextCountMismatch,
	/// Proof or signature bytes could not be decoded.
	DecodeError,
	/// Cryptographic verification failed (invalid proof or signature).
	VerificationFailed,
	/// The operation does not support the supplied input.
	///
	/// Currently used by the batch validation methods when given a
	/// multi-context proof. Only single-context proofs are batchable today.
	Unsupported,
}

/// A single item in a batch proof validation request.
///
/// Groups together a proof with the configuration and members set (ring) it was
/// created against and the context and message it was created for, so that
/// multiple proofs can be validated in a single batch operation via
/// [`GenerateVerifiable::batch_validate`]. Each item carries its own `config`
/// and `members`, so a single batch may mix proofs from different rings, even
/// rings of different sizes.
#[derive(Clone)]
pub struct BatchProofItem<Proof, Members, Config> {
	/// The ring VRF proof to validate.
	pub proof: Proof,
	/// The configuration (e.g. ring domain size) the proof was created under.
	pub config: Config,
	/// The members set (ring) the proof was created against.
	pub members: Members,
	/// The context under which the proof was created.
	pub context: Vec<u8>,
	/// The message that was signed.
	pub message: Vec<u8>,
}

/// [`BatchProofItem`] specialized to a given [`GenerateVerifiable`] implementation `V`.
pub type BatchProofItemFor<V> = BatchProofItem<
	<V as GenerateVerifiable>::Proof,
	<V as GenerateVerifiable>::Members,
	<V as GenerateVerifiable>::Config,
>;

// The trait. This (alone) must be implemented in its entirely by the Ring-VRF.

/// Trait allowing cryptographic proof of membership of a set with known members under multiple
/// contexts without exposing the underlying member who is proving it and giving an unlinkable
/// deterministic pseudonymic "alias" under each context.
///
/// A `Self::Proof` is created using the `Self::create` function from the `Self::Secret` value
/// associated with a `Self::Member` value who exists within a set of members identified with a
/// `Self::Members` value. The proof can later be validated with the `Self::is_valid` function
/// using the same information used to create it (except the secret, of course!).
///
/// A convenience [`Receipt`] type is provided for typical use cases which bundles the proof along
/// with needed witness information describing the message and alias.
pub trait GenerateVerifiable {
	/// Consolidated value identifying a particular set of members. Corresponds to the Ring Root.
	///
	/// This is envisioned to be stored on-chain and passed between chains.
	type Members: Clone + Eq + PartialEq + FullCodec + Debug + TypeInfo + MaxEncodedLen;

	/// Intermediate value while building a `Self::Members` value. Probably just an unfinished Ring
	/// Root(?).
	///
	/// This is envisioned to be stored on-chain.
	type Intermediate: Clone + Eq + PartialEq + FullCodec + Debug + TypeInfo + MaxEncodedLen;

	/// Encoded value identifying a single member. Corresponds to the user representation of a Public Key.
	type Member: Clone + Eq + PartialEq + FullCodec + Debug + TypeInfo + MaxEncodedLen;

	/// Value with which a member can create a proof of membership. Corresponds to the Secret Key.
	///
	/// This is not envisioned to be used on-chain.
	type Secret: Clone;

	/// A partially-created proof. This is created by the `open` function and utilized by the
	/// `create` function.
	///
	/// This is not envisioned to be used on-chain.
	type Commitment: FullCodec;

	/// A proof of membership in a group, verifiable against `Members`.
	///
	/// Created via the two-step `open`/`create` flow. The verifier learns only the
	/// context-specific `Alias` and the message, not which `Member` produced it.
	///
	/// This is expected to be passed on-chain as a parameter, but never stored.
	type Proof: Clone + Eq + PartialEq + FullCodec + Debug + TypeInfo;

	/// A chunk of precomputed static data used by the `lookup` function when pushing members.
	///
	/// For ring VRF implementations, this is typically a G1 affine point from the SRS.
	///
	/// Decoding only checks well-formedness (e.g. that the point is on the curve and in the
	/// correct subgroup); it cannot check that a chunk is the *right* point from the canonical
	/// setup. See [`Self::push_members`] for the trust requirement this places on the chunk
	/// store.
	type StaticChunk: Clone + Eq + PartialEq + FullCodec + Debug + TypeInfo + MaxEncodedLen;

	/// A signature attributable to a specific `Member`, verifiable against that member's
	/// public key.
	///
	/// Created via `sign`, verified via `verify_signature`.
	type Signature: Clone + Eq + PartialEq + FullCodec + Debug + TypeInfo;

	/// Per-call configuration for the operations below.
	///
	/// Used by implementations that support multiple parameter sets to select
	/// which one applies at each call (for ring VRF: which domain/ring size).
	/// Set to `()` when there is nothing to configure.
	type Config: Clone + Copy;

	/// Begin building a `Members` value.
	fn start_members(config: Self::Config) -> Self::Intermediate;

	/// Introduce a set of new `Member`s into the intermediate value used to build a new `Members`
	/// value.
	///
	/// Duplicate members are accepted; the backend does not deduplicate.
	///
	/// An error is returned if at least one member failed to be pushed. This happens in those
	/// situations:
	/// * the maximum capacity has already been reached
	/// * the member is invalid (can be checked with `is_member_valid`)
	/// * the lookup function is invalid
	///
	/// # Trust requirement on `lookup`
	///
	/// Soundness of the resulting `Members` value depends on `lookup` serving the canonical
	/// precomputed data (for ring VRF: points of the suite's trusted-setup SRS, at the
	/// requested indices). This cannot be verified here: chunks have no compact canonical
	/// reference to check against, and decoding only validates well-formedness. A corrupted
	/// chunk store yields a `Members` value under the canonical setup that misstates the
	/// member set, enabling membership forgery that no later check detects. Integrators
	/// must authenticate the chunk data at ingestion (e.g. hash-check against the published
	/// builder params, restrict writes to genesis/governance).
	fn push_members(
		intermediate: &mut Self::Intermediate,
		members: impl Iterator<Item = Self::Member>,
		lookup: impl Fn(Range<usize>) -> Result<Vec<Self::StaticChunk>, ()>,
	) -> Result<(), Error>;

	/// Consume the `intermediate` value to create a new `Members` value.
	fn finish_members(inter: Self::Intermediate) -> Self::Members;

	/// Create a new secret from some particular `entropy`.
	fn new_secret(entropy: Entropy) -> Self::Secret;

	/// Determine the `Member` value corresponding to a given `Secret`. Basically just the
	/// secret-to-public-key function of the crypto.
	fn member_from_secret(secret: &Self::Secret) -> Self::Member;

	/// First step in creating a proof that `member` exists in a group `members`. The result of this
	/// must be passed into `create` in order to actually create the proof.
	///
	/// This operation uses the potentially large set `members` and as such is expected to be
	/// executed on a device with access to the chain state and is presumably online. The
	/// counterpart operation `create` does not utilize this data. It does require knowledge of the
	/// `Secret` for `member` and as such is practical to conduct on an offline/air-gapped device.
	///
	/// Requires the `prover` feature. The prover paths are heavy and intended for
	/// off-chain use (wallets, signing services), not for runtime execution.
	#[cfg(feature = "prover")]
	fn open(
		config: Self::Config,
		member: &Self::Member,
		members_iter: impl Iterator<Item = Self::Member>,
	) -> Result<Self::Commitment, Error>;

	/// Create a proof of membership with the `commitment` using the given `secret` of the member
	/// of the `commitment`.
	///
	/// The proof will be specific to a given `context` (which determines the resultant `Alias` of
	/// the member in a way unlinkable to the member's original identification and aliases in any
	/// other contexts) together with a provided `message` which entirely at the choice of the
	/// individual.
	///
	/// - `context`: The context under which membership is proven. Proofs over different `[u8]`s
	///   are unlinkable.
	///
	/// Requires the `prover` feature. Intended for off-chain use (wallets, signing
	/// services), not for runtime execution.
	#[cfg(feature = "prover")]
	fn create(
		commitment: Self::Commitment,
		secret: &Self::Secret,
		context: &[u8],
		message: &[u8],
	) -> Result<(Self::Proof, Alias), Error> {
		let (proof, aliases) = Self::create_multi_context(commitment, secret, &[context], message)?;
		Ok((proof, aliases[0]))
	}

	/// Works like [`Self::create`] but takes multiple contexts as an input and returns aliases
	/// corresponding to these contexts.
	///
	/// Calling it will have the same effect as running [`Self::create`] multiple times on each
	/// `context` from the `contexts` but additionally the proof will guarantee that all these
	/// aliases are derived from the correponding contexts using the same `secret`.
	#[cfg(feature = "prover")]
	fn create_multi_context(
		commitment: Self::Commitment,
		secret: &Self::Secret,
		contexts: &[&[u8]],
		message: &[u8],
	) -> Result<(Self::Proof, AliasVec), Error>;

	/// Check whether `proof` is a valid proof of membership in `members` in the given `context`;
	/// if so, ensure that the member is necessarily associated with `alias` in this `context` and
	/// that they elected to opine `message`.
	fn is_valid(
		config: Self::Config,
		proof: &Self::Proof,
		members: &Self::Members,
		context: &[u8],
		alias: &Alias,
		message: &[u8],
	) -> bool {
		match Self::validate(config, proof, members, context, message) {
			Ok(a) => &a == alias,
			Err(_) => false,
		}
	}

	/// Check whether `proof` is a valid proof of membership in `members` in every `context` from the given `contexts`;
	/// if so, ensure that the member is necessarily associated with corresponding `alias` from the given `aliases` in this `context` and
	/// that they elected to opine `message`.
	fn is_valid_multi_context(
		config: Self::Config,
		proof: &Self::Proof,
		members: &Self::Members,
		contexts: &[&[u8]],
		aliases: &[Alias],
		message: &[u8],
	) -> bool {
		match Self::validate_multi_context(config, proof, members, contexts, message) {
			Ok(a) => a.as_slice() == aliases,
			Err(_) => false,
		}
	}

	/// Generate the alias a `secret` would have in a given `context`.
	fn alias_in_context(secret: &Self::Secret, context: &[u8]) -> Result<Alias, Error>;

	/// Like `is_valid`, but `alias` is returned, not provided.
	fn validate(
		config: Self::Config,
		proof: &Self::Proof,
		members: &Self::Members,
		context: &[u8],
		message: &[u8],
	) -> Result<Alias, Error> {
		let result = Self::validate_multi_context(config, proof, members, &[context], message)?;
		Ok(result[0])
	}

	/// Like `is_valid_multi_context`, but aliases are returned, not provided.
	fn validate_multi_context(
		config: Self::Config,
		proof: &Self::Proof,
		members: &Self::Members,
		contexts: &[&[u8]],
		message: &[u8],
	) -> Result<AliasVec, Error>;

	/// Check whether all of the proofs in this batch are valid, returning the `Alias` for each one,
	/// in order of input.
	///
	/// Each [`BatchProofItem`] carries its own `config` and `members` set, so the
	/// proofs in a batch may come from different rings, even rings of different
	/// sizes.
	///
	/// This is all-or-nothing: a single invalid item rejects the whole batch with
	/// an error that does not identify the offending item, and the worst-case cost
	/// stays that of one batched check. Appropriate when the batch has a single
	/// responsible producer (e.g. the proofs of an already-authored block). When
	/// batching proofs from untrusted submitters, use
	/// [`Self::batch_validate_per_item`] instead, so one junk submission cannot
	/// suppress the honest proofs grouped with it.
	///
	/// Currently only supports single-context proofs. Multi-context proofs should be
	/// validated individually via [`Self::validate_multi_context`].
	fn batch_validate(proofs: &[BatchProofItemFor<Self>]) -> Result<Vec<Alias>, Error> {
		proofs
			.iter()
			.map(|item| {
				Self::validate(
					item.config,
					&item.proof,
					&item.members,
					&item.context,
					&item.message,
				)
			})
			.collect()
	}

	/// Like [`Self::batch_validate`], but returns one outcome per item, in input
	/// order, attributing each failure to the item responsible: an invalid,
	/// malformed, or unsupported item never affects the outcome of the others.
	///
	/// Implementations may verify the whole batch in a single combined check and
	/// pay an extra attribution cost only when that check fails, so a batch with
	/// invalid items can cost more than [`Self::batch_validate`] on the same
	/// input. Prefer `batch_validate` when an all-or-nothing verdict suffices and
	/// the worst-case cost matters.
	///
	/// Currently only supports single-context proofs; multi-context proofs are
	/// reported as [`Error::Unsupported`].
	fn batch_validate_per_item(proofs: &[BatchProofItemFor<Self>]) -> Vec<Result<Alias, Error>> {
		proofs
			.iter()
			.map(|item| {
				Self::validate(
					item.config,
					&item.proof,
					&item.members,
					&item.context,
					&item.message,
				)
			})
			.collect()
	}

	/// Check whether `member` is a valid encoded public key for this scheme.
	fn is_member_valid(member: &Self::Member) -> bool;

	/// Make a non-anonymous signature of `message` using `secret`.
	fn sign(secret: &Self::Secret, message: &[u8]) -> Result<Self::Signature, Error>;

	/// Verify a non-anonymous signature of `message` against the given `member`'s public key.
	fn verify_signature(signature: &Self::Signature, message: &[u8], member: &Self::Member)
	-> bool;
}

/// Convenience wrapper bundling a proof with its associated alias and message.
///
/// Provides a simpler API for the common create-then-verify workflow via
/// [`Receipt::create`] and [`Receipt::verify`].
#[derive(Clone, Eq, PartialEq, Encode, Decode, Debug, TypeInfo, DecodeWithMemTracking)]
pub struct Receipt<Gen: GenerateVerifiable> {
	proof: Gen::Proof,
	alias: Alias,
	message: Vec<u8>,
}

impl<Gen: GenerateVerifiable> Receipt<Gen> {
	/// Create a receipt by opening a commitment and producing a proof in one step.
	///
	/// Combines [`GenerateVerifiable::open`] and [`GenerateVerifiable::create`].
	#[cfg(feature = "prover")]
	pub fn create<'a>(
		config: Gen::Config,
		secret: &Gen::Secret,
		members: impl Iterator<Item = Gen::Member>,
		context: &[u8],
		message: Vec<u8>,
	) -> Result<Self, Error>
	where
		Gen::Member: 'a,
	{
		let commitment = Gen::open(config, &Gen::member_from_secret(secret), members)?;
		let (proof, alias) = Gen::create(commitment, secret, context, &message)?;
		Ok(Self {
			proof,
			alias,
			message,
		})
	}
	/// Returns the alias associated with this receipt.
	pub fn alias(&self) -> &Alias {
		&self.alias
	}
	/// Returns the message associated with this receipt.
	pub fn message(&self) -> &[u8] {
		&self.message
	}
	/// Consume the receipt and return the alias and message.
	pub fn into_parts(self) -> (Alias, Vec<u8>) {
		(self.alias, self.message)
	}
	/// Verify the receipt against the given `members` set and `context`.
	///
	/// On success, returns the validated alias and message. On failure, the
	/// receipt is returned in `Err` so the caller can retry verification against
	/// a different `members` set or `context` without rebuilding it.
	pub fn verify(
		self,
		config: Gen::Config,
		members: &Gen::Members,
		context: &[u8],
	) -> Result<(Alias, Vec<u8>), Self> {
		match Gen::validate(config, &self.proof, members, context, &self.message) {
			Ok(alias) => Ok((alias, self.message)),
			Err(_) => Err(self),
		}
	}
	/// Check whether this receipt contains a valid proof for the given `members` and `context`.
	pub fn is_valid(&self, config: Gen::Config, members: &Gen::Members, context: &[u8]) -> bool {
		Gen::is_valid(
			config,
			&self.proof,
			members,
			context,
			&self.alias,
			&self.message,
		)
	}
}