Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193] helo=mx.sourceforge.net) by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1Ysb85-0008Nj-Kh for bitcoin-development@lists.sourceforge.net; Wed, 13 May 2015 18:11:37 +0000 Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.192.46 as permitted sender) client-ip=209.85.192.46; envelope-from=tier.nolan@gmail.com; helo=mail-qg0-f46.google.com; Received: from mail-qg0-f46.google.com ([209.85.192.46]) by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1Ysb84-0003DJ-Fc for bitcoin-development@lists.sourceforge.net; Wed, 13 May 2015 18:11:37 +0000 Received: by qgfi89 with SMTP id i89so25753682qgf.1 for ; Wed, 13 May 2015 11:11:31 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.140.107.165 with SMTP id h34mr196474qgf.63.1431540691058; Wed, 13 May 2015 11:11:31 -0700 (PDT) Received: by 10.140.85.241 with HTTP; Wed, 13 May 2015 11:11:30 -0700 (PDT) In-Reply-To: References: Date: Wed, 13 May 2015 19:11:30 +0100 Message-ID: From: Tier Nolan Cc: Bitcoin Dev Content-Type: multipart/alternative; boundary=001a1139594e5f62dd0515fa8aae X-Spam-Score: 2.3 (++) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (tier.nolan[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 1.2 MISSING_HEADERS Missing To: header 1.0 HTML_MESSAGE BODY: HTML included in message -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature 1.9 MALFORMED_FREEMAIL Bad headers on message from free email service -0.2 AWL AWL: Adjusted score from AWL reputation of From: address X-Headers-End: 1Ysb84-0003DJ-Fc Subject: Re: [Bitcoin-development] [BIP] Normalized Transaction IDs X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 13 May 2015 18:11:37 -0000 --001a1139594e5f62dd0515fa8aae Content-Type: text/plain; charset=UTF-8 On Wed, May 13, 2015 at 6:14 PM, Pieter Wuille wrote: > Normalized transaction ids are only effectively non-malleable when all > inputs they refer to are also non-malleable (or you can have malleability > in 2nd level dependencies), so I do not believe it makes sense to allow > mixed usage of the txids at all. > The txid or txid-norm is signed, so can't be changed after signing. The hard fork is to allow transactions to refer to their inputs by txid or txid-norm. You pick one before signing. > They do not provide the actual benefit of guaranteed non-malleability > before it becomes disallowed to use the old mechanism. > A signed transaction cannot have its txid changed. It is true that users of the system would have to use txid-norm. The basic refund transaction is as follows. A creates TX1: "Pay w BTC to if signed by A & B" A creates TX2: "Pay w BTC from TX1-norm to , locked 48 hours in the future, signed by A" A sends TX2 to B B signs TX2 and returns to A A broadcasts TX1. It is mutated before entering the chain to become TX1-mutated. A can still submit TX2 to the blockchain, since TX1 and TX1-mutated have the same txid-norm. > > That, together with the +- resource doubling needed for the UTXO set (as > earlier mentioned) and the fact that an alternative which is only a > softfork are available, makes this a bad idea IMHO. > > Unsure to what extent this has been presented on the mailinglist, but the > softfork idea is this: > * Transactions get 2 txids, one used to reference them (computed as > before), and one used in an (extended) sighash. > * The txins keep using the normal txid, so not structural changes to > Bitcoin. > * The ntxid is computed by replacing the scriptSigs in inputs by the empty > string, and by replacing the txids in txins by their corresponding ntxids. > * A new checksig operator is softforked in, which uses the ntxids in its > sighashes rather than the full txid. > * To support efficiently computing ntxids, every tx in the utxo set > (currently around 6M) stores the ntxid, but only supports lookup bu txid > still. > > This does result in a system where a changed dependency indeed invalidates > the spending transaction, but the fix is trivial and can be done without > access to the private key. > The problem with this is that 2 level malleability is not protected against. C spends B which spends A. A is mutated before it hits the chain. The only change in A is in the scriptSig. B can be converted to B-new without breaking the signature. This is because the only change to A was in the sciptSig, which is dropped when computing the txid-norm. B-new spends A-mutated. B-new is different from B in a different place. The txid it uses to refer to the previous output is changed. The signed transaction C cannot be converted to a valid C-new. The txid of the input points to B. It is updated to point at B-new. B-new and B don't have the same txid-norm, since the change is outside the scriptSig. This means that the signature for C is invalid. The txid replacements should be done recursively. All input txids should be replaced by txid-norms when computing the txid-norm for the transaction. I think this repairs the problem with only allowing one level? Computing txid-norm: - replace all txids in inputs with txid-norms of those transactions - replace all input scriptSigs with empty scripts - transaction hash is txid-norm for that transaction The same situation as above is not fatal now. C spends B which spends A. A is mutated before it hits the chain. The only change in A is in the scriptSig. B can be converted to B-new without breaking the signature. This is because the only change to A was in the sciptSig, which is dropped when computing the txid-norm (as before). B-new spends A mutated. B-new is different from B in for the previous inputs. The input for B-new points to A-mutated. When computing the txid-norm, that would be replaced with the txid-norm for A. Similarly, the input for B points to A and that would have been replaced with the txid-norm for A. This means that B and B-new have the same txid-norm. The signed transaction C can be converted to a valid C-new. The txid of the input points to B. It is updated to point at B-new. B-new and B now have have the same txid-norm and so C is valid. I think this reasoning is valid, but probably needs writing out actual serializations. --001a1139594e5f62dd0515fa8aae Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
On W= ed, May 13, 2015 at 6:14 PM, Pieter Wuille <pieter.wuille@gmail.com<= /a>> wrote:
=

Normalized transaction ids are only effectively non-malleabl= e when all inputs they refer to are also non-malleable (or you can have mal= leability in 2nd level dependencies), so I do not believe it makes sense to= allow mixed usage of the txids at all.


The txid or txid-norm is signed, so can't be changed after signing.=C2= =A0

The hard fork is to allow transactions to refer to their inputs= by txid or txid-norm.=C2=A0 You pick one before signing.

They d= o not provide the actual benefit of guaranteed non-malleability before it b= ecomes disallowed to use the old mechanism.


A can still submit TX2 t= o the blockchain, since TX1 and TX1-mutated have the same txid-norm.
=C2=A0

T= hat, together with the +- resource doubling needed for the UTXO set (as ear= lier mentioned) and the fact that an alternative which is only a softfork a= re available, makes this a bad idea IMHO.

Unsure to what extent this has been presented on the mailing= list, but the softfork idea is this:
* Transactions get 2 txids, one used to reference them (computed as before)= , and one used in an (extended) sighash.
* The txins keep using the normal txid, so not structural changes to Bitcoi= n.
* The ntxid is computed by replacing the scriptSigs in inputs by the empty = string, and by replacing the txids in txins by their corresponding ntxids.<= br> * A new checksig operator is softforked in, which uses the ntxids in its si= ghashes rather than the full txid.
* To support efficiently computing ntxids, every tx in the utxo set (curren= tly around 6M) stores the ntxid, but only supports lookup bu txid still.

This does result in a system where a changed dependency inde= ed invalidates the spending transaction, but the fix is trivial and can be = done without access to the private key.

The problem wi= th this is that 2 level malleability is not protected against.

C spends B which spends A.

A is mutated = before it hits the chain.=C2=A0 The only change in A is in the scriptSig.
B can be converted to B-new without breaking the signature.=C2=A0 Thi= s is because the only change to A was in the sciptSig, which is dropped whe= n computing the txid-norm.

B-new spends A-mutated.=C2=A0 = B-new is different from B in a different place.=C2=A0 The txid it uses to r= efer to the previous output is changed.

The signed transa= ction C cannot be converted to a valid C-new.=C2=A0 The txid of the input p= oints to B.=C2=A0 It is updated to point at B-new.=C2=A0 B-new and B don= 9;t have the same txid-norm, since the change is outside the scriptSig.=C2= =A0 This means that the signature for C is invalid.

The txid replacements should be done recursively.=C2=A0 Al= l input txids should be replaced by txid-norms when computing the txid-norm= for the transaction.=C2=A0 I think this repairs the problem with only allo= wing one level?

Computing txid-norm:

- = replace all txids in inputs with txid-norms of those transactions
=
- replace all input scriptSigs with empty scripts
- tran= saction hash is txid-norm for that transaction

The same s= ituation as above is not fatal now.

C spends B which spends A.<= br>

A is mutated before it hits the chain.=C2=A0 The only cha= nge in A is in the scriptSig.

B can be converted to B-new without breaking the signature.=C2=A0 This is=20 because the only change to A was in the sciptSig, which is dropped when=20 computing the txid-norm (as before).

B-new spends A mutat= ed.=C2=A0=20 B-new is different from B in for the previous inputs.=C2=A0

The inp= ut for B-new points to A-mutated.=C2=A0 When computing the txid-norm, that = would be replaced with the txid-norm for A.

Similarly, th= e input for B points to A and that would have been replaced with the txid-n= orm for A.

This means that B and B-new have the same txid= -norm.

The signed=20 transaction C can be converted to a valid C-new.=C2=A0 The txid of the input points to B.=C2=A0 It is updated to point at B-new.=C2=A0 B-new and = B now have have the same txid-norm and so C is valid.

I think this = reasoning is valid, but probably needs writing out actual serializations.
--001a1139594e5f62dd0515fa8aae--