From c947050ed87b18be580f540951704d35809f92c9 Mon Sep 17 00:00:00 2001 From: Brad Denby Date: Fri, 20 Apr 2018 18:34:22 -0400 Subject: Dandelion BIP Dandelion BIP Dandelion BIP Dandelion BIP Dandelion BIP Dandelion BIP Dandelion BIP Dandelion BIP Dandelion BIP Dandelion BIP Dandelion BIP --- bip-dandelion.mediawiki | 321 +++++++++++++++++++++ bip-dandelion/1-dandelion.png | Bin 0 -> 136499 bytes bip-dandelion/2-attack.png | Bin 0 -> 96620 bytes bip-dandelion/3-attack-plot.png | Bin 0 -> 71995 bytes bip-dandelion/4-dandelion-plot.png | Bin 0 -> 55017 bytes bip-dandelion/bitcoin.conf | 16 + bip-dandelion/dandelion-debug-logs-example.pdf | Bin 0 -> 41016 bytes .../dandelion-reference-documentation.pdf | Bin 0 -> 89864 bytes 8 files changed, 337 insertions(+) create mode 100644 bip-dandelion.mediawiki create mode 100644 bip-dandelion/1-dandelion.png create mode 100644 bip-dandelion/2-attack.png create mode 100644 bip-dandelion/3-attack-plot.png create mode 100644 bip-dandelion/4-dandelion-plot.png create mode 100644 bip-dandelion/bitcoin.conf create mode 100644 bip-dandelion/dandelion-debug-logs-example.pdf create mode 100644 bip-dandelion/dandelion-reference-documentation.pdf diff --git a/bip-dandelion.mediawiki b/bip-dandelion.mediawiki new file mode 100644 index 0000000..965c275 --- /dev/null +++ b/bip-dandelion.mediawiki @@ -0,0 +1,321 @@ +
+  BIP: ?
+  Layer: Peer Services
+  Title: Dandelion - Privacy Enhancing Routing
+  Author: Brad Denby 
+          Andrew Miller 
+          Giulia Fanti 
+          Surya Bakshi 
+          Shaileshh Bojja Venkatakrishnan 
+          Pramod Viswanath 
+  Comments-URI: https://github.com/mablem8/bips/wiki/Comments:BIP-Dandelion
+  Status: Draft
+  Type: Standards Track
+  Created: 2017-06-09
+  License: Creative Commons CC0 1.0 Universal
+
+ +==Abstract== + +Bitcoin's transaction spreading protocol is vulnerable to deanonymization +attacks. Dandelion is a transaction routing mechanism that provides formal +anonymity guarantees against these attacks. When a node generates a transaction +without Dandelion, it transmits that transaction to its peers with independent, +exponential delays. This approach, known as diffusion in academia, allows +network adversaries to link transactions to IP addresses. + +Dandelion mitigates this class of attacks by sending transactions over a +randomly selected path before diffusion. Transactions travel along this path +during the "stem phase" and are then diffused during the "fluff phase" (hence +Dandelion). We have shown that this routing protocol provides near-optimal +anonymity guarantees among schemes that do not introduce additional encryption +mechanisms. + +==Motivation== + +Transaction diffusion in Bitcoin is vulnerable to deanonymization attacks. +Because transactions are sent to peers with independent, exponential delays, +messages spread through the network in a statistically symmetric manner. This +pattern allows colluding spy nodes to infer the transaction source. Breaking +this symmetry prevents the attack. However, we have shown that an adversary with +knowledge of the network topology can launch a much more effective "fingerprint" +attack if the symmetry breaking is not done properly. + +Consider a botnet-style adversary with access to the P2P graph. Botnets of size +comparable to the Bitcoin P2P network are common and cheap, and these +adversaries can learn the network structure with probe messages. We have shown +that such an adversary can achieve total deanonymization of the entire network +after observing less than ten transactions per node. + +Dandelion is a practical, lightweight privacy solution that provides the Bitcoin +network formal anonymity guarantees. While other privacy solutions aim to +protect individual users, Dandelion protects anonymity by limiting the +capability of adversaries to deanonymize the entire network. + +==How Dandelion Works== + +Dandelion enhances user privacy by sending transactions through an anonymity +phase before diffusing them throughout the network. At a high level, Dandelion +enhances privacy by (i) breaking the symmetry of diffusion and (ii) mixing +transactions by forwarding messages from different sources along the same path. + +Dandelion routing can be conceptualized in three phases. First, a privacy graph +is constructed. In practice, this privacy graph is constructed in a fully +decentralized manner and is a subgraph of the existing Bitcoin P2P network. +Next, transactions are forwarded along this privacy graph during the "stem +phase." Finally, messages are broadcast to the network during the "fluff phase" +using the typical method of diffusion. + +[[File:bip-dandelion/1-dandelion.png|framed|center|alt=An illustration of Dandelion routing|Figure 1]] +Figure 1 + +In order to select the privacy graph in a decentralized manner, each node +selects a subset of its outbound peers to be Dandelion destinations. Dandelion +transactions (transactions in their stem phase) that arrive at this node via +inbound connections are forwarded to these Dandelion destinations. + +In an ideal setting, we have found that a Hamiltonian circuit provides +near-optimal privacy guarantees. However, constructing a Hamiltonian circuit +through the Bitcoin P2P network in a decentralized, trustless manner is not +feasible. Thus, we recommend that each node select two Dandelion destinations +uniformly at random without replacement from its list of outbound peers. Our +tests have shown that this method provides comparable privacy with increased +robustness. + +During stem phase routing, there is a question of how to route messages in order +to protect privacy. For example, if two Dandelion transactions arrive at a node +from different inbound peers, to which Dandelion destination(s) should these +transactions be sent? We have found that some choices are much better than +others. + +Consider the case in which each Dandelion transaction is forwarded to a +Dandelion destination selected uniformly at random. This approach results in a +fingerprint attack allowing network-level botnet adversaries to achieve total +deanonymization of the P2P network after observing less than ten transactions +per node. + +[[File:bip-dandelion/2-attack.png|framed|center|alt=An illustration of a fingerprint attack|Figure 2]] +Figure 2 + +During a fingerprint attack, a botnet-style adversary with knowledge of the +graph structure first simulates transaction propagation. This offline step lets +the adversary generate fingerprints for each network node. During the online +attack, the adversary collects transactions at its spy nodes and matches these +observations to the simulated fingerprints. Our simulations have shown that this +attack results in devastating, network-wide deanonymization. + +[[File:bip-dandelion/3-attack-plot.png|framed|center|alt=A plot illustrating total deanonymization|Figure 3]] +Figure 3 + +To avoid this issue, we suggest "per-inbound-edge" routing. Each inbound peer is +assigned a particular Dandelion destination. Each Dandelion transaction that +arrives via this peer is forwarded to the same Dandelion destination. +Per-inbound-edge routing breaks the described attack by blocking an adversary's +ability to construct useful fingerprints. Fingerprints arise when routing +decisions are made independently per transaction at each node. In this case, two +transactions from the same node generally take different paths through the +network. Crucially, this results in multiple, unique data points that are +aggregated to match with a fingerprint. + +Dandelion ensures that two transactions from the same node take the same network +path, limiting adversaries to the far-left of the graph in Figure 3. In other +words, adversary knowledge is limited to the case of one observed message rather +than a rich profile of multiple transaction paths. Dandelion also breaks the +symmetry of diffusion, making the source of the transaction difficult to infer. + +[[File:bip-dandelion/4-dandelion-plot.png|framed|center|alt=A plot illustrating limited deanonymization|Figure 4]] +Figure 4 + +After a transaction has traveled along a Dandelion stem for a random number of +hops, it transitions into the fluff phase of routing. The transaction is shared +with the network through the existing process of diffusion. In practice, this +fluff mechanism is enforced by a weighted coin flip at each node. If the random +value is below some threshold, the Dandelion transaction is transformed into a +typical transaction. In our testing, we have chosen a probability of ten percent +that a given Dandelion transaction enters fluff phase when leaving a given node. +This value strikes a good balance between stem path length and transaction +spreading latency. + +Note that Dandelion's expected precision guarantees are a population-level +metric, whereas the expected recall guarantees can be interpreted as an +individual-level metric. Expected recall is equivalent to the probability that +an adversary associates a single transaction with a given source. These +guarantees are probabilistic. They do not address scenarios in which a node has +been eclipsed by other nodes, or when a node is specifically targeted by an +ISP-like adversary. Individuals who are concerned about targeted deanonymization +should still use Tor. + +At a high level, Dandelion is like an "anonymity inoculation" for the public at +large - including users who are not aware of Bitcoin's privacy issues. Higher +adoption leads to greater benefits, even for users who do not use Tor. Early +adopters of Dandelion still receive privacy benefits. In the worst case when no +neighbors support Dandelion, transactions make at least one hop before +diffusing. Note that any solution based only on routing cannot be perfectly +anonymous due to the fundamental lower bounds on precision and recall shown in +the original Dandelion paper. Dandelion provides near-optimal anonymity +guarantees among such solutions. + +==Specification== + +Dandelion can be specified with a handful of features: Dandelion transaction +support, Dandelion routing data and logic, periodic Dandelion route shuffling, +memory pool logic, the fluff mechanism, transaction embargoes, and Dandelion +transaction logic. Specification details are summarized below. + +===Dandelion transaction support=== + +During the stem phase, transactions are "Dandelion transactions." When a +Dandelion transaction enters fluff phase, it becomes a typical Bitcoin +transaction. Dandelion transactions and typical transactions differ only in +their NetMsgType. + +Dandelion (stem phase) transactions MUST be differentiable from typical Bitcoin +transactions. + +===Dandelion routing data and logic=== + +Dandelion routing during the stem phase requires notions of inbound peers, +outbound peers, Dandelion destinations, and Dandelion routes. Inbound peers +consist of all currently connected peers that initiated the peer connection. +Outbound peers consist of all currently connected peers that were connected to +by this node. Dandelion destinations are a subset of outbound peers. The number +of Dandelion destinations is limited by the +DANDELION_MAX_DESTINATIONS parameter. In the reference +implementation, this parameter is set to two. Our tests have shown that this +value provides both privacy and robustness (see the reference paper for more +details on the parameter tradeoffs). Dandelion routes are a map of inbound peers +to Dandelion destinations. Every inbound peer is mapped to a Dandelion +destination. + +Note that a Dandelion node may choose a different +DANDELION_MAX_DESTINATIONS parameter without splitting from the +privacy graph. When mapping inbound connections to outbound connections for +Dandelion routes, we implement the following routing logic. First, select a set +of Dandelion destinations from the set of outbound peers. This set of Dandelion +destinations is of size less than or equal to +DANDELION_MAX_DESTINATIONS. For each inbound connection, first +identify the subset of Dandelion destinations with the least number of routes. +For example, some subset of Dandelion destinations may be affiliated with zero +routes while all other Dandelion destinations are affiliated with one or more +routes. From this subset, select one Dandelion destination uniformly at random. +Establish a Dandelion route from the inbound connection to this Dandelion +destination. + +For a given Dandelion routing epoch, two distinct Dandelion destinations SHOULD +be selected uniformly at random from the set of outbound connections. All +Dandelion transactions that arrive via a given inbound connection MUST be +transmitted to the same Dandelion destination. When choosing a Dandelion +destination for a given inbound connection, the destination MUST be selected +uniformly at random from the set of Dandelion destinations with the least number +of inbound connections mapped to them. + +===Periodic Dandelion route shuffling=== + +The map of Dandelion routes is cleared and reconstructed every ten minutes on +average. We have chosen the value of ten minutes heuristically in order to make +privacy graph learning difficult for adversaries. Note that a Dandelion node may +choose a different average shuffle time without splitting from the privacy +graph. + +Dandelion routes MUST be cleared and reconstructed at random intervals. +Dandelion routes SHOULD be cleared and reconstructed every ten minutes on +average. + +===Memory pool logic=== + +Dandelion transactions are segregated from typical transactions. The +mempool remains unchanged. Another instance of the +CTxMemPool class, called the stempool, is used for +Dandelion transactions. Information flows from mempool to +stempool in order to ensure proper transaction propagation. +Information does not flow from stempool to mempool, +except when a Dandelion transaction fluffs into a typical transaction. + +When a Dandelion transaction arrives, the transaction MUST be added to the +stempool and MUST NOT be added to the mempool. When a typical Bitcoin +transaction arrives, the transaction MUST be added to the mempool and MUST be +added to the stempool. When a Dandelion transaction fluffs, the transaction MUST +be added to the mempool. + +===The fluff mechanism=== + +When relaying a Dandelion transaction along a Dandelion route, there is a 10% +chance that the Dandelion transaction becomes a typical Bitcoin transaction and +is therefore relayed via diffusion. In our testing, this value strikes a good +balance between stem path length and transaction spreading latency. Note that a +Dandelion node may choose a different chance of fluffing without splitting from +the privacy graph. + +When a node prepares to transmit a Dandelion transaction, the node MUST flip a +biased coin. If the outcome is "Dandelion transaction," then the node MUST +transmit the transaction to the appropriate Dandelion destination. Otherwise, +the node MUST convert the Dandelion transaction into a typical Bitcoin +transaction. A Dandelion transaction SHOULD fluff into a typical Bitcoin +transaction with a 10% probability. + +===Transaction embargoes=== + +During the stem phase, transactions are relayed along a single path. If any node +in this path were to receive the Dandelion transaction and go offline, then the +transaction would cease to propagate. To increase robustness, every node that +forwards a Dandelion transaction initializes a timer at the time of reception. +If the Dandelion transaction does not appear in the memory pool by the time the +timer expires, then the transaction enters fluff phase and is forwarded via +diffusion. + +When a Dandelion transaction arrives, the node MUST set an embargo timer for a +random time in the future. If the Dandelion transaction arrives as a typical +Bitcoin transaction, the node MUST cancel the timer. If the timer expires before +the Dandelion transaction is observed as a typical Bitcoin transaction, then the +node MUST fluff the Dandelion transaction. + +===Dandelion transaction logic=== + +The following cases define a node's behavior when receiving network packets +referencing Dandelion transactions. +* Receive INV for Dandelion TX: If the peer is inbound and the Dandelion transaction has not been received from this peer, then reply with GETDATA. +* Receive GETDATA for Dandelion TX: If the peer is not inbound and the Dandelion transaction has been advertised to this peer, then reply with the Dandelion transaction. +* Receive Dandelion TX: If the peer is inbound, then relay the Dandelion TX to the appropriate Dandelion destination. + +==Implementation== + +A reference implementation is available at the following URL: +https://github.com/mablem8/bitcoin/tree/dandelion-feature-commits + +All features have been compressed into a single commit at the following URL: +https://github.com/mablem8/bitcoin/tree/dandelion + +==Compatibility== + +Dandelion does not conflict with existing versions of Bitcoin. A Bitcoin node +that supports Dandelion appears no differently to Bitcoin nodes running older +software versions. Bitcoin nodes that support Dandelion can identify feature +support through a probe message. Obviously, older nodes are not capable of +Dandelion routing. If a Bitcoin node supporting Dandelion has no peers that also +support Dandelion, then its behavior naturally decays to that of a Bitcoin node +without Dandelion support due to the Dandelion transaction embargoes. + +==Acknowledgements== + +We would like to thank the Bitcoin Core developers and Gregory Maxwell in +particular for their insightful comments, which helped to inform this +implementation and some of the follow-up work we conducted. We would also like +to thank the Mimblewimble development community for coining the term "stempool," +which we happily adopted for this implementation. + +==References== + +# An Analysis of Anonymity in Bitcoin Using P2P Network Traffic http://fc14.ifca.ai/papers/fc14_submission_71.pdf +# Deanonymisation of clients in Bitcoin P2P network https://arxiv.org/abs/1405.7418 +# Discovering Bitcoin’s Public Topology and Influential Nodes https://cs.umd.edu/projects/coinscope/coinscope.pdf +# (Sigmetrics 2017) Dandelion: Redesigning the Bitcoin Network for Anonymity https://arxiv.org/abs/1701.04439 +# (Sigmetrics 2018) Dandelion++: Lightweight Cryptocurrency Networking with Formal Anonymity Guarantees https://arxiv.org/pdf/1805.11060.pdf + +==Copyright== + +To the extent possible under law, the author(s) have dedicated all copyright and +related and neighboring rights to this work to the public domain worldwide. This +work is distributed without any warranty. + +You should have received a copy of the CC0 Public Domain Dedication with this +work. If not, see https://creativecommons.org/publicdomain/zero/1.0/ . diff --git a/bip-dandelion/1-dandelion.png b/bip-dandelion/1-dandelion.png new file mode 100644 index 0000000..d17e5ce Binary files /dev/null and b/bip-dandelion/1-dandelion.png differ diff --git a/bip-dandelion/2-attack.png b/bip-dandelion/2-attack.png new file mode 100644 index 0000000..c6165d1 Binary files /dev/null and b/bip-dandelion/2-attack.png differ diff --git a/bip-dandelion/3-attack-plot.png b/bip-dandelion/3-attack-plot.png new file mode 100644 index 0000000..8a35a86 Binary files /dev/null and b/bip-dandelion/3-attack-plot.png differ diff --git a/bip-dandelion/4-dandelion-plot.png b/bip-dandelion/4-dandelion-plot.png new file mode 100644 index 0000000..5fe2150 Binary files /dev/null and b/bip-dandelion/4-dandelion-plot.png differ diff --git a/bip-dandelion/bitcoin.conf b/bip-dandelion/bitcoin.conf new file mode 100644 index 0000000..e9e6581 --- /dev/null +++ b/bip-dandelion/bitcoin.conf @@ -0,0 +1,16 @@ +regtest=1 # Run this node on its own independent test network +debug=net # Enable network debug logs +debug=mempool # Enable mempool debug logs +debug=mempoolrej # Enable mempool rejection debug logs +debug=dandelion # Enable dandelion debug logs +logips=1 # Log IP addresses in debug output +logtimemicros=1 # Log timestamps with microsecond precision +printtoconsole=1 # Print debug logs to console instead of debug.log +server=1 # Accept command line JSON-RPC commands +rpcuser=xxx # Username for JSON-RPC connections +rpcpassword=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx +rpcauth=xxx:xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx +dns=0 # Do not allow DNS lookups for -addnode, -seednode, and -connect +dnsseed=0 # Do not query for peer addresses via DNS lookup +persistmempool=0 # Do not save mempool on shutdown to load on restart +dandelion=1 # Enable Dandelion transactions diff --git a/bip-dandelion/dandelion-debug-logs-example.pdf b/bip-dandelion/dandelion-debug-logs-example.pdf new file mode 100644 index 0000000..4f4180e Binary files /dev/null and b/bip-dandelion/dandelion-debug-logs-example.pdf differ diff --git a/bip-dandelion/dandelion-reference-documentation.pdf b/bip-dandelion/dandelion-reference-documentation.pdf new file mode 100644 index 0000000..aee33f1 Binary files /dev/null and b/bip-dandelion/dandelion-reference-documentation.pdf differ -- cgit v1.2.3 From ad3356689f88e6576dbefc340f92a98e9194e454 Mon Sep 17 00:00:00 2001 From: Giulia Fanti Date: Mon, 13 Aug 2018 21:18:22 -0400 Subject: fixed bip number --- bip-dandelion.mediawiki | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/bip-dandelion.mediawiki b/bip-dandelion.mediawiki index 965c275..3ecdfbb 100644 --- a/bip-dandelion.mediawiki +++ b/bip-dandelion.mediawiki @@ -1,5 +1,5 @@ 
-  BIP: ?
+  BIP: 156
   Layer: Peer Services
   Title: Dandelion - Privacy Enhancing Routing
   Author: Brad Denby 
@@ -8,11 +8,11 @@
           Surya Bakshi 
           Shaileshh Bojja Venkatakrishnan 
           Pramod Viswanath 
-  Comments-URI: https://github.com/mablem8/bips/wiki/Comments:BIP-Dandelion
+  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0156
   Status: Draft
   Type: Standards Track
   Created: 2017-06-09
-  License: Creative Commons CC0 1.0 Universal
+  License: CC0-1.0
==Abstract== -- cgit v1.2.3 From 8e4e640096747688fab61af661b1e4d8db8fc2bb Mon Sep 17 00:00:00 2001 From: Giulia Fanti Date: Mon, 13 Aug 2018 22:08:58 -0400 Subject: renamed files and updated README.mediawiki index --- README.mediawiki | 7 + bip-0156.mediawiki | 321 +++++++++++++++++++++ bip-0156/1-dandelion.png | Bin 0 -> 136499 bytes bip-0156/2-attack.png | Bin 0 -> 96620 bytes bip-0156/3-attack-plot.png | Bin 0 -> 71995 bytes bip-0156/4-dandelion-plot.png | Bin 0 -> 55017 bytes bip-0156/bitcoin.conf | 16 + bip-0156/dandelion-debug-logs-example.pdf | Bin 0 -> 41016 bytes bip-0156/dandelion-reference-documentation.pdf | Bin 0 -> 89864 bytes bip-dandelion.mediawiki | 321 --------------------- bip-dandelion/1-dandelion.png | Bin 136499 -> 0 bytes bip-dandelion/2-attack.png | Bin 96620 -> 0 bytes bip-dandelion/3-attack-plot.png | Bin 71995 -> 0 bytes bip-dandelion/4-dandelion-plot.png | Bin 55017 -> 0 bytes bip-dandelion/bitcoin.conf | 16 - bip-dandelion/dandelion-debug-logs-example.pdf | Bin 41016 -> 0 bytes .../dandelion-reference-documentation.pdf | Bin 89864 -> 0 bytes 17 files changed, 344 insertions(+), 337 deletions(-) create mode 100644 bip-0156.mediawiki create mode 100644 bip-0156/1-dandelion.png create mode 100644 bip-0156/2-attack.png create mode 100644 bip-0156/3-attack-plot.png create mode 100644 bip-0156/4-dandelion-plot.png create mode 100644 bip-0156/bitcoin.conf create mode 100644 bip-0156/dandelion-debug-logs-example.pdf create mode 100644 bip-0156/dandelion-reference-documentation.pdf delete mode 100644 bip-dandelion.mediawiki delete mode 100644 bip-dandelion/1-dandelion.png delete mode 100644 bip-dandelion/2-attack.png delete mode 100644 bip-dandelion/3-attack-plot.png delete mode 100644 bip-dandelion/4-dandelion-plot.png delete mode 100644 bip-dandelion/bitcoin.conf delete mode 100644 bip-dandelion/dandelion-debug-logs-example.pdf delete mode 100644 bip-dandelion/dandelion-reference-documentation.pdf diff --git a/README.mediawiki b/README.mediawiki index eb3b0e7..0f36f9f 100644 --- a/README.mediawiki +++ b/README.mediawiki @@ -736,6 +736,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Draft |- +| [[bip-0156.mediawiki|156]] +| Peer Services +| Dandelion - Privacy Enhancing Routing +| Bradley Denby, Andrew Miller, Giulia Fanti, Surya Bakshi, Shaileshh Bojja Venkatakrishnan, Pramod Viswanath +| Standard +| Draft +|- | [[bip-0157.mediawiki|157]] | Peer Services | Client Side Block Filtering diff --git a/bip-0156.mediawiki b/bip-0156.mediawiki new file mode 100644 index 0000000..3ecdfbb --- /dev/null +++ b/bip-0156.mediawiki @@ -0,0 +1,321 @@ +
+  BIP: 156
+  Layer: Peer Services
+  Title: Dandelion - Privacy Enhancing Routing
+  Author: Brad Denby 
+          Andrew Miller 
+          Giulia Fanti 
+          Surya Bakshi 
+          Shaileshh Bojja Venkatakrishnan 
+          Pramod Viswanath 
+  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0156
+  Status: Draft
+  Type: Standards Track
+  Created: 2017-06-09
+  License: CC0-1.0
+
+ +==Abstract== + +Bitcoin's transaction spreading protocol is vulnerable to deanonymization +attacks. Dandelion is a transaction routing mechanism that provides formal +anonymity guarantees against these attacks. When a node generates a transaction +without Dandelion, it transmits that transaction to its peers with independent, +exponential delays. This approach, known as diffusion in academia, allows +network adversaries to link transactions to IP addresses. + +Dandelion mitigates this class of attacks by sending transactions over a +randomly selected path before diffusion. Transactions travel along this path +during the "stem phase" and are then diffused during the "fluff phase" (hence +Dandelion). We have shown that this routing protocol provides near-optimal +anonymity guarantees among schemes that do not introduce additional encryption +mechanisms. + +==Motivation== + +Transaction diffusion in Bitcoin is vulnerable to deanonymization attacks. +Because transactions are sent to peers with independent, exponential delays, +messages spread through the network in a statistically symmetric manner. This +pattern allows colluding spy nodes to infer the transaction source. Breaking +this symmetry prevents the attack. However, we have shown that an adversary with +knowledge of the network topology can launch a much more effective "fingerprint" +attack if the symmetry breaking is not done properly. + +Consider a botnet-style adversary with access to the P2P graph. Botnets of size +comparable to the Bitcoin P2P network are common and cheap, and these +adversaries can learn the network structure with probe messages. We have shown +that such an adversary can achieve total deanonymization of the entire network +after observing less than ten transactions per node. + +Dandelion is a practical, lightweight privacy solution that provides the Bitcoin +network formal anonymity guarantees. While other privacy solutions aim to +protect individual users, Dandelion protects anonymity by limiting the +capability of adversaries to deanonymize the entire network. + +==How Dandelion Works== + +Dandelion enhances user privacy by sending transactions through an anonymity +phase before diffusing them throughout the network. At a high level, Dandelion +enhances privacy by (i) breaking the symmetry of diffusion and (ii) mixing +transactions by forwarding messages from different sources along the same path. + +Dandelion routing can be conceptualized in three phases. First, a privacy graph +is constructed. In practice, this privacy graph is constructed in a fully +decentralized manner and is a subgraph of the existing Bitcoin P2P network. +Next, transactions are forwarded along this privacy graph during the "stem +phase." Finally, messages are broadcast to the network during the "fluff phase" +using the typical method of diffusion. + +[[File:bip-dandelion/1-dandelion.png|framed|center|alt=An illustration of Dandelion routing|Figure 1]] +Figure 1 + +In order to select the privacy graph in a decentralized manner, each node +selects a subset of its outbound peers to be Dandelion destinations. Dandelion +transactions (transactions in their stem phase) that arrive at this node via +inbound connections are forwarded to these Dandelion destinations. + +In an ideal setting, we have found that a Hamiltonian circuit provides +near-optimal privacy guarantees. However, constructing a Hamiltonian circuit +through the Bitcoin P2P network in a decentralized, trustless manner is not +feasible. Thus, we recommend that each node select two Dandelion destinations +uniformly at random without replacement from its list of outbound peers. Our +tests have shown that this method provides comparable privacy with increased +robustness. + +During stem phase routing, there is a question of how to route messages in order +to protect privacy. For example, if two Dandelion transactions arrive at a node +from different inbound peers, to which Dandelion destination(s) should these +transactions be sent? We have found that some choices are much better than +others. + +Consider the case in which each Dandelion transaction is forwarded to a +Dandelion destination selected uniformly at random. This approach results in a +fingerprint attack allowing network-level botnet adversaries to achieve total +deanonymization of the P2P network after observing less than ten transactions +per node. + +[[File:bip-dandelion/2-attack.png|framed|center|alt=An illustration of a fingerprint attack|Figure 2]] +Figure 2 + +During a fingerprint attack, a botnet-style adversary with knowledge of the +graph structure first simulates transaction propagation. This offline step lets +the adversary generate fingerprints for each network node. During the online +attack, the adversary collects transactions at its spy nodes and matches these +observations to the simulated fingerprints. Our simulations have shown that this +attack results in devastating, network-wide deanonymization. + +[[File:bip-dandelion/3-attack-plot.png|framed|center|alt=A plot illustrating total deanonymization|Figure 3]] +Figure 3 + +To avoid this issue, we suggest "per-inbound-edge" routing. Each inbound peer is +assigned a particular Dandelion destination. Each Dandelion transaction that +arrives via this peer is forwarded to the same Dandelion destination. +Per-inbound-edge routing breaks the described attack by blocking an adversary's +ability to construct useful fingerprints. Fingerprints arise when routing +decisions are made independently per transaction at each node. In this case, two +transactions from the same node generally take different paths through the +network. Crucially, this results in multiple, unique data points that are +aggregated to match with a fingerprint. + +Dandelion ensures that two transactions from the same node take the same network +path, limiting adversaries to the far-left of the graph in Figure 3. In other +words, adversary knowledge is limited to the case of one observed message rather +than a rich profile of multiple transaction paths. Dandelion also breaks the +symmetry of diffusion, making the source of the transaction difficult to infer. + +[[File:bip-dandelion/4-dandelion-plot.png|framed|center|alt=A plot illustrating limited deanonymization|Figure 4]] +Figure 4 + +After a transaction has traveled along a Dandelion stem for a random number of +hops, it transitions into the fluff phase of routing. The transaction is shared +with the network through the existing process of diffusion. In practice, this +fluff mechanism is enforced by a weighted coin flip at each node. If the random +value is below some threshold, the Dandelion transaction is transformed into a +typical transaction. In our testing, we have chosen a probability of ten percent +that a given Dandelion transaction enters fluff phase when leaving a given node. +This value strikes a good balance between stem path length and transaction +spreading latency. + +Note that Dandelion's expected precision guarantees are a population-level +metric, whereas the expected recall guarantees can be interpreted as an +individual-level metric. Expected recall is equivalent to the probability that +an adversary associates a single transaction with a given source. These +guarantees are probabilistic. They do not address scenarios in which a node has +been eclipsed by other nodes, or when a node is specifically targeted by an +ISP-like adversary. Individuals who are concerned about targeted deanonymization +should still use Tor. + +At a high level, Dandelion is like an "anonymity inoculation" for the public at +large - including users who are not aware of Bitcoin's privacy issues. Higher +adoption leads to greater benefits, even for users who do not use Tor. Early +adopters of Dandelion still receive privacy benefits. In the worst case when no +neighbors support Dandelion, transactions make at least one hop before +diffusing. Note that any solution based only on routing cannot be perfectly +anonymous due to the fundamental lower bounds on precision and recall shown in +the original Dandelion paper. Dandelion provides near-optimal anonymity +guarantees among such solutions. + +==Specification== + +Dandelion can be specified with a handful of features: Dandelion transaction +support, Dandelion routing data and logic, periodic Dandelion route shuffling, +memory pool logic, the fluff mechanism, transaction embargoes, and Dandelion +transaction logic. Specification details are summarized below. + +===Dandelion transaction support=== + +During the stem phase, transactions are "Dandelion transactions." When a +Dandelion transaction enters fluff phase, it becomes a typical Bitcoin +transaction. Dandelion transactions and typical transactions differ only in +their NetMsgType. + +Dandelion (stem phase) transactions MUST be differentiable from typical Bitcoin +transactions. + +===Dandelion routing data and logic=== + +Dandelion routing during the stem phase requires notions of inbound peers, +outbound peers, Dandelion destinations, and Dandelion routes. Inbound peers +consist of all currently connected peers that initiated the peer connection. +Outbound peers consist of all currently connected peers that were connected to +by this node. Dandelion destinations are a subset of outbound peers. The number +of Dandelion destinations is limited by the +DANDELION_MAX_DESTINATIONS parameter. In the reference +implementation, this parameter is set to two. Our tests have shown that this +value provides both privacy and robustness (see the reference paper for more +details on the parameter tradeoffs). Dandelion routes are a map of inbound peers +to Dandelion destinations. Every inbound peer is mapped to a Dandelion +destination. + +Note that a Dandelion node may choose a different +DANDELION_MAX_DESTINATIONS parameter without splitting from the +privacy graph. When mapping inbound connections to outbound connections for +Dandelion routes, we implement the following routing logic. First, select a set +of Dandelion destinations from the set of outbound peers. This set of Dandelion +destinations is of size less than or equal to +DANDELION_MAX_DESTINATIONS. For each inbound connection, first +identify the subset of Dandelion destinations with the least number of routes. +For example, some subset of Dandelion destinations may be affiliated with zero +routes while all other Dandelion destinations are affiliated with one or more +routes. From this subset, select one Dandelion destination uniformly at random. +Establish a Dandelion route from the inbound connection to this Dandelion +destination. + +For a given Dandelion routing epoch, two distinct Dandelion destinations SHOULD +be selected uniformly at random from the set of outbound connections. All +Dandelion transactions that arrive via a given inbound connection MUST be +transmitted to the same Dandelion destination. When choosing a Dandelion +destination for a given inbound connection, the destination MUST be selected +uniformly at random from the set of Dandelion destinations with the least number +of inbound connections mapped to them. + +===Periodic Dandelion route shuffling=== + +The map of Dandelion routes is cleared and reconstructed every ten minutes on +average. We have chosen the value of ten minutes heuristically in order to make +privacy graph learning difficult for adversaries. Note that a Dandelion node may +choose a different average shuffle time without splitting from the privacy +graph. + +Dandelion routes MUST be cleared and reconstructed at random intervals. +Dandelion routes SHOULD be cleared and reconstructed every ten minutes on +average. + +===Memory pool logic=== + +Dandelion transactions are segregated from typical transactions. The +mempool remains unchanged. Another instance of the +CTxMemPool class, called the stempool, is used for +Dandelion transactions. Information flows from mempool to +stempool in order to ensure proper transaction propagation. +Information does not flow from stempool to mempool, +except when a Dandelion transaction fluffs into a typical transaction. + +When a Dandelion transaction arrives, the transaction MUST be added to the +stempool and MUST NOT be added to the mempool. When a typical Bitcoin +transaction arrives, the transaction MUST be added to the mempool and MUST be +added to the stempool. When a Dandelion transaction fluffs, the transaction MUST +be added to the mempool. + +===The fluff mechanism=== + +When relaying a Dandelion transaction along a Dandelion route, there is a 10% +chance that the Dandelion transaction becomes a typical Bitcoin transaction and +is therefore relayed via diffusion. In our testing, this value strikes a good +balance between stem path length and transaction spreading latency. Note that a +Dandelion node may choose a different chance of fluffing without splitting from +the privacy graph. + +When a node prepares to transmit a Dandelion transaction, the node MUST flip a +biased coin. If the outcome is "Dandelion transaction," then the node MUST +transmit the transaction to the appropriate Dandelion destination. Otherwise, +the node MUST convert the Dandelion transaction into a typical Bitcoin +transaction. A Dandelion transaction SHOULD fluff into a typical Bitcoin +transaction with a 10% probability. + +===Transaction embargoes=== + +During the stem phase, transactions are relayed along a single path. If any node +in this path were to receive the Dandelion transaction and go offline, then the +transaction would cease to propagate. To increase robustness, every node that +forwards a Dandelion transaction initializes a timer at the time of reception. +If the Dandelion transaction does not appear in the memory pool by the time the +timer expires, then the transaction enters fluff phase and is forwarded via +diffusion. + +When a Dandelion transaction arrives, the node MUST set an embargo timer for a +random time in the future. If the Dandelion transaction arrives as a typical +Bitcoin transaction, the node MUST cancel the timer. If the timer expires before +the Dandelion transaction is observed as a typical Bitcoin transaction, then the +node MUST fluff the Dandelion transaction. + +===Dandelion transaction logic=== + +The following cases define a node's behavior when receiving network packets +referencing Dandelion transactions. +* Receive INV for Dandelion TX: If the peer is inbound and the Dandelion transaction has not been received from this peer, then reply with GETDATA. +* Receive GETDATA for Dandelion TX: If the peer is not inbound and the Dandelion transaction has been advertised to this peer, then reply with the Dandelion transaction. +* Receive Dandelion TX: If the peer is inbound, then relay the Dandelion TX to the appropriate Dandelion destination. + +==Implementation== + +A reference implementation is available at the following URL: +https://github.com/mablem8/bitcoin/tree/dandelion-feature-commits + +All features have been compressed into a single commit at the following URL: +https://github.com/mablem8/bitcoin/tree/dandelion + +==Compatibility== + +Dandelion does not conflict with existing versions of Bitcoin. A Bitcoin node +that supports Dandelion appears no differently to Bitcoin nodes running older +software versions. Bitcoin nodes that support Dandelion can identify feature +support through a probe message. Obviously, older nodes are not capable of +Dandelion routing. If a Bitcoin node supporting Dandelion has no peers that also +support Dandelion, then its behavior naturally decays to that of a Bitcoin node +without Dandelion support due to the Dandelion transaction embargoes. + +==Acknowledgements== + +We would like to thank the Bitcoin Core developers and Gregory Maxwell in +particular for their insightful comments, which helped to inform this +implementation and some of the follow-up work we conducted. We would also like +to thank the Mimblewimble development community for coining the term "stempool," +which we happily adopted for this implementation. + +==References== + +# An Analysis of Anonymity in Bitcoin Using P2P Network Traffic http://fc14.ifca.ai/papers/fc14_submission_71.pdf +# Deanonymisation of clients in Bitcoin P2P network https://arxiv.org/abs/1405.7418 +# Discovering Bitcoin’s Public Topology and Influential Nodes https://cs.umd.edu/projects/coinscope/coinscope.pdf +# (Sigmetrics 2017) Dandelion: Redesigning the Bitcoin Network for Anonymity https://arxiv.org/abs/1701.04439 +# (Sigmetrics 2018) Dandelion++: Lightweight Cryptocurrency Networking with Formal Anonymity Guarantees https://arxiv.org/pdf/1805.11060.pdf + +==Copyright== + +To the extent possible under law, the author(s) have dedicated all copyright and +related and neighboring rights to this work to the public domain worldwide. This +work is distributed without any warranty. + +You should have received a copy of the CC0 Public Domain Dedication with this +work. If not, see https://creativecommons.org/publicdomain/zero/1.0/ . diff --git a/bip-0156/1-dandelion.png b/bip-0156/1-dandelion.png new file mode 100644 index 0000000..d17e5ce Binary files /dev/null and b/bip-0156/1-dandelion.png differ diff --git a/bip-0156/2-attack.png b/bip-0156/2-attack.png new file mode 100644 index 0000000..c6165d1 Binary files /dev/null and b/bip-0156/2-attack.png differ diff --git a/bip-0156/3-attack-plot.png b/bip-0156/3-attack-plot.png new file mode 100644 index 0000000..8a35a86 Binary files /dev/null and b/bip-0156/3-attack-plot.png differ diff --git a/bip-0156/4-dandelion-plot.png b/bip-0156/4-dandelion-plot.png new file mode 100644 index 0000000..5fe2150 Binary files /dev/null and b/bip-0156/4-dandelion-plot.png differ diff --git a/bip-0156/bitcoin.conf b/bip-0156/bitcoin.conf new file mode 100644 index 0000000..e9e6581 --- /dev/null +++ b/bip-0156/bitcoin.conf @@ -0,0 +1,16 @@ +regtest=1 # Run this node on its own independent test network +debug=net # Enable network debug logs +debug=mempool # Enable mempool debug logs +debug=mempoolrej # Enable mempool rejection debug logs +debug=dandelion # Enable dandelion debug logs +logips=1 # Log IP addresses in debug output +logtimemicros=1 # Log timestamps with microsecond precision +printtoconsole=1 # Print debug logs to console instead of debug.log +server=1 # Accept command line JSON-RPC commands +rpcuser=xxx # Username for JSON-RPC connections +rpcpassword=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx +rpcauth=xxx:xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx +dns=0 # Do not allow DNS lookups for -addnode, -seednode, and -connect +dnsseed=0 # Do not query for peer addresses via DNS lookup +persistmempool=0 # Do not save mempool on shutdown to load on restart +dandelion=1 # Enable Dandelion transactions diff --git a/bip-0156/dandelion-debug-logs-example.pdf b/bip-0156/dandelion-debug-logs-example.pdf new file mode 100644 index 0000000..4f4180e Binary files /dev/null and b/bip-0156/dandelion-debug-logs-example.pdf differ diff --git a/bip-0156/dandelion-reference-documentation.pdf b/bip-0156/dandelion-reference-documentation.pdf new file mode 100644 index 0000000..aee33f1 Binary files /dev/null and b/bip-0156/dandelion-reference-documentation.pdf differ diff --git a/bip-dandelion.mediawiki b/bip-dandelion.mediawiki deleted file mode 100644 index 3ecdfbb..0000000 --- a/bip-dandelion.mediawiki +++ /dev/null @@ -1,321 +0,0 @@ -
-  BIP: 156
-  Layer: Peer Services
-  Title: Dandelion - Privacy Enhancing Routing
-  Author: Brad Denby 
-          Andrew Miller 
-          Giulia Fanti 
-          Surya Bakshi 
-          Shaileshh Bojja Venkatakrishnan 
-          Pramod Viswanath 
-  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0156
-  Status: Draft
-  Type: Standards Track
-  Created: 2017-06-09
-  License: CC0-1.0
-
- -==Abstract== - -Bitcoin's transaction spreading protocol is vulnerable to deanonymization -attacks. Dandelion is a transaction routing mechanism that provides formal -anonymity guarantees against these attacks. When a node generates a transaction -without Dandelion, it transmits that transaction to its peers with independent, -exponential delays. This approach, known as diffusion in academia, allows -network adversaries to link transactions to IP addresses. - -Dandelion mitigates this class of attacks by sending transactions over a -randomly selected path before diffusion. Transactions travel along this path -during the "stem phase" and are then diffused during the "fluff phase" (hence -Dandelion). We have shown that this routing protocol provides near-optimal -anonymity guarantees among schemes that do not introduce additional encryption -mechanisms. - -==Motivation== - -Transaction diffusion in Bitcoin is vulnerable to deanonymization attacks. -Because transactions are sent to peers with independent, exponential delays, -messages spread through the network in a statistically symmetric manner. This -pattern allows colluding spy nodes to infer the transaction source. Breaking -this symmetry prevents the attack. However, we have shown that an adversary with -knowledge of the network topology can launch a much more effective "fingerprint" -attack if the symmetry breaking is not done properly. - -Consider a botnet-style adversary with access to the P2P graph. Botnets of size -comparable to the Bitcoin P2P network are common and cheap, and these -adversaries can learn the network structure with probe messages. We have shown -that such an adversary can achieve total deanonymization of the entire network -after observing less than ten transactions per node. - -Dandelion is a practical, lightweight privacy solution that provides the Bitcoin -network formal anonymity guarantees. While other privacy solutions aim to -protect individual users, Dandelion protects anonymity by limiting the -capability of adversaries to deanonymize the entire network. - -==How Dandelion Works== - -Dandelion enhances user privacy by sending transactions through an anonymity -phase before diffusing them throughout the network. At a high level, Dandelion -enhances privacy by (i) breaking the symmetry of diffusion and (ii) mixing -transactions by forwarding messages from different sources along the same path. - -Dandelion routing can be conceptualized in three phases. First, a privacy graph -is constructed. In practice, this privacy graph is constructed in a fully -decentralized manner and is a subgraph of the existing Bitcoin P2P network. -Next, transactions are forwarded along this privacy graph during the "stem -phase." Finally, messages are broadcast to the network during the "fluff phase" -using the typical method of diffusion. - -[[File:bip-dandelion/1-dandelion.png|framed|center|alt=An illustration of Dandelion routing|Figure 1]] -Figure 1 - -In order to select the privacy graph in a decentralized manner, each node -selects a subset of its outbound peers to be Dandelion destinations. Dandelion -transactions (transactions in their stem phase) that arrive at this node via -inbound connections are forwarded to these Dandelion destinations. - -In an ideal setting, we have found that a Hamiltonian circuit provides -near-optimal privacy guarantees. However, constructing a Hamiltonian circuit -through the Bitcoin P2P network in a decentralized, trustless manner is not -feasible. Thus, we recommend that each node select two Dandelion destinations -uniformly at random without replacement from its list of outbound peers. Our -tests have shown that this method provides comparable privacy with increased -robustness. - -During stem phase routing, there is a question of how to route messages in order -to protect privacy. For example, if two Dandelion transactions arrive at a node -from different inbound peers, to which Dandelion destination(s) should these -transactions be sent? We have found that some choices are much better than -others. - -Consider the case in which each Dandelion transaction is forwarded to a -Dandelion destination selected uniformly at random. This approach results in a -fingerprint attack allowing network-level botnet adversaries to achieve total -deanonymization of the P2P network after observing less than ten transactions -per node. - -[[File:bip-dandelion/2-attack.png|framed|center|alt=An illustration of a fingerprint attack|Figure 2]] -Figure 2 - -During a fingerprint attack, a botnet-style adversary with knowledge of the -graph structure first simulates transaction propagation. This offline step lets -the adversary generate fingerprints for each network node. During the online -attack, the adversary collects transactions at its spy nodes and matches these -observations to the simulated fingerprints. Our simulations have shown that this -attack results in devastating, network-wide deanonymization. - -[[File:bip-dandelion/3-attack-plot.png|framed|center|alt=A plot illustrating total deanonymization|Figure 3]] -Figure 3 - -To avoid this issue, we suggest "per-inbound-edge" routing. Each inbound peer is -assigned a particular Dandelion destination. Each Dandelion transaction that -arrives via this peer is forwarded to the same Dandelion destination. -Per-inbound-edge routing breaks the described attack by blocking an adversary's -ability to construct useful fingerprints. Fingerprints arise when routing -decisions are made independently per transaction at each node. In this case, two -transactions from the same node generally take different paths through the -network. Crucially, this results in multiple, unique data points that are -aggregated to match with a fingerprint. - -Dandelion ensures that two transactions from the same node take the same network -path, limiting adversaries to the far-left of the graph in Figure 3. In other -words, adversary knowledge is limited to the case of one observed message rather -than a rich profile of multiple transaction paths. Dandelion also breaks the -symmetry of diffusion, making the source of the transaction difficult to infer. - -[[File:bip-dandelion/4-dandelion-plot.png|framed|center|alt=A plot illustrating limited deanonymization|Figure 4]] -Figure 4 - -After a transaction has traveled along a Dandelion stem for a random number of -hops, it transitions into the fluff phase of routing. The transaction is shared -with the network through the existing process of diffusion. In practice, this -fluff mechanism is enforced by a weighted coin flip at each node. If the random -value is below some threshold, the Dandelion transaction is transformed into a -typical transaction. In our testing, we have chosen a probability of ten percent -that a given Dandelion transaction enters fluff phase when leaving a given node. -This value strikes a good balance between stem path length and transaction -spreading latency. - -Note that Dandelion's expected precision guarantees are a population-level -metric, whereas the expected recall guarantees can be interpreted as an -individual-level metric. Expected recall is equivalent to the probability that -an adversary associates a single transaction with a given source. These -guarantees are probabilistic. They do not address scenarios in which a node has -been eclipsed by other nodes, or when a node is specifically targeted by an -ISP-like adversary. Individuals who are concerned about targeted deanonymization -should still use Tor. - -At a high level, Dandelion is like an "anonymity inoculation" for the public at -large - including users who are not aware of Bitcoin's privacy issues. Higher -adoption leads to greater benefits, even for users who do not use Tor. Early -adopters of Dandelion still receive privacy benefits. In the worst case when no -neighbors support Dandelion, transactions make at least one hop before -diffusing. Note that any solution based only on routing cannot be perfectly -anonymous due to the fundamental lower bounds on precision and recall shown in -the original Dandelion paper. Dandelion provides near-optimal anonymity -guarantees among such solutions. - -==Specification== - -Dandelion can be specified with a handful of features: Dandelion transaction -support, Dandelion routing data and logic, periodic Dandelion route shuffling, -memory pool logic, the fluff mechanism, transaction embargoes, and Dandelion -transaction logic. Specification details are summarized below. - -===Dandelion transaction support=== - -During the stem phase, transactions are "Dandelion transactions." When a -Dandelion transaction enters fluff phase, it becomes a typical Bitcoin -transaction. Dandelion transactions and typical transactions differ only in -their NetMsgType. - -Dandelion (stem phase) transactions MUST be differentiable from typical Bitcoin -transactions. - -===Dandelion routing data and logic=== - -Dandelion routing during the stem phase requires notions of inbound peers, -outbound peers, Dandelion destinations, and Dandelion routes. Inbound peers -consist of all currently connected peers that initiated the peer connection. -Outbound peers consist of all currently connected peers that were connected to -by this node. Dandelion destinations are a subset of outbound peers. The number -of Dandelion destinations is limited by the -DANDELION_MAX_DESTINATIONS parameter. In the reference -implementation, this parameter is set to two. Our tests have shown that this -value provides both privacy and robustness (see the reference paper for more -details on the parameter tradeoffs). Dandelion routes are a map of inbound peers -to Dandelion destinations. Every inbound peer is mapped to a Dandelion -destination. - -Note that a Dandelion node may choose a different -DANDELION_MAX_DESTINATIONS parameter without splitting from the -privacy graph. When mapping inbound connections to outbound connections for -Dandelion routes, we implement the following routing logic. First, select a set -of Dandelion destinations from the set of outbound peers. This set of Dandelion -destinations is of size less than or equal to -DANDELION_MAX_DESTINATIONS. For each inbound connection, first -identify the subset of Dandelion destinations with the least number of routes. -For example, some subset of Dandelion destinations may be affiliated with zero -routes while all other Dandelion destinations are affiliated with one or more -routes. From this subset, select one Dandelion destination uniformly at random. -Establish a Dandelion route from the inbound connection to this Dandelion -destination. - -For a given Dandelion routing epoch, two distinct Dandelion destinations SHOULD -be selected uniformly at random from the set of outbound connections. All -Dandelion transactions that arrive via a given inbound connection MUST be -transmitted to the same Dandelion destination. When choosing a Dandelion -destination for a given inbound connection, the destination MUST be selected -uniformly at random from the set of Dandelion destinations with the least number -of inbound connections mapped to them. - -===Periodic Dandelion route shuffling=== - -The map of Dandelion routes is cleared and reconstructed every ten minutes on -average. We have chosen the value of ten minutes heuristically in order to make -privacy graph learning difficult for adversaries. Note that a Dandelion node may -choose a different average shuffle time without splitting from the privacy -graph. - -Dandelion routes MUST be cleared and reconstructed at random intervals. -Dandelion routes SHOULD be cleared and reconstructed every ten minutes on -average. - -===Memory pool logic=== - -Dandelion transactions are segregated from typical transactions. The -mempool remains unchanged. Another instance of the -CTxMemPool class, called the stempool, is used for -Dandelion transactions. Information flows from mempool to -stempool in order to ensure proper transaction propagation. -Information does not flow from stempool to mempool, -except when a Dandelion transaction fluffs into a typical transaction. - -When a Dandelion transaction arrives, the transaction MUST be added to the -stempool and MUST NOT be added to the mempool. When a typical Bitcoin -transaction arrives, the transaction MUST be added to the mempool and MUST be -added to the stempool. When a Dandelion transaction fluffs, the transaction MUST -be added to the mempool. - -===The fluff mechanism=== - -When relaying a Dandelion transaction along a Dandelion route, there is a 10% -chance that the Dandelion transaction becomes a typical Bitcoin transaction and -is therefore relayed via diffusion. In our testing, this value strikes a good -balance between stem path length and transaction spreading latency. Note that a -Dandelion node may choose a different chance of fluffing without splitting from -the privacy graph. - -When a node prepares to transmit a Dandelion transaction, the node MUST flip a -biased coin. If the outcome is "Dandelion transaction," then the node MUST -transmit the transaction to the appropriate Dandelion destination. Otherwise, -the node MUST convert the Dandelion transaction into a typical Bitcoin -transaction. A Dandelion transaction SHOULD fluff into a typical Bitcoin -transaction with a 10% probability. - -===Transaction embargoes=== - -During the stem phase, transactions are relayed along a single path. If any node -in this path were to receive the Dandelion transaction and go offline, then the -transaction would cease to propagate. To increase robustness, every node that -forwards a Dandelion transaction initializes a timer at the time of reception. -If the Dandelion transaction does not appear in the memory pool by the time the -timer expires, then the transaction enters fluff phase and is forwarded via -diffusion. - -When a Dandelion transaction arrives, the node MUST set an embargo timer for a -random time in the future. If the Dandelion transaction arrives as a typical -Bitcoin transaction, the node MUST cancel the timer. If the timer expires before -the Dandelion transaction is observed as a typical Bitcoin transaction, then the -node MUST fluff the Dandelion transaction. - -===Dandelion transaction logic=== - -The following cases define a node's behavior when receiving network packets -referencing Dandelion transactions. -* Receive INV for Dandelion TX: If the peer is inbound and the Dandelion transaction has not been received from this peer, then reply with GETDATA. -* Receive GETDATA for Dandelion TX: If the peer is not inbound and the Dandelion transaction has been advertised to this peer, then reply with the Dandelion transaction. -* Receive Dandelion TX: If the peer is inbound, then relay the Dandelion TX to the appropriate Dandelion destination. - -==Implementation== - -A reference implementation is available at the following URL: -https://github.com/mablem8/bitcoin/tree/dandelion-feature-commits - -All features have been compressed into a single commit at the following URL: -https://github.com/mablem8/bitcoin/tree/dandelion - -==Compatibility== - -Dandelion does not conflict with existing versions of Bitcoin. A Bitcoin node -that supports Dandelion appears no differently to Bitcoin nodes running older -software versions. Bitcoin nodes that support Dandelion can identify feature -support through a probe message. Obviously, older nodes are not capable of -Dandelion routing. If a Bitcoin node supporting Dandelion has no peers that also -support Dandelion, then its behavior naturally decays to that of a Bitcoin node -without Dandelion support due to the Dandelion transaction embargoes. - -==Acknowledgements== - -We would like to thank the Bitcoin Core developers and Gregory Maxwell in -particular for their insightful comments, which helped to inform this -implementation and some of the follow-up work we conducted. We would also like -to thank the Mimblewimble development community for coining the term "stempool," -which we happily adopted for this implementation. - -==References== - -# An Analysis of Anonymity in Bitcoin Using P2P Network Traffic http://fc14.ifca.ai/papers/fc14_submission_71.pdf -# Deanonymisation of clients in Bitcoin P2P network https://arxiv.org/abs/1405.7418 -# Discovering Bitcoin’s Public Topology and Influential Nodes https://cs.umd.edu/projects/coinscope/coinscope.pdf -# (Sigmetrics 2017) Dandelion: Redesigning the Bitcoin Network for Anonymity https://arxiv.org/abs/1701.04439 -# (Sigmetrics 2018) Dandelion++: Lightweight Cryptocurrency Networking with Formal Anonymity Guarantees https://arxiv.org/pdf/1805.11060.pdf - -==Copyright== - -To the extent possible under law, the author(s) have dedicated all copyright and -related and neighboring rights to this work to the public domain worldwide. This -work is distributed without any warranty. - -You should have received a copy of the CC0 Public Domain Dedication with this -work. If not, see https://creativecommons.org/publicdomain/zero/1.0/ . diff --git a/bip-dandelion/1-dandelion.png b/bip-dandelion/1-dandelion.png deleted file mode 100644 index d17e5ce..0000000 Binary files a/bip-dandelion/1-dandelion.png and /dev/null differ diff --git a/bip-dandelion/2-attack.png b/bip-dandelion/2-attack.png deleted file mode 100644 index c6165d1..0000000 Binary files a/bip-dandelion/2-attack.png and /dev/null differ diff --git a/bip-dandelion/3-attack-plot.png b/bip-dandelion/3-attack-plot.png deleted file mode 100644 index 8a35a86..0000000 Binary files a/bip-dandelion/3-attack-plot.png and /dev/null differ diff --git a/bip-dandelion/4-dandelion-plot.png b/bip-dandelion/4-dandelion-plot.png deleted file mode 100644 index 5fe2150..0000000 Binary files a/bip-dandelion/4-dandelion-plot.png and /dev/null differ diff --git a/bip-dandelion/bitcoin.conf b/bip-dandelion/bitcoin.conf deleted file mode 100644 index e9e6581..0000000 --- a/bip-dandelion/bitcoin.conf +++ /dev/null @@ -1,16 +0,0 @@ -regtest=1 # Run this node on its own independent test network -debug=net # Enable network debug logs -debug=mempool # Enable mempool debug logs -debug=mempoolrej # Enable mempool rejection debug logs -debug=dandelion # Enable dandelion debug logs -logips=1 # Log IP addresses in debug output -logtimemicros=1 # Log timestamps with microsecond precision -printtoconsole=1 # Print debug logs to console instead of debug.log -server=1 # Accept command line JSON-RPC commands -rpcuser=xxx # Username for JSON-RPC connections -rpcpassword=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx -rpcauth=xxx:xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx -dns=0 # Do not allow DNS lookups for -addnode, -seednode, and -connect -dnsseed=0 # Do not query for peer addresses via DNS lookup -persistmempool=0 # Do not save mempool on shutdown to load on restart -dandelion=1 # Enable Dandelion transactions diff --git a/bip-dandelion/dandelion-debug-logs-example.pdf b/bip-dandelion/dandelion-debug-logs-example.pdf deleted file mode 100644 index 4f4180e..0000000 Binary files a/bip-dandelion/dandelion-debug-logs-example.pdf and /dev/null differ diff --git a/bip-dandelion/dandelion-reference-documentation.pdf b/bip-dandelion/dandelion-reference-documentation.pdf deleted file mode 100644 index aee33f1..0000000 Binary files a/bip-dandelion/dandelion-reference-documentation.pdf and /dev/null differ -- cgit v1.2.3 From b2c3359bffa6254f5b8df12a06d18b3159693763 Mon Sep 17 00:00:00 2001 From: Giulia Fanti Date: Mon, 13 Aug 2018 22:29:14 -0400 Subject: fixed typo --- README.mediawiki | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/README.mediawiki b/README.mediawiki index 0f36f9f..9f016bb 100644 --- a/README.mediawiki +++ b/README.mediawiki @@ -739,7 +739,7 @@ Those proposing changes should consider that ultimately consent may rest with th | [[bip-0156.mediawiki|156]] | Peer Services | Dandelion - Privacy Enhancing Routing -| Bradley Denby, Andrew Miller, Giulia Fanti, Surya Bakshi, Shaileshh Bojja Venkatakrishnan, Pramod Viswanath +| Brad Denby, Andrew Miller, Giulia Fanti, Surya Bakshi, Shaileshh Bojja Venkatakrishnan, Pramod Viswanath | Standard | Draft |- -- cgit v1.2.3