Still confused by Plonk's permutation? posted last month

By now there's already a number of great explanation for Plonk's permutation argument (e.g. my own here, zcash's). But if it still causes you trouble, maybe read this visual explanation first.

On the left of this diagram you can see the table created by the three wires (or columns) of Plonk, with some added colors for cells that are wired to one another. As you can see, the values in the cells are valid: they respect the wiring (two cells that are wired must have the same values). Take a look at it and then read the next paragraph for an explanation of what's happening on the right:

On the right, you can see how we encode a permutation on the columns and rows to obtain a new table that, if the wiring was respected, should be the exact same table but with a different ordering.

The ordering will be eliminated in the permutation argument of Plonk, which will just check that both tables contain the same rows.

To encode the tables, we use two techniques illustrated in this diagram:

The first one is to use different cosets (i.e. completely distinct sets of points) to represent the different columns and rows. This is most likely the more confusing step of the permutation and so I've illustrated it with what it does in essence (assign a unique "index" that we can use to refer to each value).

The second one is simply to compress multiple columns with a challenge. (This technique is used in lookups as well when lookup tables have multiple columns.)

The following permutation circuit is then implemented:

def pos(col, row):
    return cosets[col] * row

def tuple(col, row, separator, value):
    return pos(col, row) * separator + value

# ((0, i), a[i]) * ((1, i), b[i]) * ((2, i), c[i]) 
def f(row, registers, challenges):
    return tuple(0, row, challenges[BETA], registers[0][row]) * tuple(1, row, challenges[BETA], registers[1][row]) * tuple(2, row, challenges[BETA], registers[2][row])

# (perm(0, i), a[i]) * (perm(1, i), b[i]) * (perm(2, i), c[i]) 
def g(row, registers, challenges):
    col0, row0 = circuit_permutation(0, row)
    col1, row1 = circuit_permutation(1, row)
    col2, row2 = circuit_permutation(2, row)
    return tuple(col0, row0, challenges[BETA], registers[0][row]) * tuple(col1, row1, challenges[BETA], registers[1][row]) * tuple(col2, row2, challenges[BETA], registers[2][row])

Z = 4

def compute_accumulator(row, registers, challenges):
    # z[-1] = 1
    if row == -1: 
        assert registers[Z][row] == 1
        return

    # z[0] = 1
    if row == 0: 
        assert registers[Z][row] == 1

    # z[i+1] = z[i] * f[i] / g[i]
    registers[Z][row+1] = registers[Z][row] * f(row, registers, challenges) / g(row, registers, challenges)

where the circuit is an AIR circuit built iteratively. That is, it was iteratively built on top of the first 3 registers. This means that the first 3 registers are now read-only (the left, right, and output registers of Plonk), whereas the fourth register (Z) can be written to. Since it's an AIR, things can be read at and written to at different adjacent rows, but as there is a cost to pay we only use that ability to write to the next adjacent row of the Z register.

To understand why the circuit looks like this, read the real explanation.