PaperlayerView exact revision on arXiv

Source-linked AI summary

Coconut: Threshold Issuance Selective Disclosure Credentials with Applications to Distributed Ledgers

Alberto Sonnino, Mustafa Al-Bassam, Shehar Bano, Sarah Meiklejohn, George Danezis

arXiv:1802.07344v4cs.CR

TL;DR

Selective disclosure credentials have not combined distributed trust with the efficiency and privacy properties needed for blockchain-based applications. Coconut provides threshold issuance for public and private attributes, re-randomizable unlinkable revelations, and smart-contract libraries, with verification taking about 10ms. Its security and applications remain bounded by threshold assumptions and implementation constraints.

  • Problem

    Existing selective credential schemes lack the full combination of efficiency, distributed trust, re-randomization, blind issuance, and selective disclosure needed for distributed ledgers.

  • Method

    Coconut combines threshold credential issuance, public and private attributes, re-randomization, selective disclosure, and smart-contract libraries for Chainspace and Ethereum.

  • Results

    Verification takes about 10ms, while Coconut provides short credentials and constant-size showing and verification independent of the number of authorities.

  • Takeaways & Limitations

    Coconut supports anonymous payments, privacy-preserving petitions, and censorship-resistant proxy distribution through distributed credential authorities.

  • Takeaways & Limitations

    Coconut is vulnerable when more than the threshold number of authorities are malicious, allowing attacks against its applications.

Abstract

from arXiv · show

Coconut is a novel selective disclosure credential scheme supporting distributed threshold issuance, public and private attributes, re-randomization, and multiple unlinkable selective attribute revelations. Coconut integrates with blockchains to ensure confidentiality, authenticity and availability even when a subset of credential issuing authorities are malicious or offline. We implement and evaluate a generic Coconut smart contract library for Chainspace and Ethereum; and present three applications related to anonymous payments, electronic petitions, and distribution of proxies for censorship resistance. Coconut uses short and computationally efficient credentials, and our evaluation shows that most Coconut cryptographic primitives take just a few milliseconds on average, with verification taking the longest time (10 milliseconds).

I. INTRODUCTION

Existing selective disclosure credentials lack the combination of distributed trust, efficiency, re-randomization, blind issuance, and selective disclosure needed for distributed ledgers. Coconut addresses this gap with threshold-issued credentials, blockchain libraries, and applications spanning payments, petitions, and censorship resistance.

  • Existing schemes may let a single issuer forge credentials, while others lack efficiency, re-randomization, blind issuance, or selective disclosure capabilities.
  • Coconut lets mutually distrusting authorities jointly issue credentials containing public or private attributes, while supporting re-randomization and unlinkable selective revelations.Users aggregate partial claims into one credential, and small subsets of corrupt authorities cannot forge credentials.
  • Coconut’s smart-contract libraries support credential issuance and disclosure in blockchain settings, with applications to anonymous payments, electronic petitions, and censorship-resistant proxy distribution.The implementations target Chainspace and Ethereum; the first two applications are implemented and evaluated on Chainspace.
  • O(t) communication is sufficient for request and issuance, where t authorities provide the threshold needed to generate a consolidated credential.A consolidated credential cannot be generated from fewer than t partial credentials.
  • Coconut guarantees liveness when a threshold number of authorities remains honest under weak synchrony assumptions for key distribution.
  • After aggregation and re-randomization, showing and verification require O(1) cryptographic computation and communication regardless of the number of authorities.Each partial and consolidated credential contains exactly two group elements, independent of authority and attribute counts.

III. THE COCONUT CONSTRUCTION

The Coconut construction builds a threshold credential scheme from prior pairing-based signatures and extends it to distributed issuance, zero-knowledge proofs, and multiple attributes. Its interface separates setup, key aggregation, issuance, credential aggregation, proving, and verification.

  • Construction steps: The construction combines ideas from Pointcheval–Sanders and Boneh et al. to overcome the limitations of single-attribute credentials and achieve Coconut’s design goals.
  • Construction steps: Coconut extends the scheme to credentials embedding q distinct attributes simultaneously.
  • Proofs and assumptions: Non-interactive zero-knowledge proofs assert knowledge of secret values and relations over them while leaving other values public.
  • Proofs and assumptions: Coconut assumes an honest majority, n/2 < t, and users aggregate t-out-of-n authority replies without requiring authorities to communicate with one another.The protocol therefore implicitly assumes an asynchronous setting, while current implementations rely on distributed key generation.
  • Protocol interface: IssueCred embeds a private attribute m satisfying φ, AggCred combines t partial credentials, ProveCred generates a proof for φ′, and VerifyCred returns true or false.
  • Security properties: The security properties are unforgeability, blindness, and unlinkability or zero-knowledge for credentials issued and shown under the threshold scheme.

C. Foundations of Coconut

Coconut’s foundations start from a pairing-based single-attribute credential scheme and add mechanisms for threshold issuance and private attributes. The resulting operations use bilinear-group parameters, authority keys, aggregation, randomized credentials, and verification equations.

  • Base credential scheme: The base scheme sets bilinear-group parameters, generates authority keys, signs an attribute with randomized group elements, and verifies a pairing equation.The signature is σ = (h, s) = (h, h^(x+y·m)), and verification checks h ≠ 1 and e(h, αβ^m) = e(s, g2).
  • Base credential scheme: The signature can be randomized by exponentiating both components with a fresh random value, supporting unlinkable presentations.
  • Private attributes: Private-attribute issuance uses a commitment and a zero-knowledge proof before the authority returns a blinded credential.
  • Private attributes: The user unblinds the returned signature into σ = (h, e_s(h)^(−t)), which serves as the credential.
  • Starting point: The Pointcheval–Sanders scheme provides blindness, unlinkability, efficiency, and short credentials but does not support threshold issuance.Its private issuer-generated randomness prevents efficient distribution to multiple authorities.

D. The Coconut Threshold Credential Scheme

Coconut introduces threshold credentials that let users collect partial credentials from authorities, aggregate them, and later prove selected attributes with randomized credentials. Its security and efficiency rely on distributed issuance, zero-knowledge proofs, and constant-size credentials.

  • Threshold issuance: A t-out-of-n scheme lets users aggregate any t partial credentials, where n/2 < t ≤ n.Partial credentials are issued on public or private attributes and reconstructed without exposing the underlying secret polynomial values.
  • Blind issuance: Users blind private attributes with commitments, El-Gamal encryption, and a zero-knowledge proof that the attribute satisfies predicate φ.Authorities verify the proof and use El-Gamal homomorphism to create encrypted partial credentials.
  • Showing and verification: Users randomize consolidated credentials before proving possession, while VerifyCred checks the proof, pairing equation, and application predicate.The verifier uses an aggregated verification key collected once before verification.
  • Security: Under LRSW, XDH, and random-oracle assumptions, Coconut provides unforgeability below the threshold, blindness, and unlinkability.Unforgeability requires fewer than t colluding authorities; blindness and unlinkability hold even when authorities and the verifier collude.

E. Multi-Attribute Credentials

Coconut extends its threshold credential scheme to multiple attributes without increasing credential size, while supporting mixed public and private attributes and selective disclosure.

  • Construction: Multiple attributes are embedded into one credential by extending the authorities’ key pairs with one component per attribute.The construction follows the Waters and Pointcheval–Sanders schemes.
  • Size and security: The credential remains two group elements regardless of the number of attributes or authorities.The multi-attribute security proof reduces to the single-attribute scheme.
  • Selective disclosure: Public and private attributes can coexist, allowing some attributes to remain hidden while others are revealed.BlindSign verifies proofs only for private attributes.
  • Privacy boundary: A private random attribute is required when credentials contain only non-random attributes, preventing brute-force guessing of an attribute value.The random attribute can also serve as the credential’s authorization key.

IV. IMPLEMENTATION

The authors implement Coconut as an open-source Python library and provide smart-contract libraries for Chainspace and Ethereum, including evaluated functionality and integrations with applications.

  • Libraries: A Python library implements Coconut’s cryptographic scheme and is published as an open-source project.The implementation follows the paper’s threshold credential construction.
  • Blockchain integration: A Chainspace smart-contract library exposes Coconut primitives to application-specific smart contracts.The paper also implements and evaluates some smart-contract functionality in Ethereum.

A. The Coconut Smart Contract Library

The Coconut smart-contract library coordinates credential creation, requests, issuance, and verification through contract calls and authority interactions. Its architecture supports callback contracts but requires a mitigation for continuous authority monitoring.

  • Contract workflow: The library provides Create, Request, Issue, and Verify functions for threshold credential workflows.Create initializes contract information, authority verification keys, the authority count, and the threshold.
  • Attribute privacy: An age attribute could be guessed by testing the verification algorithm across candidate values when it is not randomized.The paper motivates embedding a private random attribute to prevent this attack.
  • Credential requests: Request supplies public attributes in clear text and private attributes in encrypted form through a specified callback contract.Authorities monitor the blockchain for executed requests before issuing partial credentials.
  • Limitation: Continuous blockchain monitoring by authorities is inefficient, so the architecture embeds authorities into blockchain-running nodes as a workaround.This limitation and mitigation are identified in the implementation discussion.

B. Ethereum Smart Contract Library

The Ethereum library brings Coconut credential verification into smart contracts, adapting elliptic-curve support to Ethereum’s available primitives and gas limits. Its broader blockchain integrations embed authorities in semi-permissioned systems, while applications use the library for privacy-preserving transactions and petitions.

  • Ethereum implementation: Ethereum’s pre-compiled contract supports pairing checks and elliptic-curve operations on alt bn128, enabling Coconut verification in a smart contract.The released Solidity library supplements Ethereum’s native G1 support with G2 operations required by Coconut.
  • Ethereum implementation: One revealed attribute requires one G2 addition and one scalar multiplication, whereas unrevealed attributes require three G2 multiplications exceeding Ethereum’s 8M gas limit.The Ethereum design therefore favors applications that reveal one attribute.
  • Deeper blockchain integration: Embedding authorities in semi-permissioned blockchain infrastructure enables credential issuance as a side effect of normal operations without extra authorities.Embedding Coconut into permissionless proof-of-work or proof-of-stake systems remains an open problem because their node sets are highly dynamic.
  • Deeper blockchain integration: Coconut authorities can coincide with authorities in Fabric, Chainspace shards, and Omniledger shards, using known membership and public keys for distributed issuance.Fabric contracts can trigger setup, key distribution, and partial credential issuance; sharded systems can signal credential requests to shard authorities.
  • Applications: Coconut applications include a distributed Chainspace coin tumbler, a privacy-preserving petition system, and censorship-resistant proxy distribution.The applications generally assume external authorities, although blockchain embedding is also supported.
  • Applications: The coin tumbler uses blind issuance, re-randomized credentials, and a spent list to support unlinkable payments while preventing authority theft and double spending.The tumbler keeps the transfer value public and uses a threshold of authorities rather than a central operator.

B. Privacy-preserving petition

The privacy-preserving petition application lets citizens use Coconut credentials to sign petitions anonymously and without linkability across petitions. Distributed blind issuance protects citizen keys from authorities while threshold resilience removes reliance on one central issuer.

  • Motivation: The application targets countries where all citizens may participate while preserving anonymity and extending prior petition work with threshold credential issuance.The authorities represent the country, while a petition initiator creates each petition contract.
  • System design: Citizens obtain a blind, long-term signature on a private key from multiple authorities after proving their identity.The credential needs to be obtained only once and serves as the citizen’s long-term credential.
  • System design: Petition contracts bind each petition to a unique identifier and authorities’ verification key, then verify credential proofs and prevent repeated signatures.A spent list records the petition-specific value ζ so a citizen cannot sign the same petition multiple times.
  • Privacy and security: Citizens remain anonymous and unlinkable across petitions because authorities do not learn their secret keys and credentials can be reused.Coconut’s blindness prevents authorities from misusing a citizen’s key to sign petitions on the citizen’s behalf.

A. Cryptographic Primitives

The evaluation benchmarks Coconut’s cryptographic primitives, distributed latency, and smart-contract implementations in Chainspace and Ethereum. Verification is the main cryptographic cost, while Chainspace applications run in a few milliseconds and Ethereum performance is constrained by high-level G2 arithmetic.

  • Cryptographic primitives: Verification takes about 10ms, while signing is much faster because verification invokes a pairing operation.The benchmark reports mean and standard deviation over 10,000 runs; signing a private attribute is about three times faster.
  • Client-perceived latency: Authorities farther from the client produce higher response times, with European authorities responding first and Sydney and Tokyo latest.The client was in London and authorities were geographically distributed across the world.
  • Client-perceived latency: Latency grows linearly with the threshold parameter, except for an approximately 150ms jump when t increases from 2 to 3.The client waited for t-out-of-10 partial signatures from geographically distributed authorities over 100 runs.
  • Chainspace implementation: Chainspace’s most time-consuming library procedures are Create and Verify checkers because they call VerifyCred, which takes about 10ms.The evaluation assumes two authorities; Issue transaction size grows by about 132 bytes per additional authority, while other transactions are independent of authority count.
  • Chainspace applications: Coin tumbler and e-petition checkers call BlindVerify with pairing checks, yet the evaluated transactions remain practical and run in a few milliseconds.Application transaction costs are independent of authority count because issuance is handled off-chain or by the Coconut library.
  • Ethereum implementation: Ethereum Create and Verify execute more slowly than Chainspace versions because arithmetic runs in Solidity on the EVM rather than through Python bindings to C libraries.The Ethereum evaluation measured execution times and gas costs for the smart-contract library.
  • Ethereum implementation: Verify has a significantly higher gas cost than Create because native elliptic-curve multiplication costs around 1,700,000 gas.The pairing operation through Ethereum’s precompiled contract costs 260,000 gas.
  • Ethereum implementation: The Ethereum implementation’s bottleneck is high-level arithmetic in G2, although swapping G1 and G2 could use Ethereum’s G1 precompile under the stronger SXDH assumption.This alternative would change the cryptographic assumption used by the implementation.

VII. COMPARISON WITH RELATED WORKS

Coconut extends prior credential constructions with short, aggregable, randomizable credentials that support threshold and blind issuance. It addresses limitations in existing schemes around distributed trust, credential size, unlinkable use, and aggregation.

  • Anonymous credentials: CL Signatures and Idemix provide blind issuance and unlinkability, but their credentials grow linearly with signed attributes and are not aggregable.Their computational overhead is also described as significant.
  • Anonymous credentials: Prior ledger-based credentials support private attributes, blind issuance, and unlinkable multi-show disclosure, but showing credentials requires an expensive double discrete-logarithm proof of about 50KB.Their security also relies on the ledger.
  • Short and threshold issuance anonymous credentials: Coconut supports short, aggregable, randomizable credentials with threshold and blind issuance for multiple authorities.Independent parties can aggregate any threshold number of partial signatures without sequential signer coordination.
  • Limitations: Adding or removing authorities requires rerunning key generation, while frequent key rotation makes credentials from different key sets distinguishable and reduces privacy.The limitation is inherited from Shamir’s secret sharing and may be mitigated using proactive secret sharing techniques.
  • Limitations: Coconut’s threshold security fails when more than the threshold number of authorities are malicious.Such collusion can affect the tumbler, petition, and proxy-distribution applications in distinct ways.
  • Contribution: Coconut is presented as a general-purpose selective disclosure scheme for distributed ledgers, with public and private attributes, re-randomization, and multiple unlinkable revelations.The paper evaluates implementations for Chainspace and Ethereum and presents applications to anonymous payments, petitions, and censorship resistance.

APPENDIX A SKETCH OF SECURITY PROOFS

The appendix sketches security arguments for Coconut’s threshold credential construction, focusing on unforgeability, blindness, and unlinkability. These properties follow from zero-knowledge proofs, threshold interpolation, hiding commitments or encryption, and credential re-randomization under stated assumptions.

  • Unforgeability: Unforgeability against invalid proofs follows from zero-knowledge soundness, while fewer than t partial credentials leave the degree-(t −1) interpolation polynomial undetermined.An adversary with fewer than t shares must therefore forge the remaining credentials directly.
  • Blindness: Blindness follows from the underlying Pointcheval–Sanders signature and from hiding commitments or IND-CPA-secure encryption of attributes.Coconut uses Pedersen commitments and El-Gamal encryption; the overall blindness argument is implied by XDH.
  • Unlinkability / Zero-knowledge: Re-randomization at the start of ProveCred ensures unlinkability across proof executions, while zero knowledge reveals no more than validity of the statement.The statement may include public attributes.
  • Key generation: Threshold keys are generated from degree-(t −1) polynomials, with each authority receiving evaluations and publishing corresponding verification keys.The setup selects bilinear groups and generators before generating the polynomial shares.

APPENDIX C ETHEREUM TUMBLER

The Ethereum tumbler implementation modifies the application to reduce gas costs. It replaces a variable denomination attribute with fixed-denomination Coconut instances and requests issuance on a private merchant address and sequence number.

  • Implementation: The Ethereum version extends the tumbler application with modifications specifically intended to reduce gas costs.The implementation is an extension of the example tumbler application.
  • Gas-cost reductions: Fixed-denomination Coconut instances replace the variable coin-count attribute to reduce elliptic-curve multiplications during credential verification.Separate instances are set up for different denominations.
  • Tumbler flow: Users deposit Ether into the contract and request issuance on the private attribute addr||s.Here addr is the merchant destination address and s is a randomly generated sequence number.
Loading 1802.07344v4…