Hash function requirements for Taproot

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

Good morning LL,

Thank you very much for this work, it seems quite interesting.

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

I am uncertain what you mean here by "coin-tossing". From the comparison to MuSig, I imagine it is an interactive key generation protocol like this:

* Everybody generates fresh keypairs.
* Everybody sends the hash of their pubkey to everyone else.
* After receiving a hash of pubkey from everyone else, everybody sends their pubkey to everyone else.
* They add all their pubkeys to generate the aggregate key (and if using Taproot, use it as the internal key).

Is that correct?

In any case, the comparison to MuSig signing appears to imply interactive key generation. The advantage of MuSig is that it requires no interactivity for key generation of n-of-n (I am told it requires interactivity to generate k-of-n).

However, it can generally be pointed out that, before you put anything into an n-of-n, you would damn well sure want to have *some* assurance that you can get it out later. So in general you would need coordination and interaction anyway to arrange getting into an n-of-n in the first place.

On the other hand, it would be best to have at least some minimum of privacy by always interacting over Tor and having a Tor .onion address, which has absolutely horrid latency because human beings cry when peeling onions. So in general reducing the latency by reducing communication rounds is better in general. Counter to this, assuming you use an n-of-n in an offchain protocol of some sort, the number of communication rounds to generate the aggregate key may be dwarfed by the total number of communication rounds to create signatures to update the offchain protocol. Counter counter to this is that one plan for reducing communications rounds for creating signatures during offchain operation is to (haha) use a Taproot with an n-of-n internal key and a tapscript that has n `OP_CHECKSIG` operations, so that for normal operation you just toss individual signatures at each other but at termination of the offchain protocol you can do the heavy MuSig-style signing with the n-of-n aggregate key.

Regards, ZmnSCPxj

> I am uncertain what you mean here by "coin-tossing".
> From the comparison to MuSig, I imagine it is an interactive key

generation protocol like this:

> * Everybody generates fresh keypairs.
> * Everybody sends the hash of their pubkey to everyone else.
> * After receiving a hash of pubkey from everyone else, everybody sends

their pubkey to everyone else.

> * They add all their pubkeys to generate the aggregate key (and if using

Taproot, use it as the internal key).

> Is that correct?

Yes exactly. The reason it's called coin tossing is that the resulting key is guaranteed to be uniformly random (in the random oracle model at least), so it's like tossing a fair 2^256 sided coin. This is not true in MuSig for example, where the aggregate key is not guaranteed to be from a uniform distribution against a malicious party (but still secure as an aggregate key).

> However, it can generally be pointed out that, before you put anything

into an n-of-n, you would damn well sure want to have *some* assurance that you can get it out later. So in general you would need coordination and interaction anyway to arrange getting into an n-of-n in the first place.

Right. Taking your example of a lightning channel, when you set it up I don't *think* there is a way to use the non-interactivity of MuSig to remove any rounds of communication to get to the starting state where there is a channel funding on-chain and both parties have a tx that spends from it which returns their funds. Doing coin tossing for the aggregate key as well as the aggregate nonce shouldn't lead to any extra rounds of communication. The downside of coin tossing is that it requires honest parties to sample their keys non-deterministically (or at least have a counter to avoid using the same key twice).

> On the other hand, it would be best to have at least some minimum of

privacy by always interacting over Tor and having a Tor .onion address, which has absolutely horrid latency because human beings cry when peeling onions.

> So in general reducing the latency by reducing communication rounds is

better in general.

> Counter to this, assuming you use an n-of-n in an offchain protocol of

some sort, the number of communication rounds to generate the aggregate key may be dwarfed by the total number of communication rounds to create signatures to update the offchain protocol.

> Counter counter to this is that one plan for reducing communications

rounds for creating signatures during offchain operation is to (haha) use a Taproot with an n-of-n internal key and a tapscript that has n `OP_CHECKSIG` operations, so that for normal operation you just toss individual signatures at each other but at termination of the offchain protocol you can do the heavy MuSig-style signing with the n-of-n aggregate key.

Counter³ to this is that, in the case of lightning, the aggregate key for a PTLC does not need to be chosen at payment time. They channel members could simply use the "master" aggregate key they generated by coin tossing at the channel's inception and pseudorandomly randomise it every time they need a new joint key (so the keys do not look related to everyone else on the chain but you would effectively just be reusing the same public key).

Having said that if there is some advantage to using MuSig in some particular case I wouldn't hesitate to use it in combination with Taproot. I don't think the new assumption that I think you have to make wrt to the hash function really weighs up against most design considerations. In general, it is probably worth considering whether your protocol actually benefits from the non-interactivity MuSig gives in the key generation stage. If it doesn't due to the fact that it doesn't make signing anymore non-interactive, then coin tossing might be the answer.

LL

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

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