The benefits of zero-knowledge for mechanism design

Cross-posted on the Aleo blog

Since software started eating the world more than a decade ago, the scale of available information has never been greater. As a result, developers now have the opportunity to prove quite a lot of things using verifiable computing, creating succinct proofs about almost all of the world's interactions and software. However, since the possibilities are so great, we need to focus on the most practical applications, where privacy can make the biggest impact.

Verifiable compute offers us two unique properties: Privacy and scalability. First, proofs can be made about computations or data without revealing anything other than the desired property. And second, the validity of truly enormous statements can be verified in seconds, making them quite useful.

However, as Tarun Chitra discusses, the advantages of verifiable compute are still quite abstract and technical, and suggests we address the search for concrete use cases by staying in a technical domain: mechanism design.

What is mechanism design?

Mechanism design is the mathematical study of designing economic mechanisms to incentivize agents to achieve certain desired outcomes. Using mechanism design, we can model the interactions of people based on their preferences given certain states of the world. Christopher Goes talks about the concept of program equilibria: If users in a system can commit to programmatically defined predicates and make private proofs of compliance, this can potentially fundamentally scale up cooperative games. Taking the basic prisoner's dilemma as a starting point, you can imagine a future where companies or governments decide only to donate to shared causes if all parties can prove that they cooperated in the past; did not invest in unethical products, and did not break too many laws.

Potential benefits modeled in such an abstract setting might be usable in a range of real-world use cases. Consider, for example, financial auctions, school placement auctions, or even public goods funding mechanisms. One could privately validate all of these statements into a Leo program, allowing for cooperation of entities on a massive scale.

Benefits of zero-knowledge for mechanism design

If that sounds pretty abstract, that’s because it is. However, verifiable computing has a few important, real-world benefits for mechanism design: namely, transparency, privacy, and credibility.

Introduce more auditability

Many mechanisms rely on a trusted coordinator. When executing a particular mechanism, the coordinator may, for example, accept spending commitments from users, compute allocations, and bill users accordingly.

One concrete use case of zero-knowledge proofs is that the coordinator can prove to any stakeholders involved that allocations were computed correctly. For example, an auction house running a second-price auction can show all bidders and outside participants that yes, they did not secretly run a first-price auction.

Unfortunately, there are many examples of trusted coordinators not adhering to the rules. Take this quote from an auditor of school allocation mechanisms:

"OIG interviews with principals of 30 audited schools that held more than 500 combined audit failures revealed that many didn’t know all the admissions rules, which are scattered across several locations. Others knew the rules and broke them. In some cases, audit failures may have been caused by documentation errors. [...] One principal improperly admitted her four children, her niece and nephew.” - A Theory of Auditability for Allocation and Social Choice Mechanisms

One formal way to model how a coordinator can prove that it acted correctly is to introduce a measure of auditability: The number of users who need to communicate to detect cheating. in his presentation linked previously, Chitra outlined that zero-knowledge proofs could help make succinct auditability statements for very large mechanisms. Auctions are used every day around the world, and it is key that coordinators are held accountable.

Hide the mechanism itself to increase privacy and resilience

Counterintuitively, it is possible to hide details of the mechanism itself from any participants. In a recent paper, Canetti, Fiat and Gonczarowski show how to commit to, and run, any given mechanism without disclosing it, while enabling the verification of incentive properties and the outcome—all without the need for any mediators.

It is useful to distinguish two different classes of mechanisms to intuit the relevance:

• In the first class, players have private types and public actions/reports. This includes auctions and matching mechanisms. By hiding parts of the mechanism, it can become harder for players to collude or infer private costs of the mechanism designer. As another example, we can e.g., in a matching setting, hide whether the mechanism that is run is Deferred Acceptance, Top Trading Cycles, or Serial Dictatorship.
• In the second class, players have private actions (and hence moral hazard), which includes contracts (and contract theory). The principal would be sending to the agent a cryptographic commitment to a hidden contract along with a zero-knowledge proof of the optimal effort for the agent to exert.

It has yet to be seen in which areas this counterintuitive and powerful approach can be of value. Perhaps one day auctions and salary negotiations worldwide use zero-knowledge proofs to preserve participants' privacy.

Remove reliance on the coordinator entirely and grow credible neutrality

For some settings, the holy grail is to entirely remove trust in a coordinator.  By leveraging a zero-knowledge, proof-based cryptocurrency like Aleo, many mechanisms can be instantiated in a privacy-preserving and credibly neutral way.

There has been a wealth of research and development in recent years, ranging from on-chain auctions to on-chain voting, which are just waiting to be adopted. You can already find examples of these on our developer documentation.

Conclusion

In conclusion, the integration of zero-knowledge proofs into mechanism design holds immense potential for transforming the way we incentivize and coordinate social interactions. Concrete applications of zero-knowledge proofs in mechanism design can range from financial auctions to school placements.

Cryptocurrencies like Aleo make it possible to eliminate the need for trust in coordinators entirely. With ongoing research and development, the adoption of zero-knowledge mechanisms promises a future where social coordination can occur in a privacy-preserving and credibly neutral manner, ushering in a new era of transparency and cooperation.