Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id BE136E92 for ; Thu, 10 Dec 2015 04:03:31 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ig0-f175.google.com (mail-ig0-f175.google.com [209.85.213.175]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 003CE151 for ; Thu, 10 Dec 2015 04:03:30 +0000 (UTC) Received: by mail-ig0-f175.google.com with SMTP id ph11so5063870igc.1 for ; Wed, 09 Dec 2015 20:03:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=ORF4aXCxlyq6cCrsinDR7otBKLRePnxgjhyk6ZHldK8=; b=oAK6av4eu4Omg2jy6MZ1vpbsxGUcuBdoJ4KFptGEQh9Q1mkblb3z4yDZhb+F0+oqlN qg9C9go37Bn6JxxzT6xCZgvcDpm9U9M7lAGJWx2ZCglZuLd7AKXYT63cgum9I785e2cU QGVb1QF1h5oJNj5bzp7FRHmjNNVFI4HCDZ+g88c7LB+9R/jXkDn0s8XQjkAYR8tzccau Ldd7kf+10M9Bt3QGR0TRAtNvP5J3G2oRSmNwbnCRYe5Vq55zOWdBRiJARRPmt1QJw60B uK/cqk6lI90zHpVk6KfvE3r+2n1t7i3lOTaq6Z4pfPX5SRWdeVxINZIQYLIdf7zz4hpx 9RFw== MIME-Version: 1.0 X-Received: by 10.50.160.2 with SMTP id xg2mr34722923igb.54.1449720210432; Wed, 09 Dec 2015 20:03:30 -0800 (PST) Received: by 10.79.8.198 with HTTP; Wed, 9 Dec 2015 20:03:30 -0800 (PST) In-Reply-To: References: Date: Thu, 10 Dec 2015 12:03:30 +0800 Message-ID: From: Jeff Garzik To: Luke Durback Content-Type: multipart/alternative; boundary=001a11343db82aa9190526834a94 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 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:03:31 -0000 --001a11343db82aa9190526834a94 Content-Type: text/plain; charset=UTF-8 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 > > --001a11343db82aa9190526834a94 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
There is no need for a BIP draft. =C2=A0"Turing compl= ete" is just a fancy, executive-impressing term for "it can run a= ny computer program", or put even more simply, "it can loop"=

Furthermore, the specification of such a language is tr= ivial.=C2=A0 It is the economics of validation that is the complex piece.= =C2=A0 Proving whether 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... running the program.=C2=A0 That produces enormous validat= ion 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. com= puter language, with your preferred algorithm libraries and development too= ls.

See=C2=A0https://github.com/jgarzik/moxiebox for a working example of= provable execution.



On Thu, Dec 10, 2015 at 9:35 A= M, Luke Durback via bitcoin-dev <bitcoin-dev@lists.lin= uxfoundation.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 Wrig= ht suggested is possible.

---

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

Th= e principle opcodes (excluding conditional versions of call and return_from= ) needed are

OP_DEFINITION_START FunctionName: =C2= =A0The code that follows is the definition of a new function to be named Tr= ansactionSenderAddress.FunctionName.=C2=A0 If this function name is already= taken, the transaction is marked invalid.=C2=A0 Within the transaction, th= e function can be called simply as FunctionName.

O= P_DEFINITION_END: =C2=A0This ends a function definition

=
OP_FUNCTION_NAME FunctionName: =C2=A0Gives the current transacti= on the name FunctionName (this is necessary to build recursive functions)

---

OP_CALL Namespac= e.FunctionName Value TransactionFee: =C2=A0This marks the transaction as va= lid.=C2=A0 It also pushes the current execution location onto the return st= ack, debits the calling transaction by the TransactionFee and Value, and cr= eates a new transaction specified by Namespace.FunctionName with both stack= s continued from before (this may be dangerous, but I see no way around it)= with the specified value.

OP_RETURN_FROM_CALL_AND= _CONTINUE: =C2=A0This 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 transact= ion can create another transaction arbitrarily, so to prepare for that, I a= dditionally propose

OP_NAMESPACE: =C2=A0Pushes the= current namespace onto the control stack

This, combined with the ab= ility to make new transactions arbitrarily would allow a function to pay it= s creator.



I underst= and that this isn't all that is needed, but I think it's a start.= =C2=A0 I hope this 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


--001a11343db82aa9190526834a94--