Return-Path: Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 45325C077D for ; Fri, 6 Dec 2019 04:52:04 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id 3B7B4883BB for ; Fri, 6 Dec 2019 04:52:04 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from whitealder.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 35+Sw21+pwa4 for ; Fri, 6 Dec 2019 04:52:03 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from azure.erisian.com.au (cerulean.erisian.com.au [139.162.42.226]) by whitealder.osuosl.org (Postfix) with ESMTPS id 3800C883B8 for ; Fri, 6 Dec 2019 04:52:03 +0000 (UTC) Received: from aj@azure.erisian.com.au (helo=sapphire.erisian.com.au) by azure.erisian.com.au with esmtpsa (Exim 4.89 #1 (Debian)) id 1id5aw-0005Bi-6O; Fri, 06 Dec 2019 14:51:59 +1000 Received: by sapphire.erisian.com.au (sSMTP sendmail emulation); Fri, 06 Dec 2019 14:51:53 +1000 Date: Fri, 6 Dec 2019 14:51:53 +1000 From: Anthony Towns To: Russell O'Connor Message-ID: <20191206045153.dufkatmm6izcy4dw@erisian.com.au> References: <20191128080659.msrpdpcjhhvbqtv2@erisian.com.au> <20191203083538.ggiginwo5k6m4ywq@erisian.com.au> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: User-Agent: NeoMutt/20170113 (1.7.2) X-Spam-Score-int: -18 X-Spam-Bar: - 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: Fri, 06 Dec 2019 04:52:04 -0000 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 " 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