core_utils/circuit/latest/

constraint.rs

//! Constraints attached to a [`Gate::ConstrainPlaintextBits`](crate::circuit::Gate) gate.
//!
//! The gate takes a plaintext bit batch that each peer supplies locally — typically fetched from a
//! URL, so peers may hold different bits — and outputs a batch of the same length satisfying the
//! constraints, which are held as a disjunction of conjunctions ([`ConstraintClause`]). Both sides
//! are plaintext, so a constraint is a pure deterministic predicate: each peer can evaluate it
//! without any secure computation. Constraints therefore carry no secret material; keys and
//! expected values are ordinary plaintext wires.
//!
//! Bit-order convention, matching [`Gate::CompressPlaintextPoint`](crate::circuit::Gate) and the
//! compiler's `Byte`: a byte string is laid out as 8 consecutive bits per byte, least-significant
//! bit first.

use std::collections::BTreeMap;

use ed25519_dalek::{Signature, VerifyingKey};
use serde::{Deserialize, Serialize};
use sha2::{Digest as _, Sha256};

use crate::circuit::{GateIndex, Slice};

/// Nesting allowed in a [`ConstraintExpr`]. Bounds the work a hostile circuit can ask every peer
/// to do while reconciling, and the recursion in validation.
pub const MAX_EXPR_DEPTH: usize = 8;

/// Total nodes allowed in a single [`ConstraintExpr`], for the same reason.
pub const MAX_EXPR_NODES: usize = 64;

#[cfg_attr(test, derive(strum::AsRefStr, strum::VariantNames))]
/// Hash available to [`ConstraintExpr::Digest`].
///
/// Wire-format note: variants must only be appended, never reordered.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
#[repr(C)]
pub enum DigestAlgorithm {
    Sha256,
}

impl DigestAlgorithm {
    pub const fn output_bits(&self) -> u32 {
        match self {
            DigestAlgorithm::Sha256 => 256,
        }
    }

    fn hash(&self, bytes: &[u8]) -> Vec<u8> {
        match self {
            DigestAlgorithm::Sha256 => Sha256::digest(bytes).to_vec(),
        }
    }
}

#[cfg_attr(test, derive(strum::AsRefStr, strum::VariantNames))]
/// Encoding available to [`ConstraintExpr::Decode`].
///
/// Wire-format note: variants must only be appended, never reordered.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
#[repr(C)]
pub enum Encoding {
    /// base64url without padding: RFC 4648 section 5, the alphabet and the omitted padding that
    /// JWS and COSE use.
    Base64UrlNoPad,
}

impl Encoding {
    /// Width of the decoded form in bits, given the width of the encoded form.
    ///
    /// `None` when nothing of that width decodes at all, so an operand that could never be
    /// evaluated is rejected when the gate is validated rather than by every peer at runtime. For
    /// unpadded base64 that is any character count congruent to 1 mod 4: a lone trailing character
    /// carries 6 bits and the byte it would start needs 8.
    pub const fn decoded_bits(&self, encoded_bits: u32) -> Option<u32> {
        match self {
            Encoding::Base64UrlNoPad => {
                if !encoded_bits.is_multiple_of(8) {
                    return None;
                }
                let chars = encoded_bits / 8;
                if chars % 4 == 1 {
                    return None;
                }
                // Exact, not a bound: with padding omitted the character count determines the byte
                // count, which is why this is the variant a fixed-width operand can use.
                Some(8 * (3 * chars / 4))
            }
        }
    }

    /// Decodes, or `None` if `bytes` is not the one canonical encoding of some byte string.
    ///
    /// Strict in both directions that matter here. Only this variant's alphabet is accepted, so
    /// `+`, `/` and `=` are rejected rather than quietly tolerated; and the spare low bits of a
    /// short final group must be zero. Laxness in either would give one payload several encodings,
    /// and peers holding different encodings of the same bytes are distinct candidates as far as
    /// reconciliation is concerned -- an encoding quirk arriving as a disagreement.
    fn decode(&self, bytes: &[u8]) -> Option<Vec<u8>> {
        match self {
            Encoding::Base64UrlNoPad => {
                let mut out = Vec::with_capacity(3 * bytes.len() / 4);
                for group in bytes.chunks(4) {
                    if group.len() == 1 {
                        return None;
                    }
                    let mut acc = 0u32;
                    for byte in group {
                        acc = (acc << 6) | u32::from(base64url_digit(*byte)?);
                    }
                    // A group of n characters carries 6n bits and yields n-1 whole bytes. The
                    // remaining low bits are not part of the output and must be zero.
                    let whole_bytes = group.len() - 1;
                    let spare = 6 * group.len() - 8 * whole_bytes;
                    if acc & ((1 << spare) - 1) != 0 {
                        return None;
                    }
                    acc >>= spare;
                    for i in (0..whole_bytes).rev() {
                        out.push((acc >> (8 * i)) as u8);
                    }
                }
                Some(out)
            }
        }
    }
}

/// One base64url character as its six bits. `None` for anything outside the alphabet, padding
/// included.
const fn base64url_digit(byte: u8) -> Option<u8> {
    match byte {
        b'A'..=b'Z' => Some(byte - b'A'),
        b'a'..=b'z' => Some(byte - b'a' + 26),
        b'0'..=b'9' => Some(byte - b'0' + 52),
        b'-' => Some(62),
        b'_' => Some(63),
        _ => None,
    }
}

#[cfg_attr(test, derive(strum::AsRefStr, strum::VariantNames))]
/// What to do when more than one *distinct* candidate satisfies the clauses.
///
/// Peers agreeing is the ordinary case and is never ambiguous, however many peers there are — this
/// only applies when the satisfying candidates differ from each other, which means the source
/// served different bytes to different peers and every version of them verified.
///
/// Wire-format note: variants must only be appended, never reordered.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[repr(C)]
pub enum OnAmbiguity {
    /// Report failure, as for no satisfying candidate at all: zeroed data and a false success bit.
    ///
    /// The conservative reading, and the right one when the source is meant to be byte-stable:
    /// handing the circuit one of several verifying values silently is the failure mode hardest to
    /// notice.
    ///
    /// It is not the right one for a source that mints per request. A JWS carrying `iat` inside
    /// its signed payload gives two peers two valid responses whose difference no constraint
    /// could have forbidden, so this refuses every computation over such a source rather than
    /// the occasional one; `test_two_valid_jws_from_one_issuer_are_ambiguous` is that case.
    /// The trade between the variants is which single peer gets to misbehave: under `Fail` one
    /// peer contributing a differently-minted valid response denies the computation, and under
    /// `TakeSmallestBits` one peer choosing among responses it can obtain valid signatures for
    /// steers which is used.
    Fail,
    /// Take the smallest candidate.
    ///
    /// Smallest as a *bit vector*, in this module's LSB-first-per-byte order — which is not the
    /// smallest byte string, and differs from it whenever the candidates' low bits do: of `0x41`
    /// and `0x42` this picks `0x42`, whose first bit is 0. Deterministic and independent of the
    /// order peers answer in, which is what it has to be; just not what "smallest" suggests.
    ///
    /// For a source where any correctly-signed answer is acceptable and proceeding beats failing.
    TakeSmallestBits,
}

#[cfg_attr(test, derive(strum::AsRefStr, strum::VariantNames))]
/// How a constraint's operand is built.
///
/// Real signed formats often sign something other than a contiguous run of the response: CMS signs
/// a re-tagged copy of the attribute block, and a detached signature covers a digest of the content
/// rather than the content. Expressing an operand as a small expression rather than a single slice
/// is what makes those reachable, and it costs nothing — this is evaluated on plaintext during
/// reconciliation, so a digest here is a library call rather than thousands of gates.
///
/// JWS needs no reconstruction of its signing input -- that is `b64(header) || "." ||
/// b64(payload)`, a contiguous prefix of the compact serialization, so a slice covers it. What it
/// needs is the other direction: its signature is base64url where the gate wants raw bytes, which
/// is [`ConstraintExpr::Decode`].
///
/// Wire-format note: variants must only be appended, never reordered.
#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[repr(C)]
pub enum ConstraintExpr {
    /// Bits of the gate's input batch.
    Slice(Slice),
    /// A fixed byte string: framing, separators, domain-separation tags.
    Constant(Vec<u8>),
    /// The operands' bits, in order.
    Concat(Vec<ConstraintExpr>),
    /// The digest of another expression, which must be a whole number of bytes.
    Digest {
        algorithm: DigestAlgorithm,
        of: Box<ConstraintExpr>,
    },
    /// A plaintext bit batch on another wire.
    Wire(GateIndex),
    /// Another expression decoded, which must be a whole number of bytes and must be a valid
    /// encoding. Signed formats overwhelmingly transport their signatures in text.
    ///
    /// The one operand that is a predicate as much as a value: bytes that do not decode make this
    /// unevaluable, and an unevaluable operand fails its constraint. So "is well-formed base64url"
    /// needs no constraint of its own.
    Decode {
        encoding: Encoding,
        of: Box<ConstraintExpr>,
    },
}

impl ConstraintExpr {
    /// Slices of the gate input this expression reads, in order.
    pub fn slices(&self) -> Vec<&Slice> {
        match self {
            ConstraintExpr::Slice(slice) => vec![slice],
            ConstraintExpr::Constant(_) | ConstraintExpr::Wire(_) => Vec::new(),
            ConstraintExpr::Concat(parts) => {
                parts.iter().flat_map(ConstraintExpr::slices).collect()
            }
            ConstraintExpr::Digest { of, .. } | ConstraintExpr::Decode { of, .. } => of.slices(),
        }
    }

    /// Wires this expression reads, in order. May repeat.
    pub fn wires(&self) -> Vec<GateIndex> {
        match self {
            ConstraintExpr::Wire(wire) => vec![*wire],
            ConstraintExpr::Slice(_) | ConstraintExpr::Constant(_) => Vec::new(),
            ConstraintExpr::Concat(parts) => parts.iter().flat_map(ConstraintExpr::wires).collect(),
            ConstraintExpr::Digest { of, .. } | ConstraintExpr::Decode { of, .. } => of.wires(),
        }
    }

    /// Mutable references to the wires this expression reads, in the same order as [`Self::wires`].
    pub fn wires_mut(&mut self) -> Vec<&mut GateIndex> {
        match self {
            ConstraintExpr::Wire(wire) => vec![wire],
            ConstraintExpr::Slice(_) | ConstraintExpr::Constant(_) => Vec::new(),
            ConstraintExpr::Concat(parts) => parts
                .iter_mut()
                .flat_map(ConstraintExpr::wires_mut)
                .collect(),
            ConstraintExpr::Digest { of, .. } | ConstraintExpr::Decode { of, .. } => of.wires_mut(),
        }
    }

    pub fn depth(&self) -> usize {
        match self {
            ConstraintExpr::Slice(_) | ConstraintExpr::Constant(_) | ConstraintExpr::Wire(_) => 1,
            ConstraintExpr::Concat(parts) => {
                1 + parts.iter().map(ConstraintExpr::depth).max().unwrap_or(0)
            }
            ConstraintExpr::Digest { of, .. } | ConstraintExpr::Decode { of, .. } => 1 + of.depth(),
        }
    }

    pub fn node_count(&self) -> usize {
        match self {
            ConstraintExpr::Slice(_) | ConstraintExpr::Constant(_) | ConstraintExpr::Wire(_) => 1,
            ConstraintExpr::Concat(parts) => {
                1 + parts.iter().map(ConstraintExpr::node_count).sum::<usize>()
            }
            ConstraintExpr::Digest { of, .. } | ConstraintExpr::Decode { of, .. } => {
                1 + of.node_count()
            }
        }
    }

    /// Length in bits, given a way to look up how wide a wire is.
    ///
    /// `Option` rather than a plain `u32` because a wire may not resolve, and to leave room for
    /// operands whose width is only known once the bytes are in hand -- parsing a DER field, say.
    /// Validation checks what it can and defers the rest.
    pub fn static_len<F>(&self, wire_bits: &F) -> Option<u32>
    where
        F: Fn(GateIndex) -> Option<u32>,
    {
        match self {
            ConstraintExpr::Slice(slice) => Some(slice.len()),
            ConstraintExpr::Constant(bytes) => u32::try_from(8 * bytes.len()).ok(),
            ConstraintExpr::Wire(wire) => wire_bits(*wire),
            ConstraintExpr::Concat(parts) => parts.iter().try_fold(0u32, |acc, part| {
                part.static_len(wire_bits)
                    .and_then(|len| acc.checked_add(len))
            }),
            ConstraintExpr::Digest { algorithm, .. } => Some(algorithm.output_bits()),
            ConstraintExpr::Decode { encoding, of } => of
                .static_len(wire_bits)
                .and_then(|bits| encoding.decoded_bits(bits)),
        }
    }

    /// Evaluates against the gate's input batch and the values of the wires it reads.
    ///
    /// `None` when the expression cannot be evaluated: a slice running past the batch, a wire with
    /// no value, a digest or a decode over a partial byte, or bytes that are not a valid encoding
    /// of anything.
    ///
    /// `wires` is a `BTreeMap` for size rather than for order. It holds one entry per wire operand
    /// — a handful at most, and `MAX_EXPR_NODES` caps it at 64 — so an ordered map on `u32`
    /// keys beats building a hash state and paying SipHash per lookup. Nothing here iterates
    /// it, so the ordering is not load-bearing today; keeping it ordered is insurance for a
    /// path where every peer must agree bit for bit, should anyone later log, hash or serialise
    /// the wire set.
    pub fn eval(&self, bits: &[bool], wires: &BTreeMap<GateIndex, Vec<bool>>) -> Option<Vec<bool>> {
        match self {
            ConstraintExpr::Slice(slice) => slice
                .get_indices()
                .into_iter()
                .map(|i| bits.get(i as usize).copied())
                .collect(),
            ConstraintExpr::Constant(bytes) => Some(bytes_to_bits(bytes)),
            ConstraintExpr::Wire(wire) => wires.get(wire).cloned(),
            ConstraintExpr::Concat(parts) => {
                let mut out = Vec::new();
                for part in parts {
                    out.extend(part.eval(bits, wires)?);
                }
                Some(out)
            }
            ConstraintExpr::Digest { algorithm, of } => {
                let inner = of.eval(bits, wires)?;
                Some(bytes_to_bits(&algorithm.hash(&bits_to_bytes(&inner)?)))
            }
            ConstraintExpr::Decode { encoding, of } => {
                let inner = of.eval(bits, wires)?;
                Some(bytes_to_bits(&encoding.decode(&bits_to_bytes(&inner)?)?))
            }
        }
    }
}

#[cfg_attr(test, derive(strum::AsRefStr, strum::VariantNames))]
/// Which way a [`PlaintextBitConstraint::Comparison`] bounds its left operand.
///
/// Wire-format note: variants must only be appended, never reordered.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
#[repr(C)]
pub enum Relation {
    /// `lhs <= rhs`.
    AtMost,
    /// `lhs >= rhs`.
    AtLeast,
}

#[cfg_attr(test, derive(strum::AsRefStr, strum::VariantNames))]
/// Signature scheme used by [`PlaintextBitConstraint::Signature`].
///
/// Wire-format note: variants must only be appended, never reordered.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
#[repr(C)]
pub enum SignatureScheme {
    Ed25519,
}

impl SignatureScheme {
    /// Length of a signature, in bits.
    pub const fn signature_bits(&self) -> u32 {
        match self {
            SignatureScheme::Ed25519 => 512,
        }
    }

    /// Length of a public key, in bits.
    pub const fn public_key_bits(&self) -> u32 {
        match self {
            SignatureScheme::Ed25519 => 256,
        }
    }
}

#[cfg_attr(test, derive(strum::AsRefStr, strum::VariantNames))]
/// A predicate that the bits entering a [`Gate::ConstrainPlaintextBits`](crate::circuit::Gate) gate
/// must satisfy.
///
/// Operands are [`ConstraintExpr`]s, so a constraint can name what was actually signed rather than
/// only a contiguous run of the response. Wires read by an expression must themselves be values the
/// peers already agree on -- a key read from an unconstrained local input only moves the problem up
/// one level.
///
/// Wire-format note: variants must only be appended, never reordered.
#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[repr(C)]
pub enum PlaintextBitConstraint {
    /// `signature` is a valid `scheme` signature of `message` under `public_key`.
    Signature {
        scheme: SignatureScheme,
        signature: ConstraintExpr,
        message: ConstraintExpr,
        public_key: ConstraintExpr,
    },
    /// The two operands are equal.
    Equality {
        bits: ConstraintExpr,
        expected: ConstraintExpr,
    },
    /// `lhs` is ordered against `rhs` as **big-endian byte strings of equal length**, which is
    /// what bounds a timestamp or a sequence number carried as text.
    ///
    /// Bytes, deliberately, and not the bit vector this module otherwise works in: LSB-first
    /// per byte compares the low bits of each byte first, and the two orders disagree -- of
    /// `"...001"` and `"...002"` the byte order says the first is smaller and the bit order says
    /// the second is. The same trap as [`OnAmbiguity::TakeSmallestBits`], and here it would mean
    /// accepting a value the bound was meant to exclude.
    ///
    /// Equal length is required rather than zero-padded, because it is what makes the comparison
    /// unambiguous: for equal-length operands, lexicographic order over bytes *is* numeric order,
    /// so fixed-width ASCII decimal needs no parsing. Unequal lengths would leave "shorter means
    /// smaller" and "shorter is zero-extended" both plausible, so they are refused instead.
    ///
    /// A comparison does not count towards a clause's coverage. It bounds its operand rather than
    /// pinning it, and ten bytes constrained only by `>= T` still leave a peer a wide range to
    /// vary in.
    Comparison {
        relation: Relation,
        lhs: ConstraintExpr,
        rhs: ConstraintExpr,
    },
}

impl PlaintextBitConstraint {
    /// The constraint's operands, in wire order.
    pub fn operands(&self) -> Vec<&ConstraintExpr> {
        match self {
            PlaintextBitConstraint::Signature {
                signature,
                message,
                public_key,
                ..
            } => vec![signature, message, public_key],
            PlaintextBitConstraint::Equality { bits, expected } => vec![bits, expected],
            PlaintextBitConstraint::Comparison { lhs, rhs, .. } => vec![lhs, rhs],
        }
    }

    fn operands_mut(&mut self) -> Vec<&mut ConstraintExpr> {
        match self {
            PlaintextBitConstraint::Signature {
                signature,
                message,
                public_key,
                ..
            } => vec![signature, message, public_key],
            PlaintextBitConstraint::Equality { bits, expected } => vec![bits, expected],
            PlaintextBitConstraint::Comparison { lhs, rhs, .. } => vec![lhs, rhs],
        }
    }

    /// The operands whose bytes this constraint *pins*, and which therefore count towards a
    /// clause's coverage.
    ///
    /// Not the same as the operands it reads. Reading a byte proves nothing about it; coverage is
    /// meant to answer "could a peer vary this byte and still satisfy the clause?", and only an
    /// operand the constraint actually determines answers no.
    ///
    /// The distinction is load-bearing for `Signature`. A signature's `public_key` is its
    /// *authority*, not something it pins: "this key signed this message" says nothing about the
    /// key being the right one. Counting it would let a clause authenticate itself — a peer puts a
    /// key, a message and a matching signature in its own proposal, every byte is read, and the
    /// gate reports success on data that peer signed for itself. Excluding the key means those
    /// bytes are uncovered unless something else in the clause pins them, which is exactly the
    /// question that needed asking. It also leaves the legitimate shape working: a key carried in
    /// the response and bound by a second constraint to a trusted root is covered by that
    /// constraint.
    ///
    /// Note the signature and the message are covered *regardless* of where the key comes from.
    /// Refusing to cover them when the key is sliced from the batch would be redundant — the key's
    /// own bytes are already uncovered, so the clause is refused unless something anchors them —
    /// and it would break the legitimate shape: a key carried in the response and pinned by a
    /// second constraint leaves the signature and message covered by this one.
    ///
    /// `Equality` is the same question without the asymmetry: a side is pinned by the other only
    /// if the other is anchored. Two slices of the batch compared against each other pin neither,
    /// since any pair that happens to match satisfies it.
    pub fn covering_operands(&self) -> Vec<&ConstraintExpr> {
        match self {
            PlaintextBitConstraint::Signature {
                signature, message, ..
            } => vec![signature, message],
            PlaintextBitConstraint::Equality { bits, expected } => {
                match (bits.slices().is_empty(), expected.slices().is_empty()) {
                    (true, _) => vec![expected],
                    (_, true) => vec![bits],
                    _ => Vec::new(),
                }
            }
            // A comparison bounds rather than pins; see the variant's docs.
            PlaintextBitConstraint::Comparison { .. } => Vec::new(),
        }
    }

    /// Slices of the gate input this constraint reads, in order.
    pub fn slices(&self) -> Vec<&Slice> {
        self.operands()
            .into_iter()
            .flat_map(ConstraintExpr::slices)
            .collect()
    }

    /// Wires this constraint reads, in order.
    pub fn wires(&self) -> Vec<GateIndex> {
        self.operands()
            .into_iter()
            .flat_map(ConstraintExpr::wires)
            .collect()
    }

    /// Mutable references to the wires this constraint reads, in the same order as [`Self::wires`].
    pub fn wires_mut(&mut self) -> Vec<&mut GateIndex> {
        self.operands_mut()
            .into_iter()
            .flat_map(ConstraintExpr::wires_mut)
            .collect()
    }

    /// Checks the constraint against `bits`, the gate's input batch, and the values of the wires it
    /// reads.
    ///
    /// Returns `false` rather than erroring on anything malformed -- an unevaluable operand, a
    /// public key off the curve -- since that is a failed constraint, not a broken circuit.
    pub fn is_satisfied(&self, bits: &[bool], wires: &BTreeMap<GateIndex, Vec<bool>>) -> bool {
        match self {
            PlaintextBitConstraint::Signature {
                scheme,
                signature,
                message,
                public_key,
            } => {
                let (Some(signature), Some(message), Some(public_key)) = (
                    signature.eval(bits, wires),
                    message.eval(bits, wires),
                    public_key.eval(bits, wires),
                ) else {
                    return false;
                };
                let (Some(signature), Some(message), Some(public_key)) = (
                    bits_to_bytes(&signature),
                    bits_to_bytes(&message),
                    bits_to_bytes(&public_key),
                ) else {
                    return false;
                };
                match scheme {
                    SignatureScheme::Ed25519 => {
                        let (Ok(public_key), Ok(signature)) = (
                            <[u8; 32]>::try_from(public_key),
                            <[u8; 64]>::try_from(signature),
                        ) else {
                            return false;
                        };
                        match VerifyingKey::from_bytes(&public_key) {
                            Ok(key) => key
                                .verify_strict(&message, &Signature::from_bytes(&signature))
                                .is_ok(),
                            Err(_) => false,
                        }
                    }
                }
            }
            PlaintextBitConstraint::Equality {
                bits: lhs,
                expected,
            } => match (lhs.eval(bits, wires), expected.eval(bits, wires)) {
                (Some(lhs), Some(rhs)) => lhs == rhs,
                _ => false,
            },
            PlaintextBitConstraint::Comparison { relation, lhs, rhs } => {
                let (Some(lhs), Some(rhs)) = (lhs.eval(bits, wires), rhs.eval(bits, wires)) else {
                    return false;
                };
                // Through bytes, which is where the ordering is defined. `Vec<u8>` compares
                // lexicographically, so this is the big-endian reading, and equal length makes it
                // the numeric one too.
                let (Some(lhs), Some(rhs)) = (bits_to_bytes(&lhs), bits_to_bytes(&rhs)) else {
                    return false;
                };
                if lhs.len() != rhs.len() {
                    return false;
                }
                match relation {
                    Relation::AtMost => lhs <= rhs,
                    Relation::AtLeast => lhs >= rhs,
                }
            }
        }
    }
}

/// A conjunction of constraints.
///
/// A gate holds a disjunction of these, so its constraints form a disjunctive normal form: the gate
/// is satisfied when *some* clause is, and a clause is satisfied when *all* of its constraints are.
/// A builder writes an alternative — a second accepted response shape, a fallback signing key — by
/// adding a clause, rather than by chaining a second gate over the same input, which would
/// reconcile the peers twice and could settle on a different candidate each time.
#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct ConstraintClause(Vec<PlaintextBitConstraint>);

impl ConstraintClause {
    pub fn new(constraints: Vec<PlaintextBitConstraint>) -> Self {
        Self(constraints)
    }

    pub fn constraints(&self) -> &[PlaintextBitConstraint] {
        &self.0
    }

    pub fn is_empty(&self) -> bool {
        self.0.is_empty()
    }

    /// Wires this clause's constraints read, in order. May repeat.
    pub fn wires(&self) -> Vec<GateIndex> {
        self.0
            .iter()
            .flat_map(PlaintextBitConstraint::wires)
            .collect()
    }

    /// Mutable references to the wires this clause's constraints read, in the same order as
    /// [`Self::wires`].
    pub fn wires_mut(&mut self) -> Vec<&mut GateIndex> {
        self.0
            .iter_mut()
            .flat_map(PlaintextBitConstraint::wires_mut)
            .collect()
    }

    /// Checks every constraint in the clause against `bits`, the gate's input batch, and the
    /// values of the wires they read. Keyed by wire rather than positional, so a constraint that
    /// reads the same wire twice, or reads them in a different order, needs no special handling.
    pub fn is_satisfied(&self, bits: &[bool], wires: &BTreeMap<GateIndex, Vec<bool>>) -> bool {
        self.0
            .iter()
            .all(|constraint| constraint.is_satisfied(bits, wires))
    }
}

/// Unpacks bytes into bits, least-significant bit first.
fn bytes_to_bits(bytes: &[u8]) -> Vec<bool> {
    bytes
        .iter()
        .flat_map(|byte| (0..8).map(move |i| (byte >> i) & 1u8 == 1u8))
        .collect()
}

/// Packs bits into bytes, least-significant bit first. `None` on a partial trailing byte: an
/// operand that is not a whole number of bytes cannot be signed over or hashed.
fn bits_to_bytes(bits: &[bool]) -> Option<Vec<u8>> {
    if !bits.len().is_multiple_of(8) {
        return None;
    }
    Some(
        bits.chunks(8)
            .map(|chunk| {
                chunk
                    .iter()
                    .enumerate()
                    .fold(0u8, |acc, (i, bit)| acc | (u8::from(*bit) << i))
            })
            .collect(),
    )
}

#[cfg(test)]
mod tests {
    use ed25519_dalek::{Signer, SigningKey};

    use super::*;

    fn bytes_to_bits(bytes: &[u8]) -> Vec<bool> {
        bytes
            .iter()
            .flat_map(|byte| (0..8).map(move |i| (byte >> i) & 1u8 == 1u8))
            .collect()
    }

    /// `message || signature`, the layout a signed URL response would arrive in.
    fn signed_batch(key: &SigningKey, message: &[u8]) -> (Vec<bool>, Vec<bool>) {
        let signature = key.sign(message);
        let mut bits = bytes_to_bits(message);
        bits.extend(bytes_to_bits(&signature.to_bytes()));
        (bits, bytes_to_bits(key.verifying_key().as_bytes()))
    }

    fn slice(start: u32, size: u32) -> ConstraintExpr {
        ConstraintExpr::Slice(Slice::range(start, size, 1).unwrap())
    }

    /// The key on wire 0.
    fn wires(public_key: &[bool]) -> BTreeMap<GateIndex, Vec<bool>> {
        BTreeMap::from([(0, public_key.to_vec())])
    }

    fn signature_constraint(message_bytes: u32) -> PlaintextBitConstraint {
        PlaintextBitConstraint::Signature {
            scheme: SignatureScheme::Ed25519,
            signature: slice(8 * message_bytes, 512),
            message: slice(0, 8 * message_bytes),
            public_key: ConstraintExpr::Wire(0),
        }
    }

    #[test]
    fn test_signature_constraint() {
        let key = SigningKey::from_bytes(&[7u8; 32]);
        let message = b"{\"price\":42}";
        let (bits, public_key) = signed_batch(&key, message);
        let constraint = signature_constraint(message.len() as u32);

        assert!(constraint.is_satisfied(&bits, &wires(&public_key)));

        // Flipping any message bit invalidates the signature.
        let mut tampered = bits.clone();
        tampered[3] = !tampered[3];
        assert!(!constraint.is_satisfied(&tampered, &wires(&public_key)));

        // So does verifying under a different key.
        let other = SigningKey::from_bytes(&[9u8; 32]);
        let other_key = bytes_to_bits(other.verifying_key().as_bytes());
        assert!(!constraint.is_satisfied(&bits, &wires(&other_key)));
    }

    #[test]
    fn test_signature_constraint_rejects_malformed_key() {
        let key = SigningKey::from_bytes(&[7u8; 32]);
        let message = b"{\"price\":42}";
        let (bits, _) = signed_batch(&key, message);
        // All-ones is not a canonical compressed Edwards point.
        let public_key = vec![true; 256];
        assert!(
            !signature_constraint(message.len() as u32).is_satisfied(&bits, &wires(&public_key))
        );
    }

    #[test]
    fn test_equality_constraint() {
        let bits = bytes_to_bits(b"header:body");
        let constraint = PlaintextBitConstraint::Equality {
            bits: slice(0, 48),
            expected: ConstraintExpr::Wire(0),
        };
        assert!(constraint.is_satisfied(&bits, &wires(&bytes_to_bits(b"header"))));
        assert!(!constraint.is_satisfied(&bits, &wires(&bytes_to_bits(b"HEADER"))));
    }

    #[test]
    fn test_bits_to_bytes_is_lsb_first() {
        assert_eq!(
            bits_to_bytes(&bytes_to_bits(&[0x01, 0x80, 0xa5])).unwrap(),
            [0x01, 0x80, 0xa5]
        );
        // A partial trailing byte cannot be signed over or hashed.
        assert_eq!(bits_to_bytes(&[true; 4]), None);
    }

    /// The shape that motivated expressions: a signature over something assembled from the
    /// response rather than a contiguous run of it -- here a constant prefix, a slice, and a digest
    /// of another slice, which is the CMS/JWS pattern in miniature.
    #[test]
    fn test_signature_over_a_composed_message() {
        let key = SigningKey::from_bytes(&[7u8; 32]);
        let payload = b"{\"price\":42}";

        // The batch is `payload || signature`, and what is signed is `0x31 || H(payload)`.
        let signed = {
            let mut signed = vec![0x31u8];
            signed.extend(Sha256::digest(payload));
            signed
        };
        let mut bits = bytes_to_bits(payload);
        bits.extend(bytes_to_bits(&key.sign(&signed).to_bytes()));

        let constraint = PlaintextBitConstraint::Signature {
            scheme: SignatureScheme::Ed25519,
            signature: slice(8 * payload.len() as u32, 512),
            message: ConstraintExpr::Concat(vec![
                ConstraintExpr::Constant(vec![0x31]),
                ConstraintExpr::Digest {
                    algorithm: DigestAlgorithm::Sha256,
                    of: Box::new(slice(0, 8 * payload.len() as u32)),
                },
            ]),
            public_key: ConstraintExpr::Wire(0),
        };
        let public_key = bytes_to_bits(key.verifying_key().as_bytes());
        assert!(constraint.is_satisfied(&bits, &wires(&public_key)));

        // The digest binds the payload, so tampering with it still breaks the signature even
        // though no slice of the payload is signed directly.
        let mut tampered = bits.clone();
        tampered[3] = !tampered[3];
        assert!(!constraint.is_satisfied(&tampered, &wires(&public_key)));
    }

    /// Binding a digest to a value carried elsewhere in the response -- the CMS `messageDigest`
    /// attribute pattern.
    #[test]
    fn test_equality_against_a_digest() {
        let content = b"the content";
        let mut bits = bytes_to_bits(content);
        bits.extend(bytes_to_bits(&Sha256::digest(content)));

        let constraint = PlaintextBitConstraint::Equality {
            bits: slice(8 * content.len() as u32, 256),
            expected: ConstraintExpr::Digest {
                algorithm: DigestAlgorithm::Sha256,
                of: Box::new(slice(0, 8 * content.len() as u32)),
            },
        };
        assert!(constraint.is_satisfied(&bits, &BTreeMap::new()));

        let mut tampered = bits.clone();
        tampered[0] = !tampered[0];
        assert!(!constraint.is_satisfied(&tampered, &BTreeMap::new()));
    }

    #[test]
    fn test_static_len_adds_up() {
        let expr = ConstraintExpr::Concat(vec![
            ConstraintExpr::Constant(vec![0u8; 3]),
            slice(0, 5),
            ConstraintExpr::Digest {
                algorithm: DigestAlgorithm::Sha256,
                of: Box::new(ConstraintExpr::Wire(0)),
            },
            ConstraintExpr::Wire(1),
        ]);
        // 24 constant + 5 slice + 256 digest + 7 wire
        assert_eq!(
            expr.static_len(&|wire| Some(wire + 7)),
            Some(24 + 5 + 256 + 8)
        );
        // A wire whose width is unknown makes the whole length unknown, rather than wrong.
        assert_eq!(expr.static_len(&|_| None), None);
    }

    #[test]
    fn test_eval_refuses_a_slice_past_the_batch() {
        assert_eq!(slice(0, 16).eval(&[true; 8], &BTreeMap::new()), None);
    }

    #[test]
    fn test_eval_refuses_a_digest_over_a_partial_byte() {
        let expr = ConstraintExpr::Digest {
            algorithm: DigestAlgorithm::Sha256,
            of: Box::new(slice(0, 4)),
        };
        assert_eq!(expr.eval(&[true; 8], &BTreeMap::new()), None);
    }

    #[test]
    fn test_depth_and_node_count() {
        let expr = ConstraintExpr::Concat(vec![
            slice(0, 1),
            ConstraintExpr::Digest {
                algorithm: DigestAlgorithm::Sha256,
                of: Box::new(ConstraintExpr::Concat(vec![slice(1, 1), slice(2, 1)])),
            },
        ]);
        assert_eq!(expr.depth(), 4);
        assert_eq!(expr.node_count(), 6);
    }

    /// A real JWS, produced once from the seed `[7u8; 32]`:
    ///
    /// ```python
    /// import base64
    /// from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey
    /// b64u = lambda b: base64.urlsafe_b64encode(b).rstrip(b"=")
    /// sk = Ed25519PrivateKey.from_private_bytes(bytes([7] * 32))
    /// si = b64u(b'{"alg":"EdDSA"}') + b"." + b64u(b'{"iat":1756100000,"px":"0000004242"}')
    /// jws = si + b"." + b64u(sk.sign(si))
    /// ```
    const JWS: &[u8] = b"eyJhbGciOiJFZERTQSJ9.eyJpYXQiOjE3NTYxMDAwMDAsInB4IjoiMDAwMDAwNDI0MiJ9.\
                         ZdO1q9RcSfUrdq8UhqZYHVNBHp1OsDLgKG16bQDd-txuigbHkeuG-Bqbu335MrjoPL5Ssq6e\
                         3mJiJpXOTW6nCw";

    /// The compact serialization's three fields, in bytes: `b64u(header)`, `b64u(payload)`,
    /// `b64u(signature)`, with a `.` between each pair.
    const JWS_SIGNING_INPUT_BYTES: u32 = 20 + 1 + 48;
    const JWS_SIGNATURE_BYTES: u32 = 86;

    /// The constraint a JWS actually needs: the signing input is a contiguous prefix, and the
    /// signature is that prefix's text-encoded signature sitting after the second `.`.
    fn jws_constraint() -> PlaintextBitConstraint {
        PlaintextBitConstraint::Signature {
            scheme: SignatureScheme::Ed25519,
            signature: ConstraintExpr::Decode {
                encoding: Encoding::Base64UrlNoPad,
                of: Box::new(slice(
                    8 * (JWS_SIGNING_INPUT_BYTES + 1),
                    8 * JWS_SIGNATURE_BYTES,
                )),
            },
            message: slice(0, 8 * JWS_SIGNING_INPUT_BYTES),
            public_key: ConstraintExpr::Wire(0),
        }
    }

    #[test]
    fn test_jws_verifies_through_a_decoded_signature() {
        let key = SigningKey::from_bytes(&[7u8; 32]);
        let public_key = bytes_to_bits(key.verifying_key().as_bytes());
        assert_eq!(JWS.len(), 156);
        let bits = bytes_to_bits(JWS);

        assert!(jws_constraint().is_satisfied(&bits, &wires(&public_key)));

        // The signature covers the encoded signing input, so flipping a character of the payload
        // segment invalidates it -- no decoding of the payload required.
        let mut tampered = JWS.to_vec();
        tampered[60] ^= 0x01;
        assert!(!jws_constraint().is_satisfied(&bytes_to_bits(&tampered), &wires(&public_key)));
    }

    /// A signature that is not valid base64url makes its operand unevaluable, and an unevaluable
    /// operand fails the constraint. This is the property that lets a decoder be an operand and a
    /// predicate at once: nothing has to check well-formedness separately.
    #[test]
    fn test_a_signature_that_does_not_decode_fails_the_constraint() {
        let key = SigningKey::from_bytes(&[7u8; 32]);
        let public_key = bytes_to_bits(key.verifying_key().as_bytes());

        for (what, byte) in [
            ("padding", b'='),
            ("standard alphabet", b'+'),
            ("junk", b'!'),
        ] {
            let mut body = JWS.to_vec();
            body[80] = byte;
            assert!(
                !jws_constraint().is_satisfied(&bytes_to_bits(&body), &wires(&public_key)),
                "a {what} character should not decode"
            );
        }
    }

    /// The same issuer and price, minted in November 2023 -- a token a peer could replay.
    const JWS_STALE: &[u8] = b"eyJhbGciOiJFZERTQSJ9.eyJpYXQiOjE3MDAwMDAwMDAsInB4IjoiMDAwMDAwNDI0\
                               MiJ9.Sp-OEJIDpCKuVEuTyxKkMZyNP-2pI86wCfWxN59KPONfJBNC4ILVEMSOdLhl\
                               kjPEu4XYEgzIyHNoHFbyHQ8cCg";

    /// `iat` sits at payload bytes 7..17, which no operand can address directly -- an expression
    /// reads slices of the *batch*, and nothing takes a sub-range of a decoded operand.
    ///
    /// What makes it reachable is that base64 groups are independent: cut the encoded form at a
    /// multiple of four characters and that piece decodes on its own. Payload bytes 6..18 are
    /// groups 2..5, so encoded characters 8..24 -- batch bytes 29..45 -- decode to exactly
    /// `:1756100000,`, the digits with their two delimiters. The slop is the framing, which is the
    /// best case: a bound carrying the same framing is comparing the digits and checking the field
    /// boundaries at once.
    fn iat_window() -> ConstraintExpr {
        ConstraintExpr::Decode {
            encoding: Encoding::Base64UrlNoPad,
            of: Box::new(slice(8 * 29, 8 * 16)),
        }
    }

    fn iat_bound(relation: Relation, bound: &[u8]) -> PlaintextBitConstraint {
        PlaintextBitConstraint::Comparison {
            relation,
            lhs: iat_window(),
            rhs: ConstraintExpr::Constant(bound.to_vec()),
        }
    }

    /// Bounding a timestamp carried as ASCII decimal, with no parsing anywhere: for equal-length
    /// operands, lexicographic order over bytes is numeric order, and ASCII digits are contiguous
    /// and ascending.
    #[test]
    fn test_a_comparison_bounds_a_text_timestamp() {
        let not_before = iat_bound(Relation::AtLeast, b":1756000000,");
        let not_after = iat_bound(Relation::AtMost, b":1757000000,");
        // A comparison against a constant reads no wires.
        let no_wires = BTreeMap::new();

        let fresh = bytes_to_bits(JWS);
        assert!(not_before.is_satisfied(&fresh, &no_wires));
        assert!(not_after.is_satisfied(&fresh, &no_wires));

        // A token from 2023 fails the lower bound and nothing else, which is the replay this is
        // for: it verifies perfectly well under the issuer's key.
        let key = SigningKey::from_bytes(&[7u8; 32]);
        let stale = bytes_to_bits(JWS_STALE);
        assert!(jws_constraint().is_satisfied(
            &stale,
            &wires(&bytes_to_bits(key.verifying_key().as_bytes()))
        ));
        assert!(!not_before.is_satisfied(&stale, &no_wires));
        assert!(not_after.is_satisfied(&stale, &no_wires));
    }

    /// The comparison is over bytes, and this is the pair that proves it.
    ///
    /// `"...001"` and `"...002"` differ in one ASCII digit. As byte strings the first is smaller;
    /// as LSB-first bit vectors the second is, because bit 0 of `'1'` is 1 and of `'2'` is 0. A
    /// comparison built on the bit order would accept a timestamp its bound was meant to exclude,
    /// which is the same unit confusion as `OnAmbiguity::TakeSmallestBits` and much worse here.
    #[test]
    fn test_a_comparison_is_over_bytes_not_the_bit_vector() {
        let lower = b"1756100001";
        let higher = b"1756100002";
        assert!(lower < higher, "as byte strings");
        assert!(
            bytes_to_bits(lower) > bytes_to_bits(higher),
            "and the other way as LSB-first bit vectors, which is the trap"
        );

        let no_wires = BTreeMap::new();
        let bits = bytes_to_bits(lower);
        let at_most = PlaintextBitConstraint::Comparison {
            relation: Relation::AtMost,
            lhs: slice(0, 8 * 10),
            rhs: ConstraintExpr::Constant(higher.to_vec()),
        };
        let at_least = PlaintextBitConstraint::Comparison {
            relation: Relation::AtLeast,
            lhs: slice(0, 8 * 10),
            rhs: ConstraintExpr::Constant(higher.to_vec()),
        };
        assert!(
            at_most.is_satisfied(&bits, &no_wires),
            "1756100001 <= 1756100002"
        );
        assert!(!at_least.is_satisfied(&bits, &no_wires));
    }

    /// Unequal widths are refused rather than zero-extended: "shorter means smaller" and "shorter
    /// is zero-padded" are both plausible readings, and a comparison that silently picks one is a
    /// bound that does not mean what it says.
    #[test]
    fn test_a_comparison_refuses_unequal_widths() {
        let constraint = PlaintextBitConstraint::Comparison {
            relation: Relation::AtMost,
            lhs: slice(0, 8 * 4),
            rhs: ConstraintExpr::Constant(b"12345".to_vec()),
        };
        assert!(!constraint.is_satisfied(&bytes_to_bits(b"1234"), &BTreeMap::new()));
    }

    /// Which operands count towards coverage, which is not the same as which are read.
    #[test]
    fn test_only_pinned_operands_cover() {
        let n = |c: PlaintextBitConstraint| c.covering_operands().len();

        // A comparison bounds rather than pins.
        assert_eq!(n(iat_bound(Relation::AtLeast, b":1756000000,")), 0);

        // A signature under an anchored key pins its signature and its message -- but never the
        // key itself, which is the constraint's authority rather than something it determines.
        assert_eq!(n(jws_constraint()), 2);
        assert!(jws_constraint()
            .covering_operands()
            .iter()
            .all(|operand| !matches!(operand, ConstraintExpr::Wire(_))));

        // A key sliced out of the batch is covered by nothing, which is what refuses the clause.
        // The signature and message are still covered by it -- deliberately, so that a key pinned
        // by a *second* constraint leaves a working cert-chain clause.
        assert_eq!(n(self_signed_constraint()), 2);
        let key_bits = 512 + 8 * 12;
        assert!(
            self_signed_constraint()
                .covering_operands()
                .iter()
                .flat_map(|operand| operand.slices())
                .flat_map(|slice| slice.get_indices())
                .all(|index| index < key_bits),
            "the key's own bytes must not be covered by its signature"
        );

        // An equality against something anchored pins the other side, whichever way round it is
        // written.
        assert_eq!(
            n(PlaintextBitConstraint::Equality {
                bits: slice(0, 8),
                expected: ConstraintExpr::Constant(vec![b'.']),
            }),
            1
        );
        assert_eq!(
            n(PlaintextBitConstraint::Equality {
                bits: ConstraintExpr::Constant(vec![b'.']),
                expected: slice(0, 8),
            }),
            1
        );
        // Two slices of the batch against each other pin neither.
        assert_eq!(
            n(PlaintextBitConstraint::Equality {
                bits: slice(0, 8),
                expected: slice(8, 8),
            }),
            0
        );
    }

    /// The shape the coverage rule exists to refuse: signature, message and key all sliced out of
    /// the peer's own proposal, so the peer signs its own data with a key of its choosing.
    ///
    /// Every byte is *read*, which is why "is it read?" was the wrong question.
    fn self_signed_constraint() -> PlaintextBitConstraint {
        PlaintextBitConstraint::Signature {
            scheme: SignatureScheme::Ed25519,
            signature: slice(0, 512),
            message: slice(512, 8 * 12),
            public_key: slice(512 + 8 * 12, 256),
        }
    }

    /// And it really does verify — the predicate is satisfied, so nothing but coverage stops it.
    #[test]
    fn test_a_self_signed_batch_satisfies_its_own_constraint() {
        let attacker = SigningKey::from_bytes(&[42u8; 32]);
        let message = b"whatever it li";
        let message = &message[..12];
        let signature = attacker.sign(message);

        let mut bits = bytes_to_bits(&signature.to_bytes());
        bits.extend(bytes_to_bits(message));
        bits.extend(bytes_to_bits(attacker.verifying_key().as_bytes()));

        assert!(
            self_signed_constraint().is_satisfied(&bits, &BTreeMap::new()),
            "a peer can always satisfy a clause whose key it supplies"
        );
    }

    #[test]
    fn test_decoded_bits_is_exact_for_unpadded_base64() {
        let b64 = Encoding::Base64UrlNoPad;
        // A 64-byte signature is 86 characters, and 86 characters are 64 bytes.
        assert_eq!(b64.decoded_bits(8 * 86), Some(8 * 64));
        assert_eq!(b64.decoded_bits(8 * 4), Some(8 * 3));
        assert_eq!(b64.decoded_bits(8 * 2), Some(8));
        assert_eq!(b64.decoded_bits(8 * 3), Some(8 * 2));
        // One trailing character carries 6 bits and cannot start a byte, so no input of this width
        // decodes -- which is a width validation can reject outright.
        assert_eq!(b64.decoded_bits(8 * 5), None);
        // A partial byte is not a character count at all.
        assert_eq!(b64.decoded_bits(4), None);
    }

    /// Every byte string must have exactly one encoding, or two peers holding the same payload
    /// encoded differently would reconcile as two distinct candidates.
    #[test]
    fn test_decode_rejects_non_canonical_encodings() {
        let b64 = Encoding::Base64UrlNoPad;
        // "QQ" is `A`: 6 bits used, 4 spare, and the spare ones must be zero. "QR" carries the
        // same byte with rubbish in the bits that are not part of it.
        assert_eq!(b64.decode(b"QQ"), Some(vec![b'A']));
        assert_eq!(b64.decode(b"QR"), None);
        // Padded input is the same bytes under a different encoding, so it is refused too.
        assert_eq!(b64.decode(b"QQ=="), None);
        // A lone trailing character: five characters are four plus one, and one cannot start a
        // byte. Six and seven characters are both fine, which is why the check is on the count mod
        // four rather than on it being a multiple of four.
        assert_eq!(b64.decode(b"QUJDRA"), Some(b"ABCD".to_vec()));
        assert_eq!(
            b64.decode(b"QUJDRAA"),
            Some(vec![b'A', b'B', b'C', b'D', 0])
        );
        assert_eq!(b64.decode(b"QUJDR"), None);
        // The URL alphabet, not the standard one.
        assert_eq!(b64.decode(b"-_-_"), Some(vec![0xfb, 0xff, 0xbf]));
        assert_eq!(b64.decode(b"+/+/"), None);
    }

    #[test]
    fn test_static_len_of_a_decode() {
        let expr = ConstraintExpr::Decode {
            encoding: Encoding::Base64UrlNoPad,
            of: Box::new(slice(0, 8 * 86)),
        };
        assert_eq!(expr.static_len(&|_| None), Some(512));
        // And it nests, so the ceilings that bound an expression still see it.
        assert_eq!(expr.depth(), 2);
        assert_eq!(expr.node_count(), 2);
        assert_eq!(expr.slices().len(), 1);
    }

    mod circuit {
        use num_bigint::BigUint;
        use primitives::random::rng::test_rng;

        use super::*;
        use crate::{
            circuit::{AlgebraicType, Circuit, Gate, Input},
            config::DefaultConfig as C,
        };

        const MESSAGE_BYTES: u32 = 12;
        /// `message || signature`
        const BATCH_SIZE: u32 = 8 * MESSAGE_BYTES + 512;

        fn plaintext_bits(circuit: &mut Circuit<C>, batch_size: u32) -> u32 {
            circuit
                .add_gate(Gate::Input(Input::Plaintext {
                    algebraic_type: AlgebraicType::Bit,
                    batch_size,
                }))
                .unwrap()
        }

        /// A circuit whose single gate constrains a `message || signature` batch. The public key is
        /// gate 0 and the constrained batch gate 1, matching [`signature_constraint`].
        fn build(clauses: Vec<ConstraintClause>) -> Result<Circuit<C>, String> {
            build_sized(BATCH_SIZE, clauses)
        }

        fn build_sized(
            batch_size: u32,
            clauses: Vec<ConstraintClause>,
        ) -> Result<Circuit<C>, String> {
            let mut circuit = Circuit::<C>::new();
            plaintext_bits(&mut circuit, 256);
            let x = plaintext_bits(&mut circuit, batch_size);
            let gate = circuit
                .add_gate(Gate::ConstrainPlaintextBits {
                    x,
                    clauses,
                    on_ambiguity: OnAmbiguity::Fail,
                })
                .map_err(|e| e.to_string())?;
            circuit.add_output(gate).unwrap();
            Ok(circuit)
        }

        /// The single-clause case, which most of these tests only need.
        fn one(constraint: PlaintextBitConstraint) -> Vec<ConstraintClause> {
            vec![ConstraintClause::new(vec![constraint])]
        }

        /// The gate's output: `data` followed by the success bit.
        fn expect(data: &[bool], ok: bool) -> Vec<BigUint> {
            data.iter()
                .chain(std::iter::once(&ok))
                .map(|b| BigUint::from(*b))
                .collect()
        }

        /// One bit wider than the input: the data, then the success bit.
        #[test]
        fn test_gate_output_is_the_input_plus_a_success_bit() {
            let circuit = build(one(signature_constraint(MESSAGE_BYTES))).unwrap();
            let output = circuit.gate_output_unchecked(2);
            assert_eq!(output.get_batch_size(), BATCH_SIZE + 1);
            assert_eq!(output.get_type(), AlgebraicType::Bit);
            assert_eq!(
                output.get_form(),
                crate::circuit::ShareOrPlaintext::Plaintext
            );
        }

        /// Validation counts the same way the interpreter does: a bound is not a pin, so a clause
        /// whose only constraint is a comparison leaves the whole batch uncovered.
        #[test]
        fn test_a_comparison_alone_does_not_cover_the_batch() {
            let err = build(one(PlaintextBitConstraint::Comparison {
                relation: Relation::AtLeast,
                lhs: slice(0, 8 * 4),
                rhs: ConstraintExpr::Constant(vec![0u8; 4]),
            }))
            .expect_err("a comparison covers nothing");
            assert!(err.contains("must be covered"), "{err}");
        }

        /// Beside a constraint that does pin the batch, the comparison is free: its slices are
        /// still range-checked, they just add no coverage of their own.
        #[test]
        fn test_a_comparison_beside_a_pinning_constraint_validates() {
            build(vec![ConstraintClause::new(vec![
                signature_constraint(MESSAGE_BYTES),
                PlaintextBitConstraint::Comparison {
                    relation: Relation::AtLeast,
                    lhs: slice(0, 8 * 4),
                    rhs: ConstraintExpr::Constant(vec![0u8; 4]),
                },
            ])])
            .expect("pinned by the signature");
        }

        /// Widths are checked before a peer ever evaluates it, since an operand pair that can never
        /// compare is a gate that can only report failure.
        #[test]
        fn test_validation_refuses_a_comparison_of_unequal_widths() {
            let err = build(vec![ConstraintClause::new(vec![
                signature_constraint(MESSAGE_BYTES),
                PlaintextBitConstraint::Comparison {
                    relation: Relation::AtMost,
                    lhs: slice(0, 8 * 4),
                    rhs: ConstraintExpr::Constant(vec![0u8; 5]),
                },
            ])])
            .expect_err("four bytes against five");
            assert!(err.contains("same length"), "{err}");
        }

        /// `message || signature || key`, wide enough for a clause that reads its key out of the
        /// response.
        const KEY_IN_RESPONSE_BITS: u32 = 512 + 8 * MESSAGE_BYTES + 256;

        /// The clause the coverage rule exists to refuse. It verifies — see
        /// `test_a_self_signed_batch_satisfies_its_own_constraint` — so validation is the only
        /// thing standing between a peer and a gate that reports success on data it signed itself.
        #[test]
        fn test_a_self_signed_clause_is_refused() {
            let err = build_sized(KEY_IN_RESPONSE_BITS, one(self_signed_constraint()))
                .expect_err("a key sliced from the batch is anchored by nothing");
            assert!(err.contains("must be covered"), "{err}");
        }

        /// And the shape that must keep working: the key travels in the response, and a second
        /// constraint binds it to a value the circuit author supplied. That is a cert chain in
        /// miniature, and it is why the signature and message stay covered even when the key is a
        /// slice.
        #[test]
        fn test_a_key_from_the_response_pinned_by_another_constraint_validates() {
            let key_at = 512 + 8 * MESSAGE_BYTES;
            build_sized(
                KEY_IN_RESPONSE_BITS,
                vec![ConstraintClause::new(vec![
                    self_signed_constraint(),
                    PlaintextBitConstraint::Equality {
                        bits: slice(key_at, 256),
                        expected: ConstraintExpr::Constant(vec![0u8; 32]),
                    },
                ])],
            )
            .expect("the key is pinned by the equality");
        }

        #[test]
        fn test_mock_eval_passes_the_bits_through() {
            let key = SigningKey::from_bytes(&[7u8; 32]);
            let message = b"{\"price\":42}";
            assert_eq!(message.len() as u32, MESSAGE_BYTES);
            let (bits, public_key) = signed_batch(&key, message);

            let circuit = build(one(signature_constraint(MESSAGE_BYTES))).unwrap();
            let inputs = public_key
                .iter()
                .chain(bits.iter())
                .map(|b| BigUint::from(*b))
                .collect::<Vec<BigUint>>();
            let output = circuit.mock_eval_big_uint(inputs, &mut test_rng());

            assert_eq!(output, expect(&bits, true));
        }

        /// Unsatisfied constraints are reported, not fatal: the data is zeroed and the success bit
        /// is false. Being total this way is what lets randomised tests, whose bits will never
        /// satisfy a signature, reach anything downstream of the gate.
        #[test]
        fn test_mock_eval_reports_an_unsatisfied_constraint() {
            let key = SigningKey::from_bytes(&[7u8; 32]);
            let (mut bits, public_key) = signed_batch(&key, b"{\"price\":42}");
            bits[0] = !bits[0];

            let circuit = build(one(signature_constraint(MESSAGE_BYTES))).unwrap();
            let inputs = public_key
                .iter()
                .chain(bits.iter())
                .map(|b| BigUint::from(*b))
                .collect::<Vec<BigUint>>();
            let output = circuit.mock_eval_big_uint(inputs, &mut test_rng());

            assert_eq!(output, expect(&vec![false; BATCH_SIZE as usize], false));
        }

        #[test]
        fn test_validation_rejects_uncovered_bits() {
            // Constrains the signature and all but the last byte of the message.
            let err = build(one(PlaintextBitConstraint::Signature {
                scheme: SignatureScheme::Ed25519,
                signature: slice(8 * MESSAGE_BYTES, 512),
                message: slice(0, 8 * (MESSAGE_BYTES - 1)),
                public_key: ConstraintExpr::Wire(0),
            }))
            .unwrap_err();
            assert!(
                err.contains("clause 0") && err.contains("8 are not"),
                "{err}"
            );
        }

        #[test]
        fn test_validation_rejects_no_clauses() {
            let err = build(vec![]).unwrap_err();
            assert!(err.contains("expected at least one clause"), "{err}");
        }

        #[test]
        fn test_validation_rejects_an_empty_clause() {
            let err = build(vec![
                ConstraintClause::new(vec![signature_constraint(MESSAGE_BYTES)]),
                ConstraintClause::new(vec![]),
            ])
            .unwrap_err();
            assert!(err.contains("clause 1 is empty"), "{err}");
        }

        #[test]
        fn test_validation_rejects_out_of_range_slice() {
            let err = build(one(signature_constraint(MESSAGE_BYTES + 1))).unwrap_err();
            assert!(err.contains("out-of-range"), "{err}");
        }

        #[test]
        fn test_validation_rejects_mis_sized_signature() {
            let err = build(one(PlaintextBitConstraint::Signature {
                scheme: SignatureScheme::Ed25519,
                signature: slice(8 * MESSAGE_BYTES, 256),
                message: slice(0, 8 * MESSAGE_BYTES),
                public_key: ConstraintExpr::Wire(0),
            }))
            .unwrap_err();
            assert!(
                err.contains("expected a 512-bit Ed25519 signature"),
                "{err}"
            );
        }

        #[test]
        fn test_validation_rejects_mis_sized_public_key() {
            let mut circuit = Circuit::<C>::new();
            // 128 bits, where Ed25519 wants 256.
            plaintext_bits(&mut circuit, 128);
            let x = plaintext_bits(&mut circuit, BATCH_SIZE);
            let err = circuit
                .add_gate(Gate::ConstrainPlaintextBits {
                    x,
                    on_ambiguity: OnAmbiguity::Fail,
                    clauses: one(signature_constraint(MESSAGE_BYTES)),
                })
                .unwrap_err()
                .to_string();
            assert!(
                err.contains("expected a 256-bit Ed25519 public key"),
                "{err}"
            );
        }

        #[test]
        fn test_validation_rejects_mis_sized_equality_value() {
            let err = build(one(PlaintextBitConstraint::Equality {
                // The wire at index 0 holds 256 bits, not `BATCH_SIZE`.
                bits: slice(0, BATCH_SIZE),
                expected: ConstraintExpr::Wire(0),
            }))
            .unwrap_err();
            assert!(err.contains("must be the same length"), "{err}");
        }

        /// Two clauses, each a signature under its own key: gate 0 holds the first key, gate 1 the
        /// second, gate 2 the constrained batch.
        fn build_two_keys() -> Circuit<C> {
            let mut circuit = Circuit::<C>::new();
            plaintext_bits(&mut circuit, 256);
            plaintext_bits(&mut circuit, 256);
            let x = plaintext_bits(&mut circuit, BATCH_SIZE);
            let clause = |public_key| {
                ConstraintClause::new(vec![PlaintextBitConstraint::Signature {
                    scheme: SignatureScheme::Ed25519,
                    signature: slice(8 * MESSAGE_BYTES, 512),
                    message: slice(0, 8 * MESSAGE_BYTES),
                    public_key: ConstraintExpr::Wire(public_key),
                }])
            };
            let gate = circuit
                .add_gate(Gate::ConstrainPlaintextBits {
                    x,
                    on_ambiguity: OnAmbiguity::Fail,
                    clauses: vec![clause(0), clause(1)],
                })
                .unwrap();
            circuit.add_output(gate).unwrap();
            circuit
        }

        /// A second clause accepts data the first rejects — the fallback-signing-key case.
        #[test]
        fn test_a_later_clause_can_satisfy_the_gate() {
            let circuit = build_two_keys();
            let first = SigningKey::from_bytes(&[7u8; 32]);
            let second = SigningKey::from_bytes(&[9u8; 32]);
            let first_key = bytes_to_bits(first.verifying_key().as_bytes());

            // Signed by the *second* key, so only the second clause holds.
            let (bits, second_key) = signed_batch(&second, b"{\"price\":42}");
            let inputs = first_key
                .iter()
                .chain(second_key.iter())
                .chain(bits.iter())
                .map(|b| BigUint::from(*b))
                .collect::<Vec<BigUint>>();

            let output = circuit.mock_eval_big_uint(inputs, &mut test_rng());
            assert_eq!(output, expect(&bits, true));
        }

        /// Only when *every* clause fails does the gate report failure.
        #[test]
        fn test_the_gate_reports_failure_only_when_all_clauses_fail() {
            let circuit = build_two_keys();
            let third = SigningKey::from_bytes(&[11u8; 32]);
            let (bits, _) = signed_batch(&third, b"{\"price\":42}");
            let first = bytes_to_bits(
                SigningKey::from_bytes(&[7u8; 32])
                    .verifying_key()
                    .as_bytes(),
            );
            let second = bytes_to_bits(
                SigningKey::from_bytes(&[9u8; 32])
                    .verifying_key()
                    .as_bytes(),
            );
            let inputs = first
                .iter()
                .chain(second.iter())
                .chain(bits.iter())
                .map(|b| BigUint::from(*b))
                .collect::<Vec<BigUint>>();
            let output = circuit.mock_eval_big_uint(inputs, &mut test_rng());
            assert_eq!(output, expect(&vec![false; BATCH_SIZE as usize], false));
        }

        /// The reason the gate reports rather than aborts: a randomised test feeds bits that will
        /// never satisfy a signature, and must still be able to evaluate the circuit and compare
        /// outputs instead of dying at this gate.
        #[test]
        fn test_random_bits_evaluate_to_a_clean_failure() {
            use rand::Rng;

            let circuit = build(one(signature_constraint(MESSAGE_BYTES))).unwrap();
            let mut rng = test_rng();
            let inputs = (0..256 + BATCH_SIZE)
                .map(|_| BigUint::from(rng.gen::<bool>()))
                .collect::<Vec<BigUint>>();

            // Deterministic despite the random input, which is what makes the comparison in a
            // randomised test meaningful.
            let output = circuit.mock_eval_big_uint(inputs, &mut test_rng());
            assert_eq!(output, expect(&vec![false; BATCH_SIZE as usize], false));
        }

        /// Coverage is per clause: a second clause covering only part of the batch is rejected even
        /// though the first clause covers all of it.
        #[test]
        fn test_validation_requires_coverage_from_every_clause() {
            let err = build(vec![
                ConstraintClause::new(vec![signature_constraint(MESSAGE_BYTES)]),
                ConstraintClause::new(vec![PlaintextBitConstraint::Equality {
                    bits: slice(0, 256),
                    expected: ConstraintExpr::Wire(0),
                }]),
            ])
            .unwrap_err();
            assert!(err.contains("clause 1"), "{err}");
            assert!(err.contains("must be covered"), "{err}");
        }

        #[test]
        fn test_gate_inputs_are_listed_clause_by_clause() {
            let circuit = build_two_keys();
            assert_eq!(circuit.gate_unchecked(3).get_inputs(), vec![2, 0, 1]);
        }

        /// The bounds exist so a hostile circuit cannot make every peer do unbounded work while
        /// reconciling, and so validation's own recursion terminates.
        #[test]
        fn test_validation_rejects_an_over_deep_expression() {
            let mut expected = slice(0, 256);
            for _ in 0..MAX_EXPR_DEPTH {
                expected = ConstraintExpr::Digest {
                    algorithm: DigestAlgorithm::Sha256,
                    of: Box::new(expected),
                };
            }
            let err = build(one(PlaintextBitConstraint::Equality {
                bits: slice(0, 256),
                expected,
            }))
            .unwrap_err();
            assert!(err.contains("nests deeper than"), "{err}");
        }

        #[test]
        fn test_validation_rejects_an_over_wide_expression() {
            let err = build(one(PlaintextBitConstraint::Equality {
                bits: ConstraintExpr::Concat(
                    (0..MAX_EXPR_NODES as u32 + 1)
                        .map(|i| slice(i, 1))
                        .collect(),
                ),
                expected: ConstraintExpr::Wire(0),
            }))
            .unwrap_err();
            assert!(err.contains("more than"), "{err}");
        }

        #[test]
        fn test_validation_rejects_shared_input() {
            let mut circuit = Circuit::<C>::new();
            plaintext_bits(&mut circuit, 256);
            let x = circuit
                .add_gate(Gate::Input(Input::Share {
                    algebraic_type: AlgebraicType::Bit,
                    batch_size: BATCH_SIZE,
                }))
                .unwrap();
            let err = circuit
                .add_gate(Gate::ConstrainPlaintextBits {
                    x,
                    on_ambiguity: OnAmbiguity::Fail,
                    clauses: one(signature_constraint(MESSAGE_BYTES)),
                })
                .unwrap_err()
                .to_string();
            assert!(err.contains("is_plaintext"), "{err}");
        }
    }
}