From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 7712CC0177 for ; Thu, 12 Mar 2020 17:04:57 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id 62F2F88307 for ; Thu, 12 Mar 2020 17:04:57 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from whitealder.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id p29FiWcUU7BP for ; Thu, 12 Mar 2020 17:04:55 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from mout-p-101.mailbox.org (mout-p-101.mailbox.org [80.241.56.151]) by whitealder.osuosl.org (Postfix) with ESMTPS id 1247A881D7 for ; Thu, 12 Mar 2020 17:04:54 +0000 (UTC) Received: from smtp1.mailbox.org (smtp1.mailbox.org [IPv6:2001:67c:2050:105:465:1:1:0]) (using TLSv1.2 with cipher ECDHE-RSA-CHACHA20-POLY1305 (256/256 bits)) (No client certificate requested) by mout-p-101.mailbox.org (Postfix) with ESMTPS id 48dZv81V16zKmQX; Thu, 12 Mar 2020 18:04:52 +0100 (CET) X-Virus-Scanned: amavisd-new at heinlein-support.de Received: from smtp1.mailbox.org ([80.241.60.240]) by spamfilter06.heinlein-hosting.de (spamfilter06.heinlein-hosting.de [80.241.56.125]) (amavisd-new, port 10030) with ESMTP id P1Ym3Wg08LxA; Thu, 12 Mar 2020 18:04:48 +0100 (CET) Message-ID: <3e5b438ce1487412d203387d6c0e8f53cfdb7449.camel@timruffing.de> From: Tim Ruffing To: Lloyd Fournier , Bitcoin Protocol Discussion Date: Thu, 12 Mar 2020 18:04:47 +0100 In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Mailman-Approved-At: Thu, 12 Mar 2020 17:06:06 +0000 Subject: Re: [bitcoin-dev] Hash function requirements for Taproot X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 12 Mar 2020 17:04:57 -0000 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