Find out the max number of entries that is possible to put into the advidce columns given a certain K

[alxkzmn]

The expected maximum number of usable columns for the univariate grand sum circuit is 2^K-6. https://github.com/summa-dev/halo2/blob/main/halo2_proofs/src/plonk/circuit.rs#L2349 https://github.com/summa-dev/halo2/blob/main/halo2_proofs/src/plonk/prover.rs#L310 However, the observed number is much lower.

[sifnoc]

The current maximum number of users that can be accommodated is $2^K - 2^{16} - 6$ in the advice column, given K. The deduction of 6 rows for blind factors, and $2^{16}$ rows represents the number of values occupied in the fixed column. These are constant values ranging from 0 to $2^{16}$, utilized for the range check chip.

This configuration leads to an issue where the UnivariateGrandSum circuit cannot be fully populated with $2^K - 6$ entries in the advice columns, despite there being $2^{16}$ empty rows in these columns.

The table structure is illustrated as follows:

Number of Row	Username	Currency_1	Currency_2	...	range_u16
1	dxGaEAii	11888	41163		0
...
65536	MBlfbBGI	67823	18651		65535
65537	lAhWlEWZ	18651	2087		0
65538	nuZweYtO	22073	55683		0
...					...
$2^K - 2^{16} - 6$	RZNneNuP	31699	35479		0
$2^K - 2^{16} - 5$					0
...					...
2^K				...	0

The root cause of this issue stems from the assign_region method. This method performs two operations included: it assigns a constant value to the fixed column (denoted as range_u16 in the table) and then mapping this value(internally called, permutation.copy) to the advice column here, which is triggered to verify the zero value in the range check chip with constrain_constant. Essentially, the assign_region function, assigns values to the next available row after the last used row each time it is called, meaning it populates the next empty row in the fixed column.

At row $2^K - 2^{16} - 5$, the range check chip cannot assign 0 values to range_u16 anymore, as the column is already filled with other values.

Below is the actual trace log for reference:

1834972 DEBUG synthesize:region{name="load range check table of 16 bits"}:assign_fixed{name="assign cell in fixed column" column=Column { index: 0, column_type: Fixed } offset=65535}: layouter: Entered
1834973 DEBUG synthesize:region{name="load range check table of 16 bits"}:assign_fixed{name="assign cell in fixed column" column=Column { index: 0, column_type: Fixed } offset=65535}: position: row=65535
1834974 DEBUG synthesize:region{name="load range check table of 16 bits"}:assign_fixed{name="assign cell in fixed column" column=Column { index: 0, column_type: Fixed } offset=65535}: assigned: value=Trivial(0x0
1834974 00000000000000000000000000000000000000000000000000000000000ffff)
1834975 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_0" column=Column { index: 2, column_type: Advice } offset=0}: layouter: Entered
1834976 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_1" column=Column { index: 3, column_type: Advice } offset=0}: layouter: Entered
1834977 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_2" column=Column { index: 4, column_type: Advice } offset=0}: layouter: Entered
1834978 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_3" column=Column { index: 5, column_type: Advice } offset=0}: layouter: Entered
1834979 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}: constrain_constant: cell=Cell { region_index: RegionIndex(2), row_offset: 0, column: Column { index: 5, column_type: Advice } }1834979  constant=Trivial(0x0000000000000000000000000000000000000000000000000000000000000000)
1834980 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_0" column=Column { index: 2, column_type: Advice } offset=0}: layouter: Entered
1834981 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_0" column=Column { index: 2, column_type: Advice } offset=0}: position: row=0
1834982 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_0" column=Column { index: 2, column_type: Advice } offset=0}: assigned: value=Trivial(0x000000000000000001834982 00000000000000000000000000000000000000000000000)
1834983 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_1" column=Column { index: 3, column_type: Advice } offset=0}: layouter: Entered
1834984 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_1" column=Column { index: 3, column_type: Advice } offset=0}: position: row=0
1834985 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_1" column=Column { index: 3, column_type: Advice } offset=0}: assigned: value=Trivial(0x000000000000000001834985 00000000000000000000000000000000000000000000000)
1834986 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_2" column=Column { index: 4, column_type: Advice } offset=0}: layouter: Entered
1834987 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_2" column=Column { index: 4, column_type: Advice } offset=0}: position: row=0
1834988 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_2" column=Column { index: 4, column_type: Advice } offset=0}: assigned: value=Trivial(0x000000000000000001834988 00000000000000000000000000000000000000000000000)
1834989 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_3" column=Column { index: 5, column_type: Advice } offset=0}: layouter: Entered
1834990 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_3" column=Column { index: 5, column_type: Advice } offset=0}: position: row=0
1834991 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:assign_advice{name="zs_3" column=Column { index: 5, column_type: Advice } offset=0}: assigned: value=Trivial(0x000000000000000001834991 00000000000000000000000000000000000000000000000)
1834992 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}: constrain_constant: cell=Cell { region_index: RegionIndex(2), row_offset: 0, column: Column { index: 5, column_type: Advice } }1834992  constant=Trivial(0x0000000000000000000000000000000000000000000000000000000000000000)
1834993 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}: assign_fixed: name="Constant(0x0000000000000000000000000000000000000000000000000000000000000000)" column=Column { index: 0, col1834993 umn_type: Fixed } row=65536
1834994 DEBUG synthesize:region{name="Perform range check on balance 0 of user 0"}:positioned: copy: left_column=Column { index: 0, column_type: Fixed } left_row=65536 right_column=Column { index: 5, column_type1834994 : Advice } right_row=0

To resolve this issue, we must consider assigning the zero value used in the range check chip to a more suitable location rather than the fixed column.

[alxkzmn]

$2^K-6$. Fixed in #276.