public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Tier Nolan <tier.nolan@gmail.com>
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Capacity increases for the Bitcoin system.
Date: Tue, 8 Dec 2015 19:08:57 +0000	[thread overview]
Message-ID: <CAE-z3OVrpoSHVeJFN-6NzkkZP1y9RmUjKdpxjWN-dJgLK20TBg@mail.gmail.com> (raw)
In-Reply-To: <CAOG=w-vW36Q5_NMqzZsBgc-p7QEDEYp9OtLkg5tzbAN0YRXFUA@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 1313 bytes --]

On Tue, Dec 8, 2015 at 5:41 PM, Mark Friedenbach via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> 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.
>

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.

The number of non-zero bits in the tx count determings how many digests are
required.

https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header.mediawiki

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.

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.

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.

Managing the UTXO set to ensure that there is at least one output that pays
to OP_TRUE is also a hassle.

[-- Attachment #2: Type: text/html, Size: 1985 bytes --]

  parent reply	other threads:[~2015-12-08 19:08 UTC|newest]

Thread overview: 56+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2015-12-07 22:02 [bitcoin-dev] Capacity increases for the Bitcoin system Gregory Maxwell
2015-12-07 22:54 ` Bryan Bishop
2015-12-08  2:42 ` Anthony Towns
2015-12-08  4:58   ` Anthony Towns
2015-12-08  5:21     ` Gregory Maxwell
2015-12-08  6:54       ` Anthony Towns
2016-01-18 12:02     ` Anthony Towns
2016-01-22  9:46       ` Anthony Towns
2015-12-08 11:07 ` Wladimir J. van der Laan
2015-12-08 11:14   ` Jorge Timón
2015-12-08 15:12     ` Gavin Andresen
2015-12-08 15:55       ` Justus Ranvier
2015-12-08 17:41         ` Mark Friedenbach
2015-12-08 18:43           ` Justus Ranvier
2015-12-08 19:08           ` Tier Nolan [this message]
2015-12-08 19:31         ` Gregory Maxwell
2015-12-08 23:40         ` Jonathan Toomim
2015-12-08 23:48           ` Luke Dashjr
2015-12-09  0:54             ` Jonathan Toomim
2015-12-08 23:50           ` Jorge Timón
2015-12-09  0:56             ` Jonathan Toomim
2015-12-08 23:59       ` Gregory Maxwell
2015-12-09  0:58         ` Jorge Timón
2015-12-09  1:02           ` Jorge Timón
2015-12-09  1:09         ` Gavin Andresen
2015-12-09  1:31           ` Gregory Maxwell
2015-12-09  4:44             ` Ryan Butler
2015-12-09  6:29               ` Gregory Maxwell
2015-12-09  6:36                 ` Ryan Butler
2015-12-09  6:59                 ` Mark Friedenbach
2015-12-09  7:17                   ` Gregory Maxwell
2015-12-09  7:54                 ` Jorge Timón
2015-12-09  8:03                   ` Gregory Maxwell
2015-12-09  8:46                     ` Mark Friedenbach
2015-12-09 11:08                     ` Jorge Timón
2015-12-09 16:40                     ` Gavin Andresen
2015-12-11 16:18                       ` Jorge Timón
2015-12-11 16:43                         ` Gavin Andresen
2015-12-12  5:13                           ` digitsu
2015-12-12 15:18                             ` Mark Friedenbach
2015-12-14 11:21                               ` Jonathan Toomim
2015-12-14 12:44                                 ` Adam Back
2015-12-09  4:51             ` Anthony Towns
2015-12-09 14:51       ` Chris
     [not found]   ` <CAPWm=eUomq6SBC0ky0WSs5=_G942vigm4RmgYuq0O-yJ-vqC2A@mail.gmail.com>
     [not found]     ` <CAPg+sBig9O5+he0PWhTkX5iin14QLz5+eCCu6KfwU=DxntKYtg@mail.gmail.com>
2015-12-21  4:33       ` Pieter Wuille
2015-12-21  4:42         ` Justus Ranvier
2015-12-21  4:44         ` Alex Morcos
2015-12-21  4:50         ` Mark Friedenbach
2015-12-21  5:29           ` Douglas Roark
2015-12-21  5:21         ` Btc Drak
2015-12-21  8:07           ` Anthony Towns
2015-12-21  9:56             ` Jorge Timón
2015-12-08 23:48 ` Jonathan Toomim
2015-12-09  0:23   ` Gregory Maxwell
     [not found]   ` <CAAS2fgRP8bLWZoKR9-iJS-2RKTGQQ9NG-LpAfa2BOdcR=GuB_A@mail.gmail.com>
2015-12-09  0:40     ` Jonathan Toomim
2015-12-09 12:28 Daniele Pinna

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CAE-z3OVrpoSHVeJFN-6NzkkZP1y9RmUjKdpxjWN-dJgLK20TBg@mail.gmail.com \
    --to=tier.nolan@gmail.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox