Return-Path: Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id D8DDBC077D for ; Thu, 5 Dec 2019 20:25:00 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id C7B398752A for ; Thu, 5 Dec 2019 20:25:00 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from fraxinus.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ZFZiBt4wRz04 for ; Thu, 5 Dec 2019 20:24:59 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from mail-il1-f177.google.com (mail-il1-f177.google.com [209.85.166.177]) by fraxinus.osuosl.org (Postfix) with ESMTPS id 5552687484 for ; Thu, 5 Dec 2019 20:24:59 +0000 (UTC) Received: by mail-il1-f177.google.com with SMTP id z90so4168304ilc.8 for ; Thu, 05 Dec 2019 12:24:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blockstream.io; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=7zjV94FNE3bZzkx6T1Vlz+Zjm4gGntNP2bNd8XT/loM=; b=YBUXmfsfzhmQo27kS89BzQ3emFbHxceQ2+wkUXafqHmdqvSwB3V1GaTR++pyCj0T14 cJqsXjiCIOK1pw8px+CtTfEVCGq6IRjh9gnlzqFZuBavz7SnhwjRnHsOkGOjd3L4nh1d 1szdvrHhMNcmCv5cYV5OYhsJDtctT7qBje+vg= 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=7zjV94FNE3bZzkx6T1Vlz+Zjm4gGntNP2bNd8XT/loM=; b=j2JmEnIKTaPKVwCLcqHn/GBjvZcBdIQaaBAddKPd1GxuUqZQnjebKDle7TjLDNGsus +RTcP9fpVLubTmHaSJ1aosEb1dgIcacVbPpV1SMez0AKuTZngB2JyEOkcjm0Gq7ZyGvk Ruv56NJwxRlViChSPidy3AoSqJlC/ioj5C1hV093oBV1xgtm+A6BcFVRFaFaFKf2fjc0 AYorBm3ypW5P8oZvHLZb2OS4xHL6+OVhuWuwHv84STxDOlpgD2Iw4/UpS1tWa0qRIG3l lghbQD/nOabZcRSOWZczJHQN/vE/O7RvTK1RwY60+BVY2xEKSdhe8uJtP/iFXDQ2DMV7 MAvw== X-Gm-Message-State: APjAAAUavZ5eSl8Yl+HFww47Hl1p25CLKr107xWe0pvgEovdTzxT25VN PwINVLLMnfgqrhZw2pUbYPQQJPR3YT0IO2xoI96bl3Vrzgw= X-Google-Smtp-Source: APXvYqzobHJ2/0B8Zm3df6LUPOFb4BOCX2UirCIRqWnovZcqy8Nf/iQJqCQv2xmv/GK3pgiaSjSePZajtTMhmpQG334= X-Received: by 2002:a92:79d2:: with SMTP id u201mr11067292ilc.103.1575577498246; Thu, 05 Dec 2019 12:24:58 -0800 (PST) MIME-Version: 1.0 References: <20191128080659.msrpdpcjhhvbqtv2@erisian.com.au> <20191203083538.ggiginwo5k6m4ywq@erisian.com.au> In-Reply-To: <20191203083538.ggiginwo5k6m4ywq@erisian.com.au> From: "Russell O'Connor" Date: Thu, 5 Dec 2019 15:24:46 -0500 Message-ID: To: Anthony Towns Content-Type: multipart/alternative; boundary="0000000000001985bc0598fab940" Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Signing CHECKSIG position in Tapscript 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, 05 Dec 2019 20:25:00 -0000 --0000000000001985bc0598fab940 Content-Type: text/plain; charset="UTF-8" After chatting with andytoshi and others, and some more thinking I've been convinced that my specific concern about other users masquerading other people pubkeys as their own in complex scripts is actually a non-issue. No matter what you write in Script (today), you are limited to expressing some policy that is logically equivalent to a set of conditions and signatures on pubkeys that can be expressed in disjunctive normal form. We can write such a policy as (C[1] && PK[1,1] && ... && PK[1,m[1]]) || ... || (C[n] && PK[n,1] && ... && PK[n,m[n]]) where C[i] is some conjunction of conditions such as timelock constraints, or hash-lock constraints or any other kind of proof of publication, and where PK[i,j] is a requirement of a signature against a specific public key. From Alice's point of view, she can divide set of clauses under the disjunction into those that contain a pubkey that she considers (partially) under her control and those clauses that she does not control (even though as we shall see those other keys might actually be under Alice's control, unbeknownst to her). To that end, let us consider a specific representative policy. (C[1] && APK[1]) || (C[2] && APK[2] && BPK[2]) || (C[3] && BPK[3]) where Alice considers herself in control of APK[1] and APK[2], and where she considers Bob in control of BPK[2] and BPK[3] and where C[1], C[2], and C[3] are different conditions, let's say three different hash-locks. We will also say that Alice has ensured that her pubkeys in different clauses are different (i.e. APK[1] != APK[2]), but she doesn't make any such assumption for Bob's keys and neither will we. When Alice funded this Script, or otherwise accepted it for consideration, she agreed that she wouldn't control the redemption of the UTXO as long as the preimage for C[3] is published. In particular, Alice doesn't even need to fully decode the Script semantics for that clause beyond determining that it enforces the C[3] requirement that she cares about. Even if Bob was masquerading Alice's pubkey as his own (as in BPK[3] = APK[1] or BPK[3] = APK[2]), and he ends up copying her signature into that clause, Alice ends up with C[3] published as she originally accepted as a possibility. Bob masquerading Alice's pubkey as his own only serves to hamper his own ability to sign for his clauses (I mean, Bob might be trying to convince some third party that Alice signed for something she didn't actually sign for, but such misrepresentations of the meaning of digital signatures is outside our scope and this just serves as a reminder not to be deceived by Bob's tricks here). And the same argument holds for BPK[2]. Even if BPK[2] = APK[1] and Bob tries to copy Alice's signature into the C[2] condition, he still needs a countersignature with her APK[2], so Alice remains in control of that clause. And if BPK[2] = APK[2] then Bob can only copy Alice's signature on the C[2] condition, but in that case she has already authorised that condition. Again, Bob masquerading Alice's pubkey as his own only serves to hamper his own ability to sign for his clauses. So what makes our potential issue here safe, versus the dangers that would happen in where Bob masqurades Alice's UTXO as his own? The key problem in the UTXO case isn't so much Bob masquerading Alice's pubkey as his own, as it is an issue with Alice reusing her pubkeys and Bob taking advantage of that. We do, in fact, have exactly the same issue in Script. If Alice were to reuse pubkeys such that APK[1] = APK[2], then Bob could take her signature for C[1] and transplant it to redeem under condition C[2]. We see that it is imperative that Alice ensures that she doesn't reuse pubkeys that she considers under her control for different conditions when she wants her signature to distinguish between them. For various reasons, some historical, it is much harder to avoid pubkey reuse for different UTXOs than it is to avoid pubkey reuse within a single script. We often use Bitcoin addresses in non-interactive ways, such as putting them on flyers or painting them on walls and such. Without a standard for tweaking such pubkeys in a per-transaction way, we end up with a lot of pubkey reuse between various UTXOs. However, within a Script, avoiding pubkey reuse ought to be easier. Alice must communicate different pubkeys intended for different clauses, or if Bob is constructing a whole complex script on Alice's behalf, he may need to add CODESEPARATORs if tweaking Alice's pubkey isn't an option. The conversion of a policy to disjunctive normal form can involve an exponential blowup (see < https://en.wikipedia.org/wiki/Disjunctive_normal_form#Conversion_to_DNF>). For instance, if Alice's policy (not in disjunctive normal form) is of the form (C[1] || D[1]) && ... && (C[n] || D[n]) && APK where C[i] and D[i] are all distinct hashlocks, we require O(2^n) clauses to put it in disjunctive normal form. If Alice wants to create signatures that are restricted to a specific combination of C[i]'s and D[i]'s, she needs to use an exponential number of pubkeys, which isn't tractable to do in Script. But neither my original proposal nor CODESEPARATOR helps in this case either because CODESEPARATOR can mark only the last executed position. Taproot's MAST (Merklized Alternative Script Tree per aj's suggestion), can maybe provide a tractable solution to this in cases where it is applicable. The MAST is always a disjunction and because the tapleaf is signed, it is safe to reuse pubkeys between alternative branches. This analysis suggests that we should amend CODESEPARATORs behaviour to update an accumulator (presumably a running hash value), so that all executed CODESEPARATOR positions end up covered by the signature. That would provide a solution to the above problem for those cases where taproot's MAST cannot be used. I'm not sure if it is better to propose such an amendment to CODESEPARATOR's behaviour now, or to propose to soft-fork in such optional behaviour at a later time. However, what I said above was even too simplified. In general, a policy of the form. (Exists w[1]. C[1](w[1]) && PK[1,1](w[1]) && ... && PK[1,m[1]](w[1]) || ... || (Exists w[n]. C[n](w[n]) && PK[n,1](w[n]) && ... && PK[n,m[n]](w[n])) where each term could possibly be parameterized by some witness value (though at the moment there isn't enough functionality in Script to parameterize the pubkeys in any reasonably way and it maybe isn't even possible to parameterise the conditions in any reasonable way). In general, you might want your signature to cover (some function of) this witness value. This suggests that we would actually want a CODESEPARATOR variant that pushes a stack item into the accumulator that gets covered by the signature rather than pushing the CODESEPARATOR position. Though at this point the name CODESEPARATOR is probably not suitable, even if it subsumes the functionality. Again, I'm not sure if it is better to propose such a replacement for CODESEPARATOR's behaviour now, or to propose to soft-fork in such optional behaviour at a later time. --0000000000001985bc0598fab940 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
After chatting with andytoshi and others, and some mo= re thinking I've been convinced that my specific concern about other us= ers masquerading other people pubkeys as their own in complex scripts is ac= tually a non-issue.

No matter what you write in Sc= ript (today), you are limited to expressing some policy that is logically e= quivalent to a set of conditions and signatures on pubkeys that can be expr= essed in disjunctive normal form.=C2=A0 We can write such a policy as
=

(C[1] && PK[1,1] && ... && PK[1= ,m[1]]) || ... || (C[n] && PK[n,1] && ... && PK[n,m= [n]])

where C[i] is some conjunction of conditions= such as timelock constraints, or hash-lock constraints or any other kind o= f proof of publication, and where PK[i,j] is a requirement of a signature a= gainst a specific public key.

From Alice's poi= nt of view, she can divide set of clauses under the disjunction into those = that contain a pubkey that she considers (partially) under her control and = those clauses that she does not control (even though as we shall see those = other keys might actually be under Alice's control, unbeknownst to her)= . To that end, let us consider a specific representative policy.
=
=C2=A0=C2=A0=C2=A0 (C[1] && APK[1]) || (C[2] &&a= mp; APK[2] && BPK[2]) || (C[3] && BPK[3])

where Alice considers herself in control of APK[1] and APK[2], and = where she considers Bob in control of BPK[2] and BPK[3] and where C[1], C[2= ], and C[3] are different conditions, let's say three different hash-lo= cks.=C2=A0 We will also say that Alice has ensured that her pubkeys in diff= erent clauses are different (i.e. APK[1] !=3D APK[2]), but she doesn't = make any such assumption for Bob's keys and neither will we.
<= div>
When Alice funded this Script, or otherwise accepted it = for consideration, she agreed that she wouldn't control the redemption = of the UTXO as long as the preimage for C[3] is published.=C2=A0 In particu= lar, Alice doesn't even need to fully decode the Script semantics for t= hat clause beyond determining that it enforces the C[3] requirement that sh= e cares about. Even if Bob was masquerading Alice's pubkey as his own (= as in BPK[3] =3D APK[1] or BPK[3] =3D APK[2]), and he ends up copying her s= ignature into that clause, Alice ends up with C[3] published as she origina= lly accepted as a possibility.=C2=A0 Bob masquerading Alice's pubkey as= his own only serves to hamper his own ability to sign for his clauses (I m= ean, Bob might be trying to convince some third party that Alice signed for= something she didn't actually sign for, but such misrepresentations of= the meaning of digital signatures is outside our scope and this just serve= s as a reminder not to be deceived by Bob's tricks here).
And the same argument holds for BPK[2].=C2=A0 Even if BPK[2] = =3D APK[1] and Bob tries to copy Alice's signature into the C[2] condit= ion, he still needs a countersignature with her APK[2], so Alice remains in= control of that clause.=C2=A0 And if BPK[2] =3D APK[2] then Bob can only c= opy Alice's signature on the C[2] condition, but in that case she has a= lready authorised that condition.=C2=A0 Again, Bob masquerading Alice's= pubkey as his own only serves to hamper his own ability to sign for his cl= auses.

So what makes our potential issue here safe= , versus the dangers that would happen in <https://bitcoin.stackexchange.com/a/85665/49= 364> where Bob masqurades Alice's UTXO as his own?=C2=A0 The key= problem in the UTXO case isn't so much Bob masquerading Alice's pu= bkey as his own, as it is an issue with Alice reusing her pubkeys and Bob t= aking advantage of that.=C2=A0 We do, in fact, have exactly the same issue = in Script.=C2=A0 If Alice were to reuse pubkeys such that APK[1] =3D APK[2]= , then Bob could take her signature for C[1] and transplant it to redeem un= der condition C[2].=C2=A0 We see that it is imperative that Alice ensures t= hat she doesn't reuse pubkeys that she considers under her control for = different conditions when she wants her signature to distinguish between th= em.

For various reasons, some historical, it i= s much harder to avoid pubkey reuse for different UTXOs than it is to avoid= pubkey reuse within a single script.=C2=A0 We often use Bitcoin addresses = in non-interactive ways, such as putting them on flyers or painting them on= walls and such.=C2=A0 Without a standard for tweaking such pubkeys in a pe= r-transaction way, we end up with a lot of pubkey reuse between various UTX= Os.=C2=A0 However, within a Script, avoiding pubkey reuse ought to be easie= r.=C2=A0 Alice must communicate different pubkeys intended for different cl= auses, or if Bob is constructing a whole complex script on Alice's beha= lf, he may need to add CODESEPARATORs if tweaking Alice's pubkey isn= 9;t an option.

The conversion of a policy to disju= nctive normal form can involve an exponential blowup (see <http= s://en.wikipedia.org/wiki/Disjunctive_normal_form#Conversion_to_DNF>= ).=C2=A0 For instance, if Alice's policy (not in disjunctive normal for= m) is of the form

=C2=A0=C2=A0=C2=A0 (C[1] || D[1]= ) && ... && (C[n] || D[n]) && APK
where C[i] and D[i] are all distinct hashlocks, we require O(2^= n) clauses to put it in disjunctive normal form.=C2=A0 If Alice wants to cr= eate signatures that are restricted to a specific combination of C[i]'s= and D[i]'s, she needs to use an exponential number of pubkeys, which i= sn't tractable to do in Script.=C2=A0 But neither my original proposal = nor CODESEPARATOR helps in this case either because CODESEPARATOR can mark = only the last executed position.=C2=A0 Taproot's MAST (Merklized Altern= ative Script Tree per aj's suggestion), can maybe provide a tractable s= olution to this in cases where it is applicable.=C2=A0 The MAST is always a= disjunction and because the tapleaf is signed, it is safe to reuse pubkeys= between alternative branches.

This analysis sugge= sts that we should amend CODESEPARATORs behaviour to update an accumulator = (presumably a running hash value), so that all executed CODESEPARATOR posit= ions end up covered by the signature.=C2=A0 That would provide a solution t= o the above problem for those cases where taproot's MAST cannot be used= .=C2=A0 I'm not sure if it is better to propose such an amendment to CO= DESEPARATOR's behaviour now, or to propose to soft-fork in such optiona= l behaviour at a later time.

However, what I said = above was even too simplified.=C2=A0 In general, a policy of the form.

=C2=A0=C2=A0=C2=A0 (Exists w[1]. C[1](w[1]) &= & PK[1,1](w[1]) && ... && PK[1,m[1]](w[1]) || ... || (E= xists w[n]. C[n](w[n]) && PK[n,1](w[n]) && ... && P= K[n,m[n]](w[n]))

where each term could possibly be= parameterized by some witness value (though at the moment there isn't = enough functionality in Script to parameterize the pubkeys in any reasonabl= y way and it maybe isn't even possible to parameterise the conditions i= n any reasonable way).=C2=A0 In general, you might want your signature to c= over (some function of) this witness value.=C2=A0 This suggests that we wou= ld actually want a CODESEPARATOR variant that pushes a stack item into the = accumulator that gets covered by the signature rather than pushing the CODE= SEPARATOR position.=C2=A0 Though at this point the name CODESEPARATOR is pr= obably not suitable, even if it subsumes the functionality.=C2=A0 Again, I&= #39;m not sure if it is better to propose such a replacement for CODESEPARA= TOR's behaviour now, or to propose to soft-fork in such optional behavi= our at a later time.
--0000000000001985bc0598fab940--