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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
|
Return-Path: <pieter.wuille@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 0792239
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 6 Jun 2018 04:01:03 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ot0-f178.google.com (mail-ot0-f178.google.com
[74.125.82.178])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id D611E709
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 6 Jun 2018 04:01:01 +0000 (UTC)
Received: by mail-ot0-f178.google.com with SMTP id q17-v6so5535217otg.2
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 05 Jun 2018 21:01:01 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to;
bh=26lXPbQbbRRzESBy0t0eAambOIkkrhTnKvHDgEAaSac=;
b=cJPpCPT8Dg0BDqlUTV4NEhCThJUJRUv4nIGZXUv+OZJkuWbiRR6b/cwiq1pcdG4p2b
9bg0iFGB1TylgLKNOqFe5/EgGKKBnSPZN2E8Hvzyc8uyYc17LSxohKAaQQ3NR2/1PFf5
UGuJFbtJh+84SHN2BRf6T1sZ4ugnKZweW21FkwtUAMX/8IEF67a7C+gCKOnpuCrld3jI
qjFro1/PYXhy1/Sw9QJg122ahhT5nOO7WaOpdf50b705VBzEO9hr2JD3RXtZz7QBPmP2
t7UbUMAKBYzvZ4nhzk7C08B1AaR3sMFR4JRGbkEXw7he+dXjHk5bgJrCAUP+FiMFyRyw
mCqQ==
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=26lXPbQbbRRzESBy0t0eAambOIkkrhTnKvHDgEAaSac=;
b=tHwh2443quHdrnjW8njRrm708VFkPDxWlkYXb+LfvsnCGk9CT8+886TuNWiTwWpQS9
nj+xPytqXcSLqwroZOnn7me/bDWpzFmrzNbr2hfROmkrVqGGbanUlEG8eVqxWqcC0tZm
w4BXlghGNcC6PlLQxBvJdB0xSRhGkFg9Nm/eX+igg3cSdHQ1gNiPw2Hx/QWIYzjDEM0L
n0ailCh6aFcl48xRWFbCKcv7nBBuxLePUu6cSRawjmHzXE7HMh7hv6zDf/NCf3jYzoMO
I2ByItaLlkMwrRppWOeETqZ1gdIXGgRVff1bHQsTOvuv2H6cBegCUPu35f3lNDOJNzq3
epBg==
X-Gm-Message-State: APt69E2PiVXtdcl6ENaTKCK8m/egKV8SWiLDB0MLjH9BuFhzFkcafVYn
P1So4q3y2GafF/faBIw6OpsgggclJn8rYMs6cDs=
X-Google-Smtp-Source: ADUXVKL8w9lNmGCxM1QLF5N26tJpkYsyWcH+bElAzWg44y9byPkbXkHSNSGM8LTInqeYRZ3ay7VcZhYsE5I3I+gIgfc=
X-Received: by 2002:a9d:124:: with SMTP id 33-v6mr948237otu.65.1528257660997;
Tue, 05 Jun 2018 21:01:00 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a4a:6a89:0:0:0:0:0 with HTTP;
Tue, 5 Jun 2018 21:01:00 -0700 (PDT)
In-Reply-To: <CAGq_bNLvnZcOGU7c-8i7OL-OGAp4N2bX9T5SEROm59YBGL5yzw@mail.gmail.com>
References: <CAGq_bNLvnZcOGU7c-8i7OL-OGAp4N2bX9T5SEROm59YBGL5yzw@mail.gmail.com>
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Tue, 5 Jun 2018 21:01:00 -0700
Message-ID: <CAPg+sBjdTmZ4m5c92CQK5DsU18M=GKgTM-OZZzwgjpE3hqe6=w@mail.gmail.com>
To: Bradley Denby <bdenby@cmu.edu>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM,
RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving
Transaction Propagation
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: Wed, 06 Jun 2018 04:01:03 -0000
On Thu, May 10, 2018 at 5:59 AM, Bradley Denby via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> Hi all,
>
> ...
>
> This iteration of Dandelion has been tested on our own small network, and we
> would like to get the implementation in front of a wider audience. An
> updated
> BIP document with further details on motivation, specification,
> compatibility,
> and implementation is located here:
> https://github.com/mablem8/bips/blob/master/bip-dandelion.mediawiki
Hi Bradley,
thank you for working on this and going as far as implementing the
entire protocol. It looks like a very well-worked out idea already,
and its semantics can probably be adopted pretty much as-is. It would
be very exciting to bring these kinds of privacy improvements to
Bitcoin's P2P protocol.
I do have a number of comments on the specification and suggested
implementation in Bitcoin Core. I'm dumping my thoughts here, though
at this stage the specification is probably more important. The
implementation can be discussed more thoroughly when there is a PR
open.
Specification
* Overall, I think it would be worthwhile to describe the intended
node behavior in the BIP, at a higher level than Bitcoin Core
patchsets, but more detailed than what is in the BIP now. The
patch-based descriptions are both hard to read for developers working
on different systems who are unfamiliar with the Core codebase, and
don't make it clear to what extent implementation decisions are local
policy (which can be changed without network coordination), and which
follow from security or privacy arguments for the protocol.
* Interaction with feefilter (BIP 133) and Bloom filter (BIP 37). When
peers have given us filters on what transactions they will accept,
should Dandelion transactions be subject to the same? Should it
influence the choice of route? One simple possibility is perhaps to
avoid choosing BIP37 peers as Dandelion routes, and treat transactions
that do not pass the feefilter for its
would-be-outgoing-Dandelion-route as an automatic fluff - justified by
noting that relaying a transaction close to what fee is acceptable to
the network's mempools is already less likely to get good privacy due
to reduced chances of propagation.
* Mempool dependant transactions. It looks like the current
implementation accepts Dandelion transactions which are dependant on
other Dandelion (stempool) transactions and on confirmed blockchain
transactions, but not ones that are dependant on other unconfirmed
normal mempool transactions. Is this intentional, or resulting from a
difficulty in implementing this? Should the correct behaviour be
specified, or left free for nodes to decide?
* Orphan transactions. It looks like the current implementation
assumes no orphan transactions, but in a dynamic network (especially
with occasionally shuffling of Dandelion routes), I expect that
sometimes a dependent transaction will go on a different route than
its parent. Do you have any thoughts about that (even if not addressed
in a very implementation). Could we have a Dandelion-orphan-pool of
transactions, similar to the normal mempool has a set of orphan
transactions?
* Preferred connections. Should we bias the outgoing connection peer
selection code to prefer Dandelion-capable peers when the number is
too low?
Implementation
* How do we control the size of the stempool? Should acceptance of a
transaction to the normal mempool and/or blockchain result in eviction
of it (and conflicts) from the stempool? The existing code
intentionally has an upper bound on the size of the mempool to assure
predictable resource usage - the introduction of the stempool
shouldn't change that.
* I don't think you need to fully materialize all the routes. Instead,
you can just maintain a vector of 2 selected Dandelion-supporting
peers (and if one disconnects, replace just that one with another
one). To map incoming peers to an index in that list of peers, you can
use deterministic randomness (see SipHasher in the source code) with
the incoming node_id as data and a single global secret nonce (chosen
at startup, and reset on reshuffle).
* setDandelionInventoryKnown looks like it can grow unboundedly. A
rolling Bloom filter (like used for filterInventoryKnown) is perhaps
easier to guarantee predictable memory usage for.
* Use a scheduler job instead of a separate thread for shuffling the
routes (extra threads use unnecessarily large amounts of memory).
* (nit) coding style: doc/developer-notes.md has a number of
guidelines on coding style you may want to check out.
Cheers,
--
Pieter
|
