Compatibility with 32 bit architectures

[Dhole]

It seems that conversions between Element and math/big.Int expect the architecture to be 64 bits, and break when the architecture is 32 bits.

For example, in SetBigInt (https://github.com/ConsenSys/goff/blob/master/internal/example/bn256/element.go#L538)

func (z *Element) SetBigInt(v *big.Int) *Element {
    // [...]

    vv := new(big.Int).Set(v)

    // [...]

    vBits := vv.Bits()
    for i := 0; i < len(vBits); i++ {
        z[i] = uint64(vBits[i])
    }

From go doc math/big.Int.Bits():

Bits provides raw (unchecked but fast) access to x by returning its absolute value as a little-endian Word slice. The result and x share the same underlying array. Bits is intended to support implementation of missing low-level Int functionality outside this package; it should be avoided otherwise.

In a 32 bit architecture, big.Int.Bits() will return 32 bit words, but SetBigInt expects 64 bit words. So in the bn256 example, vv.Bits() will return a slice of 8 elements, i in the loop will range [0..8) and the fifth iteration will panic because it will try to index z[4].

Error log as example:

panic: runtime error: index out of range [4] with length 4

goroutine 1 [running]:
github.com/iden3/go-iden3-crypto/ff.(*Element).SetBigInt(0x814a2080, 0x81498e00, 0x20)
/tmp/gomobile-work-097157879/pkg/mod/github.com/iden3/go-iden3-crypto@v0.0.3/ff/element.go:552 +0x31f

[gbotrel]

Thanks for reporting -- not surprised on that one, we kept this "32bit compatibility" as "nice to have" so far.

I suspect it may have other implications than just this call to big.Int.Bits() but I may be wrong. There may be some edge cases in the algorithms, depending on how go uses uint64 on a 32bits platforms. Need to setup a virtual environment to test on a 32bit target, unless you have an easier way to test 32bit target from a 64bit host?

As a temporary work around, I suppose you could try to use an unsafe pointer (not tested):

(*[N]uint64)(unsafe.Pointer(&vv.Bits()))

or just use a mask to concatenate uint32 if word size is 32 and not 64.

[mratsim]

Need to setup a virtual environment to test on a 32bit target, unless you have an easier way to test 32bit target from a 64bit host?

Easiest is probably to use a Windows VM in Azure Pipelines or Appveyor.

Appveyor supports both x86 and x64. Azure is x64-only but since the core libraries are 32-bit compatible, you only need to run the go 32-bit compiler.

[Dhole]

I managed to test this issue very easily from an x86_64 machine by setting the GOARCH env var in a test:

dev@mako ~/git/goff/internal/example/bn256 master
 $ uname -a
Linux mako 5.5.5-arch1-1 #1 SMP PREEMPT Thu, 20 Feb 2020 18:23:09 +0000 x86_64 GNU/Linux

dev@mako ~/git/goff/internal/example/bn256 master
 $ go test -count=1 -v ./...
=== RUN   TestELEMENTCorrectnessAgainstBigInt
--- PASS: TestELEMENTCorrectnessAgainstBigInt (0.08s)
=== RUN   TestELEMENTIsRandom
--- PASS: TestELEMENTIsRandom (0.00s)
PASS
ok      github.com/consensys/goff/internal/example/bn256    0.083s

dev@mako ~/git/goff/internal/example/bn256 master
 $ GOARCH=386 go test -count=1 -v ./...
=== RUN   TestELEMENTCorrectnessAgainstBigInt
--- FAIL: TestELEMENTCorrectnessAgainstBigInt (0.00s)
panic: runtime error: index out of range [4] with length 4 [recovered]
    panic: runtime error: index out of range [4] with length 4

goroutine 18 [running]:
testing.tRunner.func1.1(0x816f720, 0x8d18070)
    /usr/lib/go/src/testing/testing.go:941 +0x331
testing.tRunner.func1(0x8d380a0)
    /usr/lib/go/src/testing/testing.go:944 +0x349
panic(0x816f720, 0x8d18070)
    /usr/lib/go/src/runtime/panic.go:967 +0x122
github.com/consensys/goff/internal/example/bn256.(*Element).SetBigInt(0x8c32ea0, 0x8d12060, 0x8c32ec0)
    /home/dev/git/goff/internal/example/bn256/element.go:562 +0x314
github.com/consensys/goff/internal/example/bn256.TestELEMENTCorrectnessAgainstBigInt(0x8d380a0)
    /home/dev/git/goff/internal/example/bn256/element_test.go:65 +0x7e6
testing.tRunner(0x8d380a0, 0x8187d40)
    /usr/lib/go/src/testing/testing.go:992 +0xb4
created by testing.(*T).Run
    /usr/lib/go/src/testing/testing.go:1043 +0x2ad
FAIL    github.com/consensys/goff/internal/example/bn256    0.005s
FAIL

[gbotrel]

@Dhole tried the GOARCH thing on my MBP before and didn't work (bad CPU type in executable) but it did work on a Linux EC2 instance 👍

Good news is, fixing the SetBigInt with something like this:

vvBits := vv.Bits()
    p := (*[]uint64)(unsafe.Pointer(&vvBits))
    n := len(vv.Bits())
    if bits.UintSize == 64 {
        for i := 0; i < n; i++ {
            z[i] = uint64((*p)[i])
        }
    } else {
        // 32 bits, n %2 == 0
        for i := 0; i < n/2; i++ {
            z[i] = uint64((*p)[i])
        }
        if n%2 != 0 {
            z[n/2] = uint64(vv.Bits()[n-1])
        }
    }

seems to pass,

However, bad news, is the fix for goff ain't just about that, as suspected other methods seems to fail (I suspect the Mul and by consequence the Montgomery conversion).

This is a low-priority issue on our side -- and it will be easier to debug once we have a proper test-suite (and not just TestELEMENTCorrectnessAgainstBigInt).

[Dhole]

With the following changes in SetBigInt, ToBigInt and ToBigIntRegular I managed to get all the tests to pass. I'm not certain about how extensive the test suite is though.

// ToBigInt returns z as a big.Int in Montgomery form
func (z *Element) ToBigInt(res *big.Int) *big.Int {
    if bits.UintSize == 64 {
        bits := (*[4]big.Word)(unsafe.Pointer(z))
        return res.SetBits(bits[:])
    } else {
        var bits [8]big.Word
        for i := 0; i < len(z); i++ {
            bits[i*2] = big.Word(z[i])
            bits[i*2+1] = big.Word(z[i] >> 32)
        }
        return res.SetBits(bits[:])
    }
}

// ToBigIntRegular returns z as a big.Int in regular form
func (z Element) ToBigIntRegular(res *big.Int) *big.Int {
    z.FromMont()
    if bits.UintSize == 64 {
        bits := (*[4]big.Word)(unsafe.Pointer(&z))
        return res.SetBits(bits[:])
    } else {
        var bits [8]big.Word
        for i := 0; i < len(z); i++ {
            bits[i*2] = big.Word(z[i])
            bits[i*2+1] = big.Word(z[i] >> 32)
        }
        return res.SetBits(bits[:])
    }
}
// SetBigInt sets z to v (regular form) and returns z in Montgomery form
func (z *Element) SetBigInt(v *big.Int) *Element {
    // ...

    // v should
    vBits := vv.Bits()
    if bits.UintSize == 64 {
        for i := 0; i < len(vBits); i++ {
            z[i] = uint64(vBits[i])
        }
    } else {
        for i := 0; i < len(vBits); i++ {
            if i%2 == 0 {
                z[i/2] = uint64(vBits[i])
            } else {
                z[i/2] |= uint64(vBits[i]) << 32
            }
        }
    }
    return z.ToMont()
}

The benchmarks are not that good on 32 bits architecture with this change. I'm not sure exactly how uint64 arithmetic is implemented in go for i386; maybe having good performance for 32 bits arch requires the Element to be defined in arrays of uint32 instead of uint64.

Here are some bench results for comparison ran on Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz:

dev@mako ~/git/goff/internal/example/bn256 master
 $ go test -test.run=NONE -test.bench="MulAssign" -test.count=5 -test.benchtime=2s -test.cpu=1
goos: linux
goarch: amd64
pkg: github.com/consensys/goff/internal/example/bn256
BenchmarkMulAssignELEMENT       99691762                22.9 ns/op
BenchmarkMulAssignELEMENT       100000000               23.0 ns/op
BenchmarkMulAssignELEMENT       100000000               23.0 ns/op
BenchmarkMulAssignELEMENT       100000000               23.0 ns/op
BenchmarkMulAssignELEMENT       100000000               23.1 ns/op
BenchmarkMulAssignBigInt         4818390               491 ns/op
BenchmarkMulAssignBigInt         4814484               490 ns/op
BenchmarkMulAssignBigInt         4859062               480 ns/op
BenchmarkMulAssignBigInt         4886485               484 ns/op
BenchmarkMulAssignBigInt         4914770               491 ns/op
PASS
ok      github.com/consensys/goff/internal/example/bn256        27.926s
dev@mako ~/git/goff/internal/example/bn256 master
 $ GOARCH=386 go test -test.run=NONE -test.bench="MulAssign" -test.count=5 -test.benchtime=2s -test.cpu=1
goos: linux
goarch: 386
pkg: github.com/consensys/goff/internal/example/bn256
BenchmarkMulAssignELEMENT        5591630               420 ns/op
BenchmarkMulAssignELEMENT        5702698               413 ns/op
BenchmarkMulAssignELEMENT        5864181               402 ns/op
BenchmarkMulAssignELEMENT        5853076               405 ns/op
BenchmarkMulAssignELEMENT        5846158               409 ns/op
BenchmarkMulAssignBigInt         3385386               693 ns/op
BenchmarkMulAssignBigInt         3408957               695 ns/op
BenchmarkMulAssignBigInt         3417356               693 ns/op
BenchmarkMulAssignBigInt         3379266               683 ns/op
BenchmarkMulAssignBigInt         3455282               684 ns/op
PASS
ok      github.com/consensys/goff/internal/example/bn256        29.246s

Where BenchmarkMulAssignBigInt is:

func BenchmarkMulAssignBigInt(b *testing.B) {
    _x := Element{
        17522657719365597833,
        13107472804851548667,
        5164255478447964150,
        493319470278259999,
    }
    x := new(big.Int)
    x = _x.ToBigIntRegular(x)
    res := new(big.Int).Set(x)
    q, ok := new(big.Int).SetString("21888242871839275222246405745257275088696311157297823662689037894645226208583", 0)
    if !ok {
        b.Fatal("big.Int.SetString()")
    }
    // benchResElement.SetOne()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        res.Mul(res, x)
        res.Mod(res, q)
    }
}

[gbotrel]

Fixed on latest releases, closing (goff supports 64 bits only at generation time, but then 32bits compiles and works, with the caveat exposed here that... it is terribly slow).