Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
How about using for the first stage, `<...> OP_CALCMERKLEROOT OP_EQUAL` instead of ` OP_CHECKMERKLEBRANCH`? There's maybe 1 or 2 bytes extra, but it seems more future-proof (since there could more easily be alternatives to ` OP_EQUAL` in future script versions). OTOH, OP_ADDTOSCRIPTHASH may be fatally incompatible with script versioning... Old nodes won't know how to check the witness program, which means an undefined version could be used to bypass the correct script entirely. Need to think more on this still. Luke On Wednesday 01 November 2017 3:08:46 PM Mark Friedenbach wrote: > Yes, if you use a witness script version you can save about 40 witness > bytes by templating the MBV script, which I think is equivalent to what > you are suggesting. 32 bytes from the saved hash, plus another 8 bytes or > so from script templates and more efficient serialization. > > I believe the conservatively correct approach is to do this in stages, > however. First roll out MBV and tail call to witness v0. Then once there > is experience with people using it in production, design and deploy a > hashing template for script v1. It might be that we learn more and think > of something better in the meantime. > > > On Nov 1, 2017, at 1:43 AM, Luke Dashjr wrote: > > > > Mark, > > > > I think I have found an improvement that can be made. > > > > As you recall, a downside to this approach is that one must make two > > commitments: first, to the particular "membership-checking script"; and > > then in that script, to the particular merkle root of possible scripts. > > > > Would there be any harm in, instead of checking membership, *calculating* > > the root? If not, then we could define that instead of the witness > > program committing to H(membership-check script), it rather commits to > > H(membership- calculation script | data added by an OP_ADDTOSCRIPTHASH). > > This would, I believe, securely reduce the commitment of both to a > > single hash. > > > > It also doesn't reduce flexibility, since one could omit > > OP_ADDTOSCRIPTHASH from their "membership-calculation" script to get the > > previous membership- check behaviour, and use OP_EQUAL in its > > place. > > > > What do you think? > > > > Luke > > > >> On Saturday 28 October 2017 4:40:01 AM Mark Friedenbach wrote: > >> I have completed updating the three BIPs with all the feedback that I > >> have received so far. In short summary, here is an incomplete list of > >> the changes that were made: > >> > >> * Modified the hashing function fast-SHA256 so that an internal node > >> cannot be interpreted simultaneously as a leaf. * Changed > >> MERKLEBRANCHVERIFY to verify a configurable number of elements from the > >> tree, instead of just one. * Changed MERKLEBRANCHVERIFY to have two > >> modes: one where the inputs are assumed to be hashes, and one where > >> they are run through double-SHA256 first. * Made tail-call eval > >> compatible with BIP141??s CLEANSTACK consensus rule by allowing > >> parameters to be passed on the alt-stack. * Restricted tail-call eval > >> to segwit scripts only, so that checking sigop and opcode limits of the > >> policy script would not be necessary. > >> > >> There were a bunch of other small modifications, typo fixes, and > >> optimizations that were made as well. > >> > >> I am now ready to submit these BIPs as a PR against the bitcoin/bips > >> repo, and I request that the BIP editor assign numbers. > >> > >> Thank you, > >> Mark Friedenbach > >> > >>> On Sep 6, 2017, at 5:38 PM, Mark Friedenbach > >>> wrote: > >>> > >>> I would like to propose two new script features to be added to the > >>> bitcoin protocol by means of soft-fork activation. These features are > >>> a new opcode, MERKLE-BRANCH-VERIFY (MBV) and tail-call execution > >>> semantics. > >>> > >>> In brief summary, MERKLE-BRANCH-VERIFY allows script authors to force > >>> redemption to use values selected from a pre-determined set committed > >>> to in the scriptPubKey, but without requiring revelation of unused > >>> elements in the set for both enhanced privacy and smaller script > >>> sizes. Tail-call execution semantics allows a single level of > >>> recursion into a subscript, providing properties similar to P2SH while > >>> at the same time more flexible. > >>> > >>> These two features together are enough to enable a range of > >>> applications such as tree signatures (minus Schnorr aggregation) as > >>> described by Pieter Wuille [1], and a generalized MAST useful for > >>> constructing private smart contracts. It also brings privacy and > >>> fungibility improvements to users of counter-signing wallet/vault > >>> services as unique redemption policies need only be revealed if/when > >>> exceptional circumstances demand it, leaving most transactions looking > >>> the same as any other MAST-enabled multi-sig script. > >>> > >>> I believe that the implementation of these features is simple enough, > >>> and the use cases compelling enough tha
Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
Yes, if you use a witness script version you can save about 40 witness bytes by templating the MBV script, which I think is equivalent to what you are suggesting. 32 bytes from the saved hash, plus another 8 bytes or so from script templates and more efficient serialization. I believe the conservatively correct approach is to do this in stages, however. First roll out MBV and tail call to witness v0. Then once there is experience with people using it in production, design and deploy a hashing template for script v1. It might be that we learn more and think of something better in the meantime. > On Nov 1, 2017, at 1:43 AM, Luke Dashjr wrote: > > Mark, > > I think I have found an improvement that can be made. > > As you recall, a downside to this approach is that one must make two > commitments: first, to the particular "membership-checking script"; and then > in that script, to the particular merkle root of possible scripts. > > Would there be any harm in, instead of checking membership, *calculating* the > root? If not, then we could define that instead of the witness program > committing to H(membership-check script), it rather commits to H(membership- > calculation script | data added by an OP_ADDTOSCRIPTHASH). This would, I > believe, securely reduce the commitment of both to a single hash. > > It also doesn't reduce flexibility, since one could omit OP_ADDTOSCRIPTHASH > from their "membership-calculation" script to get the previous membership- > check behaviour, and use OP_EQUAL in its place. > > What do you think? > > Luke > > >> On Saturday 28 October 2017 4:40:01 AM Mark Friedenbach wrote: >> I have completed updating the three BIPs with all the feedback that I have >> received so far. In short summary, here is an incomplete list of the >> changes that were made: >> >> * Modified the hashing function fast-SHA256 so that an internal node cannot >> be interpreted simultaneously as a leaf. * Changed MERKLEBRANCHVERIFY to >> verify a configurable number of elements from the tree, instead of just >> one. * Changed MERKLEBRANCHVERIFY to have two modes: one where the inputs >> are assumed to be hashes, and one where they are run through double-SHA256 >> first. * Made tail-call eval compatible with BIP141’s CLEANSTACK consensus >> rule by allowing parameters to be passed on the alt-stack. * Restricted >> tail-call eval to segwit scripts only, so that checking sigop and opcode >> limits of the policy script would not be necessary. >> >> There were a bunch of other small modifications, typo fixes, and >> optimizations that were made as well. >> >> I am now ready to submit these BIPs as a PR against the bitcoin/bips repo, >> and I request that the BIP editor assign numbers. >> >> Thank you, >> Mark Friedenbach >> >>> On Sep 6, 2017, at 5:38 PM, Mark Friedenbach >>> wrote: >>> >>> I would like to propose two new script features to be added to the >>> bitcoin protocol by means of soft-fork activation. These features are >>> a new opcode, MERKLE-BRANCH-VERIFY (MBV) and tail-call execution >>> semantics. >>> >>> In brief summary, MERKLE-BRANCH-VERIFY allows script authors to force >>> redemption to use values selected from a pre-determined set committed >>> to in the scriptPubKey, but without requiring revelation of unused >>> elements in the set for both enhanced privacy and smaller script >>> sizes. Tail-call execution semantics allows a single level of >>> recursion into a subscript, providing properties similar to P2SH while >>> at the same time more flexible. >>> >>> These two features together are enough to enable a range of >>> applications such as tree signatures (minus Schnorr aggregation) as >>> described by Pieter Wuille [1], and a generalized MAST useful for >>> constructing private smart contracts. It also brings privacy and >>> fungibility improvements to users of counter-signing wallet/vault >>> services as unique redemption policies need only be revealed if/when >>> exceptional circumstances demand it, leaving most transactions looking >>> the same as any other MAST-enabled multi-sig script. >>> >>> I believe that the implementation of these features is simple enough, >>> and the use cases compelling enough that we could BIP 8/9 rollout of >>> these features in relatively short order, perhaps before the end of >>> the year. >>> >>> I have written three BIPs to describe these features, and their >>> associated implementation, for which I now invite public review and >>> discussion: >>> >>> Fast Merkle Trees >>> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a >>> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree >>> >>> MERKLEBRANCHVERIFY >>> BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431 >>> Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify >>> >>> Tail-call execution semantics >>> BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368 >>> Code: https://github.com/maaku/bitcoin/tre
Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
Mark, I think I have found an improvement that can be made. As you recall, a downside to this approach is that one must make two commitments: first, to the particular "membership-checking script"; and then in that script, to the particular merkle root of possible scripts. Would there be any harm in, instead of checking membership, *calculating* the root? If not, then we could define that instead of the witness program committing to H(membership-check script), it rather commits to H(membership- calculation script | data added by an OP_ADDTOSCRIPTHASH). This would, I believe, securely reduce the commitment of both to a single hash. It also doesn't reduce flexibility, since one could omit OP_ADDTOSCRIPTHASH from their "membership-calculation" script to get the previous membership- check behaviour, and use OP_EQUAL in its place. What do you think? Luke On Saturday 28 October 2017 4:40:01 AM Mark Friedenbach wrote: > I have completed updating the three BIPs with all the feedback that I have > received so far. In short summary, here is an incomplete list of the > changes that were made: > > * Modified the hashing function fast-SHA256 so that an internal node cannot > be interpreted simultaneously as a leaf. * Changed MERKLEBRANCHVERIFY to > verify a configurable number of elements from the tree, instead of just > one. * Changed MERKLEBRANCHVERIFY to have two modes: one where the inputs > are assumed to be hashes, and one where they are run through double-SHA256 > first. * Made tail-call eval compatible with BIP141’s CLEANSTACK consensus > rule by allowing parameters to be passed on the alt-stack. * Restricted > tail-call eval to segwit scripts only, so that checking sigop and opcode > limits of the policy script would not be necessary. > > There were a bunch of other small modifications, typo fixes, and > optimizations that were made as well. > > I am now ready to submit these BIPs as a PR against the bitcoin/bips repo, > and I request that the BIP editor assign numbers. > > Thank you, > Mark Friedenbach > > > On Sep 6, 2017, at 5:38 PM, Mark Friedenbach > > wrote: > > > > I would like to propose two new script features to be added to the > > bitcoin protocol by means of soft-fork activation. These features are > > a new opcode, MERKLE-BRANCH-VERIFY (MBV) and tail-call execution > > semantics. > > > > In brief summary, MERKLE-BRANCH-VERIFY allows script authors to force > > redemption to use values selected from a pre-determined set committed > > to in the scriptPubKey, but without requiring revelation of unused > > elements in the set for both enhanced privacy and smaller script > > sizes. Tail-call execution semantics allows a single level of > > recursion into a subscript, providing properties similar to P2SH while > > at the same time more flexible. > > > > These two features together are enough to enable a range of > > applications such as tree signatures (minus Schnorr aggregation) as > > described by Pieter Wuille [1], and a generalized MAST useful for > > constructing private smart contracts. It also brings privacy and > > fungibility improvements to users of counter-signing wallet/vault > > services as unique redemption policies need only be revealed if/when > > exceptional circumstances demand it, leaving most transactions looking > > the same as any other MAST-enabled multi-sig script. > > > > I believe that the implementation of these features is simple enough, > > and the use cases compelling enough that we could BIP 8/9 rollout of > > these features in relatively short order, perhaps before the end of > > the year. > > > > I have written three BIPs to describe these features, and their > > associated implementation, for which I now invite public review and > > discussion: > > > > Fast Merkle Trees > > BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a > > Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree > > > > MERKLEBRANCHVERIFY > > BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431 > > Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify > > > > Tail-call execution semantics > > BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368 > > Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics > > > > Note: I have circulated this idea privately among a few people, and I > > will note that there is one piece of feedback which I agree with but > > is not incorporated yet: there should be a multi-element MBV opcode > > that allows verifying multiple items are extracted from a single > > tree. It is not obvious how MBV could be modified to support this > > without sacrificing important properties, or whether should be a > > separate multi-MBV opcode instead. > > > > Kind regards, > > Mark Friedenbach ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
I have completed updating the three BIPs with all the feedback that I have received so far. In short summary, here is an incomplete list of the changes that were made: * Modified the hashing function fast-SHA256 so that an internal node cannot be interpreted simultaneously as a leaf. * Changed MERKLEBRANCHVERIFY to verify a configurable number of elements from the tree, instead of just one. * Changed MERKLEBRANCHVERIFY to have two modes: one where the inputs are assumed to be hashes, and one where they are run through double-SHA256 first. * Made tail-call eval compatible with BIP141’s CLEANSTACK consensus rule by allowing parameters to be passed on the alt-stack. * Restricted tail-call eval to segwit scripts only, so that checking sigop and opcode limits of the policy script would not be necessary. There were a bunch of other small modifications, typo fixes, and optimizations that were made as well. I am now ready to submit these BIPs as a PR against the bitcoin/bips repo, and I request that the BIP editor assign numbers. Thank you, Mark Friedenbach > On Sep 6, 2017, at 5:38 PM, Mark Friedenbach wrote: > > I would like to propose two new script features to be added to the > bitcoin protocol by means of soft-fork activation. These features are > a new opcode, MERKLE-BRANCH-VERIFY (MBV) and tail-call execution > semantics. > > In brief summary, MERKLE-BRANCH-VERIFY allows script authors to force > redemption to use values selected from a pre-determined set committed > to in the scriptPubKey, but without requiring revelation of unused > elements in the set for both enhanced privacy and smaller script > sizes. Tail-call execution semantics allows a single level of > recursion into a subscript, providing properties similar to P2SH while > at the same time more flexible. > > These two features together are enough to enable a range of > applications such as tree signatures (minus Schnorr aggregation) as > described by Pieter Wuille [1], and a generalized MAST useful for > constructing private smart contracts. It also brings privacy and > fungibility improvements to users of counter-signing wallet/vault > services as unique redemption policies need only be revealed if/when > exceptional circumstances demand it, leaving most transactions looking > the same as any other MAST-enabled multi-sig script. > > I believe that the implementation of these features is simple enough, > and the use cases compelling enough that we could BIP 8/9 rollout of > these features in relatively short order, perhaps before the end of > the year. > > I have written three BIPs to describe these features, and their > associated implementation, for which I now invite public review and > discussion: > > Fast Merkle Trees > BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a > Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree > > MERKLEBRANCHVERIFY > BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431 > Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify > > Tail-call execution semantics > BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368 > Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics > > Note: I have circulated this idea privately among a few people, and I > will note that there is one piece of feedback which I agree with but > is not incorporated yet: there should be a multi-element MBV opcode > that allows verifying multiple items are extracted from a single > tree. It is not obvious how MBV could be modified to support this > without sacrificing important properties, or whether should be a > separate multi-MBV opcode instead. > > Kind regards, > Mark Friedenbach ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
(Subject was: [bitcoin-dev] Version 1 witness programs (first draft)), but I'm moving part of that conversation to this thread. On Sun, Oct 1, 2017 at 5:32 PM, Johnson Lau wrote: > 3. Do we want to allow static analysis of sigop? > BIP114 and the related proposals are specifically designed to allow static > analysis of sigop. I think this was one of the main reason of OP_EVAL not > being accepted. This was also the main reason of Ethereum failing to do a > DAO hacker softfork, leading to the ETH/ETC split. I’m not sure if we > really want to give up this property. Once we do it, we have to support it > forever. I would very much like to retain the ability to do static analysis. More generally, the idea of interpreting arbitrary data as code, as done in OP_EVAL and in TAILCALL, makes me quite anxious. This at the root of many security problems throughout the software industry, and I don't relish giving more fuel to the underhanded Bitcoin Script contestants. On Sun, Oct 1, 2017 at 8:45 PM, Luke Dashjr wrote: > > 3. Do we want to allow static analysis of sigop? > > BIP114 and the related proposals are specifically designed to allow > static > > analysis of sigop. I think this was one of the main reason of OP_EVAL not > > being accepted. This was also the main reason of Ethereum failing to do a > > DAO hacker softfork, leading to the ETH/ETC split. I’m not sure if we > > really want to give up this property. Once we do it, we have to support > it > > forever. > > It seems inevitable at this point. Maybe we could add a separate > "executable- > witness" array (in the same manner as the current witness was softforked > in), > and require tail-call and condition scripts to merely reference these by > hash, > but I'm not sure it's worth the effort? > > Thinking further, we could avoid adding a separate executable-witness > commitment by either: > A) Define that all the witness elements in v1 are type-tagged (put the > minor >witness version on them all, and redefine minor 0 as a stack item?); or > B) Use an empty element as a delimiter between stack and executable items. > > To avoid witness malleability, the executable items can be required to be > sorted in some manner. > > The downside of these approaches is that we now need an addition 20 or 32 > bytes per script reference... which IMO may possibly be worse than losing > static analysis. I wonder if there's a way to avoid that overhead? > Actually, I have a half-baked idea I've been thinking about along these lines. The idea is to add a flag to each stack item in the Script interpreter to mark whether the item in the stack is "executable" or "non-executable", not so different from how computers mark pages to implement executable space protection. By default, all stack items are marked "non-executable". We then redefine OP_PUSHDATA4 as OP_PUSHCODE within ScriptSigs. The operational semantics of OP_PUSHCODE would remain the same as OP_PUSHDATA4 except it would set the pushed item's associated flag to "executable". All data pushed by OP_PUSHCODE would be subject to the sigops limits and any other similar static analysis limits. Segwit v0 doesn't use OP_PUSHDATA codes to create the input stack, so we would have to mark executable input stack items using a new witness v1 format. But, IIUC, TAILCALL isn't going to be compatible with Segwit v0 anyway. During a TAILCALL, it is required that the top item on the stack have the "executable" flag, otherwise TAILCALL is not used (and the script succeeds or fails based on the top item's data value as usual). All other operations can treat "executable" items as data, including the merkle branch verification. None of the Script operations can create "executable" items; in particular, OP_PUSHDATA4 within the ScriptPubKey also would not create "executable" items. (We can talk about the behaviour of OP_CAT when that time comes). One last trick is that when "executable" values are duplicated, by OP_DUP, OP_IFDUP, OP_PICK. then the newly created copy of the value on top of the stack is marked "non-executable". Because we make the "executable" flag non-copyable, we are now free to allow unbounded uses of TAILCALL (i.e. TAILCALL can be used multiplie times in a single input). Why is this safe? Because the number of "executable" items decreases by at least one every time TAILCALL is invoked. the number of OP_PUSHCODE occurrences in the witness puts an upper bound on the number of invocations of TAILCALL allowed. Using static analysis of the script pubkey and the data within the OP_PUSHCODE data, we compute an upper bound on the number of operations (of any type) that can occur during execution. Unbounded TAILCALL should let us (in the presence of OP_CHECKSIGFROMSTACK) have unbounded delegation. Overall, I believe that OP_PUSHCODE 1. is fully backwards compatible. 2. maintains our ability to perform static analysis with TAILCALL. 3. never lets us interpret computed values as executable code. 4. extend
Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
10s of seconds if no further restrictions are placed. It would be trivial to include a new per input rule that reduces it to ~1s without cutting off any non-attack script (require sigops per input to be limited to witness/sig size). secp256k1 is now fast enough that we don’t need a separate sigop limit. > On Sep 30, 2017, at 4:23 PM, Luke Dashjr wrote: > > On Thursday 07 September 2017 12:38:55 AM Mark Friedenbach via bitcoin-dev > wrote: >> Tail-call execution semantics >> BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368 >> Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics > > Just noticed this doesn't count sigops toward the block sigop limit. > Is that really safe? How long would it take, to verify a malicious block with > only inputs such that there is nearly 4 MB of sigops? > > (I do already understand the difficulty in supporting the sigop limit.) > > Luke ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
On Thursday 07 September 2017 12:38:55 AM Mark Friedenbach via bitcoin-dev wrote: > Tail-call execution semantics > BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368 > Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics Just noticed this doesn't count sigops toward the block sigop limit. Is that really safe? How long would it take, to verify a malicious block with only inputs such that there is nearly 4 MB of sigops? (I do already understand the difficulty in supporting the sigop limit.) Luke ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
As some of you may know, the MAST proposal I sent to the mailing list on September 6th was discussed that the in-person CoreDev meetup in San Francisco. In this email I hope to summarize the outcome of that discussion. As chatham house rules were in effect, I will refrain from attributing names to this summary.. * An introductory overview of the BIPs was presented, for the purpose of familiarizing the audience with what they are attempting to accomplish and how they do so. * There was a discussion of a single vs multi-element MBV opcode. It was put forward that there should perhaps be different opcodes for the sake of script analysis, since a multi-element MBV will necessarily consume a variable number of inputs. However it was countered that if the script encodes the number of elements as an integer push to the top of the stack immediately before the opcode, then static analyzability is maintained in such instances. I took the action item to investigate what an ideal serialization format would be for a multi-element proof, which is the only thing holding back a multi-element MBV proposal. * It was pointed out that the non-clean-stack tail-call semantics is not compatible with segwit's consensus-enforcement of the clean stack rule. Some alternatives were suggested, such as changing deployment mechanisms. After the main discussion session it was observed that tail-call semantics could still be maintained if the alt stack is used for transferring arguments to the policy script. I will be updating the BIP and example implementation accordingly. * The observation was made that single-layer tail-call semantics can be thought of as really being P2SH with user-specified hashing. If the P2SH script template had been constructed slightly differently such as to not consume the script, it would even have been fully compatible with tail-call semantics. * It was mentioned that using script versioning to deploy a MAST template allows for saving 32 bytes of witness per input, as the root hash is contained directly in the output being spent. The downside however is losing the permissionless innovation that comes with a programmable hashing mechanism. * The discussion generally drifted into a wider discussion about script version upgrades and related issues, such as whether script versions should exist in the witness as well, and the difference in meaning between the two. This is an important subject, but only of relevance in far as using a script version upgrade to deploy MAST would add significant delay from having to sort through these issues first. This feedback led to some minor tweaks to the proposal, which I will be making, as well as the major feature request of a multi-element MERKLE-BLOCK-VERIFY opcode which requires a little bit more effort to accomplish. I will report back to this list again when that work is done. Sincerely, Mark Friedenbach ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
On Wed, Sep 13, 2017 at 08:27:36AM +0900, Karl Johan Alm via bitcoin-dev wrote: > On Wed, Sep 13, 2017 at 4:57 AM, Mark Friedenbach via bitcoin-dev > wrote: > >> Without the limit I think we would be DoS-ed to dead > > > > 4MB of secp256k1 signatures takes 10s to validate on my 5 year old > > laptop (125,000 signatures, ignoring public keys and other things that > > would consume space). That's much less than bad blocks that can be > > constructed using other vulnerabilities. > > Sidenote-ish, but I also believe it would be fairly trivial to keep a > per UTXO tally and demand additional fees when trying to respend a > UTXO which was previously "spent" with an invalid op count. I.e. if > you sign off on an input for a tx that you know is bad, the UTXO in > question will be penalized proportionately to the wasted ops when > included in another transaction later. That would probably kill that > DoS attack as the attacker would effectively lose bitcoin every time, > even if it was postponed until they spent the UTXO. The only thing > clients would need to do is to add a fee rate penalty ivar and a > mapping of outpoint to penalty value, probably stored as a separate > .dat file. I think. Ethereum does something quite like this; it's a very bad idea for a few reasons: 1) If you bailed out of verifying a script due to wasted ops, how did you know the transaction trying to spend that txout did in fact come from the owner of it? 2) How do you verify that transactions were penalized correctly without *all* nodes re-running the DoS script? 3) If the DoS is significant enough to matter on a per-node level, you're going to have serious problems anyway, quite possibly so serious that the attacker manages to cause consensus to fail. They can then spend the txouts in a block that does *not* penalize their outputs, negating the deterrent. -- https://petertodd.org 'peter'[:-1]@petertodd.org signature.asc Description: Digital signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
On Wed, Sep 13, 2017 at 4:57 AM, Mark Friedenbach via bitcoin-dev wrote: >> Without the limit I think we would be DoS-ed to dead > > 4MB of secp256k1 signatures takes 10s to validate on my 5 year old > laptop (125,000 signatures, ignoring public keys and other things that > would consume space). That's much less than bad blocks that can be > constructed using other vulnerabilities. Sidenote-ish, but I also believe it would be fairly trivial to keep a per UTXO tally and demand additional fees when trying to respend a UTXO which was previously "spent" with an invalid op count. I.e. if you sign off on an input for a tx that you know is bad, the UTXO in question will be penalized proportionately to the wasted ops when included in another transaction later. That would probably kill that DoS attack as the attacker would effectively lose bitcoin every time, even if it was postponed until they spent the UTXO. The only thing clients would need to do is to add a fee rate penalty ivar and a mapping of outpoint to penalty value, probably stored as a separate .dat file. I think. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
On Sep 12, 2017, at 1:55 AM, Johnson Lau wrote: > This is ugly and actually broken, as different script path may > require different number of stack items, so you don't know how many > OP_TOALTSTACK do you need. Easier to just use a new witness version DEPTH makes this relatively easy to do. Just repeat the following for the maximum number of stack elements that might be used: DEPTH 1SUB IF SWAP TOALTSTACK ENDIF There are probably more compact alternatives. Using a new script version is easier, but not faster. There's a number of things that might be fixed in a v1 upgrade, and various design decisions to sort out regarding specification of a witness version (version in the witness rather than the scriptPubKey). Tree signatures and MAST are immediately useful to many services, however, and I would hate to delay usage by six months to a year or more by serializing dependencies instead of doing them in parallel. > Otherwise, one could attack relay and mining nodes by sending many > small size txs with many sigops, forcing them to validate, and > discard due to insufficient fees. > > Technically it might be ok if we commit the total validation cost > (sigop + hashop + whatever) as the first witness stack item That is what I'm suggesting. And yes, there are changes that would have to be made to the p2p layer and transaction processing to handle this safely. I'm arguing that the cost of doing so is worth it, and a better path forward. > Without the limit I think we would be DoS-ed to dead 4MB of secp256k1 signatures takes 10s to validate on my 5 year old laptop (125,000 signatures, ignoring public keys and other things that would consume space). That's much less than bad blocks that can be constructed using other vulnerabilities. > So to make it functionally comparable with your proposal, the > IsMSV0Stack() function is not needed. The new 249-254 lines in > interpreter.cpp could be removed. The new 1480-1519 lines could be > replaced by a few lines copied from the existing P2WSH code. I can > make a minimal version if you want to see how it looks like That's alright, I don't think it's necessary to purposefully restrict one to compare them head to head with the same features. They are different proposals with different pros and cons. Kind regards, Mark Friedenbach ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
> On 12 Sep 2017, at 10:03 AM, Mark Friedenbach wrote: > > My apologies for a delay in responding to emails on this list; I have > been fighting a cold. > > (Also my apologies to Johnson Lau, as I forgot to forward this to the list.) > > On Sep 8, 2017, at 2:21 AM, Johnson Lau wrote: > >> Tail-call execution semantics require "unclean stake" , i.e. final >> stake with more than one item. However, "unclean stake" is invalid >> (not just non-standard) in BIP141, so you could only use it with >> legacy P2SH (which is totally pointless). A different design >> like OP_EVAL might be needed, or you need a new witness script >> version. > > I believe you meant "unclean stack," and you are correct. This was > also pointed out last tuesday by a participant at the in-person > CoreDev meetup where the idea was presented. > > This doesn't kill the idea, it just complicates the implementation > slightly. A simple fix would be to allow tail-recursion to occur if > the stack is not clean (as can happen with legacy P2SH as you point > out, or yet to be defined version 1+ forms of segwit script), OR if > there is a single item on the stack and the alt-stack is not empty. > For segwit v0 scripts you then have to move any arguments to the alt > stack before ending the redeem script, leaving just the policy script > on the main stack. This is ugly and actually broken, as different script path may require different number of stack items, so you don’t know how many OP_TOALTSTACK do you need. Easier to just use a new witness version > >> I think you have also missed the sigOp counting of the executed >> script. As you can't count it without executing the script, the >> current static analysability is lost. This was one of the reasons >> for OP_EVAL being rejected. Since sigOp is a per-block limit, any >> OP_EVAL-like operation means block validity will depend on the >> precise outcome of script execution (instead of just pass or fail), >> which is a layer violation. > > I disagree with this design requirement. > > The SigOp counting method used by bitcoin is flawed. It incorrectly > limits not the number of signature operations necessary to validate a > block, but rather the number of CHECKSIGs potentially encountered in > script execution, even if in an unexecuted branch. (Admitedly MAST > makes this less of an issue, but there are still useful compact > scripts that use if/else constructs to elide a CHECKSIG.) Nor will it > account for aggregation when that feature is added, or properly > differentiate between signature operations that can be batched and > those that can not. > > Additionally there are other resources used by script that should be > globally limited, such as hash operations, which are not accounted for > at this time and cannot be statically assessed, even by the flawed > mechanism by which SigOps are counted. I have maintained for some time > that bitcoin should move from having multiple separate global limits > (weight and sigops, hashed bytes in XT/Classic/BCH) to a single linear > metric that combines all of these factors with appropriate > coefficients. > I like the idea to have an unified global limit and suggested a way to do it (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-January/013472.html). But I think this is off-topic here. > A better way of handling this problem, which works for both SigOps and > HashOps, is to have the witness commit to the maximum resources > consumed by validation of the spend of the coin, to relay this data > with the transaction and include it in the SigHash, and to use the > committed maximum for block validation. This could be added in a > future script version upgrade. This change would also resolve the > issue that led to the clean stack rule in segwit, allowing future > versions of script to use tail-call recursion without involving the > alt-stack. > > Nevertheless it is constructive feedback that the current draft of the > BIP and its implementation do not count SigOps, at all. There are a > couple of ways this can be fixed by evaluating the top-level script > and then doing static analysis of the resulting policy script, or by > running the script and counting operations actually performed. In any case, I think maintaining static analysability for global limit(s) is very important. Ethereum had to give up their DAO softfork plan at the last minute, exactly due to the lack of this: http://hackingdistributed.com/2016/06/28/ethereum-soft-fork-dos-vector/ Otherwise, one could attack relay and mining nodes by sending many small size txs with many sigops, forcing them to validate, and discard due to insufficient fees. Technically it might be ok if we commit the total validation cost (sigop + hashop + whatever) as the first witness stack item, but that’d take more space and I’m not sure if it is desirable. Anyway, giving up static analysability for scripts is a fundamental change to our existing model. > > Additiona
Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
On Mon, Sep 11, 2017 at 9:03 PM, Mark Friedenbach via bitcoin-dev wrote: > I believe you meant "unclean stack," and you are correct. This was > also pointed out last tuesday by a participant at the in-person > CoreDev meetup where the idea was presented. http://diyhpl.us/wiki/transcripts/bitcoin-core-dev-tech/2017-09-07-merkleized-abstract-syntax-trees/ > > For code complexity, the minimal BIP114 could be really simple, like > > <30 lines of code? It looks complex now because it does much more > > than simply hiding scripts in a hash. > > Is there a repo that contains the latest implementation of BIP 114, > for comparison purposes? original bip114: https://github.com/bitcoin/bips/blob/775f26c02696e772dac4060aa092d35dedbc647c/bip-0114.mediawiki revised bip114: https://github.com/jl2012/bips/blob/vault/bip-0114.mediawiki https://github.com/jl2012/bitcoin/commits/vault from https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014963.html - Bryan http://heybryan.org/ 1 512 203 0507 ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
My apologies for a delay in responding to emails on this list; I have been fighting a cold. (Also my apologies to Johnson Lau, as I forgot to forward this to the list.) On Sep 8, 2017, at 2:21 AM, Johnson Lau wrote: > Tail-call execution semantics require "unclean stake" , i.e. final > stake with more than one item. However, "unclean stake" is invalid > (not just non-standard) in BIP141, so you could only use it with > legacy P2SH (which is totally pointless). A different design > like OP_EVAL might be needed, or you need a new witness script > version. I believe you meant "unclean stack," and you are correct. This was also pointed out last tuesday by a participant at the in-person CoreDev meetup where the idea was presented. This doesn't kill the idea, it just complicates the implementation slightly. A simple fix would be to allow tail-recursion to occur if the stack is not clean (as can happen with legacy P2SH as you point out, or yet to be defined version 1+ forms of segwit script), OR if there is a single item on the stack and the alt-stack is not empty. For segwit v0 scripts you then have to move any arguments to the alt stack before ending the redeem script, leaving just the policy script on the main stack. > I think you have also missed the sigOp counting of the executed > script. As you can't count it without executing the script, the > current static analysability is lost. This was one of the reasons > for OP_EVAL being rejected. Since sigOp is a per-block limit, any > OP_EVAL-like operation means block validity will depend on the > precise outcome of script execution (instead of just pass or fail), > which is a layer violation. I disagree with this design requirement. The SigOp counting method used by bitcoin is flawed. It incorrectly limits not the number of signature operations necessary to validate a block, but rather the number of CHECKSIGs potentially encountered in script execution, even if in an unexecuted branch. (Admitedly MAST makes this less of an issue, but there are still useful compact scripts that use if/else constructs to elide a CHECKSIG.) Nor will it account for aggregation when that feature is added, or properly differentiate between signature operations that can be batched and those that can not. Additionally there are other resources used by script that should be globally limited, such as hash operations, which are not accounted for at this time and cannot be statically assessed, even by the flawed mechanism by which SigOps are counted. I have maintained for some time that bitcoin should move from having multiple separate global limits (weight and sigops, hashed bytes in XT/Classic/BCH) to a single linear metric that combines all of these factors with appropriate coefficients. A better way of handling this problem, which works for both SigOps and HashOps, is to have the witness commit to the maximum resources consumed by validation of the spend of the coin, to relay this data with the transaction and include it in the SigHash, and to use the committed maximum for block validation. This could be added in a future script version upgrade. This change would also resolve the issue that led to the clean stack rule in segwit, allowing future versions of script to use tail-call recursion without involving the alt-stack. Nevertheless it is constructive feedback that the current draft of the BIP and its implementation do not count SigOps, at all. There are a couple of ways this can be fixed by evaluating the top-level script and then doing static analysis of the resulting policy script, or by running the script and counting operations actually performed. Additionally, it is possible that we take this time to re-evaluate whether we should be counting SigOps other than for legacy consensus rule compliance. The speed of verification in secp256k1 has made signature operations no longer the chief concern in block validation times. > Witness script versioning is by design fully compatible with P2SH > and BIP173, so there will be no hurdle for existing wallets to pay > to BIP114. Actually it should be completely transparent to them. This is correct. Your feedback will be incorporated. > For code complexity, the minimal BIP114 could be really simple, like > <30 lines of code? It looks complex now because it does much more > than simply hiding scripts in a hash. Is there a repo that contains the latest implementation of BIP 114, for comparison purposes? Kind regards, Mark Friedenbach ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
Coincidentally, the kind of Merkle tree that Mark describes in his proposal is exactly the one that we use at Stampery. The Stampery BTA whitepaper[1] includes pseudocode for many of the algorithms outlined by this proposal, including fast-SHA256, the tree building process and the inclusion proving routine. The wording is slightly different but the logic is just the same, so I hope it helps future implementations in case of eventual adoption. [1] https://s3.amazonaws.com/stampery-cdn/docs/Stampery-BTA-v6-whitepaper.pdf Best, -- Adán Sánchez de Pedro Crespo CTO, Stampery Inc. San Francisco - Madrid T: +34 663 163 375 signature.asc Description: OpenPGP digital signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
Some comments with the tail-call execution semantics BIP: Tail-call execution semantics require “unclean stake”, i.e. final stake with more than one item. However, “unclean stake” is invalid (not just non-standard) in BIP141, so you could only use it with legacy P2SH (which is totally pointless….). A different design like OP_EVAL might be needed, or you need a new witness script version. I think you have also missed the sigOp counting of the executed script. As you can’t count it without executing the script, the current static analysability is lost. This was one of the reasons for OP_EVAL being rejected. Since sigOp is a per-block limit, any OP_EVAL-like operation means block validity will depend on the precise outcome of script execution (instead of just pass or fail), which is a layer violation. (An alternative is to make sigOp a per-input limit instead of per-block limit, just like the 201 nOp limit. But this is a very different security model) Witness script versioning is by design fully compatible with P2SH and BIP173, so there will be no hurdle for existing wallets to pay to BIP114. Actually it should be completely transparent to them. For code complexity, the minimal BIP114 could be really simple, like <30 lines of code? It looks complex now because it does much more than simply hiding scripts in a hash. > On 7 Sep 2017, at 8:38 AM, Mark Friedenbach via bitcoin-dev > wrote: > > I would like to propose two new script features to be added to the > bitcoin protocol by means of soft-fork activation. These features are > a new opcode, MERKLE-BRANCH-VERIFY (MBV) and tail-call execution > semantics. > > In brief summary, MERKLE-BRANCH-VERIFY allows script authors to force > redemption to use values selected from a pre-determined set committed > to in the scriptPubKey, but without requiring revelation of unused > elements in the set for both enhanced privacy and smaller script > sizes. Tail-call execution semantics allows a single level of > recursion into a subscript, providing properties similar to P2SH while > at the same time more flexible. > > These two features together are enough to enable a range of > applications such as tree signatures (minus Schnorr aggregation) as > described by Pieter Wuille [1], and a generalized MAST useful for > constructing private smart contracts. It also brings privacy and > fungibility improvements to users of counter-signing wallet/vault > services as unique redemption policies need only be revealed if/when > exceptional circumstances demand it, leaving most transactions looking > the same as any other MAST-enabled multi-sig script. > > I believe that the implementation of these features is simple enough, > and the use cases compelling enough that we could BIP 8/9 rollout of > these features in relatively short order, perhaps before the end of > the year. > > I have written three BIPs to describe these features, and their > associated implementation, for which I now invite public review and > discussion: > > Fast Merkle Trees > BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a > Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree > > MERKLEBRANCHVERIFY > BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431 > Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify > > Tail-call execution semantics > BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368 > Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics > > Note: I have circulated this idea privately among a few people, and I > will note that there is one piece of feedback which I agree with but > is not incorporated yet: there should be a multi-element MBV opcode > that allows verifying multiple items are extracted from a single > tree. It is not obvious how MBV could be modified to support this > without sacrificing important properties, or whether should be a > separate multi-MBV opcode instead. > > Kind regards, > Mark Friedenbach > ___ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
[bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
I would like to propose two new script features to be added to the bitcoin protocol by means of soft-fork activation. These features are a new opcode, MERKLE-BRANCH-VERIFY (MBV) and tail-call execution semantics. In brief summary, MERKLE-BRANCH-VERIFY allows script authors to force redemption to use values selected from a pre-determined set committed to in the scriptPubKey, but without requiring revelation of unused elements in the set for both enhanced privacy and smaller script sizes. Tail-call execution semantics allows a single level of recursion into a subscript, providing properties similar to P2SH while at the same time more flexible. These two features together are enough to enable a range of applications such as tree signatures (minus Schnorr aggregation) as described by Pieter Wuille [1], and a generalized MAST useful for constructing private smart contracts. It also brings privacy and fungibility improvements to users of counter-signing wallet/vault services as unique redemption policies need only be revealed if/when exceptional circumstances demand it, leaving most transactions looking the same as any other MAST-enabled multi-sig script. I believe that the implementation of these features is simple enough, and the use cases compelling enough that we could BIP 8/9 rollout of these features in relatively short order, perhaps before the end of the year. I have written three BIPs to describe these features, and their associated implementation, for which I now invite public review and discussion: Fast Merkle Trees BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree MERKLEBRANCHVERIFY BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431 Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify Tail-call execution semantics BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368 Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics Note: I have circulated this idea privately among a few people, and I will note that there is one piece of feedback which I agree with but is not incorporated yet: there should be a multi-element MBV opcode that allows verifying multiple items are extracted from a single tree. It is not obvious how MBV could be modified to support this without sacrificing important properties, or whether should be a separate multi-MBV opcode instead. Kind regards, Mark Friedenbach ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev