Skip to content
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

math/big: non-deterministic behaviour of big.Rand #42701

Open
holiman opened this issue Nov 18, 2020 · 2 comments
Open

math/big: non-deterministic behaviour of big.Rand #42701

holiman opened this issue Nov 18, 2020 · 2 comments
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@holiman
Copy link

holiman commented Nov 18, 2020

What version of Go are you using (go version)?

$ go version
go version go1.15.5 linux/amd64

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/user/.cache/go-build"
GOENV="/home/user/.config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/home/user/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/user/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/local/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/linux_amd64"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/home/user/go/src/github.com/ethereum/go-ethereum/go.mod"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build512723341=/tmp/go-build -gno-record-gcc-switches"

What did you do?

main.go (edit: I added the wrong code first):

package main

import (
	"fmt"
	"math/big"
	"math/rand"
)

type rndTest struct{
	count int
	src rand.Source
}

func (r *rndTest) Int63() int64 {
	r.count++
	return r.src.Int63()
}

func (r *rndTest) Seed(seed int64) {
	r.src.Seed(seed)
}

func main(){
	shim := &rndTest{0, rand.NewSource(0)}
	random := rand.New(shim)
	max := new(big.Int).Exp(big.NewInt(2), big.NewInt(256), nil)
	fmt.Printf("%v (%d reads)\n",  new(big.Int).Rand(random, max), shim.count)
	fmt.Printf("%v (%d reads)\n",  new(big.Int).Rand(random, max), shim.count)
}

output:

$ go run .
75882278871742073348705908634037840808905895098001936781526057361623699972085 (10 reads)
32980378865574341698424589833777768979918116503443097246085029326460293060374 (30 reads)
$ GOOS=linux GOARCH=386 go run . 
75882278871742073348705908634037840808905895098001936781526057361623699972085 (9 reads)
80252028366164880526544510430800498761927255387255296632111478555188670606789 (27 reads)

What did you expect to see?

I expected the big.Rand to perform deterministic amount of reads from the source, regardless of whether it was executed on a 32-bit or 64-bit platform

What did you see instead?

That different amounts of read was performed.

In my case, this caused certain testcases to fail on 32-bit platforms, since although the exact random steps were unimportant, the differing amounts of reads caused the source to go "out of sync", thus turning what should have been a deterministic process into two different deterministic processes (one for 64-bit and one for 32-bit).

This seems wrong to me, but there are obviously ways to work around it, so can't really say it's a biggie. Maybe there are other projects bit by this in other ways though, so the behaviour should at least be documented.

@holiman holiman changed the title Non-deterministic behaviour of big.Rand math/big: non-deterministic behaviour of big.Rand Nov 20, 2020
@toothrot toothrot added this to the Backlog milestone Dec 8, 2020
@toothrot toothrot added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Dec 8, 2020
@toothrot
Copy link
Contributor

toothrot commented Dec 8, 2020

/cc @griesemer @FiloSottile

@FiloSottile
Copy link
Contributor

Hmm, things that work differently just on different platforms are not good. However, per Hyrum's Law, just like you came to rely on this algorithm being stable without that being documented, changing the 32-bit algorithm might break anyone who expected it to stay the same.

Not really sure what people use this method for, so I don't know how to weight those two concerns.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Development

No branches or pull requests

3 participants