path: root/ae/d331f6f8a76dfde9a80a14ca1e2e42e77c0f0c

Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194]
	helo=mx.sourceforge.net)
	by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
	(envelope-from <decker.christian@gmail.com>) id 1YsYWZ-0008LZ-12
	for bitcoin-development@lists.sourceforge.net;
	Wed, 13 May 2015 15:24:43 +0000
Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.215.48 as permitted sender)
	client-ip=209.85.215.48;
	envelope-from=decker.christian@gmail.com;
	helo=mail-la0-f48.google.com; 
Received: from mail-la0-f48.google.com ([209.85.215.48])
	by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
	(Exim 4.76) id 1YsYWX-0003CL-5M
	for bitcoin-development@lists.sourceforge.net;
	Wed, 13 May 2015 15:24:42 +0000
Received: by layy10 with SMTP id y10so32080373lay.0
	for <bitcoin-development@lists.sourceforge.net>;
	Wed, 13 May 2015 08:24:34 -0700 (PDT)
X-Received: by 10.152.44.225 with SMTP id h1mr16366496lam.5.1431530674751;
	Wed, 13 May 2015 08:24:34 -0700 (PDT)
MIME-Version: 1.0
References: <CALxbBHUnt7ToVK9reH6W6uT4HV=7NbxGHyNWWa-OEHg+Z1+qOg@mail.gmail.com>
	<CAE-z3OWUGPqruBkuXggzdNkOn+L-SSg84Qd1_JZYBunmY+j=HQ@mail.gmail.com>
	<CABsx9T1tPP_qrdyKPneZciwtWh2gho_d=qTCjnipo3463dJbpA@mail.gmail.com>
In-Reply-To: <CABsx9T1tPP_qrdyKPneZciwtWh2gho_d=qTCjnipo3463dJbpA@mail.gmail.com>
From: Christian Decker <decker.christian@gmail.com>
Date: Wed, 13 May 2015 15:24:34 +0000
Message-ID: <CALxbBHXjhgWrOdEa=_QLcvryZhP=tmdaCGnRwE9qNXJnVBmtjA@mail.gmail.com>
To: Gavin Andresen <gavinandresen@gmail.com>, Tier Nolan <tier.nolan@gmail.com>
Content-Type: multipart/alternative; boundary=089e0160b7be5a90f60515f835a5
X-Spam-Score: -0.6 (/)
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
	(decker.christian[at]gmail.com)
	-0.0 SPF_PASS               SPF: sender matches SPF record
	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
X-Headers-End: 1YsYWX-0003CL-5M
Cc: Bitcoin Development <bitcoin-development@lists.sourceforge.net>
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 15:24:43 -0000

--089e0160b7be5a90f60515f835a5
Content-Type: text/plain; charset=UTF-8

Glad you like it, I was afraid that I missed something obvious :-)

The points the two of you raised are valid and I will address them as soon
as possible. I certainly will implement this proposal so that it becomes
more concrete, but my C++ is a bit rusty and it'll take some time, so I
wanted to gauge interest first.

> This has the effect of doubling the size of the UTXO database.  At
minimum, there needs to be a legacy txid to normalized txid map in the
database.
>
> An addition to the BIP would eliminate the need for the 2nd index.  You
could require a SPV proof of the spending transaction to be included with
legacy transactions.  This would allow clients to verify that the
normalized txid matched the legacy id.
>
>The OutPoint would be {LegacyId | SPV Proof to spending tx  | spending tx
| index}.  This allows a legacy transaction to be upgraded.  OutPoints
which use a normalized txid don't need the SPV proof.

It does and I should have mentioned it in the draft, according to my
calculations a mapping legacy ID -> normalized ID is about 256 MB in size,
or at least it was at height 330'000, things might have changed a bit and
I'll recompute that. I omitted the deprecation of legacy IDs on purpose
since we don't know whether we will migrate completely or leave keep both
options viable.

> I think this needs more details before it gets a BIP number; for example,
which opcodes does this affect, and how, exactly, does it affect them? Is
the merkle root in the block header computed using normalized transaction
ids or normalized ids?

I think both IDs can be used in the merkle tree, since we lookup an ID in
both indices we can use both to address them and we will find them either
way.

As for the opcodes I'll have to check, but I currently don't see how they
could be affected. The OP_*SIG* codes calculate their own (more
complicated) stripped transaction before hashing and checking the
signature. The input of the stripped transaction simply contains whatever
hash was used to reference the output, so we do not replace IDs during the
operation. The stripped format used by OP_*SIG* operations does not have to
adhere to the hashes used to reference a transaction in the input.

> I think there might actually be two or three or four BIPs here:
>
>  + Overall "what is trying to be accomplished"
>  + Changes to the OP_*SIG* opcodes
>  + Changes to the bloom-filtering SPV support
>  + ...eventually, hard fork rollout plan
>
> I also think that it is a good idea to have actually implemented a
proposal before getting a BIP number. At least, I find that actually
writing the code often turns up issues I hadn't considered when thinking
about the problem at a high level. And I STRONGLY believe BIPs should be
descriptive ("here is how this thing works") not proscriptive ("here's how
I think we should all do it").

We can certainly split the proposal should it get too large, for now it
seems manageable, since opcodes are not affected. Bloom-filtering is
resolved by adding the normalized transaction IDs and checking for both IDs
in the filter. Since you mention bundling the change with other changes
that require a hard-fork it might be a good idea to build a separate
proposal for a generic hard-fork rollout mechanism.

If there are no obvious roadblocks and the change seems generally a good
thing I will implement it in Bitcoin Core :-)

Regards,
Chris

On Wed, May 13, 2015 at 3:44 PM Gavin Andresen <gavinandresen@gmail.com>
wrote:

> I think this needs more details before it gets a BIP number; for example,
> which opcodes does this affect, and how, exactly, does it affect them? Is
> the merkle root in the block header computed using normalized transaction
> ids or normalized ids?
>
> I think there might actually be two or three or four BIPs here:
>
>  + Overall "what is trying to be accomplished"
>  + Changes to the OP_*SIG* opcodes
>  + Changes to the bloom-filtering SPV support
>  + ...eventually, hard fork rollout plan
>
> I also think that it is a good idea to have actually implemented a
> proposal before getting a BIP number. At least, I find that actually
> writing the code often turns up issues I hadn't considered when thinking
> about the problem at a high level. And I STRONGLY believe BIPs should be
> descriptive ("here is how this thing works") not proscriptive ("here's how
> I think we should all do it").
>
> Finally: I like the idea of moving to a normalized txid. But it might make
> sense to bundle that change with a bigger change to OP_CHECKSIG; see Greg
> Maxwell's excellent talk about his current thoughts on that topic:
>   https://www.youtube.com/watch?v=Gs9lJTRZCDc
>
>
> On Wed, May 13, 2015 at 9:12 AM, Tier Nolan <tier.nolan@gmail.com> wrote:
>
>> I think this is a good way to handle things, but as you say, it is a hard
>> fork.
>>
>> CHECKLOCKTIMEVERIFY covers many of the use cases, but it would be nice to
>> fix malleability once and for all.
>>
>> This has the effect of doubling the size of the UTXO database.  At
>> minimum, there needs to be a legacy txid to normalized txid map in the
>> database.
>>
>> An addition to the BIP would eliminate the need for the 2nd index.  You
>> could require a SPV proof of the spending transaction to be included with
>> legacy transactions.  This would allow clients to verify that the
>> normalized txid matched the legacy id.
>>
>> The OutPoint would be {LegacyId | SPV Proof to spending tx  | spending tx
>> | index}.  This allows a legacy transaction to be upgraded.  OutPoints
>> which use a normalized txid don't need the SPV proof.
>>
>> The hard fork would be followed by a transitional period, in which both
>> txids could be used.  Afterwards, legacy transactions have to have the SPV
>> proof added.  This means that old transactions with locktimes years in the
>> future can be upgraded for spending, without nodes needing to maintain two
>> indexes.
>>
>>
>> ------------------------------------------------------------------------------
>> One dashboard for servers and applications across Physical-Virtual-Cloud
>> Widest out-of-the-box monitoring support with 50+ applications
>> Performance metrics, stats and reports that give you Actionable Insights
>> Deep dive visibility with transaction tracing using APM Insight.
>> http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
>> _______________________________________________
>> Bitcoin-development mailing list
>> Bitcoin-development@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>>
>>
>
>
> --
> --
> Gavin Andresen
>
> ------------------------------------------------------------------------------
> One dashboard for servers and applications across Physical-Virtual-Cloud
> Widest out-of-the-box monitoring support with 50+ applications
> Performance metrics, stats and reports that give you Actionable Insights
> Deep dive visibility with transaction tracing using APM Insight.
> http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

--089e0160b7be5a90f60515f835a5
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Glad you like it, I was afraid that I missed something obv=
ious :-)<br><br>The points the two of you raised are valid and I will addre=
ss them as soon as possible. I certainly will implement this proposal so th=
at it becomes more concrete, but my C++ is a bit rusty and it&#39;ll take s=
ome time, so I wanted to gauge interest first.<div dir=3D"ltr"><div><br></d=
iv><div>&gt;=C2=A0<span style=3D"font-size:13.1999998092651px;line-height:1=
9.7999992370605px">This has the effect of doubling the size of the UTXO dat=
abase.=C2=A0 At minimum, there needs to be a legacy txid to normalized txid=
 map in the database.</span></div><div style=3D"font-size:13.1999998092651p=
x;line-height:19.7999992370605px">&gt;</div><div style=3D"font-size:13.1999=
998092651px;line-height:19.7999992370605px">&gt; An addition to the BIP wou=
ld eliminate the need for the 2nd index.=C2=A0 You could require a SPV proo=
f of the spending transaction to be included with legacy transactions.=C2=
=A0 This would allow clients to verify that the normalized txid matched the=
 legacy id.<br>&gt;</div><div style=3D"font-size:13.1999998092651px;line-he=
ight:19.7999992370605px">&gt;The OutPoint would be {LegacyId | SPV Proof to=
 spending tx=C2=A0 | spending tx | index}.=C2=A0 This allows a legacy trans=
action to be upgraded.=C2=A0 OutPoints which use a normalized txid don&#39;=
t need the SPV proof.</div><div style=3D"font-size:13.1999998092651px;line-=
height:19.7999992370605px"><br></div></div><div dir=3D"ltr"><div style=3D"f=
ont-size:13.1999998092651px;line-height:19.7999992370605px">It does and I s=
hould have mentioned it in the draft, according to my calculations a mappin=
g legacy ID -&gt; normalized ID is about 256 MB in size, or at least it was=
 at height 330&#39;000, things might have changed a bit and I&#39;ll recomp=
ute that. I omitted the deprecation of legacy IDs on purpose since we don&#=
39;t know whether we will migrate completely or leave keep both options via=
ble.</div></div><div dir=3D"ltr"><div style=3D"font-size:13.1999998092651px=
;line-height:19.7999992370605px"><br></div><div><div><div>&gt; I think this=
 needs more details before it gets a BIP number; for example, which opcodes=
 does this affect, and how, exactly, does it affect them? Is the merkle roo=
t in the block header computed using normalized transaction ids or normaliz=
ed ids?</div></div></div><div><br></div></div><div dir=3D"ltr"><div>I think=
 both IDs can be used in the merkle tree, since we lookup an ID in both ind=
ices we can use both to address them and we will find them either way.</div=
><div><br></div><div>As for the opcodes I&#39;ll have to check, but I curre=
ntly don&#39;t see how they could be affected. The OP_*SIG* codes calculate=
 their own=C2=A0<span style=3D"font-size:13.1999998092651px;line-height:19.=
7999992370605px">(more complicated)=C2=A0</span><span style=3D"line-height:=
1.5;font-size:13.1999998092651px">stripped transaction before hashing and c=
hecking the signature. The input of the stripped transaction simply contain=
s whatever hash was used to reference the output, so we do not replace IDs =
during the operation. The stripped format used by OP_*SIG* operations does =
not have to adhere to the hashes used to reference a transaction in the inp=
ut.</span></div><div><br></div><div><div style=3D"font-size:13.199999809265=
1px;line-height:19.7999992370605px">&gt; I think there might actually be tw=
o or three or four BIPs here:</div><div style=3D"font-size:13.1999998092651=
px;line-height:19.7999992370605px">&gt;</div><div style=3D"font-size:13.199=
9998092651px;line-height:19.7999992370605px">&gt; =C2=A0+ Overall &quot;wha=
t is trying to be accomplished&quot;</div><div style=3D"font-size:13.199999=
8092651px;line-height:19.7999992370605px"><span style=3D"font-size:13.19999=
98092651px;line-height:19.7999992370605px">&gt;</span><span style=3D"font-s=
ize:13.1999998092651px;line-height:19.7999992370605px">=C2=A0</span>=C2=A0+=
 Changes to the OP_*SIG* opcodes</div><div style=3D"font-size:13.1999998092=
651px;line-height:19.7999992370605px"><span style=3D"font-size:13.199999809=
2651px;line-height:19.7999992370605px">&gt;</span><span style=3D"font-size:=
13.1999998092651px;line-height:19.7999992370605px">=C2=A0</span>=C2=A0+ Cha=
nges to the bloom-filtering SPV support</div><div style=3D"font-size:13.199=
9998092651px;line-height:19.7999992370605px"><span style=3D"font-size:13.19=
99998092651px;line-height:19.7999992370605px">&gt;</span><span style=3D"fon=
t-size:13.1999998092651px;line-height:19.7999992370605px">=C2=A0</span>=C2=
=A0+ ...eventually, hard fork rollout plan</div><div style=3D"font-size:13.=
1999998092651px;line-height:19.7999992370605px"><span style=3D"font-size:13=
.1999998092651px;line-height:19.7999992370605px">&gt;=C2=A0</span><br><div>=
<span style=3D"font-size:13.1999998092651px;line-height:19.7999992370605px"=
>&gt;</span><span style=3D"font-size:13.1999998092651px;line-height:19.7999=
992370605px">=C2=A0</span>I also think that it is a good idea to have actua=
lly implemented a proposal before getting a BIP number. At least, I find th=
at actually writing the code often turns up issues I hadn&#39;t considered =
when thinking about the problem at a high level. And I STRONGLY believe BIP=
s should be descriptive (&quot;here is how this thing works&quot;) not pros=
criptive (&quot;here&#39;s how I think we should all do it&quot;).</div><di=
v><br></div></div></div><div style=3D"font-size:13.1999998092651px;line-hei=
ght:19.7999992370605px">We can certainly split the proposal should it get t=
oo large, for now it seems manageable, since opcodes are not affected. Bloo=
m-filtering is resolved by adding the normalized transaction IDs and checki=
ng for both IDs in the filter. Since you mention bundling the change with o=
ther changes that require a hard-fork it might be a good idea to build a se=
parate proposal for a generic hard-fork rollout mechanism.</div><div style=
=3D"font-size:13.1999998092651px;line-height:19.7999992370605px"><br></div>=
<div style=3D"font-size:13.1999998092651px;line-height:19.7999992370605px">=
If there are no obvious roadblocks and the change seems generally a good th=
ing I will implement it in Bitcoin Core :-)</div><div style=3D"font-size:13=
.1999998092651px;line-height:19.7999992370605px"><br></div><div style=3D"fo=
nt-size:13.1999998092651px;line-height:19.7999992370605px">Regards,</div><d=
iv style=3D"font-size:13.1999998092651px;line-height:19.7999992370605px">Ch=
ris</div></div><br><div class=3D"gmail_quote">On Wed, May 13, 2015 at 3:44 =
PM Gavin Andresen &lt;<a href=3D"mailto:gavinandresen@gmail.com" target=3D"=
_blank">gavinandresen@gmail.com</a>&gt; wrote:<br><blockquote class=3D"gmai=
l_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left=
:1ex"><div dir=3D"ltr">I think this needs more details before it gets a BIP=
 number; for example, which opcodes does this affect, and how, exactly, doe=
s it affect them? Is the merkle root in the block header computed using nor=
malized transaction ids or normalized ids?=C2=A0<div><br></div><div>I think=
 there might actually be two or three or four BIPs here:</div><div><br></di=
v><div>=C2=A0+ Overall &quot;what is trying to be accomplished&quot;</div><=
div>=C2=A0+ Changes to the OP_*SIG* opcodes</div><div>=C2=A0+ Changes to th=
e bloom-filtering SPV support</div><div>=C2=A0+ ...eventually, hard fork ro=
llout plan</div><div><br><div>I also think that it is a good idea to have a=
ctually implemented a proposal before getting a BIP number. At least, I fin=
d that actually writing the code often turns up issues I hadn&#39;t conside=
red when thinking about the problem at a high level. And I STRONGLY believe=
 BIPs should be descriptive (&quot;here is how this thing works&quot;) not =
proscriptive (&quot;here&#39;s how I think we should all do it&quot;).</div=
></div><div><br></div><div>Finally: I like the idea of moving to a normaliz=
ed txid. But it might make sense to bundle that change with a bigger change=
 to OP_CHECKSIG; see Greg Maxwell&#39;s excellent talk about his current th=
oughts on that topic:</div><div>=C2=A0=C2=A0<a href=3D"https://www.youtube.=
com/watch?v=3DGs9lJTRZCDc" target=3D"_blank">https://www.youtube.com/watch?=
v=3DGs9lJTRZCDc</a></div><div><br></div></div><div class=3D"gmail_extra"></=
div><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">On Wed, May 1=
3, 2015 at 9:12 AM, Tier Nolan <span dir=3D"ltr">&lt;<a href=3D"mailto:tier=
.nolan@gmail.com" target=3D"_blank">tier.nolan@gmail.com</a>&gt;</span> wro=
te:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-=
left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>I think this is=
 a good way to handle things, but as you say, it is a hard fork.<br><br></d=
iv>CHECKLOCKTIMEVERIFY covers many of the use cases, but it would be nice t=
o fix malleability once and for all.<br><div><div><br>This has the effect o=
f doubling the size of the UTXO database.=C2=A0 At minimum, there needs to =
be a legacy txid to normalized txid map in the database.<br><br></div><div>=
An addition to the BIP would eliminate the need for the 2nd index.=C2=A0 Yo=
u could require a SPV proof of the spending transaction to be included with=
 legacy transactions.=C2=A0 This would allow clients to verify that the nor=
malized txid matched the legacy id.<br><br></div><div>The OutPoint would be=
 {LegacyId | SPV Proof to spending tx=C2=A0 | spending tx | index}.=C2=A0 T=
his allows a legacy transaction to be upgraded.=C2=A0 OutPoints which use a=
 normalized txid don&#39;t need the SPV proof.<br><br></div><div>The hard f=
ork would be followed by a transitional period, in which both txids could b=
e used.=C2=A0 Afterwards, legacy transactions have to have the SPV proof ad=
ded.=C2=A0 This means that old transactions with locktimes years in the fut=
ure can be upgraded for spending, without nodes needing to maintain two ind=
exes.<br></div></div></div>
<br>-----------------------------------------------------------------------=
-------<br>
One dashboard for servers and applications across Physical-Virtual-Cloud<br=
>
Widest out-of-the-box monitoring support with 50+ applications<br>
Performance metrics, stats and reports that give you Actionable Insights<br=
>
Deep dive visibility with transaction tracing using APM Insight.<br>
<a href=3D"http://ad.doubleclick.net/ddm/clk/290420510;117567292;y" target=
=3D"_blank">http://ad.doubleclick.net/ddm/clk/290420510;117567292;y</a><br>=
_______________________________________________<br>
Bitcoin-development mailing list<br>
<a href=3D"mailto:Bitcoin-development@lists.sourceforge.net" target=3D"_bla=
nk">Bitcoin-development@lists.sourceforge.net</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/bitcoin-development=
" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/bitcoin-de=
velopment</a><br>
<br></blockquote></div><br><br clear=3D"all"><div><br></div></div><div clas=
s=3D"gmail_extra">-- <br><div>--<br>Gavin Andresen<br></div>
</div>
---------------------------------------------------------------------------=
---<br>
One dashboard for servers and applications across Physical-Virtual-Cloud<br=
>
Widest out-of-the-box monitoring support with 50+ applications<br>
Performance metrics, stats and reports that give you Actionable Insights<br=
>
Deep dive visibility with transaction tracing using APM Insight.<br>
<a href=3D"http://ad.doubleclick.net/ddm/clk/290420510;117567292;y" target=
=3D"_blank">http://ad.doubleclick.net/ddm/clk/290420510;117567292;y</a>____=
___________________________________________<br>
Bitcoin-development mailing list<br>
<a href=3D"mailto:Bitcoin-development@lists.sourceforge.net" target=3D"_bla=
nk">Bitcoin-development@lists.sourceforge.net</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/bitcoin-development=
" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/bitcoin-de=
velopment</a><br>
</blockquote></div></div>

--089e0160b7be5a90f60515f835a5--