MIME-Version: 1.0
References: <CAMZUoKm7Y8bRJ+hqmvyPwwTWHaMA7JJc5TZdx7Eufax9G0D=Gg@mail.gmail.com>
 <20191128080659.msrpdpcjhhvbqtv2@erisian.com.au>
 <CAMZUoKmYi6btmhN8NmePPZNpPtXwNp=EpyYrxo7P2Ug7fnPSwQ@mail.gmail.com>
 <20191203083538.ggiginwo5k6m4ywq@erisian.com.au>
In-Reply-To: <20191203083538.ggiginwo5k6m4ywq@erisian.com.au>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Thu, 5 Dec 2019 15:24:46 -0500
Message-ID: <CAMZUoKkRVE-1hPvAZmo4QfLRBgeXzxk0bBncN9eZ110+Hb7T+A@mail.gmail.com>
To: Anthony Towns <aj@erisian.com.au>
Content-Type: multipart/alternative; boundary="0000000000001985bc0598fab940"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Signing CHECKSIG position in Tapscript
Precedence: list

--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 <https://bitcoin.stackexchange.com/a/85665/49364> 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

<div dir=3D"ltr"><div>After chatting with andytoshi and others, and some mo=
re thinking I&#39;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.</div><div><br></div><div>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</div>=
<div><br></div><div>(C[1] &amp;&amp; PK[1,1] &amp;&amp; ... &amp;&amp; PK[1=
,m[1]]) || ... || (C[n] &amp;&amp; PK[n,1] &amp;&amp; ... &amp;&amp; PK[n,m=
[n]])</div><div><br></div><div>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.</div><div><br></div><div>From Alice&#39;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&#39;s control, unbeknownst to her)=
. To that end, let us consider a specific representative policy.</div><div>=
<br></div><div>=C2=A0=C2=A0=C2=A0 (C[1] &amp;&amp; APK[1]) || (C[2] &amp;&a=
mp; APK[2] &amp;&amp; BPK[2]) || (C[3] &amp;&amp; BPK[3])</div><div><br></d=
iv><div>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&#39;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&#39;t =
make any such assumption for Bob&#39;s keys and neither will we.<br></div><=
div><br></div><div>When Alice funded this Script, or otherwise accepted it =
for consideration, she agreed that she wouldn&#39;t control the redemption =
of the UTXO as long as the preimage for C[3] is published.=C2=A0 In particu=
lar, Alice doesn&#39;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&#39;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&#39;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&#39;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&#39;s tricks here).</div><div><br=
></div><div>And the same argument holds for BPK[2].=C2=A0 Even if BPK[2] =
=3D APK[1] and Bob tries to copy Alice&#39;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&#39;s signature on the C[2] condition, but in that case she has a=
lready authorised that condition.=C2=A0 Again, Bob masquerading Alice&#39;s=
 pubkey as his own only serves to hamper his own ability to sign for his cl=
auses.</div><div><br></div><div>So what makes our potential issue here safe=
, versus the dangers that would happen in &lt;<a href=3D"https://bitcoin.st=
ackexchange.com/a/85665/49364">https://bitcoin.stackexchange.com/a/85665/49=
364</a>&gt; where Bob masqurades Alice&#39;s UTXO as his own?=C2=A0 The key=
 problem in the UTXO case isn&#39;t so much Bob masquerading Alice&#39;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&#39;t reuse pubkeys that she considers under her control for =
different conditions when she wants her signature to distinguish between th=
em.<br></div><div><br></div><div>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&#39;s beha=
lf, he may need to add CODESEPARATORs if tweaking Alice&#39;s pubkey isn=
9;t an option.</div><div><br></div><div>The conversion of a policy to disju=
nctive normal form can involve an exponential blowup (see &lt;<a href=3D"ht=
tps://en.wikipedia.org/wiki/Disjunctive_normal_form#Conversion_to_DNF">http=
s://en.wikipedia.org/wiki/Disjunctive_normal_form#Conversion_to_DNF</a>&gt;=
).=C2=A0 For instance, if Alice&#39;s policy (not in disjunctive normal for=
m) is of the form</div><div><br></div><div>=C2=A0=C2=A0=C2=A0 (C[1] || D[1]=
) &amp;&amp; ... &amp;&amp; (C[n] || D[n]) &amp;&amp; APK<br></div><div><br=
></div><div>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]&#39;s=
 and D[i]&#39;s, she needs to use an exponential number of pubkeys, which i=
sn&#39;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&#39;s MAST (Merklized Altern=
ative Script Tree per aj&#39;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.</div><div><br></div><div>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&#39;s MAST cannot be used=
.=C2=A0 I&#39;m not sure if it is better to propose such an amendment to CO=
DESEPARATOR&#39;s behaviour now, or to propose to soft-fork in such optiona=
l behaviour at a later time.</div><div><br></div><div>However, what I said =
above was even too simplified.=C2=A0 In general, a policy of the form.</div=
><div><br></div><div><div>=C2=A0=C2=A0=C2=A0 (Exists w[1]. C[1](w[1]) &amp;=
&amp; PK[1,1](w[1]) &amp;&amp; ... &amp;&amp; PK[1,m[1]](w[1]) || ... || (E=
xists w[n]. C[n](w[n]) &amp;&amp; PK[n,1](w[n]) &amp;&amp; ... &amp;&amp; P=
K[n,m[n]](w[n]))</div><div><br></div><div>where each term could possibly be=
 parameterized by some witness value (though at the moment there isn&#39;t =
enough functionality in Script to parameterize the pubkeys in any reasonabl=
y way and it maybe isn&#39;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&#39;s behaviour now, or to propose to soft-fork in such optional behavi=
our at a later time.</div></div></div>

--0000000000001985bc0598fab940--