Re: Converting points on a BN256 (BLS) curve to plain integer values in Kyber

[Allen Jeffrey Richard]

Hello Denis,

I’ve CC’d this response to the public cothority list, because it seems to me others might benefit and might also be able to help out.

I’m not exactly sure what you mean by “input data must be in the form of ordinary numbers”, but we’ve had significant experience with implementing crypto primitives across different implementations, so I’m generally familiar with the problem.

The main way we move BN256 points between systems is via binary marshaling and unmarshaling. See for instance:

https://pkg.go.dev/go.dedis.ch/kyber/v3#Marshaling

And the BN256 implementation of the MarshalBinary function for the G1 type:

https://github.com/dedis/kyber/blob/v3.0.13/pairing/bn256/point.go#L110 

Here is the Javascript implementation of the same idea:

https://github.com/dedis/cothority/blob/master/external/js/kyber/src/pairing/bn.ts#L117 

(The corresponding UnmarshalBinary are nearby in each language.)

Judging from your proposed code, you’ve already found these examples and you are doing something like them, i.e. using montDecode, but then you seem to be trying to get to Go bignums, instead of byte buffers. I generally always try to use Kyber without looking too closely inside of it, so the fact you need to call montDecode is a red flag for me. :)

The input to Solidity contracts need to be uint256, right? (https://docs.soliditylang.org/en/v0.8.1/types.html#integers)

I guess what you are looking for is a way to represent the output of Kyber’s MarshalBinary on a G1 point (i.e. 64 bytes, 512 bits) as two uint256 constants (i.e. 512 bits across two constants). Like this? (I put this into the bn256/suite_test.go unit tests, just as a quick place to try an experiment.)

diff --git a/pairing/bn256/suite_test.go b/pairing/bn256/suite_test.go

index f15d93ff..dc0da60c 100644

--- a/pairing/bn256/suite_test.go

+++ b/pairing/bn256/suite_test.go

@@ -3,6 +3,7 @@ package bn256

 import (

  "bytes"

  "fmt"

+ "math/big"

  "testing"

 

  "github.com/stretchr/testify/require"

@@ -92,6 +93,38 @@ func TestG1Marshal(t *testing.T) {

  require.Equal(t, ma, mb)

 }

 

+func TestG1ToSolidity(t *testing.T) {

+ bi := new(big.Int)

+ suite := NewSuite()

+

+ // Try first with a Zero point.

+ k := suite.G1().Scalar().Zero()

+ pa := suite.G1().Point().Mul(k, nil)

+ ma, err := pa.MarshalBinary()

+ require.Nil(t, err)

+

+ // To Solidity, uint256 x 2

+ // SetBytes docs (pay attention to endianess!)

+ // https://golang.org/pkg/math/big/#Int.SetBytes

+ bi.SetBytes(ma[0:32])

+ // formatting bi as %s is the same as calling math/big.(*Int).String().

+ // See: https://golang.org/pkg/math/big/#Int.String

+ t.Logf("uint256 g1x = %s", bi)

+ bi.SetBytes(ma[32:])

+ t.Logf("uint256 g1y = %s", bi)

+

+ // Now try with a random point.

+ k = suite.G1().Scalar().Pick(random.New())

+ pa = suite.G1().Point().Mul(k, nil)

+ ma, err = pa.MarshalBinary()

+ require.Nil(t, err)

+ // To Solidity, uint256 x 2

+ bi.SetBytes(ma[0:32])

+ t.Logf("uint256 g1x = %s", bi)

+ bi.SetBytes(ma[32:])

+ t.Logf("uint256 g1y = %s", bi)

+}

+

 func TestG1Ops(t *testing.T) {

  suite := NewSuite()

  a := suite.G1().Point().Pick(random.New())

When that test is run, this is the output:

go test -v -run Solidity 

=== RUN   TestG1ToSolidity

    suite_test.go:112: uint256 g1x = 0

    suite_test.go:114: uint256 g1y = 0

    suite_test.go:123: uint256 g1x = 6405964296151888589283369946297049615071462629409801671981178704280765222701

    suite_test.go:125: uint256 g1y = 24022460114782135406283456758820742407489033477860850282126363655584048101784

--- PASS: TestG1ToSolidity (0.00s)

PASS

ok   go.dedis.ch/kyber/v3/pairing/bn256 0.121s

Hope this is helpful, please feel free to respond and clarify and we can continue the conversation.

  -jeff

On 3 Feb 2021, at 16:45, ChronosX88 <chron...@gmail.com> wrote:

Hello, Jeff.

I'm Denis Davydov, the Software Engineer at Secured Finance. We are making cross-chain interoperability system called Dione, and in this project we are using Kyber as crypto library for creating BLS signatures. These signatures will be verified on Ethereum smart-contract side (there are precompiled contracts for doing this).

So, as far as I know, you are leading the Kyber library development at DEDIS. Do you know the person who is responsible for the BLS signature implementation? As I said, I need to verify BLS signatures on the side of Ethereum smart contracts, and for verification, input data (signature and public keys) must be in the form of ordinary decimal numbers. So, the question is how I can convert the points of BN256 curve to plain integer values to provide it to Ethereum smart-contracts?

I've tried to convert it by myself, looking at the code in pairing/bn256/point.go, but it didn't work - the Ethereum side is throwing the error "point not on curve".

The code for converting that I've written is provided below:

- G1 points:

func (p *pointG1) AffineCoords() []*big.Int {
    p = p.Clone().(*pointG1)

    pgtemp := *p.g
    pgtemp.MakeAffine()

    x := new(gfP)
    xi := new(big.Int)

    montDecode(x, &pgtemp.x)
    bufX := make([]byte, 32)
    x.Marshal(bufX)
    xi.SetBytes(bufX)

    y := new(gfP)
    yi := new(big.Int)

    montDecode(y, &pgtemp.y)
    bufY := make([]byte, 32)
    y.Marshal(bufY)
    yi.SetBytes(bufY)

    return []*big.Int{xi, yi}
}

- G2 points:

func (p *pointG2) AffineCoords() []*big.Int {
    p = p.Clone().(*pointG2)

    pgtemp := *p.g
    pgtemp.MakeAffine()

    xx := new(gfP)
    xxi := new(big.Int)
    montDecode(xx, &pgtemp.x.x)
    bufXX := make([]byte, 32)
    xx.Marshal(bufXX)
    xxi.SetBytes(bufXX)

    xy := new(gfP)
    xyi := new(big.Int)
    montDecode(xy, &pgtemp.x.y)
    bufXY := make([]byte, 32)
    xy.Marshal(bufXY)
    xyi.SetBytes(bufXY)

    yx := new(gfP)
    yxi := new(big.Int)
    montDecode(yx, &pgtemp.y.x)
    bufYX := make([]byte, 32)
    yx.Marshal(bufYX)
    yxi.SetBytes(bufYX)

    yy := new(gfP)
    yyi := new(big.Int)
    montDecode(yy, &pgtemp.y.y)
    bufYY := make([]byte, 32)
    yy.Marshal(bufYY)
    yyi.SetBytes(bufYY)

    return []*big.Int{xxi, xyi, yxi, yyi}
}

If it's difficult to answer my question could you please recommend which person I can contact, who is responsible for the BLS signature implementation?
I appreciate your contribution to the Kyber library, that's very fascinating stuff. Looking forward to hearing back from you.

P.S. Sorry for the second letter, don't know which email address is better to contact you.

Sincerely,
Denis Davydov
Software Engineer, Secured Finance.

[Allen Jeffrey Richard]

On 4 Feb 2021, at 16:52, ChronosX88 <chron...@gmail.com> wrote:

Oh, thank you very much, Jeff. I think this is what I need. I will try and tell back about results. Thank you again!

Well, I forgot to mention before: It is half of what you need. You would need to do the correct manipulations on the Solidity side to recreate a BN256 point out of the two incoming uint256’s. And in the likely case you need a GT instead of just the G1 point I demonstrated with, you’d need some other uint256’s.

Because I don’t know anything about Solidity nor your application, I’m going to stay out of that side of it. :)

Good luck and please stay in touch.

 -jeff

[Allen Jeffrey Richard]

On 4 Feb 2021, at 19:05, ChronosX88 <chron...@gmail.com> wrote:

So, for decoding the uint256 value I need to reproduce montDecode logic on the Solidity side? Are there any extra steps needed?

I don’t really know, it depends on what format your Solidity implementation of BN256 points needs as input.

  -jeff

[Allen Jeffrey Richard]

On 8 Feb 2021, at 16:10, ChronosX88 <chron...@gmail.com> wrote:

By the way, I want to ask you - what is montEncode/Decode? What is the algorithm inside these functions?

Please reply all, so that the conversation remains on the public mailing list, so that all may benefit. (And maybe you’ll get a better answer from someone else.)

The “mont” in montEncode/Decode refers to the Montgomery form of the curve. There is a binational equivalence between twisted Edwards curves and the Montgomery form. https://en.wikipedia.org/wiki/Montgomery_curve#Equivalence_with_twisted_Edwards_curves 

I’m not too clear on this, but I believe that for performance reasons, the bn256 package from Cloudflare (which Kyber uses) keeps the points in Montgomery form internally. Because the serialisation format for BN256 points for interchange between systems is in Edwards form, the conversation needs to happen each place in the code where the internal form is exposed to the outside. See for example curve.go, line 24, where even just to print the point in string form for debugging the montDecode function is called on a copy of the point.

Again, everything depends on your Solidity implementation. If it uses Montgomery form internally, then you will also need to respect this convention of doing a montEncode during the “unmarshal” operation on the Solidity side where you change the incoming 2 uint256s into one internal point.

  -jeff

[Allen Jeffrey Richard]

On 9 Feb 2021, at 12:00, Allen Jeffrey Richard <jeff....@epfl.ch> wrote:

Again, everything depends on your Solidity implementation.

I said that I didn’t know anything about how Solidity would implement BLS signature checking, but I lied: I knew a tiny bit, enough to make me curious and I started digging. You might already know this, but at least writing down what I found here will help others who are considering this issue, including my colleagues who will be taking over for me after my last day on 18 Feb.

In your GitHub repository is bls-solidity, which includes BLS.sol which calls BN256G1.bn256CheckPairing:

https://github.com/Secured-Finance/bls-solidity/blob/master/contracts/BN256G1.sol#L109

  function bn256CheckPairing(uint256[12] memory input) internal returns (bool) {
    uint256[1] memory result;
    bool success;
    assembly {
      // 0x08     id of the bn256CheckPairing precompile    (checking the elliptic curve pairings)
      // 0        number of ether to transfer
      // 0        since we have an array of fixed length, our input starts in 0
      // 384      size of call parameters, i.e. 12*256 bits == 384 bytes
      // 32       size of result (one 32 byte boolean!)
      success := call(sub(gas(), 2000), 0x08, 0, input, 384, result, 32)
    }
    require(success, "elliptic curve pairing failed");
    return result[0] == 1;
  }

As we can see, that’s basically just a wrapper for a call to the precompiled contract #8 (though it does cast the uint256[12] input into a []byte and a length, set to 384 bytes here). Precompiled contract #8 must be available in all of the verifiers that try to execute this contract. Luckily, precompiled contract #8 was added in the Istanbul hard fork, in 2019:

https://ethereum.stackexchange.com/questions/15479/list-of-pre-compiled-contracts/15483#15483 

https://github.com/ethereum/go-ethereum/blob/master/core/vm/contracts.go#L69

https://github.com/ethereum/go-ethereum/blob/master/core/vm/contracts.go#L531

https://github.com/ethereum/go-ethereum/blob/master/core/vm/contracts.go#L492 

The loop at line 502 takes bytes from input and parses them into BN256 points using newCurvePoint and newTwistPoint, and newCurvePoint just ends up calling bn256.(*G1).Unmarshal:

func newCurvePoint(blob []byte) (*bn256.G1, error) {
p := new(bn256.G1)
if _, err := p.Unmarshal(blob); err != nil {   //  https://github.com/ethereum/go-ethereum/blob/master/crypto/bn256/cloudflare/bn256.go#L129

return nil, err
}
return p, nil
}

So, the bytes in the uint256’s you send in to bn256CheckPairing need to be in the right format so that Unmarshal can read them. If Kyber’s G1 Marshal is compatible with Cloudflare bn256’s Unmarshal, then you’re all set. Now, I happen to know from the history of the code that Kyber’s marshalling and cloudflare/bn256’s marshalling is compatible, because ours is more or less directly derived from theirs. But a little check never hurt anything:

// put this into Kyber’s pairing/bn256/suite_test.go

func TestG1Interop(t *testing.T) {

suite := NewSuite()

k := suite.G1().Scalar().Pick(random.New())

pa := suite.G1().Point().Mul(k, nil)

ma, err := pa.MarshalBinary()

require.Nil(t, err)

g1 := new(bn256.G1)

g1.Unmarshal(ma)

// these should be the same, other than cosmetic differences; they are not. Why not?

t.Log(pa, " =? ", g1)

}

And so, imagine my surprise when that test showed that Kyber’s Marshal and bn256’s Unmarshal are NOT compatible. I’m still looking into that, and I’ll need help from some colleagues too.

  -jeff

[ChronosX88]

I've tried your testing code, and it has somehow worked correctly:

bn256.G1(5dd340bac1fbcc639cc4e0521ba53f33d54400dd144eb4ed22b4a8f87a0af770,8aa2032034c8f9d6a93ef4c6e38563d5519979a090e35a79e4fbbc9fbcf1f0dc)  =?  bn256.G1(5dd340bac1fbcc639cc4e0521ba53f33d54400dd144eb4ed22b4a8f87a0af770, 8aa2032034c8f9d6a93ef4c6e38563d5519979a090e35a79e4fbbc9fbcf1f0dc)

I've used Cloudflare's bn256 library for comparing.

Sincerely,
Denis Davydov
Software Engineer, Secured Finance.

[Gasser Linus]

There is in fact a difference between the golang.org/x/crypto/bn256 and the github.com/cloudflare/bn256 implementation:

  • https://github.com/cloudflare/bn256/blob/master/bn256.go#L129 
and

• https://github.com/golang/crypto/blob/master/bn256/bn256.go#L127

The golang.org doesn’t do the montEncode during unmarshalling, while the cloud flare one does. Looking at marshalling, there is a montDecode in in cloud flare’s implementation, but not in gland’s. And both claim to implement http://cryptojedi.org/papers/dclxvi-20100714.pdf - I couldn’t find which one actually does, or if the paper does not specify if you have to mont(En|De)code during (Un)marshalling.

Also: the golang.org one outputs decimal numbers, so you’ll have to convert them to hex numbers. Then it works. At least for (un)marshalling. As soon as you start calculating, things fail of course. In Jeff’s test you can add the following between the unmarshalling and the t.Log:

g1.Add(g1, g1)
pa.Add(pa, pa)

With g1 from cloud flare’s bn256 implementation, it works. With g1 from golang's implementation, it fails.

So depending on what implementation you have in your solidity contract, it might work - or it might not ;) If you use the kyber library, you’ll have to make sure that the solidity contract does the montEncode in the unmarshalling, so it correctly interprets your points.

Best

Linus

--
You received this message because you are subscribed to the Google Groups "Cothority Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cothority+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cothority/71c248a7-1543-d857-c515-5e357ffc8364%40gmail.com.

[Allen Jeffrey Richard]

On 10 Feb 2021, at 07:58, Gasser Linus <linus....@epfl.ch> wrote:

Also: the golang.org one outputs decimal numbers, so you’ll have to convert them to hex numbers. Then it works.

Thanks, Linus, I totally missed this. Indeed, below is a file you can add to Kyber’s bn256 directory and confirm that inerop works as expected, except for self-adding.

At least for (un)marshalling. As soon as you start calculating, things fail of course. In Jeff’s test you can add the following between the unmarshalling and the t.Log:

g1.Add(g1, g1)
pa.Add(pa, pa)

With g1 from cloud flare’s bn256 implementation, it works. With g1 from golang's implementation, it fails.

This is because Go’s bn256 implementation says this is not supported. See TestG1InteropAddSelf below.

Luckily, this problem will never manifest itself in Ethereum servers, because the way Add is called, even if the two arguments are equal points, they will not be the same exact point in memory because they are constructed via two separate calls to newCurvePoint.

So depending on what implementation you have in your solidity contract, it might work - or it might not ;) If you use the kyber library, you’ll have to make sure that the solidity contract does the montEncode in the unmarshalling, so it correctly interprets your points.

Yes, for self-adding, but that’s the only operation we are aware of where it’s a problem (and as mentioned above, it’s not a problem you’d see in production).

While I was investigating this, I wrote up the following, which is still true but not really related to my findings: I left it here because it’s interesting: The bn256 implementation used by Ethereum differs based on the architecture. It uses Cloudflare if possible (amd64, arm64) and the Go project’s one otherwise. If there are other divergences between them, this is going to cause you real headaches to debug why some verifiers cannot verify your contract.

Anyway, Denis, carry on; as I recall the next step is for you to put the 64 bytes you get out of Kyber’s MarshalBinary into two Solidity uint256’s and then see if the bn256 points you end up with inside of the Ethereum verifier are the ones you were expecting from Kyber.

Stay in touch!

  -Jeff

----- interop_test.go ---- 

package bn256

import (

"testing"

"github.com/stretchr/testify/assert"

"github.com/stretchr/testify/require"

"go.dedis.ch/kyber/v3/util/random"

cbn256 "github.com/cloudflare/bn256"

gbn256 "golang.org/x/crypto/bn256"

)

// Test that a point that is transferred from Kyber to both

// Go"s bn256 and cloudflare's bn256 end up the same point on

// arrival.

func TestG1Interop(t *testing.T) {

suite := NewSuite()

k := suite.G1().Scalar().Pick(random.New())

pa := suite.G1().Point().Mul(k, nil)

ma, err := pa.MarshalBinary()

require.Nil(t, err)

g1g := new(gbn256.G1)

g1g.Unmarshal(ma)

g1c := new(cbn256.G1)

g1c.Unmarshal(ma)

// Check for equality in a cycle, a == b == c == a.

require.Equal(t, ma, g1g.Marshal())

require.Equal(t, g1g.Marshal(), g1c.Marshal())

require.Equal(t, g1c.Marshal(), ma)

}

// Test that adding a point in the 3 implementations

// all results in the same point afterwards.

func TestG1InteropAddBase(t *testing.T) {

suite := NewSuite()

k := suite.G1().Scalar().Pick(random.New())

pa := suite.G1().Point().Mul(k, nil)

ma, err := pa.MarshalBinary()

require.Nil(t, err)

base := suite.G1().Point().Base()

b, err := base.MarshalBinary()

require.Nil(t, err)

pa.Add(pa, base)

ma2, err := pa.MarshalBinary()

require.Nil(t, err)

g1g := new(gbn256.G1)

g1g.Unmarshal(ma)

bg := new(gbn256.G1)

bg.Unmarshal(b)

g1g.Add(g1g, bg)

g1c := new(cbn256.G1)

g1c.Unmarshal(ma)

bc := new(cbn256.G1)

bc.Unmarshal(b)

g1c.Add(g1c, bc)

require.Equal(t, g1c.Marshal(), ma2)

require.Equal(t, g1g.Marshal(), g1c.Marshal())

require.Equal(t, ma2, g1g.Marshal())

}

// Test like above, but using "add to self" instead

// of "add base onto the random point"; this confirms

// that Go's bn256.(*G1).Add does not work correctly

// in this case.

func TestG1InteropAddSelf(t *testing.T) {

suite := NewSuite()

k := suite.G1().Scalar().Pick(random.New())

pa := suite.G1().Point().Mul(k, nil)

ma, err := pa.MarshalBinary()

require.Nil(t, err)

pa.Add(pa, pa)

ma2, err := pa.MarshalBinary()

require.Nil(t, err)

g1g := new(gbn256.G1)

g1g.Unmarshal(ma)

// The docs say:

// Warning: this function is not complete, it fails for a equal to b.

g1g.Add(g1g, g1g)

g1c := new(cbn256.G1)

g1c.Unmarshal(ma)

g1c.Add(g1c, g1c)

// this one is ok:

assert.Equal(t, g1c.Marshal(), ma2)

// known to fail

assert.Equal(t, ma2, g1g.Marshal())

// known to fail

assert.Equal(t, g1g.Marshal(), g1c.Marshal())

}

[Gasser Linus]

At least for (un)marshalling. As soon as you start calculating, things fail of course. In Jeff’s test you can add the following between the unmarshalling and the t.Log:

g1.Add(g1, g1)
pa.Add(pa, pa)

With g1 from cloud flare’s bn256 implementation, it works. With g1 from golang's implementation, it fails.

This is because Go’s bn256 implementation says this is not supported. See TestG1InteropAddSelf below.

Oh my - didn’t go this far. Thanks for checking this out. So the go-bn256 _does_ correctly unmarshal the kyber-bn256? Because the ‘mountEncode’ is not in there, so I’m quite surprised.

From the curve25519/ed25519 I know that the two representations used in the curve have a multiplier, which starts at 1. So if you don’t do any operations, the two representations are the same! If I had time, I’d try out to create a ‘dirty’ kyber-bn256-point that already has some operations done to it (addition, inversion, …) and then kyber-marshal and go-unmarshal it, and redo some operations in both and see if the results are the same. I’m just surprised that it works without the ‘mountEncode’…

Linus

[Allen Jeffrey Richard]

On 12 Feb 2021, at 07:12, Gasser Linus <linus....@epfl.ch> wrote:

Oh my - didn’t go this far. Thanks for checking this out. So the go-bn256 _does_ correctly unmarshal the kyber-bn256? Because the ‘mountEncode’ is not in there, so I’m quite surprised.

Keeping the point in Montgomery form internally is an optimisation used in the Cloudflare implementation. It’s an implementation choice what internal form you hold the point in. Because the Go bn256 aims for the simplest code, but not the fastest, it avoids the need to convert the point in import and export.

  -Jeff

[Gasser Linus]

>
> Keeping the point in Montgomery form internally is an optimisation used in the Cloudflare implementation. It’s an implementation choice what internal form you hold the point in. Because the Go bn256 aims for the simplest code, but not the fastest, it avoids the need to convert the point in import and export.
>
> -Jeff

OK, now I get it: and because you use `MarshalBinary` when testing for equal or when printing, it all works out. Nice.

Linus

[ChronosX88]

Guys, what is twistB constant in bn256/twist.go?

var twistB = &gfP2{
    gfP{0x75046774386b8d71, 0x5bd0854a46d36cf8, 0x664327a1d41c8414, 0x96c9abb932eeb2f},
    gfP{0xb94f760fb4c5ee14, 0xdae9f8f24c3b6eb4, 0x77a675d2e52f4fe4, 0x736f31b09116c66b},
}

P.S. It is used for checking if G2 point is on curve. So I need to know what this constant does mean.

Sincerely,
Denis Davydov
Software Engineer, Secured Finance.

[Allen Jeffrey Richard]

There are comments in twist.go (of both the Cloudflare and the Go implementation) that explain this, at least a bit. The base-10 form of the constant in the Go implementation is slightly less mysterious. The Cloudflare guys just evidently executed that base 10 conversion themselves to make the package init code more efficient.

The “IsOnCurve” function calculates y^2, and also the other side of the equation, x^3 + 3/ξ, then checks the two sides for equality. Thus apparently the constant twistB is whatever this 3/ξ term is. I do not understand this math well enough to explain it to you beyond that, unfortunately.

Here are some hints anyway… both the Cloudflare and Go package claim to implement the algorithm in https://cryptojedi.org/papers/dclxvi-20100714.pdf. The term 3/ξ is introduced on page 5 of that paper, where it says that this sextic twist is well known from 3 previous papers. Perhaps one of those papers explains it.

Good luck and stay in touch. Be sure to ask on the list, because after Thursday I won’t be working on this stuff anymore.

  -jeff