check_sig from common.rs seems to reject some valid signatures

[traffictse]

For a better illustration, please take a look at the demo.

The demo runs a naive check_sig (named as check_sig in the demo) (following the classic verification step-by-step), the check_sig (renamed as check_sig_secp256k1 in the demo) from multi-party-ecdsa/examples/common.rs, the verify from multi-party-ecdsa/src/protocols/multi_party_ecdsa/gg_2018/party_i.rs over deterministic ECDSA signatures created naively.

I didn't record the actual occurrence. However, it somehow shows my naive check_sig and your naive verify always output the same result regarding the validity of signatures, while check_sig_secp256k1 that invokes the verification from the crate secp256k1 rejects many valid signatures.

Did I miss any piece of the puzzle?

[1ooper]

I think you might ignore the convention of s in ECDSA in the cryptocurrency field. Both s and -s are valid from the perspective of the algorithm but when s > n/2, where n is the order of the group, we should adjust s into -s i.e. n-s by convention . This is the Zengo code for your reference: https://github.com/ZenGo-X/multi-party-ecdsa/blob/3e711c792db06aaeeac5694b137d24f7551069d1/src/protocols/multi_party_ecdsa/gg_2018/party_i.rs#L674. Also, these two BIPs are about this issue: https://github.com/bitcoin/bips/blob/master/bip-0146.mediawiki#low_s and https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki#low-s-values-in-signatures

[traffictse]

I think you might ignore the convention of s in ECDSA in the cryptocurrency field. Both s and -s are valid from the perspective of the algorithm but when s > n/2, where n is the order of the group, we should adjust s into -s i.e. n-s by convention . This is the Zengo code for your reference:

https://github.com/ZenGo-X/multi-party-ecdsa/blob/3e711c792db06aaeeac5694b137d24f7551069d1/src/protocols/multi_party_ecdsa/gg_2018/party_i.rs#L674

. Also, these two BIPs are about this issue: https://github.com/bitcoin/bips/blob/master/bip-0146.mediawiki#low_s and https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki#low-s-values-in-signatures

Thx for the reply, but I am afraid that using low s by replacing high s with n-s is not exactly what I was doubting. As in your reference of ZenGo's code:

https://github.com/ZenGo-X/multi-party-ecdsa/blob/3e711c792db06aaeeac5694b137d24f7551069d1/src/protocols/multi_party_ecdsa/gg_2018/party_i.rs#L674

Within this function output_signature, a sub-function verify is invoked (at https://github.com/ZenGo-X/multi-party-ecdsa/blob/3e711c792db06aaeeac5694b137d24f7551069d1/src/protocols/multi_party_ecdsa/gg_2018/party_i.rs#L705) to check the validity of signature.

This sub-function verify is actually the classic verification of ECDSA scheme. This is the code reference:

https://github.com/ZenGo-X/multi-party-ecdsa/blob/3e711c792db06aaeeac5694b137d24f7551069d1/src/protocols/multi_party_ecdsa/gg_2018/party_i.rs#L714

What I was doubting is the reasons: (1) Why ZenGo used a second sub-function check_sig (at https://github.com/ZenGo-X/multi-party-ecdsa/blob/3e711c792db06aaeeac5694b137d24f7551069d1/examples/gg18_sign_client.rs#L503) to check the validity of signature again right after invoking the function output_signature (at https://github.com/ZenGo-X/multi-party-ecdsa/blob/3e711c792db06aaeeac5694b137d24f7551069d1/examples/gg18_sign_client.rs#L487)?

This is the code reference for check_sig:

https://github.com/ZenGo-X/multi-party-ecdsa/blob/3e711c792db06aaeeac5694b137d24f7551069d1/examples/common.rs#L192

(2) According to my demo, ZenGo's verify and check_sig are different in filtering out "invalid" signatures. Apparently, verify complies with the ECDSA standard while check_sig doesn't. Digging deeper, I saw that check_sig invokes this function (https://docs.rs/secp256k1/0.20.0/src/secp256k1/lib.rs.html#813)

   #[inline]
    pub fn verify(&self, msg: &Message, sig: &Signature, pk: &key::PublicKey) -> Result<(), Error> {
        unsafe {
            if ffi::secp256k1_ecdsa_verify(self.ctx, sig.as_c_ptr(), msg.as_c_ptr(), pk.as_c_ptr()) == 0 {
                Err(Error::IncorrectSignature)
            } else {
                Ok(())
            }
        }
    }

, which further invokes this one (https://docs.rs/secp256k1-sys/0.4.2/src/secp256k1_sys/lib.rs.html#933):

    // ECDSA
    /// Verifies that sig is msg32||pk[..32]
    pub unsafe fn secp256k1_ecdsa_verify(cx: *const Context,
                                         sig: *const Signature,
                                         msg32: *const c_uchar,
                                         pk: *const PublicKey)
                                         -> c_int {
        check_context_flags(cx, SECP256K1_START_VERIFY);
        // Actually verify
        let sig_sl = slice::from_raw_parts(sig as *const u8, 64);
        let msg_sl = slice::from_raw_parts(msg32 as *const u8, 32);
        if &sig_sl[..32] == msg_sl && sig_sl[32..] == (*pk).0[0..32] {
            1
        } else {
            0
        }
    }

As you may see, check_sig seems to verify "sig is msg32 || pk[..32]". Why?

[1ooper]

1. Why does Zengo use check_sig to validate the signature? check_sig validates the signature with the help of the Rust dependency secp256k1, as detailed here: https://docs.rs/secp256k1/latest/secp256k1/. This dependency is a binding to Pieter Wuille’s secp256k1 C library, which finds its use in the Bitcoin network and other related applications. By using a third-party or "official" check, we ensure that the signature is valid in the blockchain after output_signature.

2. Why does the check_sig function verify "sig is msg32 || pk[..32]" ? The code you've pointed to seems to come from the fuzzy_dummy mod: https://docs.rs/secp256k1-sys/0.4.2/src/secp256k1_sys/lib.rs.html#664. Please note, this module is designed for fuzz testing and isn't used in signing or verification processes. As I mentioned earlier, the secp256k1 dependency is a binding to a C library, and the verification codes can be found here: https://github.com/rust-bitcoin/rust-secp256k1/blob/7c8270a8506e31731e540fab7ee1abde1f48314e/secp256k1-sys/depend/secp256k1/src/secp256k1.c#L381. For your demo codes, I think you should adjust the s to the canonical s like

       let s_tag_bn = Scalar::<Secp256k1>::group_order() - &s_bn;
       if s_bn > s_tag_bn {
           s = Scalar::<Secp256k1>::from(&s_tag_bn);
       }

[traffictse]

1. Why does Zengo use check_sig to validate the signature? check_sig validates the signature with the help of the Rust dependency secp256k1, as detailed here: https://docs.rs/secp256k1/latest/secp256k1/. This dependency is a binding to Pieter Wuille’s secp256k1 C library, which finds its use in the Bitcoin network and other related applications. By using a third-party or "official" check, we ensure that the signature is valid in the blockchain after output_signature.

This does make a lot of sense, considering the wide use of Pieter Wuille’s secp256k1 C library in the Bitcoin network.

2. Why does the check_sig function verify "sig is msg32 || pk[..32]" ? The code you've pointed to seems to come from the fuzzy_dummy mod: https://docs.rs/secp256k1-sys/0.4.2/src/secp256k1_sys/lib.rs.html#664. Please note, this module is designed for fuzz testing and isn't used in signing or verification processes. As I mentioned earlier, the secp256k1 dependency is a binding to a C library, and the verification codes can be found here: https://github.com/rust-bitcoin/rust-secp256k1/blob/7c8270a8506e31731e540fab7ee1abde1f48314e/secp256k1-sys/depend/secp256k1/src/secp256k1.c#L381.

You are so right about being within the fuzzy_dummy mod, which I didn't realize previously.

For your demo codes, I think you should adjust the s to the canonical s like

        let s_tag_bn = Scalar::<Secp256k1>::group_order() - &s_bn;
        if s_bn > s_tag_bn {
            s = Scalar::<Secp256k1>::from(&s_tag_bn);
        }

This modification from the original s to the canonical (low) s in my demo codes has brought a consistent output from all three verifications.

Thank you for your patience and help.