diff options
| author | Christian Decker <decker.christian@gmail.com> | 2015-05-13 15:24:34 +0000 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2015-05-13 15:24:43 +0000 |
| commit | 7e8aa7b03e6aab5edf49eac38bcbbd5c2f977196 (patch) | |
| tree | effa761671e20a82b1bf818f2acdc86270968bd7 | |
| parent | cae4751a85864e7fbe54c9ffffec8f0efb236063 (diff) | |
| download | pi-bitcoindev-7e8aa7b03e6aab5edf49eac38bcbbd5c2f977196.tar.gz pi-bitcoindev-7e8aa7b03e6aab5edf49eac38bcbbd5c2f977196.zip | |
Re: [Bitcoin-development] [BIP] Normalized Transaction IDs
| -rw-r--r-- | ae/d331f6f8a76dfde9a80a14ca1e2e42e77c0f0c | 398 |
1 files changed, 398 insertions, 0 deletions
diff --git a/ae/d331f6f8a76dfde9a80a14ca1e2e42e77c0f0c b/ae/d331f6f8a76dfde9a80a14ca1e2e42e77c0f0c new file mode 100644 index 000000000..8ade70dc9 --- /dev/null +++ b/ae/d331f6f8a76dfde9a80a14ca1e2e42e77c0f0c @@ -0,0 +1,398 @@ +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'll take s= +ome time, so I wanted to gauge interest first.<div dir=3D"ltr"><div><br></d= +iv><div>>=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">></div><div style=3D"font-size:13.1999= +998092651px;line-height:19.7999992370605px">> 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>></div><div style=3D"font-size:13.1999998092651px;line-he= +ight:19.7999992370605px">>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'= +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 -> 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 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>> 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'll have to check, but I curre= +ntly don'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">> 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">></div><div style=3D"font-size:13.199= +9998092651px;line-height:19.7999992370605px">> =C2=A0+ Overall "wha= +t is trying to be accomplished"</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">></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">></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">></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">>=C2=A0</span><br><div>= +<span style=3D"font-size:13.1999998092651px;line-height:19.7999992370605px"= +>></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't considered = +when thinking about the problem at a high level. And I STRONGLY believe BIP= +s should be descriptive ("here is how this thing works") not pros= +criptive ("here's how I think we should all do it").</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 <<a href=3D"mailto:gavinandresen@gmail.com" target=3D"= +_blank">gavinandresen@gmail.com</a>> 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 "what is trying to be accomplished"</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't conside= +red 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").</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'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"><<a href=3D"mailto:tier= +.nolan@gmail.com" target=3D"_blank">tier.nolan@gmail.com</a>></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'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-- + + |