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