"BLS12381G1_XMD:BLAKE2B_SSWU_RO_"

[chris-matichuk-ts]

It would be nice to be able to provide a custom hash routine to support other algorithms, such as "BLS12381G1_XMD:BLAKE2B_SSWU_RO_" for BBS+. OpenSSL includes support for "blake2b512".

Also looks like blake2b might make it into both Ethereum and Zcash. My interest is more around BBS+ though.
ethereum/EIPs#2129

Whatever the case, an option to use blake2b512 would be a nice addition.

Looking over expand_message_xmd in https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-10.html

[mratsim]

Blake2b was the initial hashing algorithm chosen for Eth2 but it was removed in favor of SHA256 for a couple reasons:

• By necessity, the hash function of Eth2 needed to be accessible in Eth1 and so needed to have a dedicated EVM opcode. At the time (2018) there was one for SHA256 but none for Blake2b.
• While Blake2b is faster than SHA256 on 64-bit CPU, we considered that SHA256 was more widespread and also had more hardware acceleration in place. Though at the time we didn't realize that Intel (SHA-NI) and Raspberry Pi didn't offer SHA256 acceleration (but Ryzen and all other ARM CPUs do)

@JustinDrake can likely expand more if I missed something. I don't think there is a plan to use Blake2b anywhere in the base Ethereum or Ethereum 2 protocol nowadays.

Note: I am not against allowing custom hash functions and suites. But Ethereum will not use Blake2b+BLS at scale AFAIK. Can't comment on Zcash.

[JustinDrake]

@JustinDrake can likely expand more if I missed something

A big one is standardisation within the blockchain space. The vast majority of blockchains (~90%) use SHA256 as their base hash function.

[chris-matichuk-ts]

Got it...makes sense. Thanks for the feedback.

For some reason the verifiable credential (and W3C) - including things like the emerging vax passport - are all heading to BBS+, and for some reason BBS+ decided to switch out sha256 for blake2b. I guess that is frustrating...because the only base libraries are in things like GO...nothing in C (I need C for what I'm trying to do).

○ https://w3c-ccg.github.io/ldp-bbs2020
○ https://mattrglobal.github.io/bbs-signatures-spec
○ https://github.com/mattrglobal/ffi-bbs-signatures
○ https://www.lfph.io/wp-content/uploads/2021/02/Verifiable-Credentials-Flavors-Explained.pdf

The last link above is for the COVID-19 credential...which is where I'm trying to head...which is using BBS+, which is "BLS12381G1_XMD:BLAKE2B_SSWU_RO_", and thus I'm trying to figure out a baseline BLS12381 starting point in C.

Odd that BBS+ is going with blake2b given your comments. I guess that was Mattr that did that...as their solution is what became BBS+....after some tweaks to what they originally implemented (as I understand from a clip from the crypto person at Evernym).

For BLS code base, I implemented MCL....was ok...but I wasn't completely satisfied. Considered the CHIA codebase...but instead moved to this BLST code base...took about a day to get everything working...and I think I could do what I need with BLST.

But will require that I replace the hash, unfortunately -> clearly I will loose all the great optimizations (which I'm getting some understanding of by having to replace the hashing) - but just looking for some starting point to start working on BBS+.

Maybe someone smarter than I could contact the BBS+ community...maybe W3C...and convince them to abort blake2b and stick with sha256....

[chris-matichuk-ts]

I have something that appears to work (where I replaced the sha256 with the OpenSSL one for just the "verify", but used the original for the sign) and it works for that. Just have 1 clarification to verify this will work for hash methods that generate 64 bytes of data.

From: https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-10.html#name-expand_message_xmdsha-256-2

The number of bits output by H MUST be b >= 2 * k, for k the 
target security level in bits, and b MUST be divisible by 8. The 
first requirement ensures k-bit collision resistance; the second 
ensures uniformity of expand_message_xmd's output.

QUESTION: Given that bls12-381 targets the 128-bit security level, I assume that even if the sha512 or black2b512 generates 64 bytes that only the first 32 bytes of the hash should be used in the expand_message_xmd command. Is this correct?

Assuming this is the case, than I have the following working. Which I'm sure there's a better way to do this...but this provides a starting point solution. I also tried with blake2b512, and the sign/verify worked...I just don't know if my above assumption is correct...if it is, than this changes should be ok to use either sha512 or blake2b512.

Have the caller fill out the following structure and pass it into any routine that ends up calling expand_message_xmd.

typedef struct {
    void* ctx;
    void(*d_init)(void* cb);
    void(*d_update)(void* cb, const void* _inp, size_t len);
    void(*d_final)(void* cb, unsigned char* md, size_t size, size_t *outlen);
} DIGEST_CB;
```

Assuming this structure is passed in as DIGEST_CB* cb is passed in, such as the following:
```
static void expand_message_xmd(unsigned char *bytes, size_t len_in_bytes,
                               const unsigned char *aug, size_t aug_len,
                               const unsigned char *msg, size_t msg_len,
                               const unsigned char *DST, size_t DST_len,
                               DIGEST_CB* cb)
```

Use the following instead for the oversize code section:

``
    size_t outlen;

     if (cb)
     {
        if (DST_len > 255)
        {
            cb->d_init(cb);
            cb->d_update(cb, "H2C-OVERSIZE-DST-", 17);
            cb->d_update(cb, DST, DST_len);
            cb->d_final(cb, (unsigned char*)b_0.c, 32, &outlen);
            DST = b_0.c, DST_len = 32;
        }
    }
```

And use the following for the hash section:

```
    if (cb)
    {
        unsigned char buf[64];
        vec_zero(buf, sizeof(buf));
        cb->d_init(cb);
        cb->d_update(cb, buf, sizeof(buf));
        cb->d_update(cb, aug, aug_len);              /* | aug | */
        cb->d_update(cb, msg, msg_len);              /* | msg | */
         /* | I2OSP(len_in_bytes, 2) || I2OSP(0, 1) || DST_prime    */
        b_i.c[30] = (unsigned char)(len_in_bytes >> 8);
        b_i.c[31] = (unsigned char)(len_in_bytes);
        b_i.c[32] = 0;
        cb->d_update(cb, b_i.c + 30, 3 + DST_len + 1);
        cb->d_final(cb, (unsigned char*)b_0.c, 32, &outlen);

        cb->d_init(cb);
        cb->d_update(cb, b_0.c, 32);
        vec_copy(b_i.c, b_0.c, 32);
        ++b_i.c[32];
        cb->d_update(cb, b_i.c + 32, 1 + DST_len + 1);
        cb->d_final(cb, bytes, 32, &outlen);

        len_in_bytes /= 32; /* divisible by 64, remember? hence 32 works too */
        while (--len_in_bytes) {
            cb->d_init(cb);
            vec_xor(b_i.c, b_0.c, bytes, 32);
            cb->d_update(cb, b_i.c, 32);
            bytes += 32;
            ++b_i.c[32];
            cb->d_update(cb, b_i.c + 32, 1 + DST_len + 1);
            cb->d_final(cb, bytes, 32, &outlen);
        }
    }

[dot-asm]

@chris-matichuk-ts

@mratsim @JustinDrake

You have to recognize that neither Mamy or Justin actually maintain the blst code, so it's not exactly appropriate to throw all kind of questions at them. I mean explicit tag[s] kind [of] implies that answer is expected from the tagged person[s], but the said expectation is not necessarily warranted:-)

Another thing to recognize is that explicit goal of the project is to cover specific specs and validate the implementation for conformance. This doesn't mean that nothing else is possible, but it does mean that there will be some resistance to suggestions outside the mentioned drafts. With this in mind, allow me to read up a little, and get back with more meaningful answers, suggestions, counter-suggestions, ...

Cheers.

[chris-matichuk-ts]

Ok...my apologies.

Ultimately my interest is something that could be applied to the following:

• https://mattrglobal.github.io/bbs-signatures-spec/
• https://w3c-ccg.github.io/ldp-bbs2020/
• https://www.lfph.io/wp-content/uploads/2021/02/Verifiable-Credentials-Flavors-Explained.pdf

But point taken...maybe this is just the wrong forum for this.

And I can delete this entire thread if it is inappropriate in this forum.

[dot-asm]

QUESTION: Given that bls12-381 targets the 128-bit security level, I assume that even if the sha512 or black2b512 generates 64 bytes that only the first 32 bytes of the hash should be used in the expand_message_xmd command. Is this correct?

No. expand_message_xmd is specified to not truncate hash function's output. In other words, in this case, if we needed just one 512-bit element, and hash function produced 512 bits, the while loop wouldn't execute. Modulo reduction does kind of "truncation" in hash_to_field, but not nothing of the sort takes place in expand_messge_xmd.

[dot-asm]

I also tried with blake2b512, and the sign/verify worked...

What does it mean? If that signature produced with modified code was verified by modified code, then it doesn't actually mean that it worked. It takes comparison to a known/recognized test vector, or at least to other programs.

[dot-asm]

static void expand_message_xmd(unsigned char *bytes, size_t len_in_bytes,
                               const unsigned char *aug, size_t aug_len,
                               const unsigned char *msg, size_t msg_len,
                               const unsigned char *DST, size_t DST_len,
                               DIGEST_CB* cb)

I'd have to say no. For starters, it's insufficient, because [the] suggestion doesn't take into account hash function's output length (per #68 (comment)). However, I'm not actually suggesting to put an effort into resolving this, because taking this route asks for further questions. I'd argue that it would be more appropriate to allow masking the expand_message_xmd at build time and make it application's responsibility to implement it in its entirety. To be more specific, imagine blst could be compiled with say -Dexpand_message_xmd=bbs_expand_message_xmd, in which case your application would need to provide bbs_expand_message_xmd... Thoughts?

[dot-asm]

• https://mattrglobal.github.io/bbs-signatures-spec/

Man, this like worst spec I've seen... For example what does w || I2OSP(0, 1) mean? There is nothing suggesting that w is used to denote a byte string, so how do you append a byte string to it? Or h_i * msg_i? How do you multiply a point by a byte string? ...

Anyway, it sounds like there is need for constant-time inversion modulo curve order. Well, I was planning to add it anyway... And reduction modulo curve order would be needed, right? What else?

[chris-matichuk-ts]

I also tried with blake2b512, and the sign/verify worked...

What does it mean? If that signature produced with modified code was verified by modified code, then it doesn't actually mean that it worked. It takes comparison to a known/recognized test vector, or at least to other programs.

No test vector...so you are correct, I don't know that it "works"...only know that the sign/verify works if the same assumption of truncating the 64byte hash result to 32byte hash result on blake2b512 is used for both the sign and verify. You've answered my question...if the hash algorithm provides 64 bytes, than use the 64 bytes.

[chris-matichuk-ts]

I'd have to say no. For starters, it's insufficient, because [the] suggestion doesn't take into account hash function's output length (per #68 (comment)). However, I'm not actually suggesting to put an effort into resolving this, because taking this route asks for further questions. I'd argue that it would be more appropriate to allow masking the expand_message_xmd at build time and make it application's responsibility to implement it in its entirety. To be more specific, imagine blst could be compiled with say -Dexpand_message_xmd=bbs_expand_message_xmd, in which case your application would need to provide bbs_expand_message_xmd... Thoughts?

That would work...the person using the blst library could provide their own expand_message_xmd. This might be the easiest way to provide a way to allow people to reuse this library with other hash algorithms (where the original function could be copied and modified as needed...only functions it calls are vec_zero, vec_copy, and vec_xor, which can be also copied ).

The other approach (which as you point out might result in more questions to answer), the hash command gets a 64byte block to fill and returns the amount filled, and the expand_message_xmd then accomodates either 32bytes or 64bytes...whatever is returned.

As an aside, this is what I used for the callback for black, using OpenSSL. The constant EVP_MAX_MD_SIZE is actually 64 bytes, and memory allocated for that, and how much is filled in is returned by the EVP_DigestFinal_ex routine. This approach could also be used in that expand_message_xmd could use the length of the hash output.

But again...maybe your approach just makes it easier or less complicated for the intent of this library, which is not so much for it to be used for things other than Eth2/FileCoin - but gives a way if people want to.

void _blake2b512_init(void* cb)
{
int err = EVP_DigestInit_ex((EVP_MD_CTX*)((blst::DIGEST_CB*)cb)->ctx, EVP_get_digestbyname("blake2b512"), NULL);
}
void _blake2b512_update(void* cb, const void* _inp, size_t len)
{
int err = EVP_DigestUpdate((EVP_MD_CTX*)((blst::DIGEST_CB*)cb)->ctx, _inp, len);
}
void _blake2b512_final(void* cb, unsigned char* md, size_t size, size_t* outlen)
{
unsigned int len2 = EVP_MAX_MD_SIZE;
unsigned char buf[EVP_MAX_MD_SIZE];
int err = EVP_DigestFinal_ex((EVP_MD_CTX*)((blst::DIGEST_CB*)cb)->ctx, buf, &len2);
len2 = size > len2 ? len2 : size;
if (outlen) *outlen = len2;
memcpy(md, buf, len2);
}

[chris-matichuk-ts]

Man, this like worst spec I've seen... For example what does w || I2OSP(0, 1) mean? There is nothing suggesting that w is used to denote a byte string, so how do you append a byte string to it? Or h_i * msg_i? How do you multiply a point by a byte string? ...

First...a side note...I'm doing this more for learning BBS+, so if this is all consuming valuable time, I'm perfectly fine if none of this get's responded to...I'll just keep trying things until I figure something out.

See 3.4, SkToPk where w is defined as "SK*P2". I am using blst_sk_to_pk_in_g2 to calculate w. I assume that w || I2OSP(0, 1) means appending a single 0 byte to the blst_p2_compress version of w.

h0, h[i] are defined in 3.4 as well, based on hash_to_curve_g1. I am using blst_hash_to_g1 for this.

For "P1 + h0 * s + h_i * msg_i + ... + h_n * msg_n", I am currently assuming P1 is blst_p1_generator.

For "A =b * (1 / (SK + e))", I am currently assuming that I use a bigint add of SK+e (but I suspect this might be wrong), and then use blst_fr_eucl_inverse for the inversion, and than blst_p1_mult....to get A. Again...I don't know if I'm interpreting this correctly.

For the verify, "C1 = e(A, w * P2 ^ e)" and "C2 = e(b, P2)" and "return C1 == C2", I don't yet know how to interpret this in relation to the blst_pairing routines.

At some point in this I'm probably going to reach out to the Mattr folks...but I wanted to get a little further along before I do that.

[dot-asm]

The other approach...

The special thing about blst is that it is self-contained and has no external dependencies. Not even on libc! Yes, no memcpy, or memcmp, or anything of the sort(*). This is not going to change, which naturally limits which approaches would be acceptable.

(*) Well, compilers were observed to generate calls to builtins, but it's on them.

[dot-asm]

I assume that w || I2OSP(0, 1) means appending a single 0 byte to the blst_p2_compress version of w.

It has to be actually spelled in specification. That's why it's called "specification." There should be no room for assumptions. Otherwise it's just "musings" rather than "specification."

For "P1 + h0 * s + h_i * msg_i + ... + h_n * msg_n", I am currently assuming P1 is blst_p1_generator.

And then? You can't multiply point by msg_i without spelling how to convert msg_i to a scalar. I would imagine that hashing the message and then reducing big-endian representation modulo curve order could be a way, but again, it may not be left to imagination.

blst_fr_eucl_inverse for the inversion,

Trouble is that since SK is involved, it better be handled in constant-time. And the subroutine in question is not.

"C1 = e(A, w * P2 ^ e)" and "C2 = e(b, P2)" and "return C1 == C2"

First of all, "w*P2^e" ought to be w+P2*e. Or P2*(SK+e) if you wish. As for C1==C2, it's kind of a trick question. The trouble is that customarily you don't calculate actual C1 and C2 and compare. Because it involves an expensive operation, a.k.a. final exponentiation, and if you were to actually calculate both, you'd have to perform two such operations, while there is a way to check for equality by performing just one. This part is embedded in blst_pairing_finalverify. Intermediate Ci values, intermediate in sense "without final exponentiation," can be calculated with blst_miller_loop, but blst_pairing_finalverify accepts only one "naked" fp12 input... Application can do what blst_pairing_finalverify does at its end, but one can argue that it would appropriate if blst had an interface accepting pair of blst_miller_loop outputs... I have to ponder a bit more...

[chris-matichuk-ts]

You can't multiply point by msg_i without spelling how to convert msg_i to a scalar. I would imagine that hashing the message and then reducing big-endian representation modulo curve order could be a way, but again, it may not be left to imagination.

Good point. I was assuming using the raw msg_i data. The doc references them as using the octet strings of the messages, and does not specify any other transformation.

For "w", it defines a DPK output as a point_to_octets_min of w, which is the compressed version.

Looks like there are a few things where it would be good for Mattr to clarify.

I located where the first public BBS+ implementation exists...but it is in Rust, which is not the language that I need...but maybe that can help in interpreting the "spec". https://github.com/hyperledger/ursa/tree/main/libzmix/bbs/src

[chris-matichuk-ts]

I assume that w || I2OSP(0, 1) means appending a single 0 byte to the blst_p2_compress version of w.

https://github.com/hyperledger/ursa/blob/main/libzmix/bbs/src/keys.rs
Line 243

For the w, they are using serialize (10 + G2_UNCOMPRESSED_SIZE). This also was not in the spec. If it had indicated using point_to_octets_norm, that would have cleared it up.

Side note: the comment there indicates using sha256...but their spec indicates using blake2b. Maybe they changed but didn't update the comment in the code.

I have some things I can raise with Mattr.

"C1 = e(A, w * P2 ^ e)" and "C2 = e(b, P2)" and "return C1 == C2"

Their verify is here where they implement the pairing:
https://github.com/hyperledger/ursa/blob/main/libzmix/bbs/src/signature.rs
Line 277

[chris-matichuk-ts]

imagine blst could be compiled with say -Dexpand_message_xmd=bbs_expand_message_xmd, in which case your application would need to provide bbs_expand_message_xmd

The program using the library would likely need a way to use multiple different hash algorithm depending on the function...and not just locking into a single hash algorithm. In my case, I would use both sha256 and blake2b512 with the same blst library. So if I ended up providing my own expand_message_xmd, than I would still need a way to signal to the custom expand_message_xmd routine which hash algorithm to use.

It could be just looking at DST...but that assumes that in all cases DST will include the hash name....maybe that might be the case...I don't know. Definitely would not want to use some global...would need to support threads. So either would depend on DST or would need to add a parameter for a user provided data block...but then would need to still modify all the related routines to include that user data block as an optional parameter. Easier to assume DST will always include the name of the hash I suppose.

[dot-asm]

In my case, I would use both sha256 and blake2b512 with the same blst library. So if I ended up providing my own expand_message_xmd, than I would still need a way to signal to the custom expand_message_xmd routine which hash algorithm to use.

Or alternate between sha256 and blake2b512 in your own expand_message_xmd. As soon as you invest into own subroutine, it's not that complicated. Again, given the specific goals of the project, there are things that are not going to happen. Well, at least not upon a [would-be-nice] request on github:-)

[dot-asm]

I was assuming using the raw msg_i data. The doc references them as using the octet strings of the messages, and does not specify any other transformation.

It would be somewhat crazy suggestion, because you'd need modulo reduction that can handle inputs of unlimited length. But even if it is the case, you'd still need [to] specify endianness. In other words, no matter how you spin it, h_i * msg_i is an inadequate way to specify anything.

[chris-matichuk-ts]

given the specific goals of the project, there are things that are not going to happen

I get it, understood, makes sense. If in using the library if I want to do something special, I am perfectly fine with making tweaks as needed to the underlying library...and so I don't really need the changes on your end....more of a nice to have....and that is it. But having your feedback has been really helpful in understanding what I would need to do. And I'm thankful for the time you've been generous with in this.

[dot-asm]

1513ec4 8b2342d

[chris-matichuk-ts]

Using your new blst_fp12_finalverify routine, I was able to get something to both sign and verify based on whatever variant I have now for the BBS+ spec -> which likely has a few things incorrect but fixable once I get a better understanding of requirements. But the harder part of getting something working for sign and verify indicates to me that this is now doable. Thanks.

[chris-matichuk-ts]

Closing as I now have a version of expand_message_xmd that will work with any hash of any input block size and output size (changes needed to accommodate both input and output). Use the test vectors in the hash_to_curve spec to verify.

[dot-asm]

63016d4

[chris-matichuk-ts]

The following is what I created for a generalized version of the expand_message_xmd that supports different hash algorithms...at least the 64 byte sha512 one works...I verified that one. Both r_in_bytes and b_in_bytes are determined by the hash algorithm. The "cb" is a pointer to a structure with callbacks for the hash function.

    size_t r_in_bytes;  // r_in_bytes = input size of hash in bytes
    size_t b_in_bytes;  // b_in_bytes = output size of hash in bytes
    cb->d_size(cb, &r_in_bytes, &b_in_bytes); // get r_in_bytes and b_in_bytes from hash

    unsigned char Z_pad[512]; // max input size of hash (appears to be 256, reserving double)

    unsigned char md[128];   // max output size of hash (appears to be 64, reserving double)
    unsigned char mdXor[128];
    unsigned char DSTc[128];

    size_t outlen = 0;

    if (DST_len > 255)
    {
        cb->d_init(cb);
        cb->d_update(cb, "H2C-OVERSIZE-DST-", 17);
        cb->d_update(cb, DST, DST_len);
        cb->d_final(cb, (unsigned char*)DSTc, b_in_bytes, &outlen);
        DST = DSTc, DST_len = outlen;
    }

    const size_t ell = len_in_bytes / b_in_bytes;
    if (ell > 255) return;  // as per spec...error condition...abort

    unsigned char iBuf = 0;
    cb->d_init(cb);
    memset(Z_pad, 0, r_in_bytes);
    cb->d_update(cb, Z_pad, r_in_bytes);
    cb->d_update(cb, msg, msg_len);
    unsigned char lenBuf[2];
    lenBuf[0] = (unsigned char)(len_in_bytes >> 8);
    lenBuf[1] = (unsigned char)(len_in_bytes);
    cb->d_update(cb, lenBuf, sizeof(lenBuf));
    cb->d_update(cb, &iBuf, 1);
    cb->d_update(cb, DST, DST_len);
    iBuf = (unsigned char)DST_len;
    cb->d_update(cb, &iBuf, 1);
    cb->d_final(cb, md, b_in_bytes, &outlen);
    cb->d_init(cb);
    cb->d_update(cb, md, b_in_bytes);
    iBuf = 1;
    cb->d_update(cb, &iBuf, 1);
    cb->d_update(cb, DST, DST_len);
    iBuf = (unsigned char)DST_len;
    cb->d_update(cb, &iBuf, 1);
    cb->d_final(cb, bytes, b_in_bytes, &outlen);;
    for (size_t i = 1; i < ell; i++) {
        cb->d_init(cb);
        for (size_t j = 0; j < b_in_bytes; j++)
            mdXor[j] = md[j] ^ bytes[b_in_bytes * (i - 1) + j];
        cb->d_update(cb, mdXor, b_in_bytes);
        iBuf = (unsigned char)(i + 1);
        cb->d_update(cb, &iBuf, 1);
        cb->d_update(cb, DST, DST_len);
        iBuf = (unsigned char)DST_len;
        cb->d_update(cb, &iBuf, 1);
        cb->d_final(cb, bytes + b_in_bytes * i, b_in_bytes, &outlen);
    }

[dot-asm]

63016d4

Just in case. Even though modulo operations in the referred commit work with variable lengths, it doesn't mean that it would be appropriate to reduce raw input messages. It would be cryptographically unsane.

[dot-asm]

blst_sk_add_n_check and blst_fr_inverse were added.