Dandelion Networks Whitepaper
Authors: Paul Chafe, Dr. Atefeh Mashatan, Alexander Munro, and Brian Goncalves. Contributors: Duncan Cameron, Jason Xu
Dandelion Networks (dandelionnet.io), May 18, 2021 — Original version (v1).
“Α blockchain that claims to have solved the [Buterin] Trilemma of secure, scalable and decentralized, has either bent the laws of physics… or it has discovered a breakthrough method that solves the major blockchain scalability problems that have stumped top mathematicians and computer scientists for the past decade.” - Georgios Konstantopoulos (Konstantopoulos, 2018)
0. EXECUTIVE SUMMARY
Open blockchain networks enable global peer-to-peer transactions through the property of distributed trust (Anjum et al., 2017; Bellini et al., 2020; Karame & Capkun, 2018). Current blockchain models have relied on either raw computing power (as in Proof of Work, PoW) or of exogenous currency (as in Proof of Stake, PoS) to commit network nodes to honest consensus. However, the accruing reinvestment cycle and economies-of-scale have driven centralization of node ownership, undermining the distributed trust property; in PoS, the store of value transfers directly from an origin currency into the staked blockchain, which enables even faster centralization. A related problem is the lack of scalability inherent in the blockchain paradigm, which increases costs and limits applications. We describe Dandelion, an alternative, centralization-resistant network, demonstrating long-term security, rapid finalization and unrestricted scalability. Development to date confirms that a wide variety of transacting systems (e.g., DeFi) built on this network can dramatically reduce gas (operating costs), finalization time, and attack vulnerabilities, while allowing a fully scalable transaction system and hence, solving the Buterin Trilemma.
1. BACKGROUND
Sufficiently decentralized networks have the property of distributed trust (Beck et al., 2016; Dorri et al., 2017; Veloso et al., 2019). This means the network may be trusted to execute transactions honestly, even if no individual on it may be. This automated trust disintermediates traditional third-party trust-providers (e.g., banks, markets, etc.), and can operate considerably more efficiently. Bitcoin and subsequent networks like Ethereum have demonstrated global demand for this service model.
Traditionally, these networks have operated under a parallel computing model which equilibrated a trade-off between three core attributes: (i) the security and integrity of the network, (ii) its intended decentralization and trust distribution, and (iii) its overall scalability. This prompted designs in which a “choose-2” trade-off over a primary attribute evolved. First expressed by the founder and designer of the Ethereum network, Vitalik Buterin, this has become the eponymous Buterin Trilemma (Altarawneh et al., 2020).
The use of the PoW method to underpin honest consensus was developed in the Bitcoin Network (Nakamoto, 2008), which operates a computational race to find the cryptographic magic numbers required to advance the blockchain. Solving for these numbers requires substantial computing power demanding a proportionally large amount of electrical power; in effect, Bitcoin encapsulates this consumed electrical power, akin to the energy encapsulation (as labor, fuel, and materials) in gold mining. This investment seeks to align the incentives of network node-owners around compliant transaction processing. This serves as the basis for the network’s distributed trust property and is an innovation in econophysics as much as in computer science.
Unfortunately, the PoW model is intrinsically inefficient. The central Bank of Canada found that operating the Canadian economy on Bitcoin would require 26.3 times the entire power consumption of the country (Chapman & Wilkins, 2019) and currently that network consumes more electrical power than industrialized Sweden (Rauchs et al., 2021). Although this ratio may improve, research into energy consumption as a “Granger-cause” for GDP growth suggests that the available useful energy (in quality-indexed British thermal units) to such an economy would need to expand infeasibly to satisfy the utility promised by such PoW models (Cleveland et al., 2000). One may draw the clear conclusion that Bitcoin cannot plausibly underpin a majority of economic transactions and may continue to prove problematic in other derivative PoW networks, including Ethereum. PoS systems (Buterin & Griffith, 2017; Zamfir et al.) displace this physical investment with economic investment. Given that the investment is indirect, PoS appears more efficient, but purchasing stake substitutes primary electrical power for derivative economic power. Under current economic theory (ref. Cleveland et al., 2000), economic power follows available energy inputs into that economy. Thus, PoS’s extensible utility and economic value still require at least proportional energy to maintain security properties as demand rises.
This energy problem is a serious concern, but more important is the second-order effect of these costs, which provide economies of scale to rent-seeking network participants through cost-reduction methods (e.g., larger mining operations) and revenue-maximization (as mining pools) (Lin William Cong et al., 2019). These have driven consolidation of network ownership, which is an expected economic process. However, in the case of open blockchain networks, centralization erodes the distributed trust property and thereby reduces the network’s intended value (Swanson, 2014). Currently, just three major mining pools control over 50% of Ethereum, and just four control over 50% of Bitcoin; indeed, “51% attacks” have already been successful against smaller blockchains such as Ethereum Classic (Jenkinson, 2019) and Bitcoin Gold. Without the physical constraint of building mining infrastructure, PoS networks are likely to centralize even faster. If open blockchains are to be universally accepted as an economic medium, then not only must node-ownership be widely distributed, it must remain so in the face of centralizing forces (see Figure 1).
To prevent this, node-owners must be structurally prevented from collusive coalitions; but even absent collusion, node operators in PoW and PoS systems have available to them mechanisms to maximize their private profit at the expense of network clients (Eskandari et al., 2019).
1.1. Problem Definition
In order to provide sustainable distributed trust, a network must resolve the Buterin Trilemma (Figure 2), simultaneously providing:
(i) Decentralization — Network membership must be available to any node of computing power, O(c)[1];
(ii) Scalability — The entire network must have computing power O(n)>O(c), where n equals network membership and O(n) is its computing power, which suggests an ability to process transactions in parallel; and,
(iii) Security — Any malicious actor (as Adversary) must have computational power >O(n) to compromise the integrity of the network.
In operation, the network must be provably secure and demonstrably decentralized in order to underpin transactions effectively, meaning scalability is the necessary sacrifice (Monte et al., 2020). Moreover, the decentralization property must hold against the pressure of economies-of-scale pressure and other external forces.
2. DANDELION PROPOSAL
We propose the Dandelion Network which can solve the Trilemma under a model which presumes its nodes and clients are (i) economically rational and (ii) exist in the real world, with the assumption set:
1. Senders expect an external gain-in-trade and thus seek to clear transactions they have initiated.
2. Receivers expect to become Senders in the future (undefined) and thus seek to settle inbound transactions and to deposit proceeds into their accounts.
3. Nodes are a special subset of Receivers and are rewarded (incentivized) for processing transactions. Reward for correct and compliant processing must exceed the potential external reward for any other behavior within their choice set.
To achieve this, the Dandelion transaction network implements three key improvements to conventional blockchain technologies:
(i) Architecture — a Transaction-Linked Directed Acyclic Graph (TL-DAG) for fully parallel processing,
(ii) Consensus — a Client-Leader Consensus Model which offloads bandwidth requirements from nodes to clients to increase throughput, and
(iii) Transaction — an Asynchronous Clear-and-Settle which decouples the clearing and settlement mechanisms, and allows cross-shard transactions.
These technologies are mutually enabled. Collectively, they achieve clear-and-settle of transactions in less than one second at very high network throughput and unrestricted scaling.
Note on cryptographic primitives and post-quantum cryptography. Dandelion requires a one-way hash function and a cryptographic signature scheme. The system is operationally agnostic to algorithm. In anticipation of feasible advances in quantum-computing (Easttom, 2021), we hold that any new system must be post-quantum secure, specifically that: (i) the hash function and its parameterization be secure against Grover’s Algorithm, and (ii) the signature scheme be secure against Shor’s algorithm. To meet this criterion, the reference implementation of Dandelion uses SHA-3 512 for the hash function and encrypted with the Falcon-512 post-quantum signature scheme.
3. ARCHITECTURE
3.1. Definitions
A clear is an operation in which an amount is debited from an account, creating a new balance.
A settle is an operation in which an amount is credited to an account, creating a new balance.
A transaction is a complementarily matched pair of exactly one clear and one settle operation, occurring asynchronously.
A fee is an amount charged for a transaction. Fees are burned (see Figure 3) by including them in the debited amount in clear operations but not in the credited amount of the matching settle operation.
A chain or account-chain is a set of hash-linked balances, resulting from successive clear and/or settle operations. Every transaction links to two account-chains.
A pennyjar is an unordered buffer associated with an account-chain which stores incoming transactions prior to a settle. The analogy is a tip jar which stores an unordered stream of incoming donations until the receiver can count and order them.
Pennies are incoming, unsettled transactions stored in the pennyjar.
A pennyroll is a collated and serialized list of pennies.
An account collectively describes the designated chain with its associated pennyjar and supporting metadata, controlled with the secret-key of a public-key/private-key[2] pair. The public-key is used to authorize transactions on the account by proving they are signed by the associated secret-key.
Tokens are the Dandelion network’s fungible currency as exchanged between accounts through transactions.[3]
A client is a network-connectable device which holds the private-key to an account and executing the processes required to clear and to settle transactions.
A node is a computer and which earns tokens through the ongoing maintenance of a dynamic subset of accounts and the verifying/authorizing of transactions involving its designated accounts.
Minting is the process by which nodes are rewarded tokens for execution of their activities.
A shard is a subset of nodes across which all maintain and cross-verify the same subset of accounts. The network can include an arbitrary number of shards.
The network is the full set of all shards.
3.2. Data structure
The Dandelion network’s basic structure is not a blockchain, but a Transaction-Linked Directed Acyclic Graph (TL-DAG). This differs from existing blockchain protocols in several important respects.
(i) There are many chains. Every account maintains its own account-linked transaction-chain.
(ii) There are no blocks. Each account-level transaction forms its own link in its paired transaction-chain.
(iii) Transactions are discretely matched and paired as a distributed ledger (DL). For every outgoing (cleared) transaction sent from an account-chain, there must exist a correlating incoming transaction (settled) on another account-chain. This is analogous to double-entry book-keeping.
(iv) Chains are updated through an asynchronous clear/settle protocol.
This structure produces several important advantages over conventional blockchains:
(i) Each account has its own chain, thus finalization time is limited only by available bandwidth to the client’s device;
(ii) Clearing and settling are asynchronous which allows the network to scale unrestrictedly; and,
(iii) Transactions are processed individually and in parallel, and therefore there is no opportunity for in-block front-running, empty-block mining, or Miner Extracted Value.
3.3. State Machine
Dandelion advances state using a simple state machine to implement a two-phase commit process (see Figure 4). Every node maintains a version of this state machine for every account chain in its subset of the TL-DAG. Perforated lines indicate state transitions requiring messages signed by the client’s private-key. Solid lines indicate state transitions requiring the aggregated signatures of a ⅔ majority of the nodes of the account-chain’s given shard.[4]
3.4. Node States
Finalized. The finalized state (State 0, S0) is the normal “resting” state of the state machine in which all transactions have been processed up to the current transaction number (Txi). In this state, the account balance is available, and the client may: (i) precommit to a transaction; (ii) move to the preabort state if the client wants to abort a transaction which has been precommitted on other nodes; or (iii) advance the node to any finalized state (States 1a, 1u, or 1c) upon receiving the collated verifications confirming that the majority of its shard’s nodes is advancing or has advanced its aggregate state-machines to such finalized state.
Lagging. When a node’s account-chain for a given client is not current with the majority of nodes on its shard, it is lagging. Here, a majority of nodes has already advanced through the state machine to finalize a subsequent transaction, and the lagging node may be updated (State 1u) through an authenticated update or abort request.
Precommit. The precommit state indicates that the client has requested a transaction of a node and the node has validated the transaction; but the node has not yet authenticated that the client has duplicated the request across a majority of nodes on its shard. An account on a node in precommit is locked to new transactions. It may be moved to a committed state (State 1c) through an authenticated commit request; the same holds for achieving a subsequent updated state (State 1u) through an authenticated update request (if it is lagging on one or more finalizations), or to a subsequent aborted state through a preabort request from the client, followed by an authenticated abort request (State 1a).
Preabort. The preabort state indicates that the client is cancelling an already initiated transaction. As with the precommit state, the preabort state is locked to new transactions, but may be updated with an authenticated update request if it is lagging (advance to State 1u). An authenticated abort request moves the state machine to a finalized state in which the transaction number advances but the balance is unchanged (State 1a).
3.5. Shard States
Shard state. Refers to the aggregated state of all node states for a given account. A client may not be able to contact some or all of a shard’s nodes at any given time. Thus, different nodes may be in different states with respect to the client’s account. Shards can be in one of two shard states:
Consistent. An account is in a consistent state when a simple-majority of the nodes in its shard are either in the same state or can be moved to the same state by completing a single state transition; or,
Inconsistent. An account is in an inconsistent state when it is not in a consistent state. An inconsistent state may always be brought to a consistent state by transiting the abort process. Inconsistent states are not expected in normal operations but may arise through Byzantine failure.
4. CONSENSUS
4.1. Client-Leader
Two-phase commit is a form of leader-based consensus system, in which a single machine coordinates the advance of the state machine across all nodes. Conventional leader-based systems suffer three flaws. First, the leader is in a privileged position to determine unilaterally the unique order of transactions. This is a significant problem for markets in which either the transaction order has priority consequence (e.g., time-fluctuating prices), or where the leader may wish to prevent certain transactions from proceeding at all (i.e., transaction censorship). Second, the leader represents a single point of failure. A denial-of-service attack need only target the network’s leader, a task orders of magnitude easier than attacking a majority of nodes in any large network. Most leader-based models have crash-recovery/leader-election systems to replace a failed leader rapidly, but a malicious node will be able to identify the new leader immediately as soon as the recovery process completes, and so can redirect the attack to disrupt the network continuously. Finally, the leader’s communications load rises quadratically (O(n2)) with the size of the network, which strictly limits both the number of nodes and the total volume of processable transactions.
Dandelion’s Client-Leader (see Figure 5) resolves these problems. With the Client’s account replicated across all nodes of its associated shard, the client becomes the leader for its own account-chain and is responsible for advancing the state machine across its shard. This offers several benefits. First, nodes do not and need not communicate with each other. All communications go through the client. This offloads the network’s quadratic communications (O(n2)) to the client, while the nodes’ communication load rises only as O(n) with node count, enabling a very high node count. By definition, clients process fewer transactions than the network broadly; thus, a quadratic rise in communication load at the client does not limit total network throughput. Further, each client is free to allocate resources to the system as best befits its needs, which enables many different client configurations, including direct clear-settle, gateway access, single-device and distributed-client configurations. Finally, short of complete network shutdown, leader-targeted denial-of-service attacks can only disrupt transactions on individual accounts and only until the client identifies the attack and connects via an alternative path to its nodes.
5. TRANSACTION
5.1. Asynchronous Clear-and-Settle
Dandelion prevents double-spend by locking the sender’s state machine to new transactions whilst it is in a transitional clearing state, thus allowing only one outbound transaction at a time. However, the receiver’s account-chain may receive any number of inbound transactions at once, in any order, from different subsets of nodes in different shards. Dandelion resolves this complexity by associating each client account with an unordered data buffer (i.e., “pennyjar”) which receives and stores incoming transactions for settlement (Figure 6). Upon finalization of a clear on the corresponding sender’s account, the resulting penny is transferred into the receiver’s pennyjar. Under Dandelion’s Client-Leader protocol, onus then lies with the receiver client to settle transactions onto its own account-chain.
This offers the following advantages:
(i) Sender and receiver do not have to be connected at the same time to execute the transaction.
(ii) Transactions can clear and settle across shards, allowing the network to scale unrestricted.
(iii) Senders and receivers are able to negotiate and to confirm the transaction out-of-band, using any digital or physical channel as may befit the application layer (e.g., NFC, QR code, URL, post mail, etc.).
5.2. Complete transaction sequence
Figure 7 illustrates a complete Client-Leader cross-shard transaction between sender (Alice) and receiver (Bob). Figure 7 is generalized and various permutations and configurations are readily constructed at the application layer. Importantly, under Client-Leader, clients assume responsibility for finalization. As clients will not initiate transactions which they do not intend, normal transactions will follow this generalized sequence. Reference algorithms defining sending (1–Send), request validations (2–Collect States), updating receiver account (3–Receive), and finally receiving (4–Reply), are provided in Annex A: Reference Algorithms.
5.3. Abort sequence
If a client decides not to complete a transaction which has not been precommitted on >⅔ of nodes (e.g., in the event of a disconnection or interruption), the client may choose to abort the transaction. In this case, any precommit nodes may be moved to the preabort state. On collecting >⅔ of signatures for the preabort state, the client may then move the transaction to the aborted state. The previously committed state is abandoned, and its transactions’ pennies withdrawn from the recipient pennyjar.
Throughout the abort process, it is impossible to clear any of the partially completed transactions given that >⅔ of nodes are never committed to any one of them; and it is impossible to settle any of the partially completed transactions, as none has been cleared. Per our Assumption-1 (Senders only initiate to obtain external gain-in-trade), the preceding behavior is not economically rational and thus initiated transactions will not normally be aborted.
Figure 8 shows the state progression through the abort state for a network in an inconsistent state. Note, the state number is advanced through the abort sequence, even though the balance is reverted.
5.4. Update Sequence
Nodes which are offline when a transaction is finalized will become lagging. To account for this, the state machine allows clients to update lagging nodes with verifications as signed by a >⅔ majority of nodes in the current finalized state. On receiving an update request, the nodes return the range of transaction IDs required to move the state machine from the furthest lagging state to the current state. The client then broadcasts these verifications to the lagging nodes. On receiving >⅔ verifications, lagging nodes can completely update the client’s chain for this transaction range without transiting the precommit-commit process for each link in the chain.
5.5. Byzantine Clients and Inconsistent States
A consequence of the client leader model is that clients are completely responsible for maintaining the state of their own account chain. While it is not possible for a byzantine client to finalize more than one transaction at a time, it is possible for byzantine client to put their chain in an inconsistent state. In this case the client initiates a transaction and obtains verifications from >⅔ of the nodes, but only commits the transaction for <⅔ of nodes; it may then initiate a second transaction, maximally gaining the remaining minority verifications (<⅓), which cannot be used to finalize the second transaction on any of the nodes. The client can initiate any number of transactions on a minority (<⅓) of nodes, but because the client cannot collect a ⅔ majority of verifications for such transactions, none can finalize; rather, only the first transaction can finalize, for which >⅔ have committed.
When the byzantine failure of the responsible client is cleared, the chain can be returned to a consistent state by moving the precommitted nodes through the abort cycle. Through this process no transaction can be cleared. The account chain is advanced to the next state, with balance and transaction status equal to the previous state.
5.6. Performance
Unlike conventional blockchains, Dandelion does not have an inherent transaction rate. Rather, transaction performance parameters are governed by the number of signatures per second that can be processed and transmitted. As these figures will vary across both nodes and clients, performance will also vary both between transactions and over network life.
At the node, the figure-of-merit for performance is transactions per second. For this metric, signature verification and transmission requirements both rise linearly with network size. This implies that capacity for both should match for optimal efficiency. Note that total network throughput is governed by the performance of the median node; as transactions require only strictly >⅔ consensus, clients may freely ignore slower verifications for finalization and update slower nodes later. Nodes are rewarded for participating in consensus and so are motivated to improve their performance to ensure their inclusion in settlement rounds. Assuming Falcon-512 signatures are used, Figure 9 presents the estimated transaction throughput by network size and median data-rates. At a shard size of 500 nodes, with server-grade hardware and 10Gbit connectivity and hardware, the network can process more than 3,000 transactions per second, per shard. For comparison, the VISA network averages about 1,700 transactions per second (Li, 2019).
At the client, the figure-of-merit is finalization time. For this metric, the verification load at the client is fixed and light, but transmission demand rises as the square of network size. This is a concern where mobile devices are a major client interface. These have a best-possible data-rate of approximately 1 Gbit/s on high quality 5G. Figure 10 presents the finalization time as a function of network size. From this analysis, it can be seen that good 5G connectivity allows direct peer-to-peer transaction with tap-and-pay speed on a network of 500 nodes. For clients with slower connections, Dandelion’s structure allows the use of gateways: systems configured to receive verifications on a low-speed channel once, and then rebroadcast those to the shard over a high bandwidth channel. For example, a client point-of-sale terminal configured for transaction settling over a fiber-link may provide a counterparty client on a mobile device with a high-speed connection to clear the transaction without any use of wireless connectivity. Given sufficiently large gateway bandwidth, the limitation on finalization time becomes network latency.
The flexibility of the Client Leader model allows many other arrangements to provide fast finalization to limited bandwidth clients and so enables a real-time payments platform across different value customers.
6. PROVABLE SECURITY
Provable security formally demonstrates the security properties of an algorithm via mathematical proofs which demonstrate the algorithm’s equivalence to computationally intractable problems. In current context, such intractability must include resistance to quantum computing attacks based on both Shor’s and Grover’s Algorithms (Mavroeidis et al., 2018; Vijayalakshmi & Raja, 2012).
By proving that there is a way to correspond security to computationally difficult problems absent efficient or practical solutions beyond sustained brute force attacks over infeasible time, one can be confident that the transmitted data are protected.
6.1. Security Basis: Goals, Attacks & Experiments
By constructing an adversary with a suite of capabilities, goals, and attacks, experiments can demonstrate system security. Abstract scenarios of the algorithm’s initialization, the adversary, and that adversary’s goals and powers, are represented with mathematical pseudo-code. By reduction to known computationally difficult problems, it is possible to prove that it would be statistically impossible for any adversary of presumed powers to achieve its goal(s) given the properties of the system.
6.2. Security Proof
6.2.1. Basis
Functional properties required for Dandelion’s intended and consistent operation are:
(i) Correctness: all honest participants will accept minimally well-formed messages;
(ii) Fault tolerance: the network will operate continuously in the face of arbitrary, Byzantine failure in a given subset of nodes. Nodes may be added or subtracted, and messages may not be delivered; and,
(iii) Decidability: the network will eventually accept all honest transactions while all dishonest transactions are eventually rejected.
Security properties required for Dandelion’s intended and consistent operation are:
(iv) Unforgeable transactions: an adversary, with some number of corrupted nodes, cannot issue transaction requests that can finalize on behalf of uncorrupted nodes;
(v) Non-repudiation: an adversary, with some number of nodes corrupted, cannot issue abortion requests that can finalize on behalf of uncorrupted nodes;
(vi) Unforgeable collection: an adversary, with some number of nodes corrupted, cannot issue a request for a pennyjar from honest nodes that causes honest nodes to return the corresponding pennyjar;
(vii) Immutability: an adversary, with some number of nodes corrupted, cannot modify existing account-chains; and,
(viii) Quantum-resistance: the above properties must hold in the presence of an adversary with quantum-computing capabilities.
6.2.2. Analysis
Dandelion satisfies correctness. This was verified by demonstrating that all well-formed honest messages are always accepted by honest nodes. Next, the network’s fault tolerance threshold — that being the point at which the adversary has final control over whether any transaction is processed or not — was determined. Assuming an adversary acts below this threshold, decidability was finally verified.
Combining the network’s model with these criteria, the capabilities of an adversary that would seek to undermine the network’s functionality and security were outlined to define the network’s attack vulnerabilities — this includes the computational powers of the adversary and its network interaction. Examples of adversarial powers include generating new nodes (e.g., a Sybil attack), seizing other nodes (e.g., session hijacking), or temporarily denying other nodes (e.g., distributed denial-of-service, isolation attack). To represent these various adversarial abilities experimentally, a series of black box functions, or oracles, representing the network was used. Each oracle represents a single action for either the network or adversary and updates the networks state in response. These oracles give the adversary the ability to add, to corrupt, or to temporarily offline any node as it wished. Adding or corrupting a node granted the adversary all private information (e.g., private-keys) and privilege over a node’s response to any request, arbitrarily. Additionally, oracles were assigned generation and viewing over each message and response to any request from honest nodes, could request transactions from honest nodes, and could view all node histories. Collectively, these oracles allowed the adversary to simulate Dandelion’s network at will throughout experimentation, and reflected real-world adversaries attempting to undermine the network.
Also defined was a series of adversary goals to reflect failures for each property of Dandelion’s required security. For unforgeable transaction, unforgeable collection, and non-repudiable properties, the experimental goal of the adversary is to produce a valid request: the adversary must attempt to produce a request message on behalf of a node it does not control, and one which the rest of the network would accept. The goal of the immutability security experiment is to produce a replacement for an existing block in any account-chain which could hash to the correct value in the next sequential block.
Finally, each goal-oriented security experiment was analyzed using an appropriately empowered adversary with influence below the fault tolerance threshold. Dandelion successfully demonstrated that each of its security properties are tied to its two cryptographic components: digital signature algorithms and collision-resistant hash functions. More specifically, construction of the proof demonstrated that any adversary which could successfully undermine any security property, could then forge digital signatures and/or produce collisions for the hash function, as this would demonstrate it could convert such success into a method to break a known secure cryptographic algorithm. However, if the digital signature and hash function are secure then this is infeasible to achieve. Thus, by using quantum-computing resistant signature algorithms and hash functions, Dandelion inherits their security and becomes provably secure.
6.3. Security Model
Add. Creates a new node under the adversary’s control and checks whether the new node gives the adversary ⅓ control of the network; if not then adds the node, else rejects.
Corrupt. Gives the adversary control of a given node and its private-keys.
Down. Offlines a node for the next transaction it would have otherwise received.
TxInitate. Adversary creates a request for some amount from an account; account-holder may arbitrarily decide to accept, and thus builds the transaction request, returning it to the adversary.
BuildTx. Adversary builds its own transaction on behalf of a corrupted node and returns it to the adversary.
TxAuthorize. Returns the response of honest nodes to a transaction request.
TxFinalize. Creates a finalized transaction message. Requires a transaction and a list of responses from both honest and corrupted nodes.
TxComplete. Completes a transaction based on a TxFinalize message, writes to the correct chain, and adds the penny to the receiver’s pennyjar.
AbortTx. Creates an abortion message for an existing transaction.
AbortConfirm. Returns the response to an abortion request from honest nodes.
AbortFinalize. Creates a finalized abortion message for a confirmed abortion request. Requires a transaction and a list of responses from both honest and corrupted nodes.
AbortComplete. Completes the abortion; removes the transaction from the corresponding pennyjar; and updates the state of the sender.
RequestPennyJar. Creates a request to collect an account’s pennyjar from the honest nodes.
SendPennyJar. Returns each node’s pennyjar for the account.
OrderPenny. Returns the ordered list of pennies according to the account-chain.
CollectPenny. Sends the ordered list of pennies to the nodes in the network to be completed, updating the requester’s account-chain, balance, and status.
TxHistory. Returns the ith transaction of an account-holder.
BlockHistory. Returns the jth block in an account-chain.
Hash. Computes the hash of the input.
6.4. Adversary
An adversary reflective of real-world malicious intent was defined, constructed, and enabled with such interactions as would be available — specifically, any means to induce potential malicious messaging (e.g., creating false transaction requests, attempts to cancel valid transactions, etc.), to subvert users (e.g., collect others’ account values), or to corrupt the network’s consensus algorithm (e.g., generate new nodes, seize existing nodes, offline other nodes, etc.).
The oracles were enabled on the network. Along with these oracles we defined a series of goals for an adversary with these oracles to achieve. Each goal corresponds to each of the properties previously defined and is presented in the form of a cryptographic experiment. These experiments form a standard framework for security analysis to be done on various protocols and allows for mathematical techniques to be applied to demonstrate provable security. In each of these experiments the adversary is given access to the oracles and time to perform polynomial many queries. Eventually, the adversary must request a challenge, where they receive an honest node’s public account information and must achieve the prespecified goal without corrupting the honest node to trivially receive the node’s private information. Once the adversary is given the challenge, they are given back access to the oracles.
For the unforgeable transaction experiment, the adversary must create a new transaction request on behalf of the honest node that the network accepts and finalizes. This includes all the responses for corrupted nodes.
In the nonrepudiation experiment, when the adversary requests the challenge, they are given an honest node’s public information and a transaction the node has created; the adversary must produce an abort transaction request that is accepted by the network.
In the unforgeable collection experiment, the adversary must create a new transaction request on behalf of the honest node that the network accepts and finalizes.
In the immutability experiment, the adversary attempts to replace an existing block in any user’s chain with a different block that hashes to the correct value in the next sequential block.
6.5. Proof Results
6.5.1. Functionality
Correctness: By the definition of how messages are structured and checked, all well-formed messages are accepted by honest nodes. Malformed messages are rejected.
Fault Tolerance: By controlling ⅓ of nodes, the adversary can completely control the network by accepting or rejecting everything. At exactly ⅓, the adversary can deadlock the network; and <⅓, the adversary cannot.
Decidability: If the adversary has <⅓ control of the network then there are enough honest nodes to accept or reject requests. By correctness we get decidability.
6.5.2. Security
Unforgeable Transactions: There exists a reduction to the security of the signature security. If the adversary can forge transactions that are accepted then they must be creating forged signatures.
Nonrepudiation: There exists a reduction to the security of the signature security. If the adversary can forge abort requests that are accepted then they must be creating forged signatures.
Unforgeable Collection: There exists a reduction to the security of the signature security. If they can forge requests to collect pennyjars that are accepted then they must be creating forged signatures.
Immutability: If the adversary can replace blocks in the user’s account-chains then they must be able to produce a hash collision. We demonstrate a reduction to the security of the collision free hash function.
Quantum Resistance: We assume the adversary is capable of local quantum computing in all proofs.
In an upcoming paper (Goncalves & Mashatan, 2021), our contributing authors will further present the security proof that Dandelion satisfies each property, particularly as pertains to a quantum-computing enabled adversary’s attempt to penetrate current art cryptographic algorithms for digital signatures and secure hashing algorithms. Summarily:
§ Correctness is demonstrated by the deterministic construction of the protocol and that proper request messages satisfy verification for nodes to execute these requests.
§ The fault tolerance threshold analysis confirms Dandelion has a ⅓ threshold. An adversary necessarily requires >⅓ to decide acceptance/rejection of requests, and at exactly ⅓ may deadlock the network. Remaining properties are proven against adversaries at <⅓ control.
§ Dandelion’s security is proved against an adversary represented by a probabilistic polynomial time algorithm over the inputs it is given. The adversary is assumed local quantum capabilities which allow computation of superposition calculations and any polynomial time algorithm (e.g., Shor’s algorithm and Grover’s search). The adversary may also compute hashes in superposition.
§ To the digital signature’s security, the following properties are tied: unforgeable transactions, nonrepudiation, and unforgeable collections; to the collision-resistant hash function, immutability. Mathematical reduction therefrom implied the existence of an algorithm that can forge signatures. However, if the digital signature algorithm is existentially unforgeable then no such algorithm exists, thus there is no attacker that can forge these requests.
§ A similar approach is used for the immutability of the user’s account-chain. Here, an adversary may modify an existing user’s account-chain. The adversary produces a collision for the hash function as each block is hashed with the next transaction to link sequential blocks. Thus, if there is such an adversary capable of producing and replacing blocks, there exists an algorithm to produce collisions for the same hash function.
Thus, by using quantum-computing resistant signature algorithms and hash functions, Dandelion’s functionality and security properties hold against adversaries with arbitrary quantum-computing power.
7. CONCLUSION
The Dandelion network provides a resolution to the Buterin trilemma by: (i) employing a Transaction-Linked Directed Acyclic Graph rather than a traditional blockchain, (ii) empowering a Client-Leader consensus mechanism which both retains sufficiency of trust properties while offloading the bandwidth demands onto the participating clients, and (iii) decoupling the clearing and settling of transactions such that asynchronous requests and approvals are intrinsically managed. Moreover, these characteristics are built (iv) using a post-quantum cryptographic model. Collectively, Dandelion enables a transaction method with real-time finalization and with highly scalable transaction throughput.
Dandelion will provide a superior mobile P2P network for transacting application layers for which existing distributed application operators may dramatically offset the risks and costs posed by finalization fees (gas costs), network seizure and centralization (consensus risk), and frontrunning and collusive activities (transaction vulnerabilities).
8. ACKNOWLEDGEMENTS
The authors would like to acknowledge the ongoing support of Dr. Peter Gregson, Dalhousie University, without whom this project would never have been possible.
9. BIBLIOGRAPHY
Altarawneh, A., Herschberg, T., Medury, S., Kandah, F., & Skjellum, A. (2020). Buterin’s Scalability Trilemma viewed through a State-change-based Classification for Common Consensus Algorithms. 2020 10th Annual Computing and Communication Workshop and Conference (CCWC), 0727–0736. https://doi.org/10.1109/CCWC47524.2020.9031204
Anjum, A., Sporny, M., & Sill, A. (2017). Blockchain Standards for Compliance and Trust. IEEE Cloud Computing, 4(4), 84–90. https://doi.org/10.1109/MCC.2017.3791019
Beck, R., Czepluch, J. S., Lollike, N., & Malone, S. (2016). Blockchain — The Gateway to Trust-Free Cryptographic Transactions. 15.
Bellini, E., Iraqi, Y., & Damiani, E. (2020). Blockchain-Based Distributed Trust and Reputation Management Systems: A Survey. IEEE Access, 8, 21127–21151. https://doi.org/10.1109/ACCESS.2020.2969820
Buterin, V., & Griffith, V. (2017). Casper the Friendly Finality Gadget (p. 10). Ethereum Foundation. https://allquantor.at/blockchainbib/pdf/buterin2017casper.pdf
Chapman, J., & Wilkins, C. A. (2019). Crypto ‘Money’: Perspective of a Couple of Canadian Central Bankers. 33.
Cleveland, C. J., Kaufmann, R. K., & Stern, D. I. (2000). Aggregation and the role of energy in the economy. Ecological Economics, 32(2), 301–317. https://doi.org/10.1016/S0921-8009(99)00113-5
Dorri, A., Kanhere, S. S., & Jurdak, R. (2017). Towards an Optimized BlockChain for IoT. Proceedings of the Second International Conference on Internet-of-Things Design and Implementation, 173–178. https://doi.org/10.1145/3054977.3055003
Easttom, W. (2021). Modern Cryptography: Applied Mathematics for Encryption and Information Security.
Eskandari, S., Moosavi, S., & Clark, J. (2019). SoK: Transparent Dishonesty: front-running attacks on Blockchain. ArXiv:1902.05164 [Cs]. http://arxiv.org/abs/1902.05164
Goncalves, B., & Mashatan, A. (2021). On the Security of Dandelion. -.
Jenkinson, G. (2019, January 10). Ethereum Classic 51% Attack — The Reality of Proof-of-Work. CoinTelegraph. https://cointelegraph.com/news/ethereum-classic-51-attack-the-reality-of-proof-of-work
Karame, G., & Capkun, S. (2018). Blockchain Security and Privacy. IEEE Security & Privacy, 16(4), 11–12. https://doi.org/10.1109/MSP.2018.3111241
Konstantopoulos, G. (2018, January 23). Scalability Tradeoffs: Why “The Ethereum Killer” Hasn’t Arrived Yet. https://medium.com/loom-network/scalability-tradeoffs-why-the-ethereum-killer-hasnt-arrived-yet-8f60a88e46c0
Li, K. (2019, January 30). The Blockchain Scalability Problem & the Race for Visa-Like Transaction Speed. https://towardsdatascience.com/the-blockchain-scalability-problem-the-race-for-visa-like-transaction-speed-5cce48f9d44
Lin William Cong, He, Z., & Li, J. (2019). (NBER Working Paper Series, p. 55). National Bureau of Economic Research. https://www.nber.org/system/files/working_papers/w25592/w25592.pdf
Mavroeidis, V., Vishi, K., D., M., & Jøsang, A. (2018). The Impact of Quantum Computing on Present Cryptography. International Journal of Advanced Computer Science and Applications, 9(3). https://doi.org/10.14569/IJACSA.2018.090354
Monte, G. D., Pennino, D., & Pizzonia, M. (2020). Scaling Blockchains without Giving up Decentralization and Security: A Solution to the Blockchain Scalability Trilemma. Proceedings of the 3rd Workshop on Cryptocurrencies and Blockchains for Distributed Systems, 71–76. https://doi.org/10.1145/3410699.3413800
Nakamoto, S. (2008). Bitcoin: A Peer-to-Peer Electronic Cash System. 9.
Rauchs, M., Blandin, A., Dek, A., & Wu, Y. (2021, May 6). University of Cambridge, Judge School of Business, Centre for Alternative Finance: Cambridge Bitcoin Electricity Consumption Index — Country Ranking. University of Cambridge — Judge School of Business, Centre for Alternative Finance: Cambridge Bitcoin Electricity Consumption Index. https://cbeci.org/cbeci/comparisons
Swanson, T. (2014). Bitcoin Hurdles: The Public Goods Costs of Securing a Decentralized Seigniorage Network which Incentivizes Alternatives and Centralization. http://www.ofnumbers.com/wp-content/uploads/2014/04/Bitcoins-Public-Goods-hurdles.pdf
Veloso, B., Leal, F., Malheiro, B., & Moreira, F. (2019). Distributed Trust & Reputation Models using Blockchain Technologies for Tourism Crowdsourcing Platforms. Procedia Computer Science, 160, 457–460. https://doi.org/10.1016/j.procs.2019.11.065
Vijayalakshmi, P. R., & Raja, K. B. (2012). Performance analysis of RSA and ECC in identity-based authenticated new multiparty key agreement protocol. 2012 International Conference on Computing, Communication and Applications, 1–5. https://doi.org/10.1109/ICCCA.2012.6179168
Zamfir, V., Rush, N., Asgaonkar, A., & Piliouras, G. (n.d.). Introducing the “Minimal CBC Casper” Family of Consensus Protocols. 29.
Zinsmeister, N., & Robinson, D. (n.d.). Hayden Adams hayden@uniswap.org. 10.
[1] In computer science, “Big-O” notation is typically used to relate functions tending toward limits, infinities, or asymptotes, such as computing power, storage constraints, network growth, algorithm run-time, etc. Here, we describe the limiting relationship amongst the Trilemma’s determinants.
[2] Dandelion abbreviates “public-key” to PK and “private-key” to “SK” using the classical “secret-key” terminology. Private-key and secret-key are used interchangeably.
[3] Internally, the Dandelion network’s tokens are called Pennies; but to avoid confusion, any use of Pennies in this document strictly refers to the backlog of incoming, unsettled transactions.
[4] In balancing the tradeoff between liveliness and safety when contending with byzantine failures, as a deterministic system, Dandelion uses 3f+1 which derives to the “>2⁄3 majority” consensus threshold.
