Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Naumenko, Hlib
Master of Science - MSc
University of British Columbia
Bitcoin is a top-ranked cryptocurrency that has experienced huge growth and survived numerous attacks. The protocols making up Bitcoin must therefore accommodate the growth of the network and ensure security. However, Bitcoin’s transaction dissemination protocol has mostly evaded optimization. This protocol is based on flooding and though it is secure and fault-tolerant, it is also highly inefficient. Specifically, our measurements indicate that 43% of the traffic generated by transaction dissemination in the Bitcoin network is redundant. In this paper we introduce a new transaction dissemination protocol called Erlay. Erlay is a hybrid protocol that combines limited flooding with intermittent reconciliation. We evaluated Erlay in simulation and by implementing and deploying it at scale. Compared to Bitcoin’s current protocols, Erlay reduces the bandwidth used to announce transactions by 84% without significantly affecting privacy or propagation speed. In addition, Erlay retains the existing Bitcoin security guarantees and is more scalable relative to the number of nodes in the network and their connectivity. Erlay is currently being investigated by the Bitcoin community for future use with the Bitcoin protocol.
Erlay: Efficient Transaction Relay in BitcoinbyHlib NaumenkoBachelor in Software Engineering, Kharkiv National University of RadioElectronics, 2017A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORALSTUDIES(Computer Science)The University of British Columbia(Vancouver)April 2019c© Hlib Naumenko, 2019The following individuals certify that they have read, and recommend to the Fac-ulty of Graduate and Postdoctoral Studies for acceptance, the thesis entitled:Erlay: Efficient Transaction Relay in Bitcoinsubmitted by Hlib Naumenko in partial fulfillment of the requirements for thedegree of Master of Science in Computer Science.Examining Committee:Ivan Beschastnikh, Computer ScienceCo-supervisorAlexandra Fedorova, Electrical and Computer EngineeringCo-supervisorNorm Hutchinson, Computer ScienceSupervisory Committee MemberiiAbstractBitcoin is a top-ranked cryptocurrency that has experienced huge growth and sur-vived numerous attacks. The protocols making up Bitcoin must therefore accom-modate the growth of the network and ensure security. However, Bitcoin’s trans-action dissemination protocol has mostly evaded optimization. This protocol isbased on flooding and though it is secure and fault-tolerant, it is also highly ineffi-cient. Specifically, our measurements indicate that 43% of the traffic generated bytransaction dissemination in the Bitcoin network is redundant.In this thesis we introduce a new transaction dissemination protocol called Er-lay. Erlay is a hybrid protocol that combines limited flooding with intermittent rec-onciliation. We evaluated Erlay in simulation and by implementing and deployingit at scale. Compared to Bitcoin’s current protocols, Erlay reduces the bandwidthused to announce transactions by 84% without significantly affecting privacy orpropagation speed. In addition, Erlay retains the existing Bitcoin security guaran-tees and is more scalable relative to the number of nodes in the network and theirconnectivity. Erlay is currently being investigated by the Bitcoin community forfuture use with the Bitcoin protocol.iiiLay SummaryBitcoin is a peer-to-peer electronic cash system, which operates over computers(nodes) running Bitcoin software across the world. Those nodes exchange mes-sages, which represent transactions (transfers of funds) as well as additional infor-mation.In currently deployed software, Bitcoin transactions are relayed across all nodesvia flooding, where every node notifies all its peers of a new transaction. Whilethis approach is robust and has fast transaction relay, it is inefficient in terms ofconsumed bandwidth, because every node learns about every transaction multipletimes.We design Erlay, a transaction relay protocol, which is more efficient thanflooding. Erlay is a combination of rapid low-fanout flooding and efficient setreconciliation. We design and evaluate Erlay, and show that it outperforms the cur-rent protocol and may enable better security and privacy of Bitcoin transactions inthe future.ivPrefaceAll of the work presented henceforth was conducted in the NSS (Networks, Sys-tems and Security) lab in the Department of Computer Science at the University ofBritish Columbia, Point Grey campus.The work presented in this thesis is original, unpublished work by the author,Hlib Naumenko. This work was performed in collaboration with Gregory Maxwelland Pieter Wuille. The entirety of this work was designed and written in assistancewith Dr. Ivan Beschastnikh and Dr. Alexandra Fedorova, who supervised thisprojects.The design of the Erlay protocol, simulator and reference implementation wereperformed by the author. Gregory Maxwell is the author of the idea of mempoolreconciliation, which pre-dated Erlay. Pieter Wuille is the main contributor (alongwith Gregory Maxwell and the author) of MiniSketch 1, an underlying library de-veloped for Erlay. Both Gregory Maxwell and Pieter Wuille contributed to thediscussions around implementation details of Erlay.1https://github.com/sipa/minisketchvTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixGlossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 The problem with flooding transactions . . . . . . . . . . . . . . . . 74 Protocol requirements . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Erlay design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135.0.1 Low fanout flooding . . . . . . . . . . . . . . . . . . . . 145.0.2 Set reconciliation . . . . . . . . . . . . . . . . . . . . . . 15vi6 Implementation details . . . . . . . . . . . . . . . . . . . . . . . . . 217 Evaluation methodology . . . . . . . . . . . . . . . . . . . . . . . . . 248 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268.0.1 Relay bandwidth usage . . . . . . . . . . . . . . . . . . . 268.0.2 Relay latency . . . . . . . . . . . . . . . . . . . . . . . . 289 Reference implementation results . . . . . . . . . . . . . . . . . . . 3210 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3411 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3512 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38viiList of TablesTable 8.1 The average bandwidth cost of relaying one transaction to onenode in the Bitcoin network with BTCFlood and Erlay. b is theannouncement size in bits. . . . . . . . . . . . . . . . . . . . 27Table 8.2 Breakdown of bandwidth usage in Erlay. . . . . . . . . . . . . 28Table 9.1 Prototype measurements collected from a 100-node deploymentcomparing the latency and bandwidth of the BTCFlood in thereference implementation against our Erlay implementation. . 33viiiList of FiguresFigure 1.1 Lifecycle of a Bitcoin transaction. In this thesis we optimizethe protocols for relaying transactions between nodes in theBitcoin network (grey box). . . . . . . . . . . . . . . . . . . 2Figure 2.1 Private and public nodes in the Bitcoin network. . . . . . . . . 5Figure 2.2 Transaction exchange between two peers. . . . . . . . . . . . 5Figure 3.1 Analytical cost of relaying one transaction across the networkof 60,000 nodes. . . . . . . . . . . . . . . . . . . . . . . . . 9Figure 4.1 Erlay disseminates transactions using low-fanout flooding asthe first step, and then several rounds of reconciliation to reachall nodes in the network. . . . . . . . . . . . . . . . . . . . . 12Figure 5.1 Comparison of reconciliation, flooding, and Erlay in their band-width usage and latency to reach all nodes. . . . . . . . . . . 14Figure 5.2 Reconciliation protocol with correct difference estimation (Reconcile-Init, followed by DiffExchange). And, reconciliation proto-col with incorrect difference estimation (Reconcile-Init, fol-lowed by Reconcile-Bisec). In case reconciliation fails duringReconcile-Bisec, reconciliation falls back to Bitcoin’s currentexchange method (see Fig. 2.2). . . . . . . . . . . . . . . . . 18Figure 5.3 Bisection is enabled by the linearity of sketches . . . . . . . . 20ixFigure 6.1 The decode time of our library (PinSketch) as compared toCPISync for varying set difference sizes. . . . . . . . . . . . 22Figure 8.1 Average bandwidth cost of relaying a transaction in a networkof 60,000 nodes with outbound connectivity of 8. . . . . . . . 27Figure 8.2 Finite state machine of the protocol in Fig. 2.2 annotated withtransition percentages observed in our experiments. . . . . . . 29Figure 8.3 Distribution of the set difference estimates during reconcilia-tion for different transaction rates. . . . . . . . . . . . . . . . 30Figure 8.4 Average latency for a single transaction to reach 100% nodesin the network. . . . . . . . . . . . . . . . . . . . . . . . . . 31xGlossaryBTC BitcoinDHT distributed hash tableDOS denial of serviceLOC lines of codeP2P peer-to-peerxiAcknowledgmentsThis research was funded by a grant from the Natural Science and EngineeringResearch Council of Canada (NSERC) Discovery Grant.Firstly, I would like to thank Ivan Beschastnikh for supervising me along thisjourney, providing insights on conducting research and allowing me to freely choosemy research direction. I would like to thank Alexandra Fedorova for joining ourwork as a co-supervisor and contributing while going through a critical personalmission in her life.I would also like to thank Blockstream for providing me with an opportunity ofan internship, where I was able to expand my research, and, even more importantly,to obtain experience in Bitcoin Core contributions. I am also grateful to themfor supporting my work after the end of my internship and expensing my trips toconferences.I would also like to thank the Bitcoin community for warm welcoming, interestin my work and useful feedback.xiiChapter 1IntroductionBitcoin is a peer-to-peer (P2P) trustless electronic cash system [47]. Recent es-timates indicate that there are just over 60,000 nodes in the Bitcoin network1.And, to keep up with the growth in the number of nodes and usage of the net-work, the system must be continually optimized while retaining the security guar-antees that its users have come to expect. For example, prior work has consid-ered optimizations to Proof-of-Work [7, 61], moving payments off-chain [53], im-proving transaction throughput by increasing the block size [5, 26, 60], as wellas optimizing block relay [13, 34, 51] and transaction representation within ablock [37]. One reason why optimizing Bitcoin is challenging is because secu-rity is not just a theoretical concern: a wide variety of attacks have been pub-lished [6, 8, 9, 14, 17, 18, 20, 27, 30, 33, 35, 39, 42–44, 48, 50] and the Bitcoinsoftware is being updated to protect against these. Therefore, any modification tothe system must carefully consider the security implications of the change.One bottleneck in the Bitcoin network that has not received much attention isthe cost of transaction relay. A Bitcoin transaction corresponds to a transfer offunds between several accounts. Fig. 1.1 overviews the lifecycle of a transaction inthe Bitcoin network. To be accepted by the network of nodes, a transaction must befirst disseminated, or relayed, throughout the network. Then it must be validatedand included into a block with other valid transactions. Finally, the block contain-ing the transaction must be relayed to all the nodes. Every Bitcoin transaction must1https://luke.dashjr.org/programs/bitcoin/files/charts/software.html1n more blocks mined that follow block Btx createdand signedtx relayedto other nodestx validatedby other nodestx includedin a mined block Bblock B relayedand validatedtx confirmedFigure 1.1: Lifecycle of a Bitcoin transaction. In this thesis we optimize theprotocols for relaying transactions between nodes in the Bitcoin net-work (grey box).reach almost all nodes in the network, and prior work has demonstrated that fullcoverage of the network is important for it to preserve security [57].Today, Bitcoin relays transactions using a protocol based on flooding: everymessage received by a node is transmitted to all of its neighbors. Flooding hashigh fault-tolerance since no single point of failure will halt relay, and it has lowlatency since nodes learn about transactions as fast as possible [38].However, flooding has poor bandwidth efficiency: every node in the networklearns about the transaction multiple times. Our empirical measurements demon-strate that transaction announcements account for 30–50% of the overall Bitcointraffic. This inefficiency is an important scalability limitation: the inefficiency in-creases as the network becomes more connected, while connectivity of the networkis desirable to the growth and the security of the network.Prior work has explored two principal approaches to this bandwidth ineffi-ciency. The first is the use of short transaction identifiers (to decrease messagesize) [32]. The second is to exclusively use blocks and never transmit individualtransactions [40]. Both approaches are inadequate: short identifiers only reduce theconstant factor and do not scale with the connectivity of the network, while usingonly blocks will create spikes in block relay and transaction validation. We discussthese approaches further in Section 11.The contribution of this thesis is Erlay, a new protocol that we designed tooptimize Bitcoin’s transaction relay while maintaining the existing security guar-antees. The main idea behind our protocol is to reduce the amount of information2propagated via flooding and instead use an efficient set reconciliation method [45]for most of the transaction dissemination. In addition we design this protocol towithstand DoS, timing, and other attacks.We implemented Erlay in a simulator as well as part of the mainline Bitcoinnode software and evaluated Erlay at scale. Our results show that Erlay makesannouncement-related bandwidth negligent while introducing a 50% latency in-crease.In summary, this thesis makes the following contributions:• We analyze bandwidth inefficiency of Bitcoin’s transaction relay protocol.We do this by running a node connected to the Bitcoin network as well asby running a simulation of the Bitcoin network. Our results demonstrate that88% of the bandwidth used to announce transactions (and around 40% of theoverall bandwidth) are redundant.• We propose a new, bandwidth-efficient, transaction relay protocol for Bitcoincalled Erlay, which is a combination of fast low-fanout flooding and efficientset reconciliation, designed to work under the assumptions of the Bitcoinnetwork.• We demonstrate that the protocol achieves a close to optimal combination ofresource consumption and propagation delay, and is robust to attacks. Erlayreduces the bandwidth used to relay transactions by 48% immediately, andallows the Bitcoin network to achieve higher connectivity to improve thesecurity of the network.3Chapter 2BackgroundThere are 2 types of nodes in the Bitcoin network: private nodes that do notaccept inbound connections and public nodes that do accept inbound connections(see Fig. 2.1). Public nodes act as a backbone of the network: they help new nodesbootstrap onto the network. If a person does not want to contribute resources (e.g.,bandwidth) to the network, then they run a private node, which only connects to theexisting public nodes. Once they joined the network, public and private nodes areindistinguishable in their operation: both perform transaction and block validationand relay valid transactions and blocks to their peers.The current version of the Bitcoin transaction relay protocol propagates mes-sages among nodes using diffusion [1], which is a variation on random flooding.Flooding is a protocol where each node announces every transaction it receivesto each of its peers. Announcements can be sent on either inbound and outboundlinks. With diffusion a peer injects a random delay before announcing a receivedtransaction to its peers. This mitigates timing attacks [50] and significantly reducesthe probability of in-flight collisions (when 2 nodes simultaneously announce thesame transaction over the link between them).The protocol by which a transaction propagates between two peers is illustratedin Fig. 2.2. When a Bitcoin node receives a transaction (peer 1 in Fig. 2.2), it ad-vertises the transaction to all of its peers except to the node that sent the transactionin the first place. To advertise a transaction, a node sends a hash of the transac-tion within an inventory, or INV message. If a node (peer 2 in Fig. 2.2) hears4…Private nodes [Max inbound: 0, Max outbound: 8]…Public nodes [Max inbound: 125, Max outbound: 8]Figure 2.1: Private and public nodes in the Bitcoin network.Peer 2Peer 1INVhash(tx)GETDATAhash(tx)txtx valida+ontxFigure 2.2: Transaction exchange between two peers.about a transaction for the first time, it will request the full transaction by sendinga GETDATA message to the node that sent it the INV message.We refer to the transaction-advertising portion of the protocol (all the INV mes-sages) as BTCFlood. Since it relies on flooding, most transactions are advertisedthrough each link in the network in one direction (except those that are advertisedduring the block relay phase). As a result, a node with n connections will send and5receive between n and 2n INV messages for a single transaction (two nodes mayannounce the same transaction simultaneously to each other).Both public and private nodes limit the number of inbound and outbound con-nections (Fig. 2.1). By default a private node has no inbound connections and upto 8 outbound connections, while a public node can have 8 outbound connectionsas well as up to 125 inbound connections (but the limit can be configured up toaround 1,000). Thus, as the Bitcoin network grows, the bandwidth and computa-tional requirements to run a public node quickly increase. This is because privatenodes connect to multiple public nodes to ensure that they are connected to thenetwork through more than a single peer.As a result, Bitcoin designers have focused on (1) making the running of apublic node more accessible, in terms of required bandwidth, computational power,and hardware resources; and, (2) making public nodes more efficient so that theycan accept more connections from private nodes. Our work targets both objectives.6Chapter 3The problem with floodingtransactionsFlooding is inefficient. BTCFlood sends many redundant transaction announce-ments. To see why, let us first consider how many announcements would be sentif the protocol were efficient. Since, optimally, each node would receive each an-nouncement exactly once, the number of times each announcement is sent shouldbe equal to the number of nodes.Next, let us consider how many times an announcement is sent with BTCFlood.By definition, each node relays an announcement on each of the links except theone where that announceent originally arrived. In other words, each link sees eachannouncement once, if no two nodes ever send the same announcement to eachother simultaneously, and more than once if they do. Therefore, in BTCFlood eachannouncement is sent at least as many times as the number of links.If N is the number of nodes in the Bitcoin network, the number of links is 8N,because each node must make eight outbound connections. Therefore, the numberof redundant announcements is at least 8N−N = 7N. Each announcement takes32 bytes out of 300 total bytes needed to relay a single transaction to one node.(These 300 bytes include the announcement, the response and the full transactionbody). Therefore, if at least seven out of eight announcements are redundant (cor-responding to 224 bytes), at least 43% of all announcement traffic is wasteful.We validated this analysis experimentally. We configured a public Bitcoin node7with eight outbound connections and ran it for one week. During this time, ournode also received four inbound connections. We measured the bandwidth dedi-cated to transaction announcements and other transaction dissemination traffic. Areceived announcement was considered redundant if it corresponded to an alreadyknown transaction. A sent announcement was considered redundant if it was notfollowed by a transaction request. According to our measurements 10% of the traf-fic corresponding to received announcements and 95% of the traffic correspondingto the sent announcements was redundant. Overall, 55% of all traffic used by ournode was redundant.Higher connectivity requires more bandwidth. Given that the amount of redun-dant traffic is proportional to the number of links, increasing the connectivity ofthe network (the number of outbound links per node) linearly increases bandwidthconsumption in BTCFlood.We modeled how the bandwidth consumption of disseminating one transactionacross the network of 60K nodes increases with connectivity. Fig. 3.1 (whose re-sults we confirmed via simulation) shows that announcement traffic turns dominantas the network becomes more connected.Higher connectivity offers more security. In peer-to-peer (P2P) networks, higherconnectivity improves network security. This was demonstrated by both traditionalP2P research [3, 4] and Bitcoin-specific prior work [8, 16, 30, 39, 49].Certain attacks become less successful if the network is highly connected [29,39, 50]. As an example, the eclipse attack [30] has shown that fewer than 13 con-nections would be detrimental to security of the network. As another example,consider a recently discovered vulnerability [18] that relies on InvBlock [44]. In-vBlock is a technique that prevents a transaction from being propagated by firstannouncing it to a node, but then withholding the transaction contents for two min-utes. With higher connectivity, this attack is easier to mitigate. For that reason,Bitcoin literature repeatedly recommends to increase the number of connections tomake the network more robust [8, 16].80204060801001201408 16 32 64Bandwidth, MBConnections every node establishesINVBase cost (GETDATA + TX)Figure 3.1: Analytical cost of relaying one transaction across the network of60,000 nodes.9Chapter 4Protocol requirementsR1: Good scalability as the number of connections increases. Our main goal isto design a transaction dissemination protocol that has good scalability in functionof the number of connections. This way, we can make the network more securewithout sacrificing performance.R2: Maintain a network topology suited for a trustless environment. Bitcoin’spremise of a trustless environment puts constraints on the design of its network.Although imposing a structure onto a network, e.g., by organizing it into a treeor star topology, or by using distributed hash table (DHT)-style routing, enablesbandwidth-efficient implementation of flooding, this also introduces the risks ofcensorship or partitioning [39]. The topology of the network must, therefore, re-main unstructured, and routing decisions must be made independently by everynode based on their local state.R3: Maintain a reasonble latency. Transaction propagation delays should remainin the ballpark of those experienced with the existing protocol. Low latency isessential to user experience and enables better efficiency in block relay [13].R4: Be robust to attacks under the existing threat model. Our protocol mustremain robust under the same threat model as that assumed by the existing protocol.Similarly to Bitcoin, we assume that an attacker has control over a limited numberof nodes in the network, has a limited ability to make other nodes to connect to it,and is otherwise unrestricted in intercepting and generating traffic for peers that itis connected to.10The transaction relay protocol must not be any more susceptible to DoS attacksand client deanonymization, and must not leak any more information about thenetwork topology [50] than the existing protocol.11ReconciliationRound 2Low-fanoutfloodingReconciliationRound 1…ReconciliationRound nPrivate nodes: Public nodes: Figure 4.1: Erlay disseminates transactions using low-fanout flooding as thefirst step, and then several rounds of reconciliation to reach all nodes inthe network.12Chapter 5Erlay designTraditionally, P2P networks addressed inefficiency of flooding by imposing a struc-tured overlay onto an ad-hoc topology. We refrained from structured network or-ganizations for security reasons discussed in Section 4. Instead, our design relieson two common system-building techniques: delay and batching.Instead of announcing every transaction on each link, a node using our protocoladvertises it to a subset of peers – this is called low-fanout flooding. To makesure that all transactions reach the entire network, a node periodically sends to itspeers a batch of transaction announcements that it accumulated recently, and thepeers request those transactions that are missing from their own collections. Thisis called set reconciliation. Our protocol, that is comprised of low-fanout floodingand set reconciliation (Fig. 4.1), is called Erlay.Low-fanout flooding. The rationale behind low-fanout flooding is to expedi-ently relay a transaction to be within a small number of hops from every node inthe network. If each transaction ends up close to every node, then reconciliationcan finish dissemination using a small number of rounds. Therefore, a key decisionin low-fanout flooding is to which peers to relay.Set reconciliation. Set reconciliation was proposed as an alternative to syn-chronization in distributed systems [45]. Using set reconciliation a node in a P2Pnetwork periodically compares its local state to the state of its peers, and sends/re-quests only the necessary information (the state difference). Set reconciliation maybe viewed as an efficient version of batching (accumulating multiple state updates13Bandwidth usedLatencyto reachall nodesReconcilationFloodingErlayFigure 5.1: Comparison of reconciliation, flooding, and Erlay in their band-width usage and latency to reach all nodes.and sending them as a single message). The key challenge in practical reconcili-ation is for the peers to efficiently compute their missing transaction state, and tolimit the exchanged transactions to just those that the other peer is missing.Fig. 5.1 shows how Erlay attempts to find a sweet spot in terms of band-width and latency by combining flooding, which wastes bandwidth but dissem-inates transactions quickly, and reconciliation, which takes longer, but does notwaste bandwidth.5.0.1 Low fanout floodingFlooding is expensive, so we want to use it sparingly and in strategic locations. Forthat reason, only well-connected public nodes flood transactions to other publicnodes via outbound connections. Since every private node is directly connected toseveral public nodes, this policy ensures that a transaction is quickly propagated tobe within one hop from the majority of the nodes in the network. As a result, onlyone or two reconciliation rounds are needed for full reachability (R3). According tothis, the protocol we propose may be viewed as two-tier optimistic replication [55].To meet our scalability goal (R1), we limit the flooding done by public nodes toeight outbound connections even if the total number of these connections is higher.This way, increasing connectivity does not increase transaction dissemination costproportionally.14The decision to relay through outbound connections, but not the inbound ones,was made to defend against timing attacks [18, 50]. In a timing attack, an attackerconnects to a victim and listens to all transactions that a victim might send onthat link (the inbound connection for the victim). If an attacker learns about atransaction from multiple nodes (including the victim), the timing of transactionarrival can be used to guess whether a transaction originated at the victim: if itdid then it will most likely arrive from the victim earlier than from other nodes.BTCFlood introduces a diffusion delay to prevent timing attacks. In Erlay, since wedo not forward individuial transactions to inbound links, this delay is not necessary.So this decision favors both R3 and R4.Transactions in the Bitcoin (BTC) network may originate both at public andprivate nodes. Public nodes disseminate their transactions to a subset of publicnodes via flooding, and via reconciliation to private nodes (and the remaining pub-lic nodes). In the protocol we propose, private nodes do not relay transactions viaflooding, so the network will learn about their originating transactions via recon-ciliation: private nodes will add their own transactions to the batch of other trans-actions that they are forwarding to their peer during reconciliation. Since a privatenode forwards its own transactions as part of the batch, as opposed to individually,a malicious public node is unlikely to discover the origin of a transaction (R4).5.0.2 Set reconciliationIn Erlay peers perform set reconciliation by computing a local set sketch, as definedby the PinSketch algorithm [19]. A set sketch is a type of set checksum with twoimportant properties:• Sketches have a predetermined capacity, and when the number of elementsin the set does not exceed the capacity, it is always possible to recover theentire set from the sketch by decoding the sketch. A sketch of b-bit elementswith capacity c can be stored in bc bits.• A sketch of the symmetric difference between the two sets (i.e., all elementsthat occur in one but not both input sets), can be obtained by XORing the bitrepresentation of sketches of those sets.15These properties make sketches appropriate for a bandwidth-efficient set rec-onciliation protocol. More specifically, if Alice and Bob suspect that their setslargely, but not entirely overlap, they can use the following protocol to have bothparties learn all the elements of the two sets:• Alice, Bob both locally compute sketches of their sets.• Alice sends her sketch to Bob.• Bob combines the two sketches, and obtains a sketch of the symmetric dif-ference.• Bob tries to recover the elements from the symmetric difference sketch.• Bob sends to Alice the elements that she is missing.This procedure will always succeed when the size of the difference (elementsthat Alice has but Bob does not have plus elements that Bob has but Alice does nothave) does not exceed the capacity of the sketch that Alice sent. A key property ofthis process is that it works regardless of the actual set sizes: only the size of theset differences matters.Decoding the sketch is computationally expensive and is quadratic in the sizeof the difference. That is why, accurately estimating the size of the difference(Section 5.0.2) and reconciling before the set difference becomes too large (Sec-tion 5.0.2) are important goals for the protocol.Reconciliation roundFig. 5.2 summarizes the reconciliation protocol. To execute a round of reconcilia-tion, every node maintains a reconciliation set for each one of its peers. A recon-ciliation set consist of short IDs of transactions that a node would have sent to acorresponding peer in regular BTCFlood, but has not because Erlay limits flooding.We will refer to Alice’s reconciliation set for Bob as A and Bob’s set for Alice as B.Alice and Bob will compute the sketches for these reconciliation sets as describedin the previous section.16Important parameters of the protocol are: D – the true size of the set difference,d – an estimate of D, and q – a parameter used to compute d. We provide thederivation of these values below. First, we describe a reconciliation round:1. According to a chosen reconciliation schedule (Section 5.0.2), Alice sendsto Bob the size of A and q.2. Bob computes d, an estimate of D, between his B and Alice’s A (see below).3. Bob computes a sketch of B which allows to reconcile D transactions andsends it to Alice, along with the size of B.4. Alice receives Bob’s sketch of B, computes a sketch of A, and XORs the twosketches. Now Alice has a sketch of the difference between A and B.5. If the difference size was estimated correctly, Alice is able to decode thesketch computed in the previous step, request the transactions that she ismissing from Bob, and then advertise to Bob the transactions that he is miss-ing. If the estimation was incorrect (sketch decoding failed), Alice will resortto bisection (Section 5.0.2).6. After this process, Alice updates q (see below) and clears A. Bob clears B.Accurate estimation of D is crucial for success of reconciliation. Prior work es-timated D using techniques like min-wise hashing [11] or random projections [24].These techniques are complex, and we were concerned that they could end up usingmore bandwidth that they save. Therefore, we resorted to a minimalistic approach,where we estimate the size of the set difference based on just the current sizes ofsets and the difference observed in the previous reconciliation round:d = abs(|A|− |B|)+q ·min(|A|, |B|)+ c,where q is a floating point coefficient (derived below) that characterizes previousreconciliation, and c is a coefficient for handling special cases.Indeed, the difference between two sets cannot be smaller than the differencein their sizes. To avoid costly underestimations, we add the size of the smaller17BISECSUMMARYsketch(B/2, d)BobAliceINIT|A|, qSUMMARYsketch(B, d)BobAliceRECONCIL_DIFFmissing1, missing2TXmissing1GETDATAmissing2TXmissing2BobAliceSet A Set BAttempt to find difference:diff, fail = recon(sketch(A), sketch(B))if (fail) then run Protocol Reconcile-Bisecelse run Protocol DiffExchangeEstimate difference:d = estimate(|A|, |B|, q) Remove from missing2 txns received from other peerssince start of this exchangeTry to find differencediff1, fail1 = recon(sketch(A/2), sketch(B/2))diff2, fail2 = recon(sketch(A-A/2), sketch(B-B/2))if (fail1 OR fail2) then run Original protocol in Fig. 3else run Protocol DiffExchangeProtocol Reconcile-InitProtocol DiffExchangeProtocol Reconcile-BisecFigure 5.2: Reconciliation protocol with correct difference estimation(Reconcile-Init, followed by DiffExchange). And, reconciliation pro-tocol with incorrect difference estimation (Reconcile-Init, followed byReconcile-Bisec). In case reconciliation fails during Reconcile-Bisec,reconciliation falls back to Bitcoin’s current exchange method (seeFig. 2.2).set normalized by q, and a constant c = 1, which prevents estimating d = 0 when|A|= |B| and q ·min(|A|, |B|) = 0.The coefficient q characterizes earlier reconciliation, so before the very firstreconciliation round it set to zero. At the end of a reconciliation round, we simplyupdate q based on the true D that we discovered during the round, by substitutingD for d in the above equation, dropping c and solving for q:q =D−abs(|A|− |B|)min(|A|, |B|)This updated q will be used in the next reconciliation round. We compute q inthis way, because we assume that every node in the network will have a consistentoptimal q.Reconciliation is a fertile ground for DoS attacks, because decoding a sketchis computationally expensive. To prevent these attacks, in our protocol the nodethat is interested in reconciliation (and the one that has to decode the sketch) ini-tiates reconciliation (Alice, in our example). Bob cannot entice Alice to performexcessive sketch decoding.18Reconciliation scheduleEvery node initiates reconciliation with one outbound peer every T seconds. Choos-ing the right value for T is important for performance and bandwidth consumption.If T is too low, reconciliation will run too often and will use more bandwidth than itsaves. If T is too high, reconciliation sets will be large and decoding set differenceswill be expensive (the computation is quadratic in the number of differences). Alarge T also increases the latency of transaction propagation.A node reconciles with one peer every T seconds. Since every node has coutbound connections, every link in the network would, on average, run reconcil-iation every T · c seconds. This means that the average reconciliation set prior toreconciliation would contain T · c ·T X rate transactions, where T X rate is the globaltransaction rate. This also means that during the interval between reconciliationsevery node would receive T ·T X rate transactions.We use a value of 1 second for T in Erlay. With this setting, and the currentratio of private to public nodes, every public node will perform about eight rec-onciliations per second. Given the current maximum Bitcoin network transactionrate T X rate of 7 transactions/s, the average difference set size for this protocol is 7elements. We evaluate our choice of parameters in Section 8.Bisection for set difference estimation failureOur set reconciliation approach relies on the assumption that an upper bound forthe set difference between two peers is predictable. That is, if the actual differenceis higher than estimated, then reconciliation will fail. This failure is detectable by aclient computing the difference. An obvious solution to this failure is to recomputeand retransmit the sketch assuming a larger difference in the sets. However, thiswould make prior reconciliation transmissions useless, which is inefficient.Instead, Erlay uses reconciliation bisection, which re-uses previously transmit-ted information. Bisection is based on the assumption that elements are uniformlydistributed in reconciliation sets (this may be achieved by hashing). If a node isunable to reconstruct set difference from a product of two sketches, the node thenmakes an additional reconciliation request, similar to the initial one, but this re-quest is applied to only a fraction of possible messages (e.g., to transactions in the19Sketches (size N)S0 N2NS1  S0S1 N : S1N : S0CanRecover TransmittedReconcile-Init:Reconcile-Bisec:Figure 5.3: Bisection is enabled by the linearity of sketchesrange 0x0–0x8). Because of the linearity of sketches, a sketch of a subset of trans-actions would allow the node to compute a sketch for the remainder, which savesbandwidth.However, this approach would allow to recover at most 2d differences, whered is the estimated set difference in the initial step. Even though bisections are notlimited to one and may be applied consequentually without loosing efficiency, inour implementation, after a reconciliation step failure, we allow only one bisectionwith a new overall estimate 2d (see Fig. 5.3). The bisection process is illustratedin protocol Reconcile-Bisec in Figure 5.2.If bisection fails, then Erlay falls backs to the original INV-GETDATA protocol(Fig. 2.2) and applies it to all of the transactions in two sets being reconciled.20Chapter 6Implementation detailsIn this section we describe low-level design decisions required to implement Erlayand increase its bandwidth efficiency (R2) and make it robust to collision-baseddenial of service (DOS) attacks (R4).Library implementation. We created a C++ library with 3055 lines of code(LOC)1, that is an optimized implementation of the PinSketch [19] algorithm. Webenchmarked the library to verify that set reconciliation would not create highcomputational workload on Bitcoin nodes. Fig. 6.1 shows the decoding perfor-mance on an Intel Core i7-7820HQ CPU of our library (PinSketch) as comparedto CPISync [58]2 for varying difference sizes3. Our library has sub-millisecondperformance for difference sizes of 100 elements or fewer. As we will show later(Fig. 8.3) this performance is sufficiently fast for the differences we observe inpractice (in simulation and in deployment).We used this library to build a reference implementation of Erlay as a part ofthe Bitcoin Core software, which we evaluate in Section 9.Short identifiers and salting. The size of a transaction ID in the Bitcoin protocolis 32 bytes. To use PinSketch [19], we have to use shorter, 64 bit, identifiers. Usingfewer bits reduces the bandwidth usage by 75% (R2), but it also creates a proba-bility of collisions. Collisions in transaction relay is an attack surface, because a1https://github.com/sipa/minisketch2https://github.com/trachten/cpisync3We omit other library benchmarks due to limited space.211 µs10 µs100 µs1 ms10 ms0 5 10 15 20 25 30 35 40 45 50DecodetimeDifferencesCPISyncPinSketchFigure 6.1: The decode time of our library (PinSketch) as compared toCPISync for varying set difference sizes.malicious actor may flood a network with colluding transactions and fill memorypools of the nodes with transactions which would be propagated and confirmed in avery slow manner. Thus, we want to secure the protocol against such attacks (R4).While collisions on one side of communication are easy to detect and handle,collisions involving transactions on both sides may cause a significant slowdown.To mitigate this, we use different salt (random data added to an input of a hash-function) while hashing transaction IDs into short identifiers.The salt value is enforced by the peer that initiates the connection, and perErlay’s design, requests reconciliation. Since the peer requesting reconciliationalso computes the reconciliation difference, the requestor peer would have to dealwith short IDs of unknown transactions. Since salt is chosen by the requestor, re-using the same salt for different reconciliations would allow him to compare saltedshort IDs of unknown transactions to the IDs received during flooding from otherpeers at the same time.Low-fanout diffusion delay. Bitcoin flooding mitigates timing attacks [50] andin-flight collisions by introducing a random delay into transaction announcements.For timing attacks Bitcoin assumes that an attacker connects (possibly, multipletimes) to the node (or takes over a fraction of outbound connections of the node).In a low-fanout model, this attack is not feasible, because transactions are flooded22through outbound connections only.In-flight collisions are also not possible in the case of low-fanout relay throughonly outbound links, because transactions are always announced in the same direc-tion of a link.Considering these arguments and to reduce latency, Erlay has a lower randomdiffusion interval. Instead of using Toi = 2 seconds for outbound connections andTii = 5 seconds for inbound, Erlay uses Toi = 1 seconds for outbound.Reconciliation diffusion delay. Even though in Erlay timing attacks by observinglow-fanout flooding are not feasible, an attacker would be able to perform themthrough reconciliations. To make timing attacks through reconciliations more ex-pensive to perform, we enforce every peer to respond to reconciliation requestsafter a small random delay (in our implementation, it is a Poisson-distributed ran-dom variable which is on average Tri = 3 seconds) and rate-limit reconciliationsper peer. This measure would make Erlay better than BTCFlood in terms of with-standing timing attacks.Our measure in Erlay has the same idea as in flooding/low-fanout diffusion,however, having the ratio Tii/Toi higher makes timing attacks less accurate, becauseduring Tii (the average time before an attacker receives a transaction) a transactionwould be propagated to more nodes in the network.We chose the interval of 3 seconds because a lower interval would make Erlaymore susceptible to timing attacks than Bitcoin, and a higher interval results in ahigh latency.23Chapter 7Evaluation methodologyIn evaluating Erlay we focus on answering the following three questions:1. How does Erlay compare in latency (the time that it takes for the transactionto reach all of the nodes) and bandwidth (number of bits used to disseminatea transaction) to BTCFlood?2. How do the two parts of Erlay (low-fanout flooding and reconciliation) per-form at scale and with varying number of nodes?3. How do malicious nodes impact Erlay’s performance?We use measurement results from two sources to answer the questions above.First, we use a simulator to simulate Erlay on a single machine. Second, we im-plemented Erlay in the mainline Bitcoin client and deployed a network of Erlayclients on the Azure cloud across several data centers (Section 9).Simulator design. Our simulation was done with ns3. We modified an open-source Bitcoin Simulator [28] to support transaction relay. The original simulatorhad 9663 LOC; we modified 9948 LOC.Our simulator is based on the INV-GETDATA transaction relay protocol (seeSection 2). It is parameterized by the current ratio of public nodes to private nodesin the Bitcoin network and the transaction rate based on the historical data fromthe Bitcoin network (on average, 7 transactions per second). To simulate the dif-24ferent ratios of faults in the network by introducing Black Hole nodes (nodes whichreceive messages, but do not propagate transactions further).However, our simulator does not account for the resource-wise heterogeneoussetting, the block relay phase, the joining and leaving of nodes during the transac-tion relay phase (churn), and we do not consider sophisticated malicious nodes.The propagation latency measured for BTCFlood by our simulator matches thevalue suggested for the validation of Bitcoin simulators [22], and our measuredbandwidth matches our analytical estimate.Topology of the simulated network. We emulated a network, similar tothe current Bitcoin network, since inferring the Bitcoin network topology is non-trivial [50]. In our simulation we bootstrap the network in 2 phrases: (1) publicnodes connect to each other using a limit of 8 outbound connections, then (2) pri-vate nodes connect to 8 random public nodes.Unless stated otherwise, our simulation results are for a network of 6,000 pub-lic nodes and 60,000 private nodes (this is the scale of today’s network1). In eachexperiment we first used the above two steps to create the topology, then we re-layed transactions for 600 seconds (on average, 4,200 transactions generated fromrandom private nodes).1https://bitnodes.earn.com/ https://luke.dashjr.org/programs/bitcoin/files/charts/software.html25Chapter 8Simulation resultsIn this section we demonstrate the measured properties (latency, bandwidth con-sumption, and security) of Erlay and compare these to BTCFlood.8.0.1 Relay bandwidth usageTo verify that Erlay scales better than BTCFlood as the number of connections pernode is increased, we varied the number of outbound connections per node andmeasured the bandwidth used for relaying transactions.We report the average relay bandwidth cost relatively to b (the size of a trans-action announcement in bits). Table 8.1 shows the results. In the table, bothBTCFlood and Erlay numbers are from simulation experiments.Erlay achieves a cost below b for connectivity of 8 because of the use of shortIDs during set reconciliation. This is because BTCFlood announces transactionson every link in the network, so its relay bandwidth increases linearly with the con-nectivity. By contrast, with higher connectivity of the network, bandwidth in Erlaygrows significantly slower than in BTCFlood. This higher connectivity allows forbetter security of the overall system.Transaction announcements in overall bandwidth. To demonstrate that Er-lay’s announcement optimization impacts overall bandwidth, we measure the band-width consumed by a simulated network to relay transactions with BTCFlood andErlay. Fig. 8.1 plots the results for simulations in which every node establishes8 connections. Erlays’s announcement bandwidth is just 12.5% of the relay band-26Table 8.1: The average bandwidth cost of relaying one transaction to onenode in the Bitcoin network with BTCFlood and Erlay. b is the announce-ment size in bits.Connectivity BTCFlood Erlay8 8b 0.93b16 16b 1.12b24 24b 1.23b32 32b 1.36b05101520253035Erlay BTCFloodBandwidth, MBAnnouncement costBase cost (TX+GETDATA)16.13 MB14.64 MB16.13 MB2.31 MBFigure 8.1: Average bandwidth cost of relaying a transaction in a network of60,000 nodes with outbound connectivity of 8.width, while for BTCFlood the announcement bandwidth is 44.7%.Breaking down Erlay’s bandwidth usage. To further understand Erlay’sbandwidth usage, we broke it down by the different parts of the protocol: low-fanout flooding, reconciliation, post-reconciliation announcements.Table 8.2 lists the results. The table shows that about a third of the bandwidthis used by low-fanout flooding, while reconciliation accounts for the bulk of thebandwidth. The post-reconciliation INVs account for a small fraction of Erlay’sbandwidth.27Table 8.2: Breakdown of bandwidth usage in Erlay.Erlay component Bandwidth %Low-fanout flooding 54%Reconciliation 32%Bisection 0.7%Fallback 4.3%Post-reconcile. INVs 9%Total 100%Set reconciliation effectiveness. To understand the effectiveness of Erlay’sset reconciliation, we measured how often reconciliation or the following bisectionprotocol fail. Fig. 8.2 reports the results aggregated from one of our simulation runswith 60,000 nodes. The end-to-end probability of reaching fallback is below 1%.Since bisection does not introduce additional bandwidth overhead (while fallbackdoes), the overall reconciliation overhead is low.Since every reconciliation round requires a set difference estimation, we mea-sured the distribution of the estimated difference sizes. Fig. 8.3 demonstrates thatset difference depends on transaction rate. This is expected: for the same recon-ciliation intervals, a higher transaction rate would result in both reconciling partiesreceiving more transactions and would lead to a larger set difference. This depen-dency between set difference and transaction rate allows accurate set differenceestimation. Fig. 8.2 illustrates that Erlay’s estimate is correct 96% of the time.For the cases where Erlay over-estimates and the initial reconciliation fails, theresulting bandwidth overhead constinutes 9% of the overall bandwidth.In our library benchmarks the decode time for a sketch containing 100 differ-ences is under 1 millisecond (Fig. 6.1). Thus, the computational cost of operatingover sketches with the distribution in Fig. 8.3 is negligible.8.0.2 Relay latencyTo analyze latency we ran simulation experiments while changing the total numberof both private and public nodes. In these experiments we kept constant the ratiobetween private and public types of nodes at 10 : 1 (this is the ratio in today’sBitcoin network). Fig. 8.4 plots the average latency for a single transaction to28FallbackReconcile-InitDiffExchangeReconcile-Bisec96%4%7%93%Figure 8.2: Finite state machine of the protocol in Fig. 2.2 annotated withtransition percentages observed in our experiments.reach all nodes for Erlay and BTCFlood. Erlay has a constant latency overhead ontop of BTCFlood that is due to its use of batching. However, this overhead is just 2seconds and changes at approximately the same rate with the number of nodes asBTCFlood’s latency. We could further reduce Erlay’s per transaction latency, butat the cost of higher bandwidth usage.Latency under faulty condition We also evaluated Erlay’s latency in a simpleadversarial setting. For this we simulated a network in which 10% of the publicnodes are black holes and measured the time for a transaction to reach all the nodes.While it is difficult to outperform the robustness of BTCFlood, an alternative pro-tocol should not be dramatically impacted by this attack.According to our measurements, while the slowdown with BTCFlood in thissetting is 2%, the slowdown with Erlay is 20%. We believe that this latency in-crease is acceptable for a batching-based protocol. We have ideas for heuristicsthat might be applied to mitigate black-hole attacks and make Erlay less suscepti-ble. For example, a node might avoid reconciling with those outbound connectionsthat regularly provide the fewest new transactions.295 tx/s6 tx/s7 tx/s8 tx/sFigure 8.3: Distribution of the set difference estimates during reconciliationfor different transaction rates.300123456730,000 60,000 90,000Latency, sNodes (both public and private) in the networkErlayBTCFloodFigure 8.4: Average latency for a single transaction to reach 100% nodes inthe network.31Chapter 9Reference implementation resultsWe implemented Erlay as part of Bitcoin Core. For this we added 584 LOC, notincluding our PinSketch library. We used a network of 100 Azure nodes locatedin one data center, running a reference implementation of our protocol integratedin Bitcoin Core node software, to evaluate Erlay in deployment. We generated andrelayed 500 transactions, all originating from one node with a rate of 7 transactionsper second. We compared the average latency and bandwidth of Erlay versus Bit-coin’s current implementation. Table 9.1 summarizes our results. According to ourmeasurements, Erlay introduced a latency increase of 2.66 seconds, while saving44% of the overall node bandwidth.As in our simulations, Erlay has a higher latency but lower bandwidth cost,confirming our original design intent (Fig. 5.1).32BTCFlood ErlayBase cost (MB)(TX+GETDATA)12.78 12.75Other messages (MB) 1.06 1.1Announcement cost (MB) 17.79 2.70Latency (s) 1.34 4.46Table 9.1: Prototype measurements collected from a 100-node deploymentcomparing the latency and bandwidth of the BTCFlood in the referenceimplementation against our Erlay implementation.33Chapter 10DiscussionReconciliation-only relay. We believe that a reconciliation-only transaction re-lay protocol would be inherently susceptible to timing attacks that could revealthe source of the transaction. Unlike flooding, in reconciliation delays cannot beapplied per-direction but rather per-link. Therefore, BTCFlood’s diffusion delaycannot be used in reconciliation.Compatibility with Dandelion. Dandelion is an alternative transaction re-lay protocol introduced to improve the anonymity and robustness to adversarialobservers in Bitcoin [23]. Erlay is complimentary with Dandelion: Erlay wouldreplace the fluff phase in Dandelion.Backward compatibility. Only about 30% of Bitcoin nodes run the latestrelease of Bitcoin Core1. Therefore, Erlay must be backwards compatible. If notall the nodes use Erlay, then Erlay may be activated per-link if both peers supportit.Timing attacks from public nodes. Erlay’s design is more robust to timingattacks from private sybils [18, 29]. Robustness to timing attacks from publicnodes remains an open questions. Both BTCFlood and Erlay use faster relay topublic nodes and slower relay to private nodes. But Erlay’s slower reconciliationcould be abused by public nodes to more easily identify transactions originatingfrom private nodes. With higher node connectivity this attack becomes expensive,but a general solution remains as future work.1https://luke.dashjr.org/programs/bitcoin/files/charts/security.html34Chapter 11Related WorkPrior studies of Bitcoin’s transaction relay focused on information leakage andother vulnerabilities [23, 50], and did not consider bandwidth optimization. Webelieve that our work is the first to introduce a bandwidth-efficient, low-latency,and robust transaction relay alternative for Bitcoin. Erlay is designed as a minimalchange to Bitcoin (584 LOC), in contrast with other proposals that optimize Bitcoinmore deeply [21].Short transaction identifiers. One solution to BTCFlood’s inefficiency is to useshort transaction identifiers. There are two issues with this solution. First, thisonly reduces bandwidth cost by a constant factor. In our simulation we foundthat short identifiers would reduce redundant traffic from 43% to 10%. But, withhigher connectivity, redundancy climbs back up faster than in does with Erlay.The second issue with short IDs is that they would make the system vulnerableto collision-related attacks and requires a new per-node or per-link secure saltingstrategy.Blocksonly setting. Bitcoin Core 0.12 introduced a blocksonly setting using whicha node does not send or receive individual transactions; instead, the node onlyhandles complete blocks. As a result, blocksonly has no INV message overhead.In the blocksonly case, nodes will have to relay and receive many transactions atonce. This will increase the maximum node bandwidth requirements and causespikes in block content relay and transaction validationReconciliation alternatives. Prior work has also devised multi-party set reconcil-35iation [10, 46]. This approach, however, has additional complexity and additionaltrust requirements between peers. We believe that the benefits of such an approachare not substantial enough to justify these limitations.In addition, reconciliation-based techniques usually provide bandwidth-efficiencyunder the assumptions where most of the state being reconciled is shared [13, 51].Prior P2P research. Structured P2P networks are usually based on a DistributedHash Tables (DHTs), in which every peer is responsible for specific content [41].In these networks research has explored the use of topology information to makeefficient routing decisions [12, 54, 56, 59]. This design, however, makes theseprotocols leak information about the structure of the network and makes them lessrobust to Byzantine faults; though limited solutions to Byzantine faults in this set-ting have been explored [15, 25].The trade-off between latency and bandwidth efficiency is well-known in P2Presearch. Kumar et. al. identified and formalized the trade-off between latencyand bandwidth [36], and Jiang et. al. proposed a solution to achieve an optimalcombination of these properties [31]. However, the solution was not designed foradversarial settings.Prior work also proposed feedback-based approaches to flooding [2, 52]. How-ever, we believe that to work efficiently (have a horizon larger than 1), this workwould have unacceptable information leakage.36Chapter 12ConclusionBitcoin is one of the most widely used P2P applications. Today, Bitcoin relieson flooding to relay transactions in a network of about 60,000 nodes. Floodingprovides low latency and is robust to adversarial behavior, but it is also bandwidth-inefficient and creates a significant amount of redundant traffic. We proposed Erlay,an alternative protocol that combines limited flooding with intermittent reconcilia-tion. We evaluated Erlay in simulation and with a practical deployment. Comparedto Bitcoin’s current protocols, Erlay reduces the bandwidth used to announce trans-actions by 84% while increasing the latency for transaction dissemination by 50%(from 4s to 6s). Erlay allows Bitcoin nodes to have higher connectivity, which willmake the network more secure. We are actively working to introduce Erlay intoBitcoin Core’s node software.37Bibliography[1] Bitcoin core commit 5400ef.https://github.com/bitcoin/bitcoin/commit/5400ef6bcb9d243b2b21697775aa6491115420f3.→ page 4[2] W. Ai, L. Xinsong, and L. Kejian. Efficient flooding in peer-to-peernetworks. 01 2006. doi:10.1109/CAIDCD.2006.329410. → page 36[3] R. Albert and A.-L. Baraba´si. Statistical mechanics of complex networks.Rev. Mod. Phys., 74:47–97, Jan 2002. doi:10.1103/RevModPhys.74.47.URL https://link.aps.org/doi/10.1103/RevModPhys.74.47. → page 8[4] R. Albert, H. Jeong, and A.-L. Baraba´si. Error and attack tolerance ofcomplex networks. Nature, 406:378 EP –, 07 2000. URLhttps://doi.org/10.1038/35019019. → page 8[5] G. Andresen. Increase maximum block size.https://github.com/bitcoin/bips/blob/master/bip-0101.mediawiki, Jun 2015.→ page 1[6] M. Andrychowicz, S. Dziembowski, D. Malinowski, and Ł. Mazurek. Onthe malleability of bitcoin transactions. In M. Brenner, N. Christin,B. Johnson, and K. Rohloff, editors, Financial Cryptography and DataSecurity, pages 1–18, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.ISBN 978-3-662-48051-9. → page 1[7] M. Ball, A. Rosen, M. Sabin, and P. N. Vasudevan. Proofs of useful work.2017. → page 1[8] A. Biryukov, D. Khovratovich, and I. Pustogarov. Deanonymisation ofClients in Bitcoin P2P Network. In ACM SIGSAC Conference on Computerand Communications Security, CCS, 2014. → pages 1, 838[9] J. Bonneau. Why buy when you can rent? - bribery attacks on bitcoin-styleconsensus. In Financial Cryptography Workshops, 2016. → page 1[10] A. Boral and M. Mitzenmacher. Multi-party set reconciliation usingcharacteristic polynomials. CoRR, abs/1410.2645, 2014. → page 36[11] A. Broder. On the resemblance and containment of documents. InProceedings of the Compression and Complexity of Sequences 1997,SEQUENCES ’97, pages 21–, Washington, DC, USA, 1997. IEEEComputer Society. ISBN 0-8186-8132-2. URLhttp://dl.acm.org/citation.cfm?id=829502.830043. → page 17[12] I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong. Freenet: A DistributedAnonymous Information Storage and Retrieval System, pages 46–66.Springer Berlin Heidelberg, Berlin, Heidelberg, 2001. ISBN978-3-540-44702-3. doi:10.1007/3-540-44702-4 4. URLhttps://doi.org/10.1007/3-540-44702-4 4. → page 36[13] M. Corallo. Bip 152: Compact block relay.https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki, 2016. →pages 1, 10, 36[14] corbixgwelt. Timejacking and bitcoin.http://culubas.blogspot.de/2011/05/timejacking-bitcoin802.html, 2011. →page 1[15] A. Dearle, G. N. C. Kirby, and S. J. Norcross. Hosting byzantine faulttolerant services on a chord ring. CoRR, abs/1006.3465, 2010. → page 36[16] C. Decker and R. Wattenhofer. Information propagation in the bitcoinnetwork. In IEEE P2P 2013 Proceedings, pages 1–10, Sept 2013.doi:10.1109/P2P.2013.6688704. → page 8[17] C. Decker and R. Wattenhofer. Bitcoin transaction malleability and mtgox.CoRR, abs/1403.6676, 2014. → page 1[18] S. Delgado Segura, S. Bakshi, C. Pe´rez-Sola`, J. Litton, A. Pachulski,A. Miller, and B. Bhattacharjee. Txprobe: Discovering bitcoin’s networktopology using orphan transactions, 12 2018. → pages 1, 8, 15, 34[19] Y. Dodis, L. Reyzin, and A. Smith. Fuzzy extractors: How to generatestrong keys from biometrics and other noisy data. In C. Cachin and J. L.Camenisch, editors, Advances in Cryptology - EUROCRYPT 2004, pages39523–540, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. ISBN978-3-540-24676-3. → pages 15, 21[20] J. R. Douceur. The Sybil Attack. In International Workshop on Peer-to-PeerSystems, IPTPS, 2002. → page 1[21] I. Eyal, A. E. Gencer, E. G. Sirer, and R. Van Renesse. Bitcoin-NG: AScalable Blockchain Protocol. In Usenix Conference on Networked SystemsDesign and Implementation, NSDI, 2016. → page 35[22] M. Fadhil, G. Owen, and M. Adda. Bitcoin network measurements forsimulation validation and parameterisation. In Proceedings of the EleventhInternational Network Conference (INC 2016), pages 109–114. Universityof Plymouth, 7 2016. → page 25[23] G. C. Fanti, S. B. Venkatakrishnan, S. Bakshi, B. Denby, S. Bhargava,A. Miller, and P. Viswanath. Dandelion++: Lightweight cryptocurrencynetworking with formal anonymity guarantees. CoRR, abs/1805.11060,2018. URL http://arxiv.org/abs/1805.11060. → pages 34, 35[24] J. Feigenbaum, S. Kannan, M. J. Strauss, and M. Viswanathan. Anapproximate l1-difference algorithm for massive data streams. SIAM J.Comput., 32(1):131–151, Jan. 2003. ISSN 0097-5397.doi:10.1137/S0097539799361701. URLhttps://doi.org/10.1137/S0097539799361701. → page 17[25] A. Fiat, J. Saia, and M. Young. Making chord robust to byzantine attacks. InProceedings of the 13th Annual European Conference on Algorithms,ESA’05, pages 803–814, Berlin, Heidelberg, 2005. Springer-Verlag. ISBN3-540-29118-0, 978-3-540-29118-3. doi:10.1007/11561071 71. URLhttp://dx.doi.org/10.1007/11561071 71. → page 36[26] J. Garzik. Block size increase to 2mb.https://github.com/bitcoin/bips/blob/master/bip-0102.mediawiki, Jun 2015.→ page 1[27] A. Gervais, H. Ritzdorf, G. O. Karame, and S. Capkun. Tampering with theDelivery of Blocks and Transactions in Bitcoin. In ACM SIGSACConference on Computer and Communications Security, CCS, 2015. →page 1[28] A. Gervais, G. Karame, K. Wu¨st, V. Glykantzis, H. Ritzdorf, and S. Capkun.On the security and performance of proof of work blockchains. In40Proceedings of the 23nd ACM SIGSAC Conference on Computer andCommunication Security (CCS). ACM, 2016. → page 24[29] M. Grundmann, T. Neudecker, and H. Hartenstein. Exploiting transactionaccumulation and double spends for topology inference in bitcoin. 2018. →pages 8, 34[30] E. Heilman, A. Kendler, A. Zohar, and S. Goldberg. Eclipse Attacks onBitcoin’s Peer-to-peer Network. In Proceedings of the 24th USENIXConference on Security Symposium, SEC, 2015. → pages 1, 8[31] J. Jiang, C. Hung, and J. Wu. Bandwidth- and latency-aware peer-to-peerinstant friendcast for online social networks. In 2010 IEEE 16thInternational Conference on Parallel and Distributed Systems, pages829–834, Dec 2010. doi:10.1109/ICPADS.2010.101. → page 36[32] jl777. Re: Blocksonly mode bw savings, the limits of efficient block xfer,and better relay.https://bitcointalk.org/index.php?topic=1377345.msg14012877#msg14012877,Feb 2016. → page 2[33] B. Johnson, A. Laszka, J. Grossklags, M. Vasek, and T. Moore.Game-theoretic analysis of ddos attacks against bitcoin mining pools. InR. Bo¨hme, M. Brenner, T. Moore, and M. Smith, editors, FinancialCryptography and Data Security, pages 72–86, Berlin, Heidelberg, 2014.Springer Berlin Heidelberg. ISBN 978-3-662-44774-1. → page 1[34] U. Klarman, S. Basu, A. Kuzmanovic, and E. G. Sirer. bloxroute: A scalabletrustless blockchain distribution network whitepaper. → page 1[35] P. Koshy, D. Koshy, and P. McDaniel. An analysis of anonymity in bitcoinusing p2p network traffic. In N. Christin and R. Safavi-Naini, editors,Financial Cryptography and Data Security, pages 469–485, Berlin,Heidelberg, 2014. Springer Berlin Heidelberg. ISBN 978-3-662-45472-5.→ page 1[36] P. Kumar, G. Sridhar, and V. Sridhar. Bandwidth and latency model for dhtbased peer-to-peer networks under variable churn. In 2005 SystemsCommunications (ICW’05, ICHSN’05, ICMCS’05, SENET’05), pages320–325, Aug 2005. doi:10.1109/ICW.2005.31. → page 36[37] E. Lombrozo, J. Lau, and P. Wuille. Segregated witness (consensus layer).https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki, Dec 2015.→ page 141[38] S. V. Margariti and V. V. Dimakopoulos. A study on the redundancy offlooding in unstructured p2p networks. International Journal of Parallel,Emergent and Distributed Systems, 28(3):214–229, 2013.doi:10.1080/17445760.2012.724067. → page 2[39] A. Maria, Z. Aviv, and V. Laurent. Hijacking bitcoin: Routing attacks oncryptocurrencies. In Security and Privacy (SP). IEEE, 2017. → pages1, 8, 10[40] G. Maxwell. Blocksonly mode bw savings, the limits of efficient block xfer,and better relay. https://bitcointalk.org/index.php?topic=1377345.0, Feb2016. → page 2[41] P. Maymounkov and D. Mazie`res. Kademlia: A peer-to-peer informationsystem based on the xor metric. In P. Druschel, F. Kaashoek, andA. Rowstron, editors, Peer-to-Peer Systems, pages 53–65, Berlin,Heidelberg, 2002. Springer Berlin Heidelberg. ISBN 978-3-540-45748-0.→ page 36[42] P. McCorry, S. F. Shahandashti, and F. Hao. Refund attacks on bitcoin’spayment protocol. IACR Cryptology ePrint Archive, 2016:24, 2016. → page1[43] A. Miller. Feather-forks: enforcing a blacklist with sub-50% hashpower?https://bitcointalk.org/index.php?topic=36788.msg463391#msg463391,2013.[44] A. Miller, J. Litton, A. Pachulski, N. Gupta, D. Levin, N. Spring, andB. Bhattacharjee. Discovering bitcoin ’ s public topology and influentialnodes. 2015. → pages 1, 8[45] Y. Minsky and A. Trachtenberg. Practical Set Reconciliation. Dept. Elec.Comput. Eng., Boston Univ., Boston, MA, Tech. Rep. BU-ECE2002-01,2002. → pages 3, 13[46] M. Mitzenmacher and R. Pagh. Simple multi-party set reconciliation. CoRR,abs/1311.2037, 2013. → page 36[47] S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system,”http://bitcoin.org/bitcoin.pdf. → page 1[48] A. Narayanan. Bitcoin and cryptocurrency technologies : a comprehensiveintroduction. Princeton University Press, Princeton, New Jersey, 2016.ISBN 978-0691171692. → page 142[49] T. Neudecker and H. Hartenstein. Network layer aspects of permissionlessblockchains. IEEE Communications Surveys Tutorials, pages 1–1, 2018.ISSN 1553-877X. doi:10.1109/COMST.2018.2852480. → page 8[50] T. Neudecker, P. Andelfinger, and H. Hartenstein. Timing analysis forinferring the topology of the bitcoin peer-to-peer network. In 2016 Intl IEEEConferences on Ubiquitous Intelligence Computing, Advanced and TrustedComputing, Scalable Computing and Communications, Cloud and Big DataComputing, Internet of People, and Smart World Congress(UIC/ATC/ScalCom/CBDCom/IoP/SmartWorld), pages 358–367, July 2016.doi:10.1109/UIC-ATC-ScalCom-CBDCom-IoP-SmartWorld.2016.0070. →pages 1, 4, 8, 11, 15, 22, 25, 35[51] A. P. Ozisik, G. Andresen, G. Bissias, A. Houmansadr, and B. N. Levine.Graphene: A new protocol for block propagation using set reconciliation. InDPM/CBT@ESORICS, volume 10436 of Lecture Notes in ComputerScience, pages 420–428. Springer, 2017. → pages 1, 36[52] C. Papadakis, P. Fragopoulou, E. P. Markatos, E. Athanasopoulos,M. Dikaiakos, and A. Labrinidis. A Feedback-Based Approach to ReduceDuplicate Messages in Unstructured Peer-To-Peer Networks, pages103–118. Springer US, Boston, MA, 2007. ISBN 978-0-387-47658-2.doi:10.1007/978-0-387-47658-2 8. URLhttps://doi.org/10.1007/978-0-387-47658-2 8. → page 36[53] J. Poon and T. Dryja. The bitcoin lightning network: Scalable off-chaininstant payments. See https://lightning. network/lightning-network-paper.pdf, 2016. → page 1[54] A. Rowstron and P. Druschel. Pastry: Scalable, distributed object locationand routing for large-scale peer-to-peer systems. In IFIP/ACM InternationalConference on Distributed Systems Platforms (Middleware), pages 329–350,Nov. 2001. → page 36[55] Y. Saito and M. Shapiro. Optimistic replication. ACM Comput. Surv., 37(1):42–81, Mar. 2005. ISSN 0360-0300. doi:10.1145/1057977.1057980. URLhttp://doi.acm.org/10.1145/1057977.1057980. → page 14[56] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan.Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. InSIGCOMM, 2001. → page 3643[57] P. Todd. Why scaling bitcoin with sharding is very hard.https://petertodd.org/2015/why-scaling-bitcoin-with-sharding-is-very-hard,2015. → page 2[58] A. Trachtenberg, D. Starobinski, and S. Agarwal. Fast PDA synchronizationusing characteristic polynomial interpolation. In Proceedings.Twenty-FirstAnnual Joint Conference of the IEEE Computer and CommunicationsSocieties, volume 3, pages 1510–1519 vol.3, June 2002.doi:10.1109/INFCOM.2002.1019402. → page 21[59] S. Vuong and J. Li. Efa: an efficient content routing algorithm in largepeer-to-peer overlay networks. In Proceedings Third InternationalConference on Peer-to-Peer Computing (P2P), pages 216–217, Sept 2003.doi:10.1109/PTP.2003.1231532. → page 36[60] P. Wuille. Block size following technological growth.https://github.com/bitcoin/bips/blob/master/bip-0103.mediawiki, Jul 2015.→ page 1[61] F. Zhang, I. Eyal, R. Escriva, A. Juels, and R. V. Renesse. REM:Resource-Efficient Mining for Blockchains. In USENIX Security Symposium(USENIX Security), 2017. → page 144
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Erlay : efficient transaction relay in Bitcoin
Text