From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 2F0EB8CC for ; Thu, 22 Nov 2018 20:53:12 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from sender-of-o53.zoho.com (sender-of-o53.zoho.com [135.84.80.218]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 1FD295E2 for ; Thu, 22 Nov 2018 20:53:10 +0000 (UTC) ARC-Seal: i=1; a=rsa-sha256; t=1542919982; cv=none; d=zoho.com; s=zohoarc; b=kIY4eXeXK3v7vURU+9K70aHIZPNDRNKb3vctT7z68aSRCBoG63YM6pguXP48YHM1UZxt+tM2lslPrIVyZuzm9RpzOh5YxCd+7i3rJAB/lI2SmNGZiY/A/Wk9BnScX/qFK66P6mBxiDZZlw8gWqQnOFVNCvqfob26OBQjmEA2+2w= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zoho.com; s=zohoarc; t=1542919982; h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:MIME-Version:Message-ID:References:Subject:To:ARC-Authentication-Results; bh=WlyM59OEDkYeLF0U7REYULF0wMMjicwpGDBFVTc1+ys=; b=APdhqeUfZqOUWdERebGyFWgCuqELrhlB7pdcbyOr8AMWP6An905KKFPd0kRWsMiUshEaDmuPwPA+JdnIpLfhw1ey83qXQPCIFDeeLFJru6yWDjii6bfGWmkJPdGt+U+r7RZrTEvJRNetHhT677aloW9/d7FYsxXIqSQ7FvV1OJM= ARC-Authentication-Results: i=1; mx.zoho.com; dkim=pass header.i=xbt.hk; spf=pass smtp.mailfrom=jl2012@xbt.hk; dmarc=pass header.from= header.from= Received: from [10.8.0.105] (n218103234118.netvigator.com [218.103.234.118]) by mx.zohomail.com with SMTPS id 1542919979271609.3178364483915; Thu, 22 Nov 2018 12:52:59 -0800 (PST) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 12.0 \(3445.100.39\)) From: Johnson Lau In-Reply-To: Date: Fri, 23 Nov 2018 04:52:54 +0800 Content-Transfer-Encoding: quoted-printable Message-Id: <8CD6C248-9ADF-4324-B4E3-DE41A1ED49A9@xbt.hk> References: <64A86A3A-4633-4BE2-AE09-30BD136BCC2D@xbt.hk> To: Russell O'Connor X-Mailer: Apple Mail (2.3445.100.39) X-ZohoMailClient: External X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Fri, 23 Nov 2018 04:04:44 +0000 Cc: bitcoin-dev Subject: Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 22 Nov 2018 20:53:12 -0000 Assuming a script size of 128 bytes (including SHA256 padding), 2^20 = scripts is 134MB. Double it to 268MB for the merkle branch hashes. With = roughly 100MB/s, this should take 2.5s (or 42min for 30 levels). = However, memory use is not considered. >each call to this operation effectively takes O(script-size) time I=E2=80=99m not sure if this is correct. Actually, = CTransactionSignatureSerializer() scans every script for = OP_CODESEPARATOR. Scripts with and without OP_CODESEPARATOR should take = exactly the same O(script-size) time (see = https://github.com/bitcoin/bitcoin/pull/14786) Also, this is no longer a concern under segwit (BIP143), which = CTransactionSignatureSerializer() is not used. Actually, = OP_CODESEPARATOR under segwit is way simpler than the proposed OP_MASK. = If one finds OP_MASK acceptable, there should be no reason to reject = OP_CODESEPARATOR. >One suggestion I heard (I think I heard it from Pieter) to achieve the = above is to add an internal counter that increments on every control = flow operator,=E2=80=A6=E2=80=A6... If I have to choose among OP_CODESEPARATOR and =E2=80=9Cflow operator = counting=E2=80=9D, I=E2=80=99d rather choose OP_CODESEPARATOR. At least = we don=E2=80=99t need to add more lines to the consensus code, just for = something that is mostly archivable with MAST. > On 23 Nov 2018, at 12:23 AM, Russell O'Connor = wrote: >=20 > I see, so your suggestion is that a sequence of OP_IF ... OP_ENDIF can = be replaced by a Merklized Script tree of that depth in practice. >=20 > I'm concerned that at script creation time it takes exponential time = to complete a Merkle root of depth 'n'. Can anyone provide benchmarks = or estimates of how long it takes to compute a Merkle root of a full = tree of various depths on typical consumer hardware? I would guess = things stop becoming practical at a depth of 20-30. >=20 > On Thu, Nov 22, 2018 at 9:28 AM Johnson Lau wrote: > With MAST in taproot, OP_IF etc become mostly redundant, with worse = privacy. To maximise fungibility, we should encourage people to use = MAST, instead of improve the functionality of OP_IF and further = complicate the protocol. >=20 >=20 >> On 22 Nov 2018, at 1:07 AM, Russell O'Connor via bitcoin-dev = wrote: >>=20 >> On Mon, Nov 19, 2018 at 10:22 PM Pieter Wuille via bitcoin-dev = wrote: >> So my question is whether anyone can see ways in which this = introduces >> redundant flexibility, or misses obvious use cases? >>=20 >> Hopefully my comment is on-topic for this thread: >>=20 >> Given that we want to move away from OP_CODESEPARATOR, because each = call to this operation effectively takes O(script-size) time, we need a = replacement for the functionality it currently provides. While perhaps = the original motivation for OP_CODESEPARTOR is surrounded in mystery, it = currently can be used (or perhaps abused) for the task of creating = signature that covers, not only which input is being signed, but which = specific branch within that input Script code is being signed for. >>=20 >> For example, one can place an OP_CODESEPARATOR within each branch of = an IF block, or by placing an OP_CODESEPARATOR before each OP_CHECKSIG = operation. By doing so, signatures created for one clause cannot be = used as signatures for another clause. Since different clauses in = Bitcoin Script may be enforcing different conditions (such as different = time-locks, hash-locks, etc), it is useful to be able to sign in such a = way that your signature is only valid when the conditions for a = particular branch are satisfied. In complex Scripts, it may not be = practical or possible to use different public keys for every different = clause. (In practice, you will be able to get away with fewer = OP_CODESEPARATORS than one in every IF block). >>=20 >> One suggestion I heard (I think I heard it from Pieter) to achieve = the above is to add an internal counter that increments on every control = flow operator, OP_IF, OP_NOTIF, OP_ELSE, OP_ENDIF, and have the = signature cover the value of this counter. Equivalently we divide every = Bitcoin Script program into blocks deliminated by these control flow = operator and have the signature cover the index of the block that the = OP_CHECKSIG occurs within. More specifically, we will want a SigHash = flag to enables/disable the signature covering this counter. >>=20 >> There are many different ways one might go about replacing the = remaining useful behaviour of OP_CODESEPARATOR than the one I gave = above. I would be happy with any solution. >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >=20