IronDict: Transparent Dictionaries from Polynomial Commitments
Hossein Hafezi from NYU presents IronDict, a novel transparent dictionary construction using polynomial commitment schemes. IronDict addresses the major limitations of existing Merkle tree-based systems, such as high auditing costs and imperfect privacy. By modeling the dictionary with polynomials and leveraging the algebraic properties of the KZH commitment scheme, IronDict achieves perfect privacy and dramatically reduces auditing overhead, making it feasible for end-users to verify the system's integrity on consumer devices.
Transparent dictionaries are a critical primitive for enabling key transparency in secure messaging applications like WhatsApp, ensuring users can verify they have the correct public key for their contacts. The core goal is to provide everyone with a consistent view of the server’s state, preventing malicious activities like man-in-the-middle attacks. Existing solutions, primarily based on Merkle trees, suffer from two significant drawbacks: high auditing costs and imperfect privacy.
The Challenge with Existing Transparency Systems
Current transparent dictionary deployments, such as WhatsApp’s, rely on Merkle trees. This approach presents major scalability and privacy challenges:
- Prohibitive Auditing Costs: At each epoch (a discrete point in time), the server publishes a commitment to the dictionary’s state and an invariance proof that certifies correct state transitions. In Merkle tree-based systems, these proofs are linear in the number of updates, resulting in massive proof sizes. For a system at WhatsApp’s scale, this could mean hashing over 200 MB of data every few minutes to audit the system. This is infeasible for typical users on mobile devices, forcing the auditing role to be delegated to a few large, trusted third parties.
- Imperfect Privacy: Merkle tree constructions inherently leak information through their proofs (Merkle paths). This leakage is formalized via a “leak function.” For example, the system used by WhatsApp, called Seamless, reveals the last time a user’s key was updated with every lookup. This metadata can be sensitive and create potential targets for adversaries.
IronDict: A New Approach with Polynomials
IronDict introduces a new construction for transparent dictionaries that replaces Merkle trees with polynomial commitment schemes (PCS). This fundamental shift allows for significantly more efficient and private systems.
The dictionary is modeled using a set of multilinear polynomials:
- Index Polynomial: Maps user labels (e.g., usernames) to unique indices, which are points on a boolean hypercube. To handle potential hash collisions when mapping arbitrary strings to a finite set of indices, IronDict employs an open addressing strategy. It iteratively probes for a vacant slot by hashing the label with a counter (
hash(label || 0),hash(label || 1), etc.). - Value Polynomial: Maps the indices from the Index Polynomial to the corresponding values (e.g., public keys).
- Rand Polynomial: A special polynomial designed to provide efficient proofs of consistency.
Key Functionalities and Innovations
Proof of Consistency
A crucial feature is proving that a user’s value (e.g., public key) has not been tampered with between two distant epochs, especially while the user was offline (a “ghost key attack”). Instead of requiring a linear number of lookups, IronDict uses the rand polynomial.
- This polynomial is constructed as a random linear combination of all the “delta” polynomials (the difference between value polynomials of consecutive epochs).
- By checking for the equality of the
randpolynomial’s evaluation at two different epochs, a client can verify with high probability that no intermediate changes occurred. The randomness ensures that malicious changes that revert themselves cannot cancel out and go undetected.
Perfect Privacy
IronDict is the first scheme to achieve perfect privacy. The server’s responses consist of polynomial commitments and openings.
- Unlike Merkle paths, these algebraic structures can be made zero-knowledge efficiently.
- By using a polynomial commitment scheme that supports efficient ZK transformations (like KZH), all server interactions reveal nothing beyond the specific query’s result, completely eliminating the metadata leakage found in previous systems.
Concrete Implementation and Performance
IronDict is instantiated with the KZH polynomial commitment scheme, which is particularly well-suited for this application due to:
- Constant-size commitments.
- Sublinear verification time.
- Extremely efficient (effectively free) openings for points on the boolean hypercube.
- Efficient zero-knowledge transformations.
In an implementation for a dictionary with 1 billion entries, IronDict demonstrates significant advantages over the state-of-the-art:
- Auditing: The audit proof is a constant 8 kB per epoch (independent of the number of updates) and can be verified in just 35 ms on a consumer laptop. This is a massive improvement over the gigabyte-sized proofs and multi-second verification times of Merkle tree systems, making self-auditing by end-users practical.
- Lookup: While server-side lookup is currently slower than highly-optimized Merkle tree implementations (33 ms vs. ~1 ms), client-side verification remains fast (30 ms).
- Fast Forwarding: For auditors who have been offline for many epochs, IronDict supports techniques like Incremental Verifiable Computation (IVC) and checkpoints to rapidly catch up. Its IVC-based solution is shown to be over 1000x more efficient for the server than previous work.