# 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 , and which is defined in Dan Boneh’s paper :

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:

q=x/l

and:

x=ql+r

Victor then sends (Q) of:

Q=u^q (mod l)

Victor then computes:

r=x (mod l)

And will accept the proof if:

Q^l u^r=w

A sample of the code is:

A sample run is [here]:

## Conclusions

We need to change the way we prove things, such as our passwords. The method defined here does some magic and allows Peggy to prove a secret to Victor. In Wesolowski’s paper, he introduces a triple (u, w, t) that satisﬁes w = u^{2^t}.

## References

 Benjamin Wesolowski. Eﬃcient veriﬁable delay functions. Cryptology ePrint Archive, Report 2018/623, 2018. https://eprint.iacr.org/2018/623.

 Boneh, D., Bünz, B., & Fisch, B. (2019, August). Batching techniques for accumulators with applications to iops and stateless blockchains. In Annual International Cryptology Conference (pp. 561–586). Springer, Cham. https://eprint.iacr.org/2018/1188.pdf

Written by