[bitcoin-dev] Continuing the discussion about noinput / anyprevout

[bitcoin-dev] Continuing the discussion about noinput / anyprevout

[Christian Decker]

With the recently renewed interest in eltoo, a proof-of-concept implementation
[1], and the discussions regarding clean abstractions for off-chain protocols
[2,3], I thought it might be time to revisit the `sighash_noinput` proposal
(BIP-118 [4]), and AJ's `bip-anyprevout` proposal [5].

(sorry for the long e-mail. I wanted to give enough context and describe the
various tradeoffs so people don't have to stitch them together from memory. If
you're impatient there are a couple of open questions at the bottom)

Both proposals are ways to allow rebinding of transactions to new outputs, by
adding a sighash flag that excludes the output when signing. This allows the
transaction to be bound to any output, without needing a new signature, as
long as output script and input script are compatible, e.g., the signature
matches the public key specified in the output.

BIP-118 is limited to explaining the details of signature verification, and
omits anything related to deployment and dependency on other proposals. This
was done in order not to depend on bip-taproot which is also in draft-phase
currently, and to allow deployment alongside the next version of segwit
script. `bip-anyprevout` builds on top of BIP-118, adding integration with
`bip-taproot`, chaperone signatures, limits the use of the sighash flag to
script path spends, as well as a new pubkey serialization which uses the first
byte to signal opt-in.

I'd like to stress that both proposals are complementary and not competing,
which is something that I've heard a couple of times.

There remain a couple of unclear points which I hope we can address in the
coming days, to get this thing moving again, and hopefully get a new tool in
our toolbox soon(ish).

In the following I will quote a couple of things that were discussed during
the CoreDev meeting earlier this year, but not everybody could join, and it is
important that we engage the wider community, to get a better picture, and I
think not everybody is up-to-date about the current state.


## Dangers of `sighash_noinput`

An argument I have heard against noinput is that it is slightly less complex
or compute intensive than `sighash_all` signatures, which may encourage wallet
creators to only implement the noinput variant, and use it indiscrimi-
nately. This is certainly a good argument, and indeed we have seen at least
one developer proposing to use noinput for all transactions to discourage
address reuse.

This was also mentioned at CoreDev [6]:

> When [...] said he wanted to write a wallet that only used SIGHASH\_NOINPUT,
> that was pause for concern. Some people might want to use SIGHASH\_NOINPUT as a
> way to cheapen or reduce the complexity of making a wallet
> implementation. SIGHASH\_NOINPUT is from a purely procedural point of view
> easier than doing a SIGHASH\_ALL, that's all I'm saying. So you're hashing
> less. It's way faster. That concern has been brought to my attention and it's
> something I can see. Do we want to avoid people being stupid and shooting
> themselves and their customers in the foot? Or do we treat this as a special
> case where you mark we're aware of how it should be used and we just try to
> get that awareness out?

Another issue that is sometimes brought up is that an external user may
attempt to send funds to a script that was really part of a higher-level
protocol. This leads to those funds becoming inaccessible unless you gather
all the participants and sign off on those funds. I don't believe this is
anything new, and if users really want to shoot themselves in the foot and
send funds to random addresses they fish out of a blockexplorer there's little
we can do. What we could do is make the scripts used internally in our
protocols unaddressable (see output tagging below), removing this issue
altogether.


## Chaperone signatures

Chaperone signatures are signatures that ensure that there is no third-party
malleability of transactions. The idea is to have an additional signature,
that doesn't use noinput, or any of its variants, and therefore needs to be
authored by one of the pubkeys in the output script, i.e., one or more of the
participants of the contract the transaction belongs to. Concretely in eltoo
we'd be using a shared key known to all participants in the eltoo instance, so
any participant can sign an update to rebind it to the desired output.

Chaperone signatures have a number of downsides however:

-   Additional size: both the public key and the signature actually need to be
    stored along with the real noinput signature, resulting in transfer,
    computational and storage overhead. We can't reuse the same pubkey from the
    noinput signature since that'd require access to the matching privkey which
    is what we want to get rid of using noinput in the first place.
-   Protocols can still simply use a globally known privkey, voiding the
    benefit of chaperone signatures, since third-parties can sign again. I
    argue that third-party malleability is a subset of first-party
    malleability, and we should protect against first-party malleability first
    and foremost. My counterparty has the incentive to trick me, a third-party
    may not.

On the plus side chaperone signatures certainly address the lazy-wallet-dev
scenario, and as AJ points out in [bip-anyprevout] we get back the same
security guarantees as we had without noinput.

From what I remember and the transcript (thanks Kanzure for your awesome work
by the way), there was no strong support for chaperone signatures during the
meeting [6], but feedback from people that were not present is needed:

> if everyone who wanted to use NOINPUT was convinced there was a problem, then
> they would pick the right thing, but clearly people aren't. It's not a
> foot-gun defense mechanism because it's easily bypassed, and it's easier to
> bypass it than to use it. Whereas for tagged outputs, it's that if you want
> any NOINPUT then you must tag.


## Output tagging

One proposal that I found rather fascinating during the discussion in
Amsterdam was that we could achieve the same disincentive to use on
non-smart-contract cases by simply making the output scripts
unaddressable. This can be done by specifying a version of taproot outputs for
which the bech32 addressing scheme simply doesn't have a representation [6]:

> The tagged outputs idea is that we don't have NOINPUT ANYPREVOUT supported for
> taproot v1 outputs, instead we have a segwit version 16 v16 that supports
> taproot. The reason for v16 is that we redefine bech32 to not cover
> v16. There's no addresses for this type of output. If you're an exchange and
> receive a bech32 address, you declare it invalid. You make it less user
> friendly here; and there shouldn't be an address anyway. You might want to see
> it on a block explorer, but you don't want to pass it around to anyone.

We don't need addresses in our contract constructions because we deal directly
with the scripts. This would also have the desired effect of no allowing
generic wallets to send to these addresses, or users accidentally sending
funds to what was supposed to be a one-off script used internally in the
off-chain contract.

Notice that this idea was already used by Russell O'Connor when performing a
transaction on elements using his new scripting language simplicity
[7]:

> For this experimental development, we created an improper segwit version,
> "version 31" for Simplicity addresses. The payload of this segwit version 31
> address contains a commitment Merkle root of a Simplicity program to control
> the UTXO.

The concern with output tagging is that it hurts fungibility, marking outputs
used in a contract as such and making them identifiable. But maybe it would be
a good idea to create two domains anyway: one for user-addressable
destinations which users can use with their general purpose wallets, and one
domain for contracts, which users cannot send to directly.

This also came up during the CoreDev meeting [ams-coredev]:

> these sort of NOINPUT signatures are only things that are within some
> application or within some protocol that gets negotiated between participants,
> but they don't cross-independent domains where you see a wallet or a protocol
> as a kind of domain. You can't tell the difference, is this an address I can
> give to someone else or not? It's all scripts, no real addresses. There are
> types of outputs that are completely insecure unconditionally; there are
> things that are protected and I can give to anyone, you don't want to reuse
> it, but there's no security issue from doing so. This is an additional class
> that is secure perfectly but only when used in the right way.


## Open questions

The questions that remain to be addressed are the following:

1.  General agreement on the usefulness of noinput / anyprevoutanyscript /
    anyprevout. While at the CoreDev meeting I think everybody agreed that
    these proposals a useful, also beyond eltoo, not everybody could be
    there. I'd therefore like to elicit some feedback from the wider community.
2.  Is there strong support or opposition to the chaperone signatures
    introduced in anyprevout / anyprevoutanyscript? I think it'd be best to
    formulate a concrete set of pros and contras, rather than talk about
    abstract dangers or advantages.
3.  The same for output tagging / explicit opt-in. What are the advantages and
    disadvantages?
4.  Shall we merge BIP-118 and bip-anyprevout. This would likely reduce the
    confusion and make for simpler discussions in the end.
5.  Anything I forgot to mention :-)

Cheers,
Christian

[1] <https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-September/002131.html>
[2] <https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-September/017285.html>
[3] <https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-August/001383.html>
[4] <https://github.com/bitcoin/bips/blob/master/bip-0118.mediawiki>
[5] <https://github.com/ajtowns/bips/blob/bip-anyprevout/bip-anyprevout.mediawiki>
[6] <http://diyhpl.us/wiki/transcripts/bitcoin-core-dev-tech/2019-06-06-noinput-etc/>
[7] <https://lists.ozlabs.org/pipermail/simplicity/2019/000018.html>

Re: [bitcoin-dev] Continuing the discussion about noinput / anyprevout

[ZmnSCPxj]

Good morning Christian,

> The concern with output tagging is that it hurts fungibility, marking outputs
> used in a contract as such and making them identifiable. But maybe it would be
> a good idea to create two domains anyway: one for user-addressable
> destinations which users can use with their general purpose wallets, and one
> domain for contracts, which users cannot send to directly.

I rather strongly oppose output tagging.

The entire point of for example Taproot was to reduce the variability of how outputs look like, so that unspent Taproot outputs look exactly like other unspent Taproot outputs regardless of the SCRIPT (or lack of SCRIPT) used to protect the outputs.
That is the reason why we would prefer to not support P2SH-wrapped Taproot even though P2SH-wrapping was intended to cover all future uses of SegWit, including SegWit v1 that Taproot will eventually get.

Indeed, if it is output tagging that gets into Bitcoin base layer, I would strongly suggest the below for all Decker-Russell-Osuntokun implementations:

* A standard MuSig 2-of-2 bip-schnorr SegWit v1 Funding Transaction Output, confirmed onchain
* A "translator transaction" spending the above and paying out to a SegWit v16 output-tagged output, kept offchain.
* Decker-Russell-Osuntokun update transaction, signed with `SIGHASH_NOINPUT` spending the translator transaction output.
* Decker-Russell-Osuntokun state transaction, signed with `SIGHASH_NOINPUT` spending the update transaction output.

The point regarding use of a commonly-known privkey to work around chaperone signatures is appropriate to the above, incidentally.
In short: this is a workaround, plain and simple, and one wonders the point of adding *either* chaperones *or* output tagging if we will, in practice, just work around them anyway.

Again, the *more* important point is that special blockchain constructions should only be used in the "bad" unilateral close case.
In the cooperative case, we want to use simple plain bip-schnorr-signed outputs getting spent to further bip-schnor/Taproot SegWit v1 addresses, to increase the anonymity set of all uses of Decker-Russell-Osuntokun and other applications that might use `SIGHASH_NOINPUT` in some edge case (but which resolve down to simple bip-schnorr-signed n-of-n cases when the protocol is completed successfully by all participants).

We already have the issue in current Lightning where the blockchain-explorer-revealed address for current, existing Poon-Dryja channels is unsafe to send any amount to.
Granted, we should work to make things safer; but I suggest that we should be willing to sacrifice some amount of safety against arguably-stupid decisions in order to have better privacy for larger sets of users.

>
> This also came up during the CoreDev meeting [ams-coredev]:
>
> > these sort of NOINPUT signatures are only things that are within some
> > application or within some protocol that gets negotiated between participants,
> > but they don't cross-independent domains where you see a wallet or a protocol
> > as a kind of domain. You can't tell the difference, is this an address I can
> > give to someone else or not? It's all scripts, no real addresses. There are
> > types of outputs that are completely insecure unconditionally; there are
> > things that are protected and I can give to anyone, you don't want to reuse
> > it, but there's no security issue from doing so. This is an additional class
> > that is secure perfectly but only when used in the right way.

I submit that a Taproot whose internal Taproot point is a NUMS point (thus nobody knows its scalar) is similarly "secure perfectly but only when used in the right way".
Yet the point of Taproot is to hide these outputs until they are spent, improving their privacy while unspent.

I submit also that a Taproot whose internal Taproot point is an n-of-n of all participants, with script branches enforcing particular modes, are similarly "secure perfectly but only when used in the right way", and again the point of Taproot is to allow the n-of-n "everybody agrees" path to hide among the 1-of-1 whale HODLers.

In short: I do not see how you can coherently argue for "we should separate `SIGHASH_NOINPUT` types to a new script type" while simultaneously arguing "we should merge all kinds of SCRIPT usage (and non-usage) together into a single script type".
If we will separate `SIGHASH_NOINPUT`-enabled outputs, we should not implement Taproot, as the existing separation of P2WSH and P2WPKH is congruent to the proposed separation of `SIGHASH_NOINPUT`-enablement.

>
> Open questions
>
> ---------------
>
> The questions that remain to be addressed are the following:
>
> 1.  General agreement on the usefulness of noinput / anyprevoutanyscript /
>     anyprevout. While at the CoreDev meeting I think everybody agreed that
>     these proposals a useful, also beyond eltoo, not everybody could be
>     there. I'd therefore like to elicit some feedback from the wider community.

I strongly agree that `NOINPUT` is useful, and I was not able to attend CoreDev (at least, not with any human fleshbot already known to you --- I checked).

>
> 2.  Is there strong support or opposition to the chaperone signatures
>     introduced in anyprevout / anyprevoutanyscript? I think it'd be best to
>     formulate a concrete set of pros and contras, rather than talk about
>     abstract dangers or advantages.

No opposition, we will just work around this by publishing a common known private key to use for all chaperone signatures, since all the important security is in the `NOINPUT` signature anyway.

>
> 3.  The same for output tagging / explicit opt-in. What are the advantages and
>     disadvantages?

Strongly oppose, see above about my argument.

>
> 4.  Shall we merge BIP-118 and bip-anyprevout. This would likely reduce the
>     confusion and make for simpler discussions in the end.

Ambivalent, mildly support.

>
> 5.  Anything I forgot to mention :-)

Cats are very interesting creatures, and are irrelevant to `SIGHASH_NOINPUT` discussion, but are extremely cute nonetheless.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Continuing the discussion about noinput / anyprevout

[ZmnSCPxj]

Good morning list,

To elucidate further ---

Suppose rather than `SIGHASH_NOINPUT`, we created a new opcode, `OP_CHECKSIG_WITHOUT_INPUT`.

This new opcode ignores any `SIGHASH` flags, if present, on a signature, but instead hashes the current transaction without the input references, then checks that hash to the signature.

This is equivalent to `SIGHASH_NOINPUT`.

Yet as an opcode, it would be possible to embed in a Taproot script.

For example, a Decker-Russell-Osuntokun would have an internal Taproot point be a 2-of-2, then have a script `OP_1 OP_CHECKSIG_WITHOUT_INPUT`.
Unilateral closes would expose the hidden script, but cooperative closes would use the 2-of-2 directly.

Of note, is that any special SCRIPT would already be supportable by Taproot.
This includes SCRIPTs that may potentially lose funds for the user.
Yet such SCRIPTs are already targetable by a Taproot address.

If we are so concerned about `SIGHASH_NOINPUT` abuse, why are we not so concerned about Taproot abuse?

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Continuing the discussion about noinput / anyprevout

[Chris Stewart]

[-- Attachment #1: Type: text/plain, Size: 15052 bytes --]

I do have some concerns about SIGHASH_NOINPUT, mainly that it does
introduce another footgun into the bitcoin protocol with address reuse.
It's common practice for bitcoin businesses to re-use addresses. Many
exchanges [1] reuse addresses for cold storage with very large sums of
money that is stored in these addreses.

It is my understanding with this part of BIP118

>Using NOINPUT the input containing the signature no longer references a
specific output. Any participant can take a transaction and rewrite it by
changing the hash reference to the previous output, without invalidating
the signatures. This allows transactions to be bound to any output that
matches the value committed to in the witness and whose witnessProgram,
combined with the spending transaction's witness returns true.

if an exchange were to once produce a digital signature from that cold
storage address with a SIGHASH_NOINPUT signature, that signature can be
replayed again and again on the blockchain until their wallet is drained.
This might be able to mitigated since the signatures commit to outputs,
which may be small in value for the transaction that SIGHASH_NOINPUT was
used. This means that an exchange could move coins from the address with a
larger transaction that spends money to a new output (and presumably pays a
higher fee than the smaller transactions).

### Why does this matter?

It seems that SIGHASH_NOINPUT will be an extremely useful tool for offchain
protocols like Lightning. This gives us the building blocks for enforcing
specific offchain states to end up onchain [2].

Since this tool is useful, we can presume that it will be integrated into
the signing path of large economic entities in bitcoin -- namely exchanges.
Many exchanges have specific signing procedures for transactions that are
leaving an exchange that is custom software. Now -- presuming wide adoption
of off chain protocols -- they will need to have a _second unique signing
path that uses SIGHASH_NOINPUT_.

It is imperative that this second signing path -- which uses
SIGHASH_NOINPUT -- does NOT get mixed up with the first signing path that
controls an exchanges onchain funds. If this were to happen, fund lost
could occur if the exchange is reusing address, which seems to be common
practice.

This is stated here in BIP118:

>This also means that particular care has to be taken in order to avoid
unintentionally enabling this rebinding mechanism. NOINPUT MUST NOT be
used, unless it is explicitly needed for the application, e.g., it MUST NOT
be a default signing flag in a wallet implementation. Rebinding is only
possible when the outputs the transaction may bind to all use the same
public keys. Any public key that is used in a NOINPUT signature MUST only
be used for outputs that the input may bind to, and they MUST NOT be used
for transactions that the input may not bind to. For example an application
SHOULD generate a new key-pair for the application instance using NOINPUT
signatures and MUST NOT reuse them afterwards.

This means we need to encourage onchain hot wallet signing procedures to be
kept separate from offchain hot wallet signing procedures, which introduces
more complexity for key management (two keychains).

One (of the few) upsides of the current Lightning penalty mechanism is that
fund loss can be contained to balance of the channel. You cannot do
something in the current protocol that will effect your funds outside of
that channel. With SIGHASH_NOINPUT, that property changes.

### A side note
In general, i think we should start disallowing uses of the SIGHASH
protocols that have unexpected behavior. The classic example of this is
SIGHASH_SINGLE [3]. I get uneasy about adding more footguns to the
protocol, which with current network behavior (address re-use)
SIGHASH_NOINPUT would be a big one.


[1] - https://bitinfocharts.com/top-100-richest-bitcoin-addresses.html
[2] -
https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-September/002136.html
[3] -
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/016048.html

On Mon, Sep 30, 2019 at 9:24 AM Christian Decker via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> With the recently renewed interest in eltoo, a proof-of-concept
> implementation
> [1], and the discussions regarding clean abstractions for off-chain
> protocols
> [2,3], I thought it might be time to revisit the `sighash_noinput` proposal
> (BIP-118 [4]), and AJ's `bip-anyprevout` proposal [5].
>
> (sorry for the long e-mail. I wanted to give enough context and describe
> the
> various tradeoffs so people don't have to stitch them together from
> memory. If
> you're impatient there are a couple of open questions at the bottom)
>
> Both proposals are ways to allow rebinding of transactions to new outputs,
> by
> adding a sighash flag that excludes the output when signing. This allows
> the
> transaction to be bound to any output, without needing a new signature, as
> long as output script and input script are compatible, e.g., the signature
> matches the public key specified in the output.
>
> BIP-118 is limited to explaining the details of signature verification, and
> omits anything related to deployment and dependency on other proposals.
> This
> was done in order not to depend on bip-taproot which is also in draft-phase
> currently, and to allow deployment alongside the next version of segwit
> script. `bip-anyprevout` builds on top of BIP-118, adding integration with
> `bip-taproot`, chaperone signatures, limits the use of the sighash flag to
> script path spends, as well as a new pubkey serialization which uses the
> first
> byte to signal opt-in.
>
> I'd like to stress that both proposals are complementary and not competing,
> which is something that I've heard a couple of times.
>
> There remain a couple of unclear points which I hope we can address in the
> coming days, to get this thing moving again, and hopefully get a new tool
> in
> our toolbox soon(ish).
>
> In the following I will quote a couple of things that were discussed during
> the CoreDev meeting earlier this year, but not everybody could join, and
> it is
> important that we engage the wider community, to get a better picture, and
> I
> think not everybody is up-to-date about the current state.
>
>
> ## Dangers of `sighash_noinput`
>
> An argument I have heard against noinput is that it is slightly less
> complex
> or compute intensive than `sighash_all` signatures, which may encourage
> wallet
> creators to only implement the noinput variant, and use it indiscrimi-
> nately. This is certainly a good argument, and indeed we have seen at least
> one developer proposing to use noinput for all transactions to discourage
> address reuse.
>
> This was also mentioned at CoreDev [6]:
>
> > When [...] said he wanted to write a wallet that only used
> SIGHASH\_NOINPUT,
> > that was pause for concern. Some people might want to use
> SIGHASH\_NOINPUT as a
> > way to cheapen or reduce the complexity of making a wallet
> > implementation. SIGHASH\_NOINPUT is from a purely procedural point of
> view
> > easier than doing a SIGHASH\_ALL, that's all I'm saying. So you're
> hashing
> > less. It's way faster. That concern has been brought to my attention and
> it's
> > something I can see. Do we want to avoid people being stupid and shooting
> > themselves and their customers in the foot? Or do we treat this as a
> special
> > case where you mark we're aware of how it should be used and we just try
> to
> > get that awareness out?
>
> Another issue that is sometimes brought up is that an external user may
> attempt to send funds to a script that was really part of a higher-level
> protocol. This leads to those funds becoming inaccessible unless you gather
> all the participants and sign off on those funds. I don't believe this is
> anything new, and if users really want to shoot themselves in the foot and
> send funds to random addresses they fish out of a blockexplorer there's
> little
> we can do. What we could do is make the scripts used internally in our
> protocols unaddressable (see output tagging below), removing this issue
> altogether.
>
>
> ## Chaperone signatures
>
> Chaperone signatures are signatures that ensure that there is no
> third-party
> malleability of transactions. The idea is to have an additional signature,
> that doesn't use noinput, or any of its variants, and therefore needs to be
> authored by one of the pubkeys in the output script, i.e., one or more of
> the
> participants of the contract the transaction belongs to. Concretely in
> eltoo
> we'd be using a shared key known to all participants in the eltoo
> instance, so
> any participant can sign an update to rebind it to the desired output.
>
> Chaperone signatures have a number of downsides however:
>
> -   Additional size: both the public key and the signature actually need
> to be
>     stored along with the real noinput signature, resulting in transfer,
>     computational and storage overhead. We can't reuse the same pubkey
> from the
>     noinput signature since that'd require access to the matching privkey
> which
>     is what we want to get rid of using noinput in the first place.
> -   Protocols can still simply use a globally known privkey, voiding the
>     benefit of chaperone signatures, since third-parties can sign again. I
>     argue that third-party malleability is a subset of first-party
>     malleability, and we should protect against first-party malleability
> first
>     and foremost. My counterparty has the incentive to trick me, a
> third-party
>     may not.
>
> On the plus side chaperone signatures certainly address the lazy-wallet-dev
> scenario, and as AJ points out in [bip-anyprevout] we get back the same
> security guarantees as we had without noinput.
>
> From what I remember and the transcript (thanks Kanzure for your awesome
> work
> by the way), there was no strong support for chaperone signatures during
> the
> meeting [6], but feedback from people that were not present is needed:
>
> > if everyone who wanted to use NOINPUT was convinced there was a problem,
> then
> > they would pick the right thing, but clearly people aren't. It's not a
> > foot-gun defense mechanism because it's easily bypassed, and it's easier
> to
> > bypass it than to use it. Whereas for tagged outputs, it's that if you
> want
> > any NOINPUT then you must tag.
>
>
> ## Output tagging
>
> One proposal that I found rather fascinating during the discussion in
> Amsterdam was that we could achieve the same disincentive to use on
> non-smart-contract cases by simply making the output scripts
> unaddressable. This can be done by specifying a version of taproot outputs
> for
> which the bech32 addressing scheme simply doesn't have a representation
> [6]:
>
> > The tagged outputs idea is that we don't have NOINPUT ANYPREVOUT
> supported for
> > taproot v1 outputs, instead we have a segwit version 16 v16 that supports
> > taproot. The reason for v16 is that we redefine bech32 to not cover
> > v16. There's no addresses for this type of output. If you're an exchange
> and
> > receive a bech32 address, you declare it invalid. You make it less user
> > friendly here; and there shouldn't be an address anyway. You might want
> to see
> > it on a block explorer, but you don't want to pass it around to anyone.
>
> We don't need addresses in our contract constructions because we deal
> directly
> with the scripts. This would also have the desired effect of no allowing
> generic wallets to send to these addresses, or users accidentally sending
> funds to what was supposed to be a one-off script used internally in the
> off-chain contract.
>
> Notice that this idea was already used by Russell O'Connor when performing
> a
> transaction on elements using his new scripting language simplicity
> [7]:
>
> > For this experimental development, we created an improper segwit version,
> > "version 31" for Simplicity addresses. The payload of this segwit
> version 31
> > address contains a commitment Merkle root of a Simplicity program to
> control
> > the UTXO.
>
> The concern with output tagging is that it hurts fungibility, marking
> outputs
> used in a contract as such and making them identifiable. But maybe it
> would be
> a good idea to create two domains anyway: one for user-addressable
> destinations which users can use with their general purpose wallets, and
> one
> domain for contracts, which users cannot send to directly.
>
> This also came up during the CoreDev meeting [ams-coredev]:
>
> > these sort of NOINPUT signatures are only things that are within some
> > application or within some protocol that gets negotiated between
> participants,
> > but they don't cross-independent domains where you see a wallet or a
> protocol
> > as a kind of domain. You can't tell the difference, is this an address I
> can
> > give to someone else or not? It's all scripts, no real addresses. There
> are
> > types of outputs that are completely insecure unconditionally; there are
> > things that are protected and I can give to anyone, you don't want to
> reuse
> > it, but there's no security issue from doing so. This is an additional
> class
> > that is secure perfectly but only when used in the right way.
>
>
> ## Open questions
>
> The questions that remain to be addressed are the following:
>
> 1.  General agreement on the usefulness of noinput / anyprevoutanyscript /
>     anyprevout. While at the CoreDev meeting I think everybody agreed that
>     these proposals a useful, also beyond eltoo, not everybody could be
>     there. I'd therefore like to elicit some feedback from the wider
> community.
> 2.  Is there strong support or opposition to the chaperone signatures
>     introduced in anyprevout / anyprevoutanyscript? I think it'd be best to
>     formulate a concrete set of pros and contras, rather than talk about
>     abstract dangers or advantages.
> 3.  The same for output tagging / explicit opt-in. What are the advantages
> and
>     disadvantages?
> 4.  Shall we merge BIP-118 and bip-anyprevout. This would likely reduce the
>     confusion and make for simpler discussions in the end.
> 5.  Anything I forgot to mention :-)
>
> Cheers,
> Christian
>
> [1] <
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-September/002131.html
> >
> [2] <
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-September/017285.html
> >
> [3] <
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-August/001383.html
> >
> [4] <https://github.com/bitcoin/bips/blob/master/bip-0118.mediawiki>
> [5] <
> https://github.com/ajtowns/bips/blob/bip-anyprevout/bip-anyprevout.mediawiki
> >
> [6] <
> http://diyhpl.us/wiki/transcripts/bitcoin-core-dev-tech/2019-06-06-noinput-etc/
> >
> [7] <https://lists.ozlabs.org/pipermail/simplicity/2019/000018.html>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 18010 bytes --]

Re: [bitcoin-dev] [Lightning-dev] Continuing the discussion about noinput / anyprevout

[ZmnSCPxj]

Good morning lists,

Let me summarize concerns brought up:

* Chris concern, is that an ordinary UTXO that is not allocated for `SIGHASH_NOINPUT` use, is inadvertently spent using `SIGHASH_NOINPUT`.
* My concern, is that unless a UTXO allocated for `SIGHASH_NOINPUT` use, is *indeed* used with SIGHASH_NOINPUT`, it should look exactly the same as any other SegWit v1 output.

I propose the below instead:

* Do ***NOT*** allocate SegWit v16 for `SIGHASH_NOINPUT`.
* Instead, allocate SegWit v1 Tapscript v16 for `SIGHASH_NOINPUT`.

Then, on usage:

* Exchange hoards can be protected by simple MuSig bip-schnorr SegWit v1 outputs, or a NUMS Taproot internal point with a MAST branch Tapscript v0 `OP_CHECKSIG_ADD` sequence.
* Decker-Russell-Osuntokun constructions are backed by a n-of-n MuSig Taproot internal point, with a MAST branch containing a Tapscript v16 with `OP_1 OP_CHECKSIG`.

This solves both concerns:

* Ordinary UTXOs not allocated for `SIGHASH_NOINPUT` use simply do not commit to any Taproot that has a Tapscript v16 branch, and thus `SIGHASH_NOINPUT` is unuseable to claim it.
* If a UTXO used for an offchain protocol ends up in a cooperative-resolution state, nobody has to know that a Tapscript v16 branch existed that could have used `SIGHASH_NOINPUT`.

Again, my objection to output tagging is that it is **publicly visible** as soon as the funding transaction is confirmed onchain that this is a special output used for a Decker-Russell-Osuntokun construction, greatly damaging privacy.
But if this fact is kept secret *unless* the very specific case of unilateral uncooperative enforcement, then it is quite fine with me.

Would this alternate proposal hold better muster?

Regards,
ZmnSCPxj



> I do have some concerns about SIGHASH_NOINPUT, mainly that it does introduce another footgun into the bitcoin protocol with address reuse. It's common practice for bitcoin businesses to re-use addresses. Many exchanges [1] reuse addresses for cold storage with very large sums of money that is stored in these addreses.
>
> It is my understanding with this part of BIP118
>
> >Using NOINPUT the input containing the signature no longer references a specific output. Any participant can take a transaction and rewrite it by changing the hash reference to the previous output, without invalidating the signatures. This allows transactions to be bound to any output that matches the value committed to in the witness and whose witnessProgram, combined with the spending transaction's witness returns true.
>
> if an exchange were to once produce a digital signature from that cold storage address with a SIGHASH_NOINPUT signature, that signature can be replayed again and again on the blockchain until their wallet is drained. This might be able to mitigated since the signatures commit to outputs, which may be small in value for the transaction that SIGHASH_NOINPUT was used. This means that an exchange could move coins from the address with a larger transaction that spends money to a new output (and presumably pays a higher fee than the smaller transactions).
>
> ### Why does this matter?
>
> It seems that SIGHASH_NOINPUT will be an extremely useful tool for offchain protocols like Lightning. This gives us the building blocks for enforcing specific offchain states to end up onchain [2].
>
> Since this tool is useful, we can presume that it will be integrated into the signing path of large economic entities in bitcoin -- namely exchanges. Many exchanges have specific signing procedures for transactions that are leaving an exchange that is custom software. Now -- presuming wide adoption of off chain protocols -- they will need to have a _second unique signing path that uses SIGHASH_NOINPUT_.
>
> It is imperative that this second signing path -- which uses SIGHASH_NOINPUT -- does NOT get mixed up with the first signing path that controls an exchanges onchain funds. If this were to happen, fund lost could occur if the exchange is reusing address, which seems to be common practice.
>
> This is stated here in BIP118:
>
> >This also means that particular care has to be taken in order to avoid unintentionally enabling this rebinding mechanism. NOINPUT MUST NOT be used, unless it is explicitly needed for the application, e.g., it MUST NOT be a default signing flag in a wallet implementation. Rebinding is only possible when the outputs the transaction may bind to all use the same public keys. Any public key that is used in a NOINPUT signature MUST only be used for outputs that the input may bind to, and they MUST NOT be used for transactions that the input may not bind to. For example an application SHOULD generate a new key-pair for the application instance using NOINPUT signatures and MUST NOT reuse them afterwards.
>
> This means we need to encourage onchain hot wallet signing procedures to be kept separate from offchain hot wallet signing procedures, which introduces more complexity for key management (two keychains).
>
> One (of the few) upsides of the current Lightning penalty mechanism is that fund loss can be contained to balance of the channel. You cannot do something in the current protocol that will effect your funds outside of that channel. With SIGHASH_NOINPUT, that property changes.
>
> ### A side note
> In general, i think we should start disallowing uses of the SIGHASH protocols that have unexpected behavior. The classic example of this is SIGHASH_SINGLE [3]. I get uneasy about adding more footguns to the protocol, which with current network behavior (address re-use) SIGHASH_NOINPUT would be a big one.
>
> [1] - https://bitinfocharts.com/top-100-richest-bitcoin-addresses.html
> [2] - https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-September/002136.html
> [3] - https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/016048.html
>
> On Mon, Sep 30, 2019 at 9:24 AM Christian Decker via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> > With the recently renewed interest in eltoo, a proof-of-concept implementation
> > [1], and the discussions regarding clean abstractions for off-chain protocols
> > [2,3], I thought it might be time to revisit the `sighash_noinput` proposal
> > (BIP-118 [4]), and AJ's `bip-anyprevout` proposal [5].
> >
> > (sorry for the long e-mail. I wanted to give enough context and describe the
> > various tradeoffs so people don't have to stitch them together from memory. If
> > you're impatient there are a couple of open questions at the bottom)
> >
> > Both proposals are ways to allow rebinding of transactions to new outputs, by
> > adding a sighash flag that excludes the output when signing. This allows the
> > transaction to be bound to any output, without needing a new signature, as
> > long as output script and input script are compatible, e.g., the signature
> > matches the public key specified in the output.
> >
> > BIP-118 is limited to explaining the details of signature verification, and
> > omits anything related to deployment and dependency on other proposals. This
> > was done in order not to depend on bip-taproot which is also in draft-phase
> > currently, and to allow deployment alongside the next version of segwit
> > script. `bip-anyprevout` builds on top of BIP-118, adding integration with
> > `bip-taproot`, chaperone signatures, limits the use of the sighash flag to
> > script path spends, as well as a new pubkey serialization which uses the first
> > byte to signal opt-in.
> >
> > I'd like to stress that both proposals are complementary and not competing,
> > which is something that I've heard a couple of times.
> >
> > There remain a couple of unclear points which I hope we can address in the
> > coming days, to get this thing moving again, and hopefully get a new tool in
> > our toolbox soon(ish).
> >
> > In the following I will quote a couple of things that were discussed during
> > the CoreDev meeting earlier this year, but not everybody could join, and it is
> > important that we engage the wider community, to get a better picture, and I
> > think not everybody is up-to-date about the current state.
> >
> > ## Dangers of `sighash_noinput`
> >
> > An argument I have heard against noinput is that it is slightly less complex
> > or compute intensive than `sighash_all` signatures, which may encourage wallet
> > creators to only implement the noinput variant, and use it indiscrimi-
> > nately. This is certainly a good argument, and indeed we have seen at least
> > one developer proposing to use noinput for all transactions to discourage
> > address reuse.
> >
> > This was also mentioned at CoreDev [6]:
> >
> > > When [...] said he wanted to write a wallet that only used SIGHASH\_NOINPUT,
> > > that was pause for concern. Some people might want to use SIGHASH\_NOINPUT as a
> > > way to cheapen or reduce the complexity of making a wallet
> > > implementation. SIGHASH\_NOINPUT is from a purely procedural point of view
> > > easier than doing a SIGHASH\_ALL, that's all I'm saying. So you're hashing
> > > less. It's way faster. That concern has been brought to my attention and it's
> > > something I can see. Do we want to avoid people being stupid and shooting
> > > themselves and their customers in the foot? Or do we treat this as a special
> > > case where you mark we're aware of how it should be used and we just try to
> > > get that awareness out?
> >
> > Another issue that is sometimes brought up is that an external user may
> > attempt to send funds to a script that was really part of a higher-level
> > protocol. This leads to those funds becoming inaccessible unless you gather
> > all the participants and sign off on those funds. I don't believe this is
> > anything new, and if users really want to shoot themselves in the foot and
> > send funds to random addresses they fish out of a blockexplorer there's little
> > we can do. What we could do is make the scripts used internally in our
> > protocols unaddressable (see output tagging below), removing this issue
> > altogether.
> >
> > ## Chaperone signatures
> >
> > Chaperone signatures are signatures that ensure that there is no third-party
> > malleability of transactions. The idea is to have an additional signature,
> > that doesn't use noinput, or any of its variants, and therefore needs to be
> > authored by one of the pubkeys in the output script, i.e., one or more of the
> > participants of the contract the transaction belongs to. Concretely in eltoo
> > we'd be using a shared key known to all participants in the eltoo instance, so
> > any participant can sign an update to rebind it to the desired output.
> >
> > Chaperone signatures have a number of downsides however:
> >
> > -   Additional size: both the public key and the signature actually need to be
> >     stored along with the real noinput signature, resulting in transfer,
> >     computational and storage overhead. We can't reuse the same pubkey from the
> >     noinput signature since that'd require access to the matching privkey which
> >     is what we want to get rid of using noinput in the first place.
> > -   Protocols can still simply use a globally known privkey, voiding the
> >     benefit of chaperone signatures, since third-parties can sign again. I
> >     argue that third-party malleability is a subset of first-party
> >     malleability, and we should protect against first-party malleability first
> >     and foremost. My counterparty has the incentive to trick me, a third-party
> >     may not.
> >
> > On the plus side chaperone signatures certainly address the lazy-wallet-dev
> > scenario, and as AJ points out in [bip-anyprevout] we get back the same
> > security guarantees as we had without noinput.
> >
> > From what I remember and the transcript (thanks Kanzure for your awesome work
> > by the way), there was no strong support for chaperone signatures during the
> > meeting [6], but feedback from people that were not present is needed:
> >
> > > if everyone who wanted to use NOINPUT was convinced there was a problem, then
> > > they would pick the right thing, but clearly people aren't. It's not a
> > > foot-gun defense mechanism because it's easily bypassed, and it's easier to
> > > bypass it than to use it. Whereas for tagged outputs, it's that if you want
> > > any NOINPUT then you must tag.
> >
> > ## Output tagging
> >
> > One proposal that I found rather fascinating during the discussion in
> > Amsterdam was that we could achieve the same disincentive to use on
> > non-smart-contract cases by simply making the output scripts
> > unaddressable. This can be done by specifying a version of taproot outputs for
> > which the bech32 addressing scheme simply doesn't have a representation [6]:
> >
> > > The tagged outputs idea is that we don't have NOINPUT ANYPREVOUT supported for
> > > taproot v1 outputs, instead we have a segwit version 16 v16 that supports
> > > taproot. The reason for v16 is that we redefine bech32 to not cover
> > > v16. There's no addresses for this type of output. If you're an exchange and
> > > receive a bech32 address, you declare it invalid. You make it less user
> > > friendly here; and there shouldn't be an address anyway. You might want to see
> > > it on a block explorer, but you don't want to pass it around to anyone.
> >
> > We don't need addresses in our contract constructions because we deal directly
> > with the scripts. This would also have the desired effect of no allowing
> > generic wallets to send to these addresses, or users accidentally sending
> > funds to what was supposed to be a one-off script used internally in the
> > off-chain contract.
> >
> > Notice that this idea was already used by Russell O'Connor when performing a
> > transaction on elements using his new scripting language simplicity
> > [7]:
> >
> > > For this experimental development, we created an improper segwit version,
> > > "version 31" for Simplicity addresses. The payload of this segwit version 31
> > > address contains a commitment Merkle root of a Simplicity program to control
> > > the UTXO.
> >
> > The concern with output tagging is that it hurts fungibility, marking outputs
> > used in a contract as such and making them identifiable. But maybe it would be
> > a good idea to create two domains anyway: one for user-addressable
> > destinations which users can use with their general purpose wallets, and one
> > domain for contracts, which users cannot send to directly.
> >
> > This also came up during the CoreDev meeting [ams-coredev]:
> >
> > > these sort of NOINPUT signatures are only things that are within some
> > > application or within some protocol that gets negotiated between participants,
> > > but they don't cross-independent domains where you see a wallet or a protocol
> > > as a kind of domain. You can't tell the difference, is this an address I can
> > > give to someone else or not? It's all scripts, no real addresses. There are
> > > types of outputs that are completely insecure unconditionally; there are
> > > things that are protected and I can give to anyone, you don't want to reuse
> > > it, but there's no security issue from doing so. This is an additional class
> > > that is secure perfectly but only when used in the right way.
> >
> > ## Open questions
> >
> > The questions that remain to be addressed are the following:
> >
> > 1.  General agreement on the usefulness of noinput / anyprevoutanyscript /
> >     anyprevout. While at the CoreDev meeting I think everybody agreed that
> >     these proposals a useful, also beyond eltoo, not everybody could be
> >     there. I'd therefore like to elicit some feedback from the wider community.
> > 2.  Is there strong support or opposition to the chaperone signatures
> >     introduced in anyprevout / anyprevoutanyscript? I think it'd be best to
> >     formulate a concrete set of pros and contras, rather than talk about
> >     abstract dangers or advantages.
> > 3.  The same for output tagging / explicit opt-in. What are the advantages and
> >     disadvantages?
> > 4.  Shall we merge BIP-118 and bip-anyprevout. This would likely reduce the
> >     confusion and make for simpler discussions in the end.
> > 5.  Anything I forgot to mention :-)
> >
> > Cheers,
> > Christian
> >
> > [1] <https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-September/002131.html>
> > [2] <https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-September/017285.html>
> > [3] <https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-August/001383.html>
> > [4] <https://github.com/bitcoin/bips/blob/master/bip-0118.mediawiki>
> > [5] <https://github.com/ajtowns/bips/blob/bip-anyprevout/bip-anyprevout.mediawiki>
> > [6] <http://diyhpl.us/wiki/transcripts/bitcoin-core-dev-tech/2019-06-06-noinput-etc/>
> > [7] <https://lists.ozlabs.org/pipermail/simplicity/2019/000018.html>
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Continuing the discussion about noinput / anyprevout

[Christian Decker]

ZmnSCPxj <ZmnSCPxj@protonmail.com> writes:
> I rather strongly oppose output tagging.
>
> The entire point of for example Taproot was to reduce the variability
> of how outputs look like, so that unspent Taproot outputs look exactly
> like other unspent Taproot outputs regardless of the SCRIPT (or lack
> of SCRIPT) used to protect the outputs.  That is the reason why we
> would prefer to not support P2SH-wrapped Taproot even though
> P2SH-wrapping was intended to cover all future uses of SegWit,
> including SegWit v1 that Taproot will eventually get.

That is a bit reductive if you ask me. Taproot brings a number of
improvements such as the reduction of on-chain footprint in the
collaborative spend case, the hiding of complex logic in that case, and
yes, the uniformity of UTXOs that you mentioned. I do agree that it'd be
to make everything look identical to the outside observer, but saying
that separating outputs into two coarse-grained domains is equivalent to
throwing the baby out with the bath-water :-)

That being said, I should clarify that I would prefer not having to make
special accomodations on top of the raw sighash_noinput proposal, for
some perceived, but abstract danger that someone might shoot themselves
in the foot. I think we're all old enough not to need too much
handholding :-)

Output tagging is my second choice, since it minimizes the need for
people to get creative to work around other proposals, and minimizes the
on-chain footprint, and finally chaperone signatures are my least
preferred option due to its heavy-handed nature and the increased cost.

> Indeed, if it is output tagging that gets into Bitcoin base layer, I
> would strongly suggest the below for all Decker-Russell-Osuntokun
> implementations:
>
> * A standard MuSig 2-of-2 bip-schnorr SegWit v1 Funding Transaction Output, confirmed onchain
> * A "translator transaction" spending the above and paying out to a SegWit v16 output-tagged output, kept offchain.
> * Decker-Russell-Osuntokun update transaction, signed with `SIGHASH_NOINPUT` spending the translator transaction output.
> * Decker-Russell-Osuntokun state transaction, signed with `SIGHASH_NOINPUT` spending the update transaction output.

That is very much how I was planning to implement it anyway, using a
trigger transaction to separate timeout start and the actual
update/settlement pairs (cfr. eltoo paper Section 4.2). So for eltoo
there shouldn't be an issue here :-)

> The point regarding use of a commonly-known privkey to work around
> chaperone signatures is appropriate to the above, incidentally.  In
> short: this is a workaround, plain and simple, and one wonders the
> point of adding *either* chaperones *or* output tagging if we will, in
> practice, just work around them anyway.

Exactly, why introduce the extra burden of chaperone signatures or
output tagging if we're just going to sidestep it?

> Again, the *more* important point is that special blockchain
> constructions should only be used in the "bad" unilateral close case.
> In the cooperative case, we want to use simple plain
> bip-schnorr-signed outputs getting spent to further bip-schnor/Taproot
> SegWit v1 addresses, to increase the anonymity set of all uses of
> Decker-Russell-Osuntokun and other applications that might use
> `SIGHASH_NOINPUT` in some edge case (but which resolve down to simple
> bip-schnorr-signed n-of-n cases when the protocol is completed
> successfully by all participants).

While I do agree that we should keep outputs as unidentifiable as
possible, I am starting to question whether that is possible for
off-chain payment networks since we are gossiping about the existence of
channels and binding them to outpoints to prove their existence anyway.

Not the strongest argument I know, but there's little point in talking
ideal cases when we need to weaken that later again. 

>> Open questions
>>
>> ---------------
>>
>> The questions that remain to be addressed are the following:
>>
>> 1.  General agreement on the usefulness of noinput / anyprevoutanyscript /
>>     anyprevout. While at the CoreDev meeting I think everybody agreed that
>>     these proposals a useful, also beyond eltoo, not everybody could be
>>     there. I'd therefore like to elicit some feedback from the wider community.
>
> I strongly agree that `NOINPUT` is useful, and I was not able to attend CoreDev (at least, not with any human fleshbot already known to you --- I checked).

Great, good to know that I'm not shouting into the void, and that I'm
not just that crazy guy trying to get his hairbrained scheme to work :-)

>> 2.  Is there strong support or opposition to the chaperone signatures
>>     introduced in anyprevout / anyprevoutanyscript? I think it'd be best to
>>     formulate a concrete set of pros and contras, rather than talk about
>>     abstract dangers or advantages.
>
> No opposition, we will just work around this by publishing a common
> known private key to use for all chaperone signatures, since all the
> important security is in the `NOINPUT` signature anyway.
>
>>
>> 3.  The same for output tagging / explicit opt-in. What are the advantages and
>>     disadvantages?
>
> Strongly oppose, see above about my argument.
>
>>
>> 4.  Shall we merge BIP-118 and bip-anyprevout. This would likely reduce the
>>     confusion and make for simpler discussions in the end.
>
> Ambivalent, mildly support.
>
>>
>> 5.  Anything I forgot to mention :-)
>
> Cats are very interesting creatures, and are irrelevant to `SIGHASH_NOINPUT` discussion, but are extremely cute nonetheless.

Definitely agreed :+1:

Re: [bitcoin-dev] Continuing the discussion about noinput / anyprevout

[Christian Decker]

ZmnSCPxj <ZmnSCPxj@protonmail.com> writes:
> To elucidate further ---
>
> Suppose rather than `SIGHASH_NOINPUT`, we created a new opcode,
> `OP_CHECKSIG_WITHOUT_INPUT`.
>
> This new opcode ignores any `SIGHASH` flags, if present, on a
> signature, but instead hashes the current transaction without the
> input references, then checks that hash to the signature.
>
> This is equivalent to `SIGHASH_NOINPUT`.
>
> Yet as an opcode, it would be possible to embed in a Taproot script.
>
> For example, a Decker-Russell-Osuntokun would have an internal Taproot
> point be a 2-of-2, then have a script `OP_1
> OP_CHECKSIG_WITHOUT_INPUT`.  Unilateral closes would expose the hidden
> script, but cooperative closes would use the 2-of-2 directly.
>
> Of note, is that any special SCRIPT would already be supportable by Taproot.
> This includes SCRIPTs that may potentially lose funds for the user.
> Yet such SCRIPTs are already targetable by a Taproot address.
>
> If we are so concerned about `SIGHASH_NOINPUT` abuse, why are we not
> so concerned about Taproot abuse?

That would certainly be another possibility, which I have not explored
in detail so far. Due to the similarity between the various signature
checking op-codes it felt that it should be a sighash flag, and it
neatly slotted into the already existing flags. If we go for a separate
opcode we might end up reinventing the wheel, and to be honest I feared
that proposing a new opcode would get us into bikeshedding territory
(which I apparently failed to avoid with the sighash flag anyway...).

The advantage would be that with the sighash flag the spender is in
charge of specifying the flags, whereas with an opcode the output
dictates the signature verification modalities. The downside is the
increased design space.

What do others think? Would this be an acceptable opt-in mechanism that
addresses the main concerns?

Cheers,
Christian

Re: [bitcoin-dev] [Lightning-dev] Continuing the discussion about noinput / anyprevout

[Ethan Heilman]

>I don't find too compelling the potential problem of a 'bad wallet designer', whether lazy or dogmatic, misusing noinput. I think there are simpler ways to cut corners and there will always be plenty of good wallet options people can choose.

I want to second this. The most expensive part of wallet design is
engineering time. Writing code that uses a new sighash or a custom
script with a OP_CODE is a very large barrier to use. How many wallets
support multisig or RBF? How much BTC has been stolen over the entire
history of Bitcoin because of sighash SIGHASH_NONE or SIGHASH_SINGLE
vs ECDSA nonce reuse?

On Tue, Oct 1, 2019 at 9:35 AM Richard Myers <rich@gotenna.com> wrote:
>
> Thanks Christian for pulling together this concise summary.
>
>> 1.  General agreement on the usefulness of noinput / anyprevoutanyscript /
>>     anyprevout.
>
>
> I certainly support the unification and adoption of the sighash_noinput and anyprevoutput* proposals to enable eltoo, but also to make possible better off-chain protocol designs generally.
>
> Among the various advantages previously discussed, the particular use case benefits from eltoo I want to take advantage of is less interactive payment channel negotiation.
>
> In talking with people about eltoo this summer, I found most people generally support adding this as an option to Lightning. The only general concern I heard, if any,  was the vague idea that rebindable transactions could be somehow misused or abused.
>
> I believe when these concerns are made more concrete they can be classified and addressed.
>
> I don't find too compelling the potential problem of a 'bad wallet designer', whether lazy or dogmatic, misusing noinput. I think there are simpler ways to cut corners and there will always be plenty of good wallet options people can choose.
>
> Because scripts signed with no_input signatures are only really exchanged and used for off-chain negotiations, very few should ever appear on chain. Those that do should represent non-cooperative situations that involve signing parties who know not to reuse or share scripts with these public keys again. No third party has any reason to spend value to a multisignature script they don't control, whether or not a no_input signature exists for it.
>
>> 2.  Is there strong support or opposition to the chaperone signatures
>>     introduced in anyprevout / anyprevoutanyscript? I think it'd be best to
>>     formulate a concrete set of pros and contras, rather than talk about
>>     abstract dangers or advantages.
>
>
> As I mentioned before, I don't think the lazy wallet designer advantage is enough to justify the downsides of chaperone signatures. One additional downside is the additional code complexity required to flag whether or not a chaperone output is included. By comparison, the code changes for creating a no_input digest that skips the prevout and prevscript parts of a tx is much less intrusive and easier to maintain.
>
>> 3.  The same for output tagging / explicit opt-in. What are the advantages and
>>     disadvantages?
>
>
> I see the point ZmnSCPxj makes about tagged outputs negatively impacting the anonymity set of taproot transactions. The suggested work around would impose a cost to unilateral closes of an additional translation transaction and not using the work around would cause a hit to anonymity for off-chain script users. I feel both costs are too high relative to the benefit gained of preventing sloppy reuse of public keys.
>
>> 4.  Shall we merge BIP-118 and bip-anyprevout. This would likely reduce the
>>     confusion and make for simpler discussions in the end.
>
>
> I believe they should be merged. I also think both chaperone signatures and output tagging should become part of the discussion of security alternatives, but not part of the initial specification.
>
> I understand the desire to be conservative with protocol changes that could be misused. However, with just taproot and taproot public key types the anyprevout functionality is already very opt-in and not something that might accidentally get used. Belt-and-suspender protections like chaperone signatures and tagged outputs have their own impacts on code complexity, on-chain transaction sizes and transaction anonymity that also must be considered.
>
> I believe efforts like descriptors will help people follow best practices when working with complex scripts without pushing extra complexity for safety into the consensus layer of bitcoin. Anywhere we can make core code simpler, and handle foot-guns in higher level non-consensus code, the better.
>
> _______________________________________________
>>
>> Lightning-dev mailing list
>> Lightning-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [bitcoin-dev] Continuing the discussion about noinput / anyprevout

[Anthony Towns]

On Mon, Sep 30, 2019 at 11:28:43PM +0000, ZmnSCPxj via bitcoin-dev wrote:
> Suppose rather than `SIGHASH_NOINPUT`, we created a new opcode, `OP_CHECKSIG_WITHOUT_INPUT`.

I don't think there's any meaningful difference between making a new
opcode and making a new tapscript public key type; the difference is
just one of encoding:

   3301<key>AC   [CHECKSIG of public key type 0x01]
   32<key>B3     [CHECKSIG_WITHOUT_INPUT (replacing NOP4) of key]

> This new opcode ignores any `SIGHASH` flags, if present, on a signature,

(How sighash flags are treated can be redefined by new public key types;
if that's not obvious already)

Cheers,
aj

Re: [bitcoin-dev] [Lightning-dev] Continuing the discussion about noinput / anyprevout

[Chris Stewart]

[-- Attachment #1: Type: text/plain, Size: 8592 bytes --]

> I don't find too compelling the potential problem of a 'bad wallet
designer', whether lazy or dogmatic, misusing noinput. I think there are
simpler ways to cut corners and there will always be plenty of good wallet
options people can choose.

In my original post, the business that I am talking about don't use "off
the shelf" wallet options. It isn't a "let's switch from wallet A to wallet
B" kind of situation. Usually this involves design from ground up with
security considerations that businesses of scale need to consider (signing
procedures and key handling being the most important!).

>Because scripts signed with no_input signatures are only really exchanged
and used for off-chain negotiations, very few should ever appear on chain.
Those that do should represent non-cooperative situations that involve
signing parties who know not to reuse or share scripts with these public
keys again. No third party has any reason to spend value to a
multisignature script they don't control, whether or not a no_input
signature exists for it.

Just because some one is your friend today, doesn't mean they aren't
necessarily your adversary tomorrow. I don't think a signature being
onchain really matters, as you have to give it to your counterparty
regardless. How do you know your counterparty won't replay that
SIGHASH_NOINPUT signature later? Offchain protocols shouldn't rely on
"good-will" for their counter parties for security.

>As I mentioned before, I don't think the lazy wallet designer advantage is
enough to justify the downsides of chaperone signatures. One additional
downside is the additional code complexity required to flag whether or not
a chaperone output is included. By comparison, the code changes for
creating a no_input digest that skips the prevout and prevscript parts of a
tx is much less intrusive and easier to maintain.

>I want to second this. The most expensive part of wallet design is
engineering time. Writing code that uses a new sighash or a custom
script with a OP_CODE is a very large barrier to use. How many wallets
support multisig or RBF? How much BTC has been stolen over the entire
history of Bitcoin because of sighash SIGHASH_NONE or SIGHASH_SINGLE
vs ECDSA nonce reuse

I actually think lazy wallet designer is a really compelling reason to fix
footguns in the bitcoin protocol. Mt Gox is allegedly a product of lazy
wallet design. Now we have non-malleable transactions in the form of segwit
(yay!) that prevent this exploit. We can wish that the Mt Gox wallet
designers were more aware of bitcoin protocol vulnerabilities, but at the
end of the day the best thing to do was offering an alternative that
circumvents the vulnerability all together.

Ethan made a great point about SIGHASH_NONE or SIGHASH_SINGLE -- which have
virtually no use AFAIK -- vs the ECDSA nonce reuse which is used in nearly
every transaction. The feature -- ECDSA in this case -- was managed to be
done wrong by wallet developers causing fund loss. Unfortunately we can't
protect against this type of bug in the protocol.

If things aren't used -- such as SIGHASH_NONE or SIGHASH_SINGLE -- it
doesn't matter if they are secure or insecure. I'm hopefully that offchain
protocols will achieve wide adoption, and I would hate to see money lost
because of this. Even though they aren't used, in my OP I do advocate for
fixing these.

> understand the desire to be conservative with protocol changes that could
be misused. However, with just taproot and taproot public key types the
anyprevout functionality is already very opt-in and not something that
might accidentally get used. Belt-and-suspender protections like chaperone
signatures and tagged outputs have their own impacts on code complexity,
on-chain transaction sizes and transaction anonymity that also must be
considered.

I'm making the assumption that the business has decided to use this
feature, and in my OP I talk about the engineering decisions that will have
to be made support this. I'm hoping the "lazy wallet designers" -- or
perhaps people that don't follow bitcoin protocol development as rabidly as
us :-) -- can see that nuance.

-Chris



On Tue, Oct 1, 2019 at 8:36 AM Richard Myers <rich@gotenna.com> wrote:

> Thanks Christian for pulling together this concise summary.
>
> 1.  General agreement on the usefulness of noinput / anyprevoutanyscript /
>>     anyprevout.
>>
>
> I certainly support the unification and adoption of the sighash_noinput
> and anyprevoutput* proposals to enable eltoo, but also to make possible
> better off-chain protocol designs generally.
>
> Among the various advantages previously discussed, the particular use case
> benefits from eltoo I want to take advantage of is less interactive payment
> channel negotiation.
>
> In talking with people about eltoo this summer, I found most people
> generally support adding this as an option to Lightning. The only general
> concern I heard, if any,  was the vague idea that rebindable transactions
> could be somehow misused or abused.
>
> I believe when these concerns are made more concrete they can be
> classified and addressed.
>
> I don't find too compelling the potential problem of a 'bad wallet
> designer', whether lazy or dogmatic, misusing noinput. I think there are
> simpler ways to cut corners and there will always be plenty of good wallet
> options people can choose.
>
> Because scripts signed with no_input signatures are only really exchanged
> and used for off-chain negotiations, very few should ever appear on chain.
> Those that do should represent non-cooperative situations that involve
> signing parties who know not to reuse or share scripts with these public
> keys again. No third party has any reason to spend value to a
> multisignature script they don't control, whether or not a no_input
> signature exists for it.
>
> 2.  Is there strong support or opposition to the chaperone signatures
>>     introduced in anyprevout / anyprevoutanyscript? I think it'd be best
>> to
>>     formulate a concrete set of pros and contras, rather than talk about
>>     abstract dangers or advantages.
>>
>
> As I mentioned before, I don't think the lazy wallet designer advantage is
> enough to justify the downsides of chaperone signatures. One additional
> downside is the additional code complexity required to flag whether or not
> a chaperone output is included. By comparison, the code changes for
> creating a no_input digest that skips the prevout and prevscript parts of a
> tx is much less intrusive and easier to maintain.
>
> 3.  The same for output tagging / explicit opt-in. What are the advantages
>> and
>>     disadvantages?
>>
>
> I see the point ZmnSCPxj makes about tagged outputs negatively impacting
> the anonymity set of taproot transactions. The suggested work around would
> impose a cost to unilateral closes of an additional translation transaction
> and not using the work around would cause a hit to anonymity for off-chain
> script users. I feel both costs are too high relative to the benefit gained
> of preventing sloppy reuse of public keys.
>
> 4.  Shall we merge BIP-118 and bip-anyprevout. This would likely reduce the
>>     confusion and make for simpler discussions in the end.
>
>
> I believe they should be merged. I also think both chaperone signatures
> and output tagging should become part of the discussion of security
> alternatives, but not part of the initial specification.
>
> I understand the desire to be conservative with protocol changes that
> could be misused. However, with just taproot and taproot public key types
> the anyprevout functionality is already very opt-in and not something that
> might accidentally get used. Belt-and-suspender protections like chaperone
> signatures and tagged outputs have their own impacts on code complexity,
> on-chain transaction sizes and transaction anonymity that also must be
> considered.
>
> I believe efforts like descriptors will help people follow best practices
> when working with complex scripts without pushing extra complexity for
> safety into the consensus layer of bitcoin. Anywhere we can make core code
> simpler, and handle foot-guns in higher level non-consensus code, the
> better.
>
> _______________________________________________
>
>> Lightning-dev mailing list
>> Lightning-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>

[-- Attachment #2: Type: text/html, Size: 11909 bytes --]

Re: [bitcoin-dev] Continuing the discussion about noinput / anyprevout

[ZmnSCPxj]

Good morning Christian,

> > -   A standard MuSig 2-of-2 bip-schnorr SegWit v1 Funding Transaction Output, confirmed onchain
> > -   A "translator transaction" spending the above and paying out to a SegWit v16 output-tagged output, kept offchain.
> > -   Decker-Russell-Osuntokun update transaction, signed with `SIGHASH_NOINPUT` spending the translator transaction output.
> > -   Decker-Russell-Osuntokun state transaction, signed with `SIGHASH_NOINPUT` spending the update transaction output.
>
> That is very much how I was planning to implement it anyway, using a
> trigger transaction to separate timeout start and the actual
> update/settlement pairs (cfr. eltoo paper Section 4.2). So for eltoo
> there shouldn't be an issue here :-)

My understanding is that a trigger transaction is not in fact necessary for Decker-Russell-Osuntokun: any update transaction could spend the funding transaction output directly, and thereby start the relative timelock.
At least, if we could arrange the funding transaction output to be spendable directly using `SIGHASH_NOINPUT` or variants thereof.


> > Again, the more important point is that special blockchain
> > constructions should only be used in the "bad" unilateral close case.
> > In the cooperative case, we want to use simple plain
> > bip-schnorr-signed outputs getting spent to further bip-schnor/Taproot
> > SegWit v1 addresses, to increase the anonymity set of all uses of
> > Decker-Russell-Osuntokun and other applications that might use
> > `SIGHASH_NOINPUT` in some edge case (but which resolve down to simple
> > bip-schnorr-signed n-of-n cases when the protocol is completed
> > successfully by all participants).
>
> While I do agree that we should keep outputs as unidentifiable as
> possible, I am starting to question whether that is possible for
> off-chain payment networks since we are gossiping about the existence of
> channels and binding them to outpoints to prove their existence anyway.

* Lightning supports unpublished channels, so we do not gossip some outpoints even though they are in fact channels underneath.
  * I confess the existence of unpublished channels in the spec fails to summon any reaction other than incredulity from me, but they exist nonetheless, my incredulity notwithstanding.
* Historical channels that have been cooperatively closed are no longer normally gossiped, so the fact that they used to be channels is no longer widely broadcast, and may eventually be forgotten by most or all of the network.
  * This means anyone who wants to record the historical use of Lightning will have to retain the information themselves, rather than delegating it to fullnodes everywhere.

>
> Not the strongest argument I know, but there's little point in talking
> ideal cases when we need to weaken that later again.

The point of ideal cases is to strive to approach them, not necessarily achieve them.
Just as a completely unbiased rational reasoner is almost impossible to achieve, does not mean we should give up all attempts to reduce bias.

Outpoints that used to be channels, but have now been closed using cooperative closes, will potentially no longer be widely gossiped as having once been channels, thus it may happen that they will eventually be forgotten by most of the network as once having been channels.
But if the outpoints of those channels are specially marked, then that cannot be forgotten, as the initial block download thereafter will have that history indelibly etched forevermore.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Continuing the discussion about noinput / anyprevout

[ZmnSCPxj]

Good morning aj,


> On Mon, Sep 30, 2019 at 11:28:43PM +0000, ZmnSCPxj via bitcoin-dev wrote:
>
> > Suppose rather than `SIGHASH_NOINPUT`, we created a new opcode, `OP_CHECKSIG_WITHOUT_INPUT`.
>
> I don't think there's any meaningful difference between making a new
> opcode and making a new tapscript public key type; the difference is
> just one of encoding:
>
> 3301<key>AC [CHECKSIG of public key type 0x01]
> 32<key>B3 [CHECKSIG_WITHOUT_INPUT (replacing NOP4) of key]
>
> > This new opcode ignores any `SIGHASH` flags, if present, on a signature,
>
> (How sighash flags are treated can be redefined by new public key types;
> if that's not obvious already)


Thank you for this thought,
I believe under tapscript v0 we can give `OP_1` as the public key to `OP_CHECKSIG` to mean to reuse the internal Taproot pubkey, would it be possible to have some similar mechanism here, to copy the internal Taproot pubkey but also to enable new `SIGHASH` flag for this particular script only?

This seems fine, as then a Decker-Russell-Osuntokun funding tx output between nodes A, B, and C would have:

* Taproot internal key: `P = MuSig(A, B, C)`
* Script 1: leaf version 0, `<MuSig(A,B,C) + pubkeytype 1> OP_CHECKSIG`

Then, update transactions could use `MuSig(A,B,C)` for signing along the "update" path, with unique "state" keys.
And cooperative closes would sign using `P + h(P | MAST(<MuSig(A,B,C) + pubkeytype 1> OPCHECKSIG)) * G`, not revealing the fact that this was in fact a Decker-Russell-Osuntokun output.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Continuing the discussion about noinput / anyprevout

[Anthony Towns]

On Mon, Sep 30, 2019 at 03:23:56PM +0200, Christian Decker via bitcoin-dev wrote:
> With the recently renewed interest in eltoo, a proof-of-concept implementation
> [1], and the discussions regarding clean abstractions for off-chain protocols
> [2,3], I thought it might be time to revisit the `sighash_noinput` proposal
> (BIP-118 [4]), and AJ's `bip-anyprevout` proposal [5].

Hey Christian, thanks for the write up!

> ## Open questions
> The questions that remain to be addressed are the following:
> 1.  General agreement on the usefulness of noinput / anyprevoutanyscript /
>     anyprevout[?]
> 2.  Is there strong support or opposition to the chaperone signatures[?]
> 3.  The same for output tagging / explicit opt-in[?]
> 4.  Shall we merge BIP-118 and bip-anyprevout. This would likely reduce the
>     confusion and make for simpler discussions in the end.

I think there's an important open question you missed from this list:
(1.5) do we really understand what the dangers of noinput/anyprevout-style
constructions actually are?

My impression on the first 3.5 q's is: (1) yes, (1.5) not really,
(2) weak opposition for requiring chaperone sigs, (3) mixed (weak)
support/opposition for output tagging.

My thinking at the moment (subject to change!) is:

 * anyprevout signatures make the address you're signing for less safe,
   which may cause you to lose funds when additional coins are sent to
   the same address; this can be avoided if handled with care (or if you
   don't care about losing funds in the event of address reuse)

 * being able to guarantee that an address can never be signed for with
   an anyprevout signature is therefore valuable; so having it be opt-in
   at the tapscript level, rather than a sighash flag available for
   key-path spends is valuable (I call this "opt-in", but it's hidden
   until use via taproot rather than "explicit" as output tagging
   would be)

 * receiving funds spent via an anyprevout signature does not involve any
   qualitatively new double-spending/malleability risks.
   
   (eltoo is unavoidably malleable if there are multiple update
   transactions (and chaperone signatures aren't used or are used with
   well known keys), but while it is better to avoid this where possible,
   it's something that's already easily dealt with simply by waiting
   for confirmations, and whether a transaction is malleable is always
   under the control of the sender not the receiver)

 * as such, output tagging is also unnecessary, and there is also no
   need for users to mark anyprevout spends as "tainted" in order to
   wait for more confirmations than normal before considering those funds
   "safe"

I think it might be good to have a public testnet (based on Richard Myers
et al's signet2 work?) where we have some fake exchanges/merchants/etc
and scheduled reorgs, and demo every weird noinput/anyprevout case anyone
can think of, and just work out if we need any extra code/tagging/whatever
to keep those fake exchanges/merchants from losing money (and write up
the weird cases we've found in a wiki or a paper so people can easily
tell if we missed something obvious).

Cheers,
aj

Re: [bitcoin-dev] Continuing the discussion about noinput / anyprevout

[ZmnSCPxj]

Good morning lists,

Let me propose the below radical idea:

* `SIGHASH` flags attached to signatures are a misdesign, sadly retained from the original BitCoin 0.1.0 Alpha for Windows design, on par with:
  * 1 RETURN
  * higher-`nSequence` replacement
  * DER-encoded pubkeys
  * unrestricted `scriptPubKey`
  * Payee-security-paid-by-payer (i.e. lack of P2SH)
  * `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
  * transaction malleability
  * probably many more

So let me propose the more radical excision, starting with SegWit v1:

* Remove `SIGHASH` from signatures.
* Put `SIGHASH` on public keys.

Public keys are now encoded as either 33-bytes (implicit `SIGHASH_ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type, followed by pubkey coordinate).
`OP_CHECKSIG` and friends then look at the *public key* to determine sighash algorithm rather than the signature.

As we expect public keys to be indirectly committed to on every output `scriptPubKey`, this is automatically output tagging to allow particular `SIGHASH`.
However, we can then utilize the many many ways to hide public keys away until they are needed, exemplified in MAST-inside-Taproot.

I propose also the addition of the opcode:

    <sighash> <pubkey> OP_SETPUBKEYSIGHASH

* `sighash` must be one byte.
* `pubkey` may be the special byte `0x1`, meaning "just use the Taproot internal pubkey".
* `pubkey` may be 33-byte public key, in which case the `sighash` byte is just prepended to it.
* `pubkey` may be 34-byte public key with sighash, in which case the first byte is replaced with `sighash` byte.
* If `sighash` is `0x00` then the result is a 33-byte public key (the sighash byte is removed) i.e. `SIGHASH_ALL` implicit.

This retains the old feature where the sighash is selected at time-of-spending rather than time-of-payment.
This is done by using the script:

    <pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG

Then the sighash can be put in the witness stack after the signature, letting the `SIGHASH` flag be selected at time-of-signing, but only if the SCRIPT specifically is formed to do so.
This is malleability-safe as the signature still commits to the `SIGHASH` it was created for.

However, by default, public keys will not have an attached `SIGHASH` byte, implying `SIGHASH_ALL` (and disallowing-by-default non-`SIGHASH_ALL`).

This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, as they are allowed only if the output specifically says they are allowed.

Would this not be a superior solution?

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Continuing the discussion about noinput / anyprevout

[s7r]

[-- Attachment #1.1: Type: text/plain, Size: 1721 bytes --]

Anthony Towns via bitcoin-dev wrote:
[SNIP]
> 
> My thinking at the moment (subject to change!) is:
> 
>  * anyprevout signatures make the address you're signing for less safe,
>    which may cause you to lose funds when additional coins are sent to
>    the same address; this can be avoided if handled with care (or if you
>    don't care about losing funds in the event of address reuse)
> 

It's not necessarily like this. Address re-use is many times OUTSIDE the
control of the address owner. Say I give my address to a counterparty.
They send me a transaction which I successfully spend. So far so good.

After that, I have no control over that counterparty. If they decide to
re-use that address, it does not mean I wanted to re-use it and it also
does not mean that I don't care about those funds being lost.

This could create a lot of problems in the industry and I think it
should be avoided. Address re-use has been strongly discouraged ever
since I can remember, and all (proper) wallet implementations try as
hard as possible to enforce it, but it's not always possible. A
counterparty that decides to re-use an address, either accidentally or
not, is not under the control of the user who handed out the address in
the first place.

There are also a lot of use cases with P2SH addresses that are some
smart contracts particularly designed to be re-used multiple times over
time.

My 2 cents are that this is not a good way to go. If you try to index
the entire blockchain until now you'll see that address re-use is more
common than we'd want it to be and there's no clear way to prevent this
from further happening without hurting the economic interests of the users.


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [bitcoin-dev] [Lightning-dev] Continuing the discussion about noinput / anyprevout

[Anthony Towns]

On Wed, Oct 02, 2019 at 02:03:43AM +0000, ZmnSCPxj via Lightning-dev wrote:
> So let me propose the more radical excision, starting with SegWit v1:
> * Remove `SIGHASH` from signatures.
> * Put `SIGHASH` on public keys.
>     <sighash> <pubkey> OP_SETPUBKEYSIGHASH

I don't think you could reasonably do this for key path spends -- if
you included the sighash as part of the scriptpubkey explicitly, that
would lose some of the indistinguishability of taproot addresses, and be
more expensive than having the sighash be in witness data. So I think
that means sighashes would still be included in key path signatures,
which would make the behaviour a little confusingly different between
signing for key path and script path spends.

> This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, as they are allowed only if the output specifically says they are allowed.

I don't think the problems with NONE and SINGLE are any worse than using
SIGHASH_ALL to pay to "1*G" -- someone may steal the money you send,
but that's as far as it goes. NOINPUT/ANYPREVOUT is worse in that if
you use it, someone may steal funds from other UTXOs too -- similar
to nonce-reuse. So I think having to commit to enabling NOINPUT for an
address may make sense; but I don't really see the need for doing the
same for other sighashes generally.

FWIW, one way of looking at a transaction spending UTXO "U" to address
"A" is something like:

 * "script" lets you enforce conditions on the transaction when you
   create "A" [0]
 * "sighash" lets you enforce conditions on the transaction when
   you sign the transaction
 * nlocktime, nsequence, taproot annex are ways you express conditions
   on the transaction

In that view, "sighash" is actually an *extremely* simple scripting
language itself (with a total of six possible scripts).

That doesn't seem like a bad design to me, fwiw.

Cheers,
aj

[0] "graftroot" lets you update those conditions for address "A" after
    the fact

Re: [bitcoin-dev] [Lightning-dev] Continuing the discussion about noinput / anyprevout

[ZmnSCPxj]

> > let me propose the more radical excision, starting with SegWit v1:
> >
> > -   Remove `SIGHASH` from signatures.
> > -   Put `SIGHASH` on public keys.
> >     <sighash> <pubkey> OP_SETPUBKEYSIGHASH
> >
>
> I don't think you could reasonably do this for key path spends -- if
> you included the sighash as part of the scriptpubkey explicitly, that
> would lose some of the indistinguishability of taproot addresses, and be
> more expensive than having the sighash be in witness data.

Nonexistence of sighash byte implies `SIGHASH_ALL`, and for offchain anyway the desired path is to end up with an n-of-n MuSig `SIGHASH_ALL` signed mutual close transaction.
Indeed we can even restrict keypath spends to not having a sighash byte and just implicitly requiring `SIGHASH_ALL` with no loss of privacy for offchain while attaining safety against `SIGHASH_NOINPUT` for MuSig and VSSS multisignature adresses.


> So I think
> that means sighashes would still be included in key path signatures,
> which would make the behaviour a little confusingly different between
> signing for key path and script path spends.
>
> > This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, as they are allowed only if the output specifically says they are allowed.
>
> I don't think the problems with NONE and SINGLE are any worse than using
> SIGHASH_ALL to pay to "1*G" -- someone may steal the money you send,
> but that's as far as it goes. NOINPUT/ANYPREVOUT is worse in that if
> you use it, someone may steal funds from other UTXOs too -- similar
> to nonce-reuse. So I think having to commit to enabling NOINPUT for an
> address may make sense; but I don't really see the need for doing the
> same for other sighashes generally.

As the existing sighashes are not particularly used anyway, additional restrictions on them are relatively immaterial.

>
> FWIW, one way of looking at a transaction spending UTXO "U" to address
> "A" is something like:
>
> -   "script" lets you enforce conditions on the transaction when you
>     create "A" [0]
>
> -   "sighash" lets you enforce conditions on the transaction when
>     you sign the transaction
>
> -   nlocktime, nsequence, taproot annex are ways you express conditions
>     on the transaction
>
>     In that view, "sighash" is actually an extremely simple scripting
>     language itself (with a total of six possible scripts).
>
>     That doesn't seem like a bad design to me, fwiw.


Only one of the scripts is widely used, another has an edge use it sucks at (assurance contracts).

Does not seem to be good design, rather legacy cruft.

Regards,
ZmnSCPxj

>
>     Cheers,
>     aj
>
>     [0] "graftroot" lets you update those conditions for address "A" after
>     the fact
>

Re: [bitcoin-dev] Continuing the discussion about noinput / anyprevout

[Christian Decker]

ZmnSCPxj <ZmnSCPxj@protonmail.com> writes:
>> That is very much how I was planning to implement it anyway, using a
>> trigger transaction to separate timeout start and the actual
>> update/settlement pairs (cfr. eltoo paper Section 4.2). So for eltoo
>> there shouldn't be an issue here :-)
>
> My understanding is that a trigger transaction is not in fact
> necessary for Decker-Russell-Osuntokun: any update transaction could
> spend the funding transaction output directly, and thereby start the
> relative timelock.  At least, if we could arrange the funding
> transaction output to be spendable directly using `SIGHASH_NOINPUT` or
> variants thereof.

This is the case in which we don't have a pre-signed settlement
transaction (or in this case refund transaction) that uses a relative
timelock. In order to have a refund transaction we would need to have
the first update and settlement pair be signed before funding (otherwise
the funder isn't sure she is getting her funds back). Since that first
update and settlement pair do not need to be rebound (they can only ever
be bound to the funding transaction) they can be signed without
noinput/anyprevoutanyscript. If we use output tagging we would mandate
that this first update must be published, so that the funding output is
indistinguishable from a normal output, and the first update switches
from non-noinput/anyprevoutanyscript to enabling it. Collaborative
closes are still indistinguishable, unilateral closes require the
switch, but then would be identifiable anyway.

The one downside I can see is that we now mandate that unilateral closes
also publish the first update, which is a bit annoying.

>> While I do agree that we should keep outputs as unidentifiable as
>> possible, I am starting to question whether that is possible for
>> off-chain payment networks since we are gossiping about the existence of
>> channels and binding them to outpoints to prove their existence anyway.
>
> * Lightning supports unpublished channels, so we do not gossip some outpoints even though they are in fact channels underneath.
>   * I confess the existence of unpublished channels in the spec fails to summon any reaction other than incredulity from me, but they exist nonetheless, my incredulity notwithstanding.

That is true, we do however selectively tell others about the channel's
existence (in invoices, our peers, ...) so I wouldn't consider that to
be the most secret information :-)

As for why they exist: nodes need to have the option of not announcing
their channels to reduce the noise in the network with channels that are
unlikely to be useable in order to forward payments. If every node were
to announce their channels we'd have a much larger routing table, mostly
consisting of unusable channels going to leafs in the
network. Furthermore, the sheer threat that there might be unannounced
channels adds uncertainty for attackers trying to profile nodes: "I see
only my channel with my peer, but he might have unannounced channels, so
I can't really tell whether the payment I forwarded to it is destined
for it or one of its unannounced peers".

> * Historical channels that have been cooperatively closed are no longer normally gossiped, so the fact that they used to be channels is no longer widely broadcast, and may eventually be forgotten by most or all of the network.
>   * This means anyone who wants to record the historical use of Lightning will have to retain the information themselves, rather than delegating it to fullnodes everywhere.

Good point, it requires storing the ephemeral data from gossip, that's
not all that hard, but I agree that it puts up a small barrier for
newcomers.

Re: [bitcoin-dev] [Lightning-dev] Continuing the discussion about noinput / anyprevout

[Christian Decker]

Chris Stewart <chris@suredbits.com> writes:

> I do have some concerns about SIGHASH_NOINPUT, mainly that it does
> introduce another footgun into the bitcoin protocol with address reuse.
> It's common practice for bitcoin businesses to re-use addresses. Many
> exchanges [1] reuse addresses for cold storage with very large sums of
> money that is stored in these addreses.
>
> It is my understanding with this part of BIP118
>
>>Using NOINPUT the input containing the signature no longer references a
> specific output. Any participant can take a transaction and rewrite it by
> changing the hash reference to the previous output, without invalidating
> the signatures. This allows transactions to be bound to any output that
> matches the value committed to in the witness and whose witnessProgram,
> combined with the spending transaction's witness returns true.
>
> if an exchange were to once produce a digital signature from that cold
> storage address with a SIGHASH_NOINPUT signature, that signature can be
> replayed again and again on the blockchain until their wallet is drained.
> This might be able to mitigated since the signatures commit to outputs,
> which may be small in value for the transaction that SIGHASH_NOINPUT was
> used. This means that an exchange could move coins from the address with a
> larger transaction that spends money to a new output (and presumably pays a
> higher fee than the smaller transactions).

Thanks for sharing your concerns Chris, I do agree that noinput and
friends are a very sharp knife that needs to be treated carefully, but
ultimately it's exactly its sharpness that makes it useful :-)

> ### Why does this matter?
>
> It seems that SIGHASH_NOINPUT will be an extremely useful tool for offchain
> protocols like Lightning. This gives us the building blocks for enforcing
> specific offchain states to end up onchain [2].
>
> Since this tool is useful, we can presume that it will be integrated into
> the signing path of large economic entities in bitcoin -- namely exchanges.
> Many exchanges have specific signing procedures for transactions that are
> leaving an exchange that is custom software. Now -- presuming wide adoption
> of off chain protocols -- they will need to have a _second unique signing
> path that uses SIGHASH_NOINPUT_.
>
> It is imperative that this second signing path -- which uses
> SIGHASH_NOINPUT -- does NOT get mixed up with the first signing path that
> controls an exchanges onchain funds. If this were to happen, fund lost
> could occur if the exchange is reusing address, which seems to be common
> practice.

Totally agreed, and as you point out, BIP118 is careful to mandate
separate private keys be used for off-chain contracts and that the
off-chain contract never be mixed with the remainder of your funds. The
way eltoo uses noinput we selectively open us up to replay attacks
(because that's what the update mechanism is after all) by controlling
the way the transactions can be replayed very carefully, and any other
use of noinput would need to make sure to have the same guarantees.
However, once we have separated the two domains, we can simply use a
separate (hardened) derivation path from a seed key, and never mix them
afterwards. We never exchange any private keys, so even leaking info
across derived keys is not an issue here.

> This is stated here in BIP118:
>
>>This also means that particular care has to be taken in order to avoid
> unintentionally enabling this rebinding mechanism. NOINPUT MUST NOT be
> used, unless it is explicitly needed for the application, e.g., it MUST NOT
> be a default signing flag in a wallet implementation. Rebinding is only
> possible when the outputs the transaction may bind to all use the same
> public keys. Any public key that is used in a NOINPUT signature MUST only
> be used for outputs that the input may bind to, and they MUST NOT be used
> for transactions that the input may not bind to. For example an application
> SHOULD generate a new key-pair for the application instance using NOINPUT
> signatures and MUST NOT reuse them afterwards.
>
> This means we need to encourage onchain hot wallet signing procedures to be
> kept separate from offchain hot wallet signing procedures, which introduces
> more complexity for key management (two keychains).

This is already the case: off-chain systems always require access to the
signing key in real-time in order to be useful. If any state change is
performed in a channel, even just adjusting fees or receiving a payment,
requires the signature from the key associated with the channel. With
high security on-chain systems on the other hand you should never have a
hot key that automatically signs off on transfers without human
intervention. So I find it unlikely that mandating the on-chain keys to
be kept separate from off-chain keys is any harder than what should be
done with the current systems.

> One (of the few) upsides of the current Lightning penalty mechanism is that
> fund loss can be contained to balance of the channel. You cannot do
> something in the current protocol that will effect your funds outside of
> that channel. With SIGHASH_NOINPUT, that property changes.

Good point, but if the key hygiene is maintained as detailed in BIP118,
i.e., off-chain keys must be kept separate from on-chain keys, and that
each off-chain contract instance uses a separate set of keys, that
property is maintained.

Regards,
Christian

Re: [bitcoin-dev] [Lightning-dev] Continuing the discussion about noinput / anyprevout

[Christian Decker]

ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> writes:

> Good morning lists,
>
> Let me summarize concerns brought up:
>
> * Chris concern, is that an ordinary UTXO that is not allocated for `SIGHASH_NOINPUT` use, is inadvertently spent using `SIGHASH_NOINPUT`.
> * My concern, is that unless a UTXO allocated for `SIGHASH_NOINPUT` use, is *indeed* used with SIGHASH_NOINPUT`, it should look exactly the same as any other SegWit v1 output.
>
> I propose the below instead:
>
> * Do ***NOT*** allocate SegWit v16 for `SIGHASH_NOINPUT`.
> * Instead, allocate SegWit v1 Tapscript v16 for `SIGHASH_NOINPUT`.
>
> Then, on usage:
>
> * Exchange hoards can be protected by simple MuSig bip-schnorr SegWit v1 outputs, or a NUMS Taproot internal point with a MAST branch Tapscript v0 `OP_CHECKSIG_ADD` sequence.
> * Decker-Russell-Osuntokun constructions are backed by a n-of-n MuSig Taproot internal point, with a MAST branch containing a Tapscript v16 with `OP_1 OP_CHECKSIG`.
>
> This solves both concerns:
>
> * Ordinary UTXOs not allocated for `SIGHASH_NOINPUT` use simply do not commit to any Taproot that has a Tapscript v16 branch, and thus `SIGHASH_NOINPUT` is unuseable to claim it.
> * If a UTXO used for an offchain protocol ends up in a cooperative-resolution state, nobody has to know that a Tapscript v16 branch existed that could have used `SIGHASH_NOINPUT`.
>
> Again, my objection to output tagging is that it is **publicly visible** as soon as the funding transaction is confirmed onchain that this is a special output used for a Decker-Russell-Osuntokun construction, greatly damaging privacy.
> But if this fact is kept secret *unless* the very specific case of unilateral uncooperative enforcement, then it is quite fine with me.
>
> Would this alternate proposal hold better muster?

Intriguing idea, this would be an invisible tagging, since the opt-in to
noinput and friends is hidden inside the committed script, which only
gets revealed whenever we actually need it.

For eltoo this would mean that the funding output would be invisibly
tagged, and the cooperative close would use the taproot pubkey, while
the uncooperative close, which would require noinput opt-in, reveals the
script, proving prior opt-in, and provides a matching signature.

If I'm not mistaken this would require AJ's alternative pubkey encoding
(0x01 or 0x00 prefixed pubkey) to make the opt-in visible, correct?

Re: [bitcoin-dev] [Lightning-dev] Continuing the discussion about noinput / anyprevout

[Christian Decker]

Chris Stewart <chris@suredbits.com> writes:

>> I don't find too compelling the potential problem of a 'bad wallet
> designer', whether lazy or dogmatic, misusing noinput. I think there are
> simpler ways to cut corners and there will always be plenty of good wallet
> options people can choose.
>
> In my original post, the business that I am talking about don't use "off
> the shelf" wallet options. It isn't a "let's switch from wallet A to wallet
> B" kind of situation. Usually this involves design from ground up with
> security considerations that businesses of scale need to consider (signing
> procedures and key handling being the most important!).

In this case I'd hope that the custom wallet designers/developers are
well-versed in the issues they might encounter when implementing their
wallet. This is especially true if they decide to opt into using some
lesser known sighash flags, such as noinput, that come with huge warning
signs (I forgot to mention that renaming noinput to noinput_dangerous is
also still on the table).

>>Because scripts signed with no_input signatures are only really exchanged
> and used for off-chain negotiations, very few should ever appear on chain.
> Those that do should represent non-cooperative situations that involve
> signing parties who know not to reuse or share scripts with these public
> keys again. No third party has any reason to spend value to a
> multisignature script they don't control, whether or not a no_input
> signature exists for it.
>
> Just because some one is your friend today, doesn't mean they aren't
> necessarily your adversary tomorrow. I don't think a signature being
> onchain really matters, as you have to give it to your counterparty
> regardless. How do you know your counterparty won't replay that
> SIGHASH_NOINPUT signature later? Offchain protocols shouldn't rely on
> "good-will" for their counter parties for security.
>
>>As I mentioned before, I don't think the lazy wallet designer advantage is
> enough to justify the downsides of chaperone signatures. One additional
> downside is the additional code complexity required to flag whether or not
> a chaperone output is included. By comparison, the code changes for
> creating a no_input digest that skips the prevout and prevscript parts of a
> tx is much less intrusive and easier to maintain.
>
>>I want to second this. The most expensive part of wallet design is
> engineering time. Writing code that uses a new sighash or a custom
> script with a OP_CODE is a very large barrier to use. How many wallets
> support multisig or RBF? How much BTC has been stolen over the entire
> history of Bitcoin because of sighash SIGHASH_NONE or SIGHASH_SINGLE
> vs ECDSA nonce reuse
>
> I actually think lazy wallet designer is a really compelling reason to fix
> footguns in the bitcoin protocol. Mt Gox is allegedly a product of lazy
> wallet design. Now we have non-malleable transactions in the form of segwit
> (yay!) that prevent this exploit. We can wish that the Mt Gox wallet
> designers were more aware of bitcoin protocol vulnerabilities, but at the
> end of the day the best thing to do was offering an alternative that
> circumvents the vulnerability all together.

It's worth pointing out that the transaction malleability issue and the
introduction of a new sighash flag are fundamentally different: a wallet
developer has to take active measures to guard against transaction
malleability since it was present even for the most minimal
implementation, whereas with sighash flags the developers have to
actively add support for it. Where transaction malleability you just had
to know that it might be an issue, with noinput you actively have to do
work yo expose yourself to it.

I'd argue that you have to have a very compelling reason to opt into
supporting noinput, and that's usually because you want to support a
more complex protocol such as an off-chain contract anyway, at which
point I'd hope you know about the tradeoffs of various sighash flags :-)

> Ethan made a great point about SIGHASH_NONE or SIGHASH_SINGLE -- which have
> virtually no use AFAIK -- vs the ECDSA nonce reuse which is used in nearly
> every transaction. The feature -- ECDSA in this case -- was managed to be
> done wrong by wallet developers causing fund loss. Unfortunately we can't
> protect against this type of bug in the protocol.
>
> If things aren't used -- such as SIGHASH_NONE or SIGHASH_SINGLE -- it
> doesn't matter if they are secure or insecure. I'm hopefully that offchain
> protocols will achieve wide adoption, and I would hate to see money lost
> because of this. Even though they aren't used, in my OP I do advocate for
> fixing these.

I do share the feeling that we better make a commonly used sighash flag
as useable and safe as possible, but it's rather unrealistic to have a
developer that is able to implement a complex off-chain system, but
fails to understand the importance of using the correct sighash flags in
their wallet. That being said, I think this concern would be addressed
by any form of explicit opt-in on the output side (whether hidden or
not), right?


Cheers,
Christian

Re: [bitcoin-dev] Continuing the discussion about noinput / anyprevout

[Christian Decker]

Anthony Towns <aj@erisian.com.au> writes:

> On Mon, Sep 30, 2019 at 03:23:56PM +0200, Christian Decker via bitcoin-dev wrote:
>> With the recently renewed interest in eltoo, a proof-of-concept implementation
>> [1], and the discussions regarding clean abstractions for off-chain protocols
>> [2,3], I thought it might be time to revisit the `sighash_noinput` proposal
>> (BIP-118 [4]), and AJ's `bip-anyprevout` proposal [5].
>
> Hey Christian, thanks for the write up!
>
>> ## Open questions
>> The questions that remain to be addressed are the following:
>> 1.  General agreement on the usefulness of noinput / anyprevoutanyscript /
>>     anyprevout[?]
>> 2.  Is there strong support or opposition to the chaperone signatures[?]
>> 3.  The same for output tagging / explicit opt-in[?]
>> 4.  Shall we merge BIP-118 and bip-anyprevout. This would likely reduce the
>>     confusion and make for simpler discussions in the end.
>
> I think there's an important open question you missed from this list:
> (1.5) do we really understand what the dangers of noinput/anyprevout-style
> constructions actually are?
>
> My impression on the first 3.5 q's is: (1) yes, (1.5) not really,
> (2) weak opposition for requiring chaperone sigs, (3) mixed (weak)
> support/opposition for output tagging.
>
> My thinking at the moment (subject to change!) is:
>
>  * anyprevout signatures make the address you're signing for less safe,
>    which may cause you to lose funds when additional coins are sent to
>    the same address; this can be avoided if handled with care (or if you
>    don't care about losing funds in the event of address reuse)
>
>  * being able to guarantee that an address can never be signed for with
>    an anyprevout signature is therefore valuable; so having it be opt-in
>    at the tapscript level, rather than a sighash flag available for
>    key-path spends is valuable (I call this "opt-in", but it's hidden
>    until use via taproot rather than "explicit" as output tagging
>    would be)
>
>  * receiving funds spent via an anyprevout signature does not involve any
>    qualitatively new double-spending/malleability risks.
>    
>    (eltoo is unavoidably malleable if there are multiple update
>    transactions (and chaperone signatures aren't used or are used with
>    well known keys), but while it is better to avoid this where possible,
>    it's something that's already easily dealt with simply by waiting
>    for confirmations, and whether a transaction is malleable is always
>    under the control of the sender not the receiver)
>
>  * as such, output tagging is also unnecessary, and there is also no
>    need for users to mark anyprevout spends as "tainted" in order to
>    wait for more confirmations than normal before considering those funds
>    "safe"

Excellent points, I had missed the hidden nature of the opt-in via
pubkey prefix while reading your proposal. I'm starting to like that
option more and more. In that case we'd only ever be revealing that we
opted into anyprevout when we're revealing the entire script anyway, at
which point all fungibility concerns go out the window anyway.

Would this scheme be extendable to opt into all sighash flags the
outpoint would like to allow (e.g., adding opt-in for sighash_none and
sighash_anyonecanpay as well)? That way the pubkey prefix could act as a
mask for the sighash flags and fail verification if they don't match.

> I think it might be good to have a public testnet (based on Richard Myers
> et al's signet2 work?) where we have some fake exchanges/merchants/etc
> and scheduled reorgs, and demo every weird noinput/anyprevout case anyone
> can think of, and just work out if we need any extra code/tagging/whatever
> to keep those fake exchanges/merchants from losing money (and write up
> the weird cases we've found in a wiki or a paper so people can easily
> tell if we missed something obvious).

That'd be great, however even that will not ensure that every possible
corner case is handled and from experience it seems that people are
unwilling to invest a lot of time testing on a network unless their
money is on the line. That's not to say that we shouldn't try, we
absolutely should, I'm just not sure it alone is enough to dispell all
remaining doubts :-)

Cheers,
Christian

[bitcoin-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Ethan Heilman]

To avoid derailing the NO_INPUT conversation, I have changed the
subject to OP_CAT.

Responding to:
"""
* `SIGHASH` flags attached to signatures are a misdesign, sadly
retained from the original BitCoin 0.1.0 Alpha for Windows design, on
par with:
[..]
* `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
[..]
"""

OP_CAT is an extremely valuable op code. I understand why it was
removed as the situation at the time with scripts was dire. However
most of the protocols I've wanted to build on Bitcoin run into the
limitation that stack values can not be concatenated. For instance
TumbleBit would have far smaller transaction sizes if OP_CAT was
supported in Bitcoin. If it happens to me as a researcher it is
probably holding other people back as well. If I could wave a magic
wand and turn on one of the disabled op codes it would be OP_CAT.  Of
course with the change that size of each concatenated value must be 64
Bytes or less.


On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> Good morning lists,
>
> Let me propose the below radical idea:
>
> * `SIGHASH` flags attached to signatures are a misdesign, sadly retained from the original BitCoin 0.1.0 Alpha for Windows design, on par with:
>   * 1 RETURN
>   * higher-`nSequence` replacement
>   * DER-encoded pubkeys
>   * unrestricted `scriptPubKey`
>   * Payee-security-paid-by-payer (i.e. lack of P2SH)
>   * `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
>   * transaction malleability
>   * probably many more
>
> So let me propose the more radical excision, starting with SegWit v1:
>
> * Remove `SIGHASH` from signatures.
> * Put `SIGHASH` on public keys.
>
> Public keys are now encoded as either 33-bytes (implicit `SIGHASH_ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type, followed by pubkey coordinate).
> `OP_CHECKSIG` and friends then look at the *public key* to determine sighash algorithm rather than the signature.
>
> As we expect public keys to be indirectly committed to on every output `scriptPubKey`, this is automatically output tagging to allow particular `SIGHASH`.
> However, we can then utilize the many many ways to hide public keys away until they are needed, exemplified in MAST-inside-Taproot.
>
> I propose also the addition of the opcode:
>
>     <sighash> <pubkey> OP_SETPUBKEYSIGHASH
>
> * `sighash` must be one byte.
> * `pubkey` may be the special byte `0x1`, meaning "just use the Taproot internal pubkey".
> * `pubkey` may be 33-byte public key, in which case the `sighash` byte is just prepended to it.
> * `pubkey` may be 34-byte public key with sighash, in which case the first byte is replaced with `sighash` byte.
> * If `sighash` is `0x00` then the result is a 33-byte public key (the sighash byte is removed) i.e. `SIGHASH_ALL` implicit.
>
> This retains the old feature where the sighash is selected at time-of-spending rather than time-of-payment.
> This is done by using the script:
>
>     <pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG
>
> Then the sighash can be put in the witness stack after the signature, letting the `SIGHASH` flag be selected at time-of-signing, but only if the SCRIPT specifically is formed to do so.
> This is malleability-safe as the signature still commits to the `SIGHASH` it was created for.
>
> However, by default, public keys will not have an attached `SIGHASH` byte, implying `SIGHASH_ALL` (and disallowing-by-default non-`SIGHASH_ALL`).
>
> This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, as they are allowed only if the output specifically says they are allowed.
>
> Would this not be a superior solution?
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[ZmnSCPxj]

Good morning Ethan,


> To avoid derailing the NO_INPUT conversation, I have changed the
> subject to OP_CAT.
>
> Responding to:
> """
>
> -   `SIGHASH` flags attached to signatures are a misdesign, sadly
>     retained from the original BitCoin 0.1.0 Alpha for Windows design, on
>     par with:
>     [..]
>
> -   `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
>     [..]
>     """
>
>     OP_CAT is an extremely valuable op code. I understand why it was
>     removed as the situation at the time with scripts was dire. However
>     most of the protocols I've wanted to build on Bitcoin run into the
>     limitation that stack values can not be concatenated. For instance
>     TumbleBit would have far smaller transaction sizes if OP_CAT was
>     supported in Bitcoin. If it happens to me as a researcher it is
>     probably holding other people back as well. If I could wave a magic
>     wand and turn on one of the disabled op codes it would be OP_CAT. Of
>     course with the change that size of each concatenated value must be 64
>     Bytes or less.

Why 64 bytes in particular?

It seems obvious to me that this 64 bytes is most suited for building Merkle trees, being the size of two SHA256 hashes.

However we have had issues with the use of Merkle trees in Bitcoin blocks.
Specifically, it is difficult to determine if a hash on a Merkle node is the hash of a Merkle subnode, or a leaf transaction.
My understanding is that this is the reason for now requiring transactions to be at least 80 bytes.

The obvious fix would be to prepend the type of the hashed object, i.e. add at least one byte to determine this type.
Taproot for example uses tagged hash functions, with a different tag for leaves, and tagged hashes are just prepend-this-32-byte-constant-twice-before-you-SHA256.

This seems to indicate that to check merkle tree proofs, an `OP_CAT` with only 64 bytes max output size would not be sufficient.

Or we could implement tagged SHA256 as a new opcode...

Regards,
ZmnSCPxj


>
>     On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bitcoin-dev
>     bitcoin-dev@lists.linuxfoundation.org wrote:
>
>
> > Good morning lists,
> > Let me propose the below radical idea:
> >
> > -   `SIGHASH` flags attached to signatures are a misdesign, sadly retained from the original BitCoin 0.1.0 Alpha for Windows design, on par with:
> >     -   1 RETURN
> >     -   higher-`nSequence` replacement
> >     -   DER-encoded pubkeys
> >     -   unrestricted `scriptPubKey`
> >     -   Payee-security-paid-by-payer (i.e. lack of P2SH)
> >     -   `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> >     -   transaction malleability
> >     -   probably many more
> >
> > So let me propose the more radical excision, starting with SegWit v1:
> >
> > -   Remove `SIGHASH` from signatures.
> > -   Put `SIGHASH` on public keys.
> >
> > Public keys are now encoded as either 33-bytes (implicit `SIGHASH_ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type, followed by pubkey coordinate).
> > `OP_CHECKSIG` and friends then look at the public key to determine sighash algorithm rather than the signature.
> > As we expect public keys to be indirectly committed to on every output `scriptPubKey`, this is automatically output tagging to allow particular `SIGHASH`.
> > However, we can then utilize the many many ways to hide public keys away until they are needed, exemplified in MAST-inside-Taproot.
> > I propose also the addition of the opcode:
> >
> >     <sighash> <pubkey> OP_SETPUBKEYSIGHASH
> >
> >
> > -   `sighash` must be one byte.
> > -   `pubkey` may be the special byte `0x1`, meaning "just use the Taproot internal pubkey".
> > -   `pubkey` may be 33-byte public key, in which case the `sighash` byte is just prepended to it.
> > -   `pubkey` may be 34-byte public key with sighash, in which case the first byte is replaced with `sighash` byte.
> > -   If `sighash` is `0x00` then the result is a 33-byte public key (the sighash byte is removed) i.e. `SIGHASH_ALL` implicit.
> >
> > This retains the old feature where the sighash is selected at time-of-spending rather than time-of-payment.
> > This is done by using the script:
> >
> >     <pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG
> >
> >
> > Then the sighash can be put in the witness stack after the signature, letting the `SIGHASH` flag be selected at time-of-signing, but only if the SCRIPT specifically is formed to do so.
> > This is malleability-safe as the signature still commits to the `SIGHASH` it was created for.
> > However, by default, public keys will not have an attached `SIGHASH` byte, implying `SIGHASH_ALL` (and disallowing-by-default non-`SIGHASH_ALL`).
> > This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, as they are allowed only if the output specifically says they are allowed.
> > Would this not be a superior solution?
> > Regards,
> > ZmnSCPxj
> >
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Ethan Heilman]

I hope you are having an great afternoon ZmnSCPxj,

You make an excellent point!

I had thought about doing the following to tag nodes

|| means OP_CAT

`node = SHA256(type||SHA256(data))`
so a subnode would be
`subnode1 = SHA256(1||SHA256(subnode2||subnode3))`
and a leaf node would be
`leafnode = SHA256(0||SHA256(leafdata))`

Yet, I like your idea better. Increasing the size of the two inputs to
OP_CAT to be 260 Bytes each where 520 Bytes is the maximum allowable
size of object on the stack seems sensible and also doesn't special
case the logic of OP_CAT.

It would also increase performance. SHA256(tag||subnode2||subnode3)
requires 2 compression function calls whereas
SHA256(1||SHA256(subnode2||subnode3)) requires 2+1=3 compression
function calls (due to padding).

>Or we could implement tagged SHA256 as a new opcode...

I agree that tagged SHA256 as an op code that would certainty be
useful, but OP_CAT provides far more utility and is a simpler change.

Thanks,
Ethan

On Thu, Oct 3, 2019 at 7:42 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> Good morning Ethan,
>
>
> > To avoid derailing the NO_INPUT conversation, I have changed the
> > subject to OP_CAT.
> >
> > Responding to:
> > """
> >
> > -   `SIGHASH` flags attached to signatures are a misdesign, sadly
> >     retained from the original BitCoin 0.1.0 Alpha for Windows design, on
> >     par with:
> >     [..]
> >
> > -   `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> >     [..]
> >     """
> >
> >     OP_CAT is an extremely valuable op code. I understand why it was
> >     removed as the situation at the time with scripts was dire. However
> >     most of the protocols I've wanted to build on Bitcoin run into the
> >     limitation that stack values can not be concatenated. For instance
> >     TumbleBit would have far smaller transaction sizes if OP_CAT was
> >     supported in Bitcoin. If it happens to me as a researcher it is
> >     probably holding other people back as well. If I could wave a magic
> >     wand and turn on one of the disabled op codes it would be OP_CAT. Of
> >     course with the change that size of each concatenated value must be 64
> >     Bytes or less.
>
> Why 64 bytes in particular?
>
> It seems obvious to me that this 64 bytes is most suited for building Merkle trees, being the size of two SHA256 hashes.
>
> However we have had issues with the use of Merkle trees in Bitcoin blocks.
> Specifically, it is difficult to determine if a hash on a Merkle node is the hash of a Merkle subnode, or a leaf transaction.
> My understanding is that this is the reason for now requiring transactions to be at least 80 bytes.
>
> The obvious fix would be to prepend the type of the hashed object, i.e. add at least one byte to determine this type.
> Taproot for example uses tagged hash functions, with a different tag for leaves, and tagged hashes are just prepend-this-32-byte-constant-twice-before-you-SHA256.
>
> This seems to indicate that to check merkle tree proofs, an `OP_CAT` with only 64 bytes max output size would not be sufficient.
>
> Or we could implement tagged SHA256 as a new opcode...
>
> Regards,
> ZmnSCPxj
>
>
> >
> >     On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bitcoin-dev
> >     bitcoin-dev@lists.linuxfoundation.org wrote:
> >
> >
> > > Good morning lists,
> > > Let me propose the below radical idea:
> > >
> > > -   `SIGHASH` flags attached to signatures are a misdesign, sadly retained from the original BitCoin 0.1.0 Alpha for Windows design, on par with:
> > >     -   1 RETURN
> > >     -   higher-`nSequence` replacement
> > >     -   DER-encoded pubkeys
> > >     -   unrestricted `scriptPubKey`
> > >     -   Payee-security-paid-by-payer (i.e. lack of P2SH)
> > >     -   `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > >     -   transaction malleability
> > >     -   probably many more
> > >
> > > So let me propose the more radical excision, starting with SegWit v1:
> > >
> > > -   Remove `SIGHASH` from signatures.
> > > -   Put `SIGHASH` on public keys.
> > >
> > > Public keys are now encoded as either 33-bytes (implicit `SIGHASH_ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type, followed by pubkey coordinate).
> > > `OP_CHECKSIG` and friends then look at the public key to determine sighash algorithm rather than the signature.
> > > As we expect public keys to be indirectly committed to on every output `scriptPubKey`, this is automatically output tagging to allow particular `SIGHASH`.
> > > However, we can then utilize the many many ways to hide public keys away until they are needed, exemplified in MAST-inside-Taproot.
> > > I propose also the addition of the opcode:
> > >
> > >     <sighash> <pubkey> OP_SETPUBKEYSIGHASH
> > >
> > >
> > > -   `sighash` must be one byte.
> > > -   `pubkey` may be the special byte `0x1`, meaning "just use the Taproot internal pubkey".
> > > -   `pubkey` may be 33-byte public key, in which case the `sighash` byte is just prepended to it.
> > > -   `pubkey` may be 34-byte public key with sighash, in which case the first byte is replaced with `sighash` byte.
> > > -   If `sighash` is `0x00` then the result is a 33-byte public key (the sighash byte is removed) i.e. `SIGHASH_ALL` implicit.
> > >
> > > This retains the old feature where the sighash is selected at time-of-spending rather than time-of-payment.
> > > This is done by using the script:
> > >
> > >     <pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG
> > >
> > >
> > > Then the sighash can be put in the witness stack after the signature, letting the `SIGHASH` flag be selected at time-of-signing, but only if the SCRIPT specifically is formed to do so.
> > > This is malleability-safe as the signature still commits to the `SIGHASH` it was created for.
> > > However, by default, public keys will not have an attached `SIGHASH` byte, implying `SIGHASH_ALL` (and disallowing-by-default non-`SIGHASH_ALL`).
> > > This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, as they are allowed only if the output specifically says they are allowed.
> > > Would this not be a superior solution?
> > > Regards,
> > > ZmnSCPxj
> > >
> > > bitcoin-dev mailing list
> > > bitcoin-dev@lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> > Lightning-dev mailing list
> > Lightning-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 7674 bytes --]

Awhile back, Ethan and I discussed having, rather than OP_CAT, an
OP_SHA256STREAM that uses the streaming properties of a SHA256 hash
function to allow concatenation of an unlimited amount of data, provided
the only use is to hash it.

You can then use it perhaps as follows:

// start a new hash with item
OP_SHA256STREAM  (-1) -> [state]
// Add item to the hash in state
OP_SHA256STREAM n [item] [state] -> [state]
// Finalize
OP_SHA256STREAM (-2) [state] -> [Hash]

<-1> OP_SHA256STREAM <tag> <subnode 2> <subnode 3> <3> OP_SHA256STREAM <-2>
OP_SHA256STREAM


Or it coul



--
@JeremyRubin <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>


On Thu, Oct 3, 2019 at 8:04 PM Ethan Heilman <eth3rs@gmail.com> wrote:

> I hope you are having an great afternoon ZmnSCPxj,
>
> You make an excellent point!
>
> I had thought about doing the following to tag nodes
>
> || means OP_CAT
>
> `node = SHA256(type||SHA256(data))`
> so a subnode would be
> `subnode1 = SHA256(1||SHA256(subnode2||subnode3))`
> and a leaf node would be
> `leafnode = SHA256(0||SHA256(leafdata))`
>
> Yet, I like your idea better. Increasing the size of the two inputs to
> OP_CAT to be 260 Bytes each where 520 Bytes is the maximum allowable
> size of object on the stack seems sensible and also doesn't special
> case the logic of OP_CAT.
>
> It would also increase performance. SHA256(tag||subnode2||subnode3)
> requires 2 compression function calls whereas
> SHA256(1||SHA256(subnode2||subnode3)) requires 2+1=3 compression
> function calls (due to padding).
>
> >Or we could implement tagged SHA256 as a new opcode...
>
> I agree that tagged SHA256 as an op code that would certainty be
> useful, but OP_CAT provides far more utility and is a simpler change.
>
> Thanks,
> Ethan
>
> On Thu, Oct 3, 2019 at 7:42 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
> >
> > Good morning Ethan,
> >
> >
> > > To avoid derailing the NO_INPUT conversation, I have changed the
> > > subject to OP_CAT.
> > >
> > > Responding to:
> > > """
> > >
> > > -   `SIGHASH` flags attached to signatures are a misdesign, sadly
> > >     retained from the original BitCoin 0.1.0 Alpha for Windows design,
> on
> > >     par with:
> > >     [..]
> > >
> > > -   `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > >     [..]
> > >     """
> > >
> > >     OP_CAT is an extremely valuable op code. I understand why it was
> > >     removed as the situation at the time with scripts was dire. However
> > >     most of the protocols I've wanted to build on Bitcoin run into the
> > >     limitation that stack values can not be concatenated. For instance
> > >     TumbleBit would have far smaller transaction sizes if OP_CAT was
> > >     supported in Bitcoin. If it happens to me as a researcher it is
> > >     probably holding other people back as well. If I could wave a magic
> > >     wand and turn on one of the disabled op codes it would be OP_CAT.
> Of
> > >     course with the change that size of each concatenated value must
> be 64
> > >     Bytes or less.
> >
> > Why 64 bytes in particular?
> >
> > It seems obvious to me that this 64 bytes is most suited for building
> Merkle trees, being the size of two SHA256 hashes.
> >
> > However we have had issues with the use of Merkle trees in Bitcoin
> blocks.
> > Specifically, it is difficult to determine if a hash on a Merkle node is
> the hash of a Merkle subnode, or a leaf transaction.
> > My understanding is that this is the reason for now requiring
> transactions to be at least 80 bytes.
> >
> > The obvious fix would be to prepend the type of the hashed object, i.e.
> add at least one byte to determine this type.
> > Taproot for example uses tagged hash functions, with a different tag for
> leaves, and tagged hashes are just
> prepend-this-32-byte-constant-twice-before-you-SHA256.
> >
> > This seems to indicate that to check merkle tree proofs, an `OP_CAT`
> with only 64 bytes max output size would not be sufficient.
> >
> > Or we could implement tagged SHA256 as a new opcode...
> >
> > Regards,
> > ZmnSCPxj
> >
> >
> > >
> > >     On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bitcoin-dev
> > >     bitcoin-dev@lists.linuxfoundation.org wrote:
> > >
> > >
> > > > Good morning lists,
> > > > Let me propose the below radical idea:
> > > >
> > > > -   `SIGHASH` flags attached to signatures are a misdesign, sadly
> retained from the original BitCoin 0.1.0 Alpha for Windows design, on par
> with:
> > > >     -   1 RETURN
> > > >     -   higher-`nSequence` replacement
> > > >     -   DER-encoded pubkeys
> > > >     -   unrestricted `scriptPubKey`
> > > >     -   Payee-security-paid-by-payer (i.e. lack of P2SH)
> > > >     -   `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > > >     -   transaction malleability
> > > >     -   probably many more
> > > >
> > > > So let me propose the more radical excision, starting with SegWit v1:
> > > >
> > > > -   Remove `SIGHASH` from signatures.
> > > > -   Put `SIGHASH` on public keys.
> > > >
> > > > Public keys are now encoded as either 33-bytes (implicit
> `SIGHASH_ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type,
> followed by pubkey coordinate).
> > > > `OP_CHECKSIG` and friends then look at the public key to determine
> sighash algorithm rather than the signature.
> > > > As we expect public keys to be indirectly committed to on every
> output `scriptPubKey`, this is automatically output tagging to allow
> particular `SIGHASH`.
> > > > However, we can then utilize the many many ways to hide public keys
> away until they are needed, exemplified in MAST-inside-Taproot.
> > > > I propose also the addition of the opcode:
> > > >
> > > >     <sighash> <pubkey> OP_SETPUBKEYSIGHASH
> > > >
> > > >
> > > > -   `sighash` must be one byte.
> > > > -   `pubkey` may be the special byte `0x1`, meaning "just use the
> Taproot internal pubkey".
> > > > -   `pubkey` may be 33-byte public key, in which case the `sighash`
> byte is just prepended to it.
> > > > -   `pubkey` may be 34-byte public key with sighash, in which case
> the first byte is replaced with `sighash` byte.
> > > > -   If `sighash` is `0x00` then the result is a 33-byte public key
> (the sighash byte is removed) i.e. `SIGHASH_ALL` implicit.
> > > >
> > > > This retains the old feature where the sighash is selected at
> time-of-spending rather than time-of-payment.
> > > > This is done by using the script:
> > > >
> > > >     <pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG
> > > >
> > > >
> > > > Then the sighash can be put in the witness stack after the
> signature, letting the `SIGHASH` flag be selected at time-of-signing, but
> only if the SCRIPT specifically is formed to do so.
> > > > This is malleability-safe as the signature still commits to the
> `SIGHASH` it was created for.
> > > > However, by default, public keys will not have an attached `SIGHASH`
> byte, implying `SIGHASH_ALL` (and disallowing-by-default non-`SIGHASH_ALL`).
> > > > This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, as
> they are allowed only if the output specifically says they are allowed.
> > > > Would this not be a superior solution?
> > > > Regards,
> > > > ZmnSCPxj
> > > >
> > > > bitcoin-dev mailing list
> > > > bitcoin-dev@lists.linuxfoundation.org
> > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> > >
> > > Lightning-dev mailing list
> > > Lightning-dev@lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
> >
> >
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>

[-- Attachment #2: Type: text/html, Size: 12201 bytes --]

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[ZmnSCPxj]

Good morning Jeremy,

> Awhile back, Ethan and I discussed having, rather than OP_CAT, an OP_SHA256STREAM that uses the streaming properties of a SHA256 hash function to allow concatenation of an unlimited amount of data, provided the only use is to hash it.
>
> You can then use it perhaps as follows:
>
> // start a new hash with item
> OP_SHA256STREAM  (-1) -> [state]
> // Add item to the hash in state
> OP_SHA256STREAM n [item] [state] -> [state]
> // Finalize
> OP_SHA256STREAM (-2) [state] -> [Hash]
>
> <-1> OP_SHA256STREAM <tag> <subnode 2> <subnode 3> <3> OP_SHA256STREAM <-2> OP_SHA256STREAM
>
> Or it coul
>

This seems a good idea.

Though it brings up the age-old tension between:

* Generically-useable components, but due to generalization are less efficient.
* Specific-use components, which are efficient, but which may end up not being useable in the future.

In particular, `OP_SHA256STREAM` would no longer be useable if SHA256 eventually is broken, while the `OP_CAT` will still be useable in the indefinite future.
In the future a new hash function can simply be defined and the same technique with `OP_CAT` would still be useable.


Regards,
ZmnSCPxj

> --
> @JeremyRubin
>
> On Thu, Oct 3, 2019 at 8:04 PM Ethan Heilman <eth3rs@gmail.com> wrote:
>
> > I hope you are having an great afternoon ZmnSCPxj,
> >
> > You make an excellent point!
> >
> > I had thought about doing the following to tag nodes
> >
> > || means OP_CAT
> >
> > `node = SHA256(type||SHA256(data))`
> > so a subnode would be
> > `subnode1 = SHA256(1||SHA256(subnode2||subnode3))`
> > and a leaf node would be
> > `leafnode = SHA256(0||SHA256(leafdata))`
> >
> > Yet, I like your idea better. Increasing the size of the two inputs to
> > OP_CAT to be 260 Bytes each where 520 Bytes is the maximum allowable
> > size of object on the stack seems sensible and also doesn't special
> > case the logic of OP_CAT.
> >
> > It would also increase performance. SHA256(tag||subnode2||subnode3)
> > requires 2 compression function calls whereas
> > SHA256(1||SHA256(subnode2||subnode3)) requires 2+1=3 compression
> > function calls (due to padding).
> >
> > >Or we could implement tagged SHA256 as a new opcode...
> >
> > I agree that tagged SHA256 as an op code that would certainty be
> > useful, but OP_CAT provides far more utility and is a simpler change.
> >
> > Thanks,
> > Ethan
> >
> > On Thu, Oct 3, 2019 at 7:42 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
> > >
> > > Good morning Ethan,
> > >
> > >
> > > > To avoid derailing the NO_INPUT conversation, I have changed the
> > > > subject to OP_CAT.
> > > >
> > > > Responding to:
> > > > """
> > > >
> > > > -   `SIGHASH` flags attached to signatures are a misdesign, sadly
> > > >     retained from the original BitCoin 0.1.0 Alpha for Windows design, on
> > > >     par with:
> > > >     [..]
> > > >
> > > > -   `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > > >     [..]
> > > >     """
> > > >
> > > >     OP_CAT is an extremely valuable op code. I understand why it was
> > > >     removed as the situation at the time with scripts was dire. However
> > > >     most of the protocols I've wanted to build on Bitcoin run into the
> > > >     limitation that stack values can not be concatenated. For instance
> > > >     TumbleBit would have far smaller transaction sizes if OP_CAT was
> > > >     supported in Bitcoin. If it happens to me as a researcher it is
> > > >     probably holding other people back as well. If I could wave a magic
> > > >     wand and turn on one of the disabled op codes it would be OP_CAT. Of
> > > >     course with the change that size of each concatenated value must be 64
> > > >     Bytes or less.
> > >
> > > Why 64 bytes in particular?
> > >
> > > It seems obvious to me that this 64 bytes is most suited for building Merkle trees, being the size of two SHA256 hashes.
> > >
> > > However we have had issues with the use of Merkle trees in Bitcoin blocks.
> > > Specifically, it is difficult to determine if a hash on a Merkle node is the hash of a Merkle subnode, or a leaf transaction.
> > > My understanding is that this is the reason for now requiring transactions to be at least 80 bytes.
> > >
> > > The obvious fix would be to prepend the type of the hashed object, i.e. add at least one byte to determine this type.
> > > Taproot for example uses tagged hash functions, with a different tag for leaves, and tagged hashes are just prepend-this-32-byte-constant-twice-before-you-SHA256.
> > >
> > > This seems to indicate that to check merkle tree proofs, an `OP_CAT` with only 64 bytes max output size would not be sufficient.
> > >
> > > Or we could implement tagged SHA256 as a new opcode...
> > >
> > > Regards,
> > > ZmnSCPxj
> > >
> > >
> > > >
> > > >     On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bitcoin-dev
> > > >     bitcoin-dev@lists.linuxfoundation.org wrote:
> > > >
> > > >
> > > > > Good morning lists,
> > > > > Let me propose the below radical idea:
> > > > >
> > > > > -   `SIGHASH` flags attached to signatures are a misdesign, sadly retained from the original BitCoin 0.1.0 Alpha for Windows design, on par with:
> > > > >     -   1 RETURN
> > > > >     -   higher-`nSequence` replacement
> > > > >     -   DER-encoded pubkeys
> > > > >     -   unrestricted `scriptPubKey`
> > > > >     -   Payee-security-paid-by-payer (i.e. lack of P2SH)
> > > > >     -   `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > > > >     -   transaction malleability
> > > > >     -   probably many more
> > > > >
> > > > > So let me propose the more radical excision, starting with SegWit v1:
> > > > >
> > > > > -   Remove `SIGHASH` from signatures.
> > > > > -   Put `SIGHASH` on public keys.
> > > > >
> > > > > Public keys are now encoded as either 33-bytes (implicit `SIGHASH_ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type, followed by pubkey coordinate).
> > > > > `OP_CHECKSIG` and friends then look at the public key to determine sighash algorithm rather than the signature.
> > > > > As we expect public keys to be indirectly committed to on every output `scriptPubKey`, this is automatically output tagging to allow particular `SIGHASH`.
> > > > > However, we can then utilize the many many ways to hide public keys away until they are needed, exemplified in MAST-inside-Taproot.
> > > > > I propose also the addition of the opcode:
> > > > >
> > > > >     <sighash> <pubkey> OP_SETPUBKEYSIGHASH
> > > > >
> > > > >
> > > > > -   `sighash` must be one byte.
> > > > > -   `pubkey` may be the special byte `0x1`, meaning "just use the Taproot internal pubkey".
> > > > > -   `pubkey` may be 33-byte public key, in which case the `sighash` byte is just prepended to it.
> > > > > -   `pubkey` may be 34-byte public key with sighash, in which case the first byte is replaced with `sighash` byte.
> > > > > -   If `sighash` is `0x00` then the result is a 33-byte public key (the sighash byte is removed) i.e. `SIGHASH_ALL` implicit.
> > > > >
> > > > > This retains the old feature where the sighash is selected at time-of-spending rather than time-of-payment.
> > > > > This is done by using the script:
> > > > >
> > > > >     <pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG
> > > > >
> > > > >
> > > > > Then the sighash can be put in the witness stack after the signature, letting the `SIGHASH` flag be selected at time-of-signing, but only if the SCRIPT specifically is formed to do so.
> > > > > This is malleability-safe as the signature still commits to the `SIGHASH` it was created for.
> > > > > However, by default, public keys will not have an attached `SIGHASH` byte, implying `SIGHASH_ALL` (and disallowing-by-default non-`SIGHASH_ALL`).
> > > > > This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, as they are allowed only if the output specifically says they are allowed.
> > > > > Would this not be a superior solution?
> > > > > Regards,
> > > > > ZmnSCPxj
> > > > >
> > > > > bitcoin-dev mailing list
> > > > > bitcoin-dev@lists.linuxfoundation.org
> > > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> > > >
> > > > Lightning-dev mailing list
> > > > Lightning-dev@lists.linuxfoundation.org
> > > > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
> > >
> > >
> > _______________________________________________
> > Lightning-dev mailing list
> > Lightning-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1688 bytes --]

On Thu, Oct 03, 2019 at 10:02:14PM -0700, Jeremy via bitcoin-dev wrote:
> Awhile back, Ethan and I discussed having, rather than OP_CAT, an
> OP_SHA256STREAM that uses the streaming properties of a SHA256 hash
> function to allow concatenation of an unlimited amount of data, provided
> the only use is to hash it.
> 
> You can then use it perhaps as follows:
> 
> // start a new hash with item
> OP_SHA256STREAM  (-1) -> [state]
> // Add item to the hash in state
> OP_SHA256STREAM n [item] [state] -> [state]
> // Finalize
> OP_SHA256STREAM (-2) [state] -> [Hash]
> 
> <-1> OP_SHA256STREAM <tag> <subnode 2> <subnode 3> <3> OP_SHA256STREAM <-2>
> OP_SHA256STREAM

One issue with this is the simplest implementation where the state is just raw
bytes would expose raw SHA256 midstates, allowing people to use them directly;
preventing that would require adding types to the stack. Specifically I could
write a script that rather than initializing the state correctly from the
official IV, instead takes an untrusted state as input.

SHA256 isn't designed to be used in situations where adversaries control the
initialization vector. I personally don't know one way or the other if anyone
has analyzed this in detail, but I'd be surprised if that's secure. I
considered adding midstate support to OpenTimestamps but decided against it for
exactly that reason.

I don't have the link handy but there's even an example of an experienced
cryptographer on this very list (bitcoin-dev) proposing a design that falls
victim to this attack. It's a subtle issue and we probably don't want to
encourage it.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 9533 bytes --]

Good point -- in our discussion, we called it OP_FFS -- Fold Functional
Stream, and it could be initialized with a different integer to select for
different functions. Therefore the stream processing opcodes would be
generic, but extensible.
--
@JeremyRubin <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>


On Fri, Oct 4, 2019 at 12:00 AM ZmnSCPxj via Lightning-dev <
lightning-dev@lists.linuxfoundation.org> wrote:

> Good morning Jeremy,
>
> > Awhile back, Ethan and I discussed having, rather than OP_CAT, an
> OP_SHA256STREAM that uses the streaming properties of a SHA256 hash
> function to allow concatenation of an unlimited amount of data, provided
> the only use is to hash it.
> >
> > You can then use it perhaps as follows:
> >
> > // start a new hash with item
> > OP_SHA256STREAM  (-1) -> [state]
> > // Add item to the hash in state
> > OP_SHA256STREAM n [item] [state] -> [state]
> > // Finalize
> > OP_SHA256STREAM (-2) [state] -> [Hash]
> >
> > <-1> OP_SHA256STREAM <tag> <subnode 2> <subnode 3> <3> OP_SHA256STREAM
> <-2> OP_SHA256STREAM
> >
> > Or it coul
> >
>
> This seems a good idea.
>
> Though it brings up the age-old tension between:
>
> * Generically-useable components, but due to generalization are less
> efficient.
> * Specific-use components, which are efficient, but which may end up not
> being useable in the future.
>
> In particular, `OP_SHA256STREAM` would no longer be useable if SHA256
> eventually is broken, while the `OP_CAT` will still be useable in the
> indefinite future.
> In the future a new hash function can simply be defined and the same
> technique with `OP_CAT` would still be useable.
>
>
> Regards,
> ZmnSCPxj
>
> > --
> > @JeremyRubin
> >
> > On Thu, Oct 3, 2019 at 8:04 PM Ethan Heilman <eth3rs@gmail.com> wrote:
> >
> > > I hope you are having an great afternoon ZmnSCPxj,
> > >
> > > You make an excellent point!
> > >
> > > I had thought about doing the following to tag nodes
> > >
> > > || means OP_CAT
> > >
> > > `node = SHA256(type||SHA256(data))`
> > > so a subnode would be
> > > `subnode1 = SHA256(1||SHA256(subnode2||subnode3))`
> > > and a leaf node would be
> > > `leafnode = SHA256(0||SHA256(leafdata))`
> > >
> > > Yet, I like your idea better. Increasing the size of the two inputs to
> > > OP_CAT to be 260 Bytes each where 520 Bytes is the maximum allowable
> > > size of object on the stack seems sensible and also doesn't special
> > > case the logic of OP_CAT.
> > >
> > > It would also increase performance. SHA256(tag||subnode2||subnode3)
> > > requires 2 compression function calls whereas
> > > SHA256(1||SHA256(subnode2||subnode3)) requires 2+1=3 compression
> > > function calls (due to padding).
> > >
> > > >Or we could implement tagged SHA256 as a new opcode...
> > >
> > > I agree that tagged SHA256 as an op code that would certainty be
> > > useful, but OP_CAT provides far more utility and is a simpler change.
> > >
> > > Thanks,
> > > Ethan
> > >
> > > On Thu, Oct 3, 2019 at 7:42 PM ZmnSCPxj <ZmnSCPxj@protonmail.com>
> wrote:
> > > >
> > > > Good morning Ethan,
> > > >
> > > >
> > > > > To avoid derailing the NO_INPUT conversation, I have changed the
> > > > > subject to OP_CAT.
> > > > >
> > > > > Responding to:
> > > > > """
> > > > >
> > > > > -   `SIGHASH` flags attached to signatures are a misdesign, sadly
> > > > >     retained from the original BitCoin 0.1.0 Alpha for Windows
> design, on
> > > > >     par with:
> > > > >     [..]
> > > > >
> > > > > -   `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > > > >     [..]
> > > > >     """
> > > > >
> > > > >     OP_CAT is an extremely valuable op code. I understand why it
> was
> > > > >     removed as the situation at the time with scripts was dire.
> However
> > > > >     most of the protocols I've wanted to build on Bitcoin run into
> the
> > > > >     limitation that stack values can not be concatenated. For
> instance
> > > > >     TumbleBit would have far smaller transaction sizes if OP_CAT
> was
> > > > >     supported in Bitcoin. If it happens to me as a researcher it is
> > > > >     probably holding other people back as well. If I could wave a
> magic
> > > > >     wand and turn on one of the disabled op codes it would be
> OP_CAT. Of
> > > > >     course with the change that size of each concatenated value
> must be 64
> > > > >     Bytes or less.
> > > >
> > > > Why 64 bytes in particular?
> > > >
> > > > It seems obvious to me that this 64 bytes is most suited for
> building Merkle trees, being the size of two SHA256 hashes.
> > > >
> > > > However we have had issues with the use of Merkle trees in Bitcoin
> blocks.
> > > > Specifically, it is difficult to determine if a hash on a Merkle
> node is the hash of a Merkle subnode, or a leaf transaction.
> > > > My understanding is that this is the reason for now requiring
> transactions to be at least 80 bytes.
> > > >
> > > > The obvious fix would be to prepend the type of the hashed object,
> i.e. add at least one byte to determine this type.
> > > > Taproot for example uses tagged hash functions, with a different tag
> for leaves, and tagged hashes are just
> prepend-this-32-byte-constant-twice-before-you-SHA256.
> > > >
> > > > This seems to indicate that to check merkle tree proofs, an `OP_CAT`
> with only 64 bytes max output size would not be sufficient.
> > > >
> > > > Or we could implement tagged SHA256 as a new opcode...
> > > >
> > > > Regards,
> > > > ZmnSCPxj
> > > >
> > > >
> > > > >
> > > > >     On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bitcoin-dev
> > > > >     bitcoin-dev@lists.linuxfoundation.org wrote:
> > > > >
> > > > >
> > > > > > Good morning lists,
> > > > > > Let me propose the below radical idea:
> > > > > >
> > > > > > -   `SIGHASH` flags attached to signatures are a misdesign,
> sadly retained from the original BitCoin 0.1.0 Alpha for Windows design, on
> par with:
> > > > > >     -   1 RETURN
> > > > > >     -   higher-`nSequence` replacement
> > > > > >     -   DER-encoded pubkeys
> > > > > >     -   unrestricted `scriptPubKey`
> > > > > >     -   Payee-security-paid-by-payer (i.e. lack of P2SH)
> > > > > >     -   `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > > > > >     -   transaction malleability
> > > > > >     -   probably many more
> > > > > >
> > > > > > So let me propose the more radical excision, starting with
> SegWit v1:
> > > > > >
> > > > > > -   Remove `SIGHASH` from signatures.
> > > > > > -   Put `SIGHASH` on public keys.
> > > > > >
> > > > > > Public keys are now encoded as either 33-bytes (implicit
> `SIGHASH_ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type,
> followed by pubkey coordinate).
> > > > > > `OP_CHECKSIG` and friends then look at the public key to
> determine sighash algorithm rather than the signature.
> > > > > > As we expect public keys to be indirectly committed to on every
> output `scriptPubKey`, this is automatically output tagging to allow
> particular `SIGHASH`.
> > > > > > However, we can then utilize the many many ways to hide public
> keys away until they are needed, exemplified in MAST-inside-Taproot.
> > > > > > I propose also the addition of the opcode:
> > > > > >
> > > > > >     <sighash> <pubkey> OP_SETPUBKEYSIGHASH
> > > > > >
> > > > > >
> > > > > > -   `sighash` must be one byte.
> > > > > > -   `pubkey` may be the special byte `0x1`, meaning "just use
> the Taproot internal pubkey".
> > > > > > -   `pubkey` may be 33-byte public key, in which case the
> `sighash` byte is just prepended to it.
> > > > > > -   `pubkey` may be 34-byte public key with sighash, in which
> case the first byte is replaced with `sighash` byte.
> > > > > > -   If `sighash` is `0x00` then the result is a 33-byte public
> key (the sighash byte is removed) i.e. `SIGHASH_ALL` implicit.
> > > > > >
> > > > > > This retains the old feature where the sighash is selected at
> time-of-spending rather than time-of-payment.
> > > > > > This is done by using the script:
> > > > > >
> > > > > >     <pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG
> > > > > >
> > > > > >
> > > > > > Then the sighash can be put in the witness stack after the
> signature, letting the `SIGHASH` flag be selected at time-of-signing, but
> only if the SCRIPT specifically is formed to do so.
> > > > > > This is malleability-safe as the signature still commits to the
> `SIGHASH` it was created for.
> > > > > > However, by default, public keys will not have an attached
> `SIGHASH` byte, implying `SIGHASH_ALL` (and disallowing-by-default
> non-`SIGHASH_ALL`).
> > > > > > This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`,
> as they are allowed only if the output specifically says they are allowed.
> > > > > > Would this not be a superior solution?
> > > > > > Regards,
> > > > > > ZmnSCPxj
> > > > > >
> > > > > > bitcoin-dev mailing list
> > > > > > bitcoin-dev@lists.linuxfoundation.org
> > > > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> > > > >
> > > > > Lightning-dev mailing list
> > > > > Lightning-dev@lists.linuxfoundation.org
> > > > > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
> > > >
> > > >
> > > _______________________________________________
> > > Lightning-dev mailing list
> > > Lightning-dev@lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>

[-- Attachment #2: Type: text/html, Size: 13472 bytes --]

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 2471 bytes --]

Interesting point.

The script is under your control, so you should be able to ensure that you
are always using a correctly constructed midstate, e.g., something like:

scriptPubKey: <-1> OP_SHA256STREAM DEPTH OP_SHA256STREAM <-2>
OP_SHA256STREAM
<hash> OP_EQUALVERIFY

would hash all the elements on the stack and compare to a known hash.
How is that sort of thing weak to midstateattacks?


--
@JeremyRubin <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>


On Fri, Oct 4, 2019 at 4:16 AM Peter Todd <pete@petertodd.org> wrote:

> On Thu, Oct 03, 2019 at 10:02:14PM -0700, Jeremy via bitcoin-dev wrote:
> > Awhile back, Ethan and I discussed having, rather than OP_CAT, an
> > OP_SHA256STREAM that uses the streaming properties of a SHA256 hash
> > function to allow concatenation of an unlimited amount of data, provided
> > the only use is to hash it.
> >
> > You can then use it perhaps as follows:
> >
> > // start a new hash with item
> > OP_SHA256STREAM  (-1) -> [state]
> > // Add item to the hash in state
> > OP_SHA256STREAM n [item] [state] -> [state]
> > // Finalize
> > OP_SHA256STREAM (-2) [state] -> [Hash]
> >
> > <-1> OP_SHA256STREAM <tag> <subnode 2> <subnode 3> <3> OP_SHA256STREAM
> <-2>
> > OP_SHA256STREAM
>
> One issue with this is the simplest implementation where the state is just
> raw
> bytes would expose raw SHA256 midstates, allowing people to use them
> directly;
> preventing that would require adding types to the stack. Specifically I
> could
> write a script that rather than initializing the state correctly from the
> official IV, instead takes an untrusted state as input.
>
> SHA256 isn't designed to be used in situations where adversaries control
> the
> initialization vector. I personally don't know one way or the other if
> anyone
> has analyzed this in detail, but I'd be surprised if that's secure. I
> considered adding midstate support to OpenTimestamps but decided against
> it for
> exactly that reason.
>
> I don't have the link handy but there's even an example of an experienced
> cryptographer on this very list (bitcoin-dev) proposing a design that falls
> victim to this attack. It's a subtle issue and we probably don't want to
> encourage it.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>

[-- Attachment #2: Type: text/html, Size: 4843 bytes --]

Re: [bitcoin-dev] Continuing the discussion about noinput / anyprevout

[Anthony Towns]

On Thu, Oct 03, 2019 at 01:08:29PM +0200, Christian Decker wrote:
> >  * anyprevout signatures make the address you're signing for less safe,
> >    which may cause you to lose funds when additional coins are sent to
> >    the same address; this can be avoided if handled with care (or if you
> >    don't care about losing funds in the event of address reuse)
> Excellent points, I had missed the hidden nature of the opt-in via
> pubkey prefix while reading your proposal. I'm starting to like that
> option more and more. In that case we'd only ever be revealing that we
> opted into anyprevout when we're revealing the entire script anyway, at
> which point all fungibility concerns go out the window anyway.
>
> Would this scheme be extendable to opt into all sighash flags the
> outpoint would like to allow (e.g., adding opt-in for sighash_none and
> sighash_anyonecanpay as well)? That way the pubkey prefix could act as a
> mask for the sighash flags and fail verification if they don't match.

For me, the thing that distinguishes ANYPREVOUT/NOINPUT as warranting
an opt-in step is that it affects the security of potentially many
UTXOs at once; whereas all the other combinations (ALL,SINGLE,NONE
cross ALL,ANYONECANPAY) still commit to the specific UTXO being spent,
so at most you only risk somehow losing the funds from the specific UTXO
you're working with (apart from the SINGLE bug, which taproot doesn't
support anyway).

Having a meaningful prefix on the taproot scriptpubkey (ie paying to
"[SIGHASH_SINGLE][32B pubkey]") seems like it would make it a bit easier
to distinguish wallets, which taproot otherwise avoids -- "oh this address
is going to be a SIGHASH_SINGLE? probably some hacker, let's ban it".

> > I think it might be good to have a public testnet (based on Richard Myers
> > et al's signet2 work?) where we have some fake exchanges/merchants/etc
> > and scheduled reorgs, and demo every weird noinput/anyprevout case anyone
> > can think of, and just work out if we need any extra code/tagging/whatever
> > to keep those fake exchanges/merchants from losing money (and write up
> > the weird cases we've found in a wiki or a paper so people can easily
> > tell if we missed something obvious).
> That'd be great, however even that will not ensure that every possible
> corner case is handled [...]

Well, sure. I'm thinking of it more as a *necessary* step than a
*sufficient* one, though. If we can't demonstrate that we can deal with
the theoretical attacks people have dreamt up in a "laboratory" setting,
then it doesn't make much sense to deploy things in a real world setting,
does it?

I think if it turns out that we can handle every case we can think of
easily, that will be good evidence that output tagging and the like isn't
necessary; and conversely if it turns out we can't handle them easily,
it at least gives us a chance to see how output tagging (or chaperone
sigs, or whatever else) would actually work, and if they'd provide any
meaningful protection at all. At the moment the best we've got is ideas
and handwaving...

Cheers,
aj

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 882 bytes --]

On Fri, Oct 04, 2019 at 11:40:53AM -0700, Jeremy wrote:
> Interesting point.
> 
> The script is under your control, so you should be able to ensure that you
> are always using a correctly constructed midstate, e.g., something like:
> 
> scriptPubKey: <-1> OP_SHA256STREAM DEPTH OP_SHA256STREAM <-2>
> OP_SHA256STREAM
> <hash> OP_EQUALVERIFY
> 
> would hash all the elements on the stack and compare to a known hash.
> How is that sort of thing weak to midstateattacks?

Obviously with care you can get the computation right. But at that point what's
the actual advantage over OP_CAT?

We're limited by the size of the script anyway; if the OP_CAT output size limit
is comparable to that for almost anything you could use SHA256STREAM on you
could just as easily use OP_CAT, followed by a single OP_SHA256.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Lloyd Fournier]

[-- Attachment #1: Type: text/plain, Size: 9514 bytes --]

Hi Thread,

I made a reply to the OP but didn't "reply all" so it just went directly to
Ethan. Since the comments were interesting I'll attempt to salvage them by
posting them in full:

== Lloyd's post ==
Hi Ethan,

I'd be interested to know what protocols you need OP_CAT for. I'm trying to
figure out if there really exists any script based protocol that doesn't
have a more efficient scriptless counterpart.  For example,
A²L[1] achieves the same thing as Tumblebit but requires no script. I can
imagine paying based on a merkle path could be useful, but a protocol was
recently suggested on lightning-dev [2] that does this but without OP_CAT
(and without any script!).


[1] https://eprint.iacr.org/2019/589.pdf
[2]
https://www.mail-archive.com/lightning-dev@lists.linuxfoundation.org/msg01427.html
(*I linked to the wrong thread in the original email*).

LL

== Ethan's response ==
Hi Lloyd,

Thanks for your response. I am not sure if you intended to take this off
list or not.

I plan to at some point to enumerate in detail protocols that OP_CAT would
benefit. A more important point is that OP_CAT is a basic building block
and that we don't know what future protocols it would allow. In my own
research I have avoiding going down certain paths because it isn't worth
the time to investigate knowing that OP_CAT wouldn't make the protocol
practical.

In regards to scriptless scripts they almost always require an interactive
protocol and sometimes ZKPs. A2L is very impressive but like TumbleBit it
places a large burden on the developer. Additionally I am aware of no way
to reveal a subset of preimages with scriptless scripts, do a conditioned
reveal i.e. these preimages can only spend under these two pubkeys and
timelockA where after timelockZ this other pubkey can spend without a
preimages. Scriptless scripts are a fantastic tool but they shouldn't be
the only tool that we have.

I'm not sure I follow what you are saying with [2]

This brings me back a philosophical point:
Bitcoin should give people basic tools to build protocols without first
knowing what all those protocols are especially when those tools have very
little downside.

I really appreciate your comments.

Thanks,
Ethan
==

*Back to normal thread*

Hi Ethan,

Thanks for the insightful reply and sorry for my mailing list errors.

> I plan to at some point to enumerate in detail protocols that OP_CAT
would benefit.

Sweet. Thanks.

> Additionally I am aware of no way to reveal a subset of preimages with
scriptless scripts, do a conditioned reveal i.e. these preimages can only
spend under these two pubkeys and timelockA where after timelockZ this
other pubkey can spend without a preimages. Scriptless scripts are a
fantastic tool but they shouldn't be the only tool that we have.

Yes. With adaptor signatures there is no way to reveal more than one
pre-image; you are limited to revealing a single scalar. But you can have
multiple transactions spending from the same output, each with a different
set of scriptless conditions (absolute time locks, relative time locks and
pre-image reveal). This is enough to achieve what I think you are
describing. FWIW there's a growing consensus that you can do lightning
without script [1]. Perhaps we can't do everything with this technique. My
current focus is figuring out what useful things we can't do like this
(even if we were to go wild and add whatever opcodes we wanted). So far it
looks like covenants are the main exception.

> I'm not sure I follow what you are saying with [2]

That is perfectly understandable as I linked the wrong thread (sorry!).
Here's the right one:
https://www.mail-archive.com/lightning-dev@lists.linuxfoundation.org/msg01427.html

I was pointing to the surprising result that you can actually pay for a
merkle path with a particular merkle root leading to a particular leaf that
you're interested in without validating the merkle path on chain (e.g.
OP_CAT and OP_SHA256). The catch is that the leaves have to be pedersen
commitments and you prove the existence of your data in the merkle root by
showing an opening to the leaf pedersen commitment. This may not be general
enough to cover every merkle tree use case (but I'm not sure what those
are!).

> This brings me back a philosophical point:
> Bitcoin should give people basic tools to build protocols without first
knowing what all those protocols are especially when those tools have very
little downside.

This is a really powerful idea. But I've started feeling like you have to
just design the layer 2 protocols first and then design layer 1! It seems
like almost every protocol that people want to make requires very
particular fundamental changes: SegWit for LN-penalty and NOINPUT for eltoo
for example. On top of that it seems like just having the right signature
scheme (schnorr) at layer 1 is enough to enable most useful stuff in an
elegant way.

[1]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-September/017309.html

Cheers,

LL

On Fri, Oct 4, 2019 at 1:08 AM Ethan Heilman <eth3rs@gmail.com> wrote:

> To avoid derailing the NO_INPUT conversation, I have changed the
> subject to OP_CAT.
>
> Responding to:
> """
> * `SIGHASH` flags attached to signatures are a misdesign, sadly
> retained from the original BitCoin 0.1.0 Alpha for Windows design, on
> par with:
> [..]
> * `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> [..]
> """
>
> OP_CAT is an extremely valuable op code. I understand why it was
> removed as the situation at the time with scripts was dire. However
> most of the protocols I've wanted to build on Bitcoin run into the
> limitation that stack values can not be concatenated. For instance
> TumbleBit would have far smaller transaction sizes if OP_CAT was
> supported in Bitcoin. If it happens to me as a researcher it is
> probably holding other people back as well. If I could wave a magic
> wand and turn on one of the disabled op codes it would be OP_CAT.  Of
> course with the change that size of each concatenated value must be 64
> Bytes or less.
>
>
> On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> > Good morning lists,
> >
> > Let me propose the below radical idea:
> >
> > * `SIGHASH` flags attached to signatures are a misdesign, sadly retained
> from the original BitCoin 0.1.0 Alpha for Windows design, on par with:
> >   * 1 RETURN
> >   * higher-`nSequence` replacement
> >   * DER-encoded pubkeys
> >   * unrestricted `scriptPubKey`
> >   * Payee-security-paid-by-payer (i.e. lack of P2SH)
> >   * `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> >   * transaction malleability
> >   * probably many more
> >
> > So let me propose the more radical excision, starting with SegWit v1:
> >
> > * Remove `SIGHASH` from signatures.
> > * Put `SIGHASH` on public keys.
> >
> > Public keys are now encoded as either 33-bytes (implicit `SIGHASH_ALL`)
> or 34-bytes (`SIGHASH` byte, followed by pubkey type, followed by pubkey
> coordinate).
> > `OP_CHECKSIG` and friends then look at the *public key* to determine
> sighash algorithm rather than the signature.
> >
> > As we expect public keys to be indirectly committed to on every output
> `scriptPubKey`, this is automatically output tagging to allow particular
> `SIGHASH`.
> > However, we can then utilize the many many ways to hide public keys away
> until they are needed, exemplified in MAST-inside-Taproot.
> >
> > I propose also the addition of the opcode:
> >
> >     <sighash> <pubkey> OP_SETPUBKEYSIGHASH
> >
> > * `sighash` must be one byte.
> > * `pubkey` may be the special byte `0x1`, meaning "just use the Taproot
> internal pubkey".
> > * `pubkey` may be 33-byte public key, in which case the `sighash` byte
> is just prepended to it.
> > * `pubkey` may be 34-byte public key with sighash, in which case the
> first byte is replaced with `sighash` byte.
> > * If `sighash` is `0x00` then the result is a 33-byte public key (the
> sighash byte is removed) i.e. `SIGHASH_ALL` implicit.
> >
> > This retains the old feature where the sighash is selected at
> time-of-spending rather than time-of-payment.
> > This is done by using the script:
> >
> >     <pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG
> >
> > Then the sighash can be put in the witness stack after the signature,
> letting the `SIGHASH` flag be selected at time-of-signing, but only if the
> SCRIPT specifically is formed to do so.
> > This is malleability-safe as the signature still commits to the
> `SIGHASH` it was created for.
> >
> > However, by default, public keys will not have an attached `SIGHASH`
> byte, implying `SIGHASH_ALL` (and disallowing-by-default non-`SIGHASH_ALL`).
> >
> > This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, as they
> are allowed only if the output specifically says they are allowed.
> >
> > Would this not be a superior solution?
> >
> > Regards,
> > ZmnSCPxj
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>

[-- Attachment #2: Type: text/html, Size: 11652 bytes --]

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[ZmnSCPxj]

Good morning Peter, Jeremy, and lists,

> On Fri, Oct 04, 2019 at 11:40:53AM -0700, Jeremy wrote:
>
> > Interesting point.
> > The script is under your control, so you should be able to ensure that you
> > are always using a correctly constructed midstate, e.g., something like:
> > scriptPubKey: <-1> OP_SHA256STREAM DEPTH OP_SHA256STREAM <-2>
> > OP_SHA256STREAM
> > <hash> OP_EQUALVERIFY
> > would hash all the elements on the stack and compare to a known hash.
> > How is that sort of thing weak to midstateattacks?
>
> Obviously with care you can get the computation right. But at that point what's
> the actual advantage over OP_CAT?
>
> We're limited by the size of the script anyway; if the OP_CAT output size limit
> is comparable to that for almost anything you could use SHA256STREAM on you
> could just as easily use OP_CAT, followed by a single OP_SHA256.

Theoretically, `OP_CAT` is less efficient.

In cases where the memory area used to back the data cannot be resized, new backing memory must be allocated elsewhere and the existing data copied.
This leads to possible O( n^2 ) behavior for `OP_CAT` (degenerate case where we add 1 byte per `OP_CAT` and each time find that the memory area currently in use is exactly fitting the data and cannot be resized in-place).

`OP_SHASTREAM` would not require new allocations once the stream state is in place and would not require any copying.


This may be relevant in considering the cost of executing `OP_CAT`.

Admittedly a sufficiently-limited  maximum `OP_CAT` output would be helpful in reducing the worst-case `OP_CAT` behavior.
The question is what limit would be reasonable.
64 bytes feels too small if one considers Merkle tree proofs, due to mentioned issues of lack of typechecking.


Regards,
ZmnSCPxj


>
> --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1737 bytes --]

On Sun, Oct 06, 2019 at 08:46:59AM +0000, ZmnSCPxj wrote:
> > Obviously with care you can get the computation right. But at that point what's
> > the actual advantage over OP_CAT?
> >
> > We're limited by the size of the script anyway; if the OP_CAT output size limit
> > is comparable to that for almost anything you could use SHA256STREAM on you
> > could just as easily use OP_CAT, followed by a single OP_SHA256.
> 
> Theoretically, `OP_CAT` is less efficient.
> 
> In cases where the memory area used to back the data cannot be resized, new backing memory must be allocated elsewhere and the existing data copied.
> This leads to possible O( n^2 ) behavior for `OP_CAT` (degenerate case where we add 1 byte per `OP_CAT` and each time find that the memory area currently in use is exactly fitting the data and cannot be resized in-place).

In even that degenerate case allocators also free memory.

Anyway, every execution step in script evaluation has a maximum output size,
and the number of steps is limited. At worst you can allocate the entire
possible stack up-front for relatively little cost (eg fitting in the MB or two
that is a common size for L2 cache).

> Admittedly a sufficiently-limited  maximum `OP_CAT` output would be helpful in reducing the worst-case `OP_CAT` behavior.
> The question is what limit would be reasonable.
> 64 bytes feels too small if one considers Merkle tree proofs, due to mentioned issues of lack of typechecking.

256 bytes is more than enough for even the most complex summed merkle tree with
512-byte hashes and full-sized sum commitments. Yet that's still less than the
~500byte limit proposed elsewhere.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Andrew Poelstra]

[-- Attachment #1: Type: text/plain, Size: 2268 bytes --]

On Thu, Oct 03, 2019 at 11:05:52AM -0400, Ethan Heilman wrote:
> To avoid derailing the NO_INPUT conversation, I have changed the
> subject to OP_CAT.
> 
> Responding to:
> """
> * `SIGHASH` flags attached to signatures are a misdesign, sadly
> retained from the original BitCoin 0.1.0 Alpha for Windows design, on
> par with:
> [..]
> * `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> [..]
> """
> 
> OP_CAT is an extremely valuable op code. I understand why it was
> removed as the situation at the time with scripts was dire. However
> most of the protocols I've wanted to build on Bitcoin run into the
> limitation that stack values can not be concatenated. For instance
> TumbleBit would have far smaller transaction sizes if OP_CAT was
> supported in Bitcoin. If it happens to me as a researcher it is
> probably holding other people back as well. If I could wave a magic
> wand and turn on one of the disabled op codes it would be OP_CAT.  Of
> course with the change that size of each concatenated value must be 64
> Bytes or less.
>

Just throwing my two cents in here - as others have noted, OP_CAT
lets you create Merkle trees (allowing e.g. log-sized accountable
threshold sigs, at least in a post-Schnorr future).

It also allows manipulating signatures - e.g. forcing the revelation
of discrete logs by requiring the user use the (1/2) point as a nonce
(this starts with 11 zero bytes, which no other computationally
accessible point does), or by requiring two sigs with the same nonce.

It also lets you do proof-of-work-like computations on hashes or
curvepoints; or enforce that EC points come from a hash and have
no known discrete log. You can also switch on hashes, something
currently impossible because of the 4-byte limitation on numeric
opcodes. I don't have specific application of these in mind but
definitely have cut off many lines of inquiry because they were
impossible.

You could build a crappy Lamport signature, though the key would
be so big that you'd never do this pre-MAST :P.


-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]