-
Notifications
You must be signed in to change notification settings - Fork 358
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
bug: emulated arithmetic: unable to call IsZero after FromBits if the input is bigger than q #1009
Comments
@hussein-aitlahcen, I think current behavior is as expected. below is my understanding step by step.
// FromBits returns a new Element given the bits is little-endian order.
func (f *Field[T]) FromBits(bs ...frontend.Variable) *Element[T] {
nbLimbs := (uint(len(bs)) + f.fParams.BitsPerLimb() - 1) / f.fParams.BitsPerLimb()
limbs := make([]frontend.Variable, nbLimbs)
for i := uint(0); i < nbLimbs-1; i++ {
limbs[i] = bits.FromBinary(f.api, bs[i*f.fParams.BitsPerLimb():(i+1)*f.fParams.BitsPerLimb()])
}
limbs[nbLimbs-1] = bits.FromBinary(f.api, bs[(nbLimbs-1)*f.fParams.BitsPerLimb():])
return f.newInternalElement(limbs, 0). //THE 0 is MISLEADING
}
func (f *Field[T]) IsZero(a *Element[T]) frontend.Variable {
ca := f.Reduce(a) //CALL Reduce
f.AssertIsInRange(ca)
res := f.api.IsZero(ca.Limbs[0])
for i := 1; i < len(ca.Limbs); i++ {
res = f.api.Mul(res, f.api.IsZero(ca.Limbs[i]))
}
return res
}
func (f *Field[T]) Reduce(a *Element[T]) *Element[T] {
f.enforceWidthConditional(a).
if a.overflow == 0 {
// fast path - already reduced, omit reduction. //SKIP THE OVERFLOWCHECK
return a
}
// sanity check
if _, aConst := f.constantValue(a); aConst {
panic("trying to reduce a constant, which happen to have an overflow flag set")
}
// slow path - use hint to reduce value
return f.mulMod(a, f.One(), 0)
}
func (f *Field[T]) Add(a, b *Element[T]) *Element[T] {
return f.reduceAndOp(f.add, f.addPreCond, a, b)
}
func (f *Field[T]) reduceAndOp(op func(*Element[T], *Element[T], uint) *Element[T], preCond func(*Element[T], *Element[T]) (uint, error), a, b *Element[T]) *Element[T] {
f.enforceWidthConditional(a)
f.enforceWidthConditional(b)
var nextOverflow uint
var err error
var target overflowError
for nextOverflow, err = preCond(a, b); errors.As(err, &target); nextOverflow, err = preCond(a, b) {
if !target.reduceRight {
a = f.Reduce(a)
} else {
b = f.Reduce(b)
}
}
return op(a, b, nextOverflow)
} I think there are 3 methods to fix this problem,
func (f *Field[T]) FromBits(bs ...frontend.Variable) *Element[T] {
nbLimbs := (uint(len(bs)) + f.fParams.BitsPerLimb() - 1) / f.fParams.BitsPerLimb()
limbs := make([]frontend.Variable, nbLimbs)
for i := uint(0); i < nbLimbs-1; i++ {
limbs[i] = bits.FromBinary(f.api, bs[i*f.fParams.BitsPerLimb():(i+1)*f.fParams.BitsPerLimb()])
}
limbs[nbLimbs-1] = bits.FromBinary(f.api, bs[(nbLimbs-1)*f.fParams.BitsPerLimb():])
return f.newInternalElement(limbs, 1) //Assume overflow happens for safety
}
type C struct {
Preimage [Bytes * 8]frontend.Variable
Image emulated.Element[emulated.BN254Fp]
DoubleImage emulated.Element[emulated.BN254Fp]
}
func (c *C) Define(api frontend.API) error {
field, err := emulated.NewField[emulated.BN254Fp](api)
if err != nil {
return err
}
image := field.FromBits(c.Preimage[:]...) //without overflow check
zero := field.NewElement(0)
image = field.Add(image, zero) //FORCE all
field.AssertIsEqual(image, &c.Image)
doubleImage := field.Add(image, image)
field.AssertIsEqual(doubleImage, &c.DoubleImage)
// Breaks, works with field.IsZero(doubleImage)
field.IsZero(image)
return nil
} |
I used the |
Could help to figure out which one is the hint function in your mind? |
Unsure if it's a bug or not but I hit issues when calling
IsZero
afterFromBits
with input bigger than the modulus. I figured thatFromBits
can generate emulated elements with a number of limbs > NbLimbs param of the curve, is it expected? If so,IsZero
should be passing? Please let me know if I am missing something.On the other hand, addition and multiplication are working, here is a strange snippet where
IsZero(image)
is failing andIsZero(doubleImage)
is passing:The text was updated successfully, but these errors were encountered: