Skip to main content

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.