Pisces: Private and Compliable Cryptocurrency Exchange

Pisces: Private and Compliable Cryptocurrency Exchange

Speakers: Ya-Nan Li

Conference: NDSS Symposium

YouTube: (No public video available)

Overview

"Pisces: Private and Compliable Cryptocurrency Exchange" introduces a groundbreaking system designed to address a critical privacy vulnerability inherent in modern centralized cryptocurrency exchanges. Given by Ya-Nan Li at the NDSS Symposium, this talk highlights how the combination of transparent public blockchains and Know Your Customer (KYC) requirements on centralized platforms like Coinbase leads to a significant privacy erosion. When users withdraw cryptocurrencies to their external on-chain wallets, exchanges, already possessing sensitive real-world identity and bank information, can link this data to all subsequent on-chain transactions. This effectively negates the pseudonymity often associated with blockchain technology, allowing platforms to build extensive profiles of users' external financial activities—for instance, deducing a car purchase from a Bitcoin withdrawal followed by a transfer to a car manufacturer's address.

The core motivation behind Pisces is to restore user anonymity, ensuring that external transaction records remain unlinkable to an individual's real identity, much like how traditional stock exchanges do not monitor external user spending. However, this goal must be achieved without compromising essential regulatory compliance and financial integrity. The system aims to protect user privacy from the exchange itself, which acts as a powerful adversary capable of extensive data aggregation.

This work is significant because it provides the first formal security model and a provably secure construction for a system that simultaneously delivers strong user anonymity and robust compliance features. It tackles the complex challenge of balancing privacy with regulatory demands like Anti-Money Laundering (AML) and tax reporting, demonstrating that these seemingly conflicting objectives can be reconciled through advanced cryptographic techniques. Pisces represents a crucial step towards building more privacy-preserving and trustworthy financial infrastructures in the rapidly evolving world of digital assets.

Background

[▶ Watch: Introduction: Privacy vulnerability in crypto exchanges (0:00)]()

The problem Pisces addresses stems from the fundamental architecture of centralized cryptocurrency exchanges interacting with public blockchains. While blockchains offer pseudonymity through public addresses, the moment a user engages with a centralized exchange, their real-world identity is typically collected via KYC processes. This means the exchange knows the user's name, address, bank details, and potentially more. When a user then withdraws funds to an external blockchain address, a direct link is established between their real identity and that public address. From this point onward, any on-chain activity involving that address can be traced back to the individual by the exchange, providing an unprecedented level of surveillance over users' financial lives.

Prior attempts and existing solutions fall short in addressing this specific challenge. Fully anonymous on-chain payments like Zcash are limited to their native coins and do not support widely traded assets such as Bitcoin or Ethereum. Private layer-2 solutions often focus on k-anonymity against external observers or a hub, but not against the platform itself, which inherently knows the payee's address during a withdrawal. Furthermore, these solutions frequently assume fixed denominations, which is impractical for the varied withdrawal amounts seen in real-world exchanges. Decentralized Exchanges (DEXs) offer a different privacy model, typically concealing transaction details from other trading parties, but not from the underlying transparent blockchain itself, nor are they designed to handle the KYC/AML requirements of centralized platforms. Atomic swaps, while ensuring fairness, ultimately rely on the transparency of the underlying blockchains, thus reducing privacy. Only one private fiat-to-Bitcoin exchange was identified, but it imposed restrictive fixed withdrawal amounts.

The core issue is that anonymity within the exchange platform, particularly against the platform as an adversary, has been largely unexplored in this context. Exchange transactions are distinct from pre-arranged payment hub interactions; they are independent requests, often involving two highly correlated parts (user-to-platform and platform-to-user) with amounts tied to exchange rates, making them easily distinguishable. Moreover, a naive approach focusing solely on anonymizing withdrawals is insufficient. The continuous connection to external blockchains through deposits and withdrawals inevitably leaks information, such as "3 BTCs deposited, 2.9 BTCs withdrawn 2 minutes later." If the anonymity set for a withdrawal is small—for example, only users with sufficient amounts of a specific, perhaps unpopular, coin are considered—deanonymization becomes trivial. This necessitates a much stronger, more comprehensive anonymity model that minimizes information leakage beyond what is absolutely necessary for the system's operation and compliance.

Key Findings

[▶ Watch: Pisces: Formal definitions, contributions, and technical overview (4:00)]()

The research behind Pisces delivers several pivotal contributions that redefine how privacy and compliance can coexist in centralized cryptocurrency exchanges:

1. Formal Security Model: The paper establishes the first formal definitions for a private and compliable cryptocurrency exchange. This includes a basic anonymity notion for withdrawals and, more critically, a stronger full anonymity model (termed Interaction Indistinguishability) that ensures the platform leaks virtually no information beyond what is strictly unavoidable. It also rigorously defines essential soundness properties such as overdraft prevention and client compliance, along with platform compliance (e.g., solvency checks).
2. Provably Secure Construction (Pisces): Pisces is presented as the first provably secure system designed to meet these stringent definitions. It achieves full anonymity, preventing the platform from linking users to their internal transactions or external on-chain activities. Simultaneously, it ensures that users cannot double-spend or submit fraudulent compliance information, while the platform maintains its solvency.
3. Efficient Cryptographic Design: The system leverages highly efficient Non-Interactive Zero-Knowledge (NIZK) proofs, specifically tailored to provide constant communication and computation overhead. This means the performance of Pisces remains efficient regardless of the number of asset types or users within the system, a crucial factor for scalability in real-world exchanges. The design incorporates additively homomorphic commitments, blind signatures, and Zero-Knowledge Argument of Knowledge (ZKAoK).
4. Practical Implementation and Evaluation: A prototype implementation of Pisces was developed and rigorously evaluated. The performance results demonstrate minimal overhead compared to traditional, non-private exchanges, even when accounting for secure communication protocols like TLS. The system's efficiency is also favorable when compared to other relevant privacy-preserving systems, highlighting its practical viability.

These findings collectively demonstrate that strong privacy for users in centralized cryptocurrency exchanges is not only achievable but can be integrated efficiently alongside critical regulatory compliance requirements, without sacrificing security or performance.

Technical Deep Dive

[▶ Watch: Pisces system workflow: User, Platform, Authority (4:50)]()

Pisces is structured around three primary entities: the User (U), the Platform (P), and an external Authority (A). The system's workflow involves a sequence of interactive protocols:

1. Registration (Join): The user undergoes KYC by providing real-world identity information to the platform.
2. Transactions: Users interact with the platform for common exchange activities: deposits, exchanges (e.g., swapping Bitcoin for Ethereum), and withdrawals.
3. Compliance: The user generates a compliance report, which is then certified by the platform and submitted to the authority. The platform also generates information to check its own solvency.

At its core, Pisces relies on several standard, yet powerful, cryptographic primitives:

• Commitments: Specifically, an additively homomorphic commitment scheme Icmt (Setup, Com) is used. This allows a user to commit to a message m with randomness r, hiding m from the platform, but later revealing it to prove knowledge without disclosing m itself. It must satisfy hiding and binding properties.
• Blind Signatures: A blind signature scheme Ibs (KeyGen, Com, BlindSign, BlindRcv, Vrfy) enables a user to obtain a signature on a message from the platform without the platform learning the content of the message. This is crucial for issuing anonymous credentials. It must be unforgeable and blind.
• Zero-Knowledge Argument of Knowledge (ZKAoK): This primitive allows a prover (the user) to convince a verifier (the platform) that they know a witness w for a statement x without revealing w. This is essential for proving ownership of funds, valid credentials, or compliance with rules without disclosing sensitive transaction details. It must be perfectly simulatable and possess an extractor.

The system's syntax defines two main types of records held privately by users:

• Rdreg (Registration Record): Contains a unique nonce (non), user identifier (uid), compliance info (cp), and a credential (cred). Each user holds one valid Rdreg.
• Rdast (Asset Record): Contains a nonce (non), user identifier (uid), asset name (name), amount (amt), asset-related compliance info (acp), and a credential (cred). Users can hold multiple Rdast records for different assets.

High-Level Algorithms:

The interactive protocols of Pisces are as follows:

• Setup(1λ) epp: Generates public parameters for the system.
• PKeyGen(epp) (pk, sk): Platform generates its key pair and initializes its state.
• Join, Issue: User commits to their uid, a random rid, and initial compliance info. They prove this commitment in zero-knowledge. If uid is new, P blindly signs the commitment, and U unblinds it to get their Rdreg credential.
• Deposit, Credit: U sends a deposit request with commitments to their Rdreg and a new Rdast (containing uid, asset i, amount ki, and buying price pri). U proves ownership of Rdreg and consistency. P blindly signs the new Rdast.
• Exchange, Update: U sends an exchange request (i for j) with commitments to Rdreg, Rdast for asset i, and new Rdreg, Rdast for remaining i, and Rdast for j. U proves ownership, sufficient funds, uid consistency, and fair exchange (e.g., pri ki = prj kj) using price credentials signed by P. P blindly signs the new records.
• Withdraw, Deduct: Similar to exchange, U proves ownership of Rdreg and Rdast, sufficient funds, and consistency for the withdrawal amount ki. P blindly signs the new Rdreg and Rdast.
• File, Sign: U sends a compliance filing request (uid, cp) with commitments to their Rdreg (and a new Rdreg with cp reset to zero) and a compliance document doc. U proves consistency. P blindly signs doc and the new Rdreg.
• Verify(epp, pk, doc) b: The authority verifies the signed compliance document.
• Check(epp, st) b: The platform performs self-checks for solvency.

Security Models:

Pisces' security model is robust, assuming a malicious platform as the adversary. It defines:

• Correctness: Honest users get correct balances and valid compliance signatures.
• Anonymity: The malicious platform cannot link external wallet addresses to specific users, except where identity leakage (e.g., fiat deposits) is unavoidable.
• Basic Withdraw Anonymity (Definition 1) is a warm-up, where U requests one-time anonymous credentials for a committed amount, then uses them to withdraw. However, this is limited; an example showed how a withdrawal of 51 BTC could be linked to Bob if only he had sufficient funds (100 BTC) among a small anonymity set.
• Full Anonymity is achieved through Interaction Indistinguishability (Definition 3). This ensures that the platform learns nothing beyond unavoidable public information (e.g., transaction type, KYC data, asset name/amount, on-chain addresses). This prevents leakage of information such as the identity of depositors/exchangers or the contents of exchanges, which were shown to shrink anonymity sets significantly.
• Overdraft Prevention (Definition 4): Malicious users cannot spend more assets than they own. This prevents fraudulent deposits, exchanges, or withdrawals, and ensures fair exchanges.
• Compliance:
• F-client-compliance (Definition 5): Users must adhere to regulatory rules, such as accurate tax reporting on accumulated profit. Users cannot deceive the authority.
• G-platform-compliance: The platform must satisfy internal rules like Liquidity Coverage Ratio (LCR), ensuring sufficient reserves. Pisces is compatible with LCR as the platform still knows total inflows/outflows.

Detailed Algorithms (from Figure 7):

Each protocol in Pisces involves specific steps by the user (U) and the platform (P), leveraging the cryptographic primitives:

• Join, Issue:
• U: Chooses uid, random rid, r. Commits to (uid, rid, cp1=0, cp2=0) as com. Proves in ZK that com contains these values. Sends (reqjoi, uid, com, π) to P.
• P: Verifies π. If valid and uid is not in its USet, P blindly signs com to get ôreg.
• U: Unblinds ôreg to get σreg, forming Rdreg = (uid, rid, cp1, cp2, σreg).
• Deposit, Credit:
• U: Chooses aid, r1, r2. Commits to (uid, rid, cp1, cp2) (from Rdreg) as com1 and (uid, aid, i, ki, pri) as com2. Proves ownership of σreg for com1, and that com2 contains consistent uid, aid, asset i, amount ki, and buying price pri. Sends (reqdep, com1, com2, π) to P.
• P: Verifies π. If valid, P blindly signs com2 to get ôast.
• U: Unblinds ôast to get σast, forming Rdast = (uid, aid, i, ki, pri, σast).
• Exchange, Update:
• U: Chooses new nonces (rid', aid', aidout) and randomness. Commits to the current Rdreg (com1), the asset to exchange (com2), the new Rdreg (com3), the remaining part of the exchanged-in asset (com4), and the new asset received (com5). Also commits to price credentials com6 (for asset i) and com7 (for asset j).
• U proves in ZK: valid platform signatures for com1, com2, com6, com7; rid, aid are in com1, com2; new nonces in com3, com4, com5; sufficient funds (vi = 0, vi-ki = v' = 0); consistent asset i and pri across com2, com4, com6; consistent asset j and prj across com5, com7; correct update of cp1, cp2 in com3 for tax reporting (cp1' = cp1 + ki*pri, cp2' = cp2 + ki*pri); fairness (prj*kj = pri*ki); and all commitments share the same uid. Sends (rid, aid, com_u, π) to P.
• P: Verifies π. If valid, P blindly signs com3, com4, com5.
• U: Unblinds signatures to get new Rdreg, Rdast for remaining funds, and Rdast for the received asset.
• Withdraw, Deduct: Similar structure to Exchange, but for a single asset. U proves ownership of Rdreg, Rdast, sufficient funds, and correct update of cp1, cp2 in the new Rdreg to reflect the withdrawal for tax purposes. P blindly signs the new Rdreg, Rdast.
• File, Sign:
• U: Commits to current Rdreg (com1), a new Rdreg with cp reset to (0,0) (com2), and the compliance document content (com3). Proves valid signature for com1, consistency of uid, and that com2 has the new rid' and (0,0), and com3 correctly reflects cp1, cp2 from com1. Sends (uid, rid, com_u, π) to P.
• P: Verifies π. If valid, P blindly signs com2 and com3.
• U: Unblinds signatures to get the updated Rdreg and the signed doc.
• Verify(epp, pk, doc) b: Authority checks the mt in doc matches the current mt' and verifies P's signature on (uid, cp1, cp2, mt).
• Check(epp, st) b: Platform monitors fund outflows and checks for LCR compliance.

Security Analysis:

Pisces' security is formally proven through several theorems:

• Theorem 1 (Interaction Indistinguishability): Guarantees full anonymity. The proof uses hybrid experiments, showing that if the underlying blind signature scheme is blind, ZKAoK is zero-knowledge, and commitments are hiding, then a real interaction is indistinguishable from a simulated one where the adversary's view is independent of the challenge bit.
• Theorem 2 (Overdraft Prevention): Ensures users cannot spend more than they own. This relies on the argument of knowledge property of ZKAoK, the binding property of commitments, and the unforgeability of blind signatures. Any attempt to overdraft would imply breaking one of these cryptographic assumptions (e.g., forging records, reusing identifiers, stealing assets, or getting records with wrong attributes).
• Theorem 3 (Compliance): Guarantees client compliance (e.g., accurate tax reporting). Similar to overdraft prevention, it relies on the same strong cryptographic properties. Any attempt to submit a false but verifiable compliance document would imply breaking the unforgeability of Ibs, the argument of knowledge of ZKAoK, or the binding property of commitments.

These rigorous proofs underscore the robustness of Pisces in simultaneously achieving strong privacy and essential compliance within a centralized exchange environment.

Demo / Proof of Concept

[▶ Watch: Cryptographic primitives and system syntax for Pisces (6:00)]()

The practical viability of Pisces was demonstrated through a prototype implementation and comprehensive performance evaluation. The system was instantiated using well-established cryptographic primitives:

• Blind Signatures: Pointcheval Sanders blind signatures were used.
• Commitments: Pedersen commitments were employed, leveraging their additively homomorphic property.
• Zero-Knowledge Proofs: The ZKAoKs were built using Σ-protocols for proving knowledge of discrete logarithms, equality of values, and range proofs, which are fundamental components for constructing efficient zero-knowledge systems.

The implementation itself was done in Java, utilizing the upb.crypto library for cryptographic operations and the mcl(bn256) bilinear group library. The mcl library, being a C/C++ implementation, was crucial for achieving high efficiency, especially for operations involving bilinear pairings.

The experimental environment for performance evaluation was a MacBook Air equipped with a 1.6 GHz Dual-Core Intel Core i5 processor and 16GB of memory. This setup, while not a high-end server, demonstrated the system's efficiency even on consumer-grade hardware.

Performance Results:

The evaluation focused on both computation cost (latency) and communication cost for each protocol:

Computation Cost (Table I):

• Join: User: 9 ms, Platform: 11 ms
• Deposit: User: 7 ms, Platform: 14 ms
• Exchange: User: 46 ms, Platform: 88 ms
• Withdraw: User: 37 ms, Platform: 62 ms

All core operations were completed in under 88 milliseconds, indicating very high efficiency for user and platform interactions.

Communication Cost:

• Join: User sends 2.6 KB, Platform sends 1.8 KB
• Deposit: User sends 3.3 KB, Platform sends 1.8 KB
• Exchange: User sends 12 KB, Platform sends 2.8 KB
• Withdraw: User sends 8.7 KB, Platform sends 2.3 KB

The maximum communication overhead was 12 KB (user-side for exchange), demonstrating low data transfer requirements, which is crucial for responsive user experiences.

Comparison with Plain Exchange (Figure 8):

A critical part of the evaluation was comparing Pisces' performance against estimated costs for plain (non-anonymous) exchange operations, including network round-trip times (RTTs) and on-chain confirmation delays.

• Secure Join: Total time was approximately 196.278 ms, compared to an estimated 150 ms for a plain join (5 RTTs). The overhead is minimal.
• Secure Deposit: Total time was around 12.355 seconds, compared to an estimated 12.33 seconds for a plain deposit (factoring in 12.21s for ETH confirmation). The overhead was less than 1%.
• Secure Exchange: Total time was approximately 255.228 ms, compared to an estimated 150 ms for a plain exchange (5 RTTs).
• Secure Withdraw: Total time was around 12.43 seconds, compared to an estimated 12.33 seconds for a plain withdrawal (with 12.21s on-chain confirmation). The overhead was again less than 1%.

The results conclusively showed that the time costs for Pisces' secure operations are very similar to their plain counterparts, with the additional cryptographic overhead typically adding less than 0.11 seconds to the overall transaction time.

Comparison with Other Privacy Systems (Table II):

Pisces' computation costs were also compared to other anonymous credential applications, specifically Privacy Pass and the Privacy-Preserving Incentive System (PPIS). For example, PPIS (13) reported Join costs of 10ms (User) / 9ms (Provider), Earn (Deposit) costs of 8ms / 12ms, and Spend (Withdraw) costs of 30ms / 72ms. Pisces' computation costs, while performing more complex functionalities and offering stronger privacy guarantees, were found to be comparable to these systems. This further underscores the practical efficiency and viability of the Pisces design in a real-world context.

Defensive Implications

[▶ Watch: High-level algorithms: Setup, PKeyGen, Join, Issue (8:00)]()

The development of Pisces offers significant defensive implications for various stakeholders within the cryptocurrency ecosystem:

1. For Centralized Cryptocurrency Exchanges: Implementing a system like Pisces can transform how exchanges manage user data and privacy. By adopting Interaction Indistinguishability, exchanges can drastically reduce their exposure to privacy-related data breaches, as they would no longer possess the ability to link users' real identities to their external on-chain activities. This mitigates the risk of catastrophic data leaks that could expose users' entire financial histories. Offering such strong privacy guarantees, while still meeting regulatory demands, could also serve as a significant competitive advantage, attracting privacy-conscious users. Furthermore, it demonstrates a proactive commitment to user protection and ethical data handling.

1. For Cryptocurrency Users: Users should actively seek out and advocate for exchanges that adopt privacy-preserving technologies like Pisces. Such systems empower users to regain control over their financial privacy, ensuring that their on-chain activities—outside the exchange platform—remain unlinkable to their real-world identities. This protects them from potential surveillance, targeted advertising based on financial behavior, and the risks associated with a centralized entity holding a complete financial profile.

1. For Regulators and Policymakers: Pisces demonstrates that AML, KYC, and tax compliance are not inherently incompatible with strong user privacy. Regulators can gain confidence that privacy-enhancing technologies can be designed to include auditability and accountability mechanisms. This understanding can foster a more progressive regulatory environment that encourages innovation in privacy-preserving financial technologies, rather than stifling it. It provides a blueprint for how future financial systems can be both private and compliant, fostering broader adoption of digital assets while maintaining financial integrity.

1. For Developers and Researchers: Pisces provides a robust framework and a set of cryptographic primitives (NIZK, blind signatures, homomorphic commitments) that can be adapted and extended for other privacy-preserving applications in finance and beyond. The formal security models and proofs serve as a foundation for future research into more complex compliance rules, multi-party computations, and decentralized privacy solutions.

In essence, Pisces offers a defensive strategy that shifts the paradigm from "collect everything and secure it" to "collect only what is unavoidable for compliance, and make the rest private by design." This approach inherently reduces the attack surface for privacy-related data, benefiting all parties involved.

Key Takeaways

• Reconciling Privacy and Compliance: Pisces demonstrates the feasibility of building a cryptocurrency exchange system that simultaneously offers strong user anonymity and adheres to crucial regulatory requirements like KYC, AML, and tax reporting.
• Full Anonymity Against the Platform: The system achieves "full anonymity" through Interaction Indistinguishability, ensuring the centralized exchange learns essentially no information about users' internal transactions or external on-chain activities beyond what is strictly necessary and publicly unavoidable.
• Leveraging Advanced Cryptography: Pisces relies on efficient cryptographic primitives, including Non-Interactive Zero-Knowledge (NIZK) proofs, additively homomorphic commitments, and blind signatures, to provide constant communication and computation overhead, making it scalable.
• Provable Security and Soundness: The system is provably secure, guaranteeing user anonymity, overdraft prevention, and client compliance (e.g., accurate tax reporting) against a malicious platform and malicious users.
• Practical Efficiency: A prototype implementation shows that Pisces operations complete in milliseconds with minimal communication overhead (under 12KB), adding less than 0.11 seconds to typical plain exchange operations, demonstrating its real-world practicality.
• Blueprint for Future Financial Systems: Pisces offers a foundational model for designing privacy-preserving and compliant financial systems, enabling a more secure and user-centric approach to digital asset management.

About the Speaker(s)

Ya-Nan Li is the speaker who presented the work "Pisces: Private and Compliable Cryptocurrency Exchange" at the NDSS Symposium. The provided transcript and metadata do not contain further biographical details about the speaker, such as their title or institutional affiliation.