fhemechanisms, a library of FHE-enabled mechanisms from algorithmic game theory, social choice, …

[orpheuslummis]

Application to the Zama grant program

Description

fhemechanisms is a Solidity library, leveraging fhevm, providing a collection of FHE-enabled mechanisms from algorithmic game theory, social choice, …

fhemechanisms is also to be a Github-based community of developers interested in tech progress on computational mechanism design.

FHE in computational mechanism design enables important capabilities. It allows conducting strategic interactions without compromising the privacy of participants' inputs, sometimes changing the game theoretical situation to be one that behaves well. For example, in some auctions it enables them to be dominant-strategy-incentive-compatible.

Deliverables

The mechanisms we focus on in this grant are:

• Approval voting
• Multiunit auction
• Dominant assurance contract
• Pairwise voting

Each mechanism is implemented as Solidity contracts, with a test suite, and organized into an overall library. Each have a README to document them, and exploring how the mechanism is changed by its specific FHE implementation.

We will write a concise post, to be published in relevant communities, to invite developers to use them or participate in the project.

Timeline

March-April 2024.
One lead developer ~10-15 hours weekly on the project during the timeline.

Impact

• Provides a toolkit for builders that will use these mechanisms in their systems. (This includes future projects by Orpheus building on FHE mechanims.)
• Provides a Schelling point for the community to collaborate on FHE-enabled mechanism design-inspired mechanisms.
• Building the tech stack around fhevm and Zama, and providing further examples. Leading the way to furthering adoption of FHE tech.

Reward

Grant range: 5K-20K €

We suggest the higher range to additionally provide example frontends leveraging the mechanisms, including more mechanisms such as a bounding curve (primary automated market maker), and a documentation website for the project. This would follow a milestone based-approach. Additionally, the higher range would allow to offer a bug bounty prize for after the grant period.

Possibilities of expansion

• more mechanisms
• more research on FHE-enabled mechanism design
• articles to showcase how they work and be useful in practice
• hackathon focused on mechanism design-inspired work

Related links and reference

• Github repo: https://github.com/orpheuslummis/fhemechanisms
• Personal profile: https://orpheuslummis.info/ & https://github.com/orpheuslummis
• Source of inspiration:
  • https://www.mechanism.institute/library
  • the fhevm examples

Contact information beyond Github:

• Discord: orpheuslummis
• Email: [email protected]

Notes

We welcome feedback!

The application is subject to change according to feedback and further (collaborative) reflection, until finalized.

We are interested in further ideas of mechanisms to focus on that would be impactful!

[zama-bot]

Hello orpheuslummis,

Thank you for your Grant application! Our team will review and add comments in your issue! In the meantime:

1. Join the FHE.org discord server for any questions (pick the Zama library channel you will use).
2. Ask questions privately: [email protected].

[aquint-zama]

Hey @orpheuslummis, Thanks for your application. Your proposal is interesting but we will soon introduce breaking changes (like asynchronous decrypt) that would justify to wait a bit before starting it.

Let me sync internally to see how long we are speaking about before having this new API.

[orpheuslummis]

@aquint-zama I am looking forward to know more of that new API. I would be surprised if it would break core flows of using FHE ops.

To derisk the project further, I will make some progress on it re structuring, documentation, implementation.

Thanks for your interest :)

[aquint-zama]

Hello @orpheuslummis

We are not forgetting about your proposal but we are about to release a new version of fhEVM that will overlap a bit with your proposal. I'll tell you as soon as we have the final decision.

[orpheuslummis]

Thanks @aquint-zama for the update! Appreciated. Turns out the "delay" fits my current agenda. I'm looking forward for the update and further feedback/decision. :)

[orpheuslummis]

I saw a new version of fhevm. https://github.com/zama-ai/fhevm/releases/tag/v0.4.0 Bravo!
I'm curious to know if it contains the 'overlap' you were mentioning, because I didn't immediately see it.

[aquint-zama]

Hello @orpheuslummis, we've introduced with this version a suite of standard contracts in fhevm-contracts. That was the part overlapping with your proposal imho. Wdyt?

[orpheuslummis]

That's great.

What I'm thinking now: It seems preferable to centralize new 'examples' contracts into fhevm-contracts instead of creating another place, unless there's a strong structural reason (e.g. quite different tooling necessary). The grant proposal then now is the introduction of mechanisms from algorithmic game theory, social choice, … to fhevm-contracts. It could proceed by providing one new example contract at a time to the common lib. I would select one from the set I had in mind initially: Approval voting, Multiunit auction, Dominant assurance contract, Pairwise voting. Each submission can be well documented. There can be a blog post on the topic after a few are implemented.

[aquint-zama]

I think proceeding one contract at a time and writing a companion blogpost is a great idea.
I would suggest picking 1-2 from the initial set and give a bit more details to let us to decide whether we launch this grant or not.

[orpheuslummis]

Here is a revised (short) grant proposal in light of our update and conversation:

Implementation of approval voting and range voting mechanisms. Demonstrate their composition with a code example, and a narrative-driven but tech-focused blog post set in a hypothetical decentralized R&D accelerator.

Approval voting: Voters approve multiple candidates. Complexity: O(voters_count * canditate_count).

Range voting: Each voter assigns a score to each project for every dimension. Complexity: O(voters_count * candidate_count * dimensions_count).

Composition: Consider an hypothetical decentralized R&D accelerator. The community needs to select and evaluate projects. They use the following approach: First, the community filters for the top N projects with approval voting (quick). Then, for the top projects, the community uses range voting to elicit evaluation along multiple relevant dimensions. Finally, the community can use that selection and evaluation data to make decisions and give feedback – think of it as part of a broader governance system empowering an open R&D accelerator.

Notes:

• One challenge is to leverage iterative computation to make the mechanisms more scalable.
• If you prefer, it can alternatively be a smaller project: implementation of just one mechanism and its PR submission.
• (random AI-related thought: Code examples become training data for the LLMs to understand the tech stack.)
• Idea of extension: governance mechanism to select the dimensions of the multidimensional range voting.
• Idea of extension: integration with identity or proof of humanity framework for authentication.
• We considered pairwise voting and multidimensional borda count for the second step, but thought are too computationally complex.

I suggest a budget of 10K euros for this, but it can be less if you want a more minimal version (e.g. no composition or blog post), or a more for a comprehensive version.

My goal is to implement and showcase generally useful mechanisms from social choice theory and the like.

I welcome feedback and suggestions of better projects to do.

[zaccherinij]

Hi @orpheuslummis,

Thank you very much for your interest in what we do at Zama, and your proposition for a grant. For now, we will not follow up with your proposition. But we invite you to keep an eye on this repository as we will launch new bounties soon, if you're interested in playing with Zama libs.

Cheers,
JZ