Proof Bundling in EOSIO/Antelope Transactions

The Halo 2 proving system comes with a powerful feature called Recursive Proof Composition. It allows for multiple zero knowledge proofs of the same arithmetic circuit to be bundled together into a single proof bundle. This feature of Halo 2 can be exploited to scale private transactions on EOSIO/Antelope blockchains.

Groth16 versus Halo2

Some notes on performance: The currently widely adopted Groth16 proving system is heavily optimized in regards to verification time and proof size which is both small and even constant for any zk-SNARK independent of the complexity of the underlying arithmetic circuit. This means that Groth16 proof verification time scales linearly with the number of proofs to be verified.

With Halo2's recursive proof composition, however, the verification time of multiple zk-SNARKs bundled together scales logarithmically with the number of proofs. While a single proof verification in Halo2 is more expensive than in Groth16, the overall performance of Halo2 can significantly increase and even beat Groth16 in case of multiple proofs being bundled and verified together. This is even true for a single-threaded Halo2 verifier but in contrast to Groth16 the proof verification in Halo2 can even be performed multi-threaded.

For a more detailed explanation of the benefits of Halo2 checkout the Technical Explainer. For use cases of complex privacy transactions on EOSIO/Antelope containing multiple zk-SNARKs refer to the ZEOS Whitepaper pages 34 to 37.

Concept for EOSIO/Antelope Transactions

In order to exploit the recursive proof composition feature of Halo2 for EOSIO/Antelope transactions the following concept is introduced.

The Problem

The ZEOS privacy actions (aka ZActions) all depend on a tuple of zero knowledge proof and corresponding public inputs $({\pi }_{C_{zeos},\omega ,x},x)$ in order to be executed. Each zaction is then executed as a seperate EOSIO/Antelope action in which the corresponding proof is verified independently from all other ZActions of the same EOSIO/Antelope transaction. In order to take advantage of the recursive proof composition feature of Halo2, the proofs of all ZActions of the same EOSIO/Antelope transaction are bundled into a single proof bundle $\Pi$ which then depends on the set of public inputs $X$ of all ZActions in that particular transaction.

$${\Pi }_{C_{zeos},\Omega ,X}=\sum _{i=1}^{\mathsf{n}}{\pi }_{C_{zeos},{\omega }_i,x_i}$$

where:

• $\sum$ is the composition function to bundle multiple zero knowledge proofs
• $n$ is the number of ZActions to be executed
• $\Omega$ is the set of private inputs $({\omega }_1,{\omega }_2,...,{\omega }_n)$
• $X$ is the set of public inputs $(x_1,x_2,...,x_n)$

But if the proofs of all ZActions of an EOSIO/Antelope transaction were to be composed into a single proof bundle, there is also only one single EOSIO/Antelope action to verify this proof bundle and thus validates all subsequent ZActions. But if that is the case, then all subsequent ZActions need to be able to reference their public inputs from this one EOSIO/Antelope action that verifies the bundle.

After all, it can't be trusted that the user executes the subsequent ZActions with the same public inputs that were used to verify the proof bundle.

Since EOSIO/Antelope actions are executed independently from each other, there is no (direct) way, to enforce the execution of two independent EOSIO/Antelope actions with the same input parameters. To prevent fraudulent actions (like verifying the proof bundle using one set of public inputs $X$ but then execute the subsequent ZActions using a different set of public inputs $Y$) it needs to be guaranteed by the ZEOS smart contract that the proof bundle is verified with the very same public inputs that are used to execute the subsequent ZActions.

The following graphics illustrate the problem. The first picture shows a transaction execution without proof composition where each zaction verifies its own zero knowledge proof ${\pi }_i$ using the corresponding public inputs $x_i$.

The second picture shows the same transaction using proof composition where the first action verifies the zero knowledge proof bundle $\Pi$ using the valid set of public inputs $X$ but the subsequent ZActions are executed using a different, fraudulent set of public inputs $Y$. This way an attacker is able to defraud the system by executing invalid ZActions.

The Solution

It needs to be guaranteed that subsequent ZActions which are validated by the proof bundle are executed with the exact same public inputs as the proof bundle was verified with. In order to achieve this, the following concept is introduced.

The exec action

The ZEOS smart contract features an 'exec' action which takes a sequence of ZActions (i.e. a ztransaction) as parameter and executes them one by one. This EOSIO/Antelope action is only executable by the ZEOS smart contract itself, to ensure it is only executed if the proof bundle that validates the sequence of zactions is verified within the same transaction.

Third party smart contracts

As described in Private Deposits & Withdrawals all third party smart contracts which choose to implement private withdrawals depend on executing ZActions as EOSIO/Antelope inline actions. To be able to support those third party private withdrawal actions they need to follow certain design guidelines which make them look very similar to the exec action of the ZEOS smart contract:

• They take a sequence of ZActions as their first action parameter
• They are only executable by the ZEOS smart contract
• They need to be whitelisted by the ZEOS smart contract

The begin and step actions

Two more actions are introduced as part of the ZEOS smart contract:

• begin: This action takes a Halo 2 proof bundle and a sequence of packed EOSIO/Antelope actions. The packed actions within the sequence need to be whitelisted by the ZEOS smart contract, may contain a sequence of ZActions as their first action parameter and are ready to be executed, after the proof bundle has been verified. In addition to that the begin action takes a sequence of encrypted UTXO ciphertexts, $\mathsf{note}{\mathsf{s}}_{\mathsf{enc}}$, which is neglected here.
• step: Each 'step' action is a placeholder which executes exactly one of the packed EOSIO/Antelope actions from the sequence of actions passed to 'begin'. It is a wrapper that executes an EOSIO/Antelope action and, if applicable, the 'exec' action right afterwards with the sequence of ZActions which is serialized as the first parameter of the preceding EOSIO/Antelope action. The number of 'step' actions in the EOSIO/Antelop transaction must equal the number of EOSIO/Antelope actions in the sequence passed to 'begin'.

The following example is given to illustrate the concept: