mpc

name

mpc

description

Run a SPARQL query across multiple mutually-distrusting RDF data holders (federated MPC) — per-holder local sub-evaluation, crypto-free disclosed-key global-IRI joins, and an honest-majority Shamir secret-sharing backend for secure cumulative aggregates + hidden-value (private-key) joins. Use for confidential federated SPARQL / secret-shared aggregates / private set-intersection joins over RDF. EARLY/RESEARCH, native-only; honest-majority with RS-consistency-checked reconstruction (tamper DETECTION + abort, and robust correction where redundancy allows) — semi-honest is the floor when no redundancy exists (e.g. the degree-2t equality open at n=2t+1, detection-only); NOT dishonest-majority / not full malicious security. Collaborative ZK proof of correctness+attestation is a stub.

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.

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.

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) — DESIGN + SEAM, no dealer-less crypto ships. 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(). The ONLY implementor is ShamirDealer, reporting RandomnessModel::TrustedDealerSim (deployable() == false) — the current single-dealer path is labelled honestly as the SIMULATION it is (the dealer knows every mask). PRSS (non-interactive, small-n) vs coin-toss (interactive, any-n) vs dealer-less VSS + the r = 0 malicious defense are follow-on beads behind this trait. Design: research/mpc-distributed-randomness-design.md.
  • 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(&[[[y_1]]..]]) -> Result<(), MpcError> (§2.5 batched check; 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).
• Malicious-with-abort threshold disclosure over an EXISTING sum (sq-6fv7, auth_disclose module) — the malicious-with-abort twin of disclose_threshold_verdict, closing the sq-ka8m residual: the federation £100k path runs over an EXISTING [sum] via the masked-open decomposition (not cleartext bit-sharing), 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. Same tier as auth_compare (AXIS-1 Malicious, AXIS-2 Abort(Unanimous), AXIS-3 HonestMajority); 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^20 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 malicious disclose path — the a², the c = sum+r, the two range-proof v·r products, and the verdict — are MAC-checked.
  • malicious_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 any tampered open, never returns a wrong verdict. The drop-in malicious-with-abort counterpart to disclose_threshold_verdict.
• 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.
• 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); the malicious twin auth_disclose still uses the lower-magnitude masked-open path, whose Rabbit upgrade is the remaining follow-up; (2) malicious security — PARTLY CLOSED by sq-ka8m: 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 any tamper at the minimal n = 2t+1 — 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 malicious-with-abort twin auth_disclose::malicious_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).
• 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 (bead sq-pwr.3) 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. The one recall-safe, summary-expressible rule is 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. It returns a PrunedCombinations { per_pattern (carried through unchanged — advisory + auditable, nothing silently removed), bgp_satisfiable, empty_patterns, components (the BGP join-graph connected components, deterministic), pruned }; is_bgp_dead() / surviving_combination_patterns() are the convenience accessors. 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/BGP length mismatch is fail-closed (SeamError::DescriptorMismatch, phase SourceCombination). The further privacy-bearing phases (untrusted-plan soundness re-validation, authenticated-input attestation) remain 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.