Re: [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness

From: Luke Durback <luke.durback@gmail•com>
To: Jeff Garzik <jgarzik@gmail•com>
Cc: Bitcoin development mailing list <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness
Date: Wed, 9 Dec 2015 23:23:26 -0500	[thread overview]
Message-ID: <CAEj3M+yHnPv0p0icRmFtNxJti2riSGzTPtGCHR_a9dW7qdkFpA@mail.gmail.com> (raw)
In-Reply-To: <CADm_WcZdC-iNF=tMmYYafsaLaHUcck03zw8cdsSCCPvXdTNyrw@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 4521 bytes --]

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 <jgarzik@gmail•com> 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
>>
>>
>

[-- Attachment #2: Type: text/html, Size: 5956 bytes --]