Schnorrsig sign with tweak #1015

Currently BIP341 recommends:

If the spending conditions do not require a script path, the output key should commit to an unspendable script path instead of having no script path. This can be achieved by computing the output key point as Q = P + int(hashTapTweak(bytes(P)))G.

This would require tweaking the private key before signing.

Currently, the only way I can work around this with my downstream library is:

• calculate the pubkey
• see if it's even or odd
• negate the privkey if odd
• tweak the privkey

Then when I pass it to this library, it does steps 1-3 again before signing (to negate it)

If there was a variation of secp256k1_schnorrsig_sign that accepted a tweak, and would tweak the privkey after any negation, and before the signature calculation, that would be extremely helpful.

Then we could just pass the tweak (int(hashTapTweak(bytes(P)))) in and everything would be more efficient.

I would like to hear what everyone thinks about adding a secp256k1_schnorrsig_sign_with_tweak function.

Also, taking this one step further, we could also add secp256k1_schnorrsig_sign_keyspend_only which will generate the tweak for us based on Q = P + int(hashTapTweak(bytes(P)))G and then pass it into secp256k1_schnorrsig_sign_with_tweak

Any and all feedback appreciated.

(Also note that while BIP341 recommends it, BIP86 (bip32 derivation scheme) requires it... so it looks like wallets that don't use this trick will run into compatibility issues down the road.)

Currently, the only way I can work around this with my downstream library is:

* calculate the pubkey
* see if it's even or odd
* negate the privkey if odd
* tweak the privkey

Then when I pass it to this library, it does steps 1-3 again before signing (to negate it)

Checking evenness and negating the privkey/seckey is very cheap, it's about 5 ns on my machine. So the only expensive step is step 1, which involves an EC multiplication. For the entire computation, you necessarily need two EC multiplications, because you want to compute two pubkeys: P and Q.

Now with our keypair type, which you're required to use with secp256k1_schnorrsig_sign, you would

• create a keypair from your seckey with secp256k1_keypair_create (EC multiplication that results in P)
• tweak the keypair with secp256k1_keypair_xonly_tweak_add (one EC multiplication that results in Q)
• sign with secp256k1_schnorrsign_sign (no EC multiplication because Q is stored in the keypair given to the function)

So we need two EC multiplications, which is optimal, no?

Yes. This is optimal if you are always in the C(/C++/Rust/WASM) space.

The major problem I have is that I am using this library through WASM, so data being managed by JS is not persisted in WASM between calls.

Perhaps a better idea would be to compute the mid-state of taptweak taggedhash as a const, and have a secp256k1_schnorrsig_sign_with_taptweak_preimage which would take in the data you want to pass to the TapTweak taggedhash (beside the pubkey).

So Q = P + int(hashTapTweak(bytes(P) + merkle_root_bytes))G we would pass in merkle_root_bytes. If it's empty, then it will just use P.

This has the advantage of also speeding up these operations for C/C++/Rust users as well instead of needing to initialize sha256 every time.

Please tell me if I'm wrong.

This is the mid-state for "TapTweak"

    sha->s[0] = 0xd129a2f3ul;
    sha->s[1] = 0x701c655dul;
    sha->s[2] = 0x6583b6c3ul;
    sha->s[3] = 0xb9419727ul;
    sha->s[4] = 0x95f4e232ul;
    sha->s[5] = 0x94fd54f4ul;
    sha->s[6] = 0xa2ae8d85ul;
    sha->s[7] = 0x47ca590bul;

This is a very rough implementation, but something like this maybe?

https://github.com/bitcoin-core/secp256k1/compare/ea5e8a9...junderw:feature/secp256k1_schnorrsig_sign_with_taptweak_preimage

Yes. This is optimal if you are always in the C(/C++/Rust/WASM) space.

The major problem I have is that I am using this library through WASM, so data being managed by JS is not persisted in WASM between calls.

Hm, can you elaborate? How do you call into the secp library then? It's hard for me to imagine how you sign without keeping some state and moving it from keypair_create to schnorrsig_sign. (Or I tend to think that then it's not our responsibility to fix this).

For the other parts, I think we need to separate the discussion:

• Even if you ignore efficiency, it may still make sense to add a schnorrsig_sign_with_tweak for convenience reasons. I'm not too convinced though but I guess it wouldn't hurt.
• In general, our tweaking functions are very raw (and thus unsafe to use), i.e., they don't even do the hashing. Originally the goal of the library was to do only the EC stuff, and leave the hashing to the user. Now with Schnorr sigs, this has changed anyway. So I agree we should have better/safer tweaking functions, e.g., tweaking functions that tweak pubkeys and do the hashing just right, for example tweak(P, m) -> P+H(P,m) for some H (SHA256 or even taptweak-midstate). We could even have a BIP32 module. But all of this requires more thought and more work.

I think we've had a vague longer-term plan to include more higher-level functions, e.g. for BIP32 derivation, so I agree having BIP341-specific tweaking functions in the library wouldn't be out of place. That said, like @real-or-random, I don't really see what the issue is with having this logic in the calling code (for reference, this is the Bitcoin Core code that invokes it: https://github.com/bitcoin/bitcoin/blob/v22.0/src/key.cpp#L264L280).

Hm, can you elaborate?

I don't really see what the issue is with having this logic in the calling code

Sure thing. (collapsing because it's long and slightly off topic, explaining motivations)

<details><summary>Open long explanation by clicking here</summary> <p> Currently, we (a JS library) are using WASM for crypto operations by calling into this C library via FFI in Rust, then compiling that Rust into WASM.

Since WASM is a sandboxed environment, any reference to keypair must live within the WASM memory during the lifetime of the WASM call. (We wouldn't want to leave private key data persistent in WASM memory until JS calls some clean method for example, for obvious reasons.)

However, our taggedHash portion of the API lives within the JS portion.

So we have this awkward dance of "ok, we want to use WASM for its speed, and secp256k1 C library." but every time a taggedhash is required we need to do that in the JS space.

For the nonce function taggedHashes, luckily, the hash is done with this library, so we were spared an awkward dance... but then we noticed the "should use Q = P + int(hashTapTweak(bytes(P)))G" clause of BIP341 and the implicit requirement of using Q = P + int(hashTapTweak(bytes(P)))G in BIP86 (which our library basically revolves around HD keys.

So originally, I thought that script path spends would be a minority, so as long as key spends don't need to do the weird back and forth dance between taggedHash and the C code, it shouldn't matter much... but then I realized that the most common signing operation is not secp256k1_schnorrsign_sign but rather, the flow that I have represented in my rough implementation of secp256k1_schnorrsig_sign_with_taptweak_preimage (since all BIP32 keys that follow BIP86 will use it, and we highly discourage single-key usage, and even if single key, BIP341 says you "should" use the taptweak for key spend.

This could be solved by adding the taggedHash logic to the Rust code, and having it live within the WASM sandbox. That way I could create my own helper function that essentially does what my rough implementation of secp256k1_schnorrsig_sign_with_taptweak_preimage does while holding onto references.

But I think you and I are running into the same dilemma ("I don't want to mix concerns between taggedHash and crypto operations") while at the same time realizing that SchnorrSig is pretty tightly coupled with taggedHash, and it's already used in secp256k1_schnorrsign_sign.

</p> </details>

Even if you ignore efficiency, it may still make sense to add a schnorrsig_sign_with_tweak for convenience reasons. I'm not too convinced though but I guess it wouldn't hurt.

If each key spend "should" tweak itself with the taggedHash of its pubkey, and each script spend must tweak itself with its pubkey and the merkle root concatenated taggedHashed together, then this convenience function would get a lot of usage and benefit from the simplicity of use (and a little bit from the performance gains of hashing from the mid-state).

(The upside for WASM users is also a nice "two birds with one stone" perk.)

In general, our tweaking functions are very raw (and thus unsafe to use), i.e., they don't even do the hashing.

Considering all script path spends require use of tweaking, I would like to learn more about why they are unsafe to use? Is it just more foot-cannon prone? Or is there something inherently unsafe about these functions specifically? Would it be better to use the non-xonly versions after converting to even pubkeys and convert to xonly after the tweak?

So I agree we should have better/safer tweaking functions, e.g., ...

This is exactly what would be best in the long run imo. Including a helper function that utilizes that tweak function before signing would be a nice extra, since 99% of schnorrsign usage in the context of Bitcoin will be signing for the point P+H(P,m)G.

for reference, this is the Bitcoin Core code that invokes it: ...

I am curious if I'm reading this wrong, but does Bitcoin Core use P+H(P)G point for keyspend-only p2tr addresses / signing? Upon quick glance it looks like the absence of a merkle root will sign with just P.

@junderw Only key path spends are tweaked. For script paths you use the key directly. That's what the merkleroot==null case corresponds to in the Bitcoin Core. The merkleroot something else corresponds to a key path spend for cases where scripts do exist.

The issue with WASM state sounds to me like we just need a serialize/deserialize function for keypair (and other objects), so it can be persisted as bytes across calls.

@sipa I see the ComputeTapTweakHash call now... (coming from higher level languages, if (merkle_root) looks like it will not go into the if scope, but then I just saw merkle_root->IsNull() ? nullptr : merkle_root and remembered I'm reading C++ (lol))

The issue with WASM state sounds to me like we just need a serialize/deserialize function for keypair (and other objects), so it can be persisted as bytes across calls.

This could also be one solution, perhaps it's as simple as a 96 length byte array with d || P.x || P.y (32 bytes each)

(Though I still do believe the helper function would be useful, and would take a burden off the caller when signing for a tweaked key)

Considering all script path spends require use of tweaking, I would like to learn more about why they are unsafe to use? Is it just more foot-cannon prone

Right, that's what I meant. There's nothing inherently unsafe about tweaking.

The issue with WASM state sounds to me like we just need a serialize/deserialize function for keypair (and other objects), so it can be persisted as bytes across calls.

That would do it. Alternatively we could expose the SHA256 functions. But you could also have the SHA256 functions in Rust, see https://github.com/rust-bitcoin/rust-secp256k1/issues/339#issuecomment-969965352 .

@junderw I understand the keypair issue but you should really think about whether the midstate optimization is worth the hassle (on your side) We do it here in a few places because it's cheap to implement but the gains are rather tiny. In particular if you want this for singing: Signing is usually not a bottleneck. (Bitcoin can do around ~10 tx/s so usually you don't need to sign quicker than that. ;)) And latency: Ok that's a thing. But as I said, the gains are tiny.

Right, that's what I meant. (re: It being more foot-cannon prone)

I think this is all the more reason to include the tweak helper function for signing (sign_with_tweak). Because it requires one less call to the tweak function for the callers to potentially mess up during signing. And seeing as the "I want to sign for my tweaked seckey" is going to be a highly used paradigm in taproot, and it requires tweak calls (foot cannons) it would make sense to offer a sign method including it (tweak_add_check can be used to verify your pubkey is used in the tweaked output key... maybe for symmetric-sake adding a verify_with_tweak could just combine the tweak_add_check and verify schnorr as a convenience thing).

I think things are getting a little all over the place right now. I made a request, and every time I meet resistance I try to come up with another "angle" as to why the request has merit to everyone and not just my own needs.

I've sort of got myself lost in the weeds a bit here.

I might just implement the function in Rust using bitcoin_hashes, but then I'd have tagged hash code in the JS level, Rust level(WASM), and the C level(ffi through Rust)

Or maybe I'll just make a helper function in the Rust layer which just takes the final TapTweak hash itself so JS would do the TapTweak hash, pass it into WASM.

I will make a separate issue for keypair serialization though.

I think things are getting a little all over the place right now. I made a request, and every time I meet resistance I try to come up with another "angle" as to why the request has merit to everyone and not just my own needs.

I've sort of got myself lost in the weeds a bit here.

All good, I have the same feeling and these things are all very intertwined.

The reason I'm hesitating to like a schnorrsig_sign_with_tweak is that it either would be another "unsafe" tweak function (without hashing), or it would be a safe one but then I think this needs more thoughts because then we should provide the same safe basic tweaking functions (without simultaneous signing). I think we should really add safer tweak functions. I'll create an issue for this.

In case it helps anybody in the meantime, here is the code the BitBox02 currently uses to compute the tweaked keypair:

https://github.com/digitalbitbox/bitbox02-firmware/blob/2453fefc428cb67ea376349af145655c17f6f434/src/keystore.c#L803-L874