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
|
Return-Path: <bram@bittorrent.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 11C46A5E
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 3 Apr 2017 03:13:54 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-io0-f176.google.com (mail-io0-f176.google.com
[209.85.223.176])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 7EB13FC
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 3 Apr 2017 03:13:53 +0000 (UTC)
Received: by mail-io0-f176.google.com with SMTP id z13so67633903iof.2
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 02 Apr 2017 20:13:53 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=bittorrent-com.20150623.gappssmtp.com; s=20150623;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to;
bh=BbB0u5+o5Jd0h/fnHzpLUzlDLXGVpNpxvWbrfRxAB9w=;
b=ZfcNHRLmuOYOx4iA8vXz+2IEDzrkLsZdz9xYeUDimI3WGftW7rgDuFNZn6v340VIZX
a7C5RWHdo/tQSmBOHI00C71466HCgFLuq197pf33iA56IR3cM9soRksjQPI6Dt5EB3S1
k8RL3Bbb3Ai+Jr3qQE8+8Pau9c+JeNaZNuuIPmR4eYqw/QsGZwhc45MloyWRX5wKAXoR
tWxsu+IoRKgpL8p7J3ha2gYELeOzmw/jJo7Uq3LPzpLQzJySwAZjZyEZ/OuEiutz1qMi
gK5SRHj6ZprZ4h1W5LNmTJYdq8+cIuYUC9GLvgUGOjBowEamvSTgZNTOMNoC53+7IA34
bltw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to;
bh=BbB0u5+o5Jd0h/fnHzpLUzlDLXGVpNpxvWbrfRxAB9w=;
b=gv0mL2RliT6Re8EonBLPl6SYF6bmPeta8pCJ1dH2fygHC/vB6lf+zac5FIgCKn5yb5
N9rV+yYk9qJdajs/85TXzE2b6998B5cXt9eUQCmLuvpLHFcsH6LeP+exiwGFvXsnlCaZ
ax19NLwml8dDMtMZOkDQg3/hQTEjCFqHo/2OfYZXn+3+2TgHq026z5hXTYW9a934ASTz
vxwfcyHiQrb8qt9cqWbM2WHPEJ2Oq58Oy7i6N6RrowrFs55hZaCayeS2nAg8dnTkKui0
MAMVLC5uRiKHLve/OJFUAQSTo7aI0kC9CFsUaSJFKGzs6oBSIwHUit7tGfM5+R2m2Hif
K32A==
X-Gm-Message-State: AFeK/H2FWRrU9NHQL5eiPmDQUIZSCGu2vXz8ija01OU4qM530ATP2oL4WH4XWZ5pJwmVZxf/sEJFaop17MM66hjx
X-Received: by 10.107.11.215 with SMTP id 84mr13876817iol.41.1491189232842;
Sun, 02 Apr 2017 20:13:52 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.36.184.70 with HTTP; Sun, 2 Apr 2017 20:13:52 -0700 (PDT)
In-Reply-To: <slZ23d145uIKHr0zGoApsczTN3MNPSMtYbNmZV3Nk7F9YrgY8XaXTZ4BPvgIGGIdHBEf5V7c_ugY4RQVWeYYQW57ZQtfkUlHwOQZC7ANGjk=@protonmail.com>
References: <CEaHrHj5i8IQC75k1BY8e6a-4l-Wdq6vofQRYGQTtwx43uhcgzpg29Pbeh72d5LP5rQwxuCzevrGGnD2Bg8NKsDkUGCyzTwPczlbH2pOjgg=@protonmail.com>
<d89b85f6e5dbeaefc6402596dfc3c843@cock.lu>
<Agqv6Is87aXmNkFS0XphXWCE2TTZuuRJP8shQaomIUqx6W789WvMwflWqnSCQCwLPglEJ2rq3SkF-8tzYaZixbW9Ph-6u4a6sRCu4w-fPmA=@protonmail.com>
<CA+KqGkoNyHbw_6thOPSLKK9xMVgJtkDWwCZgwhoEQm1pD8_kDw@mail.gmail.com>
<8f4fSx74VGLlhmwWm7Gwzl5qNMd6okkHcBlCT55CRkYxa_lrEHL-C0hARMXcTaf4CNVIh8no1CHJF-_bmZJRJDsx1H10PCrI45X0D7QdukE=@protonmail.com>
<CA+KqGkpLJasuYqn9tzA_CUihwmoRqpQZ_exOUT_uqGYEesvceQ@mail.gmail.com>
<h-i4wv8tgd-htJYGNv1FsgBOs0CJbU2CVhit0gj1JqGp6qnCB6_Lvqt-pFNQxD_cuM-Z8Bu6e-YImZkPv8LYOAaVJHmNsSJIeLV-qiGpUHc=@protonmail.com>
<slZ23d145uIKHr0zGoApsczTN3MNPSMtYbNmZV3Nk7F9YrgY8XaXTZ4BPvgIGGIdHBEf5V7c_ugY4RQVWeYYQW57ZQtfkUlHwOQZC7ANGjk=@protonmail.com>
From: Bram Cohen <bram@bittorrent.com>
Date: Sun, 2 Apr 2017 20:13:52 -0700
Message-ID: <CA+KqGkq4BNUpwsxYnc4d-RSpq7-og4Xf2zwtUC-AVBjF4_u7fg@mail.gmail.com>
To: praxeology_guy <praxeology_guy@protonmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=001a113f8a74845f85054c3a8c3d
X-Spam-Status: No, score=-1.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_NONE,
RCVD_IN_SORBS_SPAM 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] Guessing the spentness status of the pruned
relatives
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol 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: Mon, 03 Apr 2017 03:13:54 -0000
--001a113f8a74845f85054c3a8c3d
Content-Type: text/plain; charset=UTF-8
On Sun, Apr 2, 2017 at 1:43 PM, praxeology_guy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> TL;DR: using spentness bits scales linearly... vs swapping digest leafs
> with empties can scale with logorithmically increasing storage
> requirements. So if you are using a 32 byte hash and spentness bits, you
> are pretty much limited to only being able to prune 8 to 12 layers. This
> corresponds to an MMR proof length of 512 to 768 bytes.
>
Yes the point of the txo bitfield is that the constant factors are so good
that it's entirely under control. Making the memory commitments smaller
requires that the proofs be kept up to date and increases CPU requirements
and proof size. It would be entirely reasonable to make an MMRs of the
bitfield or the insertion index data structure but they aren't needed
immediately if ever. For the insertion ordering structure it's reasonable
to require full nodes to cache the top bunch of layers to make the proofs
smaller, but a very expedient approximation of that is to make them simply
remember a root per block for all the insertions contained therein, and
have full nodes remember all of those.
--001a113f8a74845f85054c3a8c3d
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 S=
un, Apr 2, 2017 at 1:43 PM, praxeology_guy via bitcoin-dev <span dir=3D"ltr=
"><<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_b=
lank">bitcoin-dev@lists.linuxfoundation.org</a>></span> wrote:<br><block=
quote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc=
solid;padding-left:1ex"><div>TL;DR: using spentness bits scales linearly..=
. vs swapping digest leafs with empties can scale with logorithmically incr=
easing storage requirements.=C2=A0 So if you are using a 32 byte hash and s=
pentness bits, you are pretty much limited to only being able to prune 8 to=
12 layers.=C2=A0 This corresponds to an MMR proof length of 512 to 768 byt=
es.<br></div></blockquote><div><br></div><div>Yes the point of the txo bitf=
ield is that the constant factors are so good that it's entirely under =
control. Making the memory commitments smaller requires that the proofs be =
kept up to date and increases CPU requirements and proof size. It would be =
entirely reasonable to make an MMRs of the bitfield or the insertion index =
data structure but they aren't needed immediately if ever. For the inse=
rtion ordering structure it's reasonable to require full nodes to cache=
the top bunch of layers to make the proofs smaller, but a very expedient a=
pproximation of that is to make them simply remember a root per block for a=
ll the insertions contained therein, and have full nodes remember all of th=
ose.</div></div></div></div>
--001a113f8a74845f85054c3a8c3d--
|
