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
130
131
132
|
Return-Path: <pete@petertodd.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id B17E99B9
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 01:26:16 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from outmail148106.authsmtp.co.uk (outmail148106.authsmtp.co.uk
[62.13.148.106])
by smtp1.linuxfoundation.org (Postfix) with ESMTP id E827C210
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 01:26:15 +0000 (UTC)
Received: from mail-c247.authsmtp.com (mail-c247.authsmtp.com [62.13.128.247])
by punt22.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1N1QE3R052722;
Thu, 23 Feb 2017 01:26:14 GMT
Received: from petertodd.org (ec2-52-5-185-120.compute-1.amazonaws.com
[52.5.185.120]) (authenticated bits=0)
by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1N1QCXE023017
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO);
Thu, 23 Feb 2017 01:26:13 GMT
Received: from [127.0.0.1] (localhost [127.0.0.1])
by petertodd.org (Postfix) with ESMTPSA id 7924440123;
Thu, 23 Feb 2017 01:26:12 +0000 (UTC)
Received: by localhost (Postfix, from userid 1000)
id A058220245; Wed, 22 Feb 2017 20:26:11 -0500 (EST)
Date: Wed, 22 Feb 2017 20:26:11 -0500
From: Peter Todd <pete@petertodd.org>
To: Bram Cohen <bram@bittorrent.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20170223012611.GA1454@savin.petertodd.org>
References: <CA+KqGkpVLfGjQUJEYdRppqvN263rHrY-rGL2k22eMryQbb6Q8g@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="5vNYLRcllDrimb99"
Content-Disposition: inline
In-Reply-To: <CA+KqGkpVLfGjQUJEYdRppqvN263rHrY-rGL2k22eMryQbb6Q8g@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
X-Server-Quench: 10d0a713-f967-11e6-bcdf-0015176ca198
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
aAdMdAEUHlAWAgsB AmEbW1VeUlt7WGc7 bghPaBtcak9QXgdq
T0pMXVMcUgQWAH1y bmseUBpydgIIfnhx YQhjXiRbDUN7dlsr
S0hTCGwHMGF9OjNL Bl1YdwJRcQRMLU5E Y1gxIyZTNCdWOiMq
EgN7FDc0ODRDLSlT Xhpl
X-Authentic-SMTP: 61633532353630.1038:706
X-AuthFastPath: 0 (Was 255)
X-AuthSMTP-Origin: 52.5.185.120/25
X-AuthVirus-Status: No virus detected - but ensure you scan with your own
anti-virus system.
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW
autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: [bitcoin-dev] Generalized Commitments
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: Thu, 23 Feb 2017 01:26:16 -0000
--5vNYLRcllDrimb99
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Tue, Feb 21, 2017 at 02:00:23PM -0800, Bram Cohen via bitcoin-dev wrote:
> 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 resista=
nt
> to malicious data, and cleans up some implementation details, at the cost
> of some extra complexity.
Note that this is a use-case specific concept of an idea I'm calling a
"generalized commitment"
A commitment scheme needs only have the property that it's not feasible to =
find
two messages m1 and m2 that map to the same commitment; it is *not* required
that it be difficult to find m given the commitment. Equally, it's not requ=
ired
that commitments always be the same size.
So a perfectly reasonable thing to do is design your scheme such that the
commitment to short messages is the message itself! This adds just a single=
bit
of data to the minimum serialized size(1) of the commitment, and in situati=
ons
where sub-digest-sized messages are common, may overall be a savings.
Another advantage is that the scheme becomes more user-friendly: you *want*
programmers to notice when a commitment is not effectively hiding the messa=
ge!
If you need message privacy, you should implement an explicit nonce, rather
than relying on the data to not be brute-forcable.
1) The more I look at these systems, the more I'm inclined to consider
bit-granularity serialization schemes... Heck, sub-bit granularity has
advantages too in some cases, e.g. by making all possible inputs to the
deserializer be valid.
--=20
https://petertodd.org 'peter'[:-1]@petertodd.org
--5vNYLRcllDrimb99
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
iQEcBAEBCAAGBQJYrjowAAoJECSBQD2l8JH76QcH/3Ipz8aGgWcVyRve/EfXijcG
F0ptbO4/pKG8WeX4wBy2jyQ6TTK4Czb29uOpMk0Zmtys25R242O2kk5QC5D6ghnf
TBUpgwL1YXYmc0zZqNU109Ax2/c1foQiNyXpgbLykGg8mtGXaNN8+KGqsrQs4qQ8
e9I6pQDZOOCqBGoNt4UF4gJyFB3gfeCwxCQN+xhv1+l6W1wCY+B1b1gWSZZFvJMF
11Ixlm+bApwCRJPrkpPdZiUcSEfqjPB26dU1iBIvLyMwmS9zDn0Fv1eSwQecwf5f
8EZ6JVV4OE9pUyGseAN3HIkEc0U0IAjlYqIRC2Q1bpLFtRTpsPRHQepBd/HmtO0=
=GaJz
-----END PGP SIGNATURE-----
--5vNYLRcllDrimb99--
|
