# Verifier's cost for _input_ _processing_ in batch Testudo
## Cost of single-input Testudo

Let input be $x = (x_1, \dots, x_{L}$).
Let $\ell = \log{L}$:

$$\mathsf{io}_{\text{single}}(\vec{r}) = \sum_{b_1,\dots,b_{\ell}} x_{\vec{b}}\cdot\chi_{\vec{b}}(\vec{r})$$

where $|\vec{r}| = \ell$.

## Cost of batch Testudo for $K$ proofs on the *same* input

Let $\kappa = \log{K}$. The whole input is now the same $x$ concatenated $K$ times. However, the cost does not increase by a multiplicative factor in $K$.

$$\mathsf{io}_{\text{many}}(\vec{s},\vec{r}) = \sum_{a_1,\dots, a_\kappa, b_1,\dots,b_{\ell}} x_{\vec{a}||\vec{b}}\cdot\chi_{\vec{a}}(\vec{s})\cdot\chi_{\vec{b}}(\vec{r})$$

where $|\vec{s}| = \kappa$.

This becomes

$$\mathsf{io}_{\text{many}}(\vec{s},\vec{r}) = \sum_{a_1,\dots, a_\kappa} \chi_{\vec{a}}(\vec{s}) \cdot \left(\sum_{b_1,\dots,b_{\ell}} x_{\vec{b}}\cdot\chi_{\vec{b}}(\vec{r}) \right) = \mathsf{io}_{\text{single}}(\vec{r}) \cdot \left(\sum_{a_1,\dots, a_\kappa} \chi_{\vec{a}}(\vec{s})\right)$$
since we are using the fact that for all $\vec{a}$, we have $x_{\vec{a}||\vec{b}} = x_{\vec{b}}$

## What this means concretely

That for a practically relevant $K= 2^{13} \approx 9000$, Batch Testudo adds only $\approx 2K \approx 20000$ field operations. Even in the least parallelized of implementations, this should be $<1$ms.