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

Discussion:

Luke Durback via bitcoin-dev

2015-12-10 01:35:17 UTC

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

Jeff Garzik via bitcoin-dev

2015-12-10 04:03:30 UTC

Permalink

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 <

Post by Luke Durback via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Luke Durback via bitcoin-dev

2015-12-10 04:23:26 UTC

Permalink

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

Post by Jeff Garzik via bitcoin-dev
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 <

Post by Luke Durback via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Jorge Timón via bitcoin-dev

2015-12-10 05:38:01 UTC

Permalink

On Dec 10, 2015 10:10 AM, "Luke Durback via bitcoin-dev" <

Post by Luke Durback via bitcoin-dev
This, combined with the ability to make new transactions arbitrarily

would allow a function to pay its creator.

I don't understand what you mean by "a function" in this context, I assume
you mean a scriptSig, but then "paying its creator" doesn't make much sense
to me .

Could you provide some high level examples of the use cases you would like
to support with this?

Luke Durback via bitcoin-dev

2015-12-10 06:36:28 UTC

Permalink

Tomorrow, I'll work on writing a way to do voting on proposals with BTC
used as voting shares (This will be difficult as I do not know FORTH).
That seems like a fairly simple, useful example that will require loops and
reused functions. I'll add a fee that goes to the creator.

IMO, if you write a complicated system of scripts that's used frequently,
it makes sense to charge a fee for its usage. A decentralized exchange
between colored coins, for instance might take a small fee on each trade.

On Dec 10, 2015 10:10 AM, "Luke Durback via bitcoin-dev" <

Post by Luke Durback via bitcoin-dev
This, combined with the ability to make new transactions arbitrarily

Jorge Timón via bitcoin-dev

2015-12-11 15:36:48 UTC

Permalink

Post by Luke Durback via bitcoin-dev
Tomorrow, I'll work on writing a way to do voting on proposals with BTC

used as voting shares (This will be difficult as I do not know FORTH).
That seems like a fairly simple, useful example that will require loops and
reused functions. I'll add a fee that goes to the creator.

If it's voting for something consensus, you will need something special. If
it's not consensus (ie external) thw voting doesn't have to hit the chain
at all.
I don't see how "loops and reused functions" are needed in the scripting
language for this use case, but I'm probably missing some details. Please,
the more concrete you make your example, the easiest it will be for me to
understand.

Post by Luke Durback via bitcoin-dev
IMO, if you write a complicated system of scripts that's used frequently,

it makes sense to charge a fee for its usage.

But each scriptSig is only executed once with its corresponding
scriptPubKey. Are you proposing we change that?

Post by Luke Durback via bitcoin-dev
A decentralized exchange between colored coins, for instance might take

a small fee on each trade.

I've been researching the topic of decentralized exchange from before the
term "colored coins" was first used (now there's multiple designs and
implementations); contributed to and reviewed many designs: none of them
(colored coins or not) required turing completeness.
I'm sorry, but what you are saying here is too vague for me to concretely
be able to refute the low level "needs" you claim your use cases to have.

Post by Luke Durback via bitcoin-dev
On Dec 10, 2015 10:10 AM, "Luke Durback via bitcoin-dev" <

Post by Luke Durback via bitcoin-dev
This, combined with the ability to make new transactions arbitrarily

would allow a function to pay its creator.

Post by Luke Durback via bitcoin-dev
I don't understand what you mean by "a function" in this context, I

assume you mean a scriptSig, but then "paying its creator" doesn't make
much sense to me .

Post by Luke Durback via bitcoin-dev
Could you provide some high level examples of the use cases you would

like to support with this?

Jorge Timón via bitcoin-dev

2015-12-11 15:38:37 UTC

Permalink

well "only executed once" (every time someone verifies that transaction)...