Description

The sdk provides a type Int248 in sdk/api_int248.go for 248-bit signed integers with which the integer range from $-2^{247}$ to $2^{247}-1$ can be represented. To represent negative values, two's complement is used.

The function ConstInt248 can be used to instantiate an Int248 from a native big.Int value, and it is implemented as follows:

// ConstInt248 initializes a constant Int248. This function does not generate
// circuit wires and should only be used outside of circuit. The input big int
// can be negative
func ConstInt248(v *big.Int) Int248 {
	if v.BitLen() > 248 {
		panic("cannot initialize Int248 with bit length > 248")
	}

	abs := new(big.Int).Abs(v)
	absBits := decomposeBitsExact(abs)

	if v.Sign() < 0 {
		bits := twosComplement(absBits, 248)
		a := recompose(bits, 1)
		return newI248(a, 1)
	}

	return newI248(abs, 0)
}

Note that the function checks the bit length of v and rejects values with a bit length larger than 248. This check does not account for the sign bit required in two's complement representation and is thereby insufficiently strict.

If v is nonnegative, then the value v is used directly as the returned Int248. Should the value of v be in the range $2^{247}<=v<2^{248}$, then the bit length check passes, yet the returned Int248 will be incorrect, as the sign bit will be set, so that the returned value will be interpreted as a negative integer.

An analogous issue is present in the negative case. For negative v, the function decomposes the absolute value of v into bits (in little endian) and passes them to the function twosComplement, and then it recomposes the bits returned by that function.

This function twosComplement is implemented in sdk/utils.go. It takes as arguments bits and n. From its usage in ConstInt248, we can conclude that bits is intended to be interpreted as representing an unsigned integer in little-endian presentation, and the return value should be the bitwise representation of the negation of that integer, represented using two's complement with n bits in total. The function is implemented as follows:

func twosComplement(bits []uint, n int) []uint {
	padded := padBitsRight(bits, n, 0)
	flipped := flipBits(padded)
	a := recompose(flipped, 1)
	a.Add(a, big.NewInt(1))
	d := decomposeAndSlice(a, 1, 248)
	ret := make([]uint, len(d))
	for i, b := range d {
		ret[i] = uint(b.Uint64())
	}
	return ret
	}

The function pads bits to n components using padBitsRight. If bits already has more than n components, then this will panic; see the discussion in section ref↗. But if bits has length exactly n, then no panic will happen. However, as one bit is needed for the sign, in two's complement with n bits, actually only values of at most n-1 bits width, and the edge case -2^(n-1), can be represented. Except that one edge case, the results will be incorrect.

For example, if bits is of length n and consists of 1, 0, ..., 0, 1, then the bits will be flipped to give 0, 1, ..., 1, 0, and then 1 is added, giving 1, 1, ..., 1, 0. This represents the positive value 2^(n-1) - 1, however, not the intended negative value -2^(n-1) - 1.

There is a single value with n bits for which twosComplement will return the correct two's complement representation of the negation, namely 2^(n-1), or in bits 0, ..., 0, 1. The bits returned by twosComplement will in this case be 0, ..., 0, 1 again, and this does represent the signed integer -2^(n-1) in n bit two's complement representation. On all other inputs with bit length n, the return value will be incorrect, however.

This in turn implies that ConstInt248 will return incorrect values for arguments v in the range -2^n < v < -2^(n-1).

Impact

The function ConstInt248 will return an incorrect Int248 value when it is called with a *big.Int value in one of the following ranges.

• $-2^{248}+1$ to $-2^{247}-1$

• $2^{247}$ to $2^{248}-1$

Recommendations

We recommend changing both ConstInt248 and twosComplement to more strictly check the inputs. Concretely, ConstInt248 should disallow every 248-bit length value as an input, except possibly for $-2^{247}$, and twosComplement should analogously disallow every length n input except possibly for [0,0,...,0,1].

Remediation

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

• 4deade11↗
• 2cd40ae7↗
• 65bd9950↗