A permutation argument is a method of showing that one vector is a permutation of another.

This sheet shows an example of a permutation argument, to demonstrate the technique behind memory consistency checks in RISC Zero.

Step 1: Prover commits to two sortings of the same data.

Time-Sorted Execution Trace

Address-Sorted Execution Trace

To enable efficient memory checking, the witness for zkVM proofs include duplicate commitments for memory operations: memory operations are included both in a time-sorted fashion and in an address-sorted fashion.

To prove correctness, we must both:

(1) enforce correctness of the memory operations in the address-sorted trace

(2) enforce correctness of the sorting

The logic in the black-box labelled "Verifier Requirements" accomplishes (1). The permutation argument accomplishes (2).

For more on (1), see Jeremy's explanation at zk7.

Step 2: Generate randomness (from Verifier or Fiat-Shamir)

Random PLONK Mixing Parameters

Step 3: Use randomness to generate accumulators.

Accumulators for Time-Sorted Trace

Accumulation Calculation

Address-Sorted Accumulation

If the Address-Sorted Execution Trace is not a permutation of the rows of the Time-Sorted Execution Trace, the accumulators are highly unlikely to match.

Step 4: Use various constraints to check details.

- Making sure accumulators match

- Making sure accumulators were constructed correctly

- Enforcing memory correctness on address-sorted trace, as described above