1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
Return-Path: <tier.nolan@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 4AC10D09
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 8 Dec 2015 19:08:59 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-io0-f178.google.com (mail-io0-f178.google.com
[209.85.223.178])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 3E5D3E5
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 8 Dec 2015 19:08:58 +0000 (UTC)
Received: by ioc74 with SMTP id 74so34313530ioc.2
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 08 Dec 2015 11:08:57 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:cc
:content-type; bh=acEMsctgIx0T9qMvLgaBqN2vnbvue+8ssqf947s7O4Y=;
b=GhuvqGbf98UJHxvOzv7IXETrbsInbxm08JAT3lYRtHhm8Vvkhms26ucJoSqlD+QUCo
5RRb8FxChBYFsLGr4dXD+y5SzR2cSdPfZjvj5EPfD/o0jxFAIAQ63M68bJZrfNLPSw9M
lrdy17e5rBKkN+K77xOON/o+05C8IfdYpii0mF6L6XLtoSIyUfKoYY/9VCN8tLyT/Vub
NIl+l5qQPvo0dIpi0hTKbIzbhGtP8PbI1oxQMFkIlp1VQcPuij+PlUHRyLjLG2CokKFW
vy4fqANeEsJg+BWd7Gle1ROu5dHBAJJ3K2cOTfiUKYRLcRa5tSb/cx+Sxpc0VujEY0t+
xqkg==
MIME-Version: 1.0
X-Received: by 10.107.163.79 with SMTP id m76mr1693608ioe.109.1449601737632;
Tue, 08 Dec 2015 11:08:57 -0800 (PST)
Received: by 10.79.113.156 with HTTP; Tue, 8 Dec 2015 11:08:57 -0800 (PST)
In-Reply-To: <CAOG=w-vW36Q5_NMqzZsBgc-p7QEDEYp9OtLkg5tzbAN0YRXFUA@mail.gmail.com>
References: <CAAS2fgQyVs1fAEj+vqp8E2=FRnqsgs7VUKqALNBHNxRMDsHdVg@mail.gmail.com>
<20151208110752.GA31180@amethyst.visucore.com>
<CABm2gDpcek=u=Rpe68EMOq6M7Bji9J=s5VvoQWKRqaQDAP5kTw@mail.gmail.com>
<CABsx9T1wga3Tandoe2mVGSKdHJytHoc9Ko7HRm2SvJXABEFk9w@mail.gmail.com>
<5666FD8D.8050201@openbitcoinprivacyproject.org>
<CAOG=w-vW36Q5_NMqzZsBgc-p7QEDEYp9OtLkg5tzbAN0YRXFUA@mail.gmail.com>
Date: Tue, 8 Dec 2015 19:08:57 +0000
Message-ID: <CAE-z3OVrpoSHVeJFN-6NzkkZP1y9RmUjKdpxjWN-dJgLK20TBg@mail.gmail.com>
From: Tier Nolan <tier.nolan@gmail.com>
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=001a11402acaa3308d052667b402
X-Spam-Status: No, score=-0.2 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
MALFORMED_FREEMAIL,
MISSING_HEADERS,RCVD_IN_DNSWL_LOW autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] Capacity increases for the Bitcoin system.
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 08 Dec 2015 19:08:59 -0000
--001a11402acaa3308d052667b402
Content-Type: text/plain; charset=UTF-8
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.
--001a11402acaa3308d052667b402
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 T=
ue, Dec 8, 2015 at 5:41 PM, Mark Friedenbach via bitcoin-dev <span dir=3D"l=
tr"><<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"=
_blank">bitcoin-dev@lists.linuxfoundation.org</a>></span> wrote:<br><blo=
ckquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left=
:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr">A far better=
place than the generation transaction (which I assume means coinbase trans=
action?) 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.=C2=A0=
If the number of transactions is limited to a power of 2 (other than the e=
xtra transactions), then you get a path of length zero.<br><br></div><div c=
lass=3D"gmail_quote">The number of non-zero bits in the tx count determings=
how many digests are required.<br></div><div class=3D"gmail_quote"><br><a =
href=3D"https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header.me=
diawiki">https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header.m=
ediawiki</a><br><br></div><div class=3D"gmail_quote">This gets the benefit =
of a soft-fork, while also keeping the proof lengths small.=C2=A0 The linke=
d bip has a 105 byte overhead for the path.<br><br></div><div class=3D"gmai=
l_quote">The cost is that only certain transaction counts are allowed.=C2=
=A0 In the worst case, 12.5% of transactions would have to be left in the m=
emory pool.=C2=A0 This means around 7% of transactions would be delayed unt=
il the next block.<br><br></div><div class=3D"gmail_quote">Blank transactio=
ns (or just transactions with low latency requirements) could be used to in=
crease the count so that it is raised to one of the valid numbers.<br><br><=
/div><div class=3D"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></di=
v></div>
--001a11402acaa3308d052667b402--
|
