Return-Path: Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 30656C013E for ; Mon, 16 Mar 2020 07:32:13 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id 2874389911 for ; Mon, 16 Mar 2020 07:32:13 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id cGOceHdKG5kG for ; Mon, 16 Mar 2020 07:32:11 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-il1-f181.google.com (mail-il1-f181.google.com [209.85.166.181]) by hemlock.osuosl.org (Postfix) with ESMTPS id A195288AD8 for ; Mon, 16 Mar 2020 07:32:11 +0000 (UTC) Received: by mail-il1-f181.google.com with SMTP id p12so805449ilm.7 for ; Mon, 16 Mar 2020 00:32:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=wf09SMKjNIQOE68QPJWlo8DpNzL/FT83MHIvphRM6jU=; b=NxwkoBuylZ8RWYf3YPLP1JQGOk8FEnjbA8SdQyz9O2OxMjluO5fOVLE+o4qNajEe0j sZQCLW5sddi+14HY6NiI7h9YboOHvfpPUOW9pf4QNzok9L+4BoNn3dECaziMsMtIPleu sR8xbaLJaAcRk5hdF6S752BWJH1b6E6fUJF8FMUr3Xn2qbuxAEXHTzvIAudaw20RVKwF 8hLrB21/ul/C8yJjKslLBydnRU/+INNBFCsDul4/68ZOEFeYkmFXQJyhyXg4nS8tkhU/ brnVuWBTnLHl5oOnVL7BQWniwMDckyDJsyMKEm51q5J3/dTeyvuUfIyObSEfetHhpWiQ kmJw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=wf09SMKjNIQOE68QPJWlo8DpNzL/FT83MHIvphRM6jU=; b=cu/zGBMXSPIG+eyxMGxq6AY9iJuChNEMcek1FJBBbmpZWz6wsvBH7CCA3TNs0Lon/F fhCFaSwgz9ttEoVwzcsXIUfIYRhodLXRmXX++Xr3zirkNdhEGRwV8YHGMJqyp3mV1iMy dRCVeYkyBBrLBEL3CQKAP8Y43jfIhvoG0HhATET4vZvdBEbyIMzA2mtYhoFgXTlJ1ahU Gbj3NRBUeGUkCYTMTkSAgUympTliBcpkn4XD07at1scCCaTgQfnHQAERh8EUjhADkgjQ FpkecZ9SedVTMcB81hob6NIryiZ7jPrfcLV4iNMuw69nej79jYp/CCWzq1xTDQ/h0yjq 0oWA== X-Gm-Message-State: ANhLgQ0x2swCUcHwozmFYm38i2QSM9WvSGM0zRF9UTtUtYxKW7Pr5y5v LUDIUV9gtsMMXTja9bpc6bS3fSiYZh0MD7HVH7f4x2DfIyM= X-Google-Smtp-Source: ADFU+vvRA1ZMTiYRD/oM0kI8f+Ofq7e4QMWlhWRp03zryykXlsmokXySUxYPqR3Q/g6ObPojmtNClIqnQMKeMml16Ac= X-Received: by 2002:a92:c7a9:: with SMTP id f9mr12427982ilk.158.1584343930721; Mon, 16 Mar 2020 00:32:10 -0700 (PDT) MIME-Version: 1.0 References: <3e5b438ce1487412d203387d6c0e8f53cfdb7449.camel@timruffing.de> In-Reply-To: <3e5b438ce1487412d203387d6c0e8f53cfdb7449.camel@timruffing.de> From: Lloyd Fournier Date: Mon, 16 Mar 2020 18:31:44 +1100 Message-ID: To: Tim Ruffing Content-Type: multipart/alternative; boundary="00000000000031590405a0f3d18c" X-Mailman-Approved-At: Mon, 16 Mar 2020 08:50:19 +0000 Cc: Bitcoin Protocol Discussion 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: Mon, 16 Mar 2020 07:32:13 -0000 --00000000000031590405a0f3d18c Content-Type: text/plain; charset="UTF-8" On Fri, Mar 13, 2020 at 4:04 AM Tim Ruffing wrote: > > 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, I missed this note in the BIP. This trick means you get property 2 (covert taproot) for free if you prove property 3 (second covert taproot). This is a big improvement as property 2 was dependent on the particulars of the key generation scheme whereas property 3 is just based on Taproot being a secure commitment scheme. Nice! > 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. > I hope we can prove these things in a more modular way without creating a hybrid scheme with multiple oracles. My hope is that you can prove that any secure key generation method will be secure once Taproot is applied to it if it is a secure commitment scheme. This was difficult before I knew about the empty commitment trick! Although the Taprooted key and the internal key are algebraically related, the security requirements on the two primitives (the group and the hash function) are nicely separated. Intuitively, 1. being able to break the Taproot hash function (e.g. find pre-images) does not help you forge signatures on any external key; it can only help you forge fake commitment openings (for the sake of this point assume that Schnorr uses an unrelated hash function for the challenge). 2. being able solve discrete logarithms doesn't help you break Taproot; it just helps you forge signatures. I believe we can formally prove these two points and therefore dismiss the need for any signing or commitment opening oracles in any security notion of Taproot: 1. We can dismiss the idea of an adversary that uses a commitment opening oracle to forge a signature because the commitment opening is not even an input into the signing algorithm. Therefore it is information theoretically impossible to learn anything about forging a signature from a Taproot opening. 2. I think we can dismiss the idea of an adversary that uses a signing oracle to forge a fake Taproot opening. To see this note that the Taproot Forge reduction to RPP in my poster actually still holds if the adversary is given the secret key x (with a few other modifications). In the proof I kept it hidden just because that seemed more realistic. If we give the adversary the secret key we can dismiss the idea that a signing oracle will help them because they can just simulate it. Furthermore, if honest parties always require the empty commitment be applied to their key we can dismiss the idea of an adversary that forges just based on the binding of the commitment scheme even if they know the secret key and regardless of the key generation algorithm. This allows us to restrict our notion of Taproot's security to its interaction with the key generation protocol only. It should be sufficient to prove these three things: 1. The key generation scheme is secure. I don't believe we have a definition for this yet but I guess it would be something like "if the adversary can't output the secret key of the agg key then it is secure". 2. The Taproot transformation of any key generation scheme satisfying (1) also satisfies (1). 3. The external key produced by any transformed protocol is a secure commitment to the message (if one is desired, if not the empty commitment trick fixes this). This gives us a modular and composable security model for Taproot. We can just prove that MuSig, threshold keygen, and all the other things you mentioned satisfy (1) and then by implication the Taprooted version of it is also secure. Or something like that! LL --00000000000031590405a0f3d18c Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Fri, Mar 13, 2020 at 4:04 AM Tim Ruffing <crypto@timruffing.de> wrote:
>> I mean, the good thing is that there's a general method to defen= d
> 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-034= 1.mediawiki#cite_ref-22-0
> Maybe we could actually mention this = in BIP340, too, when we talk about
> key generation,

I missed = this note in the BIP. This trick means you get property 2 =C2=A0(covert tap= root) for free if you prove property 3 (second covert taproot). This is a b= ig improvement as property 2 was dependent on the particulars of the key ge= neration scheme whereas property 3 is just based on Taproot being a secure = commitment scheme. Nice!

> I agree that modeling it as a commitme= nt scheme is more natural. But I
> think an optimal model would captu= re 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
> =C2=A0* the ability to obtain signatures for= the inner key does not help you
> =C2=A0 =C2=A0to forge for the oute= r key
> =C2=A0* the ability to obtain signatures for the outer key do= es not help you
> =C2=A0 =C2=A0to open the commitment, and --- if alr= eady opened --- do not help
> =C2=A0 =C2=A0you to forge for the inner= key
> =C2=A0* the ability to obtain an opening does not help you to = forge for
> =C2=A0 =C2=A0either key...
> =C2=A0* etc
>> I believe that all these properties hold, and I believe this even> without a formal proof.
>
>
> Still, it would be g= reat to have one. The problem here is really that
> things get comple= x so quickly. For example, how do you model key
> generation in the g= ame(s) that I sketched above? The traditional way or
> with MuSig. Th= e reality is that we want to have everything combined:
> =C2=A0* BIP3= 2
> =C2=A0* MuSig (and variants of it)
> =C2=A0* Taproot (with = scripts that refer to the inner key)
> =C2=A0* sign-to-contract stuff= (e.g., to prevent covert channels with
> =C2=A0 =C2=A0hardware walle= ts)
> =C2=A0* scriptless scrips
> =C2=A0* blind signatures
&= gt; =C2=A0* threshold signtures
> =C2=A0* whatever you can imagine on= top of this
>
> It's very cumbersome to come up with a for= mal model that includes all
> of this. One common approach to protoco= ls 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 an= alyze if Taproot was really =C2=A0just a commitment to
> a verificati= on key. But it's more, it's something that's both a
> ver= ification and a commitment. Taproot interferes with Schnorr
> signatu= res on an algebraic level (not at all black-box), and that's
> ac= tually the reason why it's so powerful and efficient. The same is
&g= t; true for almost everything in the list above, and this puts Taproot
&= gt; outside the scope of proof assistants for cryptographic protocols that<= br>> 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 easie= r
> to judge future proposals on all levels, from consensus changes t= o new
> multi-signature protocols, etc.
>

I hope we can = prove these things in a more modular way without creating a hybrid scheme w= ith multiple oracles. My hope is that you can prove that any secure key gen= eration method will be secure once Taproot is applied to it if it is a secu= re commitment scheme. This was difficult before I knew about the empty comm= itment trick! Although the Taprooted key and the internal key are algebraic= ally related, the security requirements on the two primitives (the group an= d the hash function) are nicely separated. Intuitively,
1. being able t= o =C2=A0break the Taproot hash function (e.g. find pre-images) does not hel= p you forge signatures on any external key; it can only help you forge fake= commitment openings (for the sake of this point assume that Schnorr uses a= n unrelated hash function for the challenge).
2. being able solve discre= te logarithms doesn't help you break Taproot; it just helps you forge s= ignatures.

I believe we can formally prove these two points and ther= efore dismiss the need for any signing or commitment opening oracles in any= security notion of Taproot:

1. We can dismiss the idea of an advers= ary that uses a commitment opening oracle to forge a signature because the = commitment opening is not even an input into the signing algorithm. Therefo= re it is information theoretically impossible to learn anything about forgi= ng a signature from a Taproot opening.
2. I think we can dismiss the ide= a of an adversary that uses a signing oracle to forge a fake Taproot openin= g. To see this note that the Taproot Forge reduction to RPP in my poster ac= tually still holds if the adversary is given the secret key x (with a few o= ther modifications). In the proof I kept it hidden just because that seemed= more realistic. If we give the adversary the secret key we can dismiss the= idea that a signing oracle will help them because they can just simulate i= t. Furthermore, if honest parties always require the empty commitment be ap= plied to their key we can dismiss the idea of an adversary that forges just= based on the binding of the commitment scheme even if they know the secret= key and regardless of the key generation algorithm.

This allows us= to restrict our notion of Taproot's security to its interaction with t= he key generation protocol only. It should be sufficient to prove these thr= ee things:
1. The key generation scheme is secure. I don't believe w= e have a definition for this yet but I guess it would be something like &qu= ot;if the adversary can't output the secret key of the agg key then it = is secure".
2. The Taproot transformation of any key generation sch= eme satisfying (1) also satisfies (1).
3. The external key produced by a= ny transformed protocol is a secure commitment to the message (if one is de= sired, if not the empty commitment trick fixes this).

This gives us = a modular and composable security model for Taproot. We can just prove that= MuSig, threshold keygen, and all the other things you mentioned satisfy (1= ) and then by implication the Taprooted version of it is also secure. Or so= mething like that!

LL
--00000000000031590405a0f3d18c--