Message Generators Creation Method

[BasileiosKal]

Since the consensus seems to be to move to global fixed message generators shared between issuers (see #19 ) the next step would be to decide how to create those generators. Opening this issue to create some discussion around possible proposals. My understanding is that they will be deterministically generated by a common seed (created from some nothing-up-my-sleeve value).

I would also propose for the process to be such that it will create a strong binding between index and generator (i.e., something like hash-to-curve(seed, dst, index)) to help with indexing in applications and avoiding ambiguities.

[tplooker]

@mikelodder7 I think last time we chatted you potentially had a good proposal for how this could be done?

[mikelodder7]

Here's my proposal

1. Set the global domain separator to be GLOBAL_DST='BBS_SETUP_GENERATOR_IKM_1_0_0\0\0\0' read as 32 bytes.
2. Decide on a nothing up my sleeve value for the GLOBAL_SEED like some Shakespeare poem or quote.
3. Hasher = SHAKE256(GLOBAL_DST, GLOBAL_SEED)

Calculate the generators as follows

4. Set the generator DST=BBS_BLS12381G1_XOF:SHAKE-256_SSWU_RO_
5. Set generators to empty collection
6. for i < num_generators
7. tv = Hasher.Read(64) // Read out 64 bytes from XOF
8. generators[i] = Hash2Curve(tv, DST)
9. output generators

The advantage of this approach is if we determine the global approach to be insecure we change the GLOBAL_SEED to be the signer's public key leaving all else the same. If we change curves then DST is updated to reflect that in the name.

[tplooker]

A couple of things we will need to generalise in spec text is the underlying curve and subgroup, note the current tool is coupled to BLS12-381

[mikelodder7]

Sure but the curve can easily be swapped

[tplooker]

Yeap agreed, just taking a note so we don't loose track of it

[BasileiosKal]

+1 for that method.

[mikelodder7]

Add a check for point at infinity and the base generator.

[andrewwhitehead]

Can hash-to-curve return infinity? 🤔

[mikelodder7]

With very small odds 1/2^256. It’s nice to check for it in case an attacker inserts one

[tplooker]

Could we generalize this to check other generators other than just these? e.g what about the generator used for the blinding factor?

[tplooker]

@mikelodder7 is this ready for a PR?

[tplooker]

If so would you be willing to contribute one?

[mikelodder7]

Yea it is. I can contribute one

[tplooker]

@mikelodder7 bump on this one, I think it should be defined under operations, generically (e.g agnostic of the underlying curve). Then the specific cipher suite can profile it

[tplooker]

I've opened #71 in an attempt to move this issue forward.

[andrewwhitehead]

I think there's one improvement we could make here to improve efficiency. At the moment the assumption seems to be that we reject infinity and the default generator by proceeding to the next XOF hash output, but that implies that we have to perform hash-to-curve for every previous generator in order to rule out those values. Instead, I think we should handle the infinity and default generator cases by initializing a new XOF based on the previous output (I'm not sure if cloning the current hash state and adding more input is widely supported). This has the advantage that in order to access generator 20, for example, you only need to advance the XOF output 20 times and can skip 20 hash-to-curve operations, which are much more expensive.

[mikelodder7]

I don’t see how that’s more efficient since you already read those out anyway with the current construction. The checking for infinity and base point is for the security proof. The odds of this happening in practice is 2^-256

[andrewwhitehead]

Okay so we're not going to reject those points when creating the generators? It is very unlikely to happen.

[mikelodder7]

No you would still reject them but the odds of it actually happening is Incredibly low

[mikelodder7]

Also the current algorithm already allows you just read out to generator 20 without having to do 20 hash to curves

[andrewwhitehead]

It seems like it only lets you do that if you assume that all the previous points were accepted. Although I'm not sure now what it means to reject a point. Maybe we can add that to the algorithm.

[tplooker]

Also the current algorithm already allows you just read out to generator 20 without having to do 20 hash to curves

Yeah I think the point here that @andrewwhitehead is raising is what if one of the generators between 1 and 19 evaluated to infinity so the algorithm had to recompute a generators, in this case strictly the 20th generator is actually the 19th but to be sure you have to compute all in order.

[tplooker]

Wouldn't modifying this algorithm in the way you describe @andrewwhitehead also make the generator computation fully parallelizable?

[mikelodder7]

I’m not seeing how since it still depends on the previous value

[tplooker]

In the proposal made by andrew it would mean the current generator computation would always know which bytes to start with for its hash to curve operation there would never be the potential for "bad" generators that came before it (e.g bytes drawn from the XOF that when hashed to curve, evaluated to infinity).

I think the tradeoff we are playing with here is the efficiency of re-initializing the XOF function per-generator and skipping to read a certain set of bytes vs the algorithm as it is described above.

[andrewwhitehead]

@tplooker Good point on the parallelization, you would still need to go through the hash output of course but it would give more options if points did not depend on previous hash-to-curve outputs.