w3f / bls Goto Github PK

verify_pok defined at https://github.com/w3f/bls/blob/skalman-schnorr-pok/src/bls_pop.rs#L83 need to be implemented.

Module names are dragging from the time library were coming from file coin. Also there is a lot of commented out code to be dealt with. This ticket for one last review of the code before submission for the first review.

Just a thread for more notes on more extreme performance measures. Anything sane should be done or given its own issue.

@burdges prefer to use a transcript abstraction instead of Message like in schnorrkel, ring-vrf, and now the apk crate. Message made sense for BLS signatures message. And maybe still does. I do not see much point in a schnorr proof.

The next module I choose to fix is verifiers.rs as it doesn't seem to depend on any of the modules we haven't upgraded yet.

APK proof can only be applied to bitfield (disjoint) aggregated BLS signature (in oppose with counted aggregation). This makes it impossible for validator to apply disjoint aggregation to aggregated BLS signatures they receive in a disorganized gossip. As such till we have a more intelligent gossip topolgy it is impossible for validators to aggregate BLS signatures before gossiping them again. As such they should sent the full list of unaggregated signatures and the prover will aggregate them before producing the proof.

blake2 implementation of substrate is different from the one used in bls-like. Furthermore there are dev depenedency which are marked as dependancy and they don't blong there.

This is basically the last module to be upgraded.

arkworks now have serialization for projective curve, so we should use it.

We should add benchmark code modeled on https://github.com/w3f/schnorrkel/blob/master/benches/schnorr_benchmarks.rs ala w3f/schnorrkel#37 which also helps with issues like #8 and #7

There are quite few changes in Arkworks Algebra which need to be reflected in the BLS library. including the renaming of the Projective and Affine Curve, removal of to_bytes and from_bytes interfaces and changes in pairing engine. BLS library need to compile and pass the tests again.

Check if SignerTable can or should be more aligned with GRANDPA's voter_set and bitfield modules. paritytech/finality-grandpa#93

Following discussion with @burdges and experimenting with Zexe library it seems that adapting bls library to Zexe is an easier than to new zkcrypto even only if for a intermediary milestone. Hence this ticket tracks the transition in this library.

Substrate requires a crypto type similar to: https://github.com/paritytech/substrate/blob/master/primitives/application-crypto/src/ecdsa.rs to be able to instantiate a signer for beefy capable of bls sigining. Implementing such crypto types help implementers to kick off BLS on beefy.

I need to see what I did that I get this failure now.

   test bit::tests::proofs_of_possession ... FAILED

We should select between using Zexe's algebra and algebra-core vs Zcash's new crates, so I'll outline the trade offs:

I think both curve abstraction traits hierarchies differ only somewhat, like both use core::ops traits similarly.

• Pro-Zcash: Zcash's traits looks slightly more detailed, so maybe Zexe would adopt Zcash's traits eventually. Zexe would surely accept pulls that made these traits more similar. Also Toni Aceri uses Zcash's traits some places. Zcash's traits look stable.
• Pro-Zexe: Zexe's maybe handled serialization nicer, but not sure. It's a smaller migration, so less work now, but much less stable.

Zexe support's bls12_377 which gives us Plonk proofs eventually, although only groth16 works right now probably. At first, I imagined this gave Zexe a definitive win, but not really: We suspect altering the bls12_381 crate to handle bls12_377 might not be that hard, and @drskalman might enjoy doing so. If so, a Zcash based signer could supply signatures for a Zexe based prover, although not sure how muc extra effort this requires. If annoying, then Zcash removed their prover abstraction trait JubjubEngine, which makes Zcash even more annoying.

Zcash support gives us constant time bls12_381, which becomes extremely important for bls. Zexe maybe added constant time, or will do so. Zcash folks were much more careful about this however. Zcash code was written to be production and they'd spend vastly more on auditing. Zcash could abandon pairing entirely if halo2 works out, but that's at least 5 years away.

All this gives us three questions:

1. Is it easier to migrate to Zexe traits than to Zcash traits?
2. Is it trivial to modify Zcash's bls12_381 crate into bls12_377?
3. Is either or their forks tracking the IRTF hash-to-curve spec closer?

Sample interface is on the branch: origin/skalman-pok-new-interface

• Generate trait should be implemented by the secret key.
• Verify trait should be implemented by the public key.

Currently we have two copy of exact function for bls12-381 and bls12-377. This needs to become a single function which takes the pairing engine as a generic parameter.

#47 depends on application crypto which on its turn depends on host api providing the following functions

		sp_io::crypto::{
        bls_public_keys(key_type),
        bls_generate(key_type, seed)
        bls_sign(key_type, self, msg.as_ref())
		bls_verify(&signature, msg.as_ref(), self)}

which this issue requires to implement.

Needed to resolve "bls_public_keys, bls_generate_new in implementation" error so Beef Keystore can be compiled.

filecoin-project/paired#5
https://github.com/poanetwork/threshold_crypto/pull/93/files

Zexe ProjectiveCurve and AffineCurve now have Basefield properties and we have to initiate them when we are deriving types for our EngineBLS class.

We need some mechanism for creating deliniarized SignerTables as an alternative to proofs-of-possession.

Check if the fact mentioned in the README.md of the crate is still relevant and if the README code compiles. Additionally:

• Emphasize on simple cases so we do not scare people out: One messaged singed by two party according to IETF proposal.
• Add explanation for the hash to curve because the library is opinionated about it.
• Explain Schnorr pop.

tests are failing because we have not ported TinyBLS implementation and I think now that UsualBLS is ported successfully it should be easy to port TinyBLS as well.

Not being resistant to side-channel attacks is a bug.

This require in part to replace the dependancy to arkworsk-w3f. This also temprory breaks BLS12-381 signature. Because WB hash has not implement for BLS12-381 yet. But the tests should pass for BLS12-377.

In step by step upgrade after upgrading engine.rs we should upgrade single.rs and perhaps its dependancy.

I believe the most advanced threshold signature implementation is https://github.com/poanetwork/threshold_crypto but they do not provide our abstractions, and one should optimize the arithmetic ala poanetwork/threshold_crypto#13 We should do threshold signatures in a way that supports #4 if possible. All this sounds doable if threshold signatures are provided in a way that exploits the current aggregation abstraction, but it's worth considering any parallels with w3f/schnorrkel#11 too.

• test single::tests::single_messages ... FAILED
• test delinear::tests::delinearized ... ok
• test distinct::tests::distinct_messages ... ok
• test bit::tests::proofs_of_possession ... FAILED

Hi!

Thank you for this amazing crate, It seems like it's the best one available for Rust now.
However I'm having one quite annoying issue with it, it seems that the decompression function is extremely slow, at least too slow for my use case.

I've seen online there is 2 methods of compression, one patented and another one not, which one do you use?

Do you know anyway of making this function faster?
pub fn from_bytes(bytes: [u8; 96]) -> Result<Self, GroupDecodingError>

https://docs.rs/bls-like/0.1.0/bls_like/single/struct.Signature.html#method.decompress

Have a nice day!

Hi,

After aggregating 500 signatures into one, the performances are dramatically slow, and I noticed it's exponentially slower for every signature I add. Is there a way to improve it without changing crate? I'd like to keep BLS like.

I'm looking basically to decrease the time it takes to verify aggregated signatures.

Thank you so much for this publishing and your work btw!

We should maybe make this PoK do both G1 and G2 if we're going that route, no? I guess that's a seperate thing that depends upon only Engine.

ValidatorSet is a set of authority ids, of type of primitive::beefy::crypto:Public which is currently hard wired to ECDSA public key. We need to change primitives::beefy::crypto:Public to primitives::beefy::crypto:ECDSAPublic and then make primitives::beefy::crypto:Public generic to be either ECDSA or ECDSA,BLS pair. that way the whole code of beefy validator can be generic over type of the public key.

I have introduced auxaulary types PublicKey/SignaturePrepared to make the EngineBLS compatible with Zexe Curves but so I need to tell rust how to convert from pairing agnostic curves to the elements prepared specififcally for G1 or G2.

In addition the bls crate points to the pulled from implementation

Most code from this library uses the text "ctx" although the README uses "Some context" and the From impl for Message uses a blank string.

It seems like the string plus length of message gets prepended to the message itself, implying any signatures derived from this Message will be affected by the choice of context.

What is it for, and what is best practice for its usage?

We should implement Pixel because doing so appears fairly straightforward and somewhat orthogonal. I believe the primary hurdle would be abstracting the verification equation, but if done properly then all the underlying optimizations work.

I think EngineBLS could act as both the curve and orientation like now, while some SignatureScheme extension trait provides the verification equation. We'd have BLS<E: EngineBLS> and Pixel<E: EngineBLS> ZSTs that satisfy SignatureScheme.

In this, Pixel's associated type SignatureGroup becomes the cartesian product of both groups, which incidentally makes us more dependent upon our patched version of pairing for batch_normalization.

Make sure BLS12-377 is supported and pass all tests

worker.rs currently only using BeefyKeystore to carry out crypto tasks, however in the new structure BeefyKeystore is only a trait now and the worker either need to instiate BeefyECDSAKeystor or BeefyBLSnECDSAKeystore depending if they want to certify their BEEFY messages using Merkle tree of ECDSA signature or an aggregated BLS signature.

pop.rs offers aggregation assuming PoP. But there is no example or test of how to do so. A test can server both purpose.

While SecretKeyVT has Canonical De/Serialize implemented for it. That is not the case for SecretKey which the library recommends to use in production.

According to paritytech/substrate#10466 (comment) BLS signatures because they can be aggregated, they should be treated differently rather than put in the vector of validator signatures. This issue intends to add an extra field as aggrigatable signature generic type to BEEFY primitve type.

Currently happening at https://github.com/drskalman/substrate/blob/skalman-bls-beefy/client/beefy/src/keystore.rs#L77

It only support signing ecdsa signature. However, in the case, where beefy message is also going to contain a single aggregated signature, this need to be change. The easiest path to this is to have AggregatableBeefyKeyStore trait which will generate and aggregate BLS signature. One could implemenet this trait for MMRed BEEFY signature and do nothing in this way the beefyclient code does not need to be changed wether we are dealing with MMRed Aggregated or BLS aggregated signature.

There is a new hash to curve function implemented in the fork https://github.com/kwantam/pairing/ via zkcrypto/pairing#56 (comment) which should be evaluated.

There is also a draft BLS standard by the IETF at https://datatracker.ietf.org/doc/draft-boneh-bls-signature/ but they only hash-to-G1, which makes verification slow after extensive aggregation. In fact, you'd only ever use BLS with extensive aggregation, so this sounds silly, but perhaps hash-to-G2 is so slow that more extensive aggregation is required before hash-to-G2 wins.

Also, the standard recommends hashing-to-G1 with try-and-increment, which sound archaic. We currently use Michael Orru's adaptation of Fouque-Tibouchi as implemented in zkcrypto/pairing#30 but Wahby-Boneh sounds interesting too.

arkworks now have serialization for projective curve, so we should use it.

zexe now uses serde like serialization as zkcrypto was using a EncodedPoint trait. We need to either adapt or migrate to new serialization or the tests won't pass.

This change is both requested by Pairity and blessed by @burdges

This happens here:

https://github.com/w3f/bls/blob/skalman-pok-new-interface/src/bls_pop.rs#L48

and here:

https://github.com/w3f/bls/blob/skalman-pok-new-interface/src/bls_pop.rs#L81

Any BLS signature library needs key splitting since afaik no constant-time pairing libraries exist, well not everyone believes the amcl claims. We do not care about the pairing itself being constant time of course, but we do signatures on the curve over an extension field, and the extension field arithmetic is not constant time.

What should our key splitting look like?

In this crate, I've used the simple aH(m) + bH(m) with a + b = s rerandomized before each signature in https://github.com/w3f/bls/blob/master/src/single.rs#L158-L189

Yet, much stronger approaches exist like a*(H(m)-X) + b*(H(m)-Y) + (aX+bY) with the (aX+bY) precomputed in the previous signature, and X, Y, and a+b=s rerandomized. In this variant, the attacker knows literally nothing about any of the inputs to the dangerous * operations, not even the point. So

/// We sign using the formula a*(H(m)-X) + b*(H(m)-Y) + (a*X+b*Y) where
/// a, b, X, Y are chosen randomly subject to a + b being our actual secret key,
/// and (a*X+b*Y) being precomputed.
pub struct SecretKey<E: EngineBLS> {
    /// [a, b]
    secrets: [E::Scalar; 2],
    /// [X, Y]
    points: [E::SignatureGroup; 2],
    /// (a*X+b*Y)
    previous: E::SignatureGroup,
}

In between, I suppose a*(H(m) - X) + b*(H(m)+X) + (a-b)*X sounds quite reasonable, so

pub struct SecretKey<E: EngineBLS> {
    a: E::Scalar,
    b: E::Scalar,
    x: E::SignatureGroup,
    y: Option<E::SignatureGroup>, // (a-b)*x
}

There are two extra scalar multiplications in the first, but only one in the second, but the second ties this scalar multiplication to the current values of a and b while the first permits leaving either a and b or X and Y fixed for longer periods.

Importantly, these extra scalar multiplications could be done in another thread, so the second requires resplit to clear y, but now resplit should be called after sign_once and another function that precomputes y should be called in between resplit and the next sign_once.