# The Mining Process

We specify a mining algorithm for the PoSW consensus protocol that is based on modular exponentiation over some group `G`. We denote by `R` the relation representing the PoSW circuit, and set a NIZK tuple `(G, P, V)` to generate the common reference string `CRS = G(R)`. We are interested in defining an algorithm for `P` with a size `S` precomputation string that minimizes the number of multiplications performed in `G`.

## Modular Multiexponentiation​

Since the PoW process reduces to the hardness of exponentiation, we work in a model where we need to compute `q` instances of exponentiating `k` random indices `x_{i,j}` in `Z_p`, `(i,j)` in `[q] x [k]` for prime `p` of size `n = log(p)` by some random bases `G_i` in `G`:

``MultiExp({G_1, ..., G_k}, {x_1, ..., x_q}) = (∏_{i = 1..k} G_i^{x_{1,i}}, ..., ∏_{i = 1..k} G_i^{x_{q,i}})``

The algorithm `A = (A_1, A_2)` proceeds in two stages: first `A_1` precomputes a string of `S` group elements in `G` from the common reference string `CRS = {G_1, ..., G_k}`. `A_2` then takes this as input along with `q` sets of `k` elements in `Z_p` and produces `q` outputs `{π_1, ..., π_q}`.

For each of the bases `G_i`, compute `S/k` exponents and store them as part of the precomputation string. These exponents will be the radix decomposition bases for `Z_p` at the maximal permissible depth `c`. On average, for each index we require at most `n/(3 + log(S) - log(k)- log(n))` multiplications for a total of `q * k * n/(log(S) - log(k) - log(n))`. This means that the size of the precomputation string `S` grows exponentially with a linear improvement in proving time.

## Security \& Miner Size​

For a precomputation table of `S = k * (n/c) * (2^c - 1)` group elements, each exponentiation can be performed in `n/c` multiplications on average. However, at some point a maximal `c^*` is obtained that balances the communication cost of sending more precomputed elements with the cost of performing additional multiplications. We can thus operate under the assumption that miners work at around that level, and look at the security it implies.

We investigate proof generation times for various values of `c` in `N_+`. At constant block frequency, these can be used to project what the minimal table size `S` is for a predicate involving `k` exponentiations to achieve sufficiently low quantization error and collision probability.

### Security Implications of Hardware Acceleration​

Since hardware-accelerated miners would be able to provide order-of-magnitude improvements to the proof generation times for a given table size, the development of faster miners will correspond to a proportional decrease of both the quantization error and collision probabilities felt by the system. This means that incentives are aligned so that as the system grows it provides higher security.