Computing the maximum ModExp input length

[hecmas]

TL;DR:
Theoretical Limit: Assuming a gas cost limit of $30M$ we have the following theoretical bounds:
$$\text{BLen} \leq 75894, \quad \text{MLen} \leq 75894, \quad \text{ELen} \leq 720M + 32,$$
but there are other things to consider (e.g., see the next comment).

Practical Limit: Assuming a maximum restriction of 2MB in memory size and that the input lengths should be balanced, i.e., that $x := \text{BLen} = \text{MLen} = \text{ELen}$, we have the following practical bounds:
$$\text{BLen}, \text{MLen}, \text{ELen} \leq 1818.$$

Use Case Limit: After taking a look at projects using the modexp precompiled, we have decided to restrict the length to:
$$\text{BLen}, \text{MLen}, \text{ELen} = 32,$$
being able to handle up to 8192-bit RSA exponentiations.

---

Introduction

This issue aims to obtain the maximum length of the inputs (base, modulus and exponent) for which we can compute the ModExp precompiled on top of. My reasoning is as follows.

Following the formulas in EIP-2565 that define the gast cost of the ModExp precompile, we have that:
$$\text{GC}(E,\text{Blen},\text{Elen},\text{Mlen}) := \max \left( 200, \left\lfloor \frac{\text{MC}(\text{Blen},\text{Mlen})·\text{IC}(\text{Elen},\text{E})}{3} \right\rfloor \right)$$
where:
$$\text{MC}(\text{Blen},\text{Mlen}) := \left\lceil \frac{\max(\text{BLen},\text{MLen})}{8} \right\rceil ^2,$$
and

1. $\text{IC}(\text{ELen},\text{E}) := 1$ if $\text{ELen} \leq 32$ and $\text{E} = 0$ or $\text{E} = 1$;
2. $\text{IC}(\text{ELen},\text{E}) := \log_2(\text{E})$ if $\text{ELen} \leq 32$ and $\text{E} \neq 0$; and
3. $\text{IC}(\text{ELen},\text{E}) := \log_2(\text{E} \pmod{2^{256}}) + 8·(\text{ELen} - 32)$ if $\text{ELen} > 32$.

Right now, in our zkEVM we have $\text{GC} \leq 30M$ and based on this limit we are going to compute the maximum positive integer that each $\text{BLen},\text{ELen},\text{MLen}$ can take. As we will see, theses maximums are reached on worst cases and/or edge cases scenarios.

Expanding the above formula for the gas (and assuming sufficiently large inputs), we can express the gas bound as $$\text{GC} \leq \text{MC}(\text{Blen},\text{Mlen})·\text{IC}(\text{Elen},\text{E}) \leq 90M.$$
and expanding we obtain:
$$\text{GC} \leq \left( \frac{\max(\text{BLen},\text{MLen})}{8} \right) ^2·\text{IC}(\text{Elen},\text{E}) \leq 90M \quad \Longrightarrow \quad \text{GC} \leq \max(\text{BLen},\text{MLen})^2·\text{IC}(\text{Elen},\text{E}) \leq 5760M.$$

BLen and MLen

Let's focus our attention to $\text{BLen}$. To obtain its maximum, we need $\text{IC}(\text{Elen},\text{E})$ to be as low as possible, so take $E$ equal to either $0$ or $1$ (which correspond to the two "trivial" cases for ModExp). In both cases we have $\text{IC}(\text{Elen},\text{E}) = 1$ and taking a sufficiently large $\text{BLen}$ we can conclude that $\text{BLen}^2 \leq 5760M$ and therefore $\text{BLen} \leq \sqrt{5760M} \approx 75894$. That is, we should be able to handle a base $B$ of at most $2372$ chunks of $256$ bits. The exact same reasoning works for $\text{MLen}$.

ELen

To obtain the maximum for $\text{ELen}$, we should set $\max(\text{BLen},\text{MLen})^2$ as low as possible and we can make it equal to $1$ by taking any (possibly non-trivial) base and modulus satisfying $\text{BLen} = \text{MLen} = 1$. Since $\text{ELen} > 32$ we can express the initial inequality as $\log_2(\text{E} \pmod{2^{256}}) + 8·(\text{ELen} - 32) \leq 5760M.$

Now, by taking $E$ to be a multiple of $2^{256}$ we make zero the first summand of the previous expression, leaving as with the inequality $8·(\text{ELen} - 32) \leq 5760M$ and therefore $\text{ELen} \leq 720M + 32$. This is a number that is represented with at most $22.500.001$ chunks of $256$ bits.

[hecmas]

@krlosMata pointed another practical limitation for the input lengths, so we have to adjust the computed lengths with this new restriction.

[hecmas]

After a meeting with @krlosMata and @laisolizq, we decided to add to additional restrictions to the maximum input length of the ModExp, i.e.:

1. We should consider that the current maximum memory that we can handle is 2MB, as pointed out by the previous comment.
2. We should also consider that the current maximum number of steps is $2^{23}$.

With these two new parameters in mind, we should put ourselves in the case where not only the maximum memory is "almost" reached (and never overflowed in the ModExp computation), but also where the maximum number of steps is "almost" reached (and, again, never overflowed). Finding the worst case scenario (in terms of input length) will give us the actual maximum input length that we can work with and that can be introduced as a possible transaction in the Polygon zkEVM.

[hecmas]

As a first approach, I only take into consideration the first restriction of the previous comment and assumed that the input lengths should be balanced, i.e., that $x := \text{BLen} = \text{MLen} = \text{ELen}$. With these in mind, taking into account all the memory I need to save to be able to run the ModExp (all the memory in each of the functions in array_lib plus the memory in the modexp itself), I obtained the following inequality of bytes:

$$1152 \cdot x + 1888 \leq 2.097.152$$

and therefore that $x = 1818$ (leaving us with some margin for storing other zkEVM-related variables).

---

The first assumption is valid due to the identification of specific inputs where none of the counters exceed their limits, yet a length of $1818$ is attained in at least one input:

1. B = [2:1818], E = [1], M = [2].
2. B = [2], E = [1], M = [2:1818].
3. B = [2], E = [1:1818], M = [2].

The second assumption is also valid because the three inputs are used indistinguishable in each of the functions in array_lib and therefore they must be all balanced.

[hecmas]

Use cases ModExp:

1. Chainlink VRF: They implemented the precompiled call here and they use it here for finding a square root modulo the 256-bit number 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F. This means, that the three the base, the exponent and the modulus are at most numbers of 256-bits. So $\text{BLen},\text{MLen},\text{ELen} \leq 1$.
2. ENS Protocol: They implemented the precompiled call here for verifying signatures made by some DNSSEC signing algorithms. In particular, they use the precompiled for RSASHA1 and RSASHA256 signature verification. Even tho they are implemented in general (i.e., you could call them with inputs of any size) the reality is that the RSA-based schemes are used with a key size of 2048 or 4096 bits (since these are big enough for security guarantees), implying that $\text{BLen},\text{MLen},\text{ELen} \leq 16$.

Other projects that we have been taking a look at using the modexp precompiled like VDF fall into one of the previous cases, so we finally decided to restrict the length of the modexp inputs to 32 to be able to handle all these cases and beyond.

[krlosMata]

implemented in https://github.com/0xPolygonHermez/zkevm-rom/releases/tag/v9.0.0-rc.2-fork.13