Skip to content

BLSAccumulator.md

Latest commit

 

History

History
110 lines (81 loc) · 7.59 KB

BLSAccumulator.md

File metadata and controls

110 lines (81 loc) · 7.59 KB

BLS Accumulator Pattern (Dynamic Membership Capsules)

This design note summarizes how to use the bilinear (BLS12-381) accumulator implemented in perturbing/plutus-accumulator, which follows the dynamic universal accumulator from Bilinear Accumulators for Decentralized Systems (ACM CCS 2022, doi:10.1145/3548606.3560676). It explains the cryptographic model and sketches a Plutus-friendly interface for building stateful contracts that certify batched membership or non-membership statements with constant-size proofs.

1. Cryptographic Overview

1.1 Setup

  • Work over pairing-friendly groups (G1, G2, GT) on BLS12-381 with generators g1 ∈ G1, g2 ∈ G2, and bilinear map e : G1 × G2 → GT.
  • A trusted setup (or MPC) samples a secret τ and publishes structured reference string (SRS) elements [g1^{τ^0}, g1^{τ^1}, …, g1^{τ^q}] plus g2.
  • Hash each element x into the scalar field via collision-resistant hash H(x); sometimes hashed-to-curve if committed directly.

1.2 Accumulating a Set

  • Interpret the set S = {x₁,…,xₙ} as a polynomial f_S(z) = ∏_{x∈S} (z + H(x)).
  • The accumulator value is Acc(S) = g2^{f_S(τ)} – a single compressed G2 element (96 bytes).
  • Because the exponent encodes the entire set polynomial evaluated at τ, removing or adding elements just multiplies/divides f_S(z) by the corresponding factors. No per-element storage is needed on-chain.

1.3 Membership Proofs

  • For y ∈ S, define witness polynomial f_{S\{y}}(z) = f_S(z) / (z + H(y)).
  • Witness is W_y = g2^{f_{S\{y}}(τ)} (constant-size G2).
  • Verification uses the bilinear check: e(g1^{τ + H(y)}, Acc(S)) == e(g1^{τ}, W_y). In practice, the verifier reconstructs the needed G1 powers from the SRS supplied off-chain (see repo’s redeemer.setup) and checks the pairing equations with Plutus BLS built-ins.

1.4 Non-Membership Proofs

  • For y ∉ S, compute polynomials a(z), b(z) such that a(z)·f_S(z) + b(z)·(z + H(y)) = 1 (Bézout relation).
  • Proof is (W_a, W_b) = (g1^{a(τ)}, g2^{b(τ)}).
  • Verifier checks e(W_a, Acc(S)) · e(g1, W_b) == e(g1, g2) and ensures W_a ≠ identity.

1.5 Dynamic Updates & Batching

  • Remove subset R ⊆ S: Provide membership proof for R, divide Acc(S) by the committed polynomial for R, producing new accumulator Acc(S\R). The removal operation reuses the membership witness as the “difference accumulator.”
  • Add subset A: Provide non-membership proof for A relative to current set plus membership proof for the resulting set (or equivalently compute updated polynomial and prove the transition). Batching keeps proof sizes constant even for large subsets.

In the Plutus implementation, the heavy scalar/polynomial arithmetic happens off-chain; on-chain scripts only check pairing equations using BLS12-381 built-ins and the provided setup values.

2. Cardano Design Pattern

2.1 On-Chain Artifacts

  1. Accumulator State UTxO

    • Datum fields:
      • accumulator : BuiltinByteString (compressed G2 from the repo’s Datum).
      • epoch / version : Integer (optional monotonic counter).
      • policy_tags : ByteString (optional to bind to particular applications).
    • Locked by an AccumulatorValidator that enforces valid membership/non-membership proofs before allowing updates.

  2. SRS Reference Input

    • Holds the list of compressed G1 powers [g1^{τ^i}] required for pairing checks.
    • Shared across scripts; hashed in redeemers to prevent tampering (as shown in the repo’s Aiken example where redeemer.setup supplies the decompressed G1 list).

  3. Off-Chain Witness Service

    • Maintains the actual set, computes membership/non-membership proofs, and crafts redeemers for contract calls.

2.2 Redeemer Interface

data AccumulatorAction
  = CheckMembership { subset : [Element], proof : G2 }
  | CheckNonMembership { subset : [Element], proof : (G1, G2) }
  | AddElements { subset : [Element], non_membership_proof : (G1, G2), membership_proof_new : G2, new_accumulator : G2 }
  | RemoveElements { subset : [Element], membership_proof : G2, new_accumulator : G2 }
  • subset contains hashed elements (H(x) scalars).
  • proof fields match the serialized witnesses expected by check_membership / check_nonmembership.
  • new_accumulator is the claimed post-state (compressed G2) when mutating.

2.3 Validator Logic (Sketch)

  1. Reconstruct SRS points: setupPoints = map g1_decompress redeemer.setup.
  2. Decompress stored accumulator: acc = g2_decompress datum.accumulator.
  3. Depending on action:
    • CheckMembership: call check_membership(setupPoints, acc, subset, proof) and ensure no state change (used for read-only attestations).
    • RemoveElements: verify membership for subset, recompute expected new accumulator (multiplying acc by inverse polynomial supplied via witness), and enforce continuing output matches new_accumulator.
    • AddElements: verify non-membership for subset, then membership for the claimed new accumulator to guard against forged additions.
  4. Enforce monotonic epoch if provided, and ensure transaction outputs pay the updated accumulator back to the same validator.

The helper functions check_membership and check_nonmembership already exist in both Haskell (plutus-accumulator package) and Aiken (aiken-bilinear-accumulator/accumulator.ak).

3. Usage Scenarios

  1. Access-Control Lists / Identity Registries

    • Accumulator stores hashes of KYC’ed addresses.
    • Users prove membership to unlock rights; regulators can remove entries with batched witnesses.

  2. Rollup Withdrawal Queues

    • Commitment aggregates pending withdrawal IDs; exits require non-membership proof to ensure uniqueness plus membership proof to mark completion.

  3. Fraud Proof Batching

    • Sequencers maintain accumulator of “pending challenges” and update state as disputes are resolved without touching large Merkle trees.

  4. Oracle Feeds

    • Data providers add signed price updates as elements; consumers trust membership proofs instead of downloading the full feed.

In each case, the Cardano transaction only carries:

  • The current accumulator G2 value.
  • Constant-size membership/non-membership proofs.
  • A list of elements being updated (size grows linearly with batch but proofs remain constant).

4. Implementation Notes

  • Serialization: Store G1/G2 elements as compressed bytes (48/96 bytes). Use Plutus BLS built-ins (bls12_381_G1_uncompress, etc.) for verification, mirroring the repo.
  • Hash-to-Scalar: Stick to the same domain separator and hash function (blake2b_256 → scalar) as the reference implementation so witnesses remain compatible.
  • SRS Distribution: Treat the SRS as immutable reference inputs. If an upgrade is required, deploy a new validator instance bound to the new SRS hash.
  • Off-Chain Costs: Computing witnesses requires polynomial arithmetic and pairings; expect heavier off-chain CPU usage but minimal on-chain memory footprint.
  • Security: Anyone who can create valid membership/non-membership proofs can mutate the accumulator, so guard the validator with signature checks or governance logic in addition to pairing equations.

This pattern lets Cardano contracts store massive sets compactly while supporting constant-size proofs, borrowing the high-performance accumulator described in the CCS paper and implemented in plutus-accumulator. Designers can plug the provided check_membership / check_nonmembership functions directly into Plutus or Aiken validators and follow the interface above to integrate BLS accumulators safely.