Description

In sdk/utils.go, the function decomposeAndSlice is used to decompose a *big.Int into a specified number of limbs. This function does not make any checks to ensure that the result fully represents the input value.

The decomposeBig function is a wrapper that performs a check to ensure that the bit length of the absolute value of the input is small enough so that it can be fully represented (panicking otherwise), and it is implemented as follows.

func decomposeBig(data *big.Int, bitSize, length uint) []*big.Int {
	if uint(data.BitLen()) > length*bitSize {
		panic(fmt.Errorf("decomposed integer (bit len %d) does not fit into output (bit len %d, length %d)",
			data.BitLen(), bitSize, length))
	}
	return decomposeAndSlice(data, bitSize, length)
}

However, decomposeBig does not ensure that the input is not negative. Since decomposeAndSlice does not handle negative values in a special way, it returns a representation that clashes with legitimate positive values. For example, if the input is -1, then every limb will be 2^bitSize - 1.

For example, both printouts in the following example will print out [15 15 15 15]. This is the correct output for the second input, (1 << 16) - 1, whose four digits in base 16 are indeed 15. However, the first input of -1 also produces this result.

r := *big.NewInt(-1)
fmt.Println(r.String(), "decomposes to", decomposeBig(&r, 4, 4))
r = *big.NewInt((1 << 16) - 1)
fmt.Println(r.String(), "decomposes to", decomposeBig(&r, 4, 4))

The decomposeAndSlice function should thus be avoided for negative values. One place in which this function is (ultimately) called, and which confusing behavior may arise for negative values, is the Bytes32 type and its conversions to binary.

The Bytes32 type is implemented in sdk/api_bytes32.go and offers two internal functions to be used for conversion to binary: toBinaryVars for the case of circuit variables and toBinary for the case of native types.

The two functions are implemented as follows:

func (v Bytes32) toBinaryVars(api frontend.API) []frontend.Variable {
	var bits []frontend.Variable
	bits = append(bits, api.ToBinary(v.Val[0], numBitsPerVar)...)
	bits = append(bits, api.ToBinary(v.Val[1], 32*8-numBitsPerVar)...)
	return bits
}

func (v Bytes32) toBinary() []uint {
	var bits []uint
	bits = append(bits, decomposeBits(fromInterface(v.Val[0]), uint(numBitsPerVar))...)
	bits = append(bits, decomposeBits(fromInterface(v.Val[1]), uint(32*8-numBitsPerVar))...)
	return bits
}

Suppose that v.Val[0] is assigned a negative number. If this is done as a witness, then this value would be reduced modulo the scalar field prime modulus r. Should the resulting value not be at most numBitsPerVar bits wide, then constraints introduced by api.ToBinary will not be satisfied, so the prover will emit an error.

In contrast, if the negative values are given as a native type such as big.Int and accordingly the second function is used, then the call to decomposeBits will ultimately result in a call to the decomposeBig function that was discussed above. If the absolute value is at most numBitsPerVar wide, then no error will be emitted.

The decompose function in common/utils/compose.go has the same behavior as decomposeAndSlice. Furthermore, it will not work as intended if its argument bitSize is bigger than 64. This latter issue also occurs for decompose from sdk/utils.go.

Impact

For negative values, the decomposeAndSlice and decompose functions return a decomposition that is likely unintended and which clashes with decompositions of positive values. As the case of negative values is not prevented by various wrapper functions, it can ultimately be reached from, for example, Bytes32.toBinary.

Thus, when negative values are assigned to the underlying fields of a Bytes32, the functions used for conversion to binary differ in their behavior depending on whether or not the variant for witnesses or the variant for native types was used. This confusing behavior could lead to mistakes.

Recommendations

We recommend making sure that the input is equal to or greater than zero in the functions decomposeAndSlice and decompose, by panicking on negative values.

For decompose, we also recommend to check that bitSize <= 64 and panic otherwise.

Remediation

This issue has been acknowledged by Brevis, and fixes were implemented in the following commits:

• 5a4114cc↗
• 9af3f96f↗
• 65bd9950↗