Check validity of a partial signature?

[robertsdotpm]

Hello, I was reading the tests for aggregate signatures and I noticed there didn't seem to be any asserts to check the validity of partial signatures. Is this an easy feature to add to the library?

[omershlo]

@robertsdotpm are you referring for example to party2 not validating party1 local sig s1: https://github.com/KZen-networks/multi-party-schnorr/blob/master/src/protocols/aggsig/test.rs#L83
?

If this is the case :

1. From technical point of view adding verification for partial signatures can be done by the receiving party because it has all that it needs for that
2. In practice this is probably not needed. If you look at the papers you would not find this step. (https://github.com/KZen-networks/multi-party-schnorr/blob/master/papers/compact_multi_signatures_for_smaller_blockchains.pdf section 5.1 step3). It seems that it has no effect on the security proof. btw, this step is also not needed in the other protocol currently implemented (check https://github.com/KZen-networks/multi-party-schnorr/blob/master/papers/accountable_subgroups_multisignatures.pdf signing page 11).

[robertsdotpm]

The problem is if there are multiple people inputting partial signatures and the aggregate signature fails how do you know which partial signature was the problem? Is there a way to incrementally verify them instead of relying on trusted input?

[omershlo]

Yes, verifying a partial signature is the same as verifying the aggregated signature. It can be done by calling verify with that party public key and ephemeral public key. The current API can support that but we can maybe do a bit of renaming and add this to the test for #17.

Since this is not part of the protocol itself (see my comment above) and the network configuration can depend on the use case: i.e. there is one dealer that gets all the partial signatures and only he can do this test, or there is a "round robin" configuration such that each party pass the aggregated signature so far to another party and each party or all peers get all partial signatures from all other peers and all do all tests - I suggest that we add a test to show that it is possible and do this little renaming at this level. Usage of this will be up to higher code level to decide. wdyt?

[robertsdotpm]

I agree with you. It seems up to the protocol to add support for this but knowing how to do it would be very useful. I've tried to modify the tests to do this myself but I wasn't successful:

let s1 = EphemeralKey::sign(
    &party1_ephemeral_key,
    &party1_h_0, // H0(Rtag || apk || message)
    &party1_key,
    &party1_key_agg.hash,
);
let r = party1_ephemeral_key.keypair.public_key.x_coor();
assert!(verify(&s1, &r, &party1_key.public_key, &message, is_musig,).is_ok());

Based on the 2 party signing example. N party aggregation seems to work fine though which is really cool. I've already tested 3 just to see that 2 wasn't a fixed size or something 👍

[omershlo]

cool! feel free to pr this test.
you made a good point here - the current verify method cannot be used for partial signature verification (because it is assumed that apk is the public key and also used for the challenge). It means that we should make some change to verify method to support this or add another verify specifically for this case.

[robertsdotpm]

After some trial and error I seem to have got it working. Hopefully the math behind this is correct:

pub fn verify_partial(
    signature: &BigInt,
    r_x: &BigInt,
    c: &BigInt,
    a: &BigInt,
    key_pub: &GE,
    message: &[u8],
    musig_bit: bool,
) -> Result<(), ProofError> {
    let base_point: GE = ECPoint::generator();
    let curve_order = FE::q();

    let minus_c = BigInt::mod_add(&curve_order, &c, &curve_order);
    let minus_c_fe: FE = ECScalar::from(&minus_c);
    let minus_a = BigInt::mod_sub(&curve_order, &a, &curve_order);
    let minus_a_fe: FE = ECScalar::from(&minus_a);
    let signature_fe: FE = ECScalar::from(signature);

    let sG = base_point.scalar_mul(&signature_fe.get_element());
    let key_pub = key_pub.scalar_mul(&minus_a_fe.get_element());
    let cY = key_pub.scalar_mul(&minus_c_fe.get_element());
    let sG = sG.add_point(&cY.get_element());

    if sG.x_coor().to_hex() == *r_x.to_hex() {
        Ok(())
    } else {
        Err(ProofError)
    }
}

Then you just pass hashes in directly and use their individual keys:

        let r = party1_ephemeral_key.keypair.public_key.x_coor();
        assert!(verify_partial(&s1, &r, &party1_h_0, &party1_key_agg.hash, &party1_key.public_key, &message, is_musig,).is_ok());

[omershlo]

Nice.
making the syntax more readable:

pub fn verify_partial(
    signature: &FE,
    r_x: &BigInt,
    c: &FE,
    a: &FE,
    key_pub: &GE,
) -> Result<(), ProofError> {

    let g: GE = ECPoint::generator();
    let sG = g * signature;
    let cY = key_pub * a * c;
    let sG = sG.sub_point(&cY.get_element());


    if sG.x_coor().to_hex() == *r_x.to_hex() {
        Ok(())
    } else {
        Err(ProofError)
    }
}

 let r = party1_ephemeral_key.keypair.public_key.x_coor();
assert!(verify_partial(&ECScalar::from(&s1), &r, &ECScalar::from(&party1_h_0), &ECScalar::from(&party1_key_agg.hash), &party1_key.public_key).is_ok());

This is the same but the math now is using only FE,GE which is more healthy way to do. Still more room to improvement.

btw since you are passing c directly there's no need to pass musig and message but it is much better to do and to add a check that c was computed correctly.

[robertsdotpm]

Your code is definitely better. I'm not sure I understand how it works though. In my code I thought I was subtracting a from the pub key but you get the same result without doing anything funky to a. Now I don't know how my code was able to work at all.

[omershlo]

Let me explain the equivalence:
my code is checking : R == sG - a*c*PK
your code is checking : R == sG + (q+a)(q-c)PK = sG + qqPK +aqPK -cqPK -acPK = sG -a*c*PK