Incorrect Matching between State Leaf and Message

[ctrlc03]

In the MACI protocol, each message submitted by a user has an index that states which state leaf it is meant to modify. However, if a message is invalid, which can happen for a variety of reasons, then it shouldn’t modify any stateleaf. Since invalid messages are expected in the protocol, they should not cause the circuits to fail. In order to support this, the coordinator is expected to pass in the state leaf at index 0 for any invalid messages. So the circuit will mark the message as invalid, then check that the passed in state leaf exists at the 0 position in the Merkle tree.

The problem is that a message can be rendered invalid if it is compared to a state leaf index that does not match the message’s state leaf index. So there is an issue where a coordinator sees an invalid message, and so compares it to the 0 state leaf. But by comparing it to the 0 state leaf, the message will be marked as invalid since it was likely intended for a different leaf.

The attack here is that a coordinator can censor any user message by simply comparing it to the 0 leaf, even if the message is valid. Since the message is likely intended for a different state leaf, the circuits will mark it as invalid and this vote will not be tallied.

Location

maci/circuits/circom/processMessages.circom

Lines 537 to 559 in 3aa4f33

	component stateIndexMux = Mux1();
	stateIndexMux.s <== transformer.isValid + msgType - 1;
	stateIndexMux.c[0] <== 0;
	stateIndexMux.c[1] <== indexByType;
	component stateLeafPathIndices = QuinGeneratePathIndices(stateTreeDepth);
	stateLeafPathIndices.in <== stateIndexMux.out;
	// -----------------------------------------------------------------------
	// 3. Verify that the original state leaf exists in the given state root
	component stateLeafQip = QuinTreeInclusionProof(stateTreeDepth);
	component stateLeafHasher = Hasher4();
	for (var i = 0; i < STATE_LEAF_LENGTH; i++) {
	stateLeafHasher.in[i] <== stateLeaf[i];
	}
	stateLeafQip.leaf <== stateLeafHasher.hash;
	for (var i = 0; i < stateTreeDepth; i ++) {
	stateLeafQip.path_index[i] <== stateLeafPathIndices.out[i];
	for (var j = 0; j < TREE_ARITY - 1; j++) {
	stateLeafQip.path_elements[i][j] <== stateLeafPathElements[i][j];
	}
	}
	stateLeafQip.root === currentStateRoot;

Fixed by #1170

[samajammin]

Fixed by #1170 👍