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
|
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 0D4283EE
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 21 Feb 2017 22:00:25 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f41.google.com (mail-it0-f41.google.com
[209.85.214.41])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8A6601B5
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 21 Feb 2017 22:00:24 +0000 (UTC)
Received: by mail-it0-f41.google.com with SMTP id d9so36552928itc.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 21 Feb 2017 14:00:24 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=bittorrent-com.20150623.gappssmtp.com; s=20150623;
h=mime-version:from:date:message-id:subject:to;
bh=DTYiRPoLkurICjMF+UofCZy8f0YDWagRiw0LZaN2Gvg=;
b=UXamKRaLooK1f3ln58f7bo8Sgj7aCZ9Yfp8oNyjElWxAp6yLruoJb+pfPBKIOT5JbT
WvRa862tUF1IDaugZ2CGODW8dhPQzGTppTMXnNwXpd9ozoUlYPvBiHaWojvkPLiMA7wE
WjWJVdo+xq2bCMZGdVBxaDmyzh5PMGOZ2gsMhH+cDw4hqpMlTrttG8j0AsiWL+BftN7z
+RvXz78W3NzYZT1Cg85lPU8k2rt19OZ/tGzJ7rL2nte6KlbEzOIFsQdPJlY5AEonjDhM
+5LS08pV9ffWJxYyfkuOW14bZOklMUG3O9aETzR6RUAAUqREsxA6669WYCMCCEin98k2
ct+A==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
bh=DTYiRPoLkurICjMF+UofCZy8f0YDWagRiw0LZaN2Gvg=;
b=Ju5BBOKiaxYrcnS12LCnHjyDwEEKtTZhyyKPxOAfhW8hU6koGV+iUUTC+zFTQBW45u
KdxgX4t/skZH5d/MoEhix+EdozMNjIz+gRUZAbrM1oKonXp14AnULmq7RLwnZB3a3bdF
e8CQMRLIQXdiLGEWpeOucNbzIx7ns8/UBoG5DfBhXhMQNXrqm9Os+KjtMIxdlVGfNIvb
BdbxX+GmpXh0zEoWL5msCSBrPVz/ePpZ0WXE/zw52pweJIEV+svY4IOyCjGAkvSI0Squ
rLPoKpwCy1ikTXAV2d32j3zSucc1jetodqqMPe3Mht3D5yNFIPZjqZ+McF2i2BSBGfzj
J18A==
X-Gm-Message-State: AMke39nLYf1awAYNNVLH1JmTU16PiJs9FDDz1O1wy991gKvGpHiV20OKuB10z3KdQk6U4jXyyRQhNT63vt1Be72V
X-Received: by 10.36.25.83 with SMTP id b80mr17180887itb.98.1487714423773;
Tue, 21 Feb 2017 14:00:23 -0800 (PST)
MIME-Version: 1.0
Received: by 10.36.73.150 with HTTP; Tue, 21 Feb 2017 14:00:23 -0800 (PST)
From: Bram Cohen <bram@bittorrent.com>
Date: Tue, 21 Feb 2017 14:00:23 -0800
Message-ID: <CA+KqGkpVLfGjQUJEYdRppqvN263rHrY-rGL2k22eMryQbb6Q8g@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=001a11440182c1b425054911818d
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: [bitcoin-dev] Proposal for utxo commitment format
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: Tue, 21 Feb 2017 22:00:25 -0000
--001a11440182c1b425054911818d
Content-Type: text/plain; charset=UTF-8
Here is a Merkle set data structure, whose format may be useful for utxo
commitments in Bitcoin blocks. It may also be useful for any other
distributed computation which wants an audit trail:
https://github.com/bramcohen/MerkleSet
This is a fairly straightforward Patricia Trie, with a simple format and a
simple reference implementation plus a performance optimized non-reference
implementation which is much more cache coherent. It will need to be ported
to C and be properly turned before the potential performance gains can be
realized though.
The clever things which affect the format spec are:
It uses blake2s as the internal hash function. This is the fastest hash
function to use on 512 bit inputs because blake2b uses a 1024 bit block
size. It might make sense to use a hypothetical variant of blake which is
optimized for 64 bits with a 512 bit block size, but that hasn't been
specified. Sha256 would take advantage of hardware acceleration, but that
isn't available everywhere.
Two bits of security are sacrificed to include metadata inline which halves
the CPU cost of hashing.
When one side of a node is empty and the other contains exactly two things
the secure hash of the child is adopted verbatim rather than rehashing it.
This roughly halves the amount of hashing done, and makes it more resistant
to malicious data, and cleans up some implementation details, at the cost
of some extra complexity.
--001a11440182c1b425054911818d
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Here is a Merkle set data structure, whose format may be u=
seful for utxo commitments in Bitcoin blocks. It may also be useful for any=
other distributed computation which wants an audit trail:<div><br></div><d=
iv><a href=3D"https://github.com/bramcohen/MerkleSet">https://github.com/br=
amcohen/MerkleSet</a><br></div><div><br></div><div>This is a fairly straigh=
tforward Patricia Trie, with a simple format and a simple reference impleme=
ntation plus a performance optimized non-reference implementation which is =
much more cache coherent. It will need to be ported to C and be properly tu=
rned before the potential performance gains can be realized though.=C2=A0</=
div><div><br></div><div>The clever things which affect the format spec are:=
</div><div><br></div><div>It uses blake2s as the internal hash function. Th=
is is the fastest hash function to use on 512 bit inputs because blake2b us=
es a 1024 bit block size. It might make sense to use a hypothetical variant=
of blake which is optimized for 64 bits with a 512 bit block size, but tha=
t hasn't been specified. Sha256 would take advantage of hardware accele=
ration, but that isn't available everywhere.</div><div><br></div><div>T=
wo bits of security are sacrificed to include metadata inline which halves =
the CPU cost of hashing.</div><div><br></div><div>When one side of a node i=
s empty and the other contains exactly two things the secure hash of the ch=
ild is adopted verbatim rather than rehashing it. This roughly halves the a=
mount of hashing done, and makes it more resistant to malicious data, and c=
leans up some implementation details, at the cost of some extra complexity.=
</div></div>
--001a11440182c1b425054911818d--
|
