<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Dec 8, 2015 at 5:41 PM, Mark Friedenbach via bitcoin-dev <span dir="ltr">&lt;<a href="mailto:bitcoin-dev@lists.linuxfoundation.org" target="_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">A far better place than the generation transaction (which I assume means coinbase transaction?) is the last transaction in the block. That allows you to save, on average, half of the hashes in the Merkle tree.<br></div></blockquote><div><br></div>This trick can be improved by only using certain tx counts.  If the number of transactions is limited to a power of 2 (other than the extra transactions), then you get a path of length zero.<br><br></div><div class="gmail_quote">The number of non-zero bits in the tx count determings how many digests are required.<br></div><div class="gmail_quote"><br><a href="https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header.mediawiki">https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header.mediawiki</a><br><br></div><div class="gmail_quote">This gets the benefit of a soft-fork, while also keeping the proof lengths small.  The linked bip has a 105 byte overhead for the path.<br><br></div><div class="gmail_quote">The cost is that only certain transaction counts are allowed.  In the worst case, 12.5% of transactions would have to be left in the memory pool.  This means around 7% of transactions would be delayed until the next block.<br><br></div><div class="gmail_quote">Blank transactions (or just transactions with low latency requirements) could be used to increase the count so that it is raised to one of the valid numbers.<br><br></div><div class="gmail_quote">Managing the UTXO set to ensure that there is at least one output that pays to OP_TRUE is also a hassle.<br></div></div></div>