Description

The sdk provides multiple unsigned integer types, among them Uint248 and Uint521, with the numbers (roughly) expressing the bit width storable in them. The Uint521 type is in particular suggested to be used when needing to multiply Uint248 values to be able to handle overflows that would happen when multiplying as Uint248 directly. Due to this reason, it is important that there be a way to convert Uint248 values, including large values, to Uint521.

The function ToUint521 in sdk/circuit_api.go handles conversion of various types to Uint521. The following is the implementation of the case of Uint248 inputs.

case Uint248:
	el := api.Uint521.f.NewElement([]variable{v.Val, 0, 0, 0, 0, 0})
	return newU521(el)

The circuit variable in which the Uint248 value is stored is used as the first limb of the Uint521, with the other limbs set to zero. However, in the current implementation, each limb only stores up to 96 bits. When constructing the new element with NewElement, the limbs are range checked to ensure they do not exceed this bit width.

Impact

Attempting to convert a Uint248 to Uint521 will lead to unsatisfied constraints should the value be at least $2^{96}$. This thus amounts to a completeness issue.

The following test demonstrates this issue:

func TestZellicToUInt521(t *testing.T) {
	circuit := &TestZellicToUInt521Circuit{A: new(big.Int).Lsh(big.NewInt(1), 96)}
	err := test.IsSolved(circuit, circuit, ecc.BN254.ScalarField())
	check(err)
}

type TestZellicToUInt521Circuit struct {
	A   frontend.Variable
	g   frontend.API
	api *CircuitAPI
}

func (c *TestZellicToUInt521Circuit) Define(g frontend.API) error {
	c.g = g
	c.api = NewCircuitAPI(g)
	c.zellicTestToUInt521()

	return nil
}

func (c *TestZellicToUInt521Circuit) zellicTestToUInt521() {
	a := newU248(c.A)
	c.api.ToUint521(a)
}

Recommendations

Instead of using the circuit variable directly as the least significant limb, it should be decomposed into bits and then recomposed in groups of f.BitsPerLimb() = 96 bits, with those values used as limbs.

Remediation

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

• c7bdc2e5↗
• f8faa2f9↗