From: Tim Ruffing <crypto@timruffing•de>
To: Lloyd Fournier <lloyd.fourn@gmail•com>,
Bitcoin Protocol Discussion
<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Hash function requirements for Taproot
Date: Thu, 12 Mar 2020 18:04:47 +0100 [thread overview]
Message-ID: <3e5b438ce1487412d203387d6c0e8f53cfdb7449.camel@timruffing.de> (raw)
In-Reply-To: <CAH5Bsr2m3+kN67h0Dd+60-i3WCnCRXr_ywzub5_OV=UxxzN3hQ@mail.gmail.com>
Hi Lloyd,
This is great research, thanks for this effort!
Here are some comments:
On Wed, 2020-03-04 at 18:10 +1100, Lloyd Fournier via bitcoin-dev
wrote:
>
> Property (2) is more difficult to argue as it depends on the multi-
> party key generation protocol. Case in point: Taproot is completely
> broken when combined with a proof of knowledge key generation
> protocol where along with their public keys each party provides a
> proof of knowledge of the secret key. Where X_1 is the key of the
> honest party, the malicious party can choose their key X_2 to be
> G*H(X_1 || m) where m is a malicious Merkle root. Clearly the
> malicious party has a covert Taproot for X = X_1 + X_2 and can
> produce a proof of knowledge for X_2.
I mean, the good thing is that there's a general method to defend
against this, namely always adding a Merkle root on top. Maybe it's
useful to make the warning here a litte bit more drastic:
https://github.com/sipa/bips/blob/bip-taproot/bip-0341.mediawiki#cite_ref-22-0
Maybe we could actually mention this in BIP340, too, when we talk about
key generation,
>
> Poelstra presented a proof in the ROM for the security of Taproot
> [3]. It frames Taproot as a way of combining two signature schemes
> into one public key (in our case Schnorr and Tapscript). He uses a
> similar line of reasoning to what I have just presented in his proof
> (Lemma 1, step 3) but this approach brings in many other
> considerations that I think can be avoided by modelling it as a
> commitment scheme. Note that this proof only shows that Taproot
> forgeries are hard i.e. property (1).
I agree that modeling it as a commitment scheme is more natural. But I
think an optimal model would capture both worlds, and would give the
attacker signing oracles for the inner and the outer key, and an
commitment opening oracle That is, it would capture that
* the ability to obtain signatures for the inner key does not help you
to forge for the outer key
* the ability to obtain signatures for the outer key does not help you
to open the commitment, and --- if already opened --- do not help
you to forge for the inner key
* the ability to obtain an opening does not help you to forge for
either key...
* etc
I believe that all these properties hold, and I believe this even
without a formal proof.
Still, it would be great to have one. The problem here is really that
things get complex so quickly. For example, how do you model key
generation in the game(s) that I sketched above? The traditional way or
with MuSig. The reality is that we want to have everything combined:
* BIP32
* MuSig (and variants of it)
* Taproot (with scripts that refer to the inner key)
* sign-to-contract stuff (e.g., to prevent covert channels with
hardware wallets)
* scriptless scrips
* blind signatures
* threshold signtures
* whatever you can imagine on top of this
It's very cumbersome to come up with a formal model that includes all
of this. One common approach to protocols that are getting too complex
is to switch to simpler models, e.g., symbolic models/Dolev-Yao models
but that's hard here given that we don't have clear layering. Things
would be easier to analyze if Taproot was really just a commitment to
a verification key. But it's more, it's something that's both a
verification and a commitment. Taproot interferes with Schnorr
signatures on an algebraic level (not at all black-box), and that's
actually the reason why it's so powerful and efficient. The same is
true for almost everything in the list above, and this puts Taproot
outside the scope of proof assistants for cryptographic protocols that
work on a symbolic level of abstraction. I really wonder how we can
handle this better. This would improve our understanding of the
interplay between various crypto components better, and make it easier
to judge future proposals on all levels, from consensus changes to new
multi-signature protocols, etc.
>
> In my opinion, the cost of Taproot is mostly borne by theoreticians.
> They can no longer treat a a public key ideally but have to consider
> the implications of it also being a commitment. For the user and
> Bitcoin as a whole it seems to offer an overwhelming benefit. In
> exchange for the complexity it adds to making security claims in the
> GGM (if using Taprscript and MuSig), it offers exciting new
> opportunities for non-interactivity and fungibility over what just
> what Schnorr would provide.
I agree with this overall statement. I'm confident in Taproot, and I
guess what say above really applies to the cost for theoreticians.
(Let's just make sure that we don't forget how theory is relevant to
security in practice.)
Tim
next prev parent reply other threads:[~2020-03-12 17:04 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-03-04 7:10 Lloyd Fournier
2020-03-04 23:29 ` ZmnSCPxj
2020-03-05 9:56 ` Lloyd Fournier
2020-03-12 17:04 ` Tim Ruffing [this message]
2020-03-16 7:31 ` Lloyd Fournier
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=3e5b438ce1487412d203387d6c0e8f53cfdb7449.camel@timruffing.de \
--to=crypto@timruffing$(echo .)de \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=lloyd.fourn@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox