FP256BN Plus and math.MaxInt64

[ale-linux]

The following test

import (
	"math"
	"math/rand"
	"testing"

	"github.com/stretchr/testify/assert"
)

func TestMaxInt(t *testing.T) {
	r1 := int(rand.Int63())
	r2 := int(rand.Int63())

	i1 := FP256BN.NewBIGint(math.MaxInt64 - r1)
	i2 := FP256BN.NewBIGint(r1)
	i3 := FP256BN.NewBIGint(math.MaxInt64 - r2)
	i4 := FP256BN.NewBIGint(r2)
	i5 := FP256BN.NewBIGint(2)

	i6 := i1.Plus(i2).Plus(i3).Plus(i4).Plus(i5)

	zero := FP256BN.NewBIGint(0)

	assert.NotEqual(t, zero, i6)
}

fails whereas it looks like it should be succeeding. The test was conducted with go version go1.14.4 linux/amd64 against the curve

32. FP256BN

generated by config64.py (git revision 5387e6a895243dde0).

[ale-linux]

This is actually related to miracl/core#44 and in fact, the git revision refers to that repo. The issue can be reproduced against both libraries

[mcarrickscott]

Hello Alessandro, Not sure what you are trying to achieve here, but this is not the best way to do it. For FP256BN the BIG type has digits of 2^56, and NewBigint() will only work with positive numbers less than that. In your case there will be overflows occurring everywhere. The library was not intended to be used like this. Tell me what you are trying to achieve, and I can probably point out a better way of doing it. Mike

…

On Tue, May 18, 2021 at 11:19 AM Alessandro Sorniotti < ***@***.***> wrote: This is actually related to miracl/core#44 <miracl/core#44> and in fact, the git revision refers to that repo. The issue can be reproduced against both libraries — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#58 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAU3ZDXGFHOA3XLGRCJWWODTOI5LJANCNFSM45CFRLVA> .

[ale-linux]

Thanks @mcarrickscott. We were testing various ECC math/crypto libraries (e.g. miracl/core, https://github.com/ConsenSys/gnark-crypto etc) trying to develop tests asserting basic behaviour across all of them, which is how we stumbled upon this issue.
What are the restrictions on the BIG and its constructors? We were expecting that something like

func TestMaxInt(t *testing.T) {
	i := FP256BN.NewBIGint(1)
	for j := 0; j < 64; j++ {
		i = i.Plus(i)
	}
	zero := FP256BN.NewBIGint(0)
	assert.NotEqual(t, zero, i)
}

would work.
Let us know how we're misusing the library - thanks!

[mcarrickscott]

OK, the particular issue is that addition needs to be followed by "normalization". For speed numbers are added digit by digit without processing the carries. Normalisation propagates the carries. So your program should look like for j := 0; j < 64; j++ { i = i.Plus(i) i.norm() } Alternatively in BIG64.go, change the Plus function to do the normalization internally /* return this+x */ func (r *BIG) Plus(x *BIG) *BIG { s := new(BIG) for i := 0; i < NLEN; i++ { s.w[i] = r.w[i] + x.w[i] } * s.norm()* return s } Actually it's probably an idea to do this since Plus is public. Hope this helps! Mike

…

On Tue, May 18, 2021 at 4:02 PM Alessandro Sorniotti < ***@***.***> wrote: Thanks @mcarrickscott <https://github.com/mcarrickscott>. We were testing various ECC math/crypto libraries (e.g. miracl/core, https://github.com/ConsenSys/gnark-crypto etc) trying to develop tests asserting basic behaviour across all of them, which is how we stumbled upon this issue. What are the restrictions on the BIG and its constructors? We were expecting that something like func TestMaxInt(t *testing.T) { i := FP256BN.NewBIGint(1) for j := 0; j < 64; j++ { i = i.Plus(i) } zero := FP256BN.NewBIGint(0) assert.NotEqual(t, zero, i) } would work. Let us know how we're misusing the library - thanks! — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#58 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAU3ZDXANSPTMPCINQI5KQLTOJ6RLANCNFSM45CFRLVA> .

[ale-linux]

Thanks a lot! So, without the explicit call to normalization the correctness of the result of Plus invocations is not guaranteed?

[mcarrickscott]

Well yes. But normalisations are not needed after every Plus, but are eventually needed to avoid overflow. It is probably best if we implement the norm() inside of Plus() since Plus() is public and likely to be used as you have used it. So thanks for bringing this to my attention. But note that this is not a bignum library, and is not expected to be used as one. Mike

…

On Tue, May 18, 2021 at 4:52 PM Alessandro Sorniotti < ***@***.***> wrote: Thanks a lot! So, without the explicit call to normalization the correctness of the result of Plus invocations is not guaranteed? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#58 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAU3ZDSQGN5RFCWMR4S6UUTTOKEMBANCNFSM45CFRLVA> .

[ale-linux]

It is probably best if we implement the norm() inside of Plus() since
Plus() is public and likely to be used as you have used it. So thanks for
bringing this to my attention.

Thank you

But note that this is not a bignum library, and is not expected to be used
as one.

Fair enough; but.. computations over the exponents (e.g. g^{\sum{a_i} mod Q}) are commonplace, and one might chain multiple +'s before calling Mod(q) (which iiuc calls norm()). So for example

func TestMaxInt(t *testing.T) {
	i := FP256BN.NewBIGint(1)
	q := FP256BN.NewBIGints(FP256BN.CURVE_Order)

	for j := 0; j < 64; j++ {
		i = i.Plus(i)
	}

	i.Mod(q)
	zero := FP256BN.NewBIGint(0)
	assert.NotEqual(t, zero, i)
}

one might assume this would work (I did notice that calling mod after every Plus seems to produce the right result).