Description

The circuits constructed using the sdk use receipt, storage, and transaction data but do not verify their correctness. Instead, they commit to these data points by hashing, and they ultimately expose a Merkle root hash of these commitments as a public input to the circuit. Correctness of the data points is then enforced by the Brevis backend circuits with the link being made through the Merkle root hash.

Calculation of the individual commitments from the receipt, storage, and transaction data is done in the commitInput function of sdk/host_circuit.go. The calculation is performed in the same way for each of the three types of data. The following snippet shows the relevant code for receipts:

   hasher, err := poseidon.NewBn254PoseidonCircuit(c.api)
if err != nil {
	return fmt.Errorf("error creating poseidon hasher instance: %s", err.Error())
}

hashOrZero := func(toggle frontend.Variable, vs []frontend.Variable) frontend.Variable {
	hasher.Reset()
	if len(vs) > 16 {
		panic(fmt.Sprintf("input is more than 16: %d", len(vs)))
	}
	for _, v := range vs {
		hasher.Write(v)
	}
	sum := hasher.Sum()
	return c.api.Select(toggle, sum, 0)
}

var inputCommits [NumMaxDataPoints]frontend.Variable
receipts := c.Input.Receipts
j := 0
for i, receipt := range receipts.Raw {
	packed := receipt.pack(c.api)
	inputCommits[j] = hashOrZero(receipts.Toggles[i], packed)
	j++
}

As seen, the receipt is being packed into field elements by using the pack function. This method function is implemented for each of the three data types and consists essentially of converting the data making up the receipt into binary bits, concatenating them, and then converting this bit string to field elements. Back in commitInput, the commitment is constrained to be zero if the entry was disabled by the toggles, and otherwise it is constrained to be the Poseidon hash of the packed data.

There is no explicit domain separation between the different data types used in the commitment.

Impact

Lack of domain separation could hypothetically make collisions between input types possible. Suppose that it is possible to construct an input of type A and one of type B so that they pack to the same field elements. Then their commitments will be the same as well. If an attacker can achieve this with the input of type B being valid, then they will be able to submit this input of type B to the Brevis backend, and the Merkle root hash will pass verification. However, they will be able to instead use the invalid input of type A within the circuit. This would amount to a critical vulnerability.

In the present situation, this is not possible, however, because the three input data types are implicitly domain separated by their different lengths: the length of the packed data in field elements is 8 for receipts, 3 for storage, and 4 for transactions.

If these lengths matched, there may be other obstacles that could prevent an attacker from obtaining useful collisions in practice.

However, relying on the different lengths can be brittle in case of changes. For example, if the way the input data types get packed is changed or more input types are added in the future.

The easiest way to prevent collisions in the future is to domain separate the hashes by prepending something unique to the type. For example, each of the packed input data could be hashed after prepending a field element that is unique to the type, such as the byte string BREVIS_INPUT_RECEIPT. Alternatively, to minimize field elements used in the hash, one might also just prepend some unique bits before converting to field elements.

Recommendations

The current version of the code is not vulnerable to type confusion as discussed. For defense in depth and to avoid such a vulnerability on future changes, we nevertheless recommend to add explicit domain separation between the different input types.

Remediation

Brevis plans to add explicit domain separation between different input types in the future.