Add randomizing factors to bls same message verification

[twoeths]

Problem description

Right now when we validate bls signatures of the same message, we aggregate signatures and public keys, if the aggregated signature is verified we consider all signatures are verified. But there's a chance 2 signatures are invalid and final verification result is still true.

Solution description

Add randomizing factors following this approach https://ethresear.ch/t/fast-verification-of-multiple-bls-signatures/5407

quick benchmark:

itBench({
      id: `BLS same message - randomizing factor - ${count} - ${bls.implementation}`,
      beforeEach: () => linspace(0, count - 1).map((i) => getSetSameMessage(i)),
      fn: (sets) => {
        const randomizingFactors = [];
        for (let i = 0; i < sets.length; i++) {
          randomizingFactors.push(randomBytesNonZero(8));
        }
        const PkConstructor = blst.P1;
        const aggregatedPubkey = new PkConstructor(); // Faster than using .dup()
        for (let i = 0; i < sets.length; i++) {
          const clone = (sets[i].publicKey as unknown as BlstPublicKey).value.dup();
          const pk = new BlstPublicKey(clone).jacobian.mult(randomizingFactors[i]);
          aggregatedPubkey.add(pk);
        }

        const SigConstructor = blst.P2;
        const aggregatedSignature = new SigConstructor(); // Faster than using .dup()
        for (let i = 0; i < sets.length; i++) {
          const clone = (bls.Signature.fromBytes(sets[i].signature, CoordType.affine, true) as unknown as BlstSignature).value.dup();
          const sig = new BlstSignature(clone).jacobian.mult(randomizingFactors[i]);
          aggregatedSignature.add(sig);
        }
        const isValid = verify(sets[0].message, new BlstPublicKey(aggregatedPubkey), new BlstSignature(aggregatedSignature));
        if (!isValid) throw Error("Invalid");
      },
    });

shows this is 2x slower than the current approach but it's still ~2.65x faster than verifyMultipleSignatures

Additional context

Given signature aggregation already took 25% of a mainnet node, it's not sustainable to still do this in main thread, we should offload the work to worker/libuv instead

Also right now we queue attestation messages in IndexedGossipQueue and bls queue, we should only queue in IndexedGossipQueue. For bls, we need to write new worker api (or libuv implementation) and verify same message signatures immediately without queueing.

cc @matthewkeil

[matthewkeil]

I got a POC built and it doesnt add as much time as you noted above. Please check out my methodology.

https://github.com/ChainSafe/blst-ts/pull/118

[twoeths]

that looks really great @matthewkeil

[philknows]

Please update with status on its testing with observations for inclusion! Thanks!

[matthewkeil]

There is little appreciable difference in metrics between the blst rebuild and the branch that is adding in the randomization factor for multiple same message verifications. While present it seems much less than anticipated (2x reduction in performance of attestation verifications).

In all images below the vertical bar was placed about where the restart happened. The branch that was deployed to the left was mkeil/test-blst-7 and the one to the right was mkeil/test-blst-mult-in-verification-2. Both branches are almost identical except for the randomization change. I did rebase mkeil/test-blst-7 on unstable when I started the multiplyBy work so it is up to date with the current state for comparisons with the unstable group. The couple issues that jumped out at me are:

• the traffic not getting all the way back up to the level it was before (msg avg peers per rpm and data/sec)
• increases RSS (will wait another day to see if its a leak or just has to do with the additional objects being created under the hood
• signature sets/sec is slightly lower but I would expect that. just seems a bit lower than anticipated. could be from reduced traffic though
• bls threadpool que length is slightly longer on average
• gossip validation que and utilization rate are up a bunch

[philknows]

21.06.2024 17:46:05 UTC-05:00 - Matthew Keil: Hi @kevaundray and @jtraglia !!! We have a couple crypto questions and I wanted to reach out to you guys to make introductions with a couple of our team members that are interested in the discussion 21.06.2024 17:46:27 UTC-05:00 - System: @caymannan is our team lead and @tuyennhv is a super star that loves this stuff 21.06.2024 17:47:33 UTC-05:00 - Cayman: 👋 hey yall 21.06.2024 17:47:37 UTC-05:00 - Matthew Keil: We implemented a function for aggregating signatures for attestations and PR'd it to supranational/blst. We found it increases our performance by a large amount but to prevent attack surface we need to mult in some randomness similar to how mult_agg_ver works under the hood.... 21.06.2024 17:48:50 UTC-05:00 - Kev: Hello! 21.06.2024 17:49:39 UTC-05:00 - Matthew Keil: https://github.com/supranational/blst/pull/225 21.06.2024 17:50:08 UTC-05:00 - Cayman: was poking around with Matt in the blst library but it is quite cryptic, was hoping to pick yalls brain 21.06.2024 17:50:10 UTC-05:00 - Matthew Keil: We found a few other "mult" related function in the blst repo but are unsure of the specifics for their use and it sparked us to want to reach out 21.06.2024 17:57:29 UTC-05:00 - Kev: Just reading the thread now to get context 🙂 21.06.2024 18:04:24 UTC-05:00 - System: Ah okay I think I understand, I'll re-iterate to make sure:

- You have a triplet of signature, message and public key.
- Currently there is a method to verify all of these faster than verifying them individually called verify_multiple_aggregate_signatures

- What you would like to do is:
- Aggregate the signatures and public keys with the same message first
- Call the verify_multiple_aggregate_signatures on this new aggregated set where all messages are distinct 21.06.2024 18:05:11 UTC-05:00 - Cayman: yup 21.06.2024 18:06:09 UTC-05:00 - Matthew Keil: saves a ton of thread time to aggregate first and run a single pairing computation 21.06.2024 18:08:19 UTC-05:00 - Kev: I believe the "correct" API would be to have a multiply method on whatever the public key format is 21.06.2024 18:08:29 UTC-05:00 - System: Oh wait, actually we might be able to get something that is faster 21.06.2024 18:09:01 UTC-05:00 - Matthew Keil: exactly... that is how i had it at first but the conversion to and from affine to stay with the rust pk signature is not ideal 21.06.2024 18:09:23 UTC-05:00 - Kev: If you are doing multiple scalar multiplications and then adding them together, you can actually do it a lot faster by calling the msm algorithm 21.06.2024 18:09:37 UTC-05:00 - Matthew Keil: sweet. i knew we should ask you 21.06.2024 18:09:42 UTC-05:00 - System: what is msm algo? 21.06.2024 18:09:59 UTC-05:00 - Kev: An MSM computes a point P such that P = a_0 G_0 + a_1 G_1 +...+ a_n G_n 21.06.2024 18:10:00 UTC-05:00 - Matthew Keil: btw here is the post we followed to get us this far...
https://ethresear.ch/t/fast-verification-of-multiple-bls-signatures/5407 21.06.2024 18:10:47 UTC-05:00 - Kev: I think you can do everything in jacobian and then convert to affine when you are done, or perhaps keep the public key in jacobian and only convert to affine for something like serialization 21.06.2024 18:11:34 UTC-05:00 - System: isn't the computation done using libuv threadpool? 21.06.2024 18:11:43 UTC-05:00 - Matthew Keil: the rust struct has them in affine for some reason and we dont want to modify that... but yes we went from having a mulitply_by on the PK and Sig to the functions in the PR to stay in jacobian 21.06.2024 18:12:07 UTC-05:00 - Cayman: heh, we've been doing some work in background threads but not all 21.06.2024 18:12:07 UTC-05:00 - Matthew Keil: https://github.com/supranational/blst/pull/225/commits/4da63bddbf53bcdc299061d175d6649693894eed 21.06.2024 18:12:54 UTC-05:00 - System: yes. but sadly libuv does not play nicely with docker after a ton of exploration. works great on bare metal but when we perf tested on docker it was running like a dog.... 21.06.2024 18:13:04 UTC-05:00 - Cayman: but this past week we started on a napi-rs binding of blst, and started on offloading a lot of work into tokio managed threads 21.06.2024 18:13:55 UTC-05:00 - System: today we were poking around the blst library on this "aggregate_with_randomness" function and definitely seemed like we were missing something 21.06.2024 18:14:01 UTC-05:00 - Matthew Keil: we are working with the lead maintainer of libuv Ben Noordhuis and he told us there are PR's in the works but there is no timeline for them to get merged.... 21.06.2024 18:16:25 UTC-05:00 - Justin Traglia: Hello too 👋 21.06.2024 18:16:32 UTC-05:00 - Matthew Keil: HI!!! 21.06.2024 18:17:07 UTC-05:00 - Cayman: hiya 21.06.2024 18:17:18 UTC-05:00 - Justin Traglia: I’m not really able to help right now (on vacation), but you’re in good hands with Kev 🙂 21.06.2024 18:18:11 UTC-05:00 - Matthew Keil: Im writing to you from a cruise ship off the coast of Italy on "workation" so can totally appreciate that!!! enjoy vacation and ttys 21.06.2024 18:18:36 UTC-05:00 - Justin Traglia: Haha awesome. You too! 21.06.2024 18:21:13 UTC-05:00 - Kev: I think a function like this could make sense -- Is it not possible to validate the public keys outside of this method? 21.06.2024 18:22:15 UTC-05:00 - Cayman: yeah for our case, the pubkeys are already validated, but the signatures are not yet validated 21.06.2024 18:22:29 UTC-05:00 - Matthew Keil: they already are validated when we deserialize them from state 21.06.2024 18:23:05 UTC-05:00 - Kev: Is it possible to do the signature validation logic outside of that method? 21.06.2024 18:23:12 UTC-05:00 - System: so it only does aggregation 21.06.2024 18:23:17 UTC-05:00 - Matthew Keil: sure 21.06.2024 18:23:37 UTC-05:00 - Kev: I think we can do what is needed without modifying the blst repo 21.06.2024 18:24:23 UTC-05:00 - Cayman: that would be ideal really 21.06.2024 18:24:45 UTC-05:00 - Kev: Are you interfacing with the rust blst library? 21.06.2024 18:24:53 UTC-05:00 - Cayman: yeah 21.06.2024 18:25:13 UTC-05:00 - Matthew Keil: for napi-rs wrapping the rust bindings we need access to the non-pub point to use the native blst functions though 21.06.2024 18:25:34 UTC-05:00 - System: was the issue i ran into in our bindings layer 21.06.2024 18:25:41 UTC-05:00 - Cayman: our bindings are in a PR here https://github.com/ChainSafe/blst-ts/pull/149/files#diff-292c21dc26ee204d63939308bcec83b4957275c30f13c74fa3db036c0917860a 21.06.2024 18:26:40 UTC-05:00 - Kev: Ah could you elaborate? I'm not sure how napi and blst are linked here 21.06.2024 18:27:24 UTC-05:00 - Matthew Keil: we are using the blst/bindings/rust and wrapping it in napi-rs to run in lodestar 21.06.2024 18:31:11 UTC-05:00 - System: just realized the link is not auto expanding... this is the file that matters
https://github.com/ChainSafe/blst-ts/blob/cayman/napi-rs/next/src/lib.rs 21.06.2024 18:44:21 UTC-05:00 - Kev: Okay got it -- was looking at the bindings code -- hmm since Public key is not marked as reprC it would be dangerous to convert it to a raw pointer and cast to the pk_affine type 21.06.2024 18:48:07 UTC-05:00 - System: I couldn't find a way around creating a new PublicKey type in your repository which you would then operate on instead and call the relevant methods. (You could serialize and then deserialize, but this is expensive)

This is likely not desirable I'm guessing since you need to maintain it, so perhaps asking the blst maintainer to expose the inner pk_affine type would be the lowest hanging fruit 21.06.2024 18:51:48 UTC-05:00 - System: The code for reference would look something like this:

pub struct LodestarPublicKey {
   point : blst_p1_affine
}

impl LodestarPublicKey {

   pub fn validate(&self) -> bool {
        // convert to the blst public key type
         let pk = self.convert_to_blst()
          // call validate on blst public key
         pk.validate()
   } 

   pub fn aggregate_with_randomness(&self, ...) {
       // custom logic
   }

   pub fn deserialize(bytes:  &[u8]) -> Self {
      
       // copy logic to deserialize from blst public key impl
   }

}

21.06.2024 18:59:40 UTC-05:00 - Cayman: yeah thats not exactly desirable 21.06.2024 18:59:57 UTC-05:00 - System: maybe the blst maintainers would be fine exposing msm? 21.06.2024 19:00:36 UTC-05:00 - Kev: It should already be exposed, I think the issue is that the inner type in PublicKey is not exposed 21.06.2024 19:00:46 UTC-05:00 - System: Because that’s what the msm method takes in 21.06.2024 19:01:02 UTC-05:00 - Cayman: oh right, I guess exposing it as a method on PublicKey or AggregatePublicKey 21.06.2024 19:01:11 UTC-05:00 - Matthew Keil: which is why i upstreamed that functionality... 21.06.2024 19:01:29 UTC-05:00 - Kev: Yep or expose the inner type 21.06.2024 19:01:49 UTC-05:00 - Cayman: yeah if they expose the inner type then we can just do whatever we want 21.06.2024 19:02:08 UTC-05:00 - Kev: It’s unclear to me if that PR will get merged in a timely manner though 21.06.2024 19:02:21 UTC-05:00 - Cayman: yea :( 21.06.2024 19:03:01 UTC-05:00 - Matthew Keil: is the approach we took to aggregate with randomness correct? this was the heart of why we reached out. we were wondering if there was a better blst function like _pippenger etc that might be better than the simple blst_p_mult that we used... ie the MSM. but we are unsure of the way to implement those safely 21.06.2024 19:03:09 UTC-05:00 - Kev: For a single message, how many public keys on average would you be aggregating? 21.06.2024 19:04:16 UTC-05:00 - Matthew Keil: let me get back to you with that. off the cuff i think its up to 1000 but i need to ask @tuyen cuz it may be way less per batch... ill commit to getting you that answer asap though 21.06.2024 19:04:17 UTC-05:00 - Cayman: probably 100 or more? 21.06.2024 19:04:41 UTC-05:00 - Kev: I think the only footgun with the msm method the way it’s implemented in blst, is that you need to ensure that none of the points are “zero/point at infinity” 21.06.2024 19:05:08 UTC-05:00 - System: If that is the case, it will return the point at infinity as the result unconditionally 21.06.2024 19:05:14 UTC-05:00 - Matthew Keil: we are doing a sig check and we also do a pk validate for sure on all pks 21.06.2024 19:05:14 UTC-05:00 - Kev: Oh wow 21.06.2024 19:06:03 UTC-05:00 - System: This would likely give a good improvement in speed, the msm function can also be parallelised internally 21.06.2024 19:06:08 UTC-05:00 - Matthew Keil: but the sig check ideally would be implemented in the aggregation function 21.06.2024 19:08:26 UTC-05:00 - System: like the best function signature for us would be fn aggregate_with_randomness(pks: &[PublicKey], sigs: &[Uint8Array]) -> (PublicKey, Signature).... whether we pass in the randomness or its generated in the function is fine but guessing the preference would be to pass in however there is another footgun with too little randomness (found that the hard way) so may be safer to have it built within the function 21.06.2024 19:09:17 UTC-05:00 - System: and same goes for sig verification... that should not be optional for consumers 21.06.2024 19:10:15 UTC-05:00 - Cayman: do you know why the blst rust library has bool parameters for pk_validate but not for pk_infcheck in PublicKey methods? whereas in Signature methods, there's both sig_groupcheck and sig_infcheck? 21.06.2024 19:11:25 UTC-05:00 - Kev: It’s probably better to generate it by hashing all of the input — haven’t checked to see if the blst library does any sort of randomness generation currently, if it does then it wouldn’t be anything new 21.06.2024 19:12:41 UTC-05:00 - Matthew Keil: it does not. they specifically exclude RNG 21.06.2024 19:13:32 UTC-05:00 - System: but in our bindings (and the rust/lighthouse) implementation we gen the randomness in the bindings layer 21.06.2024 19:13:37 UTC-05:00 - Kev: I think possibly because a zero public key is reasonable but a zero signature is likely not 21.06.2024 19:13:56 UTC-05:00 - Cayman: right, we already have rng for verify_multiple_aggregate_signatures, we can reuse the logic there 21.06.2024 19:16:06 UTC-05:00 - Kev: Is there any concern with respects to security/audits here?

If this change gets merged in, then you would be using unaudited code (probably safe) 21.06.2024 19:16:50 UTC-05:00 - Cayman: I would say some concern around use of the blst primitives 21.06.2024 19:17:33 UTC-05:00 - System: just making sure we didn't screw anything up 21.06.2024 19:17:58 UTC-05:00 - Matthew Keil: i spoke with Fredrick at interop and he mentioned we could request audit of our bindings layer so if we were to make the stuct members pub we could implement more easily and could have it sent for audit (internal or external was what Fredrick mentioned) 21.06.2024 19:17:59 UTC-05:00 - Kev: I do think your approach in the PR is reasonable though, and in terms of moving forward, I guess it depends on what the maintainer is comfortable with merging 21.06.2024 19:18:59 UTC-05:00 - Cayman: Yeah, it may be worth trying for a smaller diff (just making the underlying point public) 21.06.2024 19:19:00 UTC-05:00 - Matthew Keil: i think from this the takeway is that we are approaching the problem correctly but may be better and will provide more flexibility to expose the point for use by use downstream... 21.06.2024 19:19:41 UTC-05:00 - System: yep, exactly... unless the lighthouse team also want to exploit the same perf benefit 21.06.2024 19:19:53 UTC-05:00 - System: we could build it for us and they will get the glory lol 21.06.2024 19:20:38 UTC-05:00 - System: im going to reach out to Age and Dapplion to see if they are interested.... 21.06.2024 19:21:58 UTC-05:00 - System: @kevaundray you are a super star!!! thank you so much for your time tonight 21.06.2024 19:22:17 UTC-05:00 - Cayman: yeah very appreciated 😁 21.06.2024 19:23:36 UTC-05:00 - Kev: Glad I could be helpful :) 21.06.2024 19:23:59 UTC-05:00 - Matthew Keil: you are a 🥷 Unknown time - System: 22.06.2024 09:27:20 UTC-05:00 - Cayman: So it looks like the rust bindings already expose msm, but it operates on underlying points rather than PublicKey, Signature 22.06.2024 09:28:02 UTC-05:00 - System: https://docs.rs/blst/0.3.12/blst/struct.p1_affines.html 22.06.2024 09:39:15 UTC-05:00 - System: Their interface is a little annoying, the only way to construct that struct is by passing in jacobian points (which immediately get converted to affine). It's annoying bc in our case, we already have a vec of affine points that we would like to just... initialize as-is without going to and from jacobian. Another case where having a public field in the struct would be helpful... 22.06.2024 09:50:34 UTC-05:00 - System: ah, nvm, I guess slices of affine points implement the MultiPoint trait (and thats where the msm functionality is implemented)
https://docs.rs/blst/0.3.12/blst/trait.MultiPoint.html 22.06.2024 10:13:11 UTC-05:00 - Cayman: I suppose for now, in order to extract the underlying affine points from PublicKey and Signature, we can serialize and deserialize into blst_p1_affine and blst_p2_affine 22.06.2024 10:13:19 UTC-05:00 - System: or do some unsafe thing 22.06.2024 10:13:42 UTC-05:00 - Kev: Yep exactly — we only need the underlying point 22.06.2024 10:14:15 UTC-05:00 - System: I haven’t checked the conversion but it should be okay if the point was previously affine 22.06.2024 10:15:23 UTC-05:00 - System: I think any usage of unsafe would be undefined behaviour in this case because the structure doesn’t have a guaranteed memory layout 22.06.2024 10:15:42 UTC-05:00 - Cayman: ok darn 22.06.2024 10:20:56 UTC-05:00 - Kev: Yeah I think this is the only viable strategy, though it (deserialisation) might be relatively expensive depending on the number of points 22.06.2024 10:22:47 UTC-05:00 - Cayman: I guess its really just a one token "fix" to the underlying bindings that we want: pub 22.06.2024 10:23:21 UTC-05:00 - System: or methods to/from affine point, if the maintainer wanted to keep the field private 22.06.2024 10:25:06 UTC-05:00 - Kev: Yeah a method would probably make more sense (since then they can change the internal representation of public key without causing a breaking change) — they can then possibly add it behind a feature flag if they don’t want it to be on by default 22.06.2024 10:26:50 UTC-05:00 - Cayman: ok great, we'll clean up our PR like that. I think that has a better chance of getting merged 22.06.2024 10:47:02 UTC-05:00 - Kev: Heres what the unsafe method would look like for reference:

#[derive(Debug, Copy, Clone)]
pub struct P1Affine {
    x : u64, 
    y : u64
}

//#[repr(C)]
pub struct PublicKey {
    inner : P1Affine
}

impl PublicKey {
    
    pub fn new(x : u64, y : u64) -> Self {
        Self {
            inner : P1Affine {x, y}
        }
    }
}


fn main() {
    
    let pub_key = PublicKey::new(3, 2);
    let pointer_p1_affine = &pub_key as const PublicKey as const P1Affine;
    let p1_affine : P1Affine = unsafe {pointer_p1_affine};
    
    dbg!(p1_affine);
}

It works now without any modifications, but it assumes that the memory layout of the P1Affine is the same as the memory layout of the PublicKey struct. If you put the #[repr(C)] ontop of it. Rust makes no guarantee that this willbe the same, so it might work now and not in a future version.

If you put the #[repr(C)] ontop of the struct it fixes it to be compatible with C memory layout which fixes it. This would be another way to do it with the least amount of changes to blst.

Its not great because if blst add another field into publicKey, then that could change the alignment guarantees and then you could get undefined behavior Unknown time - System: 23.06.2024 11:54:18 UTC-05:00 - Kev: I have an hour free, so I'm gonna poke around the lighthouse codebase and see if theres a way to hack it in to see what the gain in speed is 23.06.2024 12:00:09 UTC-05:00 - Cayman: I benchmarked serializing a min_pk::PublicKey and Signature and deserializing back into a blst_p1_affine and blst_p2_affine
Seems to take about 1us and 2us respectively 23.06.2024 12:00:27 UTC-05:00 - System: not great for something that could be basically free passing by ref 23.06.2024 12:00:42 UTC-05:00 - Kev: Yeah I'm checking the method now and it does not do any checks it seems, so not as expensive as I was expecting 23.06.2024 12:02:02 UTC-05:00 - System: Yeah so I guess for every 1K keys, this conversion is costing roughly a pairing (~1ms) 23.06.2024 12:34:07 UTC-05:00 - Kev: Incase I disappear, pushing to this branch: https://github.com/kevaundray/lighthouse/commit/1f7ca1a513e403d25728c223abc60482f0facd13 23.06.2024 12:34:24 UTC-05:00 - System: Trying to run lighthouse tests to see if anything is broken 23.06.2024 12:36:51 UTC-05:00 - System: This doesn't add in the randomness to aggregate keys under the same message, it just replaces the aggregate public key method 23.06.2024 12:37:33 UTC-05:00 - System: The same method I added can be used for that usecase too 23.06.2024 12:37:55 UTC-05:00 - Cayman: i think you should be able to just mult on a slice of <code>blst_p1_affines rather than converting to projective and going thru their built-in blst::p1_affines</code> struct 23.06.2024 12:38:45 UTC-05:00 - System: if you're trying to benchmark it 23.06.2024 12:39:56 UTC-05:00 - Kev: Oh yeah true, I think we would need to use the raw pippenger API in that case 23.06.2024 12:42:12 UTC-05:00 - Cayman: should be able to use this implemented trait https://docs.rs/blst/0.3.12/blst/trait.MultiPoint.html#impl-MultiPoint-for-%5Bblst_p1_affine%5D 23.06.2024 12:42:53 UTC-05:00 - Kev: Ah sorry did not see that, will change 23.06.2024 12:47:58 UTC-05:00 - Cayman: I just pushed up similar usage to https://github.com/ChainSafe/blst-ts/pull/149
I'd love to benchmark this impl vs the other impl we had that multiplied each one by one 23.06.2024 12:48:22 UTC-05:00 - Kev: Ah its not in the version that lighthouse uses 23.06.2024 12:48:36 UTC-05:00 - Cayman: ah yea it looks like it was just added 3 wks ago 23.06.2024 13:10:39 UTC-05:00 - Cayman:

BLS aggregation of 32 pubkeys and signatures                          145.0401 ops/s       6894646 ns/op    290 runs
BLS aggregation of 32 pubkeys and signatures - aggregateWithRand      133.8267 ops/s       7472352 ns/op    268 runs
BLS aggregation of 128 pubkeys and signatures                         36.30298 ops/s   2.754595e+7 ns/op     73 runs
BLS aggregation of 128 pubkeys and signatures - aggregateWithRan      34.59277 ops/s   2.890777e+7 ns/op     70 runs
BLS aggregation of 256 pubkeys and signatures                         18.15399 ops/s   5.508431e+7 ns/op     37 runs
BLS aggregation of 256 pubkeys and signatures - aggregateWithRan      17.31709 ops/s   5.774643e+7 ns/op     35 runs

Here's a benchmark showing what we currently have aggregatePubkeys(pks, false) + aggregateSerializedSignatures(sigs, true) (without multiplying by randomness)
vs this new aggregateWithRandomness using msm 23.06.2024 13:11:17 UTC-05:00 - System: its barely slower (and doesn't have the vulnerability that we currently have, not multing in the randomness) 23.06.2024 13:11:40 UTC-05:00 - System: so thats already quite acceptable 23.06.2024 13:12:44 UTC-05:00 - System: if we could avoid serialization/deserialization it looks like it would still be a hair slower, so its not the end of the world if we can't upstream our to/from affine fns 23.06.2024 13:13:11 UTC-05:00 - Kev: Hmm it seems that both methods are roughly the same speed, which is suprising 23.06.2024 13:14:08 UTC-05:00 - Cayman: yeah, the first method is just using min_pk::AggregatePublicKey::aggregate(...).to_public_key() and similar for signature 23.06.2024 13:15:12 UTC-05:00 - Kev: Hmm maybe I'm missing something, once you start aggregating more than 5/6 things the msm algorithm should be strictly faster 23.06.2024 13:45:19 UTC-05:00 - Cayman: I wonder if its slower because its now mult-ing in randomness. Can try benchmarking exact apples to apples, using AggregatePublicKey::aggregate() vs MultiPoint::add 23.06.2024 13:51:04 UTC-05:00 - System:

BLS aggregation of 32 pubkeys and signatures                          133.1341 ops/s       7511225 ns/op    267 runs
BLS aggregation of 32 pubkeys and signatures - aggregateWithMsm       131.3886 ops/s       7611011 ns/op    263 runs
BLS aggregation of 128 pubkeys and signatures                         33.49414 ops/s   2.985597e+7 ns/op     67 runs
BLS aggregation of 128 pubkeys and signatures - aggregateWithMsm      33.17804 ops/s   3.014042e+7 ns/op     67 runs
BLS aggregation of 256 pubkeys and signatures                         16.74945 ops/s   5.970346e+7 ns/op     34 runs
BLS aggregation of 256 pubkeys and signatures - aggregateWithMsm      16.61108 ops/s   6.020078e+7 ns/op     34 runs

Ok here's apples to apples 23.06.2024 13:52:56 UTC-05:00 - Kev: Am I reading it correctly in that the benchmarks imply that MultiPointAdd is essentially the same as ::aggregate? 23.06.2024 13:53:15 UTC-05:00 - Cayman: yup it seems so 23.06.2024 13:53:26 UTC-05:00 - Kev: I'm currently trying to fix a bug in the lighthouse tests, so haven't gotten to benchmarking yet 23.06.2024 13:54:33 UTC-05:00 - System: Hmm something strange must be happening 23.06.2024 13:55:27 UTC-05:00 - Cayman: i'm running these benchmarks from javascript, using napi-rs to wrap things 23.06.2024 13:55:55 UTC-05:00 - System: is it possible that there's some overhead there thats overshadowing gains? 23.06.2024 13:56:41 UTC-05:00 - Kev: The only overhead I can think of right now, is the need to allocate scratch space for MultiPointAdd -- Even on a single thread, I would expect MultiPointAdd to be superior 23.06.2024 13:59:10 UTC-05:00 - Cayman: yea, and MultiPointAdd has a multithreaded implementation where ::aggregate doesn't ! 23.06.2024 13:59:41 UTC-05:00 - Kev: Yeah exactly 😄 This is super suprising to me 23.06.2024 14:00:27 UTC-05:00 - System: Can I see the input data you are using? Would like to copy it into the rust codebase and run benchmarks once the tests pass 23.06.2024 14:02:03 UTC-05:00 - Cayman: Yeah, benchmarks here https://github.com/ChainSafe/blst-ts/blob/cayman/napi-rs/benchmark/blstOps.ts#L328-L367 23.06.2024 14:02:34 UTC-05:00 - System: hoping @mattheweliaskeil can also check my work later, see if I missed anything 23.06.2024 14:03:39 UTC-05:00 - System: and here is that aggregate_with_msm fn https://github.com/ChainSafe/blst-ts/blob/cayman/napi-rs/next/src/lib.rs#L260 23.06.2024 14:34:45 UTC-05:00 - Matthew Keil: @dot-asm just cam back with this
https://github.com/supranational/blst/pull/225#issuecomment-2185264101 23.06.2024 14:44:14 UTC-05:00 - System: Why did he say we should not be using MSM or am I reading that wrong? 23.06.2024 15:10:19 UTC-05:00 - Kev: I’m not sure how to parse the response, though that’s what it sounds like 23.06.2024 15:23:15 UTC-05:00 - Matthew Keil: Well at least I feel a bit better. 🫣😊 Honestly the math is a bit over my head. I know enough to be dangerous but not enough to respond other than how I did... 23.06.2024 15:24:27 UTC-05:00 - System: Feel free if you want to chime in @kevaundray. I was just planning to see what he responds with cuz I'm at my knowledge limit 23.06.2024 15:24:44 UTC-05:00 - Kev: Oh he might be thinking that you are doing just the multiplication and not adding them together 23.06.2024 15:25:10 UTC-05:00 - Matthew Keil: I'll add that to the response but that is in the doc I linked 23.06.2024 15:25:17 UTC-05:00 - System: Guessing he will peek at that though 23.06.2024 15:26:14 UTC-05:00 - System: Actually he knows what we are doing cuz we mentioned it above and it was in the function signatures and implementation I pushed 23.06.2024 15:26:50 UTC-05:00 - System: If he doesn't respond I'll add it but gonna let it ride for now 23.06.2024 15:27:07 UTC-05:00 - Kev: Sounds good to me :) 23.06.2024 15:28:10 UTC-05:00 - System: Lighthouse test is passing, I had to log off before figuring out how to do the benchmark — was a bit confused wrt the generics, will go over it tomorrow 23.06.2024 15:28:43 UTC-05:00 - Matthew Keil: Sounds good. Have a good night and thanks again for all your help 23.06.2024 16:50:55 UTC-05:00 - Matthew Keil: https://github.com/supranational/blst/pull/225#issuecomment-2185284827 23.06.2024 16:51:09 UTC-05:00 - System: Here is the response I have drafted 23.06.2024 16:51:20 UTC-05:00 - System: > > All right. So that if we're to devise an additional interface it would
>
> Or maybe I've misinterpreted the "correct" remark...

Apologies, I am not sure, but perhaps I misrepresented when I said "correct". I think "yes we believe we need to use an array of scalars" is more accurate. Considering the importance of this being correct I would love to step back for a moment.

Honestly I am swimming in deep water with regards to the math here and would love to help you help us. Thank you in advance because its always a bit hard to swallow humble pie with stuff like this and its best to let the experts make expert decisions with more knowledge. I know enough to be dangerous is why we are reaching out to you (and we have also circled in some other researchers to make sure we are on the right track) but want to go over what lead us here. Some of the below may be repeated from above but i wanted to get it out to make sure I haven't missed anything.

We found that there are a lot of attestations for the same message when listening to subnet traffic on the beacon chain. We were originally doing verifiy_multiple_aggregate_signatures over groups of those for verification ({msg, pk, sig}[]).

One of the engineers on our team was playing around with optimizations and tried something novel:

interface SignatureSet {
    message: Uint8Array;
    publicKey: PublicKey;
    signature: Signature;
}

const signatureSets: SignatureSet = [
    // many that came across the wire and were bundled in a batch for verification
    // for this example assume all sets have the same message (vote for head)
];

// Option 1 - what we were originally doing
let isValid = verifyMultipleAggregateSignatures(signatureSets);


// Option 2 - the novel idea
const aggPk = aggregatePublicKey(signatureSets.map(set => set.publicKey));
const aggSig = aggregateSignatures(signatureSets.map(set => set.signature));
isValid = verify(signatureSets[0], aggPk, aggSig); // all the messages are the same so can pick any index

We found that Option1 takes roughly 4 times as long under normal circumstances.

We shared our findings with the lighthouse team and they came back with this issue:
https://github.com/sigp/lighthouse/issues/5148

We then did some research and found this post:
https://ethresear.ch/t/fast-verification-of-multiple-bls-signatures/5407

And spoke with some other core devs and from our shared understanding we could resolve the issue by:

function getNonZeroBytes(length: number) {
    const rand = crypto.randomBytes(length);
    for (let i = 0; i < rand.length(); i++) {
        if (rand[i] !== 0) return rand;
    }
    rand[0] = 0x99
    return rand;
}

const SAME_RANDOM_BYTES_AS_MULT_VER = 8;
const rands = Array.from({length: signatureSets.length()}, () => {
    return getNonZeroBytes(SAME_RANDOM_BYTES_AS_MULT_VER));
});

const aggPkWithRandomness = aggregatePublicKeys(
    signatureSets.map(({publicKey}, i) => publicKey.multiplyBy(rands[i])
);
const aggSigWithRandomness = aggregateSignatures(
    signatureSets.map(({signature}, i) => signature.multiplyBy(rands[i])
);

const isValid = verify(msg, aggPkWithRandomness, aggSigWithRandomness);

We implemented the solution above using the SWIG bindings and also using a multi-threaded C++ napi binding around the blst.hpp. We found multithreaded performance is better using napi-rs and rust so we are reimplementing the node bindings by wrapping the bindings/rust from here.


> > All right. So that if we're to devise an additional interface it would
>
> Or maybe I've misinterpreted the "correct" remark...

I guess the first question that I have is does our "solution" seem sound. We have had others tell us that it is but I would love to get your input as well. 23.06.2024 16:51:20 UTC-05:00 - System: > > > Is it actually rand[] and not a single rand here?
> >
> >
> > Correct.
>
> All right. So that if we're to devise an additional interface it would take a message, pks[], sigs[] and a random scalar, hash the message, multiply the hash by the scalar, pair-n-aggregate it with pks[], accumulate sigs[] and multiply the sum by the scalar. Then you'd simply merge the pairings for unique messages and perform the final verification. Does it sound sensible?
>
> It should be noted that this wouldn't be the most efficient way, more specifically not asymptotically. By "asymptotically" I mean there is a more efficient way to do it for a larger amount of inputs. For a larger amount of the unique messages it would be more efficient to not multiply the sum of the signatures in the new interface, but leave it to the MSM. On the other hand the improvement won't be that impressive, because the execution time would still be dominated by the pairings with pks[]. But it's no trouble to make the sig[] optional just in case...

In all honestly I am not sure how to respond to this but am more than willing to discuss this solution further. I cannot add much though, other than the info provided above. We are more than willing though, to go in another direction to optimize if you believe it to be the correct path.

My biggest concern is that this solution may be taken up by other teams, because the performance benefit is HUGE. If that is the case it MUST be mathematically sound and a rock solid solution.

Thank you again btw. I really appreciate it personally and I know our team as a whole does as well!!! You are a rockstar 🎸 ninja 🥷 !!! Unknown time - System: 24.06.2024 08:01:31 UTC-05:00 - Kev: Currently asking lighthouse for realistic inputs -- I have artifical numbers that show the msm version being favourable but I had to do the unsafe casting and tweak the NUM_BITS_SCALAR constant 24.06.2024 08:09:07 UTC-05:00 - System: Here are the artificial numbers, noting that this is not with the randomness idea. This is just replacing an existing function:

verify_signature_set/old -- num signatures 32, sig_sets 1
                        time:   [1.0899 ms 1.1332 ms 1.1981 ms]

verify_signature_set/new -- num signatures 32, sig_sets 1
                        time:   [1.0639 ms 1.0896 ms 1.1293 ms]

verify_signature_set/old -- num signatures 64, sig_sets 1
                        time:   [1.0686 ms 1.0916 ms 1.1243 ms]

verify_signature_set/new -- num signatures 64, sig_sets 1
                        time:   [1.0614 ms 1.0855 ms 1.1220 ms]

verify_signature_set/old -- num signatures 128, sig_sets 1
                        time:   [1.0921 ms 1.1118 ms 1.1419 ms]

verify_signature_set/new -- num signatures 128, sig_sets 1
                        time:   [1.0756 ms 1.0984 ms 1.1328 ms]

verify_signature_set/old -- num signatures 512, sig_sets 1
                        time:   [1.2726 ms 1.2920 ms 1.3165 ms]

verify_signature_set/new -- num signatures 512, sig_sets 1
                        time:   [1.0992 ms 1.1271 ms 1.1630 ms]

verify_signature_set/old -- num signatures 16384, sig_sets 1
                        time:   [8.2746 ms 8.3283 ms 8.3918 ms]

verify_signature_set/new -- num signatures 16384, sig_sets 1
                        time:   [1.4527 ms 1.4808 ms 1.5158 ms]

verify_signature_set/old -- num signatures 32768, sig_sets 1
                        time:   [8.2644 ms 8.3192 ms 8.3848 ms]

verify_signature_set/new -- num signatures 32768, sig_sets 1
                        time:   [1.4652 ms 1.5084 ms 1.5663 ms]

24.06.2024 08:10:11 UTC-05:00 - System: If you increase the num_signature set, the latency grows so I'm asking Michael for what is a realistic number of signature sets.

He said that post electra, the number of signatures will be ~48864 which is why the 32K is there 24.06.2024 08:36:44 UTC-05:00 - Cayman: well thats exciting, even at a fairly small number there's some improvement 24.06.2024 08:38:06 UTC-05:00 - Kev: This importantly does not change any security assumptions -- do you know if aggregating singatures are also on the critical path? 24.06.2024 08:38:55 UTC-05:00 - System: That method also seems to be unoptimized, though perhaps the block builder aggregates the signatures or something which means its not that bad 24.06.2024 08:42:11 UTC-05:00 - Cayman: for us it is, at one point we were spending 30% of our main thread aggregating signatures 24.06.2024 08:42:44 UTC-05:00 - System: just offloading that to a tokio thread helped us noticeably 24.06.2024 08:45:43 UTC-05:00 - System: looks good, though I might remove the lines "We then did some research and found this post: link" since the issue linked above is imo more relevant and should be highlighted. 24.06.2024 08:46:55 UTC-05:00 - System: might just remove the quoted paragraphs and paragraph starting "In all honestly". 24.06.2024 08:48:10 UTC-05:00 - Kev: I believe dot-asm is saying that if you aggregate under the same message then you cannot call the subsequent method -- I'll need to check the signature algorithm later to see why that would be the case 24.06.2024 10:37:35 UTC-05:00 - Cayman: looked at your implementation, I guess you could use MultiPointAdd vs MultiPointMult and avoid paying for allocing the Scalar::ones 24.06.2024 10:38:21 UTC-05:00 - System: also benchmarked that unsafe conversion to blst_p1/2_affine, its basically free 24.06.2024 10:38:42 UTC-05:00 - System: sooooo much better than round-trip serializing 24.06.2024 11:26:43 UTC-05:00 - Kev: Yep! Its just super unsafe! 24.06.2024 11:27:21 UTC-05:00 - System: Oh didn't see that -- I'll check if its doing a batched_addition or if its doing pippenger 24.06.2024 11:42:08 UTC-05:00 - System: I could be reading the code wrong -- .add looks like it should be slower than .mult, especially for larger input since its just doing naive addition just with a threadpool now 24.06.2024 11:45:31 UTC-05:00 - Cayman: aww ok 24.06.2024 11:46:01 UTC-05:00 - Kev: Its still faster, but for larger inputs it seems to start regressing from .mult -- I'm not confident that I understood the implementation of .add, so I could be missing something 24.06.2024 12:12:51 UTC-05:00 - Cayman: if i'm reading it right, its using blst_p1s_add and blst_p2s_add under the hood, which appears to be implemented here https://github.com/supranational/blst/blob/master/src/bulk_addition.c#L11 in a macro w/ the function starting on L145 24.06.2024 12:14:37 UTC-05:00 - System: hoping you'd be able to tell if that should be faster or slower than pippenger 24.06.2024 12:17:07 UTC-05:00 - Kev: That bulk addition method should be faster since .mult essentially decomposes into a bunch of bulk_addition 24.06.2024 12:17:42 UTC-05:00 - System: So I think you are right in that we should use that instead, though its unclear to me as to why its slower 24.06.2024 13:54:44 UTC-05:00 - Cayman: he responded again 24.06.2024 13:55:10 UTC-05:00 - System: I dug up a comment from one of our chats

Hey! We found a potential security vulnerability on Lodestar's optimization that batch verifies gossip attestations with the same message.

This optimization allows an attacker to force a node running this optimization to forward invalid data.

Consider two honest attesters publishing unaggregated attestation signatures $S1$, $S2$. An attacker is connected to the victim node, where the victim implements this optimization. The attacker mutates the signatures such that $S1' = S1 + Δ$, $S2' = S2 - Δ$ and forwards them to the victim. The check $e(G, S1' + S2') =? e(P1 + P2, Hm)$ will pass. If the victim strictly uses aggregated pubkey from now on it will never attempt to include invalid data on-chain in other gossip topics. However, it will forward attestations with invalid signatures and will quickly be banned by all other peers. As such an attacker can isolate the victim node forcing it to connect exclusively to other nodes implementing the optimization and attackers.

24.06.2024 13:55:45 UTC-05:00 - System: so this is what we're vulnerable to when we aggregate sigs and pks per unique message before verifying 24.06.2024 13:56:12 UTC-05:00 - System: and I suppose what the random numbers are supposed to be preventing 24.06.2024 13:59:17 UTC-05:00 - Kev: Yep this makes sense, essentially if you want to verify something like:

a + b = 0
c + d = 0

Then you can verify them individually and they will be true, but if you verify them together they could cancel out:

(a + b) + (c + d) = 0 does not imply that a + b= 0 and c + d = 0. You could have c = -a and d = -b

So we add randomness that probabilistically ensures that this is the case, ie we check:

(a + b) + random (c+d) = 0 the security proofs then argue that its impossible for the attacker to know random, so they cannot manipulate the aggregated equation to their favour 24.06.2024 14:01:04 UTC-05:00 - System: For public keys, if you have proof of possession, then you cannot "cancel out" terms because you need to prove that you now the secret key to the "negative thing" that you are trying to add. In the above case, we would need to prove ownership of "-a"

For signatures, it seems that there are cases when I can give the "negative thing" and trick someone who is verifying, so we would need the randomness 24.06.2024 14:01:57 UTC-05:00 - Matthew Keil: Saw that at dinner. Packing and will draft a response when I'm done 24.06.2024 14:02:43 UTC-05:00 - System: Wouldn't them coming out of state be proof enough. They had to be verified to be added to the contract to end up in state 24.06.2024 14:03:03 UTC-05:00 - Kev: coming out of state? 24.06.2024 14:03:18 UTC-05:00 - Matthew Keil: Yes, we deserialize the keys on startup 24.06.2024 14:03:28 UTC-05:00 - System: They are the validator keys 24.06.2024 14:04:14 UTC-05:00 - Kev: perhaps I misunderstand, proof of posession would stop someone from adding in any public key 24.06.2024 14:05:09 UTC-05:00 - System: So without a proof of possession, when we aggregate public keys lets say P1 + P2 + P3, I could just add my P4 such that P4 = -P1 - P2 - P3 24.06.2024 14:06:04 UTC-05:00 - Matthew Keil: Meaning you the person running the node? 24.06.2024 14:06:18 UTC-05:00 - Kev: With proof of possession, I need to show that I own the secret key corresponding to the publick key -P1 - P2 - P3. which means I need to know the secret key for P1, P2 and P3 24.06.2024 14:06:35 UTC-05:00 - System: I guess you would be a malicious validator here 24.06.2024 14:06:42 UTC-05:00 - Matthew Keil: Like the keys so not come across the wire. They are pulled from state according to validator index when an attestation is received 24.06.2024 14:07:09 UTC-05:00 - Kev: Yeah I think this is before that, ie how do the keys get "registered" 24.06.2024 14:07:36 UTC-05:00 - System: To register a validator key into the system, you would need to show that you own it by commonly signing over some message 24.06.2024 14:07:39 UTC-05:00 - Matthew Keil: Through the validator contact where a message is signed by the owner 24.06.2024 14:07:44 UTC-05:00 - System: Exactly 24.06.2024 14:07:51 UTC-05:00 - System: And then it gets added to state 24.06.2024 14:07:54 UTC-05:00 - Kev: Yeah thats the proof of possession part 24.06.2024 14:08:26 UTC-05:00 - System: If you allow me to add any validator key, I could cancel out the other keys and the aggregated key would just be the infinity point 24.06.2024 14:09:18 UTC-05:00 - Matthew Keil: Now I think I'm confused. Wouldn't that be proof enough. Like we get a validator index. We look up the index and get the corresponding key and then use the key we found, that was proven through signature before being added, to verify messages for that validator 24.06.2024 14:09:41 UTC-05:00 - Kev: This is assuming aggregation is done by doing P1 + P2 + P3

If its done by doing P1 + r1P2 + r3 P3 then its not possible to get a P4 that cancel out the P3s 24.06.2024 14:10:34 UTC-05:00 - Matthew Keil: That's my understanding of why randomness is added for any aggregation (mult_agg_ver or what we are trying to do) 24.06.2024 14:10:57 UTC-05:00 - System: Makes this impossible 24.06.2024 14:11:33 UTC-05:00 - Kev: I don't think its added when we aggregate public keys due to proof of possession 24.06.2024 14:12:28 UTC-05:00 - System: Not sure if I am talking past you 😂 24.06.2024 14:12:29 UTC-05:00 - Matthew Keil: Ok, question now that you mentioned that, how is fastAggregateVerify secure then? 24.06.2024 14:12:35 UTC-05:00 - System: Yes you may be 24.06.2024 14:13:00 UTC-05:00 - System: I don't purport to fully grok the math 🤷‍♂️ 24.06.2024 14:13:04 UTC-05:00 - Kev: Ah I haven't looked at that method 24.06.2024 14:13:06 UTC-05:00 - Matthew Keil: And know enough to be dangerous 24.06.2024 14:13:26 UTC-05:00 - Kev: Not sure what it is aggregating 24.06.2024 14:13:39 UTC-05:00 - System: I'm guessing one signature, multiple public keys and same message? 24.06.2024 14:13:50 UTC-05:00 - Matthew Keil: Its verify with a single message, an array of PKs and a single signature. And the keys get aggregated prior to verification 24.06.2024 14:14:40 UTC-05:00 - Kev: Yeah that makes sense, you would not need randomness if all of the public keys have a proof of possession 24.06.2024 14:17:27 UTC-05:00 - Matthew Keil: What I don't understand is why the keys in state (signed the validator contract to prove ownership and added to state proveably via state root) do not meet that condition 24.06.2024 14:18:06 UTC-05:00 - System: Like we don't hold the keys but as far as the chain is concerned they are all valid 24.06.2024 14:18:10 UTC-05:00 - Kev: They do, if I said otherwise, that was my mistake -- since from what I can tell, if they are in the contract then someone has proved ownership of the key 24.06.2024 14:18:21 UTC-05:00 - Matthew Keil: Exactly 24.06.2024 14:19:09 UTC-05:00 - Kev: A proof of possession, means that someone "knows" the secret key assosciated to the public key 24.06.2024 14:21:55 UTC-05:00 - System: the attack we are trying to avoid is that an honest validator registers their public key as A and then a dishonest validator registers a public key -A just after.

For proof of possession, the dishonest validator needs to show that they know the secret key corresponding to -A which would imply they know the secret key for A since its just a negative sign difference. 24.06.2024 14:29:55 UTC-05:00 - Matthew Keil: Oooo... But knowing -A could only make an aggregation of these two keys infinity not P4 in the message I responded to right? 24.06.2024 14:30:31 UTC-05:00 - System: Like the attacker would need to know all the Ps to make P4 24.06.2024 14:30:40 UTC-05:00 - Kev: Yep exactly! 24.06.2024 14:31:19 UTC-05:00 - System: The only way for an attacker to reasonably do that with proof of possession, is to own all of the committee 24.06.2024 14:31:32 UTC-05:00 - Matthew Keil: I need to finish packing but I'll be back in a bit 24.06.2024 14:31:50 UTC-05:00 - System: Which for Coinbase is possible 24.06.2024 14:31:52 UTC-05:00 - Kev: Heading to the gym, so may be offline for a while 24.06.2024 16:19:14 UTC-05:00 - Cayman: ok this makes sense intuitively... But does this still work in the pairing world?

it seems that verify/fast_aggregate_verify checks e(S, G1) = e(P, Hm)
can you just mult in randomness and that still hold true? e(r S, G1) = e(r P, Hm)
All the examples I've seen mult in randomness to the msg, not the pubkeys... and only mult in a single scalar 24.06.2024 16:32:50 UTC-05:00 - Kev: Yep multiplying the randomness would still hold here -- a pairing is mainly a way to check a degree-2 equation where some of the variables have been "committed to"/hidden. So a public key is a way to hide/commit to your secret key, and the pairing allows you to check equations on that secret key value.

Where the idea is generally that; if you know some secret key x then you should know 2 + x its just adding two to it or 2x or in our case H(m) x 24.06.2024 16:37:55 UTC-05:00 - System: So the equation we are checking is that [x H(m)] 1 = [x 1] H(m)

On the LHS:

- I commit to x H(m) using G1 and then call this the signature S
- I then commit to 1 using G2, in your example you called in it G1

On the RHS:

- I commit to x 1 using G1 and this is generally called my public/signing key. In your example, you called it P
- I commit to H(m) using G2 (not sure what this is called in the eth protocol) 24.06.2024 16:41:19 UTC-05:00 - System: The confusing part in the above thing is that it depending on how you "group the terms" dictates what part goes into which paert of the pairing:

(a b) c is the same as a (b c)

And when you multiply by r it's just r (a b) c = r a (b c) -- You can put the r with any of those terms and the equation would still hold true 24.06.2024 16:44:23 UTC-05:00 - System: Not sure if looking at it from an equation perspective makes it easier to reason about -- thats the way it makes sense to me though 😄

Ah I guess the other detail which usually drives implementations, is that operations over G2 are more expensive than G1. So if possible you want to avoid doing things that involve G2, in the case above that would mainly be Hm 24.06.2024 16:50:31 UTC-05:00 - Cayman: ok sweet, that clears that up 24.06.2024 16:51:50 UTC-05:00 - Kev: Oh for the napi-rs stuff, are you folks publishing a package and then using it in lodestar or is it built locally and pulled into lodestar? 24.06.2024 16:52:13 UTC-05:00 - Cayman: we're planning on publishing to npm under code>@chainsafe/blst</code 24.06.2024 16:52:14 UTC-05:00 - Matthew Keil: publishing 24.06.2024 16:53:17 UTC-05:00 - Cayman: just wanting to get this last aggregate with randomness function squared away, do some polishing and attach the existing test harness 24.06.2024 16:53:23 UTC-05:00 - System: then we should be ready to publish 24.06.2024 16:54:07 UTC-05:00 - Kev: Ah okay sweet, I'll check out your github action for publishing -- saw the default napi-rs one and didn't really like the use of qemu for cross-compilation 24.06.2024 16:55:21 UTC-05:00 - Cayman: hah yea some of their publishing stuff could be improved 24.06.2024 16:55:28 UTC-05:00 - Kev: Oh I guess you would be blocked by the blst PR then -- since you'd at least want the inner point to be exposed 24.06.2024 16:55:57 UTC-05:00 - Cayman: if we can't get it upstreamed, we can drop the blst repo into ours as a git submodule or something 24.06.2024 16:56:19 UTC-05:00 - System: definitely more annoying, having to maintain the fork, but an option 24.06.2024 16:57:20 UTC-05:00 - System: or we can do the unsafe thing, and rely on our prebuilt versions having the right behavior 24.06.2024 16:57:40 UTC-05:00 - Kev: That makes sense -- I guess signature verification is that much of a bottleneck 24.06.2024 16:57:54 UTC-05:00 - System: That would definitely keep me up at night 😅 24.06.2024 16:58:17 UTC-05:00 - Cayman: 😂 "whats the worst that could happen" 24.06.2024 16:58:24 UTC-05:00 - System: yea i guess not 24.06.2024 16:58:39 UTC-05:00 - Matthew Keil: is how its built now 24.06.2024 16:59:00 UTC-05:00 - Cayman: yeah as it stands, we're vulnerable to that attack, we were hoping to rebuild the bindings and fix the vulnerability in one swoop 24.06.2024 16:59:18 UTC-05:00 - Matthew Keil: its 35% of main thread time 24.06.2024 16:59:33 UTC-05:00 - System: and the attack surface as well 24.06.2024 17:05:54 UTC-05:00 - Cayman: can we make our randomness optimization better by adding randomness to the message instead of public keys? even tho the msg is in G2, that would be a single multiplication vs one mult per pubkey 24.06.2024 17:07:08 UTC-05:00 - System: not sure how to mult a list of scalars with single message tho 24.06.2024 17:07:32 UTC-05:00 - System: and the existing interfaces don't seem very helpful for doing this 24.06.2024 17:08:27 UTC-05:00 - Kev: Oh hmm -- I don't see why not -- though I'd need to double check to see if there might be an attack 24.06.2024 17:09:39 UTC-05:00 - System: I think you would do the multiplications separately, so combine the list of scalars and then do a scalar multiplication. Though you would need to use blst_fr instead of blst_scalar for that 24.06.2024 17:11:50 UTC-05:00 - System: It seems that it was also discussed on the original post: https://ethresear.ch/t/fast-verification-of-multiple-bls-signatures/5407/8 24.06.2024 17:12:10 UTC-05:00 - Cayman: yup, and i bet this is part of the confusion with dot-asm 24.06.2024 17:13:01 UTC-05:00 - System: he's wondering why we'd mult in randomness to pks when everyone just mults in randomness to msgs 24.06.2024 17:13:34 UTC-05:00 - System: ok so you'd sum the rand blst_frs and scalar mult the result with the message? 24.06.2024 17:14:24 UTC-05:00 - System: that sounds faster than msming the rands with pks 24.06.2024 17:15:15 UTC-05:00 - Kev: I'm not entirely sure why kirk and vitalik on that post said aggregating the public keys is faster than multiplying by the message 24.06.2024 17:15:51 UTC-05:00 - System: Yep, if you're doing r1 Hm + r2 Hm, we can factor out the Hm and do (r1 + r2)*Hm 24.06.2024 17:22:28 UTC-05:00 - Cayman: ah, i guess multiplying the message makes sense when there are more pubkeys than unique msgs, where you'd have to do more mults when multiplying the pubkeys (as we're seeing now) 24.06.2024 17:23:15 UTC-05:00 - System: and aggregating the public keys first vs doing separate verifications seems to just be fast_aggregate_verify 24.06.2024 17:24:48 UTC-05:00 - System: it seems they're kinda glossing over interweaving fast_aggregate_verify into this system 24.06.2024 17:25:30 UTC-05:00 - System: his construction starts with "Suppose that you received n signatures, S1 … Sn, where each signature Si is itself an aggregate signature" 24.06.2024 17:26:10 UTC-05:00 - Kev: Yeah that post is for the case where you've already aggregated all signatures+pubkeys with the same message 24.06.2024 17:26:42 UTC-05:00 - Cayman: we're extending this by starting with unaggregated signatures, and instead of a vec of random scalars, its a vec of vecs of random scalars 24.06.2024 17:27:32 UTC-05:00 - System: where the vecs of random scalars get multed into signatures when they get aggregated, and then the vecs of random scalars get summed before being multed into messages 24.06.2024 17:29:21 UTC-05:00 - System: but we wanted to do this in two steps because this construction is just a pass/fail, and if you fail, you have to re-verify everything individually. if we do it in two steps, we can "save" the signature and pubkey aggregation per unique message, rather than having to re-aggregate 24.06.2024 17:29:40 UTC-05:00 - Kev: right that makes sense 24.06.2024 17:29:48 UTC-05:00 - System: Why individually? 24.06.2024 17:30:28 UTC-05:00 - System: Or maybe its not possible to just halve the set and do two smaller aggregations, like a binary search 24.06.2024 17:30:59 UTC-05:00 - Cayman: ah, right.. we just fall back to naive individual verification 24.06.2024 17:35:21 UTC-05:00 - System: actually, i don't think the fact that it's in two steps matters to us at all 24.06.2024 17:36:08 UTC-05:00 - System: we're just falling back to naive individual verification, we're not using any of our saved aggregated sigs/pubkeys 24.06.2024 18:59:02 UTC-05:00 - Cayman: ok i have something compiling that first mults in randomness into unaggregated signatures, then sums the randoms and uses them at a higher level to do batch verification 24.06.2024 18:59:03 UTC-05:00 - System: https://github.com/ChainSafe/blst-ts/pull/149/commits/f0022349debc7f0d3c1587951b0e2d03dc8444e6 24.06.2024 18:59:14 UTC-05:00 - System: its not pretty rust, but i guess it proves the point 24.06.2024 19:00:33 UTC-05:00 - System: tired for today, but tomorrow i'll benchmark that against multing randoms into pks during aggregation, then doing batch verification 24.06.2024 19:56:04 UTC-05:00 - Cayman: this actually doesn't work bc the randomness will be applied to the signatures twice... 24.06.2024 19:56:15 UTC-05:00 - System: so it seems we can't reuse verify_multiple_aggregate_signatures Unknown time - System: 25.06.2024 08:29:08 UTC-05:00 - Cayman: he responded again :) https://github.com/supranational/blst/pull/225#issuecomment-2188746319 25.06.2024 08:31:37 UTC-05:00 - Matthew Keil: He is in it to win it! Your last comment was epic btw 25.06.2024 08:37:28 UTC-05:00 - Kev: Something that I don't understand yet, is whether clients receive all signatures they need to verify and then they get aggregated in this two step process, or if clients receive signatures for the same message (then tentatively aggregate those and verify)

If its the former or if we could get to a stage where its the former, then I think doing the massive aggregation makes sense 25.06.2024 08:39:50 UTC-05:00 - System: If we say it takes 1ms to verify 2^17 signatures with this approach, then even if we had a bad signature, with the binary approach it would take log(2^17) =17 iterations to find it, so 17ms which seems okay to me 25.06.2024 08:40:04 UTC-05:00 - System: It would be less than 17ms, since each time the set is halved 25.06.2024 08:41:34 UTC-05:00 - System: This makes sense to me, doing a full-width scalar Multiplication would be quite expensive, versus doing MSM where we spicy that the scalar is 64 bits and the cost is amortized across the MSM 25.06.2024 08:56:13 UTC-05:00 - Cayman: well clients are receiving a constant stream of unaggregated attestations over gossip, and most of the attestations are signed over the same message (AttestationData), ends up being ~84% of attestations are for an already-seen AttestationData 25.06.2024 08:57:49 UTC-05:00 - System: right now, those unaggregated attestations are only mostly signed over the same AttestationData within each subnet, which practically limits the amount of aggregation to the size of the committee 25.06.2024 08:59:00 UTC-05:00 - System: but in a post-electra world, with EIP-7549, which pulls out the committee index from the AttestationData, then all unaggregated attestations across all subnets can be aggregated 25.06.2024 08:59:53 UTC-05:00 - Kev: Oh I see, so this means it will grow 64 x average committee size, it being the number of signatures over the same message? 25.06.2024 09:00:16 UTC-05:00 - Cayman: in practice, beacon nodes are "required" to subscribe to 2 subnets, along with whichever subnets they need per epoch to publish their own attestations 25.06.2024 09:00:27 UTC-05:00 - System: most beacon nodes aren't subscribed to all subnets 25.06.2024 10:59:36 UTC-05:00 - Kev: Francessco (EF researcher) was interested in what and why you folks were optimizing (I mentioned it on our weekly call) -- I don't know enough about the consensus-client to speak about the suecase in detail at the moment, he suggested a group channel so you folks can talk more about it 🙂