From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) by lists.linuxfoundation.org (Postfix) with ESMTP id ABEFBC002D for ; Wed, 11 May 2022 11:42:20 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id A9961828BA for ; Wed, 11 May 2022 11:42:20 +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: smtp1.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=protonmail.com Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id x6lWV8qPi5b4 for ; Wed, 11 May 2022 11:42:19 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from mail-4319.protonmail.ch (mail-4319.protonmail.ch [185.70.43.19]) by smtp1.osuosl.org (Postfix) with ESMTPS id EE80681421 for ; Wed, 11 May 2022 11:42:18 +0000 (UTC) Date: Wed, 11 May 2022 11:42:10 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail2; t=1652269336; bh=sWSw5CobOvhoeod5U3nMy88MJ9ji2Uf0DdAdJi64tg8=; 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=Vb5raaq23zcbLNuLvwwePJOwctVvU8u7dRNkLZIuTSSF2EayNDlPUhu69jJAsVq5I zX3cLDAUoi6x3qPLXNLP1ddVpyjzS3hkT+xidxG+ZcMmEDimB9uiR+gNfHT6/YAEY0 RcN5vrLPXAvWCnLNp89qp3sVCix8oFWJsV6RjC7zizjm0d92fiIIdq173RPqVsD4Hh 05c4BDgJWTynBSjamAfL7HbbHPnlfhs2Qx3vVAKuR+iaISpBqWDudOp95wVqy/7zH8 b4E/88Ond53N3/E4fOpMZu5oSpdEqNynRUq2gW0T/+TLtYCGFnLB+811HB7xo6x5+6 /kT+P2mRueIcA== To: "vjudeu@gazeta.pl" From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: <161946014-482cdec305e2bd7a2c3fc4774c70239d@pmq1v.m5r2.onet> References: <161946014-482cdec305e2bd7a2c3fc4774c70239d@pmq1v.m5r2.onet> 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: Wed, 11 May 2022 11:42:20 -0000 Good morning vjudeu, > > Looks like `OP_CAT` is not getting enabled until after we are reasonabl= y sure that recursive covenants are not really unsafe. > > Maybe we should use OP_SUBSTR instead of OP_CAT. Or even better: OP_SPLIT= . Then, we could have OP_SPLIT ... that would spli= t a string N times (so there will be N+1 pieces). Or we could have just OP_= SPLIT to split one string into two. Or maybe OP_2SPLIT and OP_3SPLIT,= just to split into two or three pieces (as we have OP_2DUP and OP_3DUP). I= think OP_SUBSTR or OP_SPLIT is better than OP_CAT, because then things alw= ays get smaller and we can be always sure that we will have one byte as the= smallest unit in our Script. Unfortunately `OP_SUBSTR` can be used to synthesize an effective `OP_CAT`. Instead of passing in two items on the witness stack to be `OP_CAT`ted toge= ther, you instead pass in the two items to concatenate, and *then* the conc= atenation. Then you can synthesize a SCRIPT which checks that the supposed concatenati= on is indeed the two items to be concatenated. Recursive covenants DO NOT arise from the increasing amounts of memory the = trivial `OP_DUP OP_CAT OP_DUP OP_CAT` repetition allocates. REMEMBER: `OP_CAT` BY ITSELF DOES NOT ENABLE COVENANTS, WHETHER RECURSIVE O= R NOT. Instead, `OP_CAT` enable recursive covenants (which we are not certain are = safe) because `OP_CAT` allows quining to be done. Quining is a technique to pass a SCRIPT with a copy of its code, so that it= can then enforce that the output is passed to the exact same input SCRIPT. `OP_SUBSTR` allows a SCRIPT to validate that it is being passed a copy of i= tself and that the complete SCRIPT contains its copy as an `OP_PUSH` and th= e rest of the SCRIPT as actual code. This is done by `OP_SUBSTR` the appropriate parts of the supposed complete = SCRIPT and comparing them to a reference value we have access to (because o= ur own SCRIPT was passed to us inside an `OP_PUSH`). # Assume that the witness stack top is the concatenation of # `OP_PUSH`, the SCRIPT below, then the`SCRIPT below. # Assume this SCRIPT is prepended with an OP_PUSH of our own code. OP_TOALTSTACK # save our reference OP_DUP 1 OP_SUBSTR # Get the OP_PUSH argument OP_FROMALTSTACK OP_DUP OP_TOALTSTACK # Get our reference OP_EQUALVERIFY # check they are the same OP_DUP <1 + scriptlength> OP_SUBSTR # Get the SCRIPT body OP_FROMALTSTACK # Get our reference OP_EQUALVERIFY # check they are the same # At this point, we have validated that the top of the witness stack # is the quine of this SCRIPT. # TODO: validate the `OP_PUSH` instruction, left as an exercise for the # reader. Thus, `OP_SUBSTR` is enough to enable quining and is enough to implement re= cursive covenants. We cannot enable `OP_SUBSTR` either, unless we are reasonably sure that rec= ursive covenants are safe. (FWIW recursive covenants are probably safe, as they are not in fact Turing= -complete, they are a hair less powerful, equivalent to the total functiona= l programming with codata.) Regards, ZmnSCPxj