Normalized transaction IDs
36 messages, 19 Oct to 6 Nov 2015. Started by Christian Decker.
Christian Decker (14), Luke Dashjr (9), Greg Maxwell (5), s7r (2), Jorge Timón (2), Tier Nolan, Danny Thorpe, Peter Todd, +1 more
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
On Mon, Oct 19, 2015 at 3:01 PM, Christian Decker via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (5 lines)
> 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.
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:
Quoted text (31 lines)
> 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 >
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:
Quoted text (29 lines)
> 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. > >
On Tue, Oct 20, 2015 at 12:23 AM s7r via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (6 lines)
> 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.
Quoted text (5 lines)
> 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.
Quoted text (6 lines)
> > 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
Quoted text (37 lines)
> > > 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 >
On Monday, October 19, 2015 2:01:04 PM Christian Decker via bitcoin-dev wrote:
Quoted text (7 lines)
> 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
On Wed, Oct 21, 2015 at 8:19 AM Luke Dashjr <luke@dashjr•org> wrote:
Quoted text (19 lines)
> 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?
Quoted text (7 lines)
> > 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.
Quoted text (3 lines)
> > Luke >
On Wed, Oct 21, 2015 at 6:18 AM, Luke Dashjr via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (18 lines)
> 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.
On Wednesday, October 21, 2015 7:39:45 AM Christian Decker wrote:
Quoted text (13 lines)
> 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
On Wed, Oct 21, 2015 at 7:48 AM, Gregory Maxwell <gmaxwell@gmail•com> wrote:
Quoted text (4 lines)
> 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.
On Wed, Oct 21, 2015 at 9:52 AM Luke Dashjr <luke@dashjr•org> wrote:
Quoted text (29 lines)
> 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.
On Wednesday, October 21, 2015 8:31:42 AM Christian Decker wrote:
Quoted text (44 lines)
> 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
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:
Quoted text (57 lines)
> 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 >
On Wednesday, October 21, 2015 8:44:53 AM Christian Decker wrote:
Quoted text (3 lines)
> 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
On Wed, Oct 21, 2015 at 10:26 AM Gregory Maxwell <gmaxwell@gmail•com> wrote:
Quoted text (18 lines)
> 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.
Quoted text (7 lines)
> 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. >
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:
Quoted text (38 lines)
> 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. >> >
On Wed, Oct 21, 2015 at 8:49 AM, Christian Decker <decker.christian@gmail•com> wrote:
Quoted text (7 lines)
> 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).
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:
Quoted text (16 lines)
> 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 >
On Wed, Oct 21, 2015 at 6:22 PM, Danny Thorpe via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (3 lines)
> 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]
Quoted text (3 lines)
> 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.
On Wednesday, October 21, 2015 6:22:25 PM Danny Thorpe wrote:
Quoted text (4 lines)
> 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
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:
Quoted text (13 lines)
> 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 >
On Thu, Oct 22, 2015 at 8:26 AM, Christian Decker via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (4 lines)
> 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.
On Thursday, October 22, 2015 8:26:58 AM Christian Decker wrote:
Quoted text (12 lines)
> 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
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:
Quoted text (18 lines)
> 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. >
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:
Quoted text (29 lines)
> 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 >
On Tuesday, November 03, 2015 8:37:44 PM Christian Decker wrote:
Quoted text (6 lines)
> 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.
Quoted text (5 lines)
> 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
On Tue, Nov 3, 2015 at 9:49 PM Luke Dashjr <luke@dashjr•org> wrote:
Quoted text (13 lines)
> 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.
Quoted text (12 lines)
> > > 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.
Quoted text (15 lines)
> > 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.
Quoted text (3 lines)
> > Luke >
On Tuesday, November 03, 2015 9:44:02 PM Christian Decker wrote:
Quoted text (11 lines)
> 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).
Quoted text (4 lines)
> 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.
Quoted text (22 lines)
> > > 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.
Quoted text (20 lines)
> > 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...
Quoted text (4 lines)
> 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
On Tue, Nov 03, 2015 at 09:44:02PM +0000, Christian Decker via bitcoin-dev wrote:
Quoted text (16 lines)
> 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.
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:
Quoted text (35 lines)
> 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 >
On Tue, Nov 3, 2015 at 11:01 PM, Luke Dashjr via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (16 lines)
> 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.
On Thursday, November 05, 2015 3:27:37 PM Jorge Timón wrote:
Quoted text (36 lines)
> 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
On Thu, Nov 5, 2015 at 8:36 PM, Luke Dashjr <luke@dashjr•org> wrote:
Quoted text (3 lines)
> 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.
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:
Quoted text (47 lines)
> 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
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:
Quoted text (15 lines)
> 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.
On Thu, Nov 5, 2015 at 4:27 PM Jorge Timón <jtimon@jtimon•cc> wrote:
Quoted text (19 lines)
> 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 :-)