Date: Fri, 6 Dec 2019 14:51:53 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Russell O'Connor <roconnor@blockstream.io>
Message-ID: <20191206045153.dufkatmm6izcy4dw@erisian.com.au>
References: <CAMZUoKm7Y8bRJ+hqmvyPwwTWHaMA7JJc5TZdx7Eufax9G0D=Gg@mail.gmail.com>
 <20191128080659.msrpdpcjhhvbqtv2@erisian.com.au>
 <CAMZUoKmYi6btmhN8NmePPZNpPtXwNp=EpyYrxo7P2Ug7fnPSwQ@mail.gmail.com>
 <20191203083538.ggiginwo5k6m4ywq@erisian.com.au>
 <CAMZUoKkRVE-1hPvAZmo4QfLRBgeXzxk0bBncN9eZ110+Hb7T+A@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <CAMZUoKkRVE-1hPvAZmo4QfLRBgeXzxk0bBncN9eZ110+Hb7T+A@mail.gmail.com>
User-Agent: NeoMutt/20170113 (1.7.2)
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Signing CHECKSIG position in Tapscript
Precedence: list

On Thu, Dec 05, 2019 at 03:24:46PM -0500, Russell O'Connor wrote:

Thanks for the careful write up! That matches what I was thinking.

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

On IRC, gmaxwell suggests "OP_BREADCRUMB" as a name for (something like)
this functionality.

(I think it's a barely plausible stretch to use the name "CODESEPARATOR"
for marking a position in the script -- that separates what was before
and after, at least; anything more general seems like it warrants a
better name though)

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

FWIW, I think it's too soon to propose this because (a) it's not clear
there's a practical need for it, (b) it's not clear the functionality is
quite right (opcode vs more automatic sighash flag?), and (c) as you say,
it's not clear it's powerful enough.

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

Last bit first, it seems pretty clear to me that this is too novel an
idea to propose it immediately -- we should explore the problem space
more first to see what's the best way of doing it before coding it into
consensus. And (guessing) I think the tapscript upgrade methods should
be fine for handling this later.

I think the annex is also not general enough for what you're thinking
here, in that it wouldn't allow for one signature to constrain the witness
data more than some other signature -- so you'd need to determine all
the constraints for all signatures to finish filling out the annex,
and could only then start signing.

I think you could conceivably do any/all of:

 * commit to a hash of all the witness data that hasn't been popped off
   the stack ("suffix" commitment -- the data will be used by later script
   opcodes)
 * commit to a hash of all the witness data that has been popped off the
   stack ("prefix" commitment -- this is the data that's been used by
   earlier script opcodes)
 * commit to the hash of the current stack

That would be expensive, but still doable as O(1) per opcode / stack
element. I think any other masking would mean you'd have potentially
O(size of witness data) or O(size of stack) runtime per signature which
I think would be unacceptable...

I guess a general implementation to at least think about the possibilities
might be an "OP_DATACOMMIT" opcode that pops an element from the stack,
does hash_"DataCommit"(element), and then any later signatures commit
to that value (maybe with OP_0 OP_DATACOMMIT allowing you to get back to
the default state). You'd either need to write your script carefully to
commit to witness data you're using elsewhere, or have some other new
opcodes to do that more conveniently...

CODESEP at position "x" in the script is equivalent to "<x> DATACOMMIT"
here, I think. "BREADCRUMB .. BREADCRUMB" could be something like:

   OP_0 TOALT [at start of script]
   ..
   FROMALT x CAT SHA256 DUP TOALT DATACOMMIT   
   ..
   FROMALT y CAT SHA256 DUP TOALT DATACOMMIT   

if the altstack was otherwise unused, I guess; so the accumulator
behaviour probably warrants something better.

It also more or less gives you CHECKSIGFROMSTACK behaviour by doing
"SWAP OP_DATACOMMIT OP_CHECKSIG" and a SIGHASH_NONE|ANYPREVOUTANYSCRIPT
signature.

But that seems like a plausible generalisation to think about?

Cheers,
aj