[BIP-117] Tail call semantics #12132

kallewoof commented at 9:18 AM on January 9, 2018: member

Implements BIP 117 as policy rules for transaction relay, causing transactions which violate the new tail-call semantics to be treated as non-standard. This is not the soft-fork activation logic needed to use tail-call scripts in production.

Tail-call semantics is a sort of user-programmable P2SH which combines well with BIP 116's MERKLEBRANCHVERIFY to allows for a script to commit to a practically unbounded number of code pathways, and then reveal the actual code pathway used at spend time, achieving a form of generalized MAST.

in src/script/interpreter.cpp:1132 in fafc110be9 outdated

1048 | +        // subscript from the top of the stack:
1049 | +        const valtype& policyScript = stacktop(-1);
1050 | +        script = CScript(policyScript.begin(), policyScript.end());
1051 | +        popstack(stack);
1052 | +        // Only allow one tail-call:
1053 | +        allow_tail_call = false;

ckcollab commented at 10:43 PM on January 9, 2018:

Apologies for being annoying//this may be a stupid question: but why only do TCO once?

maaku commented at 11:07 PM on January 9, 2018:

https://github.com/bitcoin/bips/blob/master/bip-0117.mediawiki#rationale

ckcollab commented at 7:09 AM on January 10, 2018:

Thank you very much!

in src/script/interpreter.cpp:1076 in fafc110be9 outdated

1042 | @@ -1039,6 +1043,20 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
1043 |      if (!vfExec.empty())
1044 |          return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL);
1045 |  
1046 | +    if (allow_tail_call && !stack.empty() && ((stack.size() + altstack.size()) >= 2) && CastToBool(stack.back())) {

benma commented at 7:00 AM on January 10, 2018:

The third condition of the specification is not checked:

https://github.com/bitcoin/bips/blob/master/bip-0117.mediawiki#specification

the following Nth element on the main stack (or alt stack, as above) is between 1 and 520 bytes,

Should it?

About being able to concatenate up to 17 elements to form the script: why stop at 17? Would be great to include some rationale about this in the BIP, or possibly extend the BIP to allow longer scripts if that makes sense.

maaku commented at 1:55 AM on January 11, 2018:

Oops. The current version of this pull request does not match the BIP. My fault -- we were so busy converting MERKLEBRANCHVERIFY to be multi-element that it slipped though cracks. The BIP was updated to the new scheme which allows the script to be split across multiple stack elements, but this PR does not reflect that. I will update this PR to match the BIP.

To answer your question though, the reason that a maximum number of 17 elements is allowed, is due to the fact that only OP_1 through OP_16 are provided as single-byte opcodes, and 17*520 = 8,840 bytes is close enough to the maximum script limit of 10,000 bytes that it doesn't necessarily make sense to have a further exception for 18 or 19 pushes to reach the full limit. Particularly since MAST eliminates the need for such long scripts in the first place.

benma commented at 2:03 AM on January 11, 2018:

Thanks!

maaku commented at 6:51 AM on January 12, 2018:

The PR has been updated to allow for multiple script elements, as specified in BIP 117.

kallewoof force-pushed on Jan 11, 2018

kallewoof force-pushed on Jan 12, 2018

maaku commented at 6:52 AM on January 12, 2018: contributor

Travis build error looks like a transient issue.

laanwj added the label Consensus on Jan 15, 2018

Add tail-call semantics to script interpreter (not active).

If, at the end of script execution, the stack has more than one item on it, the top-most element is interpreted as a serialized script and executed, with the remaining elements on the stack as inputs. No state is maintained, and termination of the subscript terminates execution of the script as a whole. Only one tail-call is allowed per script execution, and neither P2SH nor segwit nor execution of the scriptSig results in tail-call semantics, although the P2SH or segwit redeem script can make a single tail-call.

c21fb91ade

Enable tail-call semantics as a standard script validation flag. Transactions that fail tail-call verification will be rejected from the mempool, making it easier to test and later soft-fork activate this feature. Blocks which contain transactions with "invalid" tail-call semantics will still be accepted; this is *not* the soft-fork required to use tail-call semantics in production. 5790a07798

kallewoof force-pushed on Apr 24, 2018

f'script_tests: switch to CLEANSTACK where appropriate 9a40e8e42a

MarcoFalke added the label Needs rebase on Jun 6, 2018

kallewoof commented at 3:31 AM on September 19, 2018: member

I'm closing this for now. If a better suited champion appears I'll help out where I can. Ping @btcdrak @maaku.

kallewoof closed this on Sep 19, 2018

laanwj removed the label Needs rebase on Oct 24, 2019

kallewoof deleted the branch on Jan 4, 2020

DrahtBot locked this on Feb 15, 2022