Discussion:
BIP 117 Feedback
(too old to reply)
Rusty Russell via bitcoin-dev
2018-01-09 11:22:18 UTC
Permalink
I've just re-read BIP 117, and I'm concerned about its flexibility. It
seems to be doing too much.

The use of altstack is awkward, and makes me query this entire approach.
I understand that CLEANSTACK painted us into a corner here :(

The simplest implementation of tail recursion would be a single blob: if
a single element is left on the altstack, pop and execute it. That
seems trivial to specify. The treatment of concatenation seems like
trying to run before we can walk.

Note that if we restrict this for a specific tx version, we can gain
experience first and get fancier later.

BIP 117 also drops SIGOP and opcode limits. This requires more
justification, in particular, measurements and bounds on execution
times. If this analysis has been done, I'm not aware of it.

We could restore statically analyzability by rules like so:
1. Only applied for tx version 3 segwit txs.
2. For version 3, top element of stack is counted for limits (perhaps
with discount).
3. The blob popped off for tail recursion must be identical to that top
element of the stack (ie. the one counted above).

Again, future tx versions could drop such restrictions.

Cheers,
Rusty.
Mark Friedenbach via bitcoin-dev
2018-01-09 12:40:30 UTC
Permalink
The use of the alt stack is a hack for segwit script version 0 which has the clean stack rule. Anticipated future improvements here are to switch to a witness script version, and a new segwit output version which supports native MAST to save an additional 40 or so witness bytes. Either approach would allow getting rid of the alt stack hack. They are not part of the proposal now because it is better to do things incrementally, and because we anticipate usage of MAST to better inform these less generic changes.

Your suggestion of “single blob on the stack” seems to be exactly this proposal afaict? Note the witness data needs to be passed separately because signatures can’t be included in that single blob if that blob is hashed and compared against something in the scriptPubKey.

The sigop and opcode limit drop can be justified with some back of the envelope calculations. Non-scriptPubKey scripts are fundamentally limited by blocksize/weight and the most damage you can do, as an adversary, is limited by space. The most expensive thing you can do check a signature. Our assumptions about block size safety are basically due to how much computation you can stuff in a block with checksigs — all the analysis there applies.

My suggestion is to limit the number of checksigs allowed in a script to size(script+witness)/64, but I wanted this to come up in review rather than complicate the code right off the bat.

I will make a strong assertion: static analyzing the number of opcodes and sigops gets us absolutely nothing. It is cargo cult safety engineering. No need to perpetuate it when it is now in the way.

Sent from my iPhone
Post by Rusty Russell via bitcoin-dev
I've just re-read BIP 117, and I'm concerned about its flexibility. It
seems to be doing too much.
The use of altstack is awkward, and makes me query this entire approach.
I understand that CLEANSTACK painted us into a corner here :(
The simplest implementation of tail recursion would be a single blob: if
a single element is left on the altstack, pop and execute it. That
seems trivial to specify. The treatment of concatenation seems like
trying to run before we can walk.
Note that if we restrict this for a specific tx version, we can gain
experience first and get fancier later.
BIP 117 also drops SIGOP and opcode limits. This requires more
justification, in particular, measurements and bounds on execution
times. If this analysis has been done, I'm not aware of it.
1. Only applied for tx version 3 segwit txs.
2. For version 3, top element of stack is counted for limits (perhaps
with discount).
3. The blob popped off for tail recursion must be identical to that top
element of the stack (ie. the one counted above).
Again, future tx versions could drop such restrictions.
Cheers,
Rusty.
Pieter Wuille via bitcoin-dev
2018-01-09 14:21:08 UTC
Permalink
On Jan 9, 2018 13:41, "Mark Friedenbach via bitcoin-dev" <
bitcoin-***@lists.linuxfoundation.org> wrote:

The use of the alt stack is a hack for segwit script version 0 which has
the clean stack rule. Anticipated future improvements here are to switch to
a witness script version, and a new segwit output version which supports
native MAST to save an additional 40 or so witness bytes. Either approach
would allow getting rid of the alt stack hack. They are not part of the
proposal now because it is better to do things incrementally, and because
we anticipate usage of MAST to better inform these less generic changes.


If the goal is to introduce a native MAST output type later, what is gained
by first having the tailcall semantics?

As far as I can see, this proposal does not have any benefits over Johnson
Lau's MAST idea [1]:
* It is more compact, already giving us the space savings a native MAST
version of the tail call semantics would bring.
* It does not need to work around limitations of push size limits or
cleanstack rules.
* The implementation (of code I've seen) is easier to reason about, as it's
just another case in VerifyScript (which you'd need for a native MAST
output later too) without introducing jumps or loops inside EvalScript.
* It can express the same, as even though the MBV opcode supports proving
multiple elements simultaneously, I don't see a way to use that in the tail
call. Every scenario that consists of some logic before deciding what the
tail call is going to be can be rewritten to have that logic inside each of
the branches, I believe.
* It does not interfere with static analysis (see further).
* Tail call semantics may be easier to extend in the future to enable
semantics that are not compactly representable in either proposal right
now, by allowing a single top-level script may invoke multiple subscripts,
or recursion. However, those sound even riskier and harder to analyse to
me, and I don't think there is sufficient evidence they're needed.

Native MAST outputs would need a new witness script version, which your
current proposal does indeed not need. However, I believe a new script
version will be desirable for other reasons regardless (returning invalid
opcodes to the pool of NOPs available for softforks, for example).

I will make a strong assertion: static analyzing the number of opcodes and
sigops gets us absolutely nothing. It is cargo cult safety engineering. No
need to perpetuate it when it is now in the way.


I'm not sure I agree here. While I'd like to see the separate execution
limits go away, removing them entirely and complicating future ability to
introduce unified costing towards weight of execution cost seems the wrong
way to go.

My reasoning is this: perhaps you can currently make an argument that the
current weight limit is sufficient in preventing overly expensive block
validation costs, due to a minimal ratio between script sizes and their
execution cost. But such an argument needs to rely on assumptions about
sighash caching and low per-opcode CPU time, which may change in the
future. In my view, tail call semantics gratuitously remove or complicate
the ability to reason about the executed code.

One suggestion to reduce the impact of this is limiting the per-script
execution to something proportional to the script size. However, I don't
think that addresses all potential concerns about static analysis (for
example, it doesn't easily let you prove all possible execution paths to a
participant in a smart contract).

Another idea that has been suggested on this list is to mark pushes of
potentially executable code on the stack/witness explicitly. This would
retain all ability to analyse, while still leaving the flexibility of
future extensions to tail call execution. If tail call semantics are
adopted, I strongly prefer an approach like that to blindly throwing out
all limits and analysis.

[1] https://github.com/jl2012/bips/blob/mast/bip-mast.mediawiki

Cheers,
--
Pieter
Mark Friedenbach via bitcoin-dev
2018-01-09 22:57:34 UTC
Permalink
I havent the hubris to suggest that we know exactly what a templated MAST *should* look like. It's not used in production anywhere. Even if we did have the foresight, the tail-call semantics allow for other constructions besides MAST and for the sake of the future we should allow such permission-less innovation. The proper sequence of events should be to enable features in a generic way, and then to create specialized templates to save space for common constructions. Not the other way around.

We've been down the route of templating new features, and have made mistakes. P2SH is a canonical example, which BIP 117 is fixing. P2SH only provides 80 bits of security to a multi-party construction. Had we been designing BIP 16 now we probably would have used double-SHA256 instead of RIPEMD160. I will also assert that had we been using single-use tail-call semantics *instead* of BIP 16, recognition of this limitation would have resulted in us immediately defining a longer '3...' address which used HASH256 instead, and we would have immediately benefited from the fix. Instead we had to wait years until segwit gave us the opportunity to fix it at the same time.

To take another example, in some ideal sense we probably shouldn't even be developing a programmable signature script framework. We should instead template a generic lightning-derived layer-2 protocol and use that for everything, including both payments (supporting cut-through) and payment channels for smart contracts. This may not be the majority technical opinion yet, but as someone working in this space I believe that's where we are headed: a single layer-2 protocol that's generic enough to use for all payment caching and smart contracts, while achieving a full anonymity set for all contracts, as closures look identical on the wire. Even if that's where things are headed, I hope it is clear that we are not yet at such a stage to standardize what that looks like. We still need many years of use of specialized lightning protocols and work to be done to make them more generic and applicable to other protocols.

I believe the situation to be similar with MAST. Even if we have a better idea of what the MAST constructions will look like, *nobody* uses MAST in production yet, and there are bound to be implementation issues in rolling it out, or unique variants we do not have the foresight to see now. As a concrete example, BIP 116 has been modified since the initial proposal to allow multiple branches to be proven at once from a single Merkle tree root. To be honest, I don't know exactly how this will be used. We were able to come up with a couple of examples to justify inclusion of the feature, but I anticipate that someone down the line will come up with an even more creative use. Maybe a payment channel that uses a single tree to simultaneously commit to both the policy script and a sequence number. Or something like that. If we provide a templated, special-cased MAST now before it sees wide use then we will be locking in the protocol that we anticipate people using without having any production experience or ecosystem-wide review. Frankly that strikes me as a poor engineering decision.

Finally, even if we had perfect foresight into how a feature will be used, which we don't, it is still the case that we would want to enable permission-less innovation with the generic construct, even if using it comes with a 40-byte or so witness hit. I make the argument for this in the "intuitive explanation of MAST" email I sent to this list back in September of last year. I will reproduce the argument below:

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015028.html

The driving motivation for the tail-call and MBV proposals, and the reason they are presented and considered together is to enable Merklized Abstract Syntax Trees. However neither BIP actually defines a MAST template, except as an example use case of the primitive features. This is very much on purpose: it is the opinion of this author that new bitcoin consensus features should follow the UNIX philosophy as expressed by Peter Salus and Mike Gancarz and paraphrased by yours truly:

* Write features that do one thing and do it well.
* Write features to work together.
* Simple is beautiful.

By using modularity and composition of powerful but simple tools like MERKLEBRANCHVERIFY and single tail-call recursion to construct MAST we enable a complex and desirable feature while minimizing changes to the consensus code, review burden, and acquired technical debt.

The reusability of the underlying primitives also means that they can be combined with other modular features to support use cases other than vanilla MAST, or reused in series to work around various limits that might otherwise be imposed on a templated form of MAST. At the moment the chief utility of these proposals is the straightforward MAST script written above, but as primitives they do allow a few other use cases and also combine well with features in the pipeline or on
the drawing board. For example, in addition to MAST you can:

1. Use MERKLEBRANCHVERIFY alone to support honeypot bounties, as
discussed in the BIP.

2. Use a series of MERKLEBRANCHVERIFY opcodes to verify a branch with
split proofs to stay under script and witness push limitations.

3. Combine MERKLEBRANCHVERIFY with key aggregation to get
Wuille-Maxwell tree signatures which support arbitrary signing
policies using a single, aggregatable signature.

4. Combine tail-call execution semantics with CHECKSIGFROMSTACK to get
delegation and signature-time commitment to subscript policy.

5. Combine MERKLEBRANCHVERIFY with a Merkle proof prefix check opcode
and Lamport signature support to get reusable Lamport keys.

I believe these benefits and possible future expansions to be strong arguments in favor of extending bitcoin in the form of small, modular, incremental, and reusable changes that can be combined and used even in ways unforeseen even by their creators, creating a platform for unrestricted innovation.

The alternative approach of rigid templates achieves the stated goals, perhaps even with slightly better encoding efficiency, but at the cost of requiring workaround for each future innovation. P2SH is just such an example -- we couldn't even upgrade to 128-bit security without designing an entirely different implementation because of the limitations of template pattern matching.
Post by Mark Friedenbach via bitcoin-dev
The use of the alt stack is a hack for segwit script version 0 which has the clean stack rule. Anticipated future improvements here are to switch to a witness script version, and a new segwit output version which supports native MAST to save an additional 40 or so witness bytes. Either approach would allow getting rid of the alt stack hack. They are not part of the proposal now because it is better to do things incrementally, and because we anticipate usage of MAST to better inform these less generic changes.
If the goal is to introduce a native MAST output type later, what is gained by first having the tailcall semantics?
* It is more compact, already giving us the space savings a native MAST version of the tail call semantics would bring.
* It does not need to work around limitations of push size limits or cleanstack rules.
* The implementation (of code I've seen) is easier to reason about, as it's just another case in VerifyScript (which you'd need for a native MAST output later too) without introducing jumps or loops inside EvalScript.
* It can express the same, as even though the MBV opcode supports proving multiple elements simultaneously, I don't see a way to use that in the tail call. Every scenario that consists of some logic before deciding what the tail call is going to be can be rewritten to have that logic inside each of the branches, I believe.
* It does not interfere with static analysis (see further).
* Tail call semantics may be easier to extend in the future to enable semantics that are not compactly representable in either proposal right now, by allowing a single top-level script may invoke multiple subscripts, or recursion. However, those sound even riskier and harder to analyse to me, and I don't think there is sufficient evidence they're needed.
Native MAST outputs would need a new witness script version, which your current proposal does indeed not need. However, I believe a new script version will be desirable for other reasons regardless (returning invalid opcodes to the pool of NOPs available for softforks, for example).
I will make a strong assertion: static analyzing the number of opcodes and sigops gets us absolutely nothing. It is cargo cult safety engineering. No need to perpetuate it when it is now in the way.
I'm not sure I agree here. While I'd like to see the separate execution limits go away, removing them entirely and complicating future ability to introduce unified costing towards weight of execution cost seems the wrong way to go.
My reasoning is this: perhaps you can currently make an argument that the current weight limit is sufficient in preventing overly expensive block validation costs, due to a minimal ratio between script sizes and their execution cost. But such an argument needs to rely on assumptions about sighash caching and low per-opcode CPU time, which may change in the future. In my view, tail call semantics gratuitously remove or complicate the ability to reason about the executed code.
One suggestion to reduce the impact of this is limiting the per-script execution to something proportional to the script size. However, I don't think that addresses all potential concerns about static analysis (for example, it doesn't easily let you prove all possible execution paths to a participant in a smart contract).
Another idea that has been suggested on this list is to mark pushes of potentially executable code on the stack/witness explicitly. This would retain all ability to analyse, while still leaving the flexibility of future extensions to tail call execution. If tail call semantics are adopted, I strongly prefer an approach like that to blindly throwing out all limits and analysis.
[1] https://github.com/jl2012/bips/blob/mast/bip-mast.mediawiki <https://github.com/jl2012/bips/blob/mast/bip-mast.mediawiki>
Cheers,
--
Pieter
Russell O'Connor via bitcoin-dev
2018-01-12 10:48:33 UTC
Permalink
Putting aside for the moment the concerns that Pieter and Rusty have raised
about BIP 117 (concerns which I agree with), is BIP 117 even a viable soft
fork to begin with?

When it comes to soft forks of Script, in the past there have been two
kinds.

The first kind is soft-forking new script semantics into NOPn codes. In
this case, everyone ought to know that these op codes are reserved for
future extensions and no one should be writing script that depends on NOPn
having NOP behavior (For users who want real nop behaviour, there does
exist a real NOP opcode).

The second kind of soft-forking new script semantics is the
reinterpretation of various wholesale scripts (historically via
templates). Examples of this are Segwit and P2SH. In the case of Segwit,
the scripts gaining new semantics were applied to a form of completely
unsecured "anyone-can-spend" programs. Anyone who created such output
prior to the activation of Segwit would know that anyone could claim
ownership of those outputs, and therefore the possibility of losing the
ability to spend legacy forms of these segwit-style outputs is arguably not
harmful as no one in particular had ownership of such funds. The story for
P2SH is somewhat similar: Prior to the activation of P2SH the creator of of
P2SH style outputs would know that anyone could claim ownership of that
style of output as soon as the hash preimage is published (in the mempool,
for example).

However, if I understand correctly, the situation for BIP 117 is entirely
different. As far as I understand there is currently no restrictions about
terminating a v0 witness program with a non-empty alt-stack, and there are
no restrictions on leaving non-canonical boolean values on the main stack.
There could already be commitments to V0 witness programs that, when
executed in some reasonable context, leave a non-empty alt-stack and/or
leave a non-canonical true value on the main stack. Unlike the P2SH or
Segwit soft-forks, these existing commitments could be real outputs that
currently confer non-trivial ownership over their associated funds. If BIP
117 were activated, these commitments would be subject to a new set of
rules that didn't exist when the commitments were made. In particular,
these funds could be rendered unspendable. Because segwit commitments are
hashes of segwit programs, there is no way to even analyze the blockchain
to determine if these commitments currently exist (and even if we could it
probably woudln't be adequate protection).

Naturally we shouldn't be making new rules that could, in principle,
retroactively remove ownership of existing user's funds.
Rusty Russell via bitcoin-dev
2018-01-16 01:06:14 UTC
Permalink
Post by Russell O'Connor via bitcoin-dev
However, if I understand correctly, the situation for BIP 117 is entirely
different. As far as I understand there is currently no restrictions about
terminating a v0 witness program with a non-empty alt-stack, and there are
no restrictions on leaving non-canonical boolean values on the main stack.
BIP-141: "The script must not fail, and result in exactly a single TRUE
on the stack." And it has long been non-standard for P2SH scripts to
not do the same (don't know exactly when).
Post by Russell O'Connor via bitcoin-dev
There could already be commitments to V0 witness programs that, when
executed in some reasonable context, leave a non-empty alt-stack and/or
leave a non-canonical true value on the main stack. Unlike the P2SH or
Segwit soft-forks, these existing commitments could be real outputs that
currently confer non-trivial ownership over their associated funds. If BIP
117 were activated, these commitments would be subject to a new set of
rules that didn't exist when the commitments were made. In particular,
these funds could be rendered unspendable. Because segwit commitments are
hashes of segwit programs, there is no way to even analyze the blockchain
to determine if these commitments currently exist (and even if we could it
probably woudln't be adequate protection).
The rule AFAICT is "standard transactions must still work". This was
violated with low-S, but the transformation was arguably trivial.

OTOH, use of altstack is completely standard, though in practice it's
unused and so only a theoretical concern.

My concern remains unanswered: I want hard numbers on the worst-case
time taken by sigops with the limit removed. It's about 120 usec per
sigop (from [1]), so how bad could it be? I think Russell had an
estimate like 1 in 3 ops, so 160 seconds to validate a block?

Thanks,
Rusty.
[1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015346.html
Gregory Maxwell via bitcoin-dev
2018-01-16 03:27:26 UTC
Permalink
On Tue, Jan 16, 2018 at 1:06 AM, Rusty Russell via bitcoin-dev
Post by Rusty Russell via bitcoin-dev
The rule AFAICT is "standard transactions must still work". This was
violated with low-S, but the transformation was arguably trivial.
That is my view, generally. Like any other principle, its
applicability is modulated by the specific facts.

For low-s the most critical mitigating specific facts were (in order
of importance): Any third party could malleate non-conforming
transactions to make them conform and that code to do this was written
and run, that S-value malleation was being actively attacked at the
time, and that the intention to eventually enforce lowS had been made
clear a long time ahead and the vast majority of transactions were
already conforming.

In particular these facts meant that the change could not result in
the confiscation of funds except in the case of a key-destroyed
unconfirmed chain of timelock transactions which was already highly
vulnerable due to the malleation attacks -- and even there, the
non-standardness step itself wouldn't destroy the funds esp. given the
malleation risk redemption of that sort of chain would probably be
best accomplished with the collaboration of a miner.
Luke Dashjr via bitcoin-dev
2018-01-16 04:15:54 UTC
Permalink
Post by Rusty Russell via bitcoin-dev
Post by Russell O'Connor via bitcoin-dev
However, if I understand correctly, the situation for BIP 117 is entirely
different. As far as I understand there is currently no restrictions
about terminating a v0 witness program with a non-empty alt-stack, and
there are no restrictions on leaving non-canonical boolean values on the
main stack.
BIP-141: "The script must not fail, and result in exactly a single TRUE
on the stack." And it has long been non-standard for P2SH scripts to
not do the same (don't know exactly when).
This doesn't affect the alt-stack (it's a completely separate stack).
Post by Rusty Russell via bitcoin-dev
The rule AFAICT is "standard transactions must still work". This was
violated with low-S, but the transformation was arguably trivial.
OTOH, use of altstack is completely standard, though in practice it's
unused and so only a theoretical concern.
I'm not aware of a single standard/BIP that uses the altstack at all.

Luke
Russell O'Connor via bitcoin-dev
2018-01-16 08:39:28 UTC
Permalink
Post by Luke Dashjr via bitcoin-dev
Post by Rusty Russell via bitcoin-dev
The rule AFAICT is "standard transactions must still work". This was
violated with low-S, but the transformation was arguably trivial.
OTOH, use of altstack is completely standard, though in practice it's
unused and so only a theoretical concern.
I'm not aware of a single standard/BIP that uses the altstack at all.
By "standard transaction" here, Rusty means that (P2SH or Segwit) scripts
that use the alt-stack pass the standardness checks and will be relayed by
recent Bitcoin Core software.

----

Regarding lowS: I think the more severe standardness change was the added
requirement that (some of the) pubkeys in a multisig must be parsable. I
have talked with people who cannot retrieve their funds now, when before
they could. However, like lowS, this was only a change to the standardness
rules and not a consensus change, so these funds are not necessarily
permanently lost. They can be retrieved with miner help.

I don't see how BIP 117, which is a change in consensus rules that could
cause permanent loss of otherwise well-secured funds (in addition to the
other issues raised about BIP 117), is even comparable to the previous
changes in only the standardness rules.
Johnson Lau via bitcoin-dev
2018-03-05 15:28:20 UTC
Permalink
Altstack in v0 P2WSH should be left untouched. If anyone is already using altstack, BIP117 would very likely confiscate those UTXOs because the altstack would unlikely be executable.

Even in v1 witness, I think altstack should remain be a temporary data storage.

The “(many scripts) concatinated together in reverse order to form a serialized script” in BIP117 is exactly the same security hole of Satoshi’s scriptSig + OP_CODESAPARATOR + scriptPubKey . That means it is possible to skip execution of scriptPubKey by using a scriptSig with an invalid push operation, so the whole concatenated script becomes a simple push.

For SigOp limit, I think it’d become more and more difficult to maintain the current statical analyzability model as we try to introduce more functions. I think we should just migrate to a model of limiting sigop per weight, and count the actual number of sigop during execution. ( https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015764.html ) Actually, this approach is cheaper to analyse, as you only need to look at the witness size, and don’t need to look at the script at all.
Post by Rusty Russell via bitcoin-dev
I've just re-read BIP 117, and I'm concerned about its flexibility. It
seems to be doing too much.
The use of altstack is awkward, and makes me query this entire approach.
I understand that CLEANSTACK painted us into a corner here :(
The simplest implementation of tail recursion would be a single blob: if
a single element is left on the altstack, pop and execute it. That
seems trivial to specify. The treatment of concatenation seems like
trying to run before we can walk.
Note that if we restrict this for a specific tx version, we can gain
experience first and get fancier later.
BIP 117 also drops SIGOP and opcode limits. This requires more
justification, in particular, measurements and bounds on execution
times. If this analysis has been done, I'm not aware of it.
1. Only applied for tx version 3 segwit txs.
2. For version 3, top element of stack is counted for limits (perhaps
with discount).
3. The blob popped off for tail recursion must be identical to that top
element of the stack (ie. the one counted above).
Again, future tx versions could drop such restrictions.
Cheers,
Rusty.
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Loading...