Skip to content

FROST: precompute group commitment / binding factors once per aggregation instead of per share #209

Description

@JesseAbram

Problem

compute_group_commitment() (crates/crypto/src/decaf377/sign.rs:193) is
recomputed from scratch on every call:

  • clones and re-sorts the full commitment list,
  • computes a binding factor for each of the n participants, where each
    compute_binding_factor() call re-serializes and hashes the entire
    n-entry commitment list (sign.rs:171-190),

so a single call is O(n²) serialization + hashing.

During signature aggregation the coordinator calls it once per share and then
once more to finish:

  • verify_share()compute_group_commitment per share
    (crates/crypto/src/decaf377/sign.rs:437), invoked per incoming share from
    bin/orbis-node/src/sign/v0/coordinator/verification.rs:101 and
    bin/orbis-node/src/sign/v0/coordinator/rounds/signing.rs:779
  • recover() → recomputes it again (sign.rs:495, called from
    rounds/signing.rs:1035)

Verifying n shares + recovering therefore does O(n³) total hash work for
values that are identical across every call in the session: (msg, all_commitments) fully determine (R, binding_factors).

For reference, RFC 9591 computes the binding-factor list once per signing
session and reuses it for all per-share operations.

Severity

Correctness is unaffected — this is pure wasted work. For today's small rings
(n ≤ 10) the absolute cost is negligible; it becomes measurable for larger
committees or high signing throughput (n = 100 → tens of MB hashed per
signing session). Filing as cleanup/efficiency, not a bug.

Proposed fix

Add a prepared-aggregation context to the ThresholdSigner trait
(crates/crypto/src/trait.rs):

/// Per-session precomputed aggregation state (FROST: R + binding factors; BLS: ()).
type AggregationContext: Send + Sync;

fn prepare_aggregation(
    &self,
    msg: &[u8],
    all_commitments: &[(u32, Self::NonceCommitment)],
) -> Result<Self::AggregationContext>;
  • verify_share() and recover() take &Self::AggregationContext instead of
    recomputing from all_commitments.
  • decaf377/FROST: context = (r_point, binding_factors, canonical participant ids); verify_share drops to O(1) hash work per share.
  • bls12_381: AggregationContext = () — BLS is non-interactive
    (NonceCommitment = ()), nothing changes.
  • Coordinator: build the context once in the aggregation path
    (rounds/signing.rs) before the share-verification loop and reuse it through
    recover.

While in there, fix the intra-call duplication too: serialize the commitment
list once and reuse the bytes across all n compute_binding_factor calls,
instead of re-serializing per participant.

sign()'s single call (sign.rs:371) can stay as-is or use
prepare_aggregation internally — one call per signer is already optimal.

Notes

  • This changes the public ThresholdSigner trait; all impls and the sign
    coordinator update together. If external implementers matter, an additive
    verify_share_with_context + default-method fallback avoids the break.
  • Standalone verification of a single share (no session context) can construct
    the context ad hoc — same cost as today.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions