# NEBRA <> Axelar Analysis

## Introduction
In this article, we show that Axelar can save gas costs in its General Message Passing (GMP) protocol by using NEBRA's Universal Proof Aggregation (UPA) system. UPA allows on-chain protocols that use Groth16 proofs to save gas costs by recursively proving the validity of batches of Groth16 proofs and verifying a single aggregated proof on-chain.

NEBRA UPA has two options for users to submit the Groth16 proofs they wish to aggregate:
1. Submit the proofs via an on-chain transaction.
2. Submit the proofs to an off-chain RPC endpoint.

The main tradoff between the two options is that the first option save less gas costs for the end user, while providing stronger censorship-resistance properties.

In the rest of the article, we provide data and insights for the following four scenarios for Axelar's GMP protocol:

1. Gas costs without any changes.
2. Gas costs with ZKPs.
3. Gas costs with ZKPs + NEBRA (on-chain submissions).
4. Gas costs with ZKPs + NEBRA (off-chain submissions).

## Methodology
We focus on analyzing Axelar's`approveMessages` function (located [here](https://github.com/axelarnetwork/axelar-gmp-sdk-solidity/blob/v5.9.0/contracts/gateway/AxelarAmplifierGateway.sol)). At a high level, this function verifies that a batch of messages is signed by some threshold number of signers. It then marks these messages as approved in storage and emits a corresponding event. ZKPs cannot reduce the gas costs of storing data or emitting events, but can potentially help reduce the cost of signature verification.

We use the gas reporter tooling already available in the [`axelar-gmp-sdk-solidity` repo](https://github.com/axelarnetwork/axelar-gmp-sdk-solidity/) to get our gas data.

## Notation
- $m$ is the multisig threshold.
- $n$ is the number of signers in the multisig.
- The number of messages being signed is fixed to $10$ in our analysis. We explain why we don't vary this parameter later.
- $S$ is the submission size for NEBRA UPA protocol. It is the number of Groth16 proofs submitted by a user in a single transaction.

## Gas Costs Without Any Changes
There are three parameters which affects the gas cost of the `approveMessages` function:
- The number of messages being signed.
- $m$ - the threshold of the multisig.
- $n$ - the number of signers of the multisig.

### Number of Messages
Gas costs increase with the number of messages because we need to update storage and emit an event to mark each message as approved (see [here](https://github.com/axelarnetwork/axelar-gmp-sdk-solidity/blob/v5.9.0/contracts/gateway/BaseAmplifierGateway.sol#L193-L219)). Importantly, we note that using ZKPs for signature verification will not improve this cost - so we do not analyze it further. As such, we simply fix this value to $10$ for the rest of this article.

### Threshold
Empirically, increasing the multisig threshold by $1$ consistently increases the gas cost by about $6300$.

### Number of Signers
Empirically, increasing the number signers by $1$ consistently increases the gas cost by about $800$.

### Rough Analytical Formula for Gas Cost
The gast cost of `approveMessages` for $m = n = 1$ is `379648`. So an empirically-derived, analytical formula for the gas cost of `approvedMessages` is:

$$379648 + 6300 \cdot (m-1) + 800 \cdot (n-1)$$

Plugging in $m = 50, n = 100$, we get $767,548$. Running the gas reporter with the $m = 50, n = 100$, we get the gas cost as $767,922$, so our formula seems reasonablly accurate!

We use:
$$6300 \cdot m + 800 \cdot n$$
as an approximation for the gas cost associated validating signatures in `approveMessages`. The rest of the gas is due to writing to storage, emitting events, etc -- costs that exists whether or not Axelar incorporates ZKPs.

## Gas Costs with ZKPs

### First Pass Circuit Structure
- The circuit mimics the functionality of the [_validateSignatures](https://github.com/axelarnetwork/axelar-gmp-sdk-solidity/blob/main/contracts/governance/BaseWeightedMultisig.sol#L192) function.
- The `weightedSigners` and `signatures` are private witnesses to the circuit.
- `messageHash`, along with the `signersHash` (as defined [here](https://github.com/axelarnetwork/axelar-gmp-sdk-solidity/blob/main/contracts/governance/BaseWeightedMultisig.sol#L119)) are public inputs so that every ZKP is tied to a certain set of messages and signers. This means that:
- Messages cannot be mistakenly marked as approved on-chain.
- Non-current set of signers cannot be used to create a valid ZKP.

As per [this detailed analysis](https://xn--2-umb.com/22/groth16-tweaks/), gas cost of Groth16 verification on-chain is:

$$181,650 + p \cdot 6150 + 4096$$

where $p$ is the number of public inputs. Since `p = 2` in Axelar's case, we can estimate the gas cost for Groth16 verification as roughly $200,000$.

As stated in above section if we use $6300 \cdot m + 800 \cdot n$ as the approximate gas cost due to signature verification. For this to surpass $200,000$ we need relatively large numbers for $m$ and $n$. For instance, even for $m = 20, n = 50$ multisig $6300 \cdot 20 + 800 \cdot 50 = 166,000$, so directly verifying Groth16 proofs on-chain is not practical!

## Gas Costs with NEBRA UPA

### UPA with On-Chain Submissions
[On-chain submission gas cost](https://docs.nebra.one/developer-guide/gas-costs) for current mainnet deployment (where we aggregated batches of size `32`) is:

$$100000 / S + 50000$$

where $S$ is the number of Groth16 proofs submitted in a single transaction by the user. If we take `S = 16`, then the total cost comes out to about `56K`.

Recall that we use $6300 \cdot m + 800 \cdot n$ as the approximate gas cost due to signature verification in Axelar's current protocol. Then, for relatively small sizes of $m, n$ using NEBRA is practical, for instance when $m = 7, n = 15$, this value already reaches $53,000$. The savings only balloon for larger multisigs. For instance, when $m = 20, n = 50$, estimated savings will be $6300 * 20 + 800 * 50 - 56,000 = 110,000$.

### UPA with Off-Chain Submissions
[Estimated off-chain submissions gas cost](https://docs.nebra.one/developer-guide/gas-costs) for NEBRA UPA is $40,000$. This means that at even smaller multisigs Axelar will benefit. For instance, when $m = 5, n = 12$, Axelar's estimated cost wil surpass $40,000$. Of course at even larger multisig sizes savings will be higher. For instance, at $m = 20, n = 50$ estimated savings is $126,000$.

## Summary of Data
In the chart below, we show approximate gas costs for signature verification in Axelar's protocol when $m = 20, n = 50$.

| UPA Submission SIze | Axeler Gas Cost Now | Gas Cost (with ZKPs) | Gas Cost (with UPA On-Chain submissions) | Gas Cost (UPA Off-Chain submissions) |
| -------- | -------- | -------- | -------- |-----|
| $4$ | $166,000$ | $200,000$ | $75,000$ | $40,000$ |
| $8$|$166,000$ | $200,000$| $63,000$ | $40,000$
| $16$ |$166,000$ | $200,000$| $56,000$ | $40,000$
| $32$|$166,000$ | $200,000$| $53,000$ | $40,000$