Provide suggested provably unspendable taproot internal key

[casey]

I'm trying to construct a taproot transaction that provably disables the key-path by using a provably unspendable key for the internal key.

BIP-341 suggests using the following internal key if the taproot key-path spend should be provably unspendable:

If one or more of the spending conditions consist of just a single key (after aggregation), the most likely one should be made the internal key. If no such condition exists, it may be worthwhile adding one that consists of an aggregation of all keys participating in all scripts combined; effectively adding an "everyone agrees" branch. If that is inacceptable, pick as internal key a point with unknown discrete logarithm. One example of such a point is H = lift_x(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) which is constructed by taking the hash of the standard uncompressed encoding of the secp256k1 base point G as X coordinate. In order to avoid leaking the information that key path spending is not possible it is recommended to pick a fresh integer r in the range 0...n-1 uniformly at random and use H + rG as internal key. It is possible to prove that this internal key does not have a known discrete logarithm with respect to G by revealing r to a verifier who can then reconstruct how the internal key was created.

It would be nice to provide H, perhaps as bitcoin::util::taproot::PROVABLY_UNSPENDABLE_INTERNAL_KEY, or something of the like.

[sanket1729]

concept ACK. Not really sure how we should expose it

[casey]

Also, I'd be happen to open a PR for this, but I'll need a hint on how to construct H.

[Kixunil]

Damn, I was afraid UntweakedPublicKey not being a newtype will cause issues and now one just appeared. I would've liked this:

impl UntweakedPublicKey {
    pub fn provably_unspendable<V: Verification>(ctx: &Secp256k1<V>, blinding: Scalar) -> Self {
        Self(H.add_tweak(ctx, self.0).expect("crypto-unlikely someone can supply inverse of H preimage"))
    }
}

I guess we will need a free-standing function with essentially the same API.

[apoelstra]

This seems reason enough to just make it a newtype. There's not a ton of methods we'll need to re-expose.

concept ACK. Not really sure how we should expose it

Can we compute it as a constexpr?

If not we might want to expose the underlying point as a constant from rust-secp. I think we can just do it by hardcoding the internal representation and unit-testing that it's correct. (We should also do this for G now that I think about it and maybe some other common values.)

[Kixunil]

Can we compute it as a constexpr?

We cannot (and will most likely never be able to) call FFI functions from const. I actually started writing your exact solution before reading the last paragraph. :D While it is kinda hack I believe it's totally acceptable and has concept ACK from me.

[Velnbur]

After some research, and assuming that if this issues is still open, it's relevant. I guess that there is still no solution for it. I'm also looking for method like @Kixunil suggested.

What's the problem with adding it for XOnlyPublicKey?

[apoelstra]

The problem is that these types' internal representation is owned by endian-dependent C code which cannot be exported into Rust constants.

[Kixunil]

Yeah, I no longer think it's a good idea to try and make the internal representation const since that would completely disable dynamic linking. If function is undesirable for any reason we could just have some kind of lazy static.

[apoelstra]

I think we should just move the "internal representation", along with parsing and serializatin, into Rust code.

[Kixunil]

That'd be great but won't it harm performance when using the keys? Could upstream have some unchecked functions that make it faster?

[apoelstra]

No. Any actual key operation takes 10s of microseconds. There is a factor at least 1000, more like 10000, between that and the perf cost of converting from the Rust representation to the C one.

And if you're not doing any actual key operations then the Rust code will probably be faster because there's no FFI boundary to cross and because Rust has better compile-time guarantees about object representation.

I'm notsure what you mean about upstream having "unchecked functions". Upstream is written in C. Nothing is checked but it doesn't help performance because nothing the compiler still can't assume anything.

[Kixunil]

Alright, I just assumed that checking the correctness and computing the internal representation would require a bunch of field operations. But if it doesn't I'm in favor of such change.

I'm notsure what you mean about upstream having "unchecked functions".

IIUC the key parsing functions currently return error if the key is invalid, so they must have at least one branch that performs the checking. I was asking if it'd be feasible to have functions that don't bother with these checks. But given the speed difference it almost certainly doesn't matter.

[apoelstra]

Ah, understood. It does not have unchecked variants in this sense (funny that now you're using it to mean "without spending time on sanity checks" and I'm interpreting it as some sort of safety thing..).

But checking the validity of an uncompressed point is super fast: you deserialize the x and y points, which is nearly instant, then compute x^3 + 7 and x^2, which takes two field squarings, a mult and an addition, and check them for equality.

Checking the validity of a compressed point is very slow and takes multiple microseconds because it requires a square root computation. But as long as our internal representation is uncompressed, we don't need to care about that.

[Kixunil]

Alright, storing "compressed" keys as uncompressed sounds reasonable too. Not sure about x-only but that probably as well.