[bitcoin-dev] [BIP] Normalized transaction IDs

[Christian Decker via bitcoin-dev]

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

[Tier Nolan via bitcoin-dev]

On Mon, Oct 19, 2015 at 3:01 PM, Christian Decker via bitcoin-dev <

Post by Christian Decker via bitcoin-dev
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.

[Christian Decker via bitcoin-dev]

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 <

Post by Tier Nolan via bitcoin-dev
On Mon, Oct 19, 2015 at 3:01 PM, Christian Decker via bitcoin-dev <

Post by Christian Decker via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[s7r via bitcoin-dev]

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)?

Post by Tier Nolan via bitcoin-dev
On Mon, Oct 19, 2015 at 3:01 PM, Christian Decker via bitcoin-dev
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.

[Christian Decker via bitcoin-dev]

On Tue, Oct 20, 2015 at 12:23 AM s7r via bitcoin-dev <

Post by s7r via bitcoin-dev
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.

Post by s7r via bitcoin-dev
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.

Post by s7r via bitcoin-dev
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

Post by s7r via bitcoin-dev

Post by Tier Nolan via bitcoin-dev
On Mon, Oct 19, 2015 at 3:01 PM, Christian Decker via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Luke Dashjr via bitcoin-dev]

Post by Christian Decker via bitcoin-dev
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

[Christian Decker via bitcoin-dev]

Post by Luke Dashjr via bitcoin-dev

Post by Christian Decker via bitcoin-dev
The proposal is implemented (see below), by computing the normalized
transaction ID when adding them to the UTXO and storing them along with

the

Post by Christian Decker via bitcoin-dev
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

Post by Christian Decker via bitcoin-dev
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?

Post by Luke Dashjr via bitcoin-dev
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.

Post by Luke Dashjr via bitcoin-dev
Luke

[Luke Dashjr via bitcoin-dev]

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev
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

[Christian Decker via bitcoin-dev]

Post by Luke Dashjr via bitcoin-dev

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev
This doesn't completely close malleability (which should be documented

in

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev
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

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev
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

Post by Christian Decker via bitcoin-dev
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

Post by Christian Decker via bitcoin-dev
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.

[Luke Dashjr via bitcoin-dev]

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev
This doesn't completely close malleability (which should be documented

in

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev
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

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev
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

Post by Christian Decker via bitcoin-dev
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

Post by Christian Decker via bitcoin-dev
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

[Christian Decker via bitcoin-dev]

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?

Post by Luke Dashjr via bitcoin-dev

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev
This doesn't completely close malleability (which should be documented

in

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev
the BIP), so I'm not sure it's worth the cost, especially if

closing

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev
malleability later on would need more. How about specifying flags

upfront

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev
in the UTXO-creating transaction specifying which parts the

signature

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev
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

Post by Christian Decker via bitcoin-dev
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

Post by Christian Decker via bitcoin-dev
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

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev
as
many real use cases as third-party malleability.
Luke

How is signer malleability still a problem if we remove the signatures

from

Post by Christian Decker via bitcoin-dev
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

[Luke Dashjr via bitcoin-dev]

Post by Christian Decker via bitcoin-dev
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

[Danny Thorpe via bitcoin-dev]

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 <

Post by Luke Dashjr via bitcoin-dev

Post by Christian Decker via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Gregory Maxwell via bitcoin-dev]

On Wed, Oct 21, 2015 at 6:22 PM, Danny Thorpe via bitcoin-dev

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.

[Luke Dashjr via bitcoin-dev]

Post by Danny Thorpe via bitcoin-dev
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

[Christian Decker via bitcoin-dev]

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.

Post by Luke Dashjr via bitcoin-dev

Post by Danny Thorpe via bitcoin-dev
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

[Luke Dashjr via bitcoin-dev]

Post by Christian Decker via bitcoin-dev
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

[Christian Decker via bitcoin-dev]

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

Post by Christian Decker via bitcoin-dev

Post by Christian Decker via bitcoin-dev
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

Post by Christian Decker via bitcoin-dev
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

Post by Christian Decker via bitcoin-dev
new input and output and we would have a different transaction.
Normalized transaction IDs do help in the case that the single signer

wants

Post by Christian Decker via bitcoin-dev
to immediately follow up its transaction with another transaction

spending

Post by Christian Decker via bitcoin-dev
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

[Luke Dashjr via bitcoin-dev]

Post by Christian Decker via bitcoin-dev
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.

Post by Christian Decker via bitcoin-dev
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

[Christian Decker via bitcoin-dev]

Post by Luke Dashjr via bitcoin-dev

Post by Christian Decker via bitcoin-dev
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

Post by Christian Decker via bitcoin-dev
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.

Post by Luke Dashjr via bitcoin-dev

Post by Christian Decker via bitcoin-dev
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.

Post by Luke Dashjr via bitcoin-dev
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.

Post by Luke Dashjr via bitcoin-dev
Luke

[Luke Dashjr via bitcoin-dev]

Post by Christian Decker via bitcoin-dev
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).

Post by Christian Decker via bitcoin-dev
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.

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev

Post by Christian Decker via bitcoin-dev
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.

Post by Christian Decker via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev
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...

Post by Christian Decker via bitcoin-dev
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

[Jorge Timón via bitcoin-dev]

On Tue, Nov 3, 2015 at 11:01 PM, Luke Dashjr via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev

Post by Christian Decker via bitcoin-dev
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.

[Luke Dashjr via bitcoin-dev]

Post by Jorge Timón via bitcoin-dev
On Tue, Nov 3, 2015 at 11:01 PM, Luke Dashjr via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev

Post by Christian Decker via bitcoin-dev
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

[Jorge Timón via bitcoin-dev]

Post by Luke Dashjr via bitcoin-dev
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.

[s7r via bitcoin-dev]

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.

Post by Jorge Timón via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev
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.

[Adam Back via bitcoin-dev]

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

Post by Luke Dashjr via bitcoin-dev

Post by Jorge Timón via bitcoin-dev
On Tue, Nov 3, 2015 at 11:01 PM, Luke Dashjr via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev

Post by Christian Decker via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Christian Decker via bitcoin-dev]

Post by Jorge Timón via bitcoin-dev
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 :-)

[Peter Todd via bitcoin-dev]

Post by Christian Decker via bitcoin-dev
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.

[Christian Decker via bitcoin-dev]

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 :-)

Post by Christian Decker via bitcoin-dev

Post by Christian Decker via bitcoin-dev
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

Post by Christian Decker via bitcoin-dev
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

Post by Christian Decker via bitcoin-dev
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.
--
00000000000000000247b0e7436a5169ac6f9087be0295d10b07bf0bcbd4c0cc

[Gregory Maxwell via bitcoin-dev]

On Thu, Oct 22, 2015 at 8:26 AM, Christian Decker via bitcoin-dev

Post by Christian Decker via bitcoin-dev
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.

[Christian Decker via bitcoin-dev]

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.

Post by Gregory Maxwell via bitcoin-dev
On Thu, Oct 22, 2015 at 8:26 AM, Christian Decker via bitcoin-dev

Post by Christian Decker via bitcoin-dev
Normalized transaction IDs do help in the case that the single signer

wants

Post by Christian Decker via bitcoin-dev
to immediately follow up its transaction with another transaction

spending

Post by Christian Decker via bitcoin-dev
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.

[Gregory Maxwell via bitcoin-dev]

On Wed, Oct 21, 2015 at 6:18 AM, Luke Dashjr via bitcoin-dev

Post by Luke Dashjr via bitcoin-dev

Post by Christian Decker via bitcoin-dev
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.

[Gregory Maxwell via bitcoin-dev]

Post by Gregory Maxwell via bitcoin-dev
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.

[Christian Decker via bitcoin-dev]

Post by Gregory Maxwell via bitcoin-dev

Post by Gregory Maxwell via bitcoin-dev
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.
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.

Post by Gregory Maxwell via bitcoin-dev
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.

[Christian Decker via bitcoin-dev]

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 <

Post by Christian Decker via bitcoin-dev

Post by Gregory Maxwell via bitcoin-dev

Post by Gregory Maxwell via bitcoin-dev
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.
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.

Post by Gregory Maxwell via bitcoin-dev
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.

[Gregory Maxwell via bitcoin-dev]

On Wed, Oct 21, 2015 at 8:49 AM, Christian Decker

Post by Christian Decker via bitcoin-dev
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).