Polkassembly - PROPOSAL - FHE-WASM Research and Development for the Polkadot Ecosystem #2366

PROPOSAL - FHE-WASM Research and Development for the Polkadot Ecosystem

FHE-Wasm
A FHE enabled WASM VM guarantees secure and privacy-preserved trustworthiness.

General Project Information

Context

With the advancement of blockchain technology, a multitude of concepts from the field of cryptography are progressively being introduced and cultivated. Among them, Zero-Knowledge Proofs (ZKPs) hold a special place as a favoured cryptographic mechanism within the seat of the blockchain.

From a technical perspective, ZKP has evolved from Groth16 to PLONK, eventually progressing to Halo2. The fundamental aim of ZKP is to decrease the size of the proof and eliminate the computational redundancy resulting from the setup.

Functionally, ZKP has found wider applications since its inception. Initially used for privacy protection in ZCash and Mixers, it now finds application in improved systems like zk-rollup, bridge, and others. And there are a large number of ZKVM frameworks under development: Plonky3, SP1, Jolt, etc.

Over the past few years, Zama proposed the Torus Fully Homomorphic Encryption (TFHE) scheme, ensuring swift completion of homomorphic computations. Just last year, the Zama team offered another solution -- FHEVM, employing threshold-FHE to tackle the issue of private key sharing and integrated it into the Ethereum Virtual Machine (EVM) for application.

From a technical viewpoint, FHE and ZKP share certain aspects. FHE is predominantly used for privacy computation. Essentially, it handles computations without exposing the data, thus negating the need for third-party proofs for data credibility. Conversely, ZKP is used to prove the existence of the data satisfying certain conditions without revealing the actual data.

However, there is a subtle yet significant interconnection between the two.

For instance:
Suppose Alice has a solution X to a certain problem expressed as f(x)=0 (where f(x) might be something complex like SHA256, which for ZKP, would require complex circuit designs). She needs to prove that she holds this solution without exposing X – it is here we see the specific role that each cryptosystem, ZKP and FHE:
To prove this, Alice can directly use ZKP. The verifier needs to validate the provided zk_proof.
Alternatively, Alice can generate a pair of public and private keys, and encrypt X using her private key (also providing a simple zk_proof). The verifier then conducts a homomorphic encryption operation on f(x) using the public key, and finally determines whether the result is zero.
As can be seen, in different scenarios, using homomorphic encryption can achieve results similar to those obtained through ZKP. (In this example, there might still be a need for slight coordination with ZKP).

However, compared to extensive applications used by ZK, the progress of FHE applications has not been substantial. The reasons are as follows:

The computations of FHE are more cumbersome compared to zk's verification.
The actual benefits of FHE are yet to manifest profoundly.
The technology and ecosystem are still in their infancy.

On the other hand, FHE and ZKP are not identical technical solutions. FHE emphasizes more on data privacy. A host of potential applications can be executed under the FHE framework.

A. (Order Book/AMM) based Dark Market: For DeFi projects, transaction privacy is essential, and privacy encryption offers the following benefits:

To prevent sandwich attacks or additional MEV
To deter tracking the flow of funds
To protect the privacy of user assets.

B. Privacy auctions and VRF generation:

To effectively counteract the advantage of latecomers

C. AI-based encrypted sharing system:

To protect users' training data
The centerpiece of Multi-Party Computation (MPC)

It is foreseeable that in the future field of encrypted computations, FHE will undoubtedly have more crucial application scenarios.
Our ultimate goal is to provide a Fully Homomorphic Encryption (FHE) solution for the RISC-V instruction set, similar to the zkVM SDK. This stands as our future work and objective.

Problem

One of our core ideas revolves around endowing wasm contract languages (like ink!), represented by Polkadot, or the general wasm language instruction set, with FHE capabilities. The FHE technology ecosystem is still in its early stages with many fundamental toolkits yet to be fully constructed. Building a wasm-based FHE solution would be immensely beneficial to the bloom Polkadot ecosystem.

Proposal

We will wrap the bytecode file compiled for different basic instruction sets with Fully Homomorphic Encryption (FHE).

Mainly, there are two parts to be implemented:
First, for the setup phase, a simple SDK can be provided to the key exchange parties to share the threshold-key-switch. Here we use a solution similar to Threshold-TFHE.

A trustworthy third party generates a pair of public and private keys and derives a shared secret key (Shamir) from the private key.
The public key is broadcasted to the entire network, and the private key is destroyed. The derived shared private key is then given to different parties.
After obtaining the public key, the user encrypts the input data and compiles the contract into a .wasm file and inputs it into FHE-Wasm.
Fhe-wasm then calculates the encrypted output based on the .wasm file and encrypted input.
Different parties use the threshold protocol to decrypt the encrypted output result and sign and broadcast it.

The workflow is illustrated as follow:

After the setup phase, we implement homomorphic encryption based on the wasm instruction set. We only perform homomorphic encryption on value types, and the compiler needs to be modified for reference types. We will later release a corresponding SDK for that.
From the flow chart, our inputs include:

Public key (pk)
Specified inputs (can be defined as function input variables)

In terms of type handling,

Value types: bool, u{8,16,32,64}, i{8,16,32,64}. For 128 bits, we will concatenate two 64-bit integers for the carry bit later on.
In wasm, bool is calculated as i32.
Array types: String (array of u8), tuples, and arrays.

For base instructions:

All constants will be encrypted via the public key (pk) (https://docs.zama.ai/tfhe-rs/get-started/operations).
Here we only list the instruction set that needs additional modification. Others, like the loop instruction, do not require modification.

A. Arithmetic Instruction
As the wasm instruction set only deals with 32-bit or 64-bit integer scenarios, we consider the following instruction set (where xx replaces 32 or 64).

B. Compare Instructions：

C. Condition Flow

D. Load And Store Instructions

For address operation, we will perform actions in plain text.
We will maintain a special table corresponding to memory storage i32/i64, mapping the encrypted array storage.

Our solution is not to implement the FHE solution through the blockchain or contract (for such a solution, the complexity required for a general solution is too high). We start with the already compiled bytecode, and recompile different instruction types into FHE-based wasm instructions. This solution is more achievable (similar to the approach used in zk-wasm). One of the advantages of this solution is that it doesn't require modifying the original code (for example, FHEVM needs to change the variable type like uint->euint), but only needs to set its instruction entry as (fhe_main).

Moreover, we currently do not support complicated wasm programs (because this involves privacy calculation of memory data storage addresses, which is a very interesting research direction) or external contract calls.

Available solutions

FHE projects have been heating up over the past two years. One such initiative comes from the Zama company that built the FHEVM project (https://www.zama.ai/fhevm) based on tfhe-rs. Their approach concentrates on handling the instruction set of the Ethereum Virtual Machine (EVM). Compared to EVM, the instruction set involved in wasm is more universal, requiring different optimizations for multiple source languages.

Another similar project is Fhenix, which has raised over 15 million dollars. They run an FHE-based co-processor through Eigenlayer's AVS approach. This implementation enables key sharing and Multi-Party Computation (MPC), which in turn allow for FHE-based Rollup (https://www.fhenix.io/). However, unlike Fhenix, our focus is more on the use of FHE at the compiler layer, rather than the underlying technical layer.

We have studied Polkadot's approach, which includes some solutions based on Trusted Execution Environment (TEE), but there is currently no implemented framework for FHE. The reason we propose an FHE solution based on wasm now is that the development of FHE has gradually evolved from a theoretical implementation a few years ago to a practical solution that can be applied today.

Scope of work

We are a group of 4 Ph.D researchers and developers from different parts of the globe (San Francisco, Vancouver, Toronto and Shanghai) with a strong background in ZK and FHE, and have been involved in various ZK and THE-related projects.

Our main objectives include:
A. An FHE-WASM module that accepts:

The compiled .wasm file, the public key 'pk', and the specified input data as inputs.
The output is the encrypted output data.
This module operates in a Docker format and extends as a pallet.

B. A key-sharing solution

A stand-alone Docker operating as a trusted third party distributing public and private keys.
The module sends the shared secrets to N parties.
These parties can then decrypt the output result through threshold decryption.

We use Rust as our programming language.

Milestones

A. Preparation

Research
Threshold shared key protocol
Novel approach for FHE
Detail plan design
Documentation

B. Threshold key sharing protocol

pk&sk generation
Zk for Malicious Protection
Key Storage

C. FHE-Wasm

Instructions:
Numeric Instructions
Conventions
Vector Instructions (Array)
Control Flow
Comparison
Load & Store
Memory-related handling
Adapt for Ink!
Pallet

D. Output phase or actual work phase:

SDK&API
Testing

E. Closing phase:

Document Explanation
Submitting research to Journalist & Conference
Packaging with Docker
Summary report

Milestone 1. – Preparation

Milestone 2. – Threshold key sharing protocol

Milestone 3. – FHE-Wasm

Milestone 4. – Closing phase

Timeline & Budget

Payment condition

Proponent: FHEWASM Team
DOT address: 155kyRnu8M2GNrB39p3y2jcXrzLys9yFWBwCgEZQTJA7KoM9
Requested allocation: $189,750 (33,884 DOT)
Governance referenda origin call: (provide the call origin: small spender, small tip,...)

Sources:
1 Income tax tariff levels/calculation formulae for tax citizens residing in North America, Income tax rates for the year 2024.
2 DOT/USD EMA30 source: https://polkadot.subscan.io/tools/charts?type=price

Key deliverables

We will deliver all the results, summary, reports of the research and the development of this project, in the below methods.

Documents
Github Repo
SDK & API
Reporting
Papers

Objectives/Success criteria

Our ultimate goal is to realise a project comparable to FHEVM, and implementing FHE-Wasm is just our first step. This project aims to introduce FHE enablement and eventually empower more privacy-preserved data, operation and the application. Hence a few reasonable KPIs and numbers will be
Github start - Our benchmark project FHEVM has 332 github stars (2024.6.18), and we aim to have the same number of acknowledgements and the popularity.
SDK installation or API calling - We aim to productize the FHE-wasm and we anticipate dApps in the Polkadot ecosystem to install or call this functionality.

Known constraints
No.

Reporting

We'll be submitting the comprehensive status reports by milestones. At the same time we will be actively communicating and interacting with the Polkadot community via github, Element, Polka Assembly and email. If you want to have collaboration with us on the research and the development of FHE technology, feel free to reach us at shiotoli@gmail.com or team.fhewasm@gmail.com

The Communication strategy
Team member:

Shiotoli
Mike Rust

Email:

Polkassebly post: https://polkadot.polkassembly.io/post/2366
Element: TBD

Team
We are a group of 4 Ph.D researchers and developers from different parts of the globe (San Francisco, Vancouver, Toronto and HongKong) with a strong background in ZK and FHE, and have been involved in various ZK and THE-related projects.

Kusama/Polkadot reputation

Though we have rich knowledge in Substrate and Polkadot technology in general, we are new to the Polkadot/Kusama open treasury and the grant program. We plan to use this project to establish our reputation in the Polkadot ecosystem.
Why Polkadot?

We have rich experience with Polkadot/Substrate and, within the context of an existing Fully Homomorphic Encryption Virtual Machine (FHEVM), implementing a WASM-based Fully Homomorphic Encryption instruction set is a significant innovation.