path: root/7d/ef1cdef026aaf2f70341df74618fb2359077e8

Return-Path: <lloyd.fourn@gmail.com>
Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id ABA65C013E
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  4 Mar 2020 07:10:34 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by hemlock.osuosl.org (Postfix) with ESMTP id 9A9CF87100
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  4 Mar 2020 07:10:34 +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 cJGoGQ5p5QBJ
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  4 Mar 2020 07:10:32 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-il1-f175.google.com (mail-il1-f175.google.com
 [209.85.166.175])
 by hemlock.osuosl.org (Postfix) with ESMTPS id 6169886F3F
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  4 Mar 2020 07:10:32 +0000 (UTC)
Received: by mail-il1-f175.google.com with SMTP id b17so947935iln.3
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 03 Mar 2020 23:10:32 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:from:date:message-id:subject:to;
 bh=Vqo2/CTVuV+qFS2NBfEixpsQy0eZJYWBi6hpP9d5rjM=;
 b=Zqf3KAXRvbiYdyYctsE2cXJsOKMQbWg2/nz/dEmu9NWtzOgTipPdFb3mB9oARIecZB
 DqtdBJGk1LIQAd1ESjQxwYQ7ivRIbTp+j6IqdluKBeEElYf1KmouscxtQlJm60TDlYVl
 yKJwsADFI6qe9/WYx8KqpMW6qJE5CyiKefDvTg5P7vrqSAjGdCEBX9EZgWUgAt/+X4s2
 t2wTF7gVqplHDm2sMyNtU9/pXxkwIBwdS28ebY/sCtN1Z20WVC/qY7cP1I2tO2DFUenn
 pBQ7NS7eWQVq7Y4srw6Htc6W9x4CLc+sBRtdCfm/k7pifEX4WO6RWhXHfECTLOzMWDeS
 LLLQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
 bh=Vqo2/CTVuV+qFS2NBfEixpsQy0eZJYWBi6hpP9d5rjM=;
 b=iy2hekzziNgxXf9Akj2PWfYBnV0vwv4sTL8hEixqe4YAVQ1NwCk418n32T5vN4FrGu
 NCtZs8D+GHediIEIjHru2GBYfEjW/YEgn9p+RPaFtDmux2rox3f200ZulzHkE9/SxM4/
 Dhlp1IntPaxyTkYQlHX/Tak7B4DoO74BEbsp8QJ/cm/vYmR6aR0tog3UFiE+0ssk+1QU
 lSPsd/PgcL1qCuhnJNXFtVeUOtZlO8WU/XvMpt0fcaJcpBdRR4Tzij23y+KmERvqt9wd
 gpumbcLTjuIw1IJkpvuYxnS/bBnM4mLQBBJM5uNu/A6IoKha8T1NBtFP4e1p2v9YQAik
 ulTw==
X-Gm-Message-State: ANhLgQ36DJ3QvEzSYYsFEmgryYu+vyWWU8+G/RPWiLVt9lnb5eS+ijFW
 jUC8BgnGdJRAb+w+kb/HpuXgxEGWbaU0ZwVfBKzvT/OT
X-Google-Smtp-Source: ADFU+vsMVS5n4TwgL6XK9qRoaLPJ6Bitshf1yIzfQIy3dtDC5Z5jITlMG1er5lUsjy2sN/xpaT9N07HT6l2N0TPzLEk=
X-Received: by 2002:a92:d28e:: with SMTP id p14mr1438880ilp.195.1583305830797; 
 Tue, 03 Mar 2020 23:10:30 -0800 (PST)
MIME-Version: 1.0
From: Lloyd Fournier <lloyd.fourn@gmail.com>
Date: Wed, 4 Mar 2020 18:10:04 +1100
Message-ID: <CAH5Bsr2m3+kN67h0Dd+60-i3WCnCRXr_ywzub5_OV=UxxzN3hQ@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000009d964005a0021d5f"
X-Mailman-Approved-At: Wed, 04 Mar 2020 08:09:43 +0000
Subject: [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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Wed, 04 Mar 2020 07:10:34 -0000

--0000000000009d964005a0021d5f
Content-Type: text/plain; charset="UTF-8"

Hi List,

I recently presented a poster at the Financial Cryptography conference
'2020 which you can find here:
https://github.com/LLFourn/taproot-ggm/blob/master/main.pdf.  It attempts
to show the security requirements for the tweak hash function in Taproot.
In this post I'll give a long description of it but first let me tl;dr:

Taproot requires no new assumptions of SHA256 over what are already made by
Schnorr signatures themselves with one exception: when using a
non-interactive key generation protocol to produce a Taproot internal key
(e.g MuSig). To prove security in this scenario we need a make an
additional assumption about SHA256: as well as being collision resistant
(i.e. find two hashes h_1 - h_2 = 0), it must satisfy a more general kind
of collision resistance where it is hard to find h_1 - h_2 = d for *any d*
when the adversary is challenged to find h_1 and h_2 with random prefixes.
This is obviously a plausible assumption. Put informally, it says that zero
is not a special case where finding collisions is difficult but rather
solving the 2-sum problem is hard for all values of d (when challenged with
random prefixes).

Now the long version.

My motivation for creating this poster came from questions I had after
discussions in Taproot Study Group #18 (this study group initiative was a
great idea btw). The main question I had was "Why is Taproot binding?" i.e.
why is it true that I can only commit to one Merkle root. Isn't it possible
that a malicious party could produce a second covert Taproot spend that
none of the other parties to the output agreed to? I submitted a poster
proposal to FC to force myself to get to the bottom of it.

The premise of the poster is to use the Generic Group Model to try and
figure out how the hash function would have to fail for Taproot to be
insecure. Most of the poster is taken up cartoon reductions I made to
remind myself as to why what I was saying might be true. They are
incomplete and difficult to parse on their own so hopefully this post is a
useful companion to them.

=== The Security of Taproot ===

There are three scenarios/games we must consider when asking whether
Taproot is secure in the context of Bitcoin:

1. Taproot Forge: Forging taproot spends must be hard. The adversary must
not be able to take a public key off the blockchain and produce a forged
Taproot spend from it.
2. Covert Taproot: When an adversary is executing a multi-party key
generation protocol (e.g. MuSig) it should be hard for them to produce a
covert malicious Taproot spend from the joint key  i.e. when honest parties
think there is no Taproot on a key there shouldn't be any Taproot on the
key. Note this is not guaranteed to be hard by 1 being hard.
3. Second Covert Taproot: Like 2, except that if honest parties agree to a
Taproot spend then the adversary shouldn't be able to generate a second
Taproot spend they are unaware of.

Properties (1) and (2) can be argued succinctly if we just prove that
Taproot is a secure commitment scheme. It should be clear that if a Taproot
external key T = X + H(X||m)*G is a secure commitment scheme (Hiding and
Binding) to any arbitrary message m, then it is a secure commitment scheme
to a Merkle root. If so, then properties (1) and (3) hold. (1) holds
because if you can create an opening to a commitment not generated by you,
you either broke hiding (if your opening is the same as the honest one) or
broke binding (if it's different). (3) holds because you must have broken
binding as there are now two openings to the same commitment.

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.

Given this definition of security, we now move onto how we should model the
problem to prove they hold.

=== Generic Group Model vs Random Oracle Model ===

For practical cryptographic schemes you often have to idealise one of its
components to prove it secure. The most popular candidate for idealisation
is the hash function in the Random Oracle Model (ROM), which idealises a
hash function as a "random oracle", a black box which spits out random
values for each input. For example, the original "forking lemma" proof by
Pointcheval and Stern [1] shows the Schnorr signature scheme is unforgeable
in this model if the discrete logarithm problem is hard. In other words,
idealising the hash function allows us to isolate what security assumptions
we are making about the group (e.g. the discrete logarithm problem being
hard in it).

But what if we want to know what assumptions we are making about the hash
function? Does the challenge hash in Schnorr signatures have to be
collision resistant or pre-image resistant or something else? To answer
this question Neven et al.[2] analysed Schnorr signatures by idealising the
group in the "Generic Group Model" (GGM). By idealising the group, they
were able to isolate the security requirements of the hash function away
from any assumptions being made about the group. In the GGM, the group
becomes a black box which, when given two group elements, spits out their
subtraction (for technical reasons it's subtraction rather than addition).
The adversary can only produce new group elements by querying the oracle.
Using the GGM they prove that the hash function needs to be Random-Prefix
Preimage (RPP) resistant (and Random-Prefix Second-Preimage resistant)
which are strictly weaker assumptions than collision resistance.

=== Taproot in the Random Oracle Model ===

Proving that Taproot is a binding commitment scheme in the ROM is
straightforward (hiding is too but I'm going to skip that). To produce two
openings for the same external key, the adversary must have two random
oracle queries H(X || m) that result in the same external key T = X +
H(X||m)*G. Since H(X||m)*G is an (almost) uniformly distributed group
element in the ROM, T is also uniformly distributed, thus breaking the
binding of Taproot is equivalent to solving a birthday problem of size
2^256 (the same as finding hash collisions in the ROM). Note that this
statement is true regardless of the discrete logarithm problem being hard
or not. This proves properties (1) and (3).

For property (2) let's consider MuSig as the key generation protocol. If we
model the MuSig key tweak hash function as a random oracle as well then for
every key X_2,  the adversary has to query the MuSig hash oracle to
determine the joint key X = X_1*H(X_1||L) + X_2*H(X_2| L). As before, it is
clear to see that this makes X a uniform group element for every X_2 in the
ROM. Liekwise for every covert Taproot internal key C and message pair the
external key T = C + H(C||m) *G will be uniform as before in the ROM. Thus,
breaking property (2) is the same as finding T = X, where you the adversary
can only sample T and X from uniform distributions and so we have another
birthday problem. This completes the proof of all three properties.

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).

=== Taproot in the Generic Group Model ===

The ROM proof is an important first step -- if it couldn't be proved secure
in ROM then it would probably be completely broken. But Taproot, unlike
Schnorr, only relies on the security of its hash function when viewed as a
commitment scheme so it would be prudent to figure out what those
properties are. By using the ROM we artificially hide what those properties
from our analysis. As in the case of Schnorr, we can idealise the group in
the GGM to help isolate the hash function's properties.

To prove Taproot was a binding commitment scheme in the GGM I had to
introduce a new property I called "Chosen Offset Prefix-Collision" (COPC)
resistance. The precise security game is sketched in the poster, but I like
to describe it as a more general kind of collision resistance. Instead of
it being hard to find two preimages a and b where H(a) - H(b) = 0, it must
be hard to find H(P_1 || a) - H(P_2 || b) = d for any d (not just d  = 0)
with random prefixes P_1 and P_2 given by the challenger (d chosen by the
adversary). COPC is necessary and sufficient to prove Taproot is a secure
commitment scheme in the GGM (the proof for this isn't in the poster but is
very similar to Second Covert Taproot proof).

This was not the ideal outcome, so I decided to analyse properties Taproot
(1) and (3) independently rather than just imply them from the commitment
scheme result. What ended up in the poster is three independent proofs for
each Taproot security property with MuSig assumed to be key generation
scheme for properties (2) and (3). Here's a summary of what I concluded for
each property.

1. Taproot Forge: In the GGM, an adversary who forges Taproot openings can
be used as a black box to mount a "Random Prefix-Preimage" (RPP) attack
against the hash function. This is a very good result as RPP is already
required by Schnorr. Essentially, this means anyone who can forge Taproot
spends can also forge Schnorr signatures.

2. Covert Taproot (MuSig): For this problem I had to split the adversary
into two types: those who query their MuSig public key X_2 from the group
oracle before their malicious internal key C and those that query C first
or set X_2 = C. For the first case I was able to show another reduction
from RRP (which shown in the poster).  The other case I was able to break
preimage resistance as long as I modelled the MuSig hash function as a
random oracle (not shown in the poster and this is only from memory). In
both cases the reduction does not work for n-party MuSig (only for 2
parties). Obviously, this is not totally satisfying. The problem with
n-party MuSig is it becomes exponentially more unlikely (in n) for the
reduction to guess which keys the adversary will use for their MuSig keys.

3. Second Covert Taproot (MuSig): Once again, this is where honest parties
agree on a joint key and Taproot spend from it, but the adversary is
somehow able to create a second covert spend during the key generation
phase. This is where I found that COPC does actually need to be hard to
ensure this property. This is true regardless of the number of parties.
Thus this is the only scenario where you need the additional security
assumption to prove security.

== Concluding Remarks ==

The main important take away of this is that there is actually a small
security cost to using a group element as both a commitment scheme and as a
public key. It would be very surprising if we got this for free. By using
the random oracle model we merely hide this in the idealisation of the hash
function. The generic group model exposes it. The question is: is the cost
worth it and who bears it? Here's what I consider to be the most important
points:

1. You only take on this COPC assumption if you use Tapscript. If you're
just putting your funds into a Taproot output without an internal key,
either as a group or an individual there is no extra security assumption.
(with the caveat that my technique only really works for  2-party MuSig).
2. The COPC assumption seems to be very plausible.
3. Even if COPC is broken and an adversary can output two openings to the
same external key, both those openings must be valid taproot spends for
anyone to lose coins (i.e. Merkle roots with valid paths to leaves with
valid tapscript).
4. Even if COPC was that badly broken on SHA256, old taproot outputs would
not be affected, the adversary has to break it during key generation before
funds are put into the output.
5. You can completely circumvent this result by using coin-tossing rather
than MuSig for the key generation protocol. In most cases this doesn't even
add any extra rounds of communication since you are doing 3-round coin
tossing to choose the R values for the signatures that spend from the joint
output anyway. You can just toss your public keys in parallel.

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 don't consider my work to be a final proof of anything. I would welcome
anyone who wants to take over this research direction and do a proper job
of it! I didn't have any personal motivation for doing this work other than
curiosity and that curiosity has been satisfied. Questions and thoughts
welcome :)

[1] https://www.di.ens.fr/david.pointcheval/Documents/Papers/2000_joc.pdf
[2] http://www.neven.org/papers/schnorr.pdf
[3] https://github.com/apoelstra/taproot/blob/master/main.pdf

Cheers,

LL

--0000000000009d964005a0021d5f
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div><div dir=3D"ltr">Hi List,<div><div><br></div><div>I r=
ecently presented a poster at the Financial Cryptography conference &#39;20=
20 which you can find here:=C2=A0<a href=3D"https://github.com/LLFourn/tapr=
oot-ggm/blob/master/main.pdf" target=3D"_blank">https://github.com/LLFourn/=
taproot-ggm/blob/master/main.pdf</a>.=C2=A0 It attempts to show the securit=
y requirements for the tweak hash function in Taproot. In this post I&#39;l=
l give a long description of it but first let me tl;dr:</div><div><br></div=
><div>Taproot requires no new assumptions of SHA256 over what are already m=
ade by Schnorr signatures themselves with one exception: when using a non-i=
nteractive key generation=C2=A0protocol to produce a Taproot internal key (=
e.g MuSig). To prove security in this scenario we need a make an additional=
 assumption about SHA256: as well as being collision resistant (i.e. find t=
wo hashes h_1 - h_2 =3D 0), it must satisfy a more general kind of collisio=
n resistance where it is hard to find h_1 - h_2 =3D d for *any d* when the =
adversary is challenged to find h_1 and h_2 with random prefixes. This is o=
bviously a plausible assumption. Put informally, it says that zero is not a=
 special case where finding collisions is difficult but rather solving the =
2-sum problem is hard for all values of d (when challenged with random pref=
ixes).</div><div><br></div><div>Now the long version.</div><div><br></div><=
div>My motivation for creating this poster came from questions I had after =
discussions in Taproot Study Group #18 (this study group initiative was a g=
reat idea btw). The main question I had was &quot;Why is Taproot binding?&q=
uot; i.e. why is it true that I can only commit to one Merkle root. Isn&#39=
;t it possible that a malicious party could produce a second covert Taproot=
 spend that none of the other parties to the output agreed to? I submitted =
a poster proposal to FC to force myself to get to the bottom of it.=C2=A0</=
div><div><br></div><div><div>The premise of the poster is to use the Generi=
c Group Model to try and figure out how the hash function would have to fai=
l for Taproot to be insecure. Most of the poster is taken up cartoon reduct=
ions I made to remind myself as to why what I was saying might be true. The=
y are incomplete and difficult to parse on their own so hopefully this post=
 is a useful companion to them.</div></div><div><br></div><div>=3D=3D=3D Th=
e Security of Taproot =3D=3D=3D</div><div><br></div><div>There are three sc=
enarios/games we must consider when asking whether Taproot is secure in the=
 context of Bitcoin:</div><div><br></div><div>1. Taproot Forge: Forging tap=
root spends must be hard. The adversary must not be able to take a public k=
ey off the blockchain and produce a forged Taproot spend from it.</div><div=
>2. Covert Taproot: When an adversary is executing a multi-party key genera=
tion protocol (e.g. MuSig) it should be hard for them to produce a covert m=
alicious Taproot spend from the joint key=C2=A0 i.e. when honest parties th=
ink there is no Taproot on a key there shouldn&#39;t be any Taproot on the =
key. Note this is not guaranteed to be hard by 1 being hard.</div><div>3. S=
econd Covert Taproot: Like 2, except that if honest parties agree to a Tapr=
oot spend then the adversary shouldn&#39;t be able to generate a second Tap=
root spend they are unaware of.</div><div><br></div><div>Properties (1) and=
 (2) can be argued succinctly if we just prove that Taproot is a secure com=
mitment scheme. It should be clear that if a Taproot external key T =3D X +=
 H(X||m)*G is a secure commitment scheme (Hiding and Binding) to any arbitr=
ary message m, then it is a secure commitment scheme to a Merkle root. If s=
o, then properties (1) and (3) hold. (1) holds because if you can create an=
 opening to a commitment not generated by you, you either broke hiding (if =
your opening is the same as the honest one) or broke binding (if it&#39;s d=
ifferent). (3) holds because you must have broken binding as there are now =
two openings to the same commitment.</div><div><br></div><div>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 ke=
ys 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 malicio=
us party has a covert Taproot for X =3D X_1=C2=A0+ X_2 and can produce a pr=
oof of knowledge for X_2.</div><div><br></div><div>Given this definition of=
 security, we now move onto how we should model the problem to prove they h=
old.</div><div><br></div><div>=3D=3D=3D Generic Group Model vs Random Oracl=
e Model =3D=3D=3D</div><div><br></div><div>For practical cryptographic sche=
mes you often have to idealise one of its components to prove it secure. Th=
e most popular candidate for idealisation is the hash function in the Rando=
m Oracle Model (ROM), which idealises a hash function=C2=A0as a &quot;rando=
m oracle&quot;, a black box which spits out random values for each input. F=
or example, the original &quot;forking lemma&quot; proof by Pointcheval and=
 Stern [1] shows the Schnorr signature scheme is unforgeable in this model =
if the discrete logarithm problem is hard. In other words, idealising the h=
ash function allows us to isolate what security assumptions we are making a=
bout the group (e.g. the discrete logarithm problem being hard in it).</div=
><div><br></div><div>But what if we want to know what assumptions we are ma=
king about the hash function? Does the challenge hash in Schnorr signatures=
 have to be collision resistant or pre-image resistant or something else? T=
o answer this question Neven et al.[2] analysed Schnorr signatures by ideal=
ising the group in the &quot;Generic Group Model&quot; (GGM). By idealising=
 the group, they were able to isolate the security requirements of the hash=
 function away from any assumptions being made about the group. In the GGM,=
 the group becomes a black box which, when given two group elements, spits =
out their subtraction (for technical reasons it&#39;s subtraction rather th=
an addition). The adversary can only produce new group elements by querying=
 the oracle. Using the GGM they prove that the hash function needs to be Ra=
ndom-Prefix Preimage (RPP) resistant (and Random-Prefix Second-Preimage res=
istant) which are strictly weaker assumptions than collision resistance.</d=
iv><div><br></div><div>=3D=3D=3D Taproot in the Random Oracle Model =3D=3D=
=3D</div><div><br></div><div>Proving that Taproot is a binding commitment s=
cheme in the ROM is straightforward (hiding is too but I&#39;m going to ski=
p that). To produce two openings for the same external key, the adversary m=
ust have two random oracle queries H(X || m) that result in the same extern=
al key T =3D X + H(X||m)*G. Since H(X||m)*G is an (almost) uniformly distri=
buted group element in the ROM, T is also uniformly distributed, thus break=
ing the binding of Taproot is equivalent to solving a birthday problem of s=
ize 2^256 (the same as finding hash collisions in the ROM). Note that this =
statement is true regardless of the discrete logarithm problem being hard o=
r not. This proves properties (1) and (3).</div><div><br></div><div>For pro=
perty (2) let&#39;s consider MuSig as the key generation protocol. If we mo=
del the MuSig key tweak hash function as a random oracle as well then for e=
very key X_2,=C2=A0 the adversary has to query the MuSig hash oracle to det=
ermine the joint key X =3D X_1*H(X_1||L)=C2=A0+ X_2*H(X_2| L). As before, i=
t is clear to see that this makes X a uniform group element for every X_2 i=
n the ROM. Liekwise for every covert Taproot internal key C and message pai=
r the external key T =3D C=C2=A0+ H(C||m) *G=C2=A0will be uniform as before=
 in the ROM. Thus, breaking property (2) is the same as finding T =3D X, wh=
ere you the adversary can only sample T and X from uniform distributions an=
d so we have another birthday problem. This completes the proof of all thre=
e properties.</div><div><br></div><div>Poelstra presented a proof in the RO=
M 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 Tapscrip=
t). He uses a similar line of reasoning to what I have just presented in hi=
s proof (Lemma 1, step 3) but this approach brings in many other considerat=
ions that I think can be avoided by modelling it as a commitment scheme. No=
te that this proof only shows that Taproot forgeries are hard i.e. property=
 (1).</div><div><br></div><div>=3D=3D=3D Taproot in the Generic Group Model=
 =3D=3D=3D</div><div><br></div><div>The ROM proof is an important first ste=
p -- if it couldn&#39;t be proved secure in ROM then it would probably be c=
ompletely broken. But Taproot, unlike Schnorr, only relies on the security =
of its hash function when viewed as a commitment scheme so it would be prud=
ent to figure out what those properties are. By using the ROM we artificial=
ly hide what those properties from our analysis. As in the case of Schnorr,=
 we can idealise the group in the GGM to help isolate the hash function&#39=
;s properties.</div><div><br></div><div>To prove Taproot was a binding comm=
itment scheme in the GGM I had to introduce a new property I called &quot;C=
hosen Offset Prefix-Collision&quot; (COPC) resistance. The precise security=
 game is sketched in the poster, but I like to describe it as a more genera=
l kind of collision resistance. Instead of it being hard to find two preima=
ges a and b where H(a) - H(b) =3D 0, it must be hard to find H(P_1 || a) - =
H(P_2 || b) =3D d for any d (not just d=C2=A0 =3D 0) with random prefixes P=
_1 and P_2 given by the challenger (d chosen by the adversary). COPC is nec=
essary and sufficient to prove Taproot is a secure commitment scheme in the=
 GGM (the proof for this isn&#39;t in the poster but is very similar to Sec=
ond Covert Taproot proof).</div><div><br></div><div>This was not the ideal =
outcome, so I decided to analyse properties Taproot (1) and (3) independent=
ly rather than just imply them from the commitment scheme result. What ende=
d up in the poster is three independent proofs for each Taproot security pr=
operty with MuSig assumed to be key generation scheme for properties (2) an=
d (3). Here&#39;s a summary of what I concluded for each property.</div><di=
v><br></div><div>1. Taproot Forge: In the GGM, an adversary who forges Tapr=
oot openings can be used as a black box to mount a &quot;Random Prefix-Prei=
mage&quot; (RPP) attack against the hash function.=C2=A0This is a very good=
 result as RPP is already required by Schnorr. Essentially, this means anyo=
ne who can forge Taproot spends can also forge Schnorr signatures.</div><di=
v><br></div><div>2. Covert Taproot (MuSig): For this problem I had to split=
 the adversary into two types: those who query their MuSig public key X_2 f=
rom the group oracle before their malicious internal key C and those that q=
uery C first or set X_2 =3D C. For the first case I was able to show anothe=
r reduction from RRP (which shown in the poster).=C2=A0 The other case I wa=
s able to break preimage resistance as long as I modelled the MuSig hash fu=
nction as a random oracle (not shown in the poster and this is only from me=
mory). In both cases the reduction does not work for n-party MuSig (only fo=
r 2 parties). Obviously, this is not totally satisfying. The problem with n=
-party MuSig is it becomes exponentially more unlikely (in n) for the reduc=
tion to guess which keys the adversary will use for their MuSig keys.</div>=
<div><br></div><div>3. Second Covert Taproot (MuSig): Once again, this is w=
here honest parties agree on a joint key and Taproot spend from it, but the=
 adversary is somehow able to create a second covert spend during the key g=
eneration phase. This is where I found that COPC does actually need to be h=
ard to ensure this property. This is true regardless of the number of parti=
es. Thus this is the only scenario where you need the additional security a=
ssumption to prove security. </div><div><br></div><div>=3D=3D Concluding Re=
marks =3D=3D</div><div><br></div><div>The main important take away of this =
is that there is actually a small security cost to using a group element as=
 both a commitment scheme and as a public key. It would be very surprising =
if we got this for free. By using the random oracle model we merely hide th=
is in the idealisation of the hash function. The generic group model expose=
s it. The question is: is the cost worth it and who bears it? Here&#39;s wh=
at I consider to be the most important points:</div><div><br></div><div>1. =
You only take on this COPC assumption if you use Tapscript. If you&#39;re j=
ust putting your funds into a Taproot output without an internal key, eithe=
r as a group or an individual there is no extra security assumption. (with =
the caveat that my technique only really works for=C2=A0 2-party MuSig).</d=
iv><div>2. The COPC assumption seems to be very plausible.</div><div>3. Eve=
n if COPC is broken and an adversary can output two openings to the same ex=
ternal key, both those openings must be valid taproot spends for anyone to =
lose coins (i.e. Merkle roots with valid paths to leaves with valid tapscri=
pt).</div><div>4. Even if COPC was that badly broken on SHA256, old taproot=
 outputs would not be affected, the adversary has to break it during key ge=
neration before funds are put into the output.</div><div>5. You can complet=
ely circumvent this result by using coin-tossing rather than MuSig for the =
key generation protocol. In most cases this doesn&#39;t even add any extra =
rounds of communication since you are doing 3-round coin tossing to choose =
the R values for the signatures that spend from the joint output anyway. Yo=
u can just toss your public keys in parallel.</div><div><br></div><div>In m=
y opinion, the cost of Taproot is mostly borne by theoreticians. They can n=
o 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 seem=
s 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 of=
fers exciting new opportunities for non-interactivity and fungibility over =
what just what Schnorr would provide.</div><div><br></div><div>I don&#39;t =
consider my work to be a final proof of anything. I would welcome anyone wh=
o wants to take over this research direction and do a proper job of it! I d=
idn&#39;t have any personal motivation for doing this work other than curio=
sity and that curiosity has been satisfied. Questions and thoughts welcome =
:)</div><div><br></div><div>[1]=C2=A0<a href=3D"https://www.di.ens.fr/david=
.pointcheval/Documents/Papers/2000_joc.pdf" target=3D"_blank">https://www.d=
i.ens.fr/david.pointcheval/Documents/Papers/2000_joc.pdf</a></div><div>[2]=
=C2=A0<a href=3D"http://www.neven.org/papers/schnorr.pdf" target=3D"_blank"=
>http://www.neven.org/papers/schnorr.pdf</a></div><div>[3]=C2=A0<a href=3D"=
https://github.com/apoelstra/taproot/blob/master/main.pdf" target=3D"_blank=
">https://github.com/apoelstra/taproot/blob/master/main.pdf</a></div><div><=
br></div><div>Cheers,</div><div><br></div><div>LL</div><div><br></div></div=
></div>
</div>
</div>

--0000000000009d964005a0021d5f--