From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id EC780C002D for ; Sat, 7 May 2022 14:08:41 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id DAB7D60E1E for ; Sat, 7 May 2022 14:08:41 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -1.601 X-Spam-Level: X-Spam-Status: No, score=-1.601 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, FROM_LOCAL_NOVOWEL=0.5, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: smtp3.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=protonmail.com Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ORC2VglBvBpH for ; Sat, 7 May 2022 14:08:41 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from mail-40130.protonmail.ch (mail-40130.protonmail.ch [185.70.40.130]) by smtp3.osuosl.org (Postfix) with ESMTPS id 0422460E1B for ; Sat, 7 May 2022 14:08:40 +0000 (UTC) Date: Sat, 07 May 2022 14:08:27 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail2; t=1651932517; bh=yl8bLcOBZWbcrwgP7W/xN7JKA+FZlZbpyv7iXnPJlCY=; h=Date:To:From:Cc:Reply-To:Subject:Message-ID:In-Reply-To: References:Feedback-ID:From:To:Cc:Date:Subject:Reply-To: Feedback-ID:Message-ID; b=KW6PHrBF70dXRnl5h14JnXVQ9V3XHoWqtd1IHUCQXoHYgm2BRutMd18MKTA8VfwC8 Bvf+zqdInscYW0P48xsL9zHptSBV02HJ9AlaBmXeefJ2ngO8le9EUy7+60YnJt2b2m CVPFHOjnnwW4BWqc+STRR8GtGv8+d9qgAHCSnYGO95hAmogMIzIpf8C0QjfVI/kEYS uU+7zS2pKZ8/P/cpjapt7Py/ef1rRX+Ga8FOgkgSrjaRI53QdmLyZ5kTFje7pnQWLC MiPe6vzz1knUvU3prLWtH3wKDLT0qmLTrB6A0f3PR4KY1xNnm2qfZcmRQGjask7Kwx 9lWWOsM/3TQVg== To: =?utf-8?Q?Jorge_Tim=C3=B3n?= From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: References: <1JO1xrnJ9GwGM4TgLH_rL_LpnZgSb1SyeEOJ9Gzc1VMbKUrmxSh-zUXKwFNvp_5wyiDtRviOf-gRJbrfbhOJl-qym1eEHXpoDAgjE9juucw=@protonmail.com> Feedback-ID: 2872618:user:proton MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Speedy covenants (OP_CAT2) 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: Sat, 07 May 2022 14:08:42 -0000 Good morning Jorge, > Thanks a lot for the many clarifications. > Yeah, I forgot it wasn't OP_CAT alone, but in combination with other thin= gs. > I guess this wouldn't be a covenants proposal then. > But simplicity would enable covenants too indeed, no? > Or did I get that wrong too? Yes, it would enable covenants. However, it could also enable *recursive* covenants, depending on what intr= ospection operations are actually implemented (though maybe not? Russell O'= Connor should be the one that answers this). It is helpful to delineate between non-recursive covenants from recursive c= ovenants. * Even ***with*** `OP_CAT`, the following will enable non-recursive covenan= ts without enabling recursive covenants: * `OP_CTV` * `SIGHASH_ANYPREVOUT` * With `OP_CAT`, the following would enable recursive covenants: * `OP_EVAL` * `OP_CHECKSIGFROMSTACK` * `OP_TX`/`OP_TXHASH` * ...possibly more. * It is actually *easier* to *design* an opcode which inadvertently sup= ports recursive covenants than to design one which avoids recursive covenan= ts. Recursive covenants are very near to true Turing-completeness. We want to avoid Turing-completeness due to the halting problem being unsol= vable for Turing-complete languages. That is, given just a program, we cannot determine for sure if for all poss= ible inputs, it will terminate. It is important in our context (Bitcoin) that any SCRIPT programs we write = *must* terminate, or else we run the risk of a DoS on the network. A fair amount of this is theoretical crap, but if you want to split hairs, = recursive covenants are *not* Turing-complete, but are instead total functi= onal programming with codata. As a very rough bastardization, a program written in a total functional pro= gramming language with codata will always assuredly terminate. However, the return value of a total functional programming language with c= odata can be another program. An external program (written in a Turing-complete language) could then just= keep invoking the interpreter of the total functional programming language= with codata (taking the output program and running it, taking *its* output= program and running it, ad infinitum, thus effectively able to loop indefi= nitely. Translated to Bitcoin transactions, a recursive covenant system can force a= n output to be spent only if the output is spent on a transaction where one= of the outputs is the same covenant (possibly with tweaks). Then an external program can keep passing the output program to the Bitcoin= SCRIPT interpreter --- by building transactions that spend the previous ou= tput. This behavior is still of concern. It may be possible to attack the network by eroding its supply, by such a r= ecursive covenant. -- Common reactions: * We can just limit the number of opcodes we can process and then fail it i= f it takes too many operations! That way we can avoid DoS! * Yes, this indeed drops it from Turing-complete to total, possibly total= functional programming **without** codata. But if it is possible to treat data as code, it may drop it "total but = with codata" instead (i.e. recursive covenants). But if you want to avoid recursive covenants while allowing recursive o= nes (i.e. equivalent to total without codata), may I suggest you instead lo= ok at `OP_CTV` and `SIGHASH_ANYPREVOUT`? * What is so wrong with total-with-codata anyway?? So what if the recursive covenant could potentially consume all Bitcoins,= nobody will pay to it except as a novelty!! If you want to burn your funds, 1BitcoinEater willingly accepts it! * The burden of proof-of-safety is on the proposer, so if you have some p= roof that total-with-codata is safe, by construction, then sure, we can add= opcodes that may enable recursive covenants, and add `OP_CAT` back in too. Regards, ZmnSCPxj