Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 4B448EFB for ; Thu, 10 Dec 2015 04:23:47 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ig0-f172.google.com (mail-ig0-f172.google.com [209.85.213.172]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 78EEB15E for ; Thu, 10 Dec 2015 04:23:46 +0000 (UTC) Received: by igcto18 with SMTP id to18so5284395igc.0 for ; Wed, 09 Dec 2015 20:23:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=aUkWPQYqyiZD2EwNA/apyOiWCQhgFobz1K7HPEcuXSE=; b=eK8ee7UDO9Iwmgs8lKsxl7NNfanGrsf24gsV6g/aZzH3bhnz1+Q0Vd4s2eoFyQTTBg mnngyYoigb6s0f1LkFUTJ07lqY47CDBfuW7ihTV6ccCqpwDIbuWAKuqUe/feRcXTLlsi 1k6uZiald8a0SswMYhMTYv0OBrLkMmjFgKbFU7bhv9yyOgJczO6R17LyU9lxVylWLPnS qQNePhlyxqWgyqOBhtsvEep9JlWhijmkNKMQchyiJsGSlrgab03Py+k46ZacdDQxd8/8 W7eUeIzv8FAlh1DS678837dwGozpERqPaKUu0TXxlYsQ+IWKxkku6n+1SgobNH/upz86 k7SQ== X-Received: by 10.50.61.164 with SMTP id q4mr13284193igr.13.1449721425991; Wed, 09 Dec 2015 20:23:45 -0800 (PST) MIME-Version: 1.0 Received: by 10.64.12.177 with HTTP; Wed, 9 Dec 2015 20:23:26 -0800 (PST) In-Reply-To: References: From: Luke Durback Date: Wed, 9 Dec 2015 23:23:26 -0500 Message-ID: To: Jeff Garzik Content-Type: multipart/alternative; boundary=047d7bdc1b6c9ea2310526839291 X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_LOW 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: Thu, 10 Dec 2015 04:34:46 +0000 Cc: Bitcoin development mailing list Subject: Re: [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Development Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 10 Dec 2015 04:23:47 -0000 --047d7bdc1b6c9ea2310526839291 Content-Type: text/plain; charset=UTF-8 Mr. Garzik, Thank you for the prompt response. I should have explained my proposal a little better. First of all, this is not Turing completeness, nor is it pseudo-complete in the sense of Ethereum's gas economics. Instead, whenever a function call is encountered, the transaction is validated and can be included in a block. The code actually halts many times. A new transaction is then produced with the 2 stacks stored in the transaction data (so that the 2 stacks are saved and execution can be continued later). When OP_RETURN_FROM_CALL_AND_CONTINUE is encountered, the top value of the Return stack is popped and execution continues from that location until validation/invalidation is reached. It's not necessary to check the code to see that it has no infinite loops because any transaction with infinite loops will run out of BTC with which to fund the transaction fees of additional function calls. To reiterate the most important point: Execution halts every time a function call is encountered and the transaction can be included in a block. A new transaction is then produced that can (if included in a block) continue execution. Luke Durback On Wed, Dec 9, 2015 at 11:03 PM, Jeff Garzik wrote: > There is no need for a BIP draft. "Turing complete" is just a fancy, > executive-impressing term for "it can run any computer program", or put > even more simply, "it can loop" > > Furthermore, the specification of such a language is trivial. It is the > economics of validation that is the complex piece. Proving whether or not > a program will halt as expected - The Halting Problem - is near impossible > for most complex programs. As a result, your proof is... running the > program. That produces enormous validation consequences and costs for > generic-execution scripts when applied to a decentralized network of > validation P2P nodes. > > If you need that capability, it is just as easy to use a normal C/C++/etc. > computer language, with your preferred algorithm libraries and development > tools. > > See https://github.com/jgarzik/moxiebox for a working example of provable > execution. > > > > On Thu, Dec 10, 2015 at 9:35 AM, Luke Durback via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > >> Hello Bitcoin-Dev, >> >> I hope this isn't out of line, but I joined the mailing list to try to >> start a discussion on adding opcodes to make Script Turing Pseudo-Complete >> as Wright suggested is possible. >> >> --- >> >> In line with Wright's suggestion, I propose adding a return stack >> alongside the, already existing, control stack. >> >> The principle opcodes (excluding conditional versions of call and >> return_from) needed are >> >> OP_DEFINITION_START FunctionName: The code that follows is the >> definition of a new function to be named >> TransactionSenderAddress.FunctionName. If this function name is already >> taken, the transaction is marked invalid. Within the transaction, the >> function can be called simply as FunctionName. >> >> OP_DEFINITION_END: This ends a function definition >> >> OP_FUNCTION_NAME FunctionName: Gives the current transaction the name >> FunctionName (this is necessary to build recursive functions) >> >> --- >> >> OP_CALL Namespace.FunctionName Value TransactionFee: This marks the >> transaction as valid. It also pushes the current execution location onto >> the return stack, debits the calling transaction by the TransactionFee and >> Value, and creates a new transaction specified by Namespace.FunctionName >> with both stacks continued from before (this may be dangerous, but I see no >> way around it) with the specified value. >> >> OP_RETURN_FROM_CALL_AND_CONTINUE: This pops the top value off the return >> stack and continues from the specified location with both stacks in tact. >> >> --- >> >> It would also be useful if a transaction can create another transaction >> arbitrarily, so to prepare for that, I additionally propose >> >> OP_NAMESPACE: Pushes the current namespace onto the control stack >> >> This, combined with the ability to make new transactions arbitrarily >> would allow a function to pay its creator. >> >> >> >> I understand that this isn't all that is needed, but I think it's a >> start. I hope this proposal has met you all well, >> >> Luke Durback >> >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> >> > --047d7bdc1b6c9ea2310526839291 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Mr. Garzik,

Thank you for the prompt re= sponse.=C2=A0 I should have explained my proposal a little better.

F= irst of all, this is not Turing completeness, nor is it pseudo-complete in = the sense of Ethereum's gas economics.

Instead= , whenever a function call is encountered, the transaction is validated and= can be included in a block.=C2=A0 The code actually halts many times.=C2= =A0 A new transaction is then produced with the 2 stacks stored in the tran= saction data (so that the 2 stacks are saved and execution can be continued= later).=C2=A0 When OP_RETURN_FROM_CALL_AND_CONTINUE is encountered, the to= p value of the Return stack is popped and execution continues from that loc= ation until validation/invalidation is reached.=C2=A0 It's not necessar= y to check the code to see that it has no infinite loops because any transa= ction with infinite loops will run out of BTC with which to fund the transa= ction fees of additional function calls.

To reiterate the most impor= tant point: =C2=A0Execution halts every time a function call is encountered= and the transaction can be included in a block.=C2=A0 A new transaction is= then produced that can (if included in a block) continue execution.

Luke Durback

On Wed, Dec 9, 2015 at 11:03 PM, Jeff Garzik = <jgarzik@gmail.co= m> wrote:
= There is no need for a BIP draft. =C2=A0"Turing complete" is just= a fancy, executive-impressing term for "it can run any computer progr= am", or put even more simply, "it can loop"

Furthermore, the specification of such a language is trivial.=C2=A0 It i= s the economics of validation that is the complex piece.=C2=A0 Proving whet= her or not a program will halt as expected - The Halting Problem - is near = impossible for most complex programs.=C2=A0 As a result, your proof is... r= unning the program.=C2=A0 That produces enormous validation consequences an= d costs for generic-execution scripts when applied to a decentralized netwo= rk of validation P2P nodes.

If you need that capab= ility, it is just as easy to use a normal C/C++/etc. computer language, wit= h your preferred algorithm libraries and development tools.

<= /div>
See=C2=A0https://github.com/jgarzik/moxiebox for a working example o= f provable execution.



On T= hu, Dec 10, 2015 at 9:35 AM, Luke Durback via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
<= /div>
Hello Bitcoin-Dev,

I hope this isn't= out of line, but I joined the mailing list to try to start a discussion on= adding opcodes to make Script Turing Pseudo-Complete as Wright suggested i= s possible.

---

In line w= ith Wright's suggestion, I propose adding a return stack alongside the,= already existing, control stack.

The principle op= codes (excluding conditional versions of call and return_from) needed are

OP_DEFINITION_START FunctionName: =C2=A0The code th= at follows is the definition of a new function to be named TransactionSende= rAddress.FunctionName.=C2=A0 If this function name is already taken, the tr= ansaction is marked invalid.=C2=A0 Within the transaction, the function can= be called simply as FunctionName.

OP_DEFINITION_E= ND: =C2=A0This ends a function definition

OP_= FUNCTION_NAME FunctionName: =C2=A0Gives the current transaction the name Fu= nctionName (this is necessary to build recursive functions)

---

OP_CALL Namespace.FunctionName= Value TransactionFee: =C2=A0This marks the transaction as valid.=C2=A0 It = also pushes the current execution location onto the return stack, debits th= e calling transaction by the TransactionFee and Value, and creates a new tr= ansaction specified by Namespace.FunctionName with both stacks continued fr= om before (this may be dangerous, but I see no way around it) with the spec= ified value.

OP_RETURN_FROM_CALL_AND_CONTINUE: =C2= =A0This pops the top value off the return stack and continues from the spec= ified location with both stacks in tact.

---

It would also be useful if a transaction can create= another transaction arbitrarily, so to prepare for that, I additionally pr= opose

OP_NAMESPACE: =C2=A0Pushes the current names= pace onto the control stack

This, combined with the ability to make = new transactions arbitrarily would allow a function to pay its creator.



I understand that this = isn't all that is needed, but I think it's a start.=C2=A0 I hope th= is proposal has met you all well,

Luke Durback

_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev



--047d7bdc1b6c9ea2310526839291--