path: root/8b/206ad5c44bc5131a7a1dde29f40b5487872c5b

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 <tier.nolan@gmail.com>) 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 <bitcoin-development@lists.sourceforge.net>;
	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: <CAPg+sBggj382me1ATDx4SS9KHVfvX5KH7ZhLHN6B+2_a+Emw1Q@mail.gmail.com>
References: <CALxbBHUnt7ToVK9reH6W6uT4HV=7NbxGHyNWWa-OEHg+Z1+qOg@mail.gmail.com>
	<CAPg+sBggj382me1ATDx4SS9KHVfvX5KH7ZhLHN6B+2_a+Emw1Q@mail.gmail.com>
Date: Wed, 13 May 2015 19:11:30 +0100
Message-ID: <CAE-z3OV1WEDEV+X7gNVx+qBMt4jpSHFKXm3dxUrUyBEJrCNDSQ@mail.gmail.com>
From: Tier Nolan <tier.nolan@gmail.com>
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
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: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=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 <pieter.wuille@gmail.com>
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 <B's public key> if signed by A & B"

 A creates TX2: "Pay w BTC from TX1-norm to <A's public key>, 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

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On W=
ed, May 13, 2015 at 6:14 PM, Pieter Wuille <span dir=3D"ltr">&lt;<a href=3D=
"mailto:pieter.wuille@gmail.com" target=3D"_blank">pieter.wuille@gmail.com<=
/a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:=
0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">=
<p dir=3D"ltr">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.</p></blockquote><div><br></div><div=
>The txid or txid-norm is signed, so can&#39;t be changed after signing.=C2=
=A0 <br><br>The hard fork is to allow transactions to refer to their inputs=
 by txid or txid-norm.=C2=A0 You pick one before signing.<br></div><div></d=
iv><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bord=
er-left:1px solid rgb(204,204,204);padding-left:1ex"><p dir=3D"ltr"> They d=
o not provide the actual benefit of guaranteed non-malleability before it b=
ecomes disallowed to use the old mechanism.</p></blockquote><div>A signed t=
ransaction cannot have its txid changed.=C2=A0 It is true that users of the=
 system would have to use txid-norm.<br><br></div><div>The basic refund tra=
nsaction is as follows.<br></div><div><br></div><div>=C2=A0A creates TX1: &=
quot;Pay w BTC to &lt;B&#39;s public key&gt; if signed by A &amp; B&quot;<b=
r>=C2=A0<br>=C2=A0A creates TX2: &quot;Pay w BTC from TX1-norm to &lt;A&#39=
;s public key&gt;, locked 48 hours in the future, signed by A&quot;<br>=C2=
=A0<br>=C2=A0A sends TX2 to B<br>=C2=A0<br>=C2=A0B signs TX2 and returns to=
 A<br><br></div><div>A broadcasts TX1.=C2=A0 It is mutated before entering =
the chain to become TX1-mutated.<br><br></div><div>A can still submit TX2 t=
o the blockchain, since TX1 and TX1-mutated have the same txid-norm.<br></d=
iv>=C2=A0<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8e=
x;border-left:1px solid rgb(204,204,204);padding-left:1ex"><p dir=3D"ltr">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.</p>
<p dir=3D"ltr">Unsure to what extent this has been presented on the mailing=
list, but the softfork idea is this:<br>
* Transactions get 2 txids, one used to reference them (computed as before)=
, and one used in an (extended) sighash.<br>
* The txins keep using the normal txid, so not structural changes to Bitcoi=
n.<br>
* 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.<br>
* 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.</p=
>
<p dir=3D"ltr">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.</p></blockquote><div>The problem wi=
th this is that 2 level malleability is not protected against.<br><br></div=
><div>C spends B which spends A.<br></div><br><div></div><div>A is mutated =
before it hits the chain.=C2=A0 The only change in A is in the scriptSig.<b=
r><br>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.<br><br></div><div>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.<br><br></div><div>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&#3=
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.<br></div><div></div><di=
v><br></div><div>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?<br><br></div><div>Computing txid-norm:<br><br></div><div>- =
replace all txids in inputs with txid-norms of those transactions<br></div>=
<div>- replace all input scriptSigs with empty scripts<br></div><div>- tran=
saction hash is txid-norm for that transaction<br><br></div><div>The same s=
ituation as above is not fatal now.<br><br><div>C spends B which spends A.<=
br></div><br><div>A is mutated before it hits the chain.=C2=A0 The only cha=
nge in A is in the scriptSig.<br><br>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).<br><br></div><div>B-new spends A mutat=
ed.=C2=A0=20
B-new is different from B in for the previous inputs.=C2=A0 <br><br>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.<br><br></div><div>Similarly, th=
e input for B points to A and that would have been replaced with the txid-n=
orm for A.<br><br></div><div>This means that B and B-new have the same txid=
-norm.<br></div><div><br></div><div>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.<br><br></div><div>I think this =
reasoning is valid, but probably needs writing out actual serializations.<b=
r></div></div></div></div></div>

--001a1139594e5f62dd0515fa8aae--