Skip to content

bug: emulated IsZero panics or returns wrong result for elements not at modulus width #1805

Description

@0x5ea000000

Description

emulated.Field.IsZero assumes the element it reduces always comes back with exactly the modulus limb count. Elements built by Field.FromBits (and other internal constructions) can legally carry a different number of limbs with zero overflow, and Field.Reduce's fast path returns zero-overflow elements unchanged regardless of width. This breaks IsZero in two ways:

  1. Wider than the modulus → panic. The resP comparison loop in field_assert.go is bounded by len(ca.Limbs) but indexes p.Limbs[i]:
resP := f.api.IsZero(f.api.Sub(p.Limbs[0], ca.Limbs[0]))
for i := 1; i < len(ca.Limbs); i++ {
	resP = f.api.Mul(resP, f.api.IsZero(f.api.Sub(p.Limbs[i], ca.Limbs[i])))
}

Feeding e.g. a 512-bit FromBits result (8 limbs) into IsZero over a 4-limb modulus panics at circuit definition with index out of range [4] with length 4. This is reachable from std: scalarMulFakeGLV calls IsZero(s) on the incoming scalar, so any circuit passing a wide FromBits scalar (e.g. a SHA-512 output reduced mod L, as in Ed25519 verification) into ScalarMul/MultiScalarMul on a fakeGLV curve crashes at compile time.

  1. Correctness for non-modulus-width elements. Even with the loop bounds fixed, the "reduced value is 0 or p" invariant only holds for values < 2p. A wide zero-overflow element can be any multiple of p (e.g. 2p, ), which would be misclassified as non-zero. Conversely, an element with fewer limbs than the modulus makes the loop compare only a prefix of p.Limbs, so a short element equal to the low limbs of p is misclassified as zero (false positive).

Expected Behavior

IsZero(a) returns whether a ≡ 0 (mod p) for any width-constrained element, per its doc ("the method internally reduces the element").

Actual Behavior

Panic for wider-than-modulus elements; wrong result possible for narrower-than-modulus elements.

Steps to Reproduce

type IsZeroWide[T emulated.FieldParams] struct {
	Bits []frontend.Variable // 2 * modulus bit length, e.g. a hash output
}

func (c *IsZeroWide[T]) Define(api frontend.API) error {
	f, err := emulated.NewField[T](api)
	if err != nil {
		return err
	}
	_ = f.IsZero(f.FromBits(c.Bits...))
	return nil
}

// frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder,
//     &IsZeroWide[emulated.BN254Fr]{Bits: make([]frontend.Variable, 508)})
// => parse circuit: runtime error: index out of range [4] with length 4

Repro stack (via the std fakeGLV path):

runtime error: index out of range [4] with length 4
emulated.(*Field[...]).IsZero            std/math/emulated/field_assert.go
sw_emulated.(*Curve[...]).scalarMulFakeGLV   std/algebra/emulated/sw_emulated/point.go
sw_emulated.(*Curve[...]).jointScalarMulFakeGLV
sw_emulated.(*Curve[...]).MultiScalarMul

Possible Fix

Force a real modular reduction in IsZero when the reduced element is wider than the modulus (the Reduce fast path skips zero-overflow elements regardless of limb count), and compare against all of p.Limbs (treating missing high limbs as zero) for narrower elements. PR incoming.

Your Environment

  • gnark master (48e4e4b) and v0.13.0
  • go 1.25.7, linux/amd64

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions