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
|
Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
helo=mx.sourceforge.net)
by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <gmaxwell@gmail.com>) id 1Vu63j-0000k5-Gf
for bitcoin-development@lists.sourceforge.net;
Fri, 20 Dec 2013 19:48:31 +0000
Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.220.42 as permitted sender)
client-ip=209.85.220.42; envelope-from=gmaxwell@gmail.com;
helo=mail-pa0-f42.google.com;
Received: from mail-pa0-f42.google.com ([209.85.220.42])
by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1Vu63h-0003Dg-IO
for bitcoin-development@lists.sourceforge.net;
Fri, 20 Dec 2013 19:48:31 +0000
Received: by mail-pa0-f42.google.com with SMTP id lj1so3060302pab.15
for <bitcoin-development@lists.sourceforge.net>;
Fri, 20 Dec 2013 11:48:23 -0800 (PST)
MIME-Version: 1.0
X-Received: by 10.68.110.132 with SMTP id ia4mr10423878pbb.99.1387568903679;
Fri, 20 Dec 2013 11:48:23 -0800 (PST)
Received: by 10.70.81.170 with HTTP; Fri, 20 Dec 2013 11:48:23 -0800 (PST)
In-Reply-To: <52B3A1C8.5000005@monetize.io>
References: <52B3A1C8.5000005@monetize.io>
Date: Fri, 20 Dec 2013 11:48:23 -0800
Message-ID: <CAAS2fgSD7qbDkcPqW1XsRbSKpF5JhJXbJQrYQQ63LEQnV0qJyA@mail.gmail.com>
From: Gregory Maxwell <gmaxwell@gmail.com>
To: Mark Friedenbach <mark@monetize.io>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Score: -1.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
(gmaxwell[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
0.0 URIBL_BLOCKED ADMINISTRATOR NOTICE: The query to URIBL was blocked.
See
http://wiki.apache.org/spamassassin/DnsBlocklists#dnsbl-block
for more information. [URIs: monetize.io]
-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: 1Vu63h-0003Dg-IO
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
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: Fri, 20 Dec 2013 19:48:31 -0000
On Thu, Dec 19, 2013 at 5:47 PM, Mark Friedenbach <mark@monetize.io> wrote:
> Hello fellow bitcoin developers. Included below is the first draft of
> a BIP for a new Merkle-compressed data structure. The need for this
> data structure arose out of the misnamed "Ultimate blockchain
> compression" project, but it has since been recognized to have many
> other applications.
A couple very early comments=E2=80=94 I shared some of these with you on IR=
C
but I thought I'd post them to make them more likely to not get lost.
Whats a VARCHAR() A zero terminated string? A length prefixed
string? How is the length encoded? Hopefully not in a way that has
redundancy, since things that don't survive a serialization round trip
is a major trap.
Is the 'middle' the best place for the extradata? Have you
contemplated the possibility that some applications might use midstate
compression?
On that general subject, since the structure here pretty much always
guarantees two compression function invocations. SHA512/256 might
actually be faster in this application.
Re: using sha256 instead of sha256^2, we need to think carefully about
the implications of Merkle-Damgard generic length extension attacks.
It would be unfortunately to introduce them here, even though they're
currently mostly theoretical for sha256.
WRT hash function performance, hash functions are so ludicrously fast
(and will be more so as processors get SHA2 instructions) that the
performance of the raw compression function would hardly ever be a
performance consideration unless you're using a slow interpreted
language (... and that sounds like a personal problem to me). So I
don't think CPU performance should be a major consideration in this
BIP.
What I do think should be a consideration is the cost of validating
the structure under a zero-knowledge proof. An example application is
a blind proof for a SIN or a proof of how much coin you control... or
even a proof that a block was a correctly validated one, and in these
cases additional compression function calls are indeed pretty
expensive. But they're not the only cost, any conditional logic in the
hash tree evaluation is expensive, and particular, I think that any
place where data from children will be combined with a variable offset
(especially if its not word aligned) would potentially be rather
expensive.
I'm unconvinced about the prefix tree compressed applications, since
they break compact update proofs. If we used them in the Bitcoin
network they could only be used for data where all verifying nodes had
all their data under the tree. I think they add a lot of complexity to
the BIP (esp from people reading the wrong section), so perhaps they
should be split into another document?
In any case, I want to thank you for talking the time to write this
up. You've been working on this stuff for a while and I think it will
be lead to useful results, even if we don't end up using how it was
originally envisioned.
|
