# Private Proof Delegation

---

## Authors

- Nam Ngo
- Takamichi

---

## Introduction

### Problem
<!-- Commit-and-prove technique is a basic technique where a client commits to a secret value and later proves that the committed value satisfies some condition is an important technique in maintaining the client's privacy when interacting with some application/service, e.g. one can commit to their birthdate (with an authority's signature on the commitment) and prove that they are above 18, i.e. year(todate - birthdate) >= 18, to buy alcoholic drink using ZKP. -->

Private Proof Delegation (PPD) involes the generation of a Zero-Knowledge Proof (ZKP) in a delegating manner, i.e. a client interacts with a server or a set of servers and together they generate a ZKP that testifies the correctness of a chosen statement by the client (with the private witness held by the client) that is (1) publicly verifiable by any party not participating in the proof generation procedure, and (2) the client will still withhold the secrecy of their witness.


Such a service is particularly useful when the client is a weak device, such as a mobile device, with limited/constrained resource, especially in terms of RAM (4-8GB), while the ZK-circuit is not small and thus generating the ZKP will either (1) take a very long time (affecting battery life) or (2) sometime impossible (out of memory, for example, Halo2 RSA signature verification circuit requires 5GB of memory for single signature verification. It crashes iPhone15 Pro for its memory constraints according to [this](https://zkmopro.org/docs/performance#halo)). Another (not always present) issue is the size of the Common Reference String that is sometimes necessary for ZKP generation may not reasonably fit into such a weak device (a.k.a. the setup parameters that needs to be downloaded and stored at the device, which can be tens of GBs depending on the supported circuit size). The size of the ZKP itself can also cause problems when considering the bandwidth of the device.

The weak client context is more and more relevant in practice: (1) we are seeing a rise in the demand of things a ZK-Circuit needs to prove inside (especially crypto-ops inside ZK-Circuit, e.g. SHA hashing, RSA or ECDSA Signature Verification, zk-SNARK Verification); (2) Not only that, but as the world itself, users are largely in the mobile scene rather than in the desktop one. It is where they generate the most amount of data as well as their to-go device for most of the things. Therefore, client-side-proving has been an area whose requirements have grown exponentially lately.

#### Direct client-side-proving

The first non-trivial solution 0 is to implement the best proving-schemes to-date. (STARK, GKR, PLONK, etc.) and try to accommodate them to commodity-level mobile hardware (e.g., mobile-native proving). So far, benchmarks show that RAM is a large issue on that front, and there are lots of tradeoffs like bandwidth (when we have big trusted setups).

Certainly more research effort can be poured into designing ZKP schemes that are more suitable for client-side-proving, yet, these fast and lightweight proving schemes (also with streaming circuit capability for RAM accomodation) so far are seeing tradeoff in terms of proof size, e.g. STARK or VOLE-in-the-Head yields less prover cost but the proof size is polylog or linear to the circuit size. One further (engineering) work-arround for this is to send the proof to a powerful server to ask it to wrap the proof with a SNARK for succinctness (as Polygon is doing with their zk-EVM proof, where STARK proofs are wrapped with FFlonk proof).

Another engineering approaches such as breaking down a big circuit into smaller ones and producing many small proofs instead of a gigantic one can definitely fit the proof generation into the memory constraint but at the cost of more computation (where consistency checks of common commitments have to be done to link the proofs), hence yielding longer proof generation time.

#### Delegated-proving
While more research and engineering effort in solution 0 can help to directly achieve client-side-proving (and of independent research interest itself), we are more interested in delegated-proving with PPD which works around the hardware constraints and aims to answer the following question:
:::info
**What would happen if we could privately delegate our proof generation without losing privacy?**.
:::
Furthermore, advances in solution 0 can always be leveraged to further improve PPD.

This is the core idea behind this team's work. The delegation of the proving to a server which has the hardware capabilities to execute the generation.

### Solutions

We summarize in the Table below some possible solutions.

| Sol. | Description | Pros | Cons |
| -------- | -------- | -------- | -------- |
| 1 | Trusted Owned Server | Simple to implement, just buy it. | Cost for security hardening and maintaining |
| 2 | Outsourced TEE Server | Simple to implement, can share with others | Trust TEE vendor and server host |
| 3 | Co-SNARK | Efficient, client only needs to secret-share witness | Trust at least one co-SNARK server |
| 4 | Co-SNARK + 1-owned-server | Efficient, client only needs to secret-share witness | Cost for security hardening and maintaining (as in Sol 1) |
| 5 | Outsourced FHE Server | Client only needs to encrypt and decrypt | Inefficient or impossible |

The first trivial solution 1 is to outsource the ZKP generation in clear to a trusted server (e.g. where the client sends private witness for proof generation on a server owned by the client itself), but this could incur cost on server maintenance, hence not always a reasonable solution. One could also rely on a proof generation service (solution 2) that runs on trusted hardware (such as TEE, where client can send encrypted witness that is only decryptable by the TEE, where ZKP generation will be done inside the TEE), but it is unclear how secure trusted hardware currently is (which depends on many factors such as vendor, verifiable hardware log, etc. which is another field of research itself), hence it is not suitable if the client wants absolute certainty about their privacy.


A somewhat better solution 3 is to thresholdize/distribute the proof generation service from one server into several ones using collaborative ZKP (where the client will secret share their private witness to a set of servers who will run a collaborative protocol for proof generation). In this case, instead of trusting a single server, the client only needs to trust that at least one among the servers is honest. This solution 3 is better than the first solution 1 in terms of maintenance cost, yet, the necessary trust assumption (that the servers will not reconstruct the secret-shared witness) may not always hold and is actually dynamic over time, especially when there may have incentives involved (i.e. when the value the proving service obtains upon the violation of client's privacy, even when there is a penalty of doing so, significantly exceeds the reputation damage and the penalty, e.g. voting for president). One may consider solution 4 where the device itself plays the role of one of the servers hence absolutely guaranteeing the privacy of the witness and the client does not have to maintain a server. However, this solution is circular to the problem because the device is weak and cannot replace a server in solution 3.


Fully-Homomorphic-Encryption (FHE), the most recent holy grail of programmable cryptography, is a prominent solution 5 to the PPD problem without all the issues of the solutions above (especially the trust assumption). Yet, its concrete cost, even with recent significant advances in efficiency, is still of susceptibility when applying to PPD, especially the FHE cost on the server and the necessary communication cost between the client and the server when they have to send FHE ciphertexts back and forth.


### Goals

#### Long term
The long term goal of the team (the vision) is to come up with breakthrough protocols and/or primitives that allow us to perform practical ZKP-delegation to a server without any privacy loss.

There are some "extra/side/intermediate" goals that come with this:
- The client's device should perform the minimal amout of computation possible. Meaning the server is largely who performs the computation of the proof.
:::warning
But within this scenario, is important to highlight that the client's device needs to participate within the protocol such that without it, the server can't do everything (to retain trust)

Think of it as a way to retain trust within the entire protocol/process.
:::
- The protocol should incur on the minimal amount of communication complexity.
Notice that mobile devices specifically are specially constrained on what bandwidth refers (at least in a lot of countries). Sending stuff through the wire is also slow. So we want to avoid it as much as possible.
- The server can't turn malicious and betray the client and obtain any knowledge of the private witness.
- Support (ideally as many as possible) but at least a well-known proving scheme. Priorities would be:
- Starks
- Plonk
- Groth16

#### This Project (Feb-June 2025)
The short term goal of the team (this project) is two fold:
- Systematization of Knowledge of PPD
- Make an official case for delegated proving by understanding the baseline comparisons in terms of computation/communication/storage cost scaling with ZK-circuit size:
- Solution 0, namely direct proving at client, especially when proving become impossible due to hard cap on resource such as RAM
- Solution 2, namely delegating proof generation to a TEE server not owned by the client
> While, as one of the today's programmable privacy preserving techs, TEE's security assyumption is not desirable, our application of proof generation has public verifiability. Hence it halven the TEE's weakness in our case. Additionally we would like to take this chance to understand better TEE's performance in proving delegation and also build in house (PSE's) knowlegde (if not some degree of expertise) of TEE.
- Solution 3, namely delegating proof generation to a set of servers using collaborative ZKP
- Understand and categorize algorithmic development of PPD that aims to efficiently compute ZKP or its bottleneck such as FHE-FFT (computing FFT in FHE), FHE-MSM (computing MSM using FHE), Random-to-fixed-MSM (pre-generate a random MSM and later use it to quickly achieve a fixed MSM), designated verifier ZKP in FHE combined with Proof of Decryption, FHE-hash, or switching FHE schemes for efficiency in various parts of the proof generation, or some form of client-assistance in FHE-crypto-ops (e.g. client can decrypt and hash), FHE- or delegared-folding, etc.
- Conduct quick and dirty experiments on existing algorithms as small trials and errors on low-hanging-fruit tweaks to test for feasibility
- A summary of feasible solutions (efficiency and compatibility of existing PPDs and ZKPs) and future directions of PPD
- Dissemination of Knowledge to Research Community
- All *meaningful* understanding and experiments will be documented, released to the public periodically
- There will be sharing sessions (such as at a conference) that will provide the community with a better chance to catchup and join this field and therefore this can become a continuing community effort

---

## Objectives

*Objectives are time-limited, measurable actions with tangible outcomes that help push progress toward the broader goal.*

### **Core objectives**
- Understand and categorize algorithmic development of PPD
- Understand the baseline comparisons in terms of computation/communication/storage cost scaling with ZK-circuit size
- A summary of feasible solutions (efficiency and compatibility of existing PPDs and ZKPs) and future directions of PPD
- Host sharing sessions and community calls

### **Secondary Objectives**

- Feasibility of some quick tweaks in SOTA
- Feasibility of solution 0-b where lightweight ZKP such as VOLEitH can be combined with a SNARK wrapper
- Feasibility of solution 4-b where we combine TEE + co-SNARK
- Find out meaningful circuit size of client-side-proving when interacting with mobile/client side prover project

---

## **Scope**

### **Inclusions**

- Understand and categorize the most prominent ones among the PPD protocols.
- Understand the efficiency and compatibility of existing prominent PPDs and ZKPs
- Create docs and content on all the explorations done. Independently on whether they reached a good outcome or not. Share these and make visible all the work that has been done and all things and ideas that have been worked on and explored.

### **Exclusions**

- *Note what is explicitly not included to manage expectations.*
- Production grade or generically usable implementation of the experiments

---

## **Milestones**
### Milestone 1: Benchmark performance of alternative approaches

#### Milestone description
The first milestone (Feb-Apr 2025) focuses on collecting baselin benchmarks of three different approaches which we can use to evaluate the performance, security and requirements of our newly proposed protocol in the later milestones.
The protocols we plan to evaluate at this milestone are, delegated prover in trusted execution environment(TEE), collaborative zkSNARKs prover, and mobile prover using mopro. For the TEE prover, we need to implement the poc protocol. For the second and third ones, we will collect the benchmarking number by utilizing the existing implementation as much as possible to avoid duplicated work with the other teams.

#### Milestone 1-1: Implement and benchmark delegated prover for single TEE instance
In this sub milestone, we will implement TEE based delegated prover soley for benchmarking purpose. We take benchmark and document the result in the public page. Throughout this milestone, we are expecting to getting familiar with recent TEE spectrum in the cryptography field and therefore contribute to PSE by providing the knowledge of TEE which we think PSE lacks.
The TEE implementation requires a single TEE instance either on hardware (e.g. [Intel SGX](https://www.intel.com/content/www/us/en/products/docs/accelerator-engines/software-guard-extensions.html), [Arm trustZONE](https://www.arm.com/technologies/trustzone-for-cortex-m)) or on the cloud service provider (e.g. [AWS Nitro](https://aws.amazon.com/ec2/nitro/nitro-enclaves/?nc1=h_ls), [GCP's confidential computing platform](https://cloud.google.com/security/products/confidential-computing?hl=en)).

**Steps**
1. Design the architecture of TEE based delegated prover and decide the specific hardware/clodu requirements.
2. Implement the TEE based delegated prover.
3. Design and take benchmark.

**Deliverables**
- Benchmark software implementation
- Design doc of the benchmark and report of its result
- Documentation of the gained knowledge of TEE

#### Milestone 1-2: Collect/benchmark collaborative SNARKs prover
In this sub milestone, we collect the benchmark number for collaborative zkSNARKs prover. We plan to use the existing implementation of coSNARKs but not reluctant to implement or modify some part of them if necessary. The same circuit has to be selected with the other two benchmarks in this milestone to meaningfully compare and analyze the result.

**Deliverables**
- Design doc of the benchmark and report of its result
- (If needed) Benchmark software implementation

#### Milestone 1-3: Collect/benchmark direct SNARK prover
In this sub milestone, we collect the benchmark number for direct prover using mopro. We plan to use the mopro to benchmark direct prover on mobile. The same circuit has to be selected with the other two benchmarks in this milestone to meaningfully compare and analyze the result. We intend to understand and analyze the limitation of the most recent effort of mobile proving so that we can evaluate our approach by meaningfully compare with their performance, limitation and requirements.

**Deliverables**
- Design doc of the benchmark and report of its result
- (If needed) Benchmark software implementation

#### Final deliverable
As a final deliverable of the first milestone, we put together all the benchmark result as one document.

### Milestone 2: Literature Review and Knowledge Dissemination

#### Milestone Description

The second milestone (April-June 2025) focuses on building a strong foundational understanding of the research landscape in areas directly relevant to private proof delegation using fully homomorphic encryption (FHE). This involves an extensive literature review to survey state-of-the-art techniques and concepts in the following domains, with a specific focus on topics most relevant to private proof delegation:

- **Fully Homomorphic Encryption (FHE)**: Investigating state-of-the-art FHE schemes and optimization techniques to identify those that can efficiently support zero-knowledge proof (ZKP) generation. The goal is to determine if specific FHE schemes or optimizations are particularly well-suited for cryptographic operations within FHE, such as elliptic curve (EC) operations, fast Fourier transforms (FFT), or hashing, which serve as base cryptographic primitives for zero-knowledge proof generation.
- **zkSNARKs/zkSTARKs**: Reviewing papers on zkSNARKs/zkSTARKs, with a focus on their suitability for delegated proof generation. Particular attention will be given to the diverse features of zkSNARKs/STARKs, such as their base cryptographic primitives and base fields, as these differences can lead to significant trade-offs when running within FHE environments.
- **Outsourced zero-knowledge proof systems and private zk proof delegation**: Reviewing methodologies and frameworks specifically well-suited for the delegated proof generation without compromising trust assumption.
- **Baseline comparisons for Delegated-Proving**: Benchmarking the other techniques including direct proving, co-SNARKs, and TEE based proving to get the baseline comparison target for new protocol.

The insights gained from this literature review will be systematically documented and shared with the internal/external community and the larger ecosystem, enabling broader awareness of our work and facilitating its accessibility to those interested in the field, thereby contributing to collective knowledge and fostering collaboration.

#### Reasoning for the Milestone

Understanding the existing body of work is critical to identify gaps where this research can contribute meaningfully and to avoid redundant efforts. By thoroughly reviewing relevant papers, we aim to:

- Establish a strong foundation for identifying the most suitable FHE and ZKP protocols that align with our goal of private proof delegation without compromising trust assumption.
- Learn from and build upon state-of-the-art research to pinpoint protocols with the highest potential.
- Identify gaps and challenges in current approaches to ensure meaningful contributions to the field.
- Identify the performance/resource requirements target numbers for new protocol.
- Continuously engage with the community to gather feedback and insights on our findings and methodology.

This milestone ensures the research is grounded in existing work while fostering collaboration and knowledge sharing within the broader community.

#### Deliverables

The following deliverables will mark the completion of this milestone:

**Final Report of the investigation results**

- Create a list of candidates protocols which are the most prominent as PPD protocol.
- Discuss the feasibility, challenges, and trade-offs of performance, security and other relevant points between the candidates protocols.
- Benchmarking direct proving, TEE based proof generation and co-SNARKs to understand the baseline numbers for our approach.

**Insights Documentation and Analytical Overview:**

- A detailed document summarizing insights from the reviewed papers, categorized by their relevance to the project goals.
- Key findings, methodologies, and potential challenges in adapting the reviewed techniques.
- A comparative analysis of existing approaches, highlighting strengths, weaknesses, and areas for improvement.
- The documentation will be published on the community forum (ethresearch), our blog, or GitHub to ensure accessibility and engagement with the larger ecosystem.

**Knowledge Dissemination:**

- Hosting one or more community calls to present the project's objectives and gather feedback on our findings.
- Sharing updates and findings through social media, newsletters to gain community traction.

### **Subsequent Milestones**
We imagine that after the above milestone is completed successfully, we have clear view of what protocol best fits for PPD as of now. In the subsequent milestones, we will be designing and implementing the best protocol to demonstrate the feasibility, performance and security of the protocol. The timeline of these subsequents milestones heavily depends on the protocol therefore we don't have a clear number. We're assuming roughly 3-6months to implement the first prototype verion of it.

---

## **Why Now?**
The timing for this research project is critically aligned with the current ecosystem's urgent demand for innovative solutions. Users are increasingly seeking ways to enhance client-side proving capabilities. Concrete examples, including World ID, Anon Aadhaar, Open Passport, Myna Wallet, and FreedomTool which are highlighted in [mopro's report](https://zkmopro.org/blog#the-rise-of-new-zk-mobile-apps) showcases the rise of zero-knowledge mobile applications, further reinforcing the necessity of acting now to bring these real world client-side zk application more feature rich and practical on mobile. Current efforts primarily focus on WASM-based prover implementations and mobile native prover implementation, which are functional for limited use-cases (which is not functional for e.g. zkEmail) for now and are unlikely to sustain their relevance over the next decade, particularly as the technology landscape evolves to demand proving RISCV VM traces within mobile devices. Additionally, the surge in interest and resources dedicated to Fully Homomorphic Encryption (FHE) underscores the growing importance and timeliness of addressing these advancements.

## **Why PSE?**

PSE is in a particularly good position to do this.
- First, this is a kind of problem that is really expensive and possibly unfruitful for companies to tackle (where most of them look into low-hanging-fruits, e.g. TACEO, focus on co-SNARK, or other might look more into TEE-based solutions). But that could be a breakthrough if achieved (efficient PPD while completely removing trust assumption on proof delegation). Hence is a position where PSE could be really helpful.
- Some academic attempts on FHE-based PPD has been conducted but not so reachable by the wide audience
- We also have good in-house expertise when it comes to MPC and FHE. Which can definitely be helpful in order to kickstart this kind of work.

---

## **Resources and Team Structure**

### **Team Members**

- Nam Ngo -> 100% FT
- Takamichi -> 100% FT
- Wanseob -> 100% FT

### **External Collaboration**

We kick started this project during Devcon 7 with TACEO and Ying Tong, yet, this project should be relevant and hence at some point during the project we should conduct (either formal or informal) collaboration with other players in this field:
- Mopro, mobile proving software
- TACEO, who is an expert on MPC
- Ying Tong, who cares about generating proof on client
- Cursive, who has been doing privacy preserving consumer apps
- 0xPARC, who is doing the POD framework, potentially moving to mobile
- Gauss Lab, who is working on cutting-edge MP-FHE

### **Resource Requirements**

- The team aims to share major results at zkSummit
- co-working of 1~2 weeks at some point at the climax of the project

---

## **Evaluation Criteria (Optional)**

### **Success Metrics**

- *Define measurable outcomes (e.g., performance benchmarks)*
- Identify the gap from the best protocol to the baseline comparison and define primitive performance requirement
- Defined future research direction and community continuing effort

---

## **Appendices (Optional)**

- *Include detailed information or references:*
- Mopro's example mobile ZK-circuit: https://zkmopro.org/blog/#the-rise-of-new-zk-mobile-apps
- Mopro's client side performance: https://benchmark-update.mopro.pages.dev/docs/performance/
- Carlos's note on client-side-proving (discussed during Precon): https://hackmd.io/@liangcc/Syd90obkJg/%2F%40CPerezz%2FBk_W__RlJg#Towards-practical-Client-side-proving
- Some preliminary meeting notes on PPD (after Devcon 7): https://hackmd.io/vbNeFfZcSbOQ-RqkNiBKcQ
- Takamichi's notes on delegating EC operations to HE: https://hackmd.io/@tkmct/HyMZGbu4Jg
- TACEO's experiment on FHE-FFT (Dec 2024): https://blog.taceo.io/mhega/ (code: https://github.com/TaceoLabs/HElib-bigint-rs/tree/main)
- Wanseob's client-aided FHE-FFT idea (Aug 2024): https://hackmd.io/@wanseob-ethorg/H1tFIdaYC

---

## **References**

- *Include references or links to foundational material or similar projects.*
- co-SNARK: https://www.usenix.org/system/files/sec23fall-prepub-492-chiesa.pdf
- FHE-MSM: https://deneuville.github.io/files/SPC2018.pdf
- Similar pre-computation technique from Pallier encryption applicable to MSM: https://eprint.iacr.org/2015/864.pdf
- FHE-EC: https://eprint.iacr.org/2018/073
- Hybrid-HE: https://eprint.iacr.org/2021/731.pdf, https://eprint.iacr.org/2024/791.pdf
- Blind SNARK generation: https://eprint.iacr.org/2023/1949.pdf (designated verifier), https://eprint.iacr.org/2024/1684.pdf (desgnated verifier + proof of decryption)
- CRT-Boostrapping for FHE: https://eprint.iacr.org/2024/1623.pdf
- Leveled-Functional-FHE: https://eprint.iacr.org/2025/022
- schmivitz: A library for zero-knowledge protocols using VOLE-in-the-head: https://github.com/GaloisInc/swanky/tree/dev/schmivitz

---