Unlike other cryptocurrencies that use graph vertices directly as votes, Avalanche only uses a DAG for the purpose of batching queries in the underlying Snowball instances. Because condence is built by collected chits, and not by just the presence of a vertex, simply ooding the network with vertices attached to the rejected side of a subgraph will not subvert the protocol.

5.4 Communication Complexity Let the DAG induced by Avalanche have an expected branching factor of p, corresponding to the width of the DAG, and determined by the parent selection algorithm. Given the 1 and 2 decision threshold, a transaction that has just reached the point of decision will have an associated progeny Y . Let m be the expected depth of Y . If we were to let the Avalanche network make progress and then freeze the DAG at a depth y, then it will have roughly py vertices/transactions, of which p(y m) are decided in expectation. Only pm recent transactions would lack the progeny required for a decision. For each node, each query requires k samples, and therefore the total message cost per transaction is in expectation (pky)/(p(y m)) = ky/(y m). Since m is a constant determined by the undecided region of the DAG as the system constantly makes progress, message complexity per node is O(k), while the total complexity is O(kn).

6 Evaluation 6.1 Setup We conduct our experiments on Amazon EC2 by running from hundreds (125) to thousands (2000) of virtual machine instances. We use c5.large instances, each of which simulates an individual node. AWS provides bandwidth of up to 2 Gbps, though the Avalanche protocol utilizes at most around 100 Mbps. Our implementation supports two versions of transactions: one is the customized UTXO format, while the other uses the 10 code directly from Bitcoin 0.16. Both supported formats use secp256k1 crypto library from bitcoin and provide the same address format for wallets. All experiments use the customized format except for the geo-replication, where results for both are given.

We simulate a constant ow of new transactions from users by creating separate client processes, each of which maintains separated wallets, generates transactions with new recipient addresses and sends the requests to Avalanche nodes. We use several such client processes to max out the capacity of our system. The number of recipients for each transaction is tuned to achieve average transaction sizes of around 250 bytes (12 inputs/outputs per transaction on average and a stable UTXO size), the current average transaction size of Bitcoin. To utilize the network eciently, we batch up to 40 transactions during a query, but maintain condence values at individual transaction granularity.