Mpc

sparq-mpc — MPC over federated SPARQL

sparq-mpc lets a set of mutually-distrusting holders, each owning private RDF named graphs, jointly answer ONE SPARQL query over the union of their data while minimising what each holder reveals. Today it delivers a real per-holder local evaluator, a crypto-free join on disclosed global IRIs, and an honest-majority Shamir secret-sharing backend that powers secure cumulative aggregates and a hidden-value (private-key) join. The reconstruction path is honest-majority with tamper DETECTION + abort — and robust correction where the (n, t) redundancy allows — over RS-consistency-checked opens; the degree-2t equality open is detection-only above n = 2t + 1, and semi-honest is the floor when a given configuration carries no redundancy. It is not dishonest-majority and not full malicious security; each backend reports its exact level via BackendInfo.malicious_security.

<!-- sq-im8u: the `scaffold-caveat` anchor is single-sourced into book/src/getting-started/capabilities.md via mdBook {{#include}}. Load-bearing honesty caveat; keep the anchored line link-portable (inline code + bead refs only, no repo-relative links) so it renders under both mounts. Keep the ANCHOR markers one-per-line — mdBook excludes only the exact marker line. privacy-claims-allow: NEGATIVE caveat block (explicitly "not full malicious security", semi-honest floor, ZK proof not implemented) — not an achieved-property claim; sq-qhy4. [OPUS-4.8] --> <!-- ANCHOR: scaffold-caveat -->

Maturity (read first). EARLY / RESEARCH, native-only (deliberately not in the wasm build). The Shamir layer's reconstruction is RS-consistency-checked: it detects (and, with enough redundancy, robustly corrects) actively-tampered shares and reports the exact guarantee via BackendInfo.malicious_security — but the degree-2t equality open in the hidden-value join is not hardened at n = 2t+1 (see Gotchas). The primitives run as an in-process simulation (one process plays all parties) for correctness/cost counting, AND over a REAL multi-process loopback transport (transport module — each party its own process over 127.0.0.1; all four QueryClass cells incl. the multi-round oblivious shuffle/sort run on the wire) for MEASURED wall-clock + bytes-on-wire. The collaborative ZK proof of correctness + issuer-attestation is not implemented: those methods return MpcError::NotYetImplemented naming their gate. No fake crypto anywhere. See Gotchas for the full envelope.

<!-- ANCHOR_END: scaffold-caveat -->

Quickstart

Cargo.toml (the crate is in-workspace, publish = false, so depend by path):

[dependencies]
sparq-mpc = { path = "crates/sparq-mpc" }
oxrdf = { version = "0.3", features = ["rdf-12"] }   # for Term / Variable / Literal

Two holders each evaluate the same fragment locally over their own data, then join on a shared global IRI — no crypto needed because the join key is a disclosed IRI:

use sparq_mpc::{Holder, DisclosedKeyJoin, GlobalJoin, JoinPlan};
use oxrdf::Variable;

const PFX: &str = "@prefix ex: <http://ex/> .\n";

// Holder A: a "knows" graph. Holder B: a "name" graph. ?x is a global IRI shared across both.
let a = Holder::from_rdf("a", &format!("{PFX} ex:p1 ex:knows ex:x1 . ex:p2 ex:knows ex:x2 ."), "turtle")?;
let b = Holder::from_rdf("b", &format!("{PFX} ex:x1 ex:name \"Xena\" . ex:x2 ex:name \"Yuri\" ."), "turtle")?;

// Each holder runs ITS OWN fragment over ITS OWN graph; only the projected rows leave the holder.
let pa = a.evaluate_local("PREFIX ex: <http://ex/> SELECT ?p ?x WHERE { ?p ex:knows ?x }")?;
let pb = b.evaluate_local("PREFIX ex: <http://ex/> SELECT ?x ?n WHERE { ?x ex:name ?n }")?;

// Disclosed-key equi-join on the global IRI ?x (crypto-free; equals union-store evaluation).
let plan = JoinPlan { join_var: Variable::new_unchecked("x"), key_disclosed: true };
let joined = DisclosedKeyJoin::new().join(&[pa, pb], &plan)?;

assert_eq!(joined.rows.len(), 2);                 // p1-x1-Xena, p2-x2-Yuri
// joined.holder == HolderId("federation"); joined.vars == [?p, ?x, ?n]
# Ok::<(), sparq_mpc::MpcError>(())

Key APIs

Top-level re-exports (use sparq_mpc::...):

• Holder — one federation participant + its private Graph.
  • Holder::from_rdf(id: impl Into<String>, text: &str, format: &str) -> Result<Holder, MpcError> — format is "turtle" | "ntriples" | "nquads" | "trig".
  • Holder::new(id, graph: sparq_core::Graph) -> Holder
  • Holder::evaluate_local(&self, fragment_sparql: &str) -> HolderResult (= Result<PartialResult, MpcError>) — runs a SELECT fragment over the holder's own graph; raw graph never leaves.
• PartialResult { holder: HolderId, vars: Vec<oxrdf::Variable>, rows: Vec<Vec<Option<oxrdf::Term>>> } — the unit of inter-holder sharing (same shape as sparq_engine::QueryResult). .len(), .is_empty().
• GlobalJoin trait + DisclosedKeyJoin — fn join(&self, partials: &[PartialResult], plan: &JoinPlan) -> Result<PartialResult, MpcError>. SPARQL compatible-mapping inner join over shared columns; independently checks the planner-named key is present (does not trust the planner for soundness). key_disclosed == false returns NotYetImplemented (use HiddenValueJoin instead).
• JoinPlan { join_var: oxrdf::Variable, key_disclosed: bool }.
• MpcBackend trait — the secret-sharing primitive seam. type Share; info() -> BackendInfo; share_private_input(&self, &Holder) -> Result<Vec<Self::Share>, MpcError>; run_secure(&self, &[Self::Share]) -> Result<Vec<Self::Share>, MpcError>; reconstruct_disclosed(&self, &[Self::Share]) -> Result<PartialResult, MpcError>.
• BackendInfo { name: &'static str, security: SecurityDescriptor, trust_model: TrustModel, malicious_security: MaliciousSecurity } — the guarantees a federation inspects before trusting a backend. The three-axis security descriptor is the source of truth; trust_model / malicious_security are kept as back-compat projections of it. Build via BackendInfo::new(name, security, robust_cheaters) so the projections can't drift. BackendInfo::malicious_secure() -> bool is a coarse "hardened at all?" accessor (malicious_security != MaliciousSecurity::SemiHonestOnly — malicious_security is the MaliciousSecurity enum, not an Option).
• SecurityDescriptor { adversary: AdversaryModel, output_guarantee: OutputGuarantee, threshold: CorruptionThreshold, public_verifiability: PublicVerifiability } — the three orthogonal axes a backend (or one operator) advertises. AdversaryModel { SemiHonest, Covert{..}, Malicious } (build covert via AdversaryModel::covert(num, den)); OutputGuarantee { Abort(AbortKind), Fairness, GuaranteedOutput } with AbortKind { Selective, Unanimous, Identifiable } (the honest-majority-only Fairness/GuaranteedOutput are constructible ONLY via OutputGuarantee::fairness(threshold) / ::guaranteed_output(threshold) — Cleve's impossibility as a type-level invariant); CorruptionThreshold { DishonestMajority{t}, HonestMajority{t}, SuperHonestMajority{t} }; PublicVerifiability(bool).
• OperatorClass { LinearAggregate, EqualityJoin, Comparison } + MpcBackend::operator_security(op) -> SecurityDescriptor — guarantees differ per operator (the Shamir degree-t aggregate is robust while the degree-2t equality open is semi-honest-only at n = 2t+1), so query the per-operator descriptor, not just the headline info().security.
• Selection / fail-closed negotiation (sq-a6p1). SecurityRequirement { min_adversary, min_output_guarantee, max_corruption, require_cheater_attribution, require_public_verifiability } — a federation's security floor, stated UP FRONT. req.satisfies(&BackendInfo) -> bool checks a backend against every axis. BackendRegistry<B: MpcBackend> holds the backends a federation will run: register(B), then select(&req) -> Result<&B, MpcError> returns the STRONGEST registered backend meeting req or fails closed with MpcError::NoBackendSatisfies (a dishonest-majority-malicious request over the shipped semi-honest set is truthfully REFUSED, never downgraded). select_for_operator(&req, op) matches against the per-operator guarantee. Convenience floors: SecurityRequirement::v1_honest_majority_semi_honest() and ::dishonest_majority_malicious() (the request that is refused fail-closed today).
• TrustModel { HonestMajority, DishonestMajority } — the majority axis (back-compat projection of CorruptionThreshold).
• MaliciousSecurity { SemiHonestOnly, HonestMajorityAbort, HonestMajorityRobust { max_cheaters: usize } } — the active-security axis (guarantee D), surfaced from the real RS reconstruction redundancy. SemiHonestOnly = semi-honest only, an active deviation is undetected (named so it cannot be confused with Option::None); HonestMajorityAbort = tampering is detected and the protocol aborts (no guaranteed output); HonestMajorityRobust { max_cheaters } = guaranteed-correct output even when up to max_cheaters parties actively cheat. Derives Copy/Eq.
• ShamirBackend — the only concrete backend (honest-majority Shamir t-of-n; its reconstruction reports tamper detect-and-abort or robust correction per the (n, t) redundancy via BackendInfo.malicious_security, falling back to SemiHonestOnly only where no redundancy exists).
  • ShamirBackend::new(n: usize) -> Result<ShamirBackend, MpcError> — n >= 2, threshold t = (n-1)/2; masks come from an OS-seeded ChaCha20 CSPRNG. No seed parameter by design.
  • ShamirBackend::new_seeded(n, seed) — test/bench only, behind cfg(test) or feature insecure-test-rng; predictable masks, no security.
  • parties(), threshold(), malicious_security() -> MaliciousSecurity (the active-security level for this (n, t)), reconstruct(&[Share]) -> Result<Fp, MpcError>, dealer() -> ShamirDealer.
• Dealer-less correlated-randomness SEAM (sq-yyro, randomness module) — the seam plus ONE dealer-less GENERATOR (PRSS, below); no source is deployable(). rng fixes the randomness QUALITY (CSPRNG, sq-1vt); this seam names WHO draws it. DistributedRandomness trait — randomness_model() -> RandomnessModel, shared_mask()/shared_nonzero_mask() (the equality mask, r ≠ 0 — a forced r = 0 flips every equality verdict), vss_own_input(secret) (dealer-less VSS: each holder shares its OWN input). RandomnessModel { TrustedDealerSim, Prss, HonestMajorityCoinToss } with is_dealer_less() / deployable(). Two implementors: ShamirDealer, reporting RandomnessModel::TrustedDealerSim — the single-dealer path labelled honestly as the SIMULATION it is (the dealer knows every mask) — and prss::PrssRandomness (below). deployable() is false for EVERY variant, so require_deployable() still refuses both fail-closed; acceptance must be tied to a validated construction (design §5 item 5), never to the self-reported label. The coin-toss source (interactive, any-n), dealer-less VSS, and the r = 0 active-adversary defense remain follow-on beads behind this trait. Design: research/mpc-distributed-randomness-design.md.
  • PRSS correlated randomness (sq-yyro follow-on, prss module) — the generator is REAL; the setup and the deployment gate are not. PrssRandomness::with_simulated_setup(n) -> Result<PrssRandomness, MpcError> builds the replicated-PRF seeds for the C(n, t) maximal unqualified sets, and shared_mask() / shared_nonzero_mask() then emit degree-t sharings via Σ_A PRF(k_A, ctr)·f_A — non-interactive (0 online rounds, C(n, t) local PRF calls per element), with each party's share touching only the seeds that party holds (f_A(x_i) = 0 exactly when i ∈ A; a checked invariant). Also with_seeded_setup(n, seed) (test/bench only, behind cfg(test) / insecure-test-rng), parties(), threshold(), seed_count(), seeds_per_party(), MAX_PRSS_SEEDS (= 128; n ≥ 10 is refused — C(10,4) = 210 — pointing at the coin-toss fallback). What it does NOT give: the setup is a simulated one-time trusted setup, not dealer-less key agreement (design §6 Q3); the crate is an in-process simulation, so structure is demonstrated, not isolation; the r ≠ 0 rejection evaluates r centrally — a simulation artefact a real deployment must replace with a distributed zero-test (design §1/§5 item 4), so it stays semi-honest only; vss_own_input returns NotYetImplemented (PRSS is not an input-sharing protocol); security is computational (PRF-based), not information-theoretic; and the source is still not deployable() (sq-qhy4 external sign-off pending).
  • Cheater attribution (sq-6u6b). The RS reconstruction surfaces which shares were tampered, with two distinct soundness levels. On the success path use sparq_mpc::reconstruct_robust_attributed(&[Share], degree) -> Result<RobustReconstruction, MpcError> — RobustReconstruction { secret: Fp, cheaters: Vec<u64> } lists the corrected shares' evaluation points, which is exact (the agreeing degree-degree majority uniquely pins the cheaters). On the abort path MpcError::Tampered { cheaters } is best-effort: the off-curve set of the minimum-disagreement reference fit — sound (names only real cheaters) in the first abort band of e+1 errors, heuristic beyond it where the honest set is genuinely unidentifiable. Detection itself is always sound; only abort-path blame is heuristic, so a Tampered name is NOT proof of guilt.
• HiddenValueJoin::new(backend: ShamirBackend) + join(&self, left: &HiddenKeyedRows, right: &HiddenKeyedRows) -> Result<PartialResult, MpcError> — joins on a private key via secret-shared equality; output schema is left.payload_vars ++ right.payload_vars, the key is never projected/reconstructed.
• HiddenValueJoin::batched_join(&left: &BatchedHiddenInput, &right, bound) -> Result<(PartialResult, ObliviousOutputCost), MpcError> (sq-khf9) — ranges over a row COLUMN per holder under a RowBinding and routes the OUTPUT through the oblivious shuffle + padded-prefix reveal (L1 bounded to B, output L2 destroyed). Still OPENS the per-pair match bit (decision-time L2 unchanged).
• HiddenValueJoin::fully_oblivious_batched_join(&left, &right, bound) -> Result<(PartialResult, ObliviousOutputCost), MpcError> (sq-xhaw — fully-oblivious) — same as batched_join but the per-pair match bit is computed as a secret-shared 0/1 by compare::secure_equal_to_bit and fed as a MatchBit::SecretShared selector, so nothing is opened per pair — the decision-time L2 match-graph leak is closed. Cost: O(COMPARE_BITS) secure-mult rounds per pair (vs one masked open). Honest-majority, semi-honest only (sq-qhy4 external sign-off pending).
• HiddenKeyedRows { holder: HolderId, payload_vars: Vec<Variable>, rows: Vec<(Fp, Vec<Option<Term>>)> } — caller encodes each private key into Fp via encode_term (must be injective on the join domain; see Gotchas + the encoder API below).
• encode_term(&Term) -> Fp (sq-dl81) — the documented, collision-resistant Term -> Fp join-key encoder: reduce_mod_p(SHA-512(DOMAIN_TAG ‖ ntriples(term))). Output is statistically uniform over F_p (random-oracle model), so two distinct terms collide only with the birthday probability ≈ q² / 2^62 over q distinct terms (50% near q ≈ 2^30.5, i.e. ≈ 2.2×10⁻¹¹ at q = 10⁴ — far above the ≤10⁴-row hidden-join regime). Variant-disambiguating (an IRI <x> and a literal "x" never collide); datatype/language tags participate in the key. The in-circuit proof that the opened key equals encode_term(term) is the M4 collaborative-proof job — this encoder is its on-ramp.
• KeyEncoder (sq-dl81) — a stateful encode_term wrapper for an exact injectivity guarantee over a CONCRETE key set: KeyEncoder::new() then encode(&Term) -> Result<Fp, EncodeError>. Re-encoding the SAME term returns the same key (recurring equi-join key, not a collision); two DISTINCT terms hashing to the same Fp return EncodeError::Collision(Box<Collision { key, first, second }>) — fail-closed BEFORE any key is secret-shared, since a collision is a false-match soundness break the hidden join cannot otherwise see. len() / is_empty() report the distinct-key count q. DOMAIN_TAG is the versioned domain-separation prefix.
• Oblivious set-returning output path (oblivious_join module) — closes the HiddenValueJoin output leaks L1 (true result cardinality) and L2 (per-pair match graph / key fan-out) by padding to a public bound + an oblivious shuffle, instead of opening a per-pair match bit. Built on the oblivious::shuffle substrate.
  • Candidate { payload: Vec<Option<Term>>, matched: MatchBit } and MatchBit::{ Public(bool), SecretShared(Vec<Share>) } — one join candidate + its match decision (public/disclosed-key bit, or a secret-shared 0/1 bit).
  • oblivious_set_output(backend, candidates, payload_arity, bound) -> Result<(Vec<OutputSlot>, ObliviousOutputCost), MpcError> — reveals exactly bound (B) OutputSlot::{ Row(..), Dummy } slots in oblivious-shuffled order; matched rows survive, non-matches/padding become Dummy. The parties learn only B and ≤ B (not the true count, not which slots matched). Fails closed if bound < candidates.len() (never truncates a match).
  • oblivious_join_output(backend, candidates, out_vars, bound) -> Result<(PartialResult, ObliviousOutputCost), MpcError> — the PartialResult-shaped wrapper (dummies filtered, federation-attributed, canonical order).
  • oblivious_set_output_hidden_keys(backend, left_keys, right_keys, bound) — the truly-private-key all-pairs variant; realised (sq-xhaw) — the secure equality-to-SHARED-bit gate (sq-rrz4/sq-dvuc) it once cited has landed, so it computes each per-pair match bit secret-shared via compare::secure_equal_to_bit (never opened) and runs the transform. Honest-majority, semi-honest only.
• Oblivious shuffle + sort substrate (sq-18lk, oblivious module) — the single highest-leverage hidden-regime primitive (ORQ SOSP'25): DISTINCT, ORDER BY, GROUP BY-over-hidden-key, MIN/MAX, OPTIONAL/MINUS, the set-returning oblivious-join output path, and ~linear sort-merge joins all reduce to oblivious shuffle + sort. The substrate the oblivious_join output path (above) consumes. Native-only; in-process multi-party simulation; communication cost is MODELLED, not measured (ShuffleCost/SortCost are derived from n, never hard-coded). All operands are SecretColumn = Vec<Vec<Share>> (a vector of full Shamir sharings, one per row).
  • shuffle(dealer: &mut ShamirDealer, col: SecretColumn) -> Result<(SecretColumn, ShuffleCost), MpcError> — REAL and sound today. Permutes the column by a uniformly-random secret permutation (Fisher–Yates over the dealer's masking CSPRNG, rejection-sampled to kill modulo bias — fails closed for n > P) routed through a full-support AS-Waksman network (WaksmanNetwork; NOT biased-Beneš). The output order is information-theoretically independent of the input order to any ≤ t-collusion: the topology is data-independent and the control bits stay secret (PRSS-generated in a real deployment). In the cleartext-control simulation a switch is a local swap of two share-vectors — zero multiplications, stays degree t, no degree reduction — which is why it is buildable on the current single-product Shamir backend.
  • sort_by<C: Comparator>(col: SecretColumn, cmp: &C) -> Result<SortByResult, MpcError> (SortByResult = (SecretColumn, AccessPattern, SortCost)) — sorts ascending via a Batcher odd-even mergesort network (SortingNetwork, O(n log² n) compare-exchange gates in O(log² n) layers). The returned AccessPattern = Vec<(usize, usize)> is the (i, j) compare-exchange sequence, a function of n alone — the load-bearing obliviousness substrate (data-independent; asserted so in tests). The Comparator seam decides each swap; its security is the comparator's responsibility. A comparator over genuinely-SECRET keys needs the degree-reduction-gated secure comparison (sq-rrz4 / sq-dvuc) — the only in-crate secret-key Comparator is the test-only insecure SimulatedSecretComparator (cfg(test)/insecure-test-rng, reconstructs to compare, LEAKS — stands in so the network can be exercised).
  • sort_with_keys(col: SecretColumn, keys: Vec<Fp>) -> Result<SortWithKeysResult, MpcError> (SortWithKeysResult = (SecretColumn, Vec<Fp>, AccessPattern, SortCost)) — the sound, shippable DISCLOSED-regime ORDER BY / GROUP BY path: sorts by public sort keys, keeping each key aligned with its sharing through every swap. Secret VALUES stay secret-shared and are obliviously permuted; only the public keys drive comparisons, so no secure comparator is needed. Stable (swaps only on strict greater-than). Fails closed (Protocol) if col.len() != keys.len().
  • Comparator trait (must_swap(&self, col: &SecretColumn, i, j) -> Result<bool, MpcError>), SortingNetwork / WaksmanNetwork / Switch (the data-independent network builders, exposed for inspection/testing), ShuffleCost { items, switches, depth_rounds } and SortCost { items, compare_exchanges, depth_rounds } (the modelled-cost reports). The downstream operators (oblivious sort-merge join sq-ujz8, hidden GROUP BY/DISTINCT/MIN-MAX) are their own beads — this module is the substrate, not those operators.
• Secure comparison / threshold (sq-rrz4, compare module) — secret-shared > over Fp that opens only the boolean verdict bit, never the operands or their difference (the disclosure-minimising counterpart to reconstruct_disclosed, which opens the integer). Bit-decomposition MSB-first comparison; chains multiplications via mul_shares_raw + the BGW degree_reduce (sq-dvuc), so it is a genuine depth-O(L) mult chain. Honest-majority, semi-honest — NOT malicious (reported as OperatorClass::Comparison → SemiHonestOnly); for the malicious-with-abort variant of this chain see auth_compare below. Operands must be < 2^60 (COMPARE_MAX_EXCLUSIVE); n >= 2t+1; both fail-closed. Round-per-bit (LAN-fine, WAN-poor); the constant-round Rabbit/DGK/edaBits family is future work.
  • secure_greater_than(dealer: &mut ShamirDealer, a: Fp, b: Fp) -> Result<Vec<Share>, MpcError> — a degree-t sharing of the bit a > b; operands secret-shared internally and never reconstructed.
  • secure_threshold(dealer, secret: Fp, threshold: Fp) -> Result<Vec<Share>, MpcError> — the £100k path: threshold is PUBLIC (its bits are constants, no extra mult round), returns the sharing of secret > threshold.
  • secure_equal_to_bit(dealer, a: Fp, b: Fp) -> Result<Vec<Share>, MpcError> (sq-xhaw) — a degree-t sharing of the equality bit 1{a == b}, computed as ∏_k [a_k == b_k] over bit-decompositions (an AND-tree of secure mults), never opened. Unlike secure_equal (which opens the masked product per pair — the L2 leak), this keeps the verdict secret-shared, so it can drive an oblivious select with no per-pair open. Feeds fully_oblivious_batched_join / oblivious_set_output_hidden_keys.
  • open_verdict(backend: &ShamirBackend, verdict: &[Share]) -> Result<bool, MpcError> — opens ONLY the verdict bit (refuses a non-0/1 reconstruction).
  • disclose_threshold_verdict(backend, sum_shares: &[Share], public_threshold: u64) -> Result<PartialResult, MpcError> — the four-flatmates path end-to-end: from a secret-shared sum, discloses a one-cell ?over_threshold boolean partial — the exact sum is never in the output. The sum is bit-decomposed in-MPC (never reconstruct(sum_shares); sq-g7t5). [OPUS-4.8] sq-bgsn lifts this to the Rabbit-style full-field decomposition (secure_bit_decompose_rabbit, eprint 2021/119): a full-field mask (r ∈ [0, 2^61), no party knows it) is added and only the (near-)uniform c = (sum + r) mod p is opened, then the sum is recovered EXACTLY through the modular wrap (sum = c − r + w·p, w = 1{c < r}) — no statistical slack, so the supported magnitude is the full sum < 2^RABBIT_VALUE_BITS = 2^60 (up from the masked-open path's 2^20), with an in-protocol range proof (fail-closed; sq-nx0s). Honest-majority, semi-honest only.
• Malicious-with-abort comparison (sq-ka8m, auth_compare module) — the honest-majority malicious-with-abort twin of the compare chain (design research/mpc-malicious-security-design.md Hole 4); pending external sign-off (sq-qhy4). Carries an IT-MAC m_x = α·x (under a session-global, secret-shared [α] no party knows) through the WHOLE decompose+compare chain — every secret AND / bit-equality is a MAC-carrying MacSession::auth_mul (design §2.4 route (a): a SECOND independent mult-then-reduce computing [α·z] = reduce([α·x]·[y]), which MAC-covers the degree_reduce re-sharing, Hole 2) — and then runs ONE batched random-challenge MAC-check (MacSession::mac_check, §2.5) over the verdict before opening it: opens a leakage-free σ = Σ χ_j·[m_{y_j}] − (Σ χ_j·y_j)·[α] and aborts with MpcError::MacCheckFailed iff σ ≠ 0. A tamper in any gate (a forged share / a wrong re-sharing) is caught with probability ≈ 1 − 2^{−61} over F_p — at the minimal n = 2t+1 where Reed–Solomon redundancy is zero (soundness comes from the secret α, not RS over-determination). Tier: AXIS-1 Malicious, AXIS-2 Abort(Unanimous) (detect-and-abort, NOT identifiable abort, NOT GOD), AXIS-3 HonestMajority (degrades / refuses if n ≤ 2t); NOT dishonest-majority (route (b)/SPDZ, sq-j5ok, is the continuation). The exact integer operands are NEVER opened — only the 1-bit verdict, only after the check passes. Operands < 2^60 (COMPARE_BITS); n >= 2t+1; both fail-closed. Round-per-bit, ~2× the semi-honest mult cost (the documented authentication price, design §5; no preprocessing under route (a)). Pending external sign-off (sq-qhy4).
  • malicious_greater_than(backend: &ShamirBackend, a: Fp, b: Fp) -> Result<bool, MpcError> — the MAC-checked verdict a > b over two SECRET operands; aborts (MacCheckFailed) on any tampered gate, never returns a wrong boolean.
  • malicious_threshold(backend: &ShamirBackend, secret: Fp, threshold: Fp) -> Result<bool, MpcError> — the £100k path with a PUBLIC threshold (its bits are constants → no mult on the threshold side); MAC-checked before open.
  • open_auth_verdict(backend: &ShamirBackend, verdict: &AuthenticatedShare) -> Result<bool, MpcError> — opens ONLY the verdict's value sharing (the MAC is consumed by the check, never opened); refuses a non-0/1 reconstruction.
  • Underlying primitives (on MacSession, reusable by other authenticated chains): auth_mul(&[[x]], &[[y]]) -> [[x·y]] (§2.4 MAC-carrying multiplication), mac_check_and_open(&[[[y_1]]..]]) -> Result<Vec<Fp>, MpcError> (sq-km34.4 — the §2.5 batched check at the open boundary. ONE σ open authenticates the WHOLE batch, so an all-pairs hidden join's |L|·|R| equality opens share a single check and the malicious upgrade's marginal round cost is O(1) per opened batch, not per opened value; it RETURNS the values it verified, so the caller acts on exactly what the check covered and does not re-open them, and on σ ≠ 0 it returns MpcError::MacCheckFailed and NO value — aborting before an inconsistent result is acted on. The challenges χ_j are derived by Fiat–Shamir over the already-fixed share vectors — domain-separated SHA-512 over (n, t, k, {[y_j], [α·y_j]}) folded into F_p — so "derived after the shares are fixed" is structural rather than a call-ordering convention. Scope (honesty): that transcript is the COMPLETE share vectors, which only the in-process trusted-dealer simulation holds — so this is NOT a coin the n parties jointly derive, and it does NOT remove the trusted dealer; a distributed public coin needs a commit-then-challenge / coin-toss protocol that is not implemented. Nor is the check grinding-proof: with the MACs left unchanged, σ = 0 iff Σ_j χ_j·δ_{y,j} = 0, which is testable WITHOUT α, so ≈ 1 − 2^{−61} is the bound against a deviation fixed before χ is known and a transcript-grinding adversary faces ≈ 2^61 work — a computational, not information-theoretic, bound (design §2.5; pending sq-qhy4)), mac_check(..) -> Result<(), MpcError> (the same check as a pure gate, opened values discarded; empty batch is a no-op pass), auth_const_sharing(c: Fp) -> [[c]] (an authenticated public constant), authenticate_existing(&[Share]) -> Result<[[v]], MpcError> (sq-6fv7 — lift an EXISTING value sharing [v] into [[v]] = ([v], [α·v]=reduce([α]·[v])) without reconstructing v; the entry the malicious disclose path uses for the federation's existing sum). Scope (honesty): this lands the malicious-with-abort comparison chain over secret operands (pending sq-qhy4 external sign-off).
• Free authenticated linear ops (sq-km34.1/.2, authenticated module, design §2.3) — [[x]] = ([x], [α·x]) = an AuthenticatedShare under a session MacKey [α]. The IT-MAC is linear in the value, so add/scale/sub/add-constant authenticate for FREE (zero extra rounds — the honest-majority sweet spot): auth_add(&[[x]], &[[y]]) -> Result<[[x+y]], _>, auth_sub(..) -> Result<[[x−y]], _>, auth_scale(&[[x]], c: Fp) -> [[c·x]] (public scalar), auth_add_constant(&[[x]], c: Fp, &MacKey) -> Result<[[x+c]], _> (the public-constant MAC term c·[α] comes from the shared [α]). auth_sum(&[AuthenticatedShare]) -> Result<[[Σx]], _> folds a slice with auth_add — the MAC-carrying, zero-round analogue of the backend's plain run_secure cumulative-SUM aggregate (empty input is a fail-closed Protocol error). All addends must be under the SAME session α and on the same party points. Scope (honesty): auth_sum only propagates the MAC relation (α·Σx) for same-session, honestly formed inputs — it never invokes mac_check itself; tamper detection requires the caller to include the result in a successful §2.5 batched mac_check before opening or relying on it, and the malicious-with-abort claim for this chain remains research-grade (internally re-audited, EXTERNAL accredited-cryptographer sign-off PENDING sq-qhy4).
• IT-MAC-hardened threshold disclosure over an EXISTING sum (sq-6fv7, auth_disclose module) — [SONNET-4.6] EXPERIMENTAL, tamper-evident only — it does NOT withstand an actively-deviating party; see the tier correction below. The IT-MAC twin of disclose_threshold_verdict, closing the sq-ka8m residual: the federation £100k path runs over an EXISTING [sum] via an in-MPC decomposition (not cleartext bit-sharing) — the masked-open one originally, the authenticated Rabbit one since sq-km34.6 — whose THREE opens were still semi-honest. This routes all three through the §2.5 MAC-check: the existing sum is authenticated (authenticate_existing), the mask bits come from an AUTHENTICATED square protocol (the c = a² open MAC-checked per bit), the masked open c = sum + r is MAC-checked before its bits are read, and the boolean verdict is MAC-checked before open — so a tamper on any of the three (a forged share / a wrong re-sharing) aborts fail-closed with MpcError::MacCheckFailed at the minimal n = 2t+1. [SONNET-4.6] Tier correction — this is NOT AXIS-1 Malicious today. MacSession::auth_mul ADOPTS a value tamper on its second operand, and the range proof's zero-test mask sits in exactly that slot: zeroing it makes the zero-test answer "yes, zero" for any input, switching the range proof off so a corrupted decomposition yields a wrong verdict instead of an abort (witness a_zeroed_zero_test_mask_defeats_the_range_proof_and_flips_the_verdict). The delivered tier is honest-majority tamper-EVIDENT-with-abort on the opened values — AXIS-2 Abort(Unanimous), AXIS-3 HonestMajority — a real but PARTIAL hardening over the semi-honest twin. Do not deploy it as the integrity tier until MacSession gains multiplication-gate verification binding BOTH operands (Chida-et-al. style). Confidentiality (only the verdict bit is disclosed) is unaffected. Also pending sq-qhy4 external sign-off. The exact sum is NEVER opened — only the sign-independent a², the statistically-masked sum + r, and the 1-bit verdict (the latter two only after their checks pass). public_threshold < 2^60 ([SONNET-4.6] sq-km34.6 routed this path onto the AUTHENTICATED Rabbit decomposition, so the masked-open path's 2^20 cap is gone; the masked-open helpers are now test-only) and n >= 2t+1 are fail-closed; the sum's magnitude is checked in-protocol by the sq-nx0s range proof, now MAC-checked end to end (sq-m4zi/sq-e7ma, auth_verify_sum_in_range): its two zero-tests each form [[v·r]] via auth_mul and MAC-check the product before its open is read, so a tampered zero-test open (which could otherwise flip "was it zero?" to smuggle an out-of-range sum past the guard) also aborts with MpcError::MacCheckFailed. So all opens on the tamper-evident disclose path — the a², the c = sum+r, the two range-proof v·r products, and the verdict — are MAC-checked.
  • experimental_tamper_evident_disclose_threshold_verdict(backend: &ShamirBackend, sum_shares: &[Share], public_threshold: u64) -> Result<PartialResult, MpcError> — the MAC-checked four-flatmates disclose: from a secret-shared sum, a one-cell ?over_threshold boolean partial; aborts on a tampered OPEN. [SONNET-4.6] It does NOT abort on every deviation — see the tier correction above; "never returns a wrong verdict" is disproved by the zeroed-zero-test-mask witness. The drop-in IT-MAC-hardened counterpart to disclose_threshold_verdict. [SONNET-4.6] Renamed in review round 2 from malicious_disclose_threshold_verdict: the old name advertised an integrity tier the code demonstrably misses, and a doc caveat on a malicious_*-named drop-in is not containment. No alias is kept under the old name. The break is NOT a regression from the sq-km34.6 Rabbit lift — auth_secret_is_zero is unchanged from the pre-lift origin/main, whose masked-open range proof fed it the same adopted second-operand mask twice — so reverting would remove the witness, not the break; the real fix is multiplication-gate verification in MacSession.
• Bounded property-path operator — a fixed-k SPARQL property path ?a (p){k} ?b (and bounded {m,k}) realised by unrolling the PUBLIC bound k into a finite disjunction of fixed-length BGP chains (research/mpc-bounded-property-path-design.md). Two regimes:
  • bounded_path::eval_bounded_path_disclosed(edges: &DisclosedEdges, form: &PathForm) -> Result<PartialResult, MpcError> (sq-py8h.1) — the DISCLOSED-key regime: every endpoint AND intermediate ?z_i is a disclosed global IRI, so the chain is a crypto-free fold of DisclosedKeyJoin + union + dedup (no MPC round runs). PathForm::{ exact, range, repeat_step, sequence } builds the form; PathStep::{ predicate, alternation } a hop; refuses any unroll exceeding MAX_UNROLL_CHAINS (public, pre-allocation).
  • hidden_path::eval_exact_k_chain_hidden(backend: &ShamirBackend, edges: &HiddenEdges, k: usize, bound: usize) -> Result<PartialResult, MpcError> (sq-py8h.2 — the cryptographic core) — the HIDDEN-intermediate exactly-k chain: the intermediate node values are PRIVATE (HiddenNode { key: Fp, term: Term } / HiddenEdge { subject, object } / HiddenEdges::new(Vec<HiddenEdge>)). Each internal hop equality e_i.object == e_{i+1}.subject is a secret-shared compare::secure_equal_to_bit bit (never opened — closes the per-hop L2 leak at the decision); the k − 1 hop bits are AND-chained (mul_shares_raw + degree_reduce, the sq-dvuc keystone) into a per-tuple chain bit, OR-folded per distinct DISCLOSED endpoint pair (set semantics — realized length never revealed), and the connected-bit drives oblivious_set_output as a MatchBit::SecretShared selector (padded+shuffled to the public B). Intermediate node keys are never reconstructed. eval_exact_k_chain_hidden_slots(..) returns the raw B shuffled OutputSlots + ObliviousOutputCost (the transcript view). Fail-closed: k >= 1, n >= 2t+1, |E|^k <= MAX_CHAIN_TUPLES, and B >= candidate count. Honest-majority, semi-honest only (sq-qhy4 external sign-off pending). Hidden-key endpoint DISTINCT (sq-py8h.4) and the planner guard (sq-py8h.5) build on this.
  • hidden_path::eval_bounded_path_hidden(backend: &ShamirBackend, edges: &PredicatedEdges, form: &HiddenBoundedPath, bound: usize) -> Result<PartialResult, MpcError> (sq-py8h.3 — bounded HIDDEN union) — the bounded repetition {1,k} / {0,k} / p? ({0,1}) + per-hop alternation (p_1|…|p_a) over the SAME secret edge set, built as a union of fixed-length predicate chains (HiddenBoundedPath::{ range, exact, optional, alternation }; PredicatedEdge { predicate: String, subject, object } / PredicatedEdges::new(Vec<PredicatedEdge>) tag each edge with its PUBLIC predicate). Every (length, alternation-branch, edge-tuple) chain bit is OR-folded per distinct DISCLOSED endpoint pair into one secret-shared connected-bit (secret_or = 1 − (1−x)(1−y), one mul_shares_raw + degree_reduce each), so a pair reached by several lengths/branches appears exactly once and the realized length is never revealed (design §1.2 length-revealing prohibition). For {0,k}/p? the length-0 reflexive diagonal (x,x) over the disclosed node domain is OR-folded in with a constant shared 1 (design §2.3). The per-hop predicate gate is a fully PUBLIC decision (mismatch → constant shared 0, no crypto). eval_bounded_path_hidden_slots(..) is the transcript view. Fail-closed: non-empty alternation, min <= max, n >= 2t+1, total tuple work Σ_ℓ (a^ℓ·|E|^ℓ) <= MAX_CHAIN_TUPLES (PUBLIC, pre-crypto), B >= candidate count. Same security tier (honest-majority, semi-honest only).
  • hidden_path::planner::plan_hidden_bounded_path(req: &HiddenPathRequest, edge_count: usize) -> Result<BoundedPathPlan, MpcError> (sq-py8h.5 — planner guard + cost-model wiring) — the planner-facing layer (no crypto; closed-form over PUBLIC params). HiddenPathRequest::{ range, unbounded } (its max: PathUpperBound::{ Finite(k), Open } can REPRESENT an open bound, unlike the bounded HiddenBoundedPath). (a) a statically-large unroll (Σ_ℓ a^ℓ·|E|^ℓ over-cap or u64-overflow) is REJECTED with MpcError::Protocol at plan time; (b) an Open upper bound ((p)+/(p)*/{m,}) is REFUSED fail-closed via MpcError::NoBackendSatisfies — never approximated by a default k (that would be a wrong answer the verifier could not recompute; the bound must be explicit + public); (c) the returned BoundedPathPlan { form, edge_count, projected_tuples, secure_equalities, warn } carries .comm_counter(parties, bound) -> CommCounter modelling the operator's cost (the k×-join secure equalities + the O(k) AND/OR degree-reduction rounds + the B-slot oblivious output), which the matrix runner reads for its QueryClass::HiddenBoundedPath cell (bench::check_bounded_path is the co-gated correctness anchor). warn flags an admissible-but-heavy projection (within reach of the cap).
  • hidden_distinct::distinct_hidden_pairs(backend: &ShamirBackend, pairs: &[SecretEndpointPair], bound: usize) -> Result<PartialResult, MpcError> (sq-py8h.4 — hidden-key endpoint DISTINCT, the gated sub-piece) — collapse duplicate secret endpoint pairs (SecretEndpointPair { a_key: Fp, b_key: Fp, a_term, b_term } — both endpoints PRIVATE keys, dup'd across input rows; distinct from the sq-py8h.3 OR-fold which collapses multiplicity ACROSS chain lengths over a DISCLOSED key). Construction: oblivious-sort the rows by their secret composite key over the data-independent oblivious::SortingNetwork, deciding each compare-exchange with a never-opened secure comparator (compare::secure_greater_than + secure_equal_to_bit, lexicographic on a then b) driving an arithmetic conditional swap x' = x + b·(y−x) of the key limbs (mul_shares_raw + degree_reduce); then an adjacent-equality scan (secure_equal_to_bit per limb, ANDed → secret keep = 1 − dup, first occurrence kept); then oblivious compaction by feeding each row as a MatchBit::SecretShared(keep) Candidate into oblivious_set_output (padded+shuffled to the public B, duplicates open to Dummy). No key is ever opened; the multiplicity structure and input→output linkage are hidden; distinct_hidden_pairs_slots(..) / distinct_hidden_pairs_oblivious(..) are the transcript views; DistinctCost { rows, sort_compare_exchanges, adjacent_equalities, output_bound } is the modelled (not measured) cost. Fail-closed: n >= 2t+1, N <= MAX_DISTINCT_ROWS, B >= N, every key < 2^COMPARE_BITS. Honest-majority, semi-honest only (sq-qhy4 external sign-off pending).
• End-to-end federated pipeline driver (sq-6y92, pipeline module) — the GLUE that composes holder → secret-share → disclosed-key join → secure-threshold → reconstruct → ProofStatement into ONE worked four-flatmates federated response (architecture §4.3 steps 1–6). Composes the EXISTING primitives only — invents no crypto; proof.prove stays the honest NotYetImplemented stub.
  • run_federated(backend: &ShamirBackend, flatmates: &[Flatmate], query: &FederatedQuery) -> Result<FederatedResponse, MpcError> — runs all six steps. Precondition: backend.parties() == flatmates.len() (each flatmate is one honest-majority compute party) and a non-empty federation, both fail-closed Protocol errors.
  • Flatmate { holder: Holder, disclosed_fragment: &str, issuer_key: String } — one participant: its wallet, the SELECT fragment it discloses locally (projecting the global-IRI join key; the PRIVATE salary is NOT in it), and the issuer key collected into the statement's key-set K.
  • FederatedQuery { join_var: oxrdf::Variable, federated_query: &str, threshold: u64 } — the global-IRI join key, the full federated query (used verbatim as the union-store differential query + ProofStatement.query), and the public threshold for the secure comparison.
  • FederatedResponse { disclosed_result: PartialResult, over_threshold: bool, verdict_partial: PartialResult, routing: Vec<OperatorRouting>, statement: ProofStatement } — the disclosed join result (byte-equal to the plaintext union-store eval), the > threshold verdict bit (only the bit is opened; the exact sum is never reconstructed across the boundary), the explicit per-operator routing, and the assembled ProofStatement (real disclosed_result, no proof). .verdict() -> bool.
  • OperatorRouting { operator: String, routing: Routing } + Routing::{ Disclosed, Hidden(OperatorClass) } — the explicit per-operator disclosed-vs-hidden decision (RQ2a): the membership join is Disclosed (crypto-free), the salary aggregate is Hidden(LinearAggregate), the threshold is Hidden(Comparison).
  • federation_holder_id() -> HolderId — the synthetic federation id the disclosed result is attributed to.
• Network tier — REAL multi-process transport (sq-tg6b + sq-bdbv, transport module) — the measured-cost counterpart of the in-process counting tier. Each party is its own OS process exchanging the actual protocol messages over loopback TCP (127.0.0.1); a star Coordinator deals shares + collects opens, exactly as the in-process dealer does but over a socket. Native-only (sockets/processes have no browser story; sparq-mpc is excluded from sparq-wasm). The transport types are generic over any Read + Write, so a Unix-domain stream — or a tc netem-shaped loopback (Tier 3, privileged; netprofiles + scripts/mpc-netem.sh) — slots in unchanged. Honesty: the in-process tier emits MODELLED comms; this tier emits MEASURED wall-clock + bytes-on-wire, and the two must AGREE on the protocol RESULT (the load-bearing cross-tier anchor asserted in tests + by the mpc_net_bench driver).
  • run_cell_networked(query_class: QueryClass, backend: &ShamirBackend, dealer: &mut ShamirDealer, values: &[u64], scale: usize) -> Result<NetworkCell, MpcError> — drives one cell over loopback (thread-per-party in-crate; real process-per-party via the mpc_net_bench/mpc_party examples) and returns the MEASURED NetworkCell { result, wall_clock, bytes_sent, bytes_recv, rounds, .. }.
  • The four wire-driven QueryClass cells now run on the wire. (The fifth class, HiddenBoundedPath (sq-py8h.5), has no live-wire Coordinator driver — its cost is wired into the ANALYTIC in-process matrix via BoundedPathPlan::comm_counter, and run_cell_networked REFUSES it with an honest NotYetImplemented rather than fabricate a wire run.) CumulativeSumAggregate + HiddenValueEquiJoin are single-round (deal → local op → open). ObliviousShuffle (AS-Waksman switches) + ObliviousSort (Batcher compare-exchanges) are MULTI-round (sq-bdbv): the Coordinator drives one Message::Swap { a, b, swap } per network gate (StepCode::SwapNetworkAndOpen), so rounds equals the network's gate count. The shuffle samples a fresh secret permutation (oblivious::sample_random_permutation) routed through WaksmanNetwork for the control bits; the sort uses the disclosed-key (sort_with_keys) regime — only the public comparator outcome's boolean crosses the wire, the switch topology is data-independent. The reported result for shuffle/sort is the multiset-invariant column sum (the cross-tier anchor that no row was lost/duplicated/corrupted on the wire); the full permuted-column / ascending-order checks live in the in-crate tests that call Coordinator::shuffle / Coordinator::sort directly. Parties hold only their own share-column and apply local swaps — never reconstruct, never learn the permutation as a whole.
  • Coordinator::{ aggregate, hidden_join, shuffle, sort }, run_party, Channel, Message, StepCode, NetworkCell — the transport surface (a hand-written length-prefixed codec, no serde).
• Fp — field element over F_p, p = 2^61 - 1. Fp::new(u64), Fp::value() -> u64, Fp::zero(), Fp::one().
• Share { x: u64, y: Fp }; field/share helpers in sparq_mpc::shamir (add_shares, sub_shares, mul_shares_raw, add_constant, scale, reconstruct_degree). ShamirDealer::degree_reduce(&[Share]) reduces a degree-2t product back to degree-t so multiplications chain (depth>1).
• MpcError::{ LocalEval { holder, message }, Protocol(String), NotYetImplemented { what, gated_on }, Tampered { detail, cheaters }, NoBackendSatisfies { requirement, considered }, MacCheckFailed { detail } } — the honest error channels: NotYetImplemented for deferred crypto, Tampered for a detected active deviation on a redundant (RS) reconstruction, NoBackendSatisfies for a fail-closed selection refusal, and MacCheckFailed (sq-ka8m) for the batched IT-MAC check (σ ≠ 0) catching a tamper on an authenticated path — distinct from Tampered because it works at the minimal n = 2t+1 (soundness from the secret α, not RS redundancy).
• CollaborativeProof<B: MpcBackend>, Attestation, ProofStatement, Proof, AttestationShare — interface only; every method is a stub returning NotYetImplemented.
• sparq_mpc::federated_binding (sq-34ml) — the two NON-research prerequisites of the buildable M4-v1 verifier-side-attestation interim (research/mpc-m4-distributed-sig-feasibility.md §2/§4), split out of the unsolved Q1 spike. Layout + out-of-circuit binding only — it is NOT a proof and closes NO ZK-audit item (see the limitation below). FieldWord (opaque 32-byte big-endian public-input word; from_be_bytes / as_be_bytes / from_hex / digest), VerifierChallenge::{fresh, fresh_from, from_word, as_word}, ValidityWindow::{new, contains}, FreshnessBinding::tag, key_set_digest(&[String]), SeenChallenges + InMemorySeenChallenges, check_freshness(statement, expected, now, seen), HolderSegment::new(holder, commitments, rows, row_capacity, attribution), FederatedStatement::{new, commitment_digest, freshness_binding, public_input_word_count, reconstruct_public_inputs, bind_public_inputs}, and the fail-closed BindingError (impl From<BindingError> for MpcError → Protocol, never NotYetImplemented).
• SecureRng / MpcRng — the CSPRNG masking seam (you rarely touch these directly).

Common recipes

1. Secure cumulative aggregate over private values (the "four flatmates" sum)

Each holder secret-shares one private integer; the sum is computed over shares (free local addition) and only the total is reconstructed — no individual value is revealed.

use sparq_mpc::{Holder, ShamirBackend, MpcBackend};

const PFX: &str = "@prefix ex: <http://ex/> . @prefix xsd: <http://www.w3.org/2001/XMLSchema#> .\n";
let alice = Holder::from_rdf("alice", &format!("{PFX} ex:a ex:salary \"30000\"^^xsd:integer ."), "turtle")?;
let bob   = Holder::from_rdf("bob",   &format!("{PFX} ex:b ex:salary \"45000\"^^xsd:integer ."), "turtle")?;

let backend = ShamirBackend::new(2)?;                // n parties; honest-majority
let mut shares = backend.share_private_input(&alice)?;   // shares Alice's ex:salary
shares.extend(backend.share_private_input(&bob)?);       // ... and Bob's
let summed = backend.run_secure(&shares)?;               // cumulative sum over shares (0 rounds)
let out = backend.reconstruct_disclosed(&summed)?;       // -> PartialResult: one ?cumulative integer (75000)
# Ok::<(), sparq_mpc::MpcError>(())

share_private_input expects the holder's data to yield exactly one row, one integer column for SELECT ?salary WHERE { ?p ex:salary ?salary }; anything else is a Protocol error (it never guesses). To disclose a threshold like sum > £100k while revealing ONLY the boolean (not the exact total), use the secure comparison (disclose_threshold_verdict, recipe 2) instead of reconstruct_disclosed — the latter opens the integer for an out-of-crypto recompute.

2. Threshold verdict only — sum > £100k without revealing the sum (the four-flatmates disclosure-minimisation)

The secure comparison opens only the boolean verdict — that one bit is the only value that ever leaves the computation; the integer total is never an output. Reuse the secret-shared sum from recipe 1.

use sparq_mpc::{ShamirBackend, MpcBackend, disclose_threshold_verdict, Fp};

let backend = ShamirBackend::new(5)?;                 // n >= 2t+1 (comparison is a mult chain)
let salaries = [30_000u64, 28_000, 26_000, 24_000];   // sums to 108_000
let shared: Vec<_> = salaries.iter().map(|&s| backend.dealer().share(Fp::new(s))).collect();
let summed = backend.run_secure(&shared)?;            // secret-shared cumulative sum
let out = disclose_threshold_verdict(&backend, &summed[0], 100_000)?;
// out: one ?over_threshold = "true"^^xsd:boolean — the £108k total is never an OUTPUT.
# Ok::<(), sparq_mpc::MpcError>(())

Honesty — the sum is bit-decomposed IN-MPC (disclose_threshold_verdict). The sum stays secret-shared end-to-end: there is no local backend.reconstruct(sum_shares) — that shortcut was removed (sq-g7t5). [OPUS-4.8] sq-bgsn lifts the production decomposition to the Rabbit-style full-field protocol (eprint 2021/119, secure_bit_decompose_rabbit): a full-field-width mask [r] (r ∈ [0, 2^61), drawn so no party knows it via the square-protocol random-bit generator) is added and only the (near-)uniform c = (sum + r) mod p is opened, then the sum is recovered exactly through the modular wrap (sum = c − r + w·p, w = 1{c < r} from a public-vs-shared LTBits). Recovering the wrap (rather than avoiding it, as the old masked-open path did) removes the value/mask slack, so the magnitude bound is the full sum < 2^60 (RABBIT_VALUE_BITS) — a 40-bit lift over the masked-open 2^20 — and the open's residual leakage is the 2^{-61} field-size floor (independent of magnitude). An in-protocol range proof (sq-nx0s / verify_value_in_range_rabbit) proves sum ∈ [0, 2^60) from the recovered bits — an over-magnitude sum aborts fail-closed, never returns a wrong verdict. Only the verdict bit is ever an OUTPUT. Honest scope: still honest-majority, semi-honest only — the a²/c = (sum+r) mod p opens and the degree_reduce re-sharings are unauthenticated (sq-qhy4 external sign-off PENDING). The malicious twin (auth_disclose) still uses the lower-magnitude (< 2^20) masked-open decomposition; its Rabbit upgrade is the remaining follow-up.

2b. End-to-end federated response — the four flatmates, all six §4.3 steps in one call

run_federated composes holder → secret-share → disclosed-key join → secure-threshold → reconstruct → ProofStatement. Each flatmate discloses a DISTINCT public fact about the shared flat (joined on the global IRI ?flat) and secret-shares a PRIVATE salary; the response carries the disclosed join result, the > £100k verdict bit (the exact sum is never reconstructed), the explicit per-operator routing, and a ProofStatement whose disclosed_result equals the plaintext union-store eval. proof.prove stays the honest stub.

use sparq_mpc::{run_federated, Flatmate, FederatedQuery, Holder, ShamirBackend, Routing, OperatorClass};
use oxrdf::Variable;

const PFX: &str = "@prefix ex: <http://ex/> . @prefix xsd: <http://www.w3.org/2001/XMLSchema#> .\n";
// Each flatmate: a distinct disclosed flat attribute on ex:flat (joined on ?flat) + a PRIVATE salary.
let mk = |m: &str, fact: &str, salary: u64, frag: &'static str, key: &str| -> Flatmate<'static> {
    let doc = format!("{PFX} {fact} . ex:resident ex:salary \"{salary}\"^^xsd:integer .");
    Flatmate { holder: Holder::from_rdf(m, &doc, "turtle").unwrap(), disclosed_fragment: frag, issuer_key: key.into() }
};
let flatmates = vec![
    mk("alice", "ex:flat ex:rent \"1200\"",            30_000, "PREFIX ex: <http://ex/> SELECT ?flat ?rent WHERE { ?flat ex:rent ?rent }", "did:ex:hr#k1"),
    mk("bob",   "ex:flat ex:city \"Leeds\"",           28_000, "PREFIX ex: <http://ex/> SELECT ?flat ?city WHERE { ?flat ex:city ?city }", "did:ex:hr#k2"),
    mk("carol", "ex:flat ex:landlord \"Acme\"",        26_000, "PREFIX ex: <http://ex/> SELECT ?flat ?landlord WHERE { ?flat ex:landlord ?landlord }", "did:ex:hr#k3"),
    mk("dave",  "ex:flat ex:postcode \"LS1\"",         24_000, "PREFIX ex: <http://ex/> SELECT ?flat ?postcode WHERE { ?flat ex:postcode ?postcode }", "did:ex:hr#k4"),
];
let backend = ShamirBackend::new(4)?;     // n = 4 compute parties == flatmate count (fail-closed if mismatched)
let q = FederatedQuery {
    join_var: Variable::new_unchecked("flat"),
    federated_query: "PREFIX ex: <http://ex/> SELECT ?flat ?rent ?city ?landlord ?postcode WHERE { \
        ?flat ex:rent ?rent . ?flat ex:city ?city . ?flat ex:landlord ?landlord . ?flat ex:postcode ?postcode }",
    threshold: 100_000,
};
let resp = run_federated(&backend, &flatmates, &q)?;
assert!(resp.over_threshold);                                            // 108k > 100k — only the BIT is opened
assert_eq!(resp.routing[0].routing, Routing::Disclosed);                 // membership join in the clear
assert_eq!(resp.routing[2].routing, Routing::Hidden(OperatorClass::Comparison)); // threshold in MPC
// resp.statement.disclosed_result == plaintext union-store eval of q.federated_query (the correctness anchor).
# Ok::<(), sparq_mpc::MpcError>(())

Honest-majority, semi-honest (the ShamirBackend tier, unchanged). proof.prove stays NotYetImplemented — the driver assembles the statement STRUCTURE with the real disclosed result, it does NOT fake a proof.

3. Hidden-value join on a private key (circuit-PSI core)

Join two holders on a key WITHOUT revealing the key — only the matched payload columns are disclosed.

use sparq_mpc::{HiddenValueJoin, HiddenKeyedRows, ShamirBackend, HolderId, encode_term};
use oxrdf::{NamedNode, Term, Variable, Literal};

let lit = |s: &str| Some(Term::Literal(Literal::new_simple_literal(s)));
let iri = |s: &str| Term::NamedNode(NamedNode::new(s).unwrap());
// PRIVATE keys are RDF terms encoded into Fp by the collision-resistant
// `encode_term` (domain-separated SHA-512 → field; injective up to the birthday
// bound). Equal terms ⇒ equal keys ⇒ a match; nothing else can match.
let bob = iri("http://example.org/people/bob");
let left  = HiddenKeyedRows { holder: HolderId::new("L"), payload_vars: vec![Variable::new_unchecked("name")],
    rows: vec![(encode_term(&iri("http://example.org/people/alice")), vec![lit("Alice")]),
               (encode_term(&bob), vec![lit("Bob")])] };
let right = HiddenKeyedRows { holder: HolderId::new("R"), payload_vars: vec![Variable::new_unchecked("city")],
    rows: vec![(encode_term(&bob), vec![lit("Leeds")]),
               (encode_term(&iri("http://example.org/people/zoe")), vec![lit("Hull")])] };

let backend = ShamirBackend::new(3)?;                // n=3, t=1 supports the 1 equality multiplication (2t+1<=n)
let joined = HiddenValueJoin::new(backend).join(&left, &right)?;
// joined.vars == [?name, ?city]; one row Bob-Leeds; non-matching keys dropped; keys never reconstructed.
// For an EXACT injectivity guarantee over a concrete key set, route each key
// through a `KeyEncoder` instead — it fails closed on a false-match collision.
# Ok::<(), sparq_mpc::MpcError>(())

4. Multi-holder chain join on disclosed global IRIs

DisclosedKeyJoin folds pairwise; chain joins by feeding the result back in with the next shared variable.

use sparq_mpc::{DisclosedKeyJoin, GlobalJoin, JoinPlan};
use oxrdf::Variable;
let v = |n: &str| Variable::new_unchecked(n);
// pa: ?p ?x , pb: ?x ?y , pc: ?y ?n  (each a PartialResult from evaluate_local)
let ab  = DisclosedKeyJoin.join(&[pa, pb], &JoinPlan { join_var: v("x"), key_disclosed: true })?;
let abc = DisclosedKeyJoin.join(&[ab, pc], &JoinPlan { join_var: v("y"), key_disclosed: true })?;
# Ok::<(), sparq_mpc::MpcError>(())

5. Inspect a backend's guarantees before trusting it

A federation should refuse a backend whose guarantees don't match its threat model.

use sparq_mpc::{ShamirBackend, MpcBackend, TrustModel, MaliciousSecurity};
let info = ShamirBackend::new(3)?.info();
assert_eq!(info.trust_model, TrustModel::HonestMajority);
// At n=3,t=1 there is one redundant share → tampering is detected & aborts
// (but a cheater can still force an abort: no guaranteed output). With more
// redundancy (n>=4) it becomes HonestMajorityRobust { max_cheaters }.
assert_eq!(info.malicious_security, MaliciousSecurity::HonestMajorityAbort);
assert!(info.malicious_secure());           // coarse "hardened at all?" bit
# Ok::<(), sparq_mpc::MpcError>(())

State the requirement UP FRONT and let a fail-closed registry match it — an over-strong request is truthfully REFUSED, never silently downgraded:

use sparq_mpc::{ShamirBackend, BackendRegistry, SecurityRequirement, MpcError};

let mut registry: BackendRegistry<ShamirBackend> = BackendRegistry::new();
registry.register(ShamirBackend::new(3)?);

// A requirement the shipped (honest-majority, semi-honest) backend meets → returns it.
let backend = registry.select(&SecurityRequirement::v1_honest_majority_semi_honest())?;
assert_eq!(backend.parties(), 3);

// A dishonest-majority-malicious request has NO satisfying backend → fail-closed.
let refused = registry.select(&SecurityRequirement::dishonest_majority_malicious());
assert!(matches!(refused, Err(MpcError::NoBackendSatisfies { .. })));
# Ok::<(), sparq_mpc::MpcError>(())

6. Reproducible tests/benches (predictable masks — never production)

[dev-dependencies]            # or [dependencies] only if you understand the risk
sparq-mpc = { path = "crates/sparq-mpc", features = ["insecure-test-rng"] }

let backend = sparq_mpc::ShamirBackend::new_seeded(3, 0xBEEF)?;   // deterministic masks; NO security
# Ok::<(), sparq_mpc::MpcError>(())

7. Handle deferred crypto honestly

The collaborative proof and the hidden-key path of DisclosedKeyJoin are gated; match the error rather than assuming success.

use sparq_mpc::MpcError;
match some_result {
    Err(MpcError::NotYetImplemented { what, gated_on }) =>
        eprintln!("deferred: {what} (gated on {gated_on})"),   // e.g. mentions M3/M4, Q1, ZK #3..#12
    Err(MpcError::Protocol(m)) => eprintln!("precondition: {m}"),
    Err(MpcError::LocalEval { holder, message }) => eprintln!("holder {holder} eval failed: {message}"),
    Ok(_partial) => { /* real result */ }
}

Gotchas / feature flags / prerequisites

• Native-only, not in wasm. sparq-mpc is intentionally absent from sparq-wasm's dependency graph (cargo tree -p sparq-wasm must not show it). The browser bundle carries zero MPC/crypto surface.
• insecure-test-rng feature (OFF by default). Gates ShamirBackend::new_seeded and rng::InsecureTestRng (a deterministic SplitMix64). The masks it produces are predictable — enabling it in a deployment reintroduces the very confidentiality weakness the CSPRNG default fixes. Use it only for reproducible tests/benchmarks. Default builds physically cannot construct a predictable masking RNG. The isolated glue test crates/sparq-mpc/tests/oblivious_join_determinism.rs (whole file #![cfg(feature = "insecure-test-rng")]) leans on this: a fixed (n, seed) yields a bit-identical Vec<OutputSlot> (including the oblivious-shuffled order). That reproducibility is a property of the seeded test RNG only — the production path draws OS-seeded ChaCha20 and is NOT reproducible, and determinism is not a security property. The transport-codec round-trip / malformed-frame tests and the collaborative-proof deferral tests (tests/transport_codec.rs, tests/proof_deferred.rs) need no RNG and run in both feature states.
• Malicious-security is now SURFACED, not blanket-absent. Confidentiality holds against <= t colluding honest-but-curious parties. Against an actively-deviating party, ShamirBackend reports the precise guarantee via BackendInfo.malicious_security (ShamirBackend::malicious_security()): the WI-1 RS-checked / Berlekamp–Welch reconstruction detects tampered shares and aborts when there is redundancy (n > t+1, always true for the honest-majority t), and robustly corrects up to max_cheaters = ⌊(n−t−1)/2⌋ cheaters when redundancy allows (n >= 4). Boundaries that are NOT hardened (do not over-trust): the degree-2t equality/mult open in the hidden-value join has no RS redundancy at n = 2t+1 (the common odd-n case, e.g. n=3,5,7) — a tampered product share there is undetectable; a fix needs an information-theoretic MAC (deferred, bead sq-6d6g). Dishonest-majority remains future work behind the same MpcBackend trait.
• In-process simulation for the PROTOCOL crypto; a real loopback transport for the COST. The protocol crypto (the dealer/HiddenValueJoin plays all parties to deal shares and open results) runs in one process — cleartext inputs are passed to the simulator only to be shared internally. The transport module (sq-tg6b + sq-bdbv) adds a REAL multi-process star-coordinator over loopback TCP for MEASURED cost (all four cells, incl. the multi-round oblivious shuffle/sort), but it remains a star-coordinator measurement harness, not a full party-mesh deployment, and the netem LAN/WAN shaping (Tier 3) needs a privileged host. disclose_threshold_verdict no longer reconstructs the sum — that local shortcut was removed (sq-g7t5); the sum is bit-decomposed in-MPC. [OPUS-4.8] sq-bgsn lifted the production path to the Rabbit-style full-field decomposition (eprint 2021/119, secure_bit_decompose_rabbit): a full-field mask [r] (square-protocol, no party knows it) is added, only the (near-)uniform c = (sum + r) mod p is opened, and the sum is recovered exactly through the modular wrap (sum = c − r + w·p, w = 1{c < r}). With an in-protocol range proof (sq-nx0s), only the verdict bit is ever an OUTPUT. sq-mnv5 deployment residuals (sq-qhy4 external sign-off pending): (1) wider magnitude — CLOSED by sq-bgsn on the semi-honest production path (the Rabbit decomposition recovers the wrap, so the bound is the full < 2^60, up from < 2^20); [SONNET-4.6] sq-km34.6 lifted the IT-MAC twin auth_disclose onto the same authenticated Rabbit construction, so it too supports < 2^60; (2) malicious security — PARTLY CLOSED by sq-ka8m, and [SONNET-4.6] LESS closed than previously written: auth_mul adopts a second-operand value tamper, which is exploitable end to end on the disclose path (see the tier correction on the auth_disclose bullet above), so neither twin is AXIS-1 Malicious today — the malicious-with-abort comparison chain over secret operands now threads IT-MACs (MacSession::auth_mul, design §2.4 route (a)) through every gate and MAC-checks the verdict before open (MacSession::mac_check, §2.5), aborting on a tampered OPEN at the minimal n = 2t+1 ([SONNET-4.6] not on any tamper — the second-operand adoption above applies to this chain too) — see auth_compare (malicious_greater_than / malicious_threshold). The end-to-end disclose_threshold_verdict decomposition opens (a², c = sum+r, the range-proof zero-test v·r products, and the verdict) are now ALL routed through the MAC-check in the IT-MAC-hardened twin auth_disclose::experimental_tamper_evident_disclose_threshold_verdict (sq-6fv7 + sq-m4zi/sq-e7ma) — the semi-honest disclose_threshold_verdict itself stays semi-honest by design (the cheap zero-round honest path). Both remain sq-qhy4 external-sign-off-pending.
• Field & range. Fp is over p = 2^61 - 1. Keep values (salaries, counts, key encodings) well under 2^61 so sums never wrap. Fp::inv(0) panics (only nonzero differences are inverted internally).
• Shamir headroom. A single multiplication (the equality test) needs n >= 2t+1. ShamirBackend::new picks t = (n-1)/2, so the happy path holds; HiddenValueJoin errors with Protocol if you somehow under-provision. reconstruct needs >= t+1 distinct-x shares.
• Hidden-join key encoding — use encode_term, and KeyEncoder if you need an EXACT guarantee. HiddenKeyedRows.rows carry Fp keys; equality in Fp stands in for term equality and is sound only if the encoding is injective over the key domain. encode_term (sq-dl81) makes that a quantified birthday event (≈ q²/2^62, negligible in the ≤10⁴-row regime) rather than an unstated assumption; for an exact guarantee on a concrete key set, drive each key through a KeyEncoder, which detects any false-match collision and fails closed before sharing. What is still deferred to the collaborative proof (M4) is the in-circuit proof that the opened key equals encode_term of the holder's real term (the encoding-correctness proof) — encode_term is its on-ramp, not a substitute. Blank-node labels are keyed verbatim (no cross-graph identity); canonicalise first if you need it. The reduce_mod_p(SHA-512(DOMAIN_TAG ‖ ntriples(term))) construction is byte-stable: a known-answer test (term_encode::tests::sha2_byte_stability_known_answers, sq-jkcj) pins the exact encode_term field elements (plus the bare SHA-256/512 empty-string vectors), so the sha2 0.10→0.11 API bump — and any future drift in the tag/truncation/reduction or oxrdf's N-Triples rendering — fails closed. That is a dependency-maintenance regression guard, not a new soundness/privacy property.
• Hidden join cost. HiddenValueJoin is naive O(|L|·|R|) all-pairs (one secure equality test per pair). No cuckoo/oblivious-hashing PSI optimisation. Honest envelope: minutes-to-tens-of-minutes for ~10³–10⁴ rows/holder on a LAN — not sub-second; do not extrapolate beyond it.
• Hidden-join leakage tiers (L1/L2) — choose the right entry point. HiddenValueJoin::join opens a per-pair match bit and emits the exact match count, leaking the bipartite match graph / key fan-out (L2 at the decision) and the true result cardinality (L1). batched_join (sq-khf9) routes the OUTPUT through pad-to-B + oblivious-shuffle, closing L1 (bounded to B) and the result-set L2 — but it STILL opens the per-pair match bit, so decision-time L2 is unchanged. fully_oblivious_batched_join (sq-xhaw) closes that last leak: the per-pair match bit is computed secret-shared (secure_equal_to_bit) and never opened, so nothing leaks per pair — at O(COMPARE_BITS) secure-mult rounds/pair (vs one masked open). Residual leakage (honest, all tiers): the parties learn only B, but the authorized result recipient still learns the true count by filtering dummies — a padded-bound scheme, not differential privacy. Hiding the count from the recipient too is the separate DP cardinality mode (bead sq-shk5). All hidden-join tiers are honest-majority, semi-honest only (sq-qhy4 external sign-off pending).
• Disclosed-key join is a faithful SPARQL inner join, not a naive key-merge. It enforces agreement on every shared variable (compatible-mapping semantics) and does not trust the planner-named key for soundness; a key absent from any partial is a Protocol error. Output rows are canonicalised (order-independent multiset).
• The M4-v1 federated binding layer binds nothing YET (sq-34ml). federated_binding gives the buildable verifier-side-attestation interim its two non-research prerequisites: an explicit out-of-circuit freshness/replay transcript (FreshnessBinding / check_freshness — ZK audit #4 stops being automatic once the issuer signature is checked beside the proof instead of inside it) and the federated/multi-source reconstruct_public_inputs byte layout spanning every holder's commitments/rows/attribution (#1 generalised to N sources). It is a deterministic byte layout plus a fail-closed transcript check, not a proof: it closes no ZK-audit item, and the whole M4 milestone stays hard-gated on the single-prover ZK-foundation remediation (#3/#4/#5/#6/#8/#9/#12) — CollaborativeProof::prove/verify still return NotYetImplemented. bind_public_inputs becomes load-bearing only once a collaborative proof exists to supply the public_inputs it byte-compares against. The interim it targets also gives up source-unlinkability (the verifier learns which issuer key signed each graph, not merely "some key in K") and a single succinct signature↔witness binding. No soundness or privacy property is asserted as achieved; the ZK verifier this layout targets is internally re-audited but NOT externally audited (sq-qhy4), and the MPC substrate is honest-majority semi-honest only. Two layout details are load-bearing and tested: holder segments are canonically ordered (sorted by HolderId, duplicates refused) so prover and verifier serialise identical bytes, and each segment carries explicit k_i/r_i arity words — without them a segment body (2k + 3r + 1 words, no internal boundary marker) is ambiguous, and a prover could present three committed graphs as six while still byte-matching (federated_layout_binds_segmentation exhibits the exact colliding pair).
• Collaborative proof is a stub. CollaborativeProof, Attestation, ProofStatement are interface + docs only; every method returns NotYetImplemented. They are hard-gated on the single-prover ZK soundness remediation (issuer-signature / replay / FILTER-binding / attribution / revocation) and the open research question of verifying a signature over a secret-shared witness (Q1, milestone M4). Do not assume any correctness/attestation guarantee from this crate yet — only confidentiality of the secret-shared inputs under the semi-honest model.

See also

• sparq-fedplan-mpc (opt-in crate, fedplan-mpc feature OFF by default) — the untrusted-planner → MPC-routing seam that produces the Vec<OperatorRouting> this crate's pipeline today receives hand-written. Phase 1 (bead sq-2q1x) landed the per-source SourcePrivacyDescriptor (default-deny — a predicate is private unless explicitly marked Disclosability::Public). Phase 2 (bead sq-fix4) landed the source-selection adapter select_private_sources: it runs sparq-fedplan::select_sources, then prunes any source that has declared it will not participate (participates == Some(false)), surfacing the retained per-pattern candidate set + an audit trail (pruned). The only prune rule is participation/authorisation — a source holding a private predicate stays a candidate (its in-clear-vs-MPC routing is the Phase-3 decision), so the adapter is recall-safe; a duplicate descriptor for one source id is refused (SeamError::DescriptorMismatch). Phase 3 (bead sq-i1wh2) lands the disclosed/hidden routing pass route_operators(&selected, &privacy, &operators, policy): per QueryOperator (a label + an OperatorClass + its Operands — a GlobalIri or a Predicate), it routes Disclosed when every operand is disclosable in the clear and Hidden(class) otherwise (default-deny; the most-private contributing source wins per operand), emitting the Vec<OperatorRouting> the pipeline consumes. The RoutingPolicy knob is Default (disclose global-IRI operands, per convention #6 — reproduces the hand-written four-flatmates routing exactly, the load-bearing differential) or Strict (the §5 "hide even a public term" knob — hides a global IRI whose predicate a contributing source marked private). It is routing plumbing — not a cryptographic guarantee: it performs no MPC, opens nothing, makes no privacy/soundness claim, and computes only the proposed partition. Phase 4 (bead sq-pwr.2) lands the leakage-envelope assembly + dual ratification. assemble_leakage_envelope(&routing, &operators, &selected) derives, from the Phase-3 routing, a declared LeakageEnvelope that honestly enumerates what the plan reveals — the operator structure (count/class/label, per OperatorDisclosure), the disclose/hide partition, the disclosed operands each Disclosed operator exposes in the clear (distinct_disclosed_operands()), and the participating sources — over-counting, never under-counting the leak; a routing/operator mismatch is fail-closed (SeamError::DescriptorMismatch, phase LeakageEnvelope). ratify_envelope(&env, &holders, verifier_budget) then runs the dual gate, returning a RatificationOutcome: each holder fail-closed-rejects a plan disclosing one of its own private predicates (constraint C-B — HolderRejected, the most-private holder wins, the data owner's veto is primary), AND the verifier rejects an over-leaking envelope whose distinct-disclosed-operand count exceeds verifier_budget (VerifierRejected; None = no cap). It is leakage-accounting + a plan-time policy gate — not a cryptographic enforcement (not a runtime guarantee a malicious holder/verifier honours it): it runs no MPC and makes no soundness/privacy claim. Honest leakage: the plan reveals the operator structure, the disclose/hide partition, the disclosed operands, and source participation — but not hidden-operand values or result cardinalities. Phase 6 (beads sq-pwr.3 + sq-xkrt) lands the FedUP-style (WWW'24) result-aware source-combination prune prune_source_combinations(&bgp, &sources, &selected). A federated query executes a conjunction of patterns and the seam's secure-join cost grows with the number of source combinations (one source per pattern) it considers; this pass surfaces which combinations provably contribute no answer so the seam routes fewer toward MPC. Two recall-safe, summary-expressible rules. Rule C1 — unsatisfiable-conjunct collapse: if any pattern's Phase-2 candidate list is empty, that conjunct is a proved-empty relation (by the upstream HiBISCuS recall-safety + the recall-safe participation prune), so the whole conjunction is unsatisfiable (∅ ⋈ R = ∅) and every combination is dead. Rule C2 — dead same-source star pairing (the FedUP quotient-summary/provenance rule, and the one that fires on the live path): a source's served characteristic sets (scs:) partition its subjects by their exact predicate set, so if two patterns share a subject-position join variable and no characteristic set of a source carries both their predicates, no subject of that source satisfies both conjuncts — assigning both patterns to that source is dead, and so is every combination containing that pairing. The source stays a valid candidate for each pattern individually (a cross-source combination is untouched); a candidate is removed only when the peer pattern's sole candidate is that same source, and when that leaves a pattern with no live source the BGP collapses like C1. Rule C2 fires only behind a completeness guard — Σ_{C ∋ p} subjects == void:distinctSubjects over sets with distinct keys — which a truncated (long-tail-elided, per sparq-introspect's max_char_sets) or unknown-distinctSubjects summary fails, as does a repeated exact-predicate-set key (two entries under one key are not a partition, so their sums prove nothing), so an unprovable case declines rather than over-prunes (the load-bearing recall-safety test). It returns a PrunedCombinations { per_pattern (carried through unchanged — advisory + auditable, nothing silently removed), bgp_satisfiable, empty_patterns, dead_patterns, dead_pairings, components (the BGP join-graph connected components, deterministic), pruned }; is_bgp_dead() / surviving_combination_patterns() / combination_is_dead(&assignment) are the convenience accessors (the last returns false — "keep it" — for anything it cannot prove). The value-overlap / bound-IRI-propagation prune is deliberately declined as not recall-safely expressible from the public SourceDescriptor summary (a single-IRI may_hold_authority test, no authority-set enumerator; a bound IRI position is already pruned per-source by select_sources Rule 2, and a join variable binds data-dependent values unknown at plan time) — recorded as a negative result so no contributor builds an unsound prune. It is selection plumbing — not a cryptographic guarantee: it performs no MPC, reads only the already-public Phase-2 selection, and makes no privacy/soundness claim; a selection whose pattern ids are not a permutation of 0..bgp.patterns.len() (wrong count, out of range, or repeated — leaving a pattern undescribed) is fail-closed (SeamError::DescriptorMismatch, phase SourceCombination). Phase 5 (bead sq-1fo4) lands the untrusted-plan binding seam — its CANONICALISATION half ONLY. commit_plan(&selected, &routing, &envelope) reduces the produced plan — the Phase-2 per-pattern source assignment, the Phase-3 disclosed/hidden route, and the Phase-4 declared participation set — to a deterministic, domain-separated PlanCommitment whose plan_digest() is a single sparq_mpc::FieldWord (the same SHA-512, length-prefixed, < 2^248 public-input word federated_binding uses, under a fresh sparq-fedplan-mpc/plan-binding/*/v1\0 tag family), i.e. a value shaped to become a public input once a collaborative proof exists to carry it. It binds plan content, not the planner's enumeration order (per-pattern source lists and disclosed-operand lists sorted; patterns ordered by index), and deliberately excludes the Phase-2 estimated_cardinality (a cost estimate, not plan semantics; no canonical f64 encoding). revalidate_plan(&claimed, &observed) compares a claimed commitment against an independently recomputed one and fails closed, returning PlanRevalidation::Diverged with a structured PlanDivergence list naming the dropped source (SourceDropped) or re-routed operator (OperatorRerouted) rather than a bare mismatch; a digest mismatch with no field-level difference still yields DigestMismatch, so Bound is never returned on a digest mismatch. A routing/envelope disagreement (operator count, label, disclose/hide route, hidden-operator class), a hidden operator whose envelope lists disclosed operands (it runs under MPC and discloses nothing), an envelope participation set that is not exactly the distinct source set the selection assigns (an omitted or an extra participant), a non-permutation pattern-index set, or a duplicated source id in one pattern is refused at commit time (SeamError::DescriptorMismatch, phase PlanBinding). This is a canonicality + transcript-integrity check, NOT a soundness mechanism — a malicious planner computes the plan and its commitment, so one that drops a source can simply commit to the plan it actually ran and pass; it catches accidental divergence (a plan mutated between ratification and execution, a planner/verifier disagreement, a truncating transport). The soundness half — bind_plan_to_proof, the step that would discharge constraint C-A — is DEFERRED: it carries its real signature and returns SeamError::Deferred naming its gates, because there is no collaborative proof to bind to (sparq-mpc::proof is an honest NotYetImplemented stub), sq-qhy4 + sq-9hrn are pending, and the attachment point is design-record §9 Q3, still OPEN (the FederatedStatement parameter is a proposal for the maintainer, not a settled decision). The PlanCommitment carries plan metadata only — source ids, operator labels, classes and disclosed predicate ids, all already declared by the Phase-4 envelope — so it widens the declared leakage by nothing. The further privacy-bearing work (Phase 5's bind_plan_to_proof soundness half, authenticated-input attestation) remains deferred and audit-gated (sq-9hrn / sq-qhy4). See research/mpc-untrusted-planner-routing-design.md.
• mpc-protocols — the SOTA / primitive background (secret sharing, garbled circuits, collaborative zk-SNARKs, authenticated-input MPC) behind the trust-model and primitive choices here.
• noir-circuit-patterns, noir-optimisation, verifiable-credentials-zk, sparql-formal-semantics — the single-prover ZK estate this crate will eventually compose with for the (deferred) collaborative proof.