[bitcoin-dev] [BIP] Normalized transaction IDs

[bitcoin-dev] [BIP] Normalized transaction IDs

[Christian Decker]

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

After spending some more time on the normalized transaction ID proposal and
reworking it to be a soft-fork (thanks sipa for helping me figuring out
how), I'd like to propose the BIP again.

As with the previous version, which was using a hard-fork, the normalized
transaction ID is computed only considering the non-malleable parts of a
transaction, i.e., stripping the signatures before computing the hash of
the transaction. This ensures that if a transaction is modified, either by
a third party fishing transactions from the network and re-injecting
modified versions or by one of the signers re-signing it, any transaction
that builds on top of it still remains valid. Furthermore it allows the use
of template transactions, unsigned transactions upon which further
transaction can be built before signing the template transaction and
locking the contract.

Unlike the previous proposal, this is a softfork proposal that redefines
OP_NOP4 with an extensible and parameterized version of the signature
checking opcodes, called OP_CHECKSIGEX. Among other things the parameters
allow to specify that an output with an OP_CHECKSIGEX is to be referenced
by the normalized transaction ID that created it, instead of the instance
transaction ID containing malleable signatures. This BIP uses the
normalized transaction IDs exclusively while signing or checking
signatures, they are not used in any network level message as the previous
version would have done, hence there is no change at network level and old
clients should be able to exchange transactions as before and blocks still
reference the transaction instances.

The proposal is implemented (see below), by computing the normalized
transaction ID when adding them to the UTXO and storing them along with the
coin state. OP_CHECKSIGEX mostly duplicates OP_CHECKSIG and
OP_CHECKMULTISIG, but I'm hoping somebody can give me some pointers into
how to best refactor the common functionality into reusable blocks. And the
annotating incoming transactions with their normalized inputs is a bit
cumbersome, maye somebody has some pointers here as well?

BIP Pull request: https://github.com/bitcoin/bips/pull/224
Implementation: https://github.com/cdecker/bitcoin/commits/normtx

I think in the discussion of my previous proposal, most of you welcomed the
introduction of normalized transaction IDs, were it not for the hardfork. I
hope this proposal adresses the previous concerns and that we can move
forward in adding the normalized transaction IDs to the bitcoin protocol.
That being said, I'm always open to suggestions :-)

Regards,
Christian

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Tier Nolan]

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

On Mon, Oct 19, 2015 at 3:01 PM, Christian Decker via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> As with the previous version, which was using a hard-fork, the normalized
> transaction ID is computed only considering the non-malleable parts of a
> transaction, i.e., stripping the signatures before computing the hash of
> the transaction.
> <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>


Is this proposal recursive?


*Coinbase transaction *

* n-txid = txid


*Non-coinbase transactions*
* replace sigScripts with empty strings
* replace txids in TxIns with n-txid for parents

The 2nd step is recursive starting from the coinbases.

In effect, the rule is that txids are what they would have been if n-txids
had been used right from the start.

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Christian Decker]

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

Yes, this has been pointed out in the PR as well. Transactions inputs must
also be normalized by replacing malleable hashes with the normalized
hashes. I will fix the spec and the implementation to reflect this :-)

Regards,
Christian

On Mon, Oct 19, 2015 at 5:24 PM Tier Nolan via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Mon, Oct 19, 2015 at 3:01 PM, Christian Decker via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> As with the previous version, which was using a hard-fork, the normalized
>> transaction ID is computed only considering the non-malleable parts of a
>> transaction, i.e., stripping the signatures before computing the hash of
>> the transaction.
>> <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>
>
>
> Is this proposal recursive?
>
>
> *Coinbase transaction *
>
> * n-txid = txid
>
>
> *Non-coinbase transactions*
> * replace sigScripts with empty strings
> * replace txids in TxIns with n-txid for parents
>
> The 2nd step is recursive starting from the coinbases.
>
> In effect, the rule is that txids are what they would have been if n-txids
> had been used right from the start.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[s7r]

So what exactly is used to create the normalized txid (sha256 hash of
what data)? I've read in the linked BIP draft that it will strip the
'malleable parts' but didn't understand what exactly will be used to
calculate the normalized transactions ids and how will the change apply
retro-active for the transactions so deep buried in the blockchain?

Pubkeys (addresses) can be reused infinitely so what guarantees us
unique normalized txids all the time and protection against replay
attacks? The question is not if this issue is covered or not, I know it
is, I am just asking how, in simpler terms.

SCRIPT_CHECKSIGEX_NORMALIZE could be explained better in the document.

Will it also fix > third level malleability (a tx which spends from
another unconfirmed tx which spends from yet another unconfirmed tx)?


On 10/19/2015 6:23 PM, Tier Nolan via bitcoin-dev wrote:
> On Mon, Oct 19, 2015 at 3:01 PM, Christian Decker via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org
> <mailto:bitcoin-dev@lists.linuxfoundation.org>> wrote:
> 
>     As with the previous version, which was using a hard-fork, the
>     normalized transaction ID is computed only considering the
>     non-malleable parts of a transaction, i.e., stripping the signatures
>     before computing the hash of the transaction.
>     <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>
> 
> 
> Is this proposal recursive? 
> 
> *Coinbase transaction
> *
> 
> * n-txid = txid
> 
> *Non-coinbase transactions
> *
> * replace sigScripts with empty strings
> * replace txids in TxIns with n-txid for parents
> 
> The 2nd step is recursive starting from the coinbases.
> 
> In effect, the rule is that txids are what they would have been if
> n-txids had been used right from the start.
> 
> 

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Christian Decker]

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

On Tue, Oct 20, 2015 at 12:23 AM s7r via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> So what exactly is used to create the normalized txid (sha256 hash of
> what data)? I've read in the linked BIP draft that it will strip the
> 'malleable parts' but didn't understand what exactly will be used to
> calculate the normalized transactions ids and how will the change apply
> retro-active for the transactions so deep buried in the blockchain?
>

The normalization involves two steps:
 - strip the scriptSig scripts in the inputs, i.e., the only part whose
integrity is not guaranteed by the signature itself, by replacing the
scripts with empty strings (var length string of size 0)
 - replace the hashes referencing the outputs being spent with the
normalized hashes of the transaction that created the outputs. This is done
recursively down to the first v2 transactions.

The second part is not yet explained in the draft, but I will amend it as
soon as possible.


> Pubkeys (addresses) can be reused infinitely so what guarantees us
> unique normalized txids all the time and protection against replay
> attacks? The question is not if this issue is covered or not, I know it
> is, I am just asking how, in simpler terms.
>

Non-coinbase transactions can still not be replayed since the normalized
transaction still includes a the normalized transaction hashes of claimed
outputs, hence any attempt to replay a transaction would fail since the
outputs were already spent. For coinbase transactions it is indeed possible
that we create multiple transactions with the same hash (only one of which
would be spendable), hence we do not strip coinbase transactions and rely
on BIP 34 to make the coinbase transactions unique (except for blocks 91842
and 91880 which are the reason we introduced BIP 34 in the first place).
Clarifying the way the normalized transaction ID is computed should remove
any ambiguities I hope.


>
> SCRIPT_CHECKSIGEX_NORMALIZE could be explained better in the document.
>
> Will it also fix > third level malleability (a tx which spends from
> another unconfirmed tx which spends from yet another unconfirmed tx)?
>

Yes, if the computation of the normalized transaction ID includes replacing
input hashes with their normalized counterpart makes a chain of any depth
non-malleable.

HTH,
Christian

>
>
> On 10/19/2015 6:23 PM, Tier Nolan via bitcoin-dev wrote:
> > On Mon, Oct 19, 2015 at 3:01 PM, Christian Decker via bitcoin-dev
> > <bitcoin-dev@lists.linuxfoundation.org
> > <mailto:bitcoin-dev@lists.linuxfoundation.org>> wrote:
> >
> >     As with the previous version, which was using a hard-fork, the
> >     normalized transaction ID is computed only considering the
> >     non-malleable parts of a transaction, i.e., stripping the signatures
> >     before computing the hash of the transaction.
> >     <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>
> >
> >
> > Is this proposal recursive?
> >
> > *Coinbase transaction
> > *
> >
> > * n-txid = txid
> >
> > *Non-coinbase transactions
> > *
> > * replace sigScripts with empty strings
> > * replace txids in TxIns with n-txid for parents
> >
> > The 2nd step is recursive starting from the coinbases.
> >
> > In effect, the rule is that txids are what they would have been if
> > n-txids had been used right from the start.
> >
> >
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Luke Dashjr]

On Monday, October 19, 2015 2:01:04 PM Christian Decker via bitcoin-dev wrote:
> The proposal is implemented (see below), by computing the normalized
> transaction ID when adding them to the UTXO and storing them along with the
> coin state. OP_CHECKSIGEX mostly duplicates OP_CHECKSIG and
> OP_CHECKMULTISIG, but I'm hoping somebody can give me some pointers into
> how to best refactor the common functionality into reusable blocks. And the
> annotating incoming transactions with their normalized inputs is a bit
> cumbersome, maye somebody has some pointers here as well?

This doesn't completely close malleability (which should be documented in the 
BIP), so I'm not sure it's worth the cost, especially if closing malleability 
later on would need more. How about specifying flags upfront in the UTXO-
creating transaction specifying which parts the signature will cover? This 
would allow implementation of fully malleability-proof wallets.

Additionally, you have a flag to control whether the opcode behaves as VERIFY 
or not. Non-VERIFY is not possible as a softfork (without doing a second/new 
P2SH) since it can be negated.

Luke

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Christian Decker]

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

On Wed, Oct 21, 2015 at 8:19 AM Luke Dashjr <luke@dashjr.org> wrote:

> On Monday, October 19, 2015 2:01:04 PM Christian Decker via bitcoin-dev
> wrote:
> > The proposal is implemented (see below), by computing the normalized
> > transaction ID when adding them to the UTXO and storing them along with
> the
> > coin state. OP_CHECKSIGEX mostly duplicates OP_CHECKSIG and
> > OP_CHECKMULTISIG, but I'm hoping somebody can give me some pointers into
> > how to best refactor the common functionality into reusable blocks. And
> the
> > annotating incoming transactions with their normalized inputs is a bit
> > cumbersome, maye somebody has some pointers here as well?


> This doesn't completely close malleability (which should be documented in
> the
> BIP), so I'm not sure it's worth the cost, especially if closing
> malleability
> later on would need more. How about specifying flags upfront in the UTXO-
> creating transaction specifying which parts the signature will cover? This
> would allow implementation of fully malleability-proof wallets.
>

As far as I see it the only remaining venues for malleability are the use
of sighash flags that are not SIGHASH_ALL, as mentioned in the BIP. Any use
of non-sighash_all flags is already an explicit permission to modify the
transactions, by adding and removing inputs and outputs, so I don't see how
these can be made non-malleable. Am I missing something?


>
> Additionally, you have a flag to control whether the opcode behaves as
> VERIFY
> or not. Non-VERIFY is not possible as a softfork (without doing a
> second/new
> P2SH) since it can be negated.
>

Yes, this is my mistake and has been pointed out in the PR, I will amend
the PR to make the verify flag mandatory, which also guarantees that the
top of the stack contains a non-null element, thus resulting in a
successful evaluation on non-updated clients.


>
> Luke
>

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Luke Dashjr]

On Wednesday, October 21, 2015 7:39:45 AM Christian Decker wrote:
> On Wed, Oct 21, 2015 at 8:19 AM Luke Dashjr <luke@dashjr.org> wrote:
> > This doesn't completely close malleability (which should be documented in
> > the BIP), so I'm not sure it's worth the cost, especially if closing
> > malleability later on would need more. How about specifying flags upfront
> > in the UTXO-creating transaction specifying which parts the signature
> > will cover? This would allow implementation of fully malleability-proof
> > wallets.
> 
> As far as I see it the only remaining venues for malleability are the use
> of sighash flags that are not SIGHASH_ALL, as mentioned in the BIP. Any use
> of non-sighash_all flags is already an explicit permission to modify the
> transactions, by adding and removing inputs and outputs, so I don't see how
> these can be made non-malleable. Am I missing something?

Signer malleability is still a notable concern needing consideration. Ideally, 
wallets should be trying to actively CoinJoin, bump fees on, etc any pending 
transactions in the background. These forms of malleability affect nearly as 
many real use cases as third-party malleability.

Luke

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Christian Decker]

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

On Wed, Oct 21, 2015 at 9:52 AM Luke Dashjr <luke@dashjr.org> wrote:

> On Wednesday, October 21, 2015 7:39:45 AM Christian Decker wrote:
> > On Wed, Oct 21, 2015 at 8:19 AM Luke Dashjr <luke@dashjr.org> wrote:
> > > This doesn't completely close malleability (which should be documented
> in
> > > the BIP), so I'm not sure it's worth the cost, especially if closing
> > > malleability later on would need more. How about specifying flags
> upfront
> > > in the UTXO-creating transaction specifying which parts the signature
> > > will cover? This would allow implementation of fully malleability-proof
> > > wallets.
> >
> > As far as I see it the only remaining venues for malleability are the use
> > of sighash flags that are not SIGHASH_ALL, as mentioned in the BIP. Any
> use
> > of non-sighash_all flags is already an explicit permission to modify the
> > transactions, by adding and removing inputs and outputs, so I don't see
> how
> > these can be made non-malleable. Am I missing something?
>
> Signer malleability is still a notable concern needing consideration.
> Ideally,
> wallets should be trying to actively CoinJoin, bump fees on, etc any
> pending
> transactions in the background. These forms of malleability affect nearly
> as
> many real use cases as third-party malleability.
>
> Luke
>

How is signer malleability still a problem if we remove the signatures from
the transaction ID of the transaction and all preceding transactions? The
signer can re-sign a transaction but it won't change the transaction ID.

It is still possible to double-spend transactions that do not have enough
fees, so just starting a new round of CoinJoin is sufficient to bump fees
for all parties that participate, and that would also result in the
double-spent low fee transaction to be discarded, resolving the state of
all coins in the first CoinJoin tx.

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Luke Dashjr]

On Wednesday, October 21, 2015 8:31:42 AM Christian Decker wrote:
> On Wed, Oct 21, 2015 at 9:52 AM Luke Dashjr <luke@dashjr.org> wrote:
> > On Wednesday, October 21, 2015 7:39:45 AM Christian Decker wrote:
> > > On Wed, Oct 21, 2015 at 8:19 AM Luke Dashjr <luke@dashjr.org> wrote:
> > > > This doesn't completely close malleability (which should be
> > > > documented
> > 
> > in
> > 
> > > > the BIP), so I'm not sure it's worth the cost, especially if closing
> > > > malleability later on would need more. How about specifying flags
> > 
> > upfront
> > 
> > > > in the UTXO-creating transaction specifying which parts the signature
> > > > will cover? This would allow implementation of fully
> > > > malleability-proof wallets.
> > > 
> > > As far as I see it the only remaining venues for malleability are the
> > > use of sighash flags that are not SIGHASH_ALL, as mentioned in the
> > > BIP. Any
> > 
> > use
> > 
> > > of non-sighash_all flags is already an explicit permission to modify
> > > the transactions, by adding and removing inputs and outputs, so I
> > > don't see
> > 
> > how
> > 
> > > these can be made non-malleable. Am I missing something?
> > 
> > Signer malleability is still a notable concern needing consideration.
> > Ideally,
> > wallets should be trying to actively CoinJoin, bump fees on, etc any
> > pending
> > transactions in the background. These forms of malleability affect nearly
> > as
> > many real use cases as third-party malleability.
> > 
> > Luke
> 
> How is signer malleability still a problem if we remove the signatures from
> the transaction ID of the transaction and all preceding transactions? The
> signer can re-sign a transaction but it won't change the transaction ID.

The signer can also change the order of the inputs, the inputs themselves, 
add/remove outputs, etc... all which should be possible without becoming a 
different logical transaction. The only unique property of the logical 
transaction is the scriptPubKey/address.

Luke

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Christian Decker]

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

Hm, that is true as long as the signer is the only signer of the
transaction, otherwise he'd be invalidating the signatures of the other
signers. That can however be fixed by having a canonical ordering of Inputs
and Outputs, which has been discussed before in order to decrease
information that can be gained about the spender. Maybe we can defer to
that effort?

On Wed, Oct 21, 2015 at 10:41 AM Luke Dashjr <luke@dashjr.org> wrote:

> On Wednesday, October 21, 2015 8:31:42 AM Christian Decker wrote:
> > On Wed, Oct 21, 2015 at 9:52 AM Luke Dashjr <luke@dashjr.org> wrote:
> > > On Wednesday, October 21, 2015 7:39:45 AM Christian Decker wrote:
> > > > On Wed, Oct 21, 2015 at 8:19 AM Luke Dashjr <luke@dashjr.org> wrote:
> > > > > This doesn't completely close malleability (which should be
> > > > > documented
> > >
> > > in
> > >
> > > > > the BIP), so I'm not sure it's worth the cost, especially if
> closing
> > > > > malleability later on would need more. How about specifying flags
> > >
> > > upfront
> > >
> > > > > in the UTXO-creating transaction specifying which parts the
> signature
> > > > > will cover? This would allow implementation of fully
> > > > > malleability-proof wallets.
> > > >
> > > > As far as I see it the only remaining venues for malleability are the
> > > > use of sighash flags that are not SIGHASH_ALL, as mentioned in the
> > > > BIP. Any
> > >
> > > use
> > >
> > > > of non-sighash_all flags is already an explicit permission to modify
> > > > the transactions, by adding and removing inputs and outputs, so I
> > > > don't see
> > >
> > > how
> > >
> > > > these can be made non-malleable. Am I missing something?
> > >
> > > Signer malleability is still a notable concern needing consideration.
> > > Ideally,
> > > wallets should be trying to actively CoinJoin, bump fees on, etc any
> > > pending
> > > transactions in the background. These forms of malleability affect
> nearly
> > > as
> > > many real use cases as third-party malleability.
> > >
> > > Luke
> >
> > How is signer malleability still a problem if we remove the signatures
> from
> > the transaction ID of the transaction and all preceding transactions? The
> > signer can re-sign a transaction but it won't change the transaction ID.
>
> The signer can also change the order of the inputs, the inputs themselves,
> add/remove outputs, etc... all which should be possible without becoming a
> different logical transaction. The only unique property of the logical
> transaction is the scriptPubKey/address.
>
> Luke
>

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Luke Dashjr]

On Wednesday, October 21, 2015 8:44:53 AM Christian Decker wrote:
> Hm, that is true as long as the signer is the only signer of the
> transaction, otherwise he'd be invalidating the signatures of the other
> signers.

Or he can just have the other signers re-sign with the modified version.
Even if it only worked with a single signer, it's still a form of malleability 
that your BIP does not presently solve, but would be desirable to solve...

Luke

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Danny Thorpe]

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

A signer modifying the order of inputs or changing outputs when
"re-signing" a transaction (which already has dependent child transactions
spending its outputs) seems like quite a different hazard than a malicious
third party modifying a transaction in the mempool by twiddling opcodes in
the signature scripts.  The former seems like more a matter of keeping your
own house in order (an internal affair) while the latter is an external
threat beyond the transaction writer's control.

While I agree that having a canonical ordering for inputs and outputs might
be useful in some cases, there are also use cases where the relative
positions of inputs and outputs are significant, where reordering would
change the semantics of the transaction.  SIGHASH_SINGLE, for example,
makes an association between an input index and an output index. Open Asset
colored coins are identified by the order of inputs and outputs.

Let's keep canonical ordering separate from the normalized transaction ID
proposal. Baby steps. Normalized transaction IDs provide an immediate
benefit against the hazard of third party manipulation of transactions in
the mempool, even without canonical ordering.

-Danny





On Wed, Oct 21, 2015 at 1:46 AM, Luke Dashjr via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Wednesday, October 21, 2015 8:44:53 AM Christian Decker wrote:
> > Hm, that is true as long as the signer is the only signer of the
> > transaction, otherwise he'd be invalidating the signatures of the other
> > signers.
>
> Or he can just have the other signers re-sign with the modified version.
> Even if it only worked with a single signer, it's still a form of
> malleability
> that your BIP does not presently solve, but would be desirable to solve...
>
> Luke
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Gregory Maxwell]

On Wed, Oct 21, 2015 at 6:22 PM, Danny Thorpe via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> outputs) seems like quite a different hazard than a malicious third party
> modifying a transaction in the mempool by twiddling opcodes in the signature
> scripts.  The former seems like more a matter of keeping your own house in

Indeed they are different, but canonical encoding enforcement prevents
the third party malleability completely on ordinary transactions.

It is an an _immediate_ solution which is already deployed as a
standardness rule-- once miners update to 0.11.1 or 0.10.3 (or
equivalent) only miners will be able to malleable ordinary payments,
to the best of our current understanding.

[snip]
> proposal. Baby steps. Normalized transaction IDs provide an immediate
> benefit against the hazard of third party manipulation of transactions in
> the mempool, even without canonical ordering.

The thing being discussed here does not provide an immediate benefit
to that particular issue.  It addresses multistep contracts and other
cases.

But it does not prevent third party mutation until people change their
public keys to new scheme (which based on p2sh we should expect a well
over a year deployment), which they cannot being doing until a soft
fork is made and settled in the network, for which the code is not yet
written. CLTV suggests that the current timeframe for a soft fork is
around a year and though I'd like to see that improved.

So canonical encoding is both sufficient (to the best of our current
understanding) for preventing third party malleability on ordinary
transactions, and the _only_ option for to have an actually immediate
benefit.

Please don't mix up third party malleability with this work which is
important in its own right.

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Luke Dashjr]

On Wednesday, October 21, 2015 6:22:25 PM Danny Thorpe wrote:
> Let's keep canonical ordering separate from the normalized transaction ID
> proposal. Baby steps. Normalized transaction IDs provide an immediate
> benefit against the hazard of third party manipulation of transactions in
> the mempool, even without canonical ordering.

My point is that third-party manipulation is not much more of a problem than 
signing-party manipulation. Solving the former (at a high cost), without 
solving the latter, seems not worth it IMO.

Luke

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Christian Decker]

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

I think the scenario of the single signer re-ordering the outputs and
inputs and then re-signing the transaction is in the same category of
simple double-spends. The signer could just as well sign a completely
different transaction spending the same coins to somewhere else, so I don't
think there is a lot we can do about it even if we instate a canonical
ordering. Even if we order the inputs and outputs the signer can just add a
new input and output and we would have a different transaction.

Normalized transaction IDs do help in the case that the single signer wants
to immediately follow up its transaction with another transaction spending
the first one's change output, and it prevents any modification in the
multi-signer scenario.

On Thu, Oct 22, 2015 at 1:21 AM Luke Dashjr <luke@dashjr.org> wrote:

> On Wednesday, October 21, 2015 6:22:25 PM Danny Thorpe wrote:
> > Let's keep canonical ordering separate from the normalized transaction ID
> > proposal. Baby steps. Normalized transaction IDs provide an immediate
> > benefit against the hazard of third party manipulation of transactions in
> > the mempool, even without canonical ordering.
>
> My point is that third-party manipulation is not much more of a problem
> than
> signing-party manipulation. Solving the former (at a high cost), without
> solving the latter, seems not worth it IMO.
>
> Luke
>

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Gregory Maxwell]

On Thu, Oct 22, 2015 at 8:26 AM, Christian Decker via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> Normalized transaction IDs do help in the case that the single signer wants
> to immediately follow up its transaction with another transaction spending
> the first one's change output, and it prevents any modification in the
> multi-signer scenario.

For ordinary transactions which are not performing interesting smart
contracts that particular is better addressed via canonical encoding,
which is immediately available and doesn't have the associated costs
(new pubkey type adoption, 20%-30% UTXO size increase, need for nodes
to fixup txid references, etc.).

Please, as I said up-thread: this is good and importantstuff to work
on, but it shouldn't be oversold.

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Christian Decker]

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

Indeed the reason I got started with all of this is the use of normalized
transaction IDs within smart contracts with multiple signers. Sorry if I
was perceived as overselling it :-)

So to summarize the discussions that have been on-going here as well as in
the PR so far, most people seem to agree that the BIP is an improvement for
smart-contracts as well as the third-party modification scenario. It comes
at the cost of increased UTXO size due to the additional hash being stored
per transaction with unclaimed outputs and some additional computations.
The additional computation is for the normalized ID computation and the
swapping in of normalized IDs during verification. No additional coin
lookups are needed as they are retrieved and cached anyway when verifying
the transaction. Would everybody agree with this assessment so far?

On the PR there were some additional suggestions of treating singlesig
transactions as 1-of-1 transactions and using Schnorr signatures for the
new opcode. Schnorr has been in the works for a long time and gives a
multitude of advantages, e.g., batch validation, and seems like a good
addition. Since the verify flag is mandatory due to the soft-fork migration
and we might merge singlesig and multisig into a single opcode we can
replace the bitmap of flags with a simple version number. Clients would
fall back to OP_NOP behaviour for versions they do not implement,
maintaining soft-fork semantics to build more future signing and
verification methods.

On Thu, Oct 22, 2015 at 10:57 AM Gregory Maxwell <gmaxwell@gmail.com> wrote:

> On Thu, Oct 22, 2015 at 8:26 AM, Christian Decker via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > Normalized transaction IDs do help in the case that the single signer
> wants
> > to immediately follow up its transaction with another transaction
> spending
> > the first one's change output, and it prevents any modification in the
> > multi-signer scenario.
>
> For ordinary transactions which are not performing interesting smart
> contracts that particular is better addressed via canonical encoding,
> which is immediately available and doesn't have the associated costs
> (new pubkey type adoption, 20%-30% UTXO size increase, need for nodes
> to fixup txid references, etc.).
>
> Please, as I said up-thread: this is good and importantstuff to work
> on, but it shouldn't be oversold.
>

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Luke Dashjr]

On Thursday, October 22, 2015 8:26:58 AM Christian Decker wrote:
> I think the scenario of the single signer re-ordering the outputs and
> inputs and then re-signing the transaction is in the same category of
> simple double-spends. The signer could just as well sign a completely
> different transaction spending the same coins to somewhere else, so I don't
> think there is a lot we can do about it even if we instate a canonical
> ordering. Even if we order the inputs and outputs the signer can just add a
> new input and output and we would have a different transaction.
> 
> Normalized transaction IDs do help in the case that the single signer wants
> to immediately follow up its transaction with another transaction spending
> the first one's change output, and it prevents any modification in the
> multi-signer scenario.

Except that unlike malicious double spending, adding more outputs to 
unconfirmed transactions is what wallets *should ideally be doing every time 
they send another transaction*. Spending unconfirmed change is the wrong 
approach. So half-fixing malleability as this PR would, encourages 
inefficient behaviour in multiple ways (first, by not making it malleability-
safe; second, by encouraging spending unconfirmed change).

Luke

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Christian Decker]

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

Ok, getting the ball rolling again after some downtime. I amended the
proposal to use a simple version number instead of the binary flags, added
the normalization of inputs before computing the signaturehash and added
Schnorr signatures as requested.

The BIP has also been assigned number 130 :-)

I am still very much intrigued by Luke's idea of having empty scriptsigs
and ship the signatures in external scripts, however the proposal uses the
on-the-fly normalization because we have no good way of relaying the
external scripts. Since we are still in the drafting phase I am open to
suggestions and if there is a good/working solution I can amend/withdraw
the proposal.

As for open venues for malleability, I'm not sure we can fix them at all,
after all the ability of a single signer to doublespend by
appending/replacing inputs/outputs in an arbitrary fashion is not fixable
IMHO and will cause any future transaction building on its outputs to be
orphaned. What would the perfect properties for such a fix be?

Regards,
Christian

On Thu, Oct 22, 2015 at 11:05 AM Luke Dashjr <luke@dashjr.org> wrote:

> On Thursday, October 22, 2015 8:26:58 AM Christian Decker wrote:
> > I think the scenario of the single signer re-ordering the outputs and
> > inputs and then re-signing the transaction is in the same category of
> > simple double-spends. The signer could just as well sign a completely
> > different transaction spending the same coins to somewhere else, so I
> don't
> > think there is a lot we can do about it even if we instate a canonical
> > ordering. Even if we order the inputs and outputs the signer can just
> add a
> > new input and output and we would have a different transaction.
> >
> > Normalized transaction IDs do help in the case that the single signer
> wants
> > to immediately follow up its transaction with another transaction
> spending
> > the first one's change output, and it prevents any modification in the
> > multi-signer scenario.
>
> Except that unlike malicious double spending, adding more outputs to
> unconfirmed transactions is what wallets *should ideally be doing every
> time
> they send another transaction*. Spending unconfirmed change is the wrong
> approach. So half-fixing malleability as this PR would, encourages
> inefficient behaviour in multiple ways (first, by not making it
> malleability-
> safe; second, by encouraging spending unconfirmed change).
>
> Luke
>

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Luke Dashjr]

On Tuesday, November 03, 2015 8:37:44 PM Christian Decker wrote:
> I am still very much intrigued by Luke's idea of having empty scriptsigs
> and ship the signatures in external scripts, however the proposal uses the
> on-the-fly normalization because we have no good way of relaying the
> external scripts. Since we are still in the drafting phase I am open to
> suggestions and if there is a good/working solution I can amend/withdraw
> the proposal.

Changing the network protocol is trivial in comparison to making a permanent 
increase in UTXO set costs.

> As for open venues for malleability, I'm not sure we can fix them at all,
> after all the ability of a single signer to doublespend by
> appending/replacing inputs/outputs in an arbitrary fashion is not fixable
> IMHO and will cause any future transaction building on its outputs to be
> orphaned. What would the perfect properties for such a fix be?

The problem isn't changing inputs/outputs, but that such changes invalidate 
later spends. In particular, note that wallets *should ideally* be actively 
trying to make transfers using multiple malleated versions of the same 
payment.

So the way to make an anti-malleable wallet, would be to strictly enforce the 
no-address-reuse rule on payments received (note this has no effect on 
other/current wallets) and rely only on the hash of that scriptPubKey+value 
for the input in subsequent transactions. This way, no matter what inputs or 
other outputs the transaction paying the address/invoice uses, the subsequent 
transaction ignores them and remains valid. (I am not suggesting this as a 
mandatory change that all wallets must adopt to receive the current semi-
malleability protection you propose - only that it be *possible* for wallets 
to upgrade to or offer in the future.)

Luke

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Christian Decker]

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

On Tue, Nov 3, 2015 at 9:49 PM Luke Dashjr <luke@dashjr.org> wrote:

> On Tuesday, November 03, 2015 8:37:44 PM Christian Decker wrote:
> > I am still very much intrigued by Luke's idea of having empty scriptsigs
> > and ship the signatures in external scripts, however the proposal uses
> the
> > on-the-fly normalization because we have no good way of relaying the
> > external scripts. Since we are still in the drafting phase I am open to
> > suggestions and if there is a good/working solution I can amend/withdraw
> > the proposal.
>
> Changing the network protocol is trivial in comparison to making a
> permanent
> increase in UTXO set costs.
>

Ok, so assuming we can get a connected component of upgraded nodes that
relay both the transaction and the associated external scripts then we
could just piggyback the external scripts on top of the normal messages.
Non-upgraded nodes will read the entire two-part message but only parse the
classical transaction, dropping the external script. Validation rules for
upgraded nodes are the same as before: if the attached signatures are
invalid the entire TX is dropped. We have to commit to the external scripts
used during the creation of a block. I think the easiest way to add this
commitment is the coinbase input I guess, and following the transaction
list a new list of signature lists is shipped with the rest of the block.
Non-upgraded will ignore it as before.

Would that work? It all hinges on having upgraded miners in a connected
component otherwise non-upgraded nodes will drop the external scripts on
the way (since they parse and then reconstruct the messages along the
path). But if it works this could be a much nicer solution.


>
> > As for open venues for malleability, I'm not sure we can fix them at all,
> > after all the ability of a single signer to doublespend by
> > appending/replacing inputs/outputs in an arbitrary fashion is not fixable
> > IMHO and will cause any future transaction building on its outputs to be
> > orphaned. What would the perfect properties for such a fix be?
>
> The problem isn't changing inputs/outputs, but that such changes invalidate
> later spends. In particular, note that wallets *should ideally* be actively
> trying to make transfers using multiple malleated versions of the same
> payment.
>

So this is indeed a form of desired malleability we will likely not be able
to fix. I'd argue that this goes more into the direction of double-spending
than a form of malleability, and is mostly out of scope for this BIP. As
the abstract mentions this BIP attempts to eliminate damage incurred by
malleability in the third party modification scenario and in the multisig
scenario, with the added benefit of enabling transaction templating. If we
can get the segregated witnesses approach working all the better, we don't
even have the penalty of increased UTXO size. The problem of singlesig
users doublespending their outputs to update transactions remains a problem
even then.


>
> So the way to make an anti-malleable wallet, would be to strictly enforce
> the
> no-address-reuse rule on payments received (note this has no effect on
> other/current wallets) and rely only on the hash of that scriptPubKey+value
> for the input in subsequent transactions. This way, no matter what inputs
> or
> other outputs the transaction paying the address/invoice uses, the
> subsequent
> transaction ignores them and remains valid. (I am not suggesting this as a
> mandatory change that all wallets must adopt to receive the current semi-
> malleability protection you propose - only that it be *possible* for
> wallets
> to upgrade to or offer in the future.)
>

Sounds very interesting. That would then be a new signature checking opcode
I guess that would allow the transaction hash in the input be replaced by
the hash of the serialized output it is spending? That way the transaction
would not be detached from the coins unless the amount or the scriptpubkey
(containing the address) is modified. So a user may add new outputs and
inputs to an existing transaction like you mentioned. This does not help
someone receiving funds from a sender to build new transactions on top
since the sender may simply doublespend its output before it is confirmed.
I think this is probably best addressed in a separate proposal.


>
> Luke
>

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Luke Dashjr]

On Tuesday, November 03, 2015 9:44:02 PM Christian Decker wrote:
> Ok, so assuming we can get a connected component of upgraded nodes that
> relay both the transaction and the associated external scripts then we
> could just piggyback the external scripts on top of the normal messages.
> Non-upgraded nodes will read the entire two-part message but only parse the
> classical transaction, dropping the external script. Validation rules for
> upgraded nodes are the same as before: if the attached signatures are
> invalid the entire TX is dropped. We have to commit to the external scripts
> used during the creation of a block. I think the easiest way to add this
> commitment is the coinbase input I guess, and following the transaction
> list a new list of signature lists is shipped with the rest of the block.
> Non-upgraded will ignore it as before.

I'd throw it in the merged-mining tree; it's not ideal, but it can be swapped 
out for something better when it's ready (I'm working on such a BIP - 
hopefully it can be before or at the same time as a SW deployment).

> Would that work? It all hinges on having upgraded miners in a connected
> component otherwise non-upgraded nodes will drop the external scripts on
> the way (since they parse and then reconstruct the messages along the
> path). But if it works this could be a much nicer solution.

It's actually better than that. If miners don't get the SW transactions, then 
they just won't mine them, and the wallets will continue to rebroadcast until 
they do. But realistically, the entire network will likely be running SW-
capable nodes long before any wallets have deployed SW transactions.

> > > As for open venues for malleability, I'm not sure we can fix them at
> > > all, after all the ability of a single signer to doublespend by
> > > appending/replacing inputs/outputs in an arbitrary fashion is not
> > > fixable IMHO and will cause any future transaction building on its
> > > outputs to be orphaned. What would the perfect properties for such a
> > > fix be?
> > 
> > The problem isn't changing inputs/outputs, but that such changes
> > invalidate later spends. In particular, note that wallets *should
> > ideally* be actively trying to make transfers using multiple malleated
> > versions of the same payment.
> 
> So this is indeed a form of desired malleability we will likely not be able
> to fix. I'd argue that this goes more into the direction of double-spending
> than a form of malleability, and is mostly out of scope for this BIP. As
> the abstract mentions this BIP attempts to eliminate damage incurred by
> malleability in the third party modification scenario and in the multisig
> scenario, with the added benefit of enabling transaction templating. If we
> can get the segregated witnesses approach working all the better, we don't
> even have the penalty of increased UTXO size. The problem of singlesig
> users doublespending their outputs to update transactions remains a problem
> even then.

I don't know what you're trying to say here. Double spending to the same 
destination(s) and malleability are literally the same thing. Things affected 
by malleability are still just as broken even with this BIP - whether it is 
triggered by a third-party or not is not very relevant.

> > So the way to make an anti-malleable wallet, would be to strictly enforce
> > the
> > no-address-reuse rule on payments received (note this has no effect on
> > other/current wallets) and rely only on the hash of that
> > scriptPubKey+value for the input in subsequent transactions. This way,
> > no matter what inputs or
> > other outputs the transaction paying the address/invoice uses, the
> > subsequent
> > transaction ignores them and remains valid. (I am not suggesting this as
> > a mandatory change that all wallets must adopt to receive the current
> > semi- malleability protection you propose - only that it be *possible*
> > for wallets
> > to upgrade to or offer in the future.)
> 
> Sounds very interesting. That would then be a new signature checking opcode
> I guess that would allow the transaction hash in the input be replaced by
> the hash of the serialized output it is spending? That way the transaction
> would not be detached from the coins unless the amount or the scriptpubkey
> (containing the address) is modified. So a user may add new outputs and
> inputs to an existing transaction like you mentioned. 

Correct...

> This does not help someone receiving funds from a sender to build new
> transactions on top since the sender may simply doublespend its output
> before it is confirmed. I think this is probably best addressed in a
> separate proposal.

Huh??

Luke

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Jorge Timón]

On Tue, Nov 3, 2015 at 11:01 PM, Luke Dashjr via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> On Tuesday, November 03, 2015 9:44:02 PM Christian Decker wrote:
>> So this is indeed a form of desired malleability we will likely not be able
>> to fix. I'd argue that this goes more into the direction of double-spending
>> than a form of malleability, and is mostly out of scope for this BIP. As
>> the abstract mentions this BIP attempts to eliminate damage incurred by
>> malleability in the third party modification scenario and in the multisig
>> scenario, with the added benefit of enabling transaction templating. If we
>> can get the segregated witnesses approach working all the better, we don't
>> even have the penalty of increased UTXO size. The problem of singlesig
>> users doublespending their outputs to update transactions remains a problem
>> even then.
>
> I don't know what you're trying to say here. Double spending to the same
> destination(s) and malleability are literally the same thing. Things affected
> by malleability are still just as broken even with this BIP - whether it is
> triggered by a third-party or not is not very relevant.

I think this is just a terminology confusion.
There's conflicting spends of the same outputs (aka unconfirmed
double-spends), and there's signature malleability which Segregated
Witnesses solves.
If we want to define malleability as signature malleability +
conflicting spends, then that's fine.
But it seems Christian is mostly interested in signature malleability,
which is what SW can solve.
In fact, creating conflicting spends is sometimes useful for some
contracts (ie to cancel the contract when that's supposed to be
allowed).
Maybe it is "incorrect" that people use "malleability" when they're
specifically talking about "signature malleability", but I think that
in this case it's clear that we're talking about transactions having
an id that cannot be changed just by signing with a different nonce
(what SW provides).

Please, Christian, correct me if you mean something else.

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Luke Dashjr]

On Thursday, November 05, 2015 3:27:37 PM Jorge Timón wrote:
> On Tue, Nov 3, 2015 at 11:01 PM, Luke Dashjr via bitcoin-dev
> 
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > On Tuesday, November 03, 2015 9:44:02 PM Christian Decker wrote:
> >> So this is indeed a form of desired malleability we will likely not be
> >> able to fix. I'd argue that this goes more into the direction of
> >> double-spending than a form of malleability, and is mostly out of scope
> >> for this BIP. As the abstract mentions this BIP attempts to eliminate
> >> damage incurred by malleability in the third party modification
> >> scenario and in the multisig scenario, with the added benefit of
> >> enabling transaction templating. If we can get the segregated witnesses
> >> approach working all the better, we don't even have the penalty of
> >> increased UTXO size. The problem of singlesig users doublespending
> >> their outputs to update transactions remains a problem even then.
> > 
> > I don't know what you're trying to say here. Double spending to the same
> > destination(s) and malleability are literally the same thing. Things
> > affected by malleability are still just as broken even with this BIP -
> > whether it is triggered by a third-party or not is not very relevant.
> 
> I think this is just a terminology confusion.
> There's conflicting spends of the same outputs (aka unconfirmed
> double-spends), and there's signature malleability which Segregated
> Witnesses solves.
> If we want to define malleability as signature malleability +
> conflicting spends, then that's fine.
> But it seems Christian is mostly interested in signature malleability,
> which is what SW can solve.
> In fact, creating conflicting spends is sometimes useful for some
> contracts (ie to cancel the contract when that's supposed to be
> allowed).
> Maybe it is "incorrect" that people use "malleability" when they're
> specifically talking about "signature malleability", but I think that
> in this case it's clear that we're talking about transactions having
> an id that cannot be changed just by signing with a different nonce
> (what SW provides).

Ok, then my point is that "signature malleability" is not particularly 
problematic or interesting alone, and the only way to get a practically-useful 
solution, is to address all kinds of malleability.

Luke

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Jorge Timón]

On Thu, Nov 5, 2015 at 8:36 PM, Luke Dashjr <luke@dashjr.org> wrote:
> Ok, then my point is that "signature malleability" is not particularly
> problematic or interesting alone, and the only way to get a practically-useful
> solution, is to address all kinds of malleability.

I disagree. Segregated witnesses, for example, doesn't solve all kinds
of malleability and is very useful in some practical cases by solving
all signature malleability.
As said, we don't want to eliminate all forms of malleability (for
example, replace by fee), although we may want to "address them" at
some level.
As you have said, wallets should be looking at scriptPubKeys, not
transaction ID, but that is orthogonal to SW, a normalized tx ID and
signature malleability.

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[s7r]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Right. Wallets are covering malleability in acceptable ways. Normal
user to user payments aren't (or at least shouldn't be) affected by
malleability.

Problems appear in second level and third level malleability, when
Alice sends txB to Bob which spends from txA which is unconfirmed. If
txA changes txid, txB becomes useless and invalidates Alice's payment.
Looking at scriptPubKeys instead of transaction IDs doesn't help in
this context.

This is the reason why some type of contracts are not workable or not
100% safe. One can't pre-sign a refund transaction with an nLockTime
in the future: the payer will provide the funding transaction ID from
which the refund tx will spend, but if the transaction ID of the
funding transaction is affected by malleability (third party
malleability, since the signer doesn't have interest to do so) the
refund tx becomes useless.

On 11/5/2015 10:25 PM, Jorge Timón via bitcoin-dev wrote:
> On Thu, Nov 5, 2015 at 8:36 PM, Luke Dashjr <luke@dashjr.org>
> wrote:
>> Ok, then my point is that "signature malleability" is not
>> particularly problematic or interesting alone, and the only way
>> to get a practically-useful solution, is to address all kinds of
>> malleability.
> 
> I disagree. Segregated witnesses, for example, doesn't solve all
> kinds of malleability and is very useful in some practical cases by
> solving all signature malleability. As said, we don't want to
> eliminate all forms of malleability (for example, replace by fee),
> although we may want to "address them" at some level. As you have
> said, wallets should be looking at scriptPubKeys, not transaction
> ID, but that is orthogonal to SW, a normalized tx ID and signature
> malleability.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.22 (MingW32)

iQEcBAEBCAAGBQJWO9w7AAoJEIN/pSyBJlsR2BsH+gMwxJ/isiWfJF12LJ9s4wat
Bd/K2Ld+Lyk5BRs+6rQzv5NeeYjYC3FtNFV+z1Z1dMDd752cUfEZqQA9dt9nl0E7
BEia3RSFii1k2L/4xwiIWKZM20qoiykou41J56GZrJa9SoP+9kg8iLq8CokahakP
PLjfBrTylJBsgq34foPPaOH9ckOa/RJpx3WHrRFTPhxbTCm1Ezv6jAZmYr9tTi1h
afzU0YayzLUIb9xH8vfODY2qMJ91uguTUZYCGuopDYhom5GMw8zss0kG5FdEZrEQ
Z7srQmKQ0SRMtiSlg6lg3d8TS5Mv1gIp1HcL+gtMFroi38pJS8dXT65nGjg0Epc=
=ZhVA
-----END PGP SIGNATURE-----

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Adam Back]

About the conflicting spends by the private key holder (self signature
malleability) that is in principle kind of fixable.

You make a new pub key type which is r,Q (where r is the DSA signature
component but chosen at key gen time, Q=xG is the pub key, r is point
compressed R = (r,f(r)) = kG ), r is the pre-computable part of an
ECDSA signature (unrelated to the message which can be decided later).

You make a new address type which is a = H(r,Q).

Then you make a new signature type which requires that the r from
sig=(r,s) matches the r committed to in the address.

As the ECDSA signature is s=(H(m)+r*x)/k mod n, if they sign two
different messages with the same r value they reveal the private key
via simultaneous equation, as s=(H(m)+r*x)/k and s'=(H(m')+r*x)/k and
solving k=(H(m)-H(m'))/(s-s') and x=(sk-H(m))/r allowing anyone who
sees both double spends to spend as they can replace the signature
with their own one.  That converts double signatures into miner can
spend.

It doesnt necessarily enforce no pubkey reuse (Q), as a=H(r,Q) and
a'=H(r',Q) are different addresses, though it does enforce no
extended-address reuse (H=(r,Q)).
Binary failure address reuse could be an issue.  Puts pressure on
transactional storage on wallets.

Adam

On 5 November 2015 at 20:36, Luke Dashjr via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> On Thursday, November 05, 2015 3:27:37 PM Jorge Timón wrote:
>> On Tue, Nov 3, 2015 at 11:01 PM, Luke Dashjr via bitcoin-dev
>>
>> <bitcoin-dev@lists.linuxfoundation.org> wrote:
>> > On Tuesday, November 03, 2015 9:44:02 PM Christian Decker wrote:
>> >> So this is indeed a form of desired malleability we will likely not be
>> >> able to fix. I'd argue that this goes more into the direction of
>> >> double-spending than a form of malleability, and is mostly out of scope
>> >> for this BIP. As the abstract mentions this BIP attempts to eliminate
>> >> damage incurred by malleability in the third party modification
>> >> scenario and in the multisig scenario, with the added benefit of
>> >> enabling transaction templating. If we can get the segregated witnesses
>> >> approach working all the better, we don't even have the penalty of
>> >> increased UTXO size. The problem of singlesig users doublespending
>> >> their outputs to update transactions remains a problem even then.
>> >
>> > I don't know what you're trying to say here. Double spending to the same
>> > destination(s) and malleability are literally the same thing. Things
>> > affected by malleability are still just as broken even with this BIP -
>> > whether it is triggered by a third-party or not is not very relevant.
>>
>> I think this is just a terminology confusion.
>> There's conflicting spends of the same outputs (aka unconfirmed
>> double-spends), and there's signature malleability which Segregated
>> Witnesses solves.
>> If we want to define malleability as signature malleability +
>> conflicting spends, then that's fine.
>> But it seems Christian is mostly interested in signature malleability,
>> which is what SW can solve.
>> In fact, creating conflicting spends is sometimes useful for some
>> contracts (ie to cancel the contract when that's supposed to be
>> allowed).
>> Maybe it is "incorrect" that people use "malleability" when they're
>> specifically talking about "signature malleability", but I think that
>> in this case it's clear that we're talking about transactions having
>> an id that cannot be changed just by signing with a different nonce
>> (what SW provides).
>
> Ok, then my point is that "signature malleability" is not particularly
> problematic or interesting alone, and the only way to get a practically-useful
> solution, is to address all kinds of malleability.
>
> Luke
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Christian Decker]

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

On Thu, Nov 5, 2015 at 4:27 PM Jorge Timón <jtimon@jtimon.cc> wrote:

> I think this is just a terminology confusion.
> There's conflicting spends of the same outputs (aka unconfirmed
> double-spends), and there's signature malleability which Segregated
> Witnesses solves.
> If we want to define malleability as signature malleability +
> conflicting spends, then that's fine.
> But it seems Christian is mostly interested in signature malleability,
> which is what SW can solve.
> In fact, creating conflicting spends is sometimes useful for some
> contracts (ie to cancel the contract when that's supposed to be
> allowed).
> Maybe it is "incorrect" that people use "malleability" when they're
> specifically talking about "signature malleability", but I think that
> in this case it's clear that we're talking about transactions having
> an id that cannot be changed just by signing with a different nonce
> (what SW provides).
>
> Please, Christian, correct me if you mean something else.
>

Yes, your differentiation is spot on. My main goal is to eliminate the risk
of detaching transactions in  off-blockchain protocols that rely on a
number of transactions being chained, hence solving signature malleability
might be the correct term. Canonical encodings do address part of the
problem, however they do nothing in the case of one of the signers
re-signing a transaction and detaching any followup transaction. Also
having transaction templates is a nice way to reduce the complexity of
protocols by eliminating some of the "who signs what when" gotchas.
Segregated witnesses would be a perfect solution, we just need to find a
good migration plan for Bitcoin :-)

Sorry for the confusion caused by me misusing the term malleability, I'll
use signature malleability in the future :-)

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Peter Todd]

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

On Tue, Nov 03, 2015 at 09:44:02PM +0000, Christian Decker via bitcoin-dev wrote:
> Ok, so assuming we can get a connected component of upgraded nodes that
> relay both the transaction and the associated external scripts then we
> could just piggyback the external scripts on top of the normal messages.
> Non-upgraded nodes will read the entire two-part message but only parse the
> classical transaction, dropping the external script. Validation rules for
> upgraded nodes are the same as before: if the attached signatures are
> invalid the entire TX is dropped. We have to commit to the external scripts
> used during the creation of a block. I think the easiest way to add this
> commitment is the coinbase input I guess, and following the transaction
> list a new list of signature lists is shipped with the rest of the block.
> Non-upgraded will ignore it as before.
> 
> Would that work? It all hinges on having upgraded miners in a connected
> component otherwise non-upgraded nodes will drop the external scripts on
> the way (since they parse and then reconstruct the messages along the
> path). But if it works this could be a much nicer solution.

FWIW my replace-by-fee fork does preferential peering with other RBF
nodes to ensure that you'll always be connected to at least some
full-RBF peers. In practice this works very well, and I'm sure a similar
scheme could be used in this situation as well.

Basically, conceptually unless you're connected to peers that advertise
that they relay the new data, you treat the situation as though you're
not connected to any peers at all. No different than if for some reason
none of your peers were advertising NODE_NETWORK.

-- 
'peter'[:-1]@petertodd.org
00000000000000000247b0e7436a5169ac6f9087be0295d10b07bf0bcbd4c0cc

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Christian Decker]

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

This does indeed sound reasonable. The chances of having a cut in the
network consisting of non-upgraded nodes partitioning the network and not
forwarding the segregated witnesses should be minimal, given a long rollout
phase before the activation.

If everybody agrees that this is a better way to approach the normalization
issue we should probably start writing it up and see if we can get critical
mass behind it :-)

On Wed, Nov 4, 2015 at 5:00 AM Peter Todd <pete@petertodd.org> wrote:

> On Tue, Nov 03, 2015 at 09:44:02PM +0000, Christian Decker via bitcoin-dev
> wrote:
> > Ok, so assuming we can get a connected component of upgraded nodes that
> > relay both the transaction and the associated external scripts then we
> > could just piggyback the external scripts on top of the normal messages.
> > Non-upgraded nodes will read the entire two-part message but only parse
> the
> > classical transaction, dropping the external script. Validation rules for
> > upgraded nodes are the same as before: if the attached signatures are
> > invalid the entire TX is dropped. We have to commit to the external
> scripts
> > used during the creation of a block. I think the easiest way to add this
> > commitment is the coinbase input I guess, and following the transaction
> > list a new list of signature lists is shipped with the rest of the block.
> > Non-upgraded will ignore it as before.
> >
> > Would that work? It all hinges on having upgraded miners in a connected
> > component otherwise non-upgraded nodes will drop the external scripts on
> > the way (since they parse and then reconstruct the messages along the
> > path). But if it works this could be a much nicer solution.
>
> FWIW my replace-by-fee fork does preferential peering with other RBF
> nodes to ensure that you'll always be connected to at least some
> full-RBF peers. In practice this works very well, and I'm sure a similar
> scheme could be used in this situation as well.
>
> Basically, conceptually unless you're connected to peers that advertise
> that they relay the new data, you treat the situation as though you're
> not connected to any peers at all. No different than if for some reason
> none of your peers were advertising NODE_NETWORK.
>
> --
> 'peter'[:-1]@petertodd.org
> 00000000000000000247b0e7436a5169ac6f9087be0295d10b07bf0bcbd4c0cc
>

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Gregory Maxwell]

On Wed, Oct 21, 2015 at 6:18 AM, Luke Dashjr via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> On Monday, October 19, 2015 2:01:04 PM Christian Decker via bitcoin-dev wrote:
>> The proposal is implemented (see below), by computing the normalized
>> transaction ID when adding them to the UTXO and storing them along with the
>> coin state. OP_CHECKSIGEX mostly duplicates OP_CHECKSIG and
>> OP_CHECKMULTISIG, but I'm hoping somebody can give me some pointers into
>> how to best refactor the common functionality into reusable blocks. And the
>> annotating incoming transactions with their normalized inputs is a bit
>> cumbersome, maye somebody has some pointers here as well?
>
> This doesn't completely close malleability (which should be documented in the
> BIP), so I'm not sure it's worth the cost, especially if closing malleability
> later on would need more. How about specifying flags upfront in the UTXO-
> creating transaction specifying which parts the signature will cover? This
> would allow implementation of fully malleability-proof wallets.
>
> Additionally, you have a flag to control whether the opcode behaves as VERIFY
> or not. Non-VERIFY is not possible as a softfork (without doing a second/new
> P2SH) since it can be negated.

Flagability cannot work recursively which is necessary for any
improvement to be useful for multi-phase protocols. (which, I think,
is the only real application of this class of improvement-- third
party mutation can be prevented by enforced canonical encodings;)

One still wants sighash flags--, but they're going to inherently
result in malleability.

I'm still sad that uniform segregated witeness is so hard to deploy,
adding another id to every utxo set won't be a nice cost. :( But I
have been trying for a long time to come up with anything better and
not being successful.

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Gregory Maxwell]

On Wed, Oct 21, 2015 at 7:48 AM, Gregory Maxwell <gmaxwell@gmail.com> wrote:
> I'm still sad that uniform segregated witeness is so hard to deploy,
> adding another id to every utxo set won't be a nice cost. :( But I
> have been trying for a long time to come up with anything better and
> not being successful.

Oh good. Luke solved it.

To deploy SW without a disruptive flag day this encoding could be used:

A new P2SH like scriptPubkey type is defined. In the soft-fork, the
scriptsig for this scriptPubkey is required to be empty.

Signatures are not covered under txid, but carried along side. Then
committed to in blocks in a separate hashtree.

The only disadvantage to the approach used in elements alpha that I
can come up with so far (in the few minutes since luke turned my can't
into a can) is that that the approach in EA did not disrupt the normal
relay handling process, and this would, since relay that transports
the extradata either needs to use a different hash that includes the
witness, or have a separate mechanism for witness transport.

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Christian Decker]

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

On Wed, Oct 21, 2015 at 10:26 AM Gregory Maxwell <gmaxwell@gmail.com> wrote:

> On Wed, Oct 21, 2015 at 7:48 AM, Gregory Maxwell <gmaxwell@gmail.com>
> wrote:
> > I'm still sad that uniform segregated witeness is so hard to deploy,
> > adding another id to every utxo set won't be a nice cost. :( But I
> > have been trying for a long time to come up with anything better and
> > not being successful.
>
> Oh good. Luke solved it.
>
> To deploy SW without a disruptive flag day this encoding could be used:
>
> A new P2SH like scriptPubkey type is defined. In the soft-fork, the
> scriptsig for this scriptPubkey is required to be empty.
>
> Signatures are not covered under txid, but carried along side. Then
> committed to in blocks in a separate hashtree.
>
>
Isn't that sort of what this BIP describes as well? Except that we use the
scriptSig to transport the signatures internally to the transactions and
strip them when it comes to signing/checking? The wire format and transport
of transactions do not change so old clients continue to fetch and process
transactions as before, they just can't verify the TX. Blocks still
reference the instance but verification uses the stripped TX with the
signatures on the side, etc.


> The only disadvantage to the approach used in elements alpha that I
> can come up with so far (in the few minutes since luke turned my can't
> into a can) is that that the approach in EA did not disrupt the normal
> relay handling process, and this would, since relay that transports
> the extradata either needs to use a different hash that includes the
> witness, or have a separate mechanism for witness transport.
>

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Christian Decker]

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

Ok, so the normalization step could add a sorting step for inputs/outputs
(which is going to be nasty for SIGHASH_SINGLE), that would solve the issue.

On Wed, Oct 21, 2015 at 10:49 AM Christian Decker <
decker.christian@gmail.com> wrote:

> On Wed, Oct 21, 2015 at 10:26 AM Gregory Maxwell <gmaxwell@gmail.com>
> wrote:
>
>> On Wed, Oct 21, 2015 at 7:48 AM, Gregory Maxwell <gmaxwell@gmail.com>
>> wrote:
>> > I'm still sad that uniform segregated witeness is so hard to deploy,
>> > adding another id to every utxo set won't be a nice cost. :( But I
>> > have been trying for a long time to come up with anything better and
>> > not being successful.
>>
>> Oh good. Luke solved it.
>>
>> To deploy SW without a disruptive flag day this encoding could be used:
>>
>> A new P2SH like scriptPubkey type is defined. In the soft-fork, the
>> scriptsig for this scriptPubkey is required to be empty.
>>
>> Signatures are not covered under txid, but carried along side. Then
>> committed to in blocks in a separate hashtree.
>>
>>
> Isn't that sort of what this BIP describes as well? Except that we use the
> scriptSig to transport the signatures internally to the transactions and
> strip them when it comes to signing/checking? The wire format and transport
> of transactions do not change so old clients continue to fetch and process
> transactions as before, they just can't verify the TX. Blocks still
> reference the instance but verification uses the stripped TX with the
> signatures on the side, etc.
>
>
>> The only disadvantage to the approach used in elements alpha that I
>> can come up with so far (in the few minutes since luke turned my can't
>> into a can) is that that the approach in EA did not disrupt the normal
>> relay handling process, and this would, since relay that transports
>> the extradata either needs to use a different hash that includes the
>> witness, or have a separate mechanism for witness transport.
>>
>

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

Re: [bitcoin-dev] [BIP] Normalized transaction IDs

[Gregory Maxwell]

On Wed, Oct 21, 2015 at 8:49 AM, Christian Decker
<decker.christian@gmail.com> wrote:
> Isn't that sort of what this BIP describes as well? Except that we use the
> scriptSig to transport the signatures internally to the transactions and
> strip them when it comes to signing/checking? The wire format and transport
> of transactions do not change so old clients continue to fetch and process
> transactions as before, they just can't verify the TX. Blocks still
> reference the instance but verification uses the stripped TX with the
> signatures on the side, etc.

"sort of"

Using the sighash normalization doesn't allow creating a utxo set or
scanning the blockchain while only transferring ~1/3rd of the data
(allowing for reduced security fast start, and private lite wallets);
it requires txin ID rewriting when the witness changes on a parent
transaction; it requires hashing each transaction multiple times (for
the normalized ID, and the old ID), it requires storing two IDs for
every transaction in the UTXO set. -- but indeed, it's easier to
deploy (though not infinitely easier as I thought before).