Verifying zk-STARKs

Verification is the process where an entity (typically referred to as the "verifier") checks the validity of a proof without gaining any knowledge about the underlying data from which the proof was constructed.

1. Importance of Verification

Verification ensures that the proof provided by the prover:

• Correctly represents the statement or computation.

• Does not leak any information about the underlying data.

The power of zk-STARKs lies in its ability to make this verification process succinct and efficient. The verifier does not need to redo the computation or be aware of all the intricacies, just the proof and a few additional pieces of information.

2. Steps in Verification

a. Receive Commitments:

• The verifier receives polynomial commitments from the prover. These commitments represent condensed versions of the polynomials without revealing their exact coefficients.

b. Challenge Generation:

• The verifier sends a challenge to the prover, typically asking them to evaluate the committed polynomial at a random point.

c. Receive Evaluation:

• The prover sends back the evaluation of their polynomial at the challenge point.

d. Verification Computation:

• Using the initial commitment, the verifier performs computations to check the correctness of the evaluation sent by the prover.

e. Accept or Reject:

• If the computations align, the verifier accepts the proof as valid.

• If there's a discrepancy, the proof is rejected.

3. Key Properties of zk-STARK Verification

a. Scalability:

• The verification process is scalable. This means that as the size or complexity of the original computation grows, the verification time does not increase linearly. This is a significant advantage, especially for systems that require verifying many computations.

b. Transparency:

• Unlike zk-SNARKs, zk-STARKs do not require a trusted setup. This means that there's no initial phase where secret parameters are generated, leading to greater trust in the system.

c. Quantum Resistance:

• zk-STARKs are designed to be post-quantum secure. This means that their security properties should hold even in the face of a quantum computer adversary.