Add frost-secp256k1-tr crate (BIP340/BIP341)

[zebra-lucky]

• add frost-secp256k1-tr crate with support of BIP0340, BIP0341

[conradoplg]

Thank you, this is great. I'll take a closer look soon and may make some adjustments.

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 74.30684% with 139 lines in your changes are missing coverage. Please review.

Project coverage is 81.07%. Comparing base (5f4ac6e) to head (b360496). Report is 4 commits behind head on main.

:exclamation: Current head b360496 differs from pull request most recent head c63a3ca. Consider uploading reports for the commit c63a3ca to get more accurate results

Files	Patch %	Lines
frost-core/src/traits.rs	16.92%	54 Missing :warning:
frost-secp256k1-tr/src/lib.rs	85.20%	46 Missing :warning:
frost-secp256k1-tr/src/keys/dkg.rs	0.00%	21 Missing :warning:
frost-secp256k1-tr/src/keys/repairable.rs	59.09%	18 Missing :warning:

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #584      +/-   ##
==========================================
- Coverage   82.18%   81.07%   -1.11%     
==========================================
  Files          31       34       +3     
  Lines        3188     3694     +506     
==========================================
+ Hits         2620     2995     +375     
- Misses        568      699     +131     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[conradoplg]

After a closer look, here are some things that we'd prefer to change before merging this PR:

• The current approach changes the key (to ensure a even Y in the public key) during the signing operation. This makes sense if you follow BIP-340 directly. However, with FROST, I think it would be better and simpler to change the key during share generation, i.e. if the public key as an odd Y, negate all the shares, verifying shares, etc. This would make the PR much less invasive since the signing code would not change. You can take a look at this PR from the reddsa crate which does basically the same thing
• The PR also tweaks the key per BIP-341 with an empty merkle root. As I understand this wouldn't work in practice since the merkle root needs to be specified. I think this can be accomplished separately, using the frost-rerandomized crate - I think that the Taproot tweak is basically equal to rerandomization, but with a specific tweak rather than a random one.

I realize these might be big changes. Let me know if this makes sense and if you are able to work on this. Otherwise we can eventually incorporate these changes to the PR, but might not be able to get that done shortly.

Also - what did you use to generate the test vectors? Do you have a separate reference implementation for this? I'd like to take a look if possible.

[zebra-lucky]

I realize these might be big changes. Let me know if this makes sense and if you are able to work on this. Otherwise we can eventually incorporate these changes to the PR, but might not be able to get that done shortly.

I'll try to add changes to generation process to use only even VerifyingKey

On the "emtpy merkle root" -- need to do more investigations, but current code is working. As a proof I'll add a link on the repo with testing code to sign tx (in the next post).

Also - what did you use to generate the test vectors? Do you have a separate reference implementation for this? I'd like to take a look if possible.

On testing vectors -- I just added the values from the working code so the tests wouldn't fail.

[zebra-lucky]

Some proofs that the current code works

Testing code on the Testnet sign-tx-frost https://github.com/zebra-lucky/sign-tx-frost

To use there is a need to fix paths in the Cargo.toml

frost-core = { version = "1.0.0-rc.0", features = ["serde"], path = "../frost.copy/frost-core" }
...
frost-secp256k1-tr = { version = "1.0.0-rc.0", features = ["serde"], path = "../frost.copy/frost-secp256k1-tr"  }

• generate command outputs to stdout and this can be saved in testdata.json
• address command show address on generated VerifyinKey in the testdata.json
• sendtoaddress allow sign and get hex of output transaction with arguments in the form:

sendtoaddress tb1pqkgsz274gjnkdxp7v9rpzwqtqtjacjp5t2mz2vaqu2r6qln8qsesve6uez 1000 02000000000101bf2d2d426...

Where last part is a hex of transaction which makes output on generated address.

Some dirty but working code.

Latest transactions on the Testnet: https://live.blockcypher.com/btc-testnet/address/tb1pqkgsz274gjnkdxp7v9rpzwqtqtjacjp5t2mz2vaqu2r6qln8qsesve6uez/

[mimoo]

Just FYI we're testing this library on Bitcoin and getting flaky results (sometimes signature fails). I'm investigating on our side to understand if it's us or if there's some issue here (my current intuition is that the issue is here).

~Maybe the issue that I'm seeing is because the negation happens based on key_package.verifying_key().y_is_odd(), but it should happen based on the tweaked verifying/public key instead (i.e. tweaked_public_key(key_package.verifying_key(), &[]).y_is_odd()).~

In addition, I had another issue which led me to spend quite some time reviewing this PR, so here are some notes and some reverse-engineering notes (for others who are trying to understand this like me):

1. it seems like there's no way to tweak the merkle tree from public facing function
2. ~half of the changes seems to be about conditional negation of "stuff". IIUC, it is needed to ensure that when the tweaked public key starts with 0x03 it is forced to start with 0x02 (as 0x03 prefix is not supported by taproot).~
3. ~Now I'm wondering, in Bitcoin how do they ensure that every tweak leads to a pubkey that starts with 0x02? -> ah, BIP 341 says "Note that because tweaks are applied to 32-byte public keys, taproot_tweak_seckey may need to negate the secret key before applying the tweak." so that makes sense with my previous comment!~
4. the term "tweak" is overused throughout the codebase (even sometimes in tests to mean tampering). IMO it shouldn't be used in most of these places as it collides with "tweak" of pubkey in taproot (it confused me a lot when I started reviewing this PR). Same comment with is_need_tweaking which imo should be renamed (e.g. bitcoin_spec, bitcoin_compat, etc.)
5. ~I initially thought that each participant would need to tweak their private share, but no need! The aggregator can do it at the end (z = k + s * c becomes z = k + (s + tweak) * c = (k + s * c) + (tweak * c) so tweak * c is added at the end)~
6. It's not clear how to use the taproot lib with the current types, as we don't know if a pubkey is tweaked or untweaked. Things just work magically because verify will end up calling tweaked_public_key. I had to understand all the code in this PR to manage to fix another issue I had: I didn't get I had to tweak the pubkey on my side if I wanted to verify a signature using a different library than frost). A such I would really recommend not inserting magic logic in the verify function but rather getting a tweaked pubkey out (maybe verifying_key() could fail with the taproot version, and you'd be forced to use a tweaked_verifying_key(tweak: &[u8]) which would be unimplemented in the trait?

Nevermind, I wrote my understanding here: https://hackmd.io/li6ByhmfQUucZOqdboF1-g?view

I'm still unsure as to why we're seeing issues on our side atm.

[mimoo]

I fixed all the comments I pointed out in https://github.com/zebra-lucky/frost/pull/1 and everything now works on our end!

(bonus, the art that helped me find the issues)

[zebra-lucky]

Nevermind, I wrote my understanding here: https://hackmd.io/li6ByhmfQUucZOqdboF1-g?view

Thanks!, I'll read it to realize.

[zebra-lucky]

I am looking at the changes proposed in https://github.com/zebra-lucky/frost/pull/1

[zebra-lucky]

Merged fix on tweaked public key processing from @mimoo. https://github.com/zebra-lucky/frost/pull/1

I'll add DKG/trusted dealer code which generates only even VerifyingKey in a few hours.

[zebra-lucky]

Some problems on tests::batch::check_batch_verify arised, need more time to resolve.

[mimoo]

I'll add DKG/trusted dealer code which generates only even VerifyingKey

actually that might be overkill since all the checks must happen anyway no?

[zebra-lucky]

actually that might be overkill since all the checks must happen anyway no?

yep... thinking on that...

currently stuck on batch test... signing with SigningKey...

[zebra-lucky]

Added:

• Some more fixes on tweaked public key use after https://github.com/zebra-lucky/frost/pull/1 merge
• Renamed fn with more consistent names
• add DKG vector test for frost-secp256k1-tr (as in recent commits for other curves)

There is a question about only even VerifyingKey generation with DKG/trusted dealer. This code is done, but tweaked public key can independently be even or odd. I'll try to analyse tomorrow, but seems no overall code simplification can be done. But maybe some refactoring on current code should be done.

Note about merkle root (as in BIP341 code example):

def taproot_sign_key(
    script_tree,
    internal_seckey,
    hash_type,
    bip340_aux_rand
):
    if script_tree is None:
        h = bytes()
...

For key path spending script_tree is absent, so empty bytes value set as h

[zebra-lucky]

p.s.: rebased PR branch on current main branch

[Polybius93]

Hey all!

I hope I it's okay to post this here, but let me know if I should ask this somewhere else, or make an issue. My question about signing Schnorr that I think might be related to this PR.

I'm encountering an issue when broadcasting a PSBT transaction signed using FROST for aggregated Schnorr signatures. While individual Schnorr signatures work correctly, the aggregated signature fails with the following error:

"sendrawtransaction RPC error: {"code":-26,"message":"non-mandatory-script-verify-flag (Invalid Schnorr signature)"}

We generate a hash from the PSBT's unsigned transaction and sign it using a keypair. This process completes without errors.

let hash = SighashCache::new(&psbt.unsigned_tx.clone())
            .taproot_script_spend_signature_hash(
                0,
                &Prevouts::All(&[tx_out.clone()]),
                ScriptPath::with_defaults(&multisig_script),
                SchnorrSighashType::Default,
            )
            .unwrap_throw();

let sig = secp.sign_schnorr(
            &Message::from_slice(&hash).unwrap_throw(),
            &keypair,
);

When using FROST to sign the transaction, we provide the same hash as the message parameter for the SigningPackage.

let signing_package =
                frost::SigningPackage::new(signing_state.signing_commitments.clone(), hash);

The process creates an aggregated signature, but broadcasting the transaction results in the above error.

Given the transition from successful individual signing to the failure of the FROST aggregated signature, is there a specific aspect of message handling or signature aggregation with FROST that needs to be adjusted for these transactions? Any insights or suggestions on resolving the "Invalid Schnorr signature" error would be greatly appreciated.

Also I'm wondering if I need the _tr library for the signing process I'm doing, or if it would be enough to just use the frost_secp256k1 library?

Thanks!

[zebra-lucky]

I'm encountering an issue when broadcasting a PSBT transaction signed using FROST for aggregated Schnorr signatures. While individual Schnorr signatures work correctly, the aggregated signature fails with the following error:

Hello!

Need to clarify details. On the first commits to the this PR there was a problems with combinations of pubkey/tweaked pubkey, which lead to invalid sig. Currently it's seems to be fixed with @mimoo help.

Do you use the latest commit of frost-secp256k1-tr b3604963317a93ab8398e674d02c9489a7697a6a?

There is some testing code on the testnet to check how it's works: https://github.com/zebra-lucky/sign-tx-frost

[zebra-lucky]

Also I'm wondering if I need the _tr library for the signing process I'm doing, or if it would be enough to just use the frost_secp256k1 library?

frost-secp256k1 is a general on a curve, frost-secp256k1-tr adds some specifics from BIP340/341

[conduition]

I'm encountering an issue when broadcasting a PSBT transaction signed using FROST for aggregated Schnorr signatures. While individual Schnorr signatures work correctly, the aggregated signature fails with the following error:

@Polybius93 The standard frost-secp256k1 crate isn't compatible with BIP340 taproot signatures by default. The reason is twofold:

• FROST uses differently namespaced hash functions to determine whether signatures are valid. Also FROST encodes the nonce as a compressed point instead of a BIP340 x-only point when hashing it for the challenge. This PR addresses that here and here.
• BIP340 has a lot of baked-in logic which was added to allow 32-byte compact x-only pubkeys, and 64-byte compact signatures without malleability. It requires signing code to constantly check 'does the point generated by this scalar have an even Y coordinate? if not, negate the scalar.' FROST doesn't do this by default, hence why this PR has lots of if taproot { /* do negation stuff */ } else { ... } statements.

To be able to sign taproot transactions, this PR will be needed

[Polybius93]

Thank you for the answer @conduition , I appreciate it!

[Polybius93]

Hey! Thank you for your answer @zebra-lucky ! Yes, I am using the latest commit. I was looking into your testing code, thank you for sharing it! Currently we are still trying to figure out how to make a valid signature for our use case. I'll get back to you if we have some answers! Thank you!

[0xBEEFCAF3]

@Polybius93 Something else to keep in mind. Looks like you are doing a taproot script spend.

let hash = SighashCache::new(&psbt.unsigned_tx.clone())
            .taproot_script_spend_signature_hash(
                0,
                &Prevouts::All(&[tx_out.clone()]),
                ScriptPath::with_defaults(&multisig_script),
                SchnorrSighashType::Default,
            )
            .unwrap_throw();

Anyone else feel free to correct me if I am wrong, but this crate hardcodes an empty taptweak. Meaning if the FROST agg key is your internal taproot key then you cannot spend from an alternative tapscript. It is however possible to use the FROST agg key in a tapscript with OP_CHECKSIG.

[sosaucily]

Thanks @0xBEEFCAF3 , Yep I think that's the problem, @Polybius93 FYI. We're going to look into either adding support for script spend into this branch, or perhaps forking off this fork and building it in there!

[conduition]

@zebra-lucky I have a few suggestions to clean up the code. Expect a PR to your repo sometime soon :sunglasses:

[conduition]

PR opened here: https://github.com/zebra-lucky/frost/pull/2

Its purpose is to improve the overall readability and 'correctness' of the naming conventions in this PR. It renames all of the methods to be more generally applicable to any ciphersuite, and removes the is_taproot_compat method in favor of stubbing the methods to return sensible defaults under the existing ciphersuites.

I also added more rustdoc comments to make the public changes on this PR more developer-friendly.

[zebra-lucky]

PR opened here: zebra-lucky#2

Thank you! I'll review it now.

[zebra-lucky]

Can not test today with sign-tx-frost, created issue https://github.com/zebra-lucky/sign-tx-frost/issues/1

Try to fix it tomorrow.

[zebra-lucky]

• Fixed docstrings as mentioned in: https://github.com/zebra-lucky/frost/pull/2#discussion_r1498551101
• Fixed sign-tx-frost with use of rust-bitcoin, sign/verify is ok: https://github.com/zebra-lucky/sign-tx-frost/commit/21092dd516cf1b020c24ea2c287413fe2255daf1

Possibly need to rebase on current main branch, will do it in a day.

[conduition]

@zebra-lucky I'm noticing a footgun here. The VerifyingKey by default is un-tweaked, so a naive caller won't be able to verify signatures unless they manually tweak the verifying key themselves with an empty tweak. Here's how your code is doing it. For those unfamiliar with taproot, this is pretty arcane.

We should provide some way to convert the untweaked verifying key into a tweaked one, and hopefully include some way to configure how and whether to tweak signatures. That way this PR can be used not just for key-spending, but also for committing to arbitrary taproot tweaks.

I'm gonna have a think about this and get back to you next week with some suggestions

[zebra-lucky]

I'm gonna have a think about this and get back to you next week with some suggestions

Thank you! I'll reread BIP341 on script spend variants, and look to early mentioned https://github.com/sigma0-xyz/zkbitcoin for examples.