Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 024C0AC9 for ; Tue, 12 Sep 2017 19:57:15 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-it0-f49.google.com (mail-it0-f49.google.com [209.85.214.49]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 07630E0 for ; Tue, 12 Sep 2017 19:57:13 +0000 (UTC) Received: by mail-it0-f49.google.com with SMTP id 6so1186433itl.1 for ; Tue, 12 Sep 2017 12:57:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=friedenbach-org.20150623.gappssmtp.com; s=20150623; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=9+7w6hbTrd2G0rZYOu8ZumhcO4GSOO1U8ie6KD4IbOM=; b=gFaL/ZX1AbItXbiXtnt9aE3Xrrm9LfA1UIefIeR3VQ4WfzWwRIt/NsQxr1jNFDD7pE zDkBHJzbLfw9hGNRj8lTK6/0Zs6M4t8uTnbKKfZOS/YPFtJ4mmuzTQb9KwQFkA6MtipA wESe0NyBAz58r485QkwMLyyIvdG4AdG88Zda3gqv3+Jpu/ydM0Y/2iY31/dF4fOMjph4 HYVUo9NJOpDDgSY1BFVbPL5koYOhTpuUFX4TNQ2Gnuuo30+wC6RpvddiyoX+6BVOJqHb th28XQyc/NTQLHjp/KGEb0q56vba7U1wo01JQ2s5WZh/ytHdGfUwyi8s4K9HAjdD/3bi AhMg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=9+7w6hbTrd2G0rZYOu8ZumhcO4GSOO1U8ie6KD4IbOM=; b=tG3kyZpjc+aRXKygS+ZfNI/h7U2x0fdRld0bkqraDuHESIlERYVDkoeqB17DL06u0K mTM8TFBhEBTYVoGp0Pz0ewh1BdPf+wjmwJhx+psMREL7NSgu7vSIwORLlV2XWep8MXE0 DZoBA0AfHQnyA4lQHrB0x+GD+ZpWQW+iyLcKX9k01J2zPQ3guicL0NFuvANy3pwckcET CiyCN5B2scE47UoJp0Z6JN3GlbZWSGj+XJS+k3RDzpk5V+/k0RBdjTG+/cOzRAd0QjnL vOEgp75O3My1CbxYLVizQw5ipB9wPMpX/g0RiyvUQIAsCiBKqJpiKSeOZbLN1v75zMO3 bhDw== X-Gm-Message-State: AHPjjUhmHd+78en5E5RiZeqirCNqkKbuopxvq5AJprHNchYEwgRM+aJi LXqGa/J8m6+Pfki7L9Taic3/FNOnUlc= X-Google-Smtp-Source: AOwi7QCYpeITe/GNCOMsUSHbQ/F0nwPAIIEaMEPluzEp09QpV+lWFnh/Wow6Cmui1ZZUWjIMJ68+ZA== X-Received: by 10.36.23.88 with SMTP id 85mr1098337ith.86.1505246233303; Tue, 12 Sep 2017 12:57:13 -0700 (PDT) Received: from ?IPv6:2601:646:8080:1291:1d3f:a13:2924:858a? ([2601:646:8080:1291:1d3f:a13:2924:858a]) by smtp.gmail.com with ESMTPSA id g133sm6287606iof.41.2017.09.12.12.57.10 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 12 Sep 2017 12:57:11 -0700 (PDT) Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\)) From: Mark Friedenbach In-Reply-To: Date: Tue, 12 Sep 2017 12:57:10 -0700 Content-Transfer-Encoding: 7bit Message-Id: <61D84B62-0F3F-48E1-B749-F628AD91BC12@friedenbach.org> References: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org> <26AD157C-A5A9-48C3-8D29-0AD1ED35EDDD@xbt.hk> <2419914E-E196-44B4-8663-599AF616A897@friedenbach.org> To: Johnson Lau X-Mailer: Apple Mail (2.3273) X-Spam-Status: No, score=0.5 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM autolearn=disabled version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Tue, 12 Sep 2017 19:57:42 +0000 Cc: bitcoin-dev Subject: Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST 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: Tue, 12 Sep 2017 19:57:15 -0000 On Sep 12, 2017, at 1:55 AM, Johnson Lau wrote: > This is ugly and actually broken, as different script path may > require different number of stack items, so you don't know how many > OP_TOALTSTACK do you need. Easier to just use a new witness version DEPTH makes this relatively easy to do. Just repeat the following for the maximum number of stack elements that might be used: DEPTH 1SUB IF SWAP TOALTSTACK ENDIF There are probably more compact alternatives. Using a new script version is easier, but not faster. There's a number of things that might be fixed in a v1 upgrade, and various design decisions to sort out regarding specification of a witness version (version in the witness rather than the scriptPubKey). Tree signatures and MAST are immediately useful to many services, however, and I would hate to delay usage by six months to a year or more by serializing dependencies instead of doing them in parallel. > Otherwise, one could attack relay and mining nodes by sending many > small size txs with many sigops, forcing them to validate, and > discard due to insufficient fees. > > Technically it might be ok if we commit the total validation cost > (sigop + hashop + whatever) as the first witness stack item That is what I'm suggesting. And yes, there are changes that would have to be made to the p2p layer and transaction processing to handle this safely. I'm arguing that the cost of doing so is worth it, and a better path forward. > Without the limit I think we would be DoS-ed to dead 4MB of secp256k1 signatures takes 10s to validate on my 5 year old laptop (125,000 signatures, ignoring public keys and other things that would consume space). That's much less than bad blocks that can be constructed using other vulnerabilities. > So to make it functionally comparable with your proposal, the > IsMSV0Stack() function is not needed. The new 249-254 lines in > interpreter.cpp could be removed. The new 1480-1519 lines could be > replaced by a few lines copied from the existing P2WSH code. I can > make a minimal version if you want to see how it looks like That's alright, I don't think it's necessary to purposefully restrict one to compare them head to head with the same features. They are different proposals with different pros and cons. Kind regards, Mark Friedenbach