TLDR:

• On-chain FHE faces 5 areas of challenge, with Part 1 covering nascent FHE schemes/libraries/compilers, as well as secure threshold decryption. This article covers ZKPs, Data Availability optimization, and FHE hardware.

• FHE combined with ZK Proofs are extremely powerful, and advancements such as Verifiable FHE are moving this forward.

• On-chain FHE requires a high volume of encrypted data to be stored, requiring a secure, performant, and cost-efficient DA layer that supports FHE. While the solution is not yet here, the space is being actively researched and moving quickly.

• FHE hardware is 100x slower than regular hardware, and yet FHE Accelerators and optimized software are showing signs of speeding things up.

Introduction:
In Part 1 of this 2-part series, we covered how FHE is a revolutionary technology that is still emerging, and currently facing 5 major challenges:

1. Nascent FHE Schemes, Libraries, and Compilers: a need for FHE-specific technological advancements and a computing paradigm shift.

2. Secure Threshold Decryption: secure, permissionless, and low-latency decryption.

3. ZKPs for User Inputs + Computing Party: efficient confirmation of correct computation.

4. Data Availability Optimization: the need for a secure, performant, and cost-efficient DA layer for FHE.

5. FHE Hardware: optimized software/hardware and FHE Accelerator advancements.

Part 1 of this series covered both 1) and 2) above in-depth, and we recommend giving it a read.

This article will cover the three remaining challenges, and potential solutions to each.

Challenge: Implementing Zero-Knowledge Proofs for Verifiability

While FHE enables arbitrary computation over encrypted data, it cannot prove that something is correct without revealing the underlying information. This is where zero-knowledge proofs (ZKPs) excel, and combining both is useful in three ways:

1. Proof of Plaintext Structure: ZKPs can be used to demonstrate that the input plaintext is properly structured, which impacts the ciphertext (encrypted data) conforming to the encryption scheme. This cannot be done by the typical SNARK/STARK approaches common for ZK rollups because FHE’s lattice-based cryptography is post-quantum secure, and instead requires a proof system designed for lattice-based relations.

2. Proof of Plaintext Input: ZKPs can also prove that the plaintext is not only properly structured, but that it meets the application’s requirements. For example, I cannot send more funds than I have in my wallet. zk-SNARKs can be used here, but the challenging part is confirming that the input for this system is the same as the input for the plaintext structure system.

3. Proof of FHE Computation: ZKPs can be used to prove that computations are correct.

Solutions:
Each of the above 3 is in the midst of ongoing research providing promising results:

a. ZKPs of plaintext structure require a cost-efficient proof system for lattice-based relations, which is an area of ongoing research.

b. ZKPs of plaintext input are being advanced by firms such as Mind Network which have been integrating ZKPs to ensure zero-trust inputs, alongside the use of FHE. Sunscreen’s ZKP Compiler also shows promise here through the use of Bulletproofs, although they are not the most efficient proof system.

c. ZKPs of correct computation can be addressed via “Verifiable FHE” whereby a validator submits a ZKP to prove honest transaction execution. Assuming others can verify the ZKP was done correctly, only a single part is needed for execution. SherLOCKED is an example of an early prototype in this space, which offloads FHE computation to Risc0’s Bonsai zkVM and returns a ZKP.

Each area is advancing rapidly and we will be providing updates via our Twitter on the latest information. 

Challenge: Data Availability Optimization

On-chain FHE will result in high volumes of data encrypted in ciphertext format, which must be adequately stored without congesting the underlying blockchain.

The results in 2 problems:

a. Locating off-chain storage
b. Finding a secure, performant, cost-efficient DA layer that supports FHE

Solutions such as Celestia exist, but Celestia’s maximum data throughput is 1.4MB/second, while any form of FHE machine learning would require at least 6GB/second. 

Furthermore, the DA layer should have reasonable resource demands from node operators to allow for sufficient decentralization.

Solution:
We do not have the right solution for this, although we wish for a DA solution that is low latency, ultra-cheap, and highly reliable.

The final solution will likely support horizontal scalability, whereby additional nodes each store a fraction of data and more nodes therefore increase performance. EigenDA potentially addresses this but it is a bit premature to tell. The DA space is moving extremely fast and we believe that a team well-versed in lattice-based cryptography will present a new DA layer that’s optimized for FHE ciphertexts.

We are also considering building optimized storage slots for storing ciphertexts, as they follow a particular encoding scheme. In the end, we do not have the correct answer for this as of yet, but it is not extremely urgent and we are confident that progress in 2024 will make significant advancements here.

Challenge: Low-Performance FHE Hardware

Latency is a recurring challenge for FHE and this is no different when it comes to hardware.  FHE computations over encrypted data were 100,000x slower than over plaintext data, but newer encryption schemes and FHE hardware advancements mean that FHE computations are now only 100x slower.

The fundamental reason for this is that calculations involve complex polynomial computations and time-consuming ciphertext operations. It’s also harder to accelerate blockchain-based FHE compared to application-specific use cases (such as Machine Learning FHE) as it requires the ability to process more general computations versus a more niche set.

Solutions:
Improvements are being made on 3 fronts: 

a. FHE Hardware: FHE Accelerators are specialized hardware devices that enhance the performance of FHE computations by speeding up the complex mathematical operations involved. One example is the Fixed Point (FPT) accelerator that can exploit FHE’s inherent noise through the implementation of TFHE bootstrapping. Another example is BASALISC, an architecture family of hardware accelerators that use the cloud to accelerate FHE computations and is the first to implement the BGV scheme. 

b. Optimized Software: F1 and CraterLake are two FHE Accelerators that combine both hardware and software elements to increase performance, and others may follow suit in the future. Fully functional compilers will likely be developed, with this software capable of optimizing FHE programs dependent on the specific For HE scheme chosen.

c. Scaling Out: Currently, FHE hardware accelerators are focused on improving individual accelerators vertically, rather than connecting various ones horizontally. This could drastically improve performance and is comparable to proof generation with ZKPs, where multiple proofs can be generated in parallel. A challenge with this is data inflation: data size increases drastically during encryption and computation, making it harder to connect various FHE hardware accelerators. Therefore, a promising area of research will be to look into the networking infrastructure amongst FHE hardware accelerators.

Conclusion:
In this second part of our deep dive into the challenges and advancements surrounding on-chain FHE, we’ve explored three critical areas:

a. The integration of Zero-Knowledge Proofs (ZKPs) for
enhancing verifiability. 

b. Data Availability (DA) optimization for efficient storage of encrypted data. 

c. The development of specialized hardware to overcome the inherent latency issues in FHE computation.

Each challenge is seeing promising solutions arise, and it’s clear that the journey toward practical and efficient on-chain FHE is both challenging and exhilarating. The field is rapidly evolving, and the progress made so far is just the tip of the iceberg.

Stay tuned for more updates, and join the conversation with us on Twitter and Discord to stay at the forefront of these exciting developments in on-chain FHE.