Git Product home page Git Product logo

Comments (15)

mcarrickscott avatar mcarrickscott commented on July 21, 2024

from core.

mallochine avatar mallochine commented on July 21, 2024

Compiled, but got an unexpected result.

Are you familiar with herumi/bls?

Is there anything like the "evaluatePolynomial" that is in herumi/bls? Because that's where the ECP2 * FP appears.

https://github.com/herumi/mcl/blob/0114a3029f74829e79dc51de6dfb28f5da580632/include/mcl/lagrange.hpp#L64

/*
	out = f(x) = c[0] + c[1] * x + c[2] * x^2 + ... + c[cSize - 1] * x^(cSize - 1)
	@retval 0 if succeed else -1 (if cSize == 0)
*/
template<class G, class T>
void evaluatePolynomial(bool *pb, G& out, const G *c, size_t cSize, const T& x)
{
	if (cSize == 0) {
		*pb = false;
		return;
	}
	if (cSize == 1) {
		out = c[0];
		*pb = true;
		return;
	}
	G y = c[cSize - 1];
	for (int i = (int)cSize - 2; i >= 0; i--) {
		G::mul(y, y, x);
		G::add(y, y, c[i]);
	}
	out = y;
	*pb = true;
}

from core.

mcarrickscott avatar mcarrickscott commented on July 21, 2024

from core.

mallochine avatar mallochine commented on July 21, 2024

Regarding calling code, I have taken notes on those indeed. They are

https://github.com/herumi/bls-go-binary/blob/master/bls/bls.go#L457

// Set --
func (pub *PublicKey) Set(mpk []PublicKey, id *ID) error {
  // #nosec
  ret := C.blsPublicKeyShare(&pub.v, &mpk[0].v, (C.mclSize)(len(mpk)), &id.v)
  if ret != 0 {
    return fmt.Errorf("err blsPublicKeyShare")
  }
  return nil
}

https://github.com/herumi/bls/blob/4ae022a6bb71dc518d81f22141d71d2a1f767ab3/src/bls_c_impl.hpp#L567

int blsPublicKeyShare(blsPublicKey *pub, const blsPublicKey *mpk, mclSize k, const blsId *id)
{
  bool b;
  mcl::evaluatePolynomial(&b, *cast(&pub->v), cast(&mpk->v), k, *cast(&id->v));
  return b ? 0 : -1;
}

from core.

mallochine avatar mallochine commented on July 21, 2024

The structs are defined here, where Fr is just FP without a modulo (is that the same thing as BIG?)

https://github.com/herumi/bls/blob/8b240cf9f80c9b3c20d05ecab74b086065e72b31/include/bls/bls.h#L60

typedef struct {
	mclBnFr v;
} blsId;

typedef struct {
#ifdef BLS_ETH
	mclBnG1 v;
#else
	mclBnG2 v;
#endif
} blsPublicKey;

https://github.com/herumi/mcl/blob/0114a3029f74829e79dc51de6dfb28f5da580632/include/mcl/bn.h#L96

typedef struct {
  mclBnFp x, y, z;
} mclBnG1;

typedef struct {
  mclBnFp2 x, y, z;
} mclBnG2;

from core.

mallochine avatar mallochine commented on July 21, 2024

seems to me like I've reached a deadend, where miracl/core simply doesn't do the same thing as herumi/bls

You have no idea how sad this makes me.

from core.

mallochine avatar mallochine commented on July 21, 2024

This is Fr, maybe this explains the problem:

#ifndef MCLBN_FP_UNIT_SIZE
	#error "define MCLBN_FP_UNIT_SIZE 4(, 6 or 8)"
#endif
#ifndef MCLBN_FR_UNIT_SIZE
	#define MCLBN_FR_UNIT_SIZE MCLBN_FP_UNIT_SIZE
#endif

/*
	G1 and G2 are isomorphism to Fr
*/
typedef struct {
	uint64_t d[MCLBN_FR_UNIT_SIZE];
} mclBnFr;

from core.

mcarrickscott avatar mcarrickscott commented on July 21, 2024

from core.

mallochine avatar mallochine commented on July 21, 2024

Hey, reading through milagro_bls gave me new ideas for where things could be going wrong! Thanks!

Basically I think I was using the wrong mul!

herumi/bls uses:

		G::mul(y, y, x);
		G::add(y, y, c[i]);

That a group mul, which means the function I should've been using was "G2mul" in PAIR.go

from core.

mallochine avatar mallochine commented on July 21, 2024

OK sorry to trouble you so far for the questions! If you have a minute to quickly answer -- is "ECP2.Add" (ECP2.go) the same thing as G::add? Just a sanity check...

from core.

mallochine avatar mallochine commented on July 21, 2024

I have in my notes from corresponding with herumi that the naive algorithm for mul and add should be:

The naive algorithm is (x + y) % r and (x * y) % r.

from core.

mcarrickscott avatar mcarrickscott commented on July 21, 2024

from core.

mallochine avatar mallochine commented on July 21, 2024

HUGE THANKS TO YOU Michael Scott! For helping illuminate the math behind what's going on here.

The final root cause analysis

  1. ECP2.mul definitely the wrong function to use. Should've been G2mul
  2. FP.mul and FP.add were also the wrong functions, should've been Modmul, Modadd using the CURVE_Order as you so greatly pointed out.

Want me to contribute open source code for this?

It would be the miracl/core port of herumi/bls "blsPublicKeyShare", "PublicKey.Set", "SecretKey.Set". I don't think you have this code in there yet.

It looks like this:

func (sk *SecretKey) Set(msk []SecretKey, id *ID) error {
  if len(msk) == 0 {
    return errors.New("No secret keys given.")
  }
  if len(msk) == 1 {
    sk.v = msk[0].CloneFP()
    return nil
  }
  sk.v = msk[len(msk)-1].CloneFP()

  m := BN254.NewBIGints(BN254.CURVE_Order)
  sk0 := sk.v.GetBIG()
  id0 := id.v.GetBIG()

  for i := len(msk) - 2; i >= 0; i-- {
    sk0 = BN254.Modmul(sk0, id0, m)
    sk0 = BN254.Modadd(sk0, msk[i].v.GetBIG(), m)
  }

  sk.v = BN254.NewFPbig(sk0)

  return nil
}
func (pk *PublicKey) Set(pks []PublicKey, id *ID) error {
  pk.v = BN254.NewECP2()
  if len(pks) == 0 {
    return errors.New("No secret keys given.")
  }
  pk.v.Copy(pks[len(pks)-1].v)
  if len(pks) == 1 {
    return nil
  }
  for i := len(pks) - 2; i >= 0; i-- {
    pk.v = BN254.G2mul(pk.v, id.v.GetBIG())
    pk.v.Add(pks[i].v)
  }
  return nil
}

from core.

mcarrickscott avatar mcarrickscott commented on July 21, 2024

from core.

mallochine avatar mallochine commented on July 21, 2024

OK, that's fine, but feel free to ping me anytime for questions about how herumi/bls implemented Set for PublicKey and SecretKey!

SecretKey was FP, PublicKey was ECP2 (i.e. G2).

from core.

Related Issues (20)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.