Integer vs field division for Merkle path indices
Please answer the following questions for yourself before submitting an issue.
File: packages/circuits/circom/coordinator/non-qv/VoteTally.circom
Commit: 4fe3cec
The code uses “/” to calculate:
Num2Bits(STATE_TREE_DEPTH_DIFFERENCE)(index / batchSize);
This is modular field division, not integer floor division, which means index / batchSize equals to index · inverse(batchSize) mod p, not floor(index / batchSize).
The constraint only holds when index is an exact multiple of batchSize and the quotient fits in STATE_TREE_DEPTH_DIFFERENCE bits. Otherwise the circuit is unsatisfiable (denial of service) or binds the path to an unintended value. It also silently enforces an alignment requirement without making it explicit.
Fix: Compute q, where index = q · batchSize + r with 0 ≤ r < batchSize, then either enforce r = 0 (if alignment is required) or use q as the parent index.
Integer vs field division for Merkle path indices
Please answer the following questions for yourself before submitting an issue.
File: packages/circuits/circom/coordinator/non-qv/VoteTally.circom
Commit: 4fe3cec
The code uses “/” to calculate:
Num2Bits(STATE_TREE_DEPTH_DIFFERENCE)(index / batchSize);This is modular field division, not integer floor division, which means
index / batchSizeequals toindex · inverse(batchSize) mod p, notfloor(index / batchSize).The constraint only holds when index is an exact multiple of batchSize and the quotient fits in STATE_TREE_DEPTH_DIFFERENCE bits. Otherwise the circuit is unsatisfiable (denial of service) or binds the path to an unintended value. It also silently enforces an alignment requirement without making it explicit.
Fix: Compute q, where
index = q · batchSize + rwith 0 ≤ r < batchSize, then either enforce r = 0 (if alignment is required) or use q as the parent index.