Member-only story
Proof of Exponentiation using Wesolowski’s Method
With zero-knowledge proofs we can implement a proof of exponentiation, and where Peggy can prove to Victor that she knows the required exponentiation. For this, we can significantly reduce the computation required, as we can define the field in which the calculations are performed in. But field we define that there are a limit number of outputs from a calculation, as we perform them with a (mod N) operation (and where the values go from 0 to N-1). The smaller the number of bits in N, the less time it will take to compute.
One method was produced by Wesolowski’s [1], and which is defined in Dan Boneh’s paper [2]:
So let’s look at the Wesolowski method and how it reduces the complexity of the zero-knowledge proof process. First, Peggy and Victor know three values u, w and x and where:
w=u^x
Peggy will prove to Victor that she still knows the values of u and x, based on a challenge. Initially, Victor generates an n-bit prime number (l) and passes it to Victor. Victor then computes a quotient and a residue of x given our n-bit prime number, with:
