Subject: Re: [bitcoin-dev] Taproot proposal

From: ZmnSCPxj <[email-masked]>
Date: Sat, 18 May 2019 17:51:16 +0000

Good morning list,

> > Can this "unknown discrete logarithm" be made provably unknown, so all signers are assured of this property? Bonus points if the outside world can't tell. The exact mechanism could be outside the scope of the BIP, but knowing that it's possible is useful.
>
> Yes, that's a TODO that's left in the draft, but this is absolutely
> possible (using a hash-to-curve operation). As ZmnSCPxj already
> suggested, there can even be a fixed known constant you can use for
> this. However, you get better privacy by taking this fixed known
> constant (call it C) and using as internal key a blinded version of it
> (C+rG, for some random value r, and G the normal secp256k1 generator);
> as long as the DL between G and C is unknown, this is safe (and does
> not reveal to the world that in fact no key-path was permitted when
> spending).

Gregory Maxwell commented some days ago:

> 2019-05-11T23:35:02  <gmaxwell> sipa: also someone might want to point out to ZmnSCPxj  that his scheme for getting a NUMS point is insecure (it must also commit to G because we don't know how G was generated)

I am assuming that gmax is referring to my description of the "hash-to-point" or "hash-to-curve" operation.

A little more research shows this: https://crypto.stackexchange.com/a/25603

>From the above, it seems the method that real cryptographers use is:

1.  Generate some random data d.
2.  Get x = h(G | d) where G is the existing generator for secp256k1.
3.  Find a point on secp256k1 with X coordinate x.
4.  If not found, go to 1.

In any case, I am almost sure that for every case where the "everyone agrees" path is unwanted in a taproot address, the simple "put your own pubkey lock on the door and throw away the privkey" technique would work without requiring a NUMS point: the same taproot assumption should also work here.
But generation of a NUMS point might be of independent interest in any case (e.g. setting up Pedersen commitments).

Regards,
ZmnSCPxj