w3f / bls Goto Github PK
View Code? Open in Web Editor NEWAggregatable BLS sigantures
Aggregatable BLS sigantures
verify_pok
defined at https://github.com/w3f/bls/blob/skalman-schnorr-pok/src/bls_pop.rs#L83 need to be implemented.
pop.rs offers aggregation assuming PoP. But there is no example or test of how to do so. A test can server both purpose.
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.
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.
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!
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.
test single::tests::single_messages ... FAILED
test delinear::tests::delinearized ... ok
test distinct::tests::distinct_messages ... ok
test bit::tests::proofs_of_possession ... FAILED
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
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?
While SecretKeyVT has Canonical De/Serialize implemented for it. That is not the case for SecretKey which the library recommends to use in production.
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.
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.
Make sure BLS12-377 is supported and pass all tests
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.
This is basically the last module to be upgraded.
arkworks now have serialization for projective curve, so we should use it.
Check if SignerTable can or should be more aligned with GRANDPA's voter_set and bitfield modules. paritytech/finality-grandpa#93
We need some mechanism for creating deliniarized SignerTable
s as an alternative to proofs-of-possession.
In addition the bls crate points to the pulled from implementation
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.
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.
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
.
Needed to resolve "bls_public_keys
, bls_generate_new
in implementation" error so Beef Keystore can be compiled.
Sample interface is on the branch: origin/skalman-pok-new-interface
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.
I need to see what I did that I get this failure now.
test bit::tests::proofs_of_possession ... FAILED
arkworks now have serialization for projective curve, so we should use it.
This change is both requested by Pairity and blessed by @burdges
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
.
Zexe ProjectiveCurve and AffineCurve now have Basefield properties and we have to initiate them when we are deriving types for our EngineBLS class.
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.
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.
Not being resistant to side-channel attacks is a bug.
Just a thread for more notes on more extreme performance measures. Anything sane should be done or given its own issue.
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.
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.
Check if the fact mentioned in the README.md of the crate is still relevant and if the README code compiles. Additionally:
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.
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.
@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.
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.
#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.
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.
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.
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:
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!
In step by step upgrade after upgrading engine.rs
we should upgrade single.rs
and perhaps its dependancy.
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.
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.