* [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness @ 2015-12-10 1:35 Luke Durback 2015-12-10 4:03 ` Jeff Garzik 2015-12-10 5:38 ` Jorge Timón 0 siblings, 2 replies; 10+ messages in thread From: Luke Durback @ 2015-12-10 1:35 UTC (permalink / raw) To: bitcoin-dev [-- Attachment #1: Type: text/plain, Size: 1910 bytes --] 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 [-- Attachment #2: Type: text/html, Size: 2384 bytes --] ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness 2015-12-10 1:35 [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness Luke Durback @ 2015-12-10 4:03 ` Jeff Garzik 2015-12-10 4:23 ` Luke Durback 2015-12-10 5:38 ` Jorge Timón 1 sibling, 1 reply; 10+ messages in thread From: Jeff Garzik @ 2015-12-10 4:03 UTC (permalink / raw) To: Luke Durback; +Cc: Bitcoin development mailing list [-- Attachment #1: Type: text/plain, Size: 3173 bytes --] 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: 4240 bytes --] ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness 2015-12-10 4:03 ` Jeff Garzik @ 2015-12-10 4:23 ` Luke Durback 0 siblings, 0 replies; 10+ messages in thread From: Luke Durback @ 2015-12-10 4:23 UTC (permalink / raw) To: Jeff Garzik; +Cc: Bitcoin development mailing list [-- 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 --] ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness 2015-12-10 1:35 [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness Luke Durback 2015-12-10 4:03 ` Jeff Garzik @ 2015-12-10 5:38 ` Jorge Timón 2015-12-10 6:36 ` Luke Durback 1 sibling, 1 reply; 10+ messages in thread From: Jorge Timón @ 2015-12-10 5:38 UTC (permalink / raw) To: Luke Durback; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 477 bytes --] On Dec 10, 2015 10:10 AM, "Luke Durback via bitcoin-dev" < bitcoin-dev@lists.linuxfoundation.org> wrote: > 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? [-- Attachment #2: Type: text/html, Size: 640 bytes --] ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness 2015-12-10 5:38 ` Jorge Timón @ 2015-12-10 6:36 ` Luke Durback 2015-12-11 15:36 ` Jorge Timón 0 siblings, 1 reply; 10+ messages in thread From: Luke Durback @ 2015-12-10 6:36 UTC (permalink / raw) To: Jorge Timón; +Cc: Bitcoin development mailing list [-- Attachment #1: Type: text/plain, Size: 979 bytes --] 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" < bitcoin-dev@lists.linuxfoundation.org> wrote: > 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? [-- Attachment #2: Type: text/html, Size: 1367 bytes --] ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness 2015-12-10 6:36 ` Luke Durback @ 2015-12-11 15:36 ` Jorge Timón 2015-12-11 15:38 ` Jorge Timón 2015-12-11 21:45 ` Luke Durback 0 siblings, 2 replies; 10+ messages in thread From: Jorge Timón @ 2015-12-11 15:36 UTC (permalink / raw) To: Luke Durback; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 1994 bytes --] On Dec 10, 2015 7:36 AM, "Luke Durback" <luke.durback@gmail.com> wrote: > > 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. > 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? > 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. > On Dec 10, 2015 10:10 AM, "Luke Durback via bitcoin-dev" < bitcoin-dev@lists.linuxfoundation.org> wrote: > > 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? [-- Attachment #2: Type: text/html, Size: 2442 bytes --] ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness 2015-12-11 15:36 ` Jorge Timón @ 2015-12-11 15:38 ` Jorge Timón 2015-12-11 21:45 ` Luke Durback 1 sibling, 0 replies; 10+ messages in thread From: Jorge Timón @ 2015-12-11 15:38 UTC (permalink / raw) To: Luke Durback; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 2266 bytes --] well "only executed once" (every time someone verifies that transaction)... On Dec 11, 2015 4:36 PM, "Jorge Timón" <jtimon@jtimon.cc> wrote: > > On Dec 10, 2015 7:36 AM, "Luke Durback" <luke.durback@gmail.com> wrote: > > > > 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. > > > 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? > > > 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. > > > On Dec 10, 2015 10:10 AM, "Luke Durback via bitcoin-dev" < > bitcoin-dev@lists.linuxfoundation.org> wrote: > > > 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? > [-- Attachment #2: Type: text/html, Size: 2830 bytes --] ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness 2015-12-11 15:36 ` Jorge Timón 2015-12-11 15:38 ` Jorge Timón @ 2015-12-11 21:45 ` Luke Durback 2015-12-12 20:00 ` Jorge Timón 1 sibling, 1 reply; 10+ messages in thread From: Luke Durback @ 2015-12-11 21:45 UTC (permalink / raw) To: Jorge Timón; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 3534 bytes --] >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 had in mind voting for something that can't be trusted if done externally: Perhaps BIPs for instance. People would somehow "mark" their BTC as being "For Proposition X" (as opposed to all other propositions) and the vote would be canceled as soon as the BTC is spent again. Unfortunately, I've spent the past 2 days trying to find a design that would allow this (I don't think my original suggestion made sense in the context of how transactions work), and I haven't gotten much yet. >But each scriptSig is only executed once with its corresponding scriptPubKey. Are you proposing we change that? Sorry, I didn't understand Bitcoin's transaction model well enough when I first made the proposal. If Turing Pseudo-Completeness is possible with Bitcoin, then I understand now that it could not require you to execute a script more than once. My current thought is that recursion can be accomplished via checking if the next output's scriptPubKey is identical in every way to the current scriptPubKey. Unfortunately, a lot more is needed than just recursion in order to do on-chain BTC voting the way I have in mind. I'll keep working on this. On Fri, Dec 11, 2015 at 10:36 AM, Jorge Timón <jtimon@jtimon.cc> wrote: > > On Dec 10, 2015 7:36 AM, "Luke Durback" <luke.durback@gmail.com> wrote: > > > > 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. > > > 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? > > > 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. > > > On Dec 10, 2015 10:10 AM, "Luke Durback via bitcoin-dev" < > bitcoin-dev@lists.linuxfoundation.org> wrote: > > > 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? > [-- Attachment #2: Type: text/html, Size: 4502 bytes --] ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness 2015-12-11 21:45 ` Luke Durback @ 2015-12-12 20:00 ` Jorge Timón 2015-12-12 21:01 ` Emin Gün Sirer 0 siblings, 1 reply; 10+ messages in thread From: Jorge Timón @ 2015-12-12 20:00 UTC (permalink / raw) To: Luke Durback; +Cc: Bitcoin Dev On Fri, Dec 11, 2015 at 10:45 PM, Luke Durback <luke.durback@gmail.com> wrote: >>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 had in mind voting for something that can't be trusted if done externally: > Perhaps BIPs for instance. People would somehow "mark" their BTC as being > "For Proposition X" (as opposed to all other propositions) and the vote > would be canceled as soon as the BTC is spent again. > > Unfortunately, I've spent the past 2 days trying to find a design that would > allow this (I don't think my original suggestion made sense in the context > of how transactions work), and I haven't gotten much yet. Well, as said, if it's for consensus, you will need to adapt the system in a special way anyway, but I still don't see why turing completeness is required. This type of idea is not new. Since miners can censor votes (and that's undetectable for consensus), several solutions have been proposed, time lock the votes, for example. >>But each scriptSig is only executed once with its corresponding >> scriptPubKey. Are you proposing we change that? > > Sorry, I didn't understand Bitcoin's transaction model well enough when I > first made the proposal. If Turing Pseudo-Completeness is possible with > Bitcoin, then I understand now that it could not require you to execute a > script more than once. My current thought is that recursion can be > accomplished via checking if the next output's scriptPubKey is identical in > every way to the current scriptPubKey. Unfortunately, a lot more is needed > than just recursion in order to do on-chain BTC voting the way I have in > mind. I'll keep working on this. What you call "recursion" seems similar to what we usually call "covenants", see https://bitcointalk.org/index.php?topic=278122.0 Although the thread says "an amusingly bad idea", I think it's actually a great idea and there's some use cases that are very hard to support without covenants. Again, no Turing completeness required for this. > On Fri, Dec 11, 2015 at 10:36 AM, Jorge Timón <jtimon@jtimon.cc> wrote: >> >> >> On Dec 10, 2015 7:36 AM, "Luke Durback" <luke.durback@gmail.com> wrote: >> > >> > 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. >> >> > 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? >> >> > 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. >> >> > On Dec 10, 2015 10:10 AM, "Luke Durback via bitcoin-dev" >> > <bitcoin-dev@lists.linuxfoundation.org> wrote: >> > > 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? > > ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness 2015-12-12 20:00 ` Jorge Timón @ 2015-12-12 21:01 ` Emin Gün Sirer 0 siblings, 0 replies; 10+ messages in thread From: Emin Gün Sirer @ 2015-12-12 21:01 UTC (permalink / raw) To: Jorge Timón, Luke Durback; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 5743 bytes --] ., , /. , /, ,. / , .. ,,, . // ., . _. ... .. ._. , _ , , , , , ... _ _. ,. . ,., _. ., , .. , ,, ._ . . _ . , , , , /..,, / , . . _ .,. _.. , , .. _ .. ,.,, _ , _ , /// . , / . ,. , ,., . , , ., ,. ._ , ,,,// , , . , , . . , , // . , , / _,. , . ,, . .. /,/ . . . .,,_// ,, ., . . /_. , / . / .._ . ,, / . . _ , , , / , _ ., , ,,, .. , , /.,. /. / . ,/ , . . /, /, ._ ,/. _ ., ,// , .,,, , , , , , ,. ,.,. . , . ,. ., , / _ . / ,.,. , ,._ ,, , _ _ , , . ,, , _ _.., , // , __ / !;"$'''. b __ On Sat, Dec 12, 2015, 3:01 PM Jorge Timón < bitcoin-dev@lists.linuxfoundation.org> wrote: > On Fri, Dec 11, 2015 at 10:45 PM, Luke Durback <luke.durback@gmail.com> > wrote: > >>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 had in mind voting for something that can't be trusted if done > externally: > > Perhaps BIPs for instance. People would somehow "mark" their BTC as > being > > "For Proposition X" (as opposed to all other propositions) and the vote > > would be canceled as soon as the BTC is spent again. > > > > Unfortunately, I've spent the past 2 days trying to find a design that > would > > allow this (I don't think my original suggestion made sense in the > context > > of how transactions work), and I haven't gotten much yet. > > Well, as said, if it's for consensus, you will need to adapt the > system in a special way anyway, but I still don't see why turing > completeness is required. > This type of idea is not new. Since miners can censor votes (and > that's undetectable for consensus), several solutions have been > proposed, time lock the votes, for example. > > >>But each scriptSig is only executed once with its corresponding > >> scriptPubKey. Are you proposing we change that? > > > > Sorry, I didn't understand Bitcoin's transaction model well enough when I > > first made the proposal. If Turing Pseudo-Completeness is possible with > > Bitcoin, then I understand now that it could not require you to execute a > > script more than once. My current thought is that recursion can be > > accomplished via checking if the next output's scriptPubKey is identical > in > > every way to the current scriptPubKey. Unfortunately, a lot more is > needed > > than just recursion in order to do on-chain BTC voting the way I have in > > mind. I'll keep working on this. > > What you call "recursion" seems similar to what we usually call > "covenants", see > > https://bitcointalk.org/index.php?topic=278122.0 > > Although the thread says "an amusingly bad idea", I think it's > actually a great idea and there's some use cases that are very hard to > support without covenants. > Again, no Turing completeness required for this. > > > On Fri, Dec 11, 2015 at 10:36 AM, Jorge Timón <jtimon@jtimon.cc> wrote: > >> > >> > >> On Dec 10, 2015 7:36 AM, "Luke Durback" <luke.durback@gmail.com> wrote: > >> > > >> > 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. > >> > >> > 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? > >> > >> > 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. > >> > >> > On Dec 10, 2015 10:10 AM, "Luke Durback via bitcoin-dev" > >> > <bitcoin-dev@lists.linuxfoundation.org> wrote: > >> > > 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? > > > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 8413 bytes --] ^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2015-12-12 21:01 UTC | newest] Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2015-12-10 1:35 [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness Luke Durback 2015-12-10 4:03 ` Jeff Garzik 2015-12-10 4:23 ` Luke Durback 2015-12-10 5:38 ` Jorge Timón 2015-12-10 6:36 ` Luke Durback 2015-12-11 15:36 ` Jorge Timón 2015-12-11 15:38 ` Jorge Timón 2015-12-11 21:45 ` Luke Durback 2015-12-12 20:00 ` Jorge Timón 2015-12-12 21:01 ` Emin Gün Sirer
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox