TL;DR
NoCherry is a cryptographic protocol that enables verifiable random sampling of private datasets without relying on a single trusted auditor. By combining decentralized randomness beacons with independent registration servers, it allows a data holder to prove that a disclosed sample was drawn fairly and wasn't "cherry-picked" to hide flaws or bias.
What Problem Does This Paper Address?
In fields like AI benchmarking, security auditing, and compliance, organizations often need to support claims about private data they cannot fully disclose. The standard approach is to provide a random sample for inspection. However, this creates a "trust gap": if the data holder picks the sample, they have a strong incentive to select only the best examples (cherry-picking).
Existing solutions usually require a single trusted third-party auditor to oversee the draw. This creates a single point of failure—the auditor could collude with the data holder or simply make a mistake. Furthermore, digital data is malleable; a malicious actor could wait to see which items are selected and then fabricate or alter them to pass the audit. NoCherry aims to solve these issues by decentralizing trust and cryptographically "locking" the dataset before the random selection is known.
Methods
The NoCherry protocol relies on three main components:
- Commitment: The data holder (committer) generates salted hashes for every item in their dataset. They sign a manifest containing these hashes, a reveal probability, and a specific "anchor round" from a public randomness beacon.
- Independent Registration: The committer sends this signed commitment to several independent registration servers. These servers act as witnesses to when the commitment was made. Crucially, they do not need to communicate with each other.
- Decentralized Randomness Beacon: The protocol uses a threshold randomness beacon (like drand), which periodically emits unpredictable, publicly verifiable random values. The selection is tied to a future beacon round (specifically, the anchor round + 2).
To handle network delays and ensure all servers agree on the same selection round without talking to each other, the authors introduced the Anchor Rule. The committer picks a current beacon round as an "anchor." Servers only accept the commitment if it arrives before the selection round starts. This prevents "backdating" attacks where a committer tries to register a dataset after the random seed is already public.
Datasets
The paper focuses on the protocol's mechanism rather than a specific machine learning task. To evaluate performance and reliability, the authors used:
- Microbenchmarks: Conducted on a dataset of 100,000 items to measure the computational overhead of salting, hashing, and verifying receipts.
- Live Beacon Trials: The protocol was tested against the live drand quicknet beacon using three local registration servers to quantify how often network jitter causes servers to disagree on the selection round.
Key Insights and Ideas
- Trust is 1-of-L: The protocol is secure as long as the randomness beacon's threshold holds and at least one of the required registration servers is honest. You don't need to trust the whole system, just a single "honest witness" among the servers you choose.
- Solving the Coordination Problem: The "Anchor Rule" is a clever way to achieve consensus on a future event across non-communicating servers. By signing the anchor round into the commitment, the committer essentially "locks in" the clock, preventing servers from accidentally (or maliciously) assigning the commitment to different random seeds.
- Offline Verification: Once the data holder publishes the "audit bundle" (receipts, revealed items, and cryptographic openings), anyone can verify the entire audit offline without ever contacting the registration servers or the beacon again.
- Named Commitments: To prevent "grinding" attacks (where a committer tries thousands of different salt combinations until they get a "lucky" draw), the protocol suggests tying commitments to a persistent identity and sequence number, which servers can enforce.
Key Results
- Efficiency: For a dataset of 100,000 items, generating the commitment takes only 200 ms. Offline verification of a receipt is even faster, taking approximately 119 ms for batch selection.
- Reliability: In live experiments with simulated network delays, the anchor rule resulted in 0% disagreement among accepting servers. Using a combination of the relay's latest round and the client's local clock for anchoring led to a 97% acceptance rate across all servers.
- Detection Power: The authors demonstrate that the protocol is highly effective against widespread data manipulation. For example, with a 10% sampling rate, an auditor has a >99% probability of catching at least one flaw if 50 items in the dataset are "bad."
Limitations and Future Work
- Population Integrity: NoCherry proves the sample is representative of the committed set. It cannot prove that the committed set is the entire or correct population. This still requires external "compliance audits" to ensure no data was left out.
- Privacy vs. Utility: Repeatedly auditing the same private dataset will eventually leak the entire corpus. The authors point to "reusable holdout" literature as a way to manage this budget.
- Scalability: Currently, the commitment size scales linearly with the number of items (~67 bytes per item). The authors suggest a Merkle tree variant as future work to reduce this cost for extremely large datasets.
- Transparency: The authors propose adding a public transparency log of registrations to make it even harder for servers to omit or backdate entries.
Summary updated