zk-SNARK Trust Setup in Space Orbit

Over the week of ETHDenver, we saw two interesting trends related to zero-knowledge proofs.

  1. There were genuine interests in zk-applications from the developer community. Hackers are shifting focus from zk- L2 / Infra to specific zk applications, such as proof of location, proof of ownership, educational game, etc.
  2. DoraHacks team successfully ran a MACI (collusion-resistant) quadratic voting grant round (with a 1,000,000 SPORK token matching pool) within the ETHDenver community, for the first time. The MACI round was fan, and effectively distributed the matching pool to the 30 finalists based on votes from the SPORK community. All votes are private, and the results are verified by zero-knowledge proofs.

Privacy and scalability are the most important features zero-knowledge secured systems can offer. In governance systems, we value credibility. Normal quadratic funding grant rounds are often criticized because of various forms of collusion (e.g. relentless airdrop or straight bribery), which damages credibility of the system as a whole, and ultimately making the systems non-scalable. The ETHDenver MACI round had almost 0 dispute over the results and the whole process was obviously more credible to the community.

On a larger scale, zk powered infrastructures and applications are having more value at stake by day. The blockchains and layer-2 protocols are accumulating TVLs and applications are being developed on top of these infrastructures, forming a fast-growing ecosystem.

A large percentage of zk applications are based on zkSNARK, which requires pre-program trust setups. The further a zk application scales, the higher the trust setup security requires. In this article, let’s talk about the security assumptions of trust setup ceremonies, and explore how we can use space orbiting devices as isolated execution environments to securely compute the trust setup. A space trust setup solution might not only be able to become an alternative to current MPC-based ceremonies, but also support the coming space-native digital economy, which is not a sci-fi anymore because launching costs are rapidly reducing.

Trust Setup Ceremonies

Currently, the zk research space is advancing at a rapid speed. There is a significant amount of research and engineering efforts going on to build ZKPs with transparent parameter generation, which do not require trust setup (STARK, Bulletproof). On the other hand, there is intensive research being conducted in academia and the blockchain space to create general SNARKs (e.g. PLONK).

An useful illustration of the status quo (security assumption vs. proof size) of current zero knowledge proof algorithms, from “Understand PLONK” , also useful to read this article

The pain point of SNARKs is the need for trust setup. It is often annoying because the security of the whole scheme relies on trust setup. If the trust setup is not secure or it breaches, the SNARK can be compromised. However, given the succinctness, zkSNARKs are still and will remain highly important, because efficiency is a dominant factor when building zk infrastructures and applications. Therefore, as long as zkSNARK continues to be a top choice of zk applications, trust setup is important.

To protect the security of trust setup, we need to protect the random elements used to generate the common reference string (CRS), which contains the ProoferKey and VerifierKey. The random elements, on the other hand, are commonly referred to as the “toxic waste”. How the toxic waste can help create fake zkSNARK proofs can be found in this article.

There was an evolution of trust setup ceremonies, from the first version ZCash ceremony in 2016 to the Power of Tau ceremonies commonly used now. A Powers of Tau ceremony allows serial participation and verification, therefore it scales the number of participants. The DoraHacks MACI repo is based on MACI 1.0, which relies on Groth16 and a MMORPG type of trust setup ceremony. The ceremony breaks down into two stages – the perpetual power of tau ceremony, then another step converting the output (ptau) and the circuit into a relation-specific CRS using SnarkJS:

snarkjs groth16 setup circuit.r1cs final.ptau circuit.zkey

The complexity of trust setup normally relies on the complexity of the problem and security level required by the application. For example, for the ETHDenver MACI grant, the trust setup was performed in a simpler way – taking a ptau files for bn128 with the peraperPhase2 54 contributions and a beacon which includes 2**22 powers (can be used to generate zk-snark parameters for circuits with up to 2**22 constraints). Take the output together with the circuit, and create a Groth16 pkey file for each circuit with one contribution.

This is sufficient for an experimental round. However, if the value at stake is high, we then need a more secure ceremony and multiple contributions from stakeholders / communities to generate the final output. If the scale of the problem increases (e.g. a voting system supporting general election, or a MACI round distributing billion-dollar matching pool), then the output of the ptau file grows exponentially.

The assumption of Power of Tau Ceremony is that at least one from many participants is honest, and his/her computing hardware is secure. Generally, a good practice would be deleting the randomness after completing the ceremony. As the number of participants increases, the probability of a compromised final output is becoming negligible.

In practice, Powers of Tau ceremonies have the following limits. The ceremonies are often performed among a certain group of people, which has inherent demographic constraints. Then there’s another constraint – the ceremonies are generally time consuming, requiring coordination between a group of people during a fairly long period of time. There are proposals (e.g. optimistic pipelining) to improve efficiency, these limits still stay true.

Trust Setup in Space Orbit

The goal of trust setup is to make sure the random elements that generate a CRS are secure. There are two fundamental challenges to securely generate a CRS – (1) can we securely compute and store / destroy the random elements after a CRS is generated? And (2) can we prevent purposeful collusion among the involved people and devices?

Specifically, we are preventing the following attacks.

  1. Physical hack. Servers and computers can be physically hacked or intruded. This is actually happening quite often in the real world, and a very hard problem to solve on earth.
  2. Network intrusion. The communication is monitored by unexpected intruders.
  3. Collusion or leak of secret information on purpose. The person or party that generates CRS purposely leads information, because of bribery, collusion, or any other reasons.

To tackle these challenges, we can secure the hardware and software of computation, we can design mechanisms / MPC algorithms to reduce single point failures, and we can isolate the computation.

As the cost to launch payloads into space is lowering and will continuously be reduced, space isolation can help create a trusted execution environment (e.g. SpaceTEE). Now we think about an alternative trust setup process in space orbit, which does not require an MPC process to guarantee security.

The goal of the space trust setup is to create a totally isolated execution environment to compute the CRS and store the toxic waste.

An execution environment in space automatically avoids the first attack (physical hack), because it is (so far) difficult to physically access an object in a space orbit. Advanced military techniques might be developed to make it less costly to catch and access a satellite. However, as outlined in the SpaceTEE paper, there are multiple measures that we can take to monitor and prevent potential attacks in space:

  • The North American Aerospace Defence Command (NORAD) has a radar system that continuously monitors and predicts the trajectory of space objects.
  • There are various ways to add pre-launch physical protections. Once the satellite is physically accessed, some internal status (e.g. inertial moment) will change and will be able to be monitored.

Furthermore, we can definitely design mechanisms to protect the secure environment. One idea is that we can plant a self-destruction system into the satellite. If the satellite is caught, the self-destruction system is triggered, completely destroying the data within the satellite.

A simpler approach is to destroy the satellite immediately after the CRS is generated and transmitted. This is under the assumption that the satellite is not providing any more functionalities than creating the trust setup. A more general approach is to continuously monitor the inertial moment of the satellite. Once an unexpected change is found, the satellite automatically destroys itself. There are several ways a self-destroying component can be achieved, some of them have reasonable cost (Vanishing Programmable Resources, dissolving electronics, expanding polymer crusher, etc.).

If the CRS is generated in space, and the satellite is kept intact (not self-destroyed), the satellite can communicate with ground stations or other satellites. There might be scenarios where self-destruction cannot be considered. In some cases, self-destruction might endanger other payloads, or there are other functionalities we want the satellite to provide so that the satellite is maximally utilized. Then we need to secure the communication and ensure that the random elements (a.k.a. toxic wastes) are not transmitted out from the satellite electronics, as well as prevent malwares to steal information from the satellite hardware and leak the toxic waste.

To prevent malwares from accessing information, we can load the entire trust setup program into a hardware trusted execution environment (e.g. ARM TrustZone). The trust setup computation can be executed inside the trusted module, and the toxic waste should remain inside the trusted module indefinitely. There are pre-defined table of functions that can be called to access the trusted module (ARM TrustZone’s veneer table), so long as the functions are not accessing and leaking toxic waste data from the TrustZone, the toxic waste data remains secure. Then the CRS generated from the trust setup programs can be transferred via some function that is accessible on the veneer table.

Some remote cryptographic attestations will be required here to secure the system boot processes by creating a chain of trust. It is important to make sure that the system is booted correctly, the program in the trusted module is the intended program, and there are no unexpected functions from the veneer table that could release the data.

A last remaining problem is manufacturing / supply chain security. However, this is a universal problem for all trust setup methods, because if the device manufacturer is bad, we always end up in a bad situation. One way to protect the system from single-point failures is to randomly purchase multiple chips from multiple manufacturers by multiple undisclosed purchasers. Then randomly select one of the devices to integrate into the satellite to be launched.

If we implement all above correctly, we have physical isolation in space orbit, a trusted execution module protecting trust setup computation and random elements, remote attestation verifying the correctness of code and state of the module. When we have all of these features, collusion is automatically impossible, because the CRS is created without human involvement, and the data is physically not accessible.

Lastly, a recap of Powers of Tau Ceremony and Space Orbit Trust Setup over a few metrics:

[This paragraph is added on 9th June 2022] Currently, CryptoSat team is working with DoraHacks devs to deliver a proof-of-concept trust setup in space via its Crypto Satellites.