mailman-lists-archive/pipermail/bls-wg/2018.txt

From bram at chia.net  Fri Mar 16 18:41:59 2018
From: bram at chia.net (Bram Cohen)
Date: Fri, 16 Mar 2018 15:41:59 -0700
Subject: [BLS-wg] Reverse BLS12-381
Message-ID: <CAHUJnBCmdXUONAbQ6U5f19x3iZG+59n0nSwYrDq33ZEKu0D_Rg@mail.gmail.com>

Hey everybody. We at Chia are working on a new cryptocurrency and are
planning on making BLS be the standard way all signatures are done in it
because we like the noninteractive aggregation and unique signatures
features.

To that end, we're implementing them using the Relic library based on
BLS12-381. Er, sort of. It turns out that BLS12-381 as defined has 96 byte
public keys and 48 byte signatures, on the theory that usually public keys
are published once and then used to sign many things. In cryptocurrencies
it's the opposite, where public keys are published once and used to sign a
fraction of one thing because signatures are aggregated. To that end we're
swapping the curves around, so the public keys are 48 bytes and the
signatures are 96 bytes.

Our implementation is meant to be mostly api compatible with Bitcoin's
Key.cpp except that we don't support non-compact signatures and don't have
salt. Features we have or are working on include basic verification,
aggregation, compact multisig, and SecureAllocator support, and maybe some
more things I don't remember off the top of my head. Eventually we plan to
swap out Relic for something constant time.

-Bram

From sean at z.cash  Fri Mar 16 19:22:31 2018
From: sean at z.cash (Sean Bowe)
Date: Fri, 16 Mar 2018 17:22:31 -0600
Subject: [BLS-wg] Reverse BLS12-381
In-Reply-To: <CAHUJnBCmdXUONAbQ6U5f19x3iZG+59n0nSwYrDq33ZEKu0D_Rg@mail.gmail.com>
References: <CAHUJnBCmdXUONAbQ6U5f19x3iZG+59n0nSwYrDq33ZEKu0D_Rg@mail.gmail.com>
Message-ID: <CAKazn3mpcKJKhrnxdf2Uvc3mpdBNRxUbQyA+-rFZ6_zX2CbFog@mail.gmail.com>

Hi,

BLS12-381 is so-named because it's from the Barreto?Lynn?Scott family
of curves. BLS signatures are so-named because it's a
Boneh?Lynn?Shacham signature scheme. It's usually the case that
pairing friendly curves have a short group encoding (G1) and a longer
group encoding (G2).

I would caution saying "swapping the curves" because it may indicate
you're changing the curve construction when you're actually just
changing the signature scheme. BLS12-381 doesn't define anything about
how you use them for BLS signature schemes, or which group you use for
the key or the signature.

I'm excited to see BLS signatures finally end up in a cryptocurrency.
Besides what group you use for the signature, it'll be important to
specify how you're hashing to that group (for BLS signatures). We've
been having discussions about this in my pairing library and in
another library. I'd like to see everyone using the same
well-specified technique to hash to the curve; hopefully this weekend
I'll have a spec fleshed out and we'll have test vectors for
inter-operability. It seems possible we could have this merged into
RELIC as well.

Sean

On Fri, Mar 16, 2018 at 4:41 PM, Bram Cohen via bls-wg
<bls-wg at lists.z.cash.foundation> wrote:
> Hey everybody. We at Chia are working on a new cryptocurrency and are
> planning on making BLS be the standard way all signatures are done in it
> because we like the noninteractive aggregation and unique signatures
> features.
>
> To that end, we're implementing them using the Relic library based on
> BLS12-381. Er, sort of. It turns out that BLS12-381 as defined has 96 byte
> public keys and 48 byte signatures, on the theory that usually public keys
> are published once and then used to sign many things. In cryptocurrencies
> it's the opposite, where public keys are published once and used to sign a
> fraction of one thing because signatures are aggregated. To that end we're
> swapping the curves around, so the public keys are 48 bytes and the
> signatures are 96 bytes.
>
> Our implementation is meant to be mostly api compatible with Bitcoin's
> Key.cpp except that we don't support non-compact signatures and don't have
> salt. Features we have or are working on include basic verification,
> aggregation, compact multisig, and SecureAllocator support, and maybe some
> more things I don't remember off the top of my head. Eventually we plan to
> swap out Relic for something constant time.
>
> -Bram


From bram at chia.net  Fri Mar 16 20:03:38 2018
From: bram at chia.net (Bram Cohen)
Date: Fri, 16 Mar 2018 17:03:38 -0700
Subject: [BLS-wg] Reverse BLS12-381
In-Reply-To: <CAKazn3mpcKJKhrnxdf2Uvc3mpdBNRxUbQyA+-rFZ6_zX2CbFog@mail.gmail.com>
References: <CAHUJnBCmdXUONAbQ6U5f19x3iZG+59n0nSwYrDq33ZEKu0D_Rg@mail.gmail.com>
 <CAKazn3mpcKJKhrnxdf2Uvc3mpdBNRxUbQyA+-rFZ6_zX2CbFog@mail.gmail.com>
Message-ID: <CAHUJnBCQd0V24N4DJgH4yXf9wcK=O5Pwf3_eCc8dHQbcjbrV6A@mail.gmail.com>

On Fri, Mar 16, 2018 at 4:22 PM, Sean Bowe <sean at z.cash> wrote:

>
> I would caution saying "swapping the curves" because it may indicate
> you're changing the curve construction when you're actually just
> changing the signature scheme. BLS12-381 doesn't define anything about
> how you use them for BLS signature schemes, or which group you use for
> the key or the signature.
>

Right, we're swapping the curves from *a* implementation which was used to
give reference numbers but not actually misusing the primitive at all.


> I'm excited to see BLS signatures finally end up in a cryptocurrency.
> Besides what group you use for the signature, it'll be important to
> specify how you're hashing to that group (for BLS signatures). We've
> been having discussions about this in my pairing library and in
> another library. I'd like to see everyone using the same
> well-specified technique to hash to the curve; hopefully this weekend
> I'll have a spec fleshed out and we'll have test vectors for
> inter-operability. It seems possible we could have this merged into
> RELIC as well.
>

Dan Boneh just sent us a construction which allows for a speedup on
aggregated signatures of a single value, which we'll be implementing for
performance. It isn't standardized because it's new but we plan to have
everything we're working on be published and reviewed and ideally
standardized.

From sean at z.cash  Fri Mar 16 21:25:46 2018
From: sean at z.cash (Sean Bowe)
Date: Fri, 16 Mar 2018 19:25:46 -0600
Subject: [BLS-wg] Reverse BLS12-381
In-Reply-To: <CAHUJnBCQd0V24N4DJgH4yXf9wcK=O5Pwf3_eCc8dHQbcjbrV6A@mail.gmail.com>
References: <CAHUJnBCmdXUONAbQ6U5f19x3iZG+59n0nSwYrDq33ZEKu0D_Rg@mail.gmail.com>
 <CAKazn3mpcKJKhrnxdf2Uvc3mpdBNRxUbQyA+-rFZ6_zX2CbFog@mail.gmail.com>
 <CAHUJnBCQd0V24N4DJgH4yXf9wcK=O5Pwf3_eCc8dHQbcjbrV6A@mail.gmail.com>
Message-ID: <CAKazn3kOnA8w9r3FR3Ut1EK2-TCxymNccnXxS1rkOxxN5FDfCg@mail.gmail.com>

> Right, we're swapping the curves from *a* implementation which was used to give reference numbers but not actually misusing the primitive at all.

I think it's totally fine if you want to use G1 for public keys, but
I'm still confused about the language you're using to describe
BLS12-381.

The title of this thread ("Reverse BLS12-381") and "It turns out that
BLS12-381 as defined has 96 byte public keys and 48 byte signatures"
are both inaccurate. BLS12-381 doesn't define what a public key is or
what a signature is because it's a curve construction, not a signature
scheme.

I just want to make sure others aren't confused because these are
easily confusable names. Carry on!

Sean

On Fri, Mar 16, 2018 at 6:03 PM, Bram Cohen <bram at chia.net> wrote:
> On Fri, Mar 16, 2018 at 4:22 PM, Sean Bowe <sean at z.cash> wrote:
>>
>>
>> I would caution saying "swapping the curves" because it may indicate
>> you're changing the curve construction when you're actually just
>> changing the signature scheme. BLS12-381 doesn't define anything about
>> how you use them for BLS signature schemes, or which group you use for
>> the key or the signature.
>
>
> Right, we're swapping the curves from *a* implementation which was used to
> give reference numbers but not actually misusing the primitive at all.
>
>>
>> I'm excited to see BLS signatures finally end up in a cryptocurrency.
>> Besides what group you use for the signature, it'll be important to
>> specify how you're hashing to that group (for BLS signatures). We've
>> been having discussions about this in my pairing library and in
>> another library. I'd like to see everyone using the same
>> well-specified technique to hash to the curve; hopefully this weekend
>> I'll have a spec fleshed out and we'll have test vectors for
>> inter-operability. It seems possible we could have this merged into
>> RELIC as well.
>
>
> Dan Boneh just sent us a construction which allows for a speedup on
> aggregated signatures of a single value, which we'll be implementing for
> performance. It isn't standardized because it's new but we plan to have
> everything we're working on be published and reviewed and ideally
> standardized.
>


From bram at chia.net  Sat Mar 17 01:12:59 2018
From: bram at chia.net (Bram Cohen)
Date: Fri, 16 Mar 2018 22:12:59 -0700
Subject: [BLS-wg] Reverse BLS12-381
In-Reply-To: <CAKazn3kOnA8w9r3FR3Ut1EK2-TCxymNccnXxS1rkOxxN5FDfCg@mail.gmail.com>
References: <CAHUJnBCmdXUONAbQ6U5f19x3iZG+59n0nSwYrDq33ZEKu0D_Rg@mail.gmail.com>
 <CAKazn3mpcKJKhrnxdf2Uvc3mpdBNRxUbQyA+-rFZ6_zX2CbFog@mail.gmail.com>
 <CAHUJnBCQd0V24N4DJgH4yXf9wcK=O5Pwf3_eCc8dHQbcjbrV6A@mail.gmail.com>
 <CAKazn3kOnA8w9r3FR3Ut1EK2-TCxymNccnXxS1rkOxxN5FDfCg@mail.gmail.com>
Message-ID: <CAHUJnBDzcuaSek4LLWU0QTx9gTfMXQPBt+CvXm7EW6KxSdpCrA@mail.gmail.com>

On Fri, Mar 16, 2018 at 6:25 PM, Sean Bowe <sean at z.cash> wrote:

> > Right, we're swapping the curves from *a* implementation which was used
> to give reference numbers but not actually misusing the primitive at all.
>
> I think it's totally fine if you want to use G1 for public keys, but
> I'm still confused about the language you're using to describe
> BLS12-381.
>

All confusion is strictly mine! Since I'm not the one doing the
implementing I'm being a bit sloppy with BLS the algorithm, BLS12-381 the
curve, and whatever we're supposed to call a specific implementation of
that, which apparently doesn't have standards or names so far.

In any case, I called it 'reverse' because at least one thing I looked at
said that if you use BLS12-381 then the sizes of keys will be 96 bytes,
hence the interpretation of that as the 'normal' thing to do and what we're
doing as 'reverse'.

From bram at chia.net  Sat Mar 24 23:40:44 2018
From: bram at chia.net (Bram Cohen)
Date: Sat, 24 Mar 2018 20:40:44 -0700
Subject: [BLS-wg] New algorithm for aggregating BLS signatures
Message-ID: <CAHUJnBC_BCrzRE3_jz9+38_ShgaRnEHobDAUJX1fqQYukgeZ2w@mail.gmail.com>

Dan Boneh came up with a new approach for aggregating BLS signatures which
allows keys to be aggregated as well as signatures. We're going to be
implementing this:

https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html

From sean at z.cash  Mon Mar 26 02:05:33 2018
From: sean at z.cash (Sean Bowe)
Date: Mon, 26 Mar 2018 00:05:33 -0600
Subject: [BLS-wg] New algorithm for aggregating BLS signatures
In-Reply-To: <CAHUJnBC_BCrzRE3_jz9+38_ShgaRnEHobDAUJX1fqQYukgeZ2w@mail.gmail.com>
References: <CAHUJnBC_BCrzRE3_jz9+38_ShgaRnEHobDAUJX1fqQYukgeZ2w@mail.gmail.com>
Message-ID: <CAKazn3mt6CXvoyQnKq1n9DAQidix6A9nBUAY91W1NViiDEWfPg@mail.gmail.com>

Thanks for posting, looks cool!

I noticed that the batch verification technique proposed in Dan's note
encourages you to perform the random exponentiations on the pairing
products, but in practice it's probably more efficient for you to
apply them as scalar multiplications to the aggregated public keys
prior to the pairings. That is,

e(g_1, sigma) = e(apk_1 * rho_1, H_0(m_1)) *** e(apk_b * rho_b, H_0(m_b))

Or, you could also apply it to the G2 element by combining it with the
G2 cofactor multiplication you have to do anyway as a result of
hashing to the group. (The G2 cofactor is quite large, so it may pay
off if you're doing windowed exponentiation.)

Sean

On Sat, Mar 24, 2018 at 9:40 PM, Bram Cohen via bls-wg
<bls-wg at lists.z.cash.foundation> wrote:
> Dan Boneh came up with a new approach for aggregating BLS signatures which
> allows keys to be aggregated as well as signatures. We're going to be
> implementing this:
>
> https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html


From bram at chia.net  Mon Mar 26 16:50:05 2018
From: bram at chia.net (Bram Cohen)
Date: Mon, 26 Mar 2018 13:50:05 -0700
Subject: [BLS-wg] New algorithm for aggregating BLS signatures
In-Reply-To: <CAKazn3mt6CXvoyQnKq1n9DAQidix6A9nBUAY91W1NViiDEWfPg@mail.gmail.com>
References: <CAHUJnBC_BCrzRE3_jz9+38_ShgaRnEHobDAUJX1fqQYukgeZ2w@mail.gmail.com>
 <CAKazn3mt6CXvoyQnKq1n9DAQidix6A9nBUAY91W1NViiDEWfPg@mail.gmail.com>
Message-ID: <CAHUJnBC+1ZAeVDcLaPFYq-+ybyvfFs7oYJXWjMD6Ae5FE34BTg@mail.gmail.com>

I pointed Dan Boneh to this post and he said:


Excellent.  Great to see that they are reading it.  The comment is correct
... that is the right way to interpret the batch verification formula.

On Sun, Mar 25, 2018 at 11:05 PM, Sean Bowe <sean at z.cash> wrote:

> Thanks for posting, looks cool!
>
> I noticed that the batch verification technique proposed in Dan's note
> encourages you to perform the random exponentiations on the pairing
> products, but in practice it's probably more efficient for you to
> apply them as scalar multiplications to the aggregated public keys
> prior to the pairings. That is,
>
> e(g_1, sigma) = e(apk_1 * rho_1, H_0(m_1)) *** e(apk_b * rho_b, H_0(m_b))
>
> Or, you could also apply it to the G2 element by combining it with the
> G2 cofactor multiplication you have to do anyway as a result of
> hashing to the group. (The G2 cofactor is quite large, so it may pay
> off if you're doing windowed exponentiation.)
>
> Sean
>
> On Sat, Mar 24, 2018 at 9:40 PM, Bram Cohen via bls-wg
> <bls-wg at lists.z.cash.foundation> wrote:
> > Dan Boneh came up with a new approach for aggregating BLS signatures
> which
> > allows keys to be aggregated as well as signatures. We're going to be
> > implementing this:
> >
> > https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html
>