Notus: Dynamic Proofs of Liabilities from Zero-knowledge RSA Accumulators

Notus: Dynamic Proofs of Liabilities from Zero-knowledge RSA Accumulators

Speakers: Jiajun Xin, PhD Student, HKU (presenting on behalf of Jing Sun, Assistant Professor, HKU)

Conference: USENIX Security '24

YouTube: https://www.youtube.com/watch?v=o-Q-54-RPHE

Overview

The talk "Notus: Dynamic Proofs of Liabilities from Zero-knowledge RSA Accumulators" introduces a novel system designed to enhance the transparency and security of centralized cryptocurrency exchanges (CEXs). Following the catastrophic collapse of FTX in 2022, which was attributed to internal unauthorized transactions and misrepresentation of assets, the cryptocurrency industry has faced immense pressure to adopt verifiable proof of solvency (PoS) systems. While Proof of Assets (PoA) is relatively straightforward, proving liabilities—the total funds a platform owes its customers—presents significant technical and privacy challenges.

This presentation by Jiajun Xin, on behalf of Jing Sun, addresses a critical vulnerability identified in existing static Proof of Liabilities (PoL) models, termed the "window opportunity attack." Notus proposes a dynamic PoL system that not only resolves this attack vector but also significantly improves efficiency, scalability, and user privacy compared to current industry practices like Binance's PoL solution. By leveraging advanced cryptographic primitives such as zero-knowledge RSA accumulators and zero-knowledge MultiSwap, Notus offers a robust framework for CEXs to continuously and verifiably demonstrate their financial integrity to users and auditors.

The work is particularly significant for the cryptocurrency ecosystem, aiming to restore user trust in centralized entities by providing a strong cryptographic guarantee that platforms are not under-reporting liabilities or manipulating user balances. This contribution moves beyond static snapshots of solvency to a dynamic, auditable, and privacy-preserving model that can adapt to the continuous flux of transactions on a CEX, offering a path towards greater accountability and stability in the digital asset economy.

Background

▶ Watch: Introduction to Notus and CEX solvency problem (0:00)

The digital asset economy heavily relies on cryptocurrency exchanges, which facilitate the trading of various digital currencies. These exchanges primarily operate in two forms: centralized exchanges (CEXs) and decentralized exchanges (DEXs). Despite the growing popularity of DEXs, CEXs continue to dominate the market, accounting for over 90% of all exchanges in 2024, largely due to their efficiency and established customer habits. However, this dominance comes with a significant security and trust challenge: the custody of user assets. Unlike DEXs, CEXs hold users' funds, making them attractive targets for attacks and susceptible to internal mismanagement.

The collapse of FTX in 2022 served as a stark reminder of these risks. Despite being the third-largest CEX globally at the time, FTX failed due to unauthorized internal transactions and a severe misrepresentation of its financial health. This event spurred a widespread call for enhanced transparency, leading many major CEX platforms to adopt Proof of Solvency (PoS) systems. A PoS system aims to cryptographically prove that a CEX platform's assets are no less than its liabilities. It typically comprises two main components: a Proof of Assets (PoA) subsystem and a Proof of Liabilities (PoL) subsystem.

The PoA subsystem is relatively straightforward; it involves the platform proving ownership of specific accounts holding certain assets, typically by generating digital signatures for these accounts. The PoL subsystem, however, is far more complex. Its goal is to prove the total funds the platform owes its customers, allowing any individual customer to act as a third-party auditor without revealing sensitive user balance information.

Current industrial practices, such as Binance's PoL solution, generally follow a static PoL model. In this model, users deposit funds, and the platform stores these liabilities in a dictionary (e.g., username-to-liability key-value pairs). This dictionary is then committed to a Merkle tree, and the Merkle root is published as a digest on a public bulletin board (often a blockchain). Users can then query their individual liability records and verify their inclusion using Merkle proofs. An auditor, meanwhile, uses zero-knowledge succinct non-interactive arguments of knowledge (SNARKs) to verify that all account balances are positive and that the sum of liabilities is correctly calculated, all while preserving user privacy. Binance, for instance, uses SNARKs to prove that the sum of all leaves in their Merkle tree corresponds to the total liability and that all individual leaf values are positive.

While this static model provides a snapshot of solvency, it suffers from several critical limitations. Firstly, it requires all accounts to be re-proven even if they haven't been updated, leading to inefficiencies. Secondly, there's no inherent correlation or verifiable link between different epochs (snapshots), making it difficult to detect historical manipulation. Most significantly, it is vulnerable to a novel attack vector termed the "window opportunity attack," which Notus specifically addresses. This attack allows a malicious platform to temporarily under-report its total liabilities by manipulating inactive user accounts, only to restore them before the users become active again, thereby deceiving auditors and users alike during the attack window.

Key Findings

▶ Watch: Static PoL model and its inherent limitations (3:00)

The research behind Notus identifies a critical flaw in existing static Proof of Liabilities (PoL) systems: the "window opportunity attack." This attack enables malicious centralized exchanges (CEXs) to temporarily under-report their total liabilities without detection, by manipulating inactive user accounts. The talk effectively illustrates this with a scenario where a user, Alice, has her liability reduced from 1,000 to 1 coin during an inactive period (epochs 2-6), only for it to be restored to 1,000 coins before she returns to the system in epoch 7. This manipulation creates a "window of opportunity" where the CEX can appear more solvent than it actually is, undermining the very purpose of PoL.

To counter this, Notus proposes and constructs a dynamic PoL model. Unlike static models that generate a new dictionary from scratch for each audit epoch, the dynamic model updates the dictionary from its previous state and cryptographically proves the correctness of these updates. This fundamentally changes the audit paradigm from verifying a snapshot to verifying a continuous, append-only history of liabilities.

The core contributions and key findings of Notus include:

1. Identification of the Window Opportunity Attack: Pinpointing a significant, previously unaddressed vulnerability in static PoL systems that allows for undetected liability manipulation.
2. Proposal of a Dynamic PoL Model: Introducing a new paradigm for PoL that ensures continuous verifiability of liability updates, making it robust against the window opportunity attack.
3. Novel Cryptographic Tools: Extending existing cryptographic primitives—specifically, RSA accumulators and MultiSwap protocols—into their zero-knowledge (ZK) counterparts. Notus presents the first construction of Zero-knowledge RSA accumulators and Zero-knowledge MultiSwap with minimal overhead, tailored for the specific privacy and efficiency needs of dynamic PoL.
4. Efficient and Scalable Construction: Notus demonstrates the first practical construction of a dynamic PoL system built upon these ZK-enhanced tools. This system uses a constant-sized digest for the dictionary and constant-sized membership proofs, offering significant efficiency gains.
5. Superior Performance: Experimental results show that Notus is approximately four times faster than current SNARK-based Merkle tree update methods (like Binance's approach) for liability updates. It also exhibits near-linear scalability for proof generation time and SNARK constraints as the number of updates increases, proving its practical viability for large-scale CEXs.
6. Enhanced Privacy and Verifiable History: Notus inherently protects user privacy through zero-knowledge proofs and provides a well-recorded transaction history via hash chains, allowing users to catch up on their entire liability history with a single membership proof.

These findings collectively present a robust, privacy-preserving, and highly efficient solution to a critical trust problem in the centralized cryptocurrency ecosystem, offering a significant improvement over existing PoL methodologies.

Technical Deep Dive

▶ Watch: Demonstrating the 'Window Opportunity Attack' (6:00)

The fundamental innovation of Notus lies in its transition from a static to a dynamic Proof of Liabilities (PoL) model, specifically engineered to thwart the "window opportunity attack" and enhance efficiency. The static model, exemplified by Binance's use of Merkle trees, generates a new Merkle root for each audit epoch, proving the sum of liabilities at that specific point in time. As highlighted, this approach is susceptible to manipulation where a malicious platform could temporarily lower inactive user liabilities, only restoring them before the user queries their balance. For instance, if Alice deposits 1,000 coins in epoch 1, a malicious platform could reduce her recorded liability to 1 coin in epoch 2 when she is inactive, only to restore it to 1,000 coins by epoch 7 when she returns. This "window" (epochs 2-6) allows the platform to misrepresent its total liabilities.

To address this, the Notus dynamic PoL model imposes stringent requirements on how the dictionary of liabilities is updated and audited:

1. Append-only Update: All updates to the ledger must be strictly append-only, preventing retroactive deletion or alteration of historical records.
2. Timestamped Transactions: Each update must include a timestamp corresponding to the current epoch number, preventing the insertion of fake historical data.
3. Non-negative Balances: No update should result in any account balance becoming negative, ensuring financial integrity.
4. Correct Liability Sum Update: The total sum of all liabilities must be correctly updated in correspondence with individual account changes.

At its core, Notus relies on three key cryptographic tools, significantly enhanced for a dynamic, privacy-preserving context:

1. RSA Accumulators: A classical cryptographic primitive that can commit a set of elements to a short, fixed-size digest. It provides O(1) membership proofs, meaning the proof size and verification time are constant regardless of the set's size. Notus extends this to Zero-knowledge RSA Accumulators, ensuring that membership proofs do not reveal information about other elements in the set, thus preserving user privacy. This allows the dictionary of user liabilities to be committed efficiently and privately.
2. Hash Chains: A fundamental data structure that links a sequence of data blocks using cryptographic hashes, similar in concept to a blockchain. In Notus, hash chains are used to record the transaction history for each user. Each entry in a user's hash chain includes their user ID, liability amount, the update epoch number, and the hash of the previous entry. This ensures a verifiable, tamper-evident history of all liability changes for each user.
3. MultiSwap Protocol: This protocol facilitates proving that a set S can be transformed into an updated set S' by removing a subset Y and inserting a new set X. Notus extends this into Zero-knowledge MultiSwap, which, when combined with SNARKs, allows the platform to prove the correctness of these set operations (deletions and insertions) without revealing the specific elements being added or removed, or the individual user balances.

Construction of Notus:

In the Notus system, the dictionary of user liabilities is committed using a Zero-knowledge RSA Accumulator. This results in a constant-sized digest that is published publicly. Crucially, the membership proofs for individual users are also constant in size, thanks to the properties of ZK-RSA accumulators.

For each epoch, instead of regenerating the entire dictionary, the platform uses ZK-MultiSwap to prove the correctness of the updates. This involves proving several critical conditions via SNARKs:

• Deleted Old Transactions in Hash Chain: The ZK-MultiSwap ensures that any "deleted" (i.e., updated) old transaction records are correctly reflected and recorded within the newly inserted transaction's hash chain. This links previous states to current states.
• Correct Epoch Timestamp: It verifies that the timestamp of the newly inserted (or updated) transaction corresponds to the current epoch, preventing the platform from retroactively injecting or altering data.
• Positive Updated Liability: The proof confirms that after any update, a user's liability remains positive, preventing the platform from falsely reducing balances below zero.
• Correct Sum of Liabilities Update: The ZK-MultiSwap verifies that the total sum of all liabilities in the accumulator is accurately updated to reflect all individual changes, maintaining the integrity of the overall PoL.

The system's implementation leverages Groth16 for the SNARKs, a widely used and efficient SNARK construction. The Poseidon hash function is chosen for its SNARK-friendliness, aligning with best practices for cryptographic systems integrated with zero-knowledge proofs.

By integrating these advanced cryptographic primitives, Notus offers several advantages:

• Efficiency: Only the updated portion of the dictionary needs to be processed and proven, leading to significant computational savings.
• Verifiable History: The use of hash chains provides an immutable and auditable transaction history for each user.
• Parallelization: Membership proof precomputations can be highly parallelized, further boosting efficiency.
• Privacy Protection: Zero-knowledge proofs ensure that individual user balances and transaction details remain confidential, addressing a key concern in PoL systems.

This sophisticated technical architecture allows Notus to provide a robust, dynamic, and privacy-preserving Proof of Liabilities solution, fundamentally improving the security and trustworthiness of CEX operations.

Demo / Proof of Concept

▶ Watch: Essential cryptographic tools for Notus's dynamic system (9:30)

The efficacy and practical advantages of Notus are demonstrated through comprehensive benchmarking and comparisons against existing industry practices. The evaluation focuses on two key metrics: the time taken to generate proofs for liability updates and the number of constraints required by the underlying SNARKs, which directly correlates with computational cost.

The experimental setup involved comparing three systems:

1. Binance's approach: Representing a state-of-the-art static PoL system based on Merkle trees and SNARKs.
2. Merkle Insert: A barebones version of Merkle tree updates within a SNARK, designed to capture the fundamental overhead of such an operation without Binance's specific business logic, providing a fairer baseline for comparison.
3. Notus: The proposed dynamic PoL system utilizing zero-knowledge RSA accumulators and ZK-MultiSwap.

All systems were benchmarked with approximately 1,000 updates to simulate real-world transaction volumes. The Notus system was built using Groth16 for SNARKs and Poseidon as the hash function, chosen for its SNARK-friendliness, similar to Binance's likely choices.

Key Performance Results:

• Update Efficiency: The benchmark results showed that Notus is approximately four times faster at generating proofs for liability updates compared to the "Merkle Insert" method (i.e., updating Merkle trees inside a SNARK). This significant efficiency gain is crucial for CEXs handling continuous high-volume transactions.
• Scalability: The presentation included a chart illustrating how the systems scale with an increasing number of updates or "swap operations" (referring to the MultiSwap protocol in Notus). Both the time required to generate proofs and the number of constraints in the SNARK grew almost linearly with the number of updates. This near-linear scalability indicates that Notus can effectively handle a growing number of users and transactions without prohibitive increases in computational resources.

To contextualize these performance figures, the speaker provided a striking comparison with Binance's reported scale:

• Binance reportedly has 55 to 45 million users in their PoL system.
• Assuming a single server with 32 cores, it would take approximately 628 days to generate a proof for all these users using Binance's current approach.
• Even with 100 servers, this process would still require 16 hours for a single proof generation. Due to this inefficiency, Binance currently generates its proofs only monthly.

In contrast, Notus demonstrates a vastly improved operational capability:

• Assuming 1 million users conduct transactions within a single epoch (a highly active scenario).
• With 32 such servers, Notus takes about 47 minutes to prove the correct update of the PoL for that single epoch.

This stark difference highlights Notus's ability to enable much more frequent, potentially even daily, PoL audits, significantly reducing the "window of opportunity" for malicious activity and offering continuous assurance to users. The experimental code for Notus is publicly available on GitHub, allowing for independent verification and further development.

Defensive Implications

▶ Watch: Notus system construction: ZK RSA accumulators and ZK Multiswap (10:30)

The Notus dynamic Proof of Liabilities (PoL) system offers profound defensive implications for centralized cryptocurrency exchanges (CEXs) and their users. By addressing the "window opportunity attack" and providing a more efficient, continuous, and privacy-preserving PoL mechanism, Notus significantly strengthens the security posture and trustworthiness of CEX platforms.

For CEX operators, adopting Notus means:

1. Mitigating the Window Opportunity Attack: The most direct defensive benefit is the elimination of the window opportunity attack. By requiring append-only, timestamped updates verified by zero-knowledge proofs, Notus makes it practically impossible for a malicious CEX to temporarily under-report liabilities for inactive users without detection. This provides a continuous, auditable chain of financial integrity.
2. Enhanced Transparency and Trust: Implementing Notus allows CEXs to provide a higher level of transparency to their users and independent auditors. The ability to frequently (e.g., daily or even more often) prove solvency, rather than just monthly, dramatically reduces the time window for potential fraud or mismanagement. This proactive demonstration of financial probity can restore and build user confidence, which is paramount in the wake of major industry collapses like FTX.
3. Improved Operational Efficiency: The four-fold speedup in proof generation for updates, combined with near-linear scalability, means CEXs can maintain a robust PoL system with significantly less computational overhead than static Merkle tree-based solutions. This efficiency allows for more frequent audits without straining resources, making continuous solvency verification a practical reality.
4. Privacy Protection: By using zero-knowledge RSA accumulators and Zero-knowledge MultiSwap, Notus ensures that individual user balances and transaction details remain confidential, even during audits. This is crucial for user privacy and regulatory compliance, preventing the exposure of sensitive financial data while still proving overall solvency.
5. Verifiable Transaction History: The integration of hash chains provides an immutable and verifiable transaction history for each user. This means that if a discrepancy were to arise, the entire history of liability changes could be traced and audited, providing strong forensic capabilities. Users themselves can easily verify their complete liability history with a single membership proof.

For users, Notus provides:

• Stronger Assurance: Users gain a higher degree of confidence that their funds are securely held and correctly accounted for by the CEX.
• Empowered Auditing: While full auditing is complex, the system is designed so that any individual user can, in principle, verify their own records against the publicly published digest and potentially identify inconsistencies.

In essence, Notus transforms PoL from a static, vulnerable snapshot into a dynamic, continuously verifiable, and privacy-preserving system. This paradigm shift offers CEXs a robust framework to proactively defend against internal fraud and external scrutiny, ultimately fostering a more secure and trustworthy digital asset ecosystem.

Key Takeaways

• Static PoL Vulnerability: Existing static Proof of Liabilities (PoL) systems are susceptible to the "window opportunity attack," where malicious exchanges can temporarily under-report liabilities for inactive users without detection.
• Dynamic PoL Paradigm: Notus introduces a dynamic PoL model that continuously proves the correctness of liability updates, effectively eliminating the window opportunity attack by requiring append-only, timestamped, and non-negative balance updates.
• Zero-Knowledge Cryptography: The system leverages novel cryptographic primitives, specifically Zero-knowledge RSA Accumulators and Zero-knowledge MultiSwap, to provide constant-sized digests and membership proofs while ensuring user privacy.
• Significant Efficiency Gains: Notus demonstrates a four-fold speedup in proof generation for liability updates compared to Merkle tree-based SNARK solutions and exhibits near-linear scalability, making frequent PoL audits practical for large CEXs.
• Enhanced Trust and Transparency: By enabling frequent, efficient, and privacy-preserving audits, Notus allows CEXs to continuously demonstrate financial integrity, thereby restoring and building user trust in centralized digital asset platforms.
• Verifiable History: The integration of hash chains provides a tamper-evident, auditable history of all user liability changes, which users can verify with a single membership proof.

About the Speaker(s)

The talk "Notus: Dynamic Proofs of Liabilities from Zero-knowledge RSA Accumulators" was presented by Jiajun Xin, a PhD student at HKU. He presented the work on behalf of Jing Sun, an Assistant Professor at HKU, who was unable to attend the conference. The presentation reflects research conducted at HKU, focusing on advanced cryptographic solutions for real-world security challenges in the cryptocurrency domain.