Skip to content

Proof Verification

Jump to bottom
Mihai Preda edited this page Jun 10, 2020 · 3 revisions

A secure hash is used in the proof generation and verification. The hash function used is SHA3-256, denoted by hash256() in the following. We also use a 64-bits truncation of the 256-bit hash, denoted with low64().

1. Initialization

hash = hash256(E, B)
A = 3

Where E is the exponent from the proof header. B is the first residue that follows the proof header.

The integer value E is hashed as a 64-bit little-endian value. The residue is hashed as a sequence of 32-bit words (see the file format)

The residue A is initialized with the starting point of the PRP test, the value 3. (A, a residue, has the same size and representation as the other residues such as B).

2. Walking the Middles

There are N middles, where N is the proof power (see File Header). For each middle M[i] in turn:

  hash = hash256(hash, M[i])
  h64 = low64(hash)
  A = A^h64 * M[i]
  B = M[i]^h64 * M[i]

(where the ^ operator above denotes modular exponentiation).

At this point a check of file integrity and hash correct application is available, by comparing for equality the Proof-hash from the file header with the low64(hash) where hash is the final hash value after walking the middles as shown in the above loop.

3. The PRP iterations

The last step of proof verification consists in running a number of PRP iterations (modular squarings). We use the value topK = (E/1024 + 1)*1024, topK being the smallest multiple of 1024 larger than E. The number of PRP iterations is

k = topK/2N

(where N is the proof power). The verification consist in checking that k iterations starting from A produce B, i.e.

A2k == B

The bulk of the work of proof verification consists in these PRP iterations. We see the effect of the proof power N on the verification cost -- each increment of the power halves the verification cost.

4. Composite or Probable-prime?

The previous steps allow to verify that the PRP residue at iteration topK is indeed equal to the first residue stored in the proof file (called "B" in the proof file format). We still need to decide whether the outcome of the PRP test for exponent E was composite or probable prime.

According to the PRP test, for a probable prime, the residue at iteration E must be equal to 9, so the residue at iteration topK must be equal to 92topK-E; otherwise (if that equality doesn't hold) the outcome of the test is composite.

Clone this wiki locally