Re: [bitcoin-dev] Signing CHECKSIG position in Tapscript

["Russell O'Connor" <roconnor@blockstream.io>]

[-- Attachment #1: Type: text/plain, Size: 7174 bytes --]

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.

[-- Attachment #2: Type: text/html, Size: 8126 bytes --]