claim_mpc

A K-of-N threshold-signing oracle for boolean claims, built on multi-party computation (MPC).

A client submits a claim — a string containing a boolean expression over integers, such as 2 + 3 == 5 — to a simulated network of N nodes. Each node independently parses and evaluates the claim, then makes a noisy endorsement decision. If and only if at least K nodes endorse it, exactly K endorsing nodes jointly produce one standard ECDSA signature over the claim, verifiable against one fixed network public key by any stock verifier. The private key never exists in one place: distributed key generation gives each node a share, and threshold signing combines share contributions, never the shares themselves.

Not production cryptography. The protocols are hand-rolled, unaudited, honest-path-only implementations built for this exercise. See Security assumptions and Deferred Byzantine behaviour.

Build, test, run

cargo build              # build library + CLI
cargo test               # full suite (unit + end-to-end), a few seconds
cargo clippy             # lints (clean)
cargo fmt                # format

# a true, a false, and a malformed claim:
cargo run -- "2 + 3 == 5" "(4 - 1) > 5" "2 +"

# tweak parameters and make the noise deterministic:
cargo run -- --nodes 3 --threshold 2 --p-true 0.95 --p-false 0.01 --seed 42 "7 * 6 == 42"

The repo ships a Nix flake (nix develop) pinning the toolchain.

CLI

claim_mpc [OPTIONS] <CLAIM>...

-n, --nodes <N>       number of nodes                      [default: 3]
-k, --threshold <K>   endorsements required to sign        [default: 2]
    --p-true <P>      endorsement probability, true claim  [default: 0.95]
    --p-false <P>     endorsement probability, false claim [default: 0.01]
    --seed <U64>      seed the endorsement RNG (deterministic noise)
    --fresh-paillier  generate fresh Paillier keys instead of the
                      checked-in demo fixtures (slow: safe-prime search)

Each claim prints either

Signed {
    claim:     "2 + 3 == 5"
    quorum:    [0, 1]
    signature: 6e7a60eb…bc00        # 64-byte (r ‖ s), verified before printing
}

or a clean NotSigned { claim, reason } — too few endorsements is a normal outcome, not an error. The Paillier keys default to checked-in demo fixtures (insecure by construction — the primes are in the source) so the demo is instant; --fresh-paillier runs the real safe-prime generation.

Architecture

src/
  rounds.rs      synchronous round model + deterministic in-memory driver
  expr/          claim language: parser wrapper, checked evaluator, limits
    grammar.lalrpop  the claim grammar (lalrpop → LALR(1) parser)
  dkg/           distributed key generation (GJKR-style, Pedersen + Feldman VSS)
    poly.rs        Z_q polynomials, Lagrange interpolation
    pedersen.rs    hiding commitments (sharing phase)
    feldman.rs     G-only commitments (key extraction)
    protocol.rs    the DKG rounds
  sign/          GG18 threshold-ECDSA signing
    paillier.rs    Paillier cryptosystem + demo fixtures
    mta.rs         multiplicative-to-additive share conversion
    keyshare.rs    aux round (Paillier directory) + per-node KeyShare
    protocol.rs    the signing rounds (R0–R5)
  network.rs     nodes, noisy endorsement, quorum, client-facing API
  main.rs        CLI client

All communication is in-memory: protocols implement RoundProtocol and run in lockstep under rounds::run_controlled, which routes each round's outboxes into the next round's inboxes. Outgoing::broadcast is the send_to_all primitive. There is deliberately no real networking, no async runtime, and no actor framework.

Protocol flow

client submission
→ claim broadcast (simulated send_to_all)
→ deterministic evaluation             (expr::check, identical at every node)
→ noisy endorsement decision           (one RNG draw per node)
→ endorsement collection
→ quorum selection                     (first K endorsing nodes, only endorsers)
→ threshold signing                    (GG18 over the quorum)
→ signature verification               (stock verifier, before release)
→ client result                        (Signed / NotSigned)

Claim language

Claims are hostile input, parsed by a table-driven LALR(1) parser generated by lalrpop — no eval, no shell, no dynamic code:

claim   := arith cmp arith EOF        (exactly one comparator)
cmp     := "==" | "!=" | "<" | "<=" | ">" | ">="
arith   := term (("+" | "-") term)*
term    := factor (("*" | "/") factor)*
factor  := "-" factor | primary
primary := integer | "(" arith ")"

Parsing and evaluation are separate steps. Evaluation uses checked i64 arithmetic: division by zero and overflow are clean errors, never panics. Limits: 1024-byte input cap (the parser's stack lives on the heap and the AST is no deeper than the input is long, so this alone bounds evaluator recursion), single-pass evaluation — a claim cannot hang or exhaust a node. Parse errors keep byte offsets and expected-token lists; trailing input, a second comparator, and unsupported syntax are all rejected.

What is signed: the ECDSA message is SHA-256("claim-mpc-v1/claim" ‖ claim-UTF-8-bytes) — the raw claim string under a fixed domain-separation tag, not a normalized parse. A verifier needs exactly the submitted string; even reformatting (2+3==5 vs 2 + 3 == 5) is a different signed message.

Noisy oracle and probability analysis

Each node behaves independently per claim: it endorses a true claim with probability p_true = 0.95 and (incorrectly) endorses a false claim with probability p_false = 0.01. Both are configurable. The decision is a single u64 draw from an injected RNG (seedable from the CLI, scriptable in tests), so noise is deterministic under test.

For independent nodes with per-node endorsement probability p,

P(sign) = Σ_{i=K..N} C(N, i) · pⁱ · (1 − p)^(N − i)

the binomial tail P(at least K of N endorse). For the initial N = 3:

K	P(sign true claim)	P(miss true claim)	P(sign false claim)	P(reject false claim)
1	0.999875	0.000125	0.029701	0.970299
2	0.992750	0.007250	0.000298	0.999702
3	0.857375	0.142625	0.000001	0.999999

Default configuration: K = 2, N = 3 (nothing is fixed here — both are CLI flags; this is just the default and why it is a sensible one).

• K = 1 is unacceptable on both axes: a false claim gets signed ~3% of the time, and cryptographically a single node can sign — there is no threshold security at all.
• K = 3 is extremely safe against false claims but misses ~14.3% of true claims (any single noisy rejection blocks signing) and has no availability margin: one crashed node halts the service.
• K = 2 signs 99.275% of true claims and only 0.0298% of false ones, and a single compromised or crashed node can neither forge nor halt.

A more robust configuration: K = 3, N = 5.

Config	P(sign true)	P(miss true)	P(sign false)
2-of-3	0.992750	0.007250	2.98 × 10⁻⁴
3-of-5	0.998842	0.001158	9.85 × 10⁻⁶

Growing to 3-of-5 improves both directions at once — ~6× fewer missed true claims and ~30× fewer falsely signed ones — because majority voting concentrates: with more nodes the two binomial distributions (around N·p_true and N·p_false) separate more sharply, and any K strictly between them wins on both axes. The costs are operational: more nodes to run, and signing traffic that grows quadratically in K (the MtA step is pairwise). The same trend continues (e.g. 4-of-7); pick K/N strictly between p_false and p_true, biased upward only as far as the false-positive budget requires.

Cryptography

Distributed key generation (dkg)

A GJKR-style joint Pedersen-committed secret sharing:

• Every node deals a random degree-K−1 polynomial: a Pedersen commitment is broadcast, private shares go point-to-point, and each share is verified against the commitment.
• A second, G-only Feldman commitment round exposes the public material: the network key X = Σᵢ Aᵢ₀ and per-node verification shares Xⱼ = xⱼ·G.
• Each node's secret is the aggregate Shamir share xⱼ = Σᵢ fᵢ(j). The group secret x = Σᵢ fᵢ(0) never exists anywhere: it is defined only as the value the shares would interpolate to, and nothing in the production code interpolates it (the reconstruction test is test-only, and the share accessor is crate-private).

References: Gennaro, Jarecki, Krawczyk, Rabin — Secure Distributed Key Generation for Discrete-Log Based Cryptosystems, J. Cryptology 2007 (GJKR); Pedersen, CRYPTO '91; Feldman, FOCS '87. Deviations: honest-path only — the complaint/qualification phase is omitted (a bad share is a clean local error instead), broadcasts are plain trusted delivery, and the Pedersen H generator is derived by hash-to-curve rather than trusted setup.

Threshold signing (sign)

GG18 (Gennaro–Goldfeder, Fast Multiparty Threshold ECDSA with Fast Trustless Setup, ACM CCS 2018), instantiated with Paillier (EUROCRYPT '99) for the MtA (multiplicative-to-additive) conversions:

1. A one-time aux round after the DKG gives every node the directory of Paillier public keys.
2. Per session, each quorum member re-weights its Shamir share into an additive share wᵢ = λᵢ^S·xᵢ (Lagrange at 0 over the quorum), samples a nonce share kᵢ and mask γᵢ, and commits to Γᵢ = γᵢ·G.
3. Pairwise MtA turns the products k·γ and k·x into additive sharings (α + β ≡ a·b mod q) without revealing any input.
4. δ = kγ is revealed and inverted in the clear (safe: γ blinds k); decommitments yield R = δ⁻¹·Γ = k⁻¹·G and r = R.x mod q.
5. Each member broadcasts sᵢ = m·kᵢ + r·σᵢ; the sum is the ECDSA s. After low-s normalization the result is verified against X with stock k256::ecdsa before release — a corrupted share yields a clean abort, never a bad signature (tamper tests cover this).

Fewer than K participants cannot sign: an under-threshold subset's λ-weighted shares do not sum to x (Shamir), so its output fails verification — demonstrated by tests at both the share-arithmetic and the protocol level.

Deviations from GG18: honest-path only — the MtA range/ZK proofs, the proofs of correct key generation, and identifiable abort are omitted; the MtA range condition a·b + β′ < N holds statistically because |N| = 2048 ≫ |q²| = 512. Commitments are plain SHA-256 hash commitments.

Secret hygiene

Secret scalars, polynomials, shares, and Paillier trapdoors are zeroized on drop (zeroize); secret-bearing types are not Clone; every wire message and output type carrying secrets has a redacting Debug. Signing sessions borrow the long-lived KeyShare and wipe all per-session state on drop, so nothing leaks between claims.

Security assumptions and simplifications

The implementation assumes, without enforcement:

• nodes follow the protocol (honest-but-noisy, not Byzantine);
• local message delivery is reliable, and send_to_all delivers the same claim and the same broadcasts to every node identically;
• node identities are fixed and known by the simulation (Incoming::from is trusted);
• messages are not forged, altered, replayed, or equivocated;
• participants provide valid shares and protocol messages;
• the in-process coordinator (Network::submit) does not maliciously manipulate sessions.

Additional simplifications: the default Paillier keys are public fixtures (demo speed — use --fresh-paillier for real ones); endorsement randomness is injected (seedable) while protocol nonces come from the OS CSPRNG; there is no persistence — keys live for one process.

Deferred Byzantine behaviour (future work)

Explicitly out of scope for this version, in rough dependency order:

• authenticated transport and participant identity (real PKI);
• Byzantine reliable broadcast (e.g. Dolev-Strong) and equivocation detection;
• validation of maliciously malformed protocol messages;
• detection of invalid shares and partial signatures beyond the honest-path checks (GJKR complaints/exclusion, GG18 range and ZK proofs, identifiable abort);
• participant replacement and resharing;
• timeouts and liveness under partial failure;
• replay protection across distributed deployments (e.g. a session id mixed into the signed message);
• denial-of-service protection against clients and participants;
• persistent, encrypted key-share storage;
• secure deletion guarantees for all transient secrets (current zeroization covers stored fields, not every big-integer temporary);
• production-grade side-channel protections (constant-time arithmetic throughout).

Known limitations

• Simulation only: one process, lockstep rounds, no real transport.
• The quorum is the first K endorsers; there is no fairness or rotation among endorsing nodes.
• i64 claim arithmetic: -9223372036854775808 (−2⁶³) is not expressible, since literals are lexed before unary minus applies.
• Fresh Paillier generation (--fresh-paillier) takes seconds to minutes per node (safe-prime search).