On the Security of the Dandelion Protocol

Abstract

In this paper, we review the peer-to-peer blockchain transaction protocol, Dandelion, and develop an oracle-based model for its network and security. We formalize a series of security and functional criteria, such as unforgeability, non-repudiation, and immutability, into security experiments. In our model, we consider a quantum-capable adversary who seeks to undermine any of the security criteria while using oracles to simulate and interact with the Dandelion network. We then prove the security of Dandelion in our model with a series of (tight) security reductions as our main result. In addition, we prove that Dandelion is resistant to double-spending attacks.

1. Introduction

Since the release of the Bitcoin paper by Nakamoto [1], blockchain technology has experienced rapid growth in both academic and industry interest. Numerous protocols, such as Ethereum [2], Ripple [3], Phantom [4], HyperLedger [5], and Ouroboros Praos [6], have presented different approaches to the decentralized/distributed nature of blockchain technologies and digital currencies. These protocols present blockchain solutions with different modifications and restrictions on who may join the network, participate, or submit blocks.

While the above represents a small sample of the more famous protocols, the development and adoption is likely to continue to grow in the longer term due to the significant interest from industry. In their 2020 global blockchain survey, Deloitte polled nearly 1400 executives across 14 countries, and 53% responded that blockchain technology was listed among their top strategic priorities [7]. Moreover, nearly a third stated that their company was in development of a blockchain-related project, and 84% indicated that they already use blockchain technology to some extent. Lastly, in their survey, Deloitte estimated that global spending on blockchain solutions will exceed USD 11 billion. Furthermore, the application of blockchain has spread beyond just financial use as a result of extended research conducted on its application to electronic health records [8,9], supply chain management [10,11], and smart cities [12].

These figures and estimates demonstrate that blockchain technology will continue to expand and become increasingly prevalent globally. As such, there is, then, a matching need for these protocols to be provably secure and trustworthy in the long-term. This last criteria of long-term security and trustworthiness is especially vital with the advancements in quantum computers. The existence of Shor’s algorithm [13] and the Grover search [14] undermine the security of currently deployed cryptographic algorithms. Shor’s algorithm provides quantum computers the ability to recover the secret keys used for both encryption and signing for both RSA and ECC systems. The Grover search can be used to find collisions in hash functions, which are used to ensure the immutability of the blockchain. Thus, any current, and more importantly, future blockchain protocols must consider the potential of quantum-based attacks.

1.1. Our Contributions

In this paper, we present formal proofs of security for the Dandelion blockchain protocol. The Dandelion protocol is designed to be a mobile peer-to-peer transaction application that allows for asynchronous payment requests and deposits [15]. More specifically, we review the protocol and define a set of properties necessary for both functionality and security in the asynchronous, distributed network of Dandelion. To do so, we define a series of black-box oracles that would allow a (potentially quantum) adversary to simulate the entire network, and a set of security experiments that capture our defined properties. Briefly, these criteria include fault tolerance, decidability, unforgeability, non-repudiation, immutability, and double-spending. We then present direct, tight security proofs against a quantum-computing-capable adversary for each of the outlined criteria.

1.2. Paper Organization

The organization of this paper is as follows. In Section 2, we review the necessary background notation and cryptographic algorithms used in this paper and the Dandelion protocol. In Section 3, we outline the network model, a description of users, a summary of Dandelion’s message flows, and a brief discussion of the key differences between Dandelion and other protocols. In Section 4, we define our security model for Dandelion, including a formal description of adversarial powers, via oracles and goals. In Section 5, we then prove both the functional and security properties of Dandelion in our model. We conclude our paper in Section 6. In Appendix A, we provide a detailed description of how messages are handled. In Appendix B, we describe how out-of-sync nodes are dealt with in our oracle model.

2. Prelimaries

In this section, we introduce the notation used in this paper, and the necessary cryptographic algorithms used in the Dandelion protocol. We will first review the notation for (cryptographic) algorithms, sampling, and negligible functions.

This section introduces the notation used in this paper and the necessary cryptographic algorithms used in the Dandelion protocol. First, we will review the notation for (cryptographic) algorithms, sampling, and negligible functions.

2.1. Notation

By $y\leftarrow \mathcal{A}(x)$ we denote an algorithm, $\mathcal{A}$, that runs on input x and output y. When $\mathcal{A}$ has access to an oracle, $\mathcal{B}$, that it may query, we write this as $\mathcal{A}{(x)}^{\mathcal{B}(·)}$. If $\mathcal{A}$ is an algorithm that uses some randomness in its execution on input x and we wish to specify what the randomness is, say r, we denote it as $\mathcal{A}(x;r)$. We will refer to specific subroutines within $\mathcal{A}(·)$ as $\mathcal{A}.\mathsf{Subroutine}$. We will consider all adversaries as probabilistic polynomial time (PPT) algorithms on their input length.

We write $x\leftarrow \$S$ to denote that x was outputted by S probabilistically, where if S is some algorithm, then x was selected according to some internal distribution, and if S is some space, such as ${\{0,1\}}^l$, then we implicitly mean for x to be sampled uniformly at random.

We say a function g mapping non-negative integers to non-negative reals is called negligible, if for all positive numbers c there exists an integer ${\lambda }_0(c)\ge 0$, such that for all $\lambda >{\lambda }_0(c)$, we have $g(\lambda )<\frac{1}{{\lambda }^c}$.

2.2. Digital Signatures

Next, we outline the core asymmetric cryptographic component of Dandelion.

Definition 1 (Digital Signature Algorithms).

We say a triple of algorithms Σ = ($\mathsf{KeyGen}$, $\mathsf{Sign}$, $\mathsf{Verify})$ form a digital signature algorithm (DSA) scheme, if:

• $\mathsf{KeyGen}$: The key generation algorithm is a probabilistic algorithm which on input $1^{\kappa }$$(n\in \mathbb{N})$ outputs a related pair, $(pk,sk)$, of public verification and secret signing keys;
• $\mathsf{Sign}$: The signing algorithm is a probabilistic algorithm that takes two inputs, a secret signing key $sk$, and a plaintext message m, from a designated message space, ${\mathcal{M}}_{\Sigma }$, and outputs a signature σ;
• $\mathsf{Verify}$: The decryption algorithm is a deterministic algorithm that takes as input a public verification key $pk$, a plaintext message m, and a signature σ, and returns either a 0 if rejected, or a 1 if accepted.

We now define our security notions for DSAs.

Definition 2 ($\mathsf{EUF}\text{-}\mathsf{CMA}$Security for DSAs).

We say that a DSA, Σ, is $\mathsf{EUF}\text{-}\mathsf{CMA}$-secure if, for all adversaries $\mathcal{A}$, we have that:

$${\mathsf{Adv}}_{\Sigma }^{\mathsf{EUF}\text{-}\mathsf{CMA}}(\mathcal{A})=Pr[{\mathsf{Expt}}_{\Sigma }^{\mathsf{EUF}\text{-}\mathsf{CMA}}(\mathcal{A})\to 1]$$

is a negligible function in κ, where ${\mathrm{Expt}}_{\Sigma }^{\mathsf{EUF}\text{-}\mathsf{CMA}}(\mathcal{A})$ is defined in Figure 1.

2.3. Hash Functions

For the purposes of this paper, when we refer to a hash function, we are specifically referring to an unkeyed compression function, which takes strings of arbitrary length and outputs digests of some fixed length l. Furthermore, when we informally refer to a secure or good hash function, we mean a hash function that is collision-resistant, that is, it should be infeasible for an adversary to produce two different messages $m_0,m_1$ that evaluate to the same digest. We now formalize the notion of a family of collision-resistant of hash functions.

Definition 3.

Let $\mathcal{H}$ be a family of functions $\mathcal{H}={\cup }_n{\{H_i:{\{0,1\}}^{*}\to {\{0,1\}}^l\}}_{i\in \mathcal{I}}$. We call this family of functions a family of collision-resistant families of hash functions if:

• There is a PPT time algorithm to sample $H_i\in \mathcal{H},\forall i\in \mathcal{I}$;
• Given $m,i$, $H_i(m)$ can be computed in poly-time;
• For all adversaries $\mathcal{A}$, and $\forall i\in \mathcal{I}$, we have that

  $${\mathsf{Adv}}_{\mathcal{H}}^{\mathrm{collision}}(\mathcal{A})=Pr[{\mathrm{Expt}}_{\mathcal{H}}^{\mathrm{collision}}(\mathcal{A})\to 1]$$

  is a negligible function, where ${\mathrm{Expt}}_{\mathcal{H}}^{\mathrm{collision}}(\mathcal{A})$ is defined in Figure 2.

3. The Dandelion Protocol

In this section of the paper, we outline the users and network settings of the Dandelion protocol [15], the protocol itself, the message flows, and the data structure.

3.1. Network and Users

The fundamental network structure of Dandelion is that of an asynchronous, open network, where users, or nodes, may join the network at any time, and may participate in any number of requests they choose. More precisely, by asynchronous we mean that there is no shared network clock, and that communication between clients and nodes can be responded to by the other at any point in time. This description also allows for situations where nodes may adaptively go on- or offline, including because of crashes, disconnections, or other reasons [15].

The network is parameterized by the following: a list of all users and all related information $\mathbb{U}$, an existentially unforgeable under chosen message attack ($\mathsf{EUF}\text{-}\mathsf{CMA}$-secure) digital signing algorithm (DSA) $\Sigma$, a collision-resistant hash function $\mathsf{Hash}$, and a variable that denotes the maximum number of unclaimed transactions a user may have at once $\left|{max}_{\mathrm{PJ}}\right|$. We refer to a user’s unclaimed transactions as the user’s penny jar.

Users, $\mathsf{U}$, in the Dandelion protocol are parameterized by the following:

Keys: 

A pair of $\Sigma$ keys $(p{k}_U,s{k}_U)$, where $sk$ remains private, and $pk$ acts as part of $\mathsf{U}$’s public account ID;

Shard 

Id: ${\mathsf{Shard}}_{\mathsf{id}}$, a parameter to denote which “shard” of the network the user belongs to. Shards are finite collections of users and are assigned to users as they join the network using a proprietary technology not discussed in this work. A specific users’ shard ID is denoted as ${{\mathsf{Shard}}_{\mathsf{id}}}^{\mathsf{U}}$;

Balance: 

The user’s account balance, denoted by $\mathsf{Balance}$. When we refer to a specific users’ balance, we will use the notation ${\mathsf{Balance}}^{\mathsf{U}}$;

Transaction 

Id: The number of sent transactions the user has completed is denoted by $\mathsf{TxID}$, which is updated incrementally as new transactions are completed. To refer to a specific i-th transaction number, we adopt the notation ${\mathsf{Tx}}_{\#i}$. In cases where we wish to refer to the transaction of a specific user, we denote it as ${\mathsf{TxID}}^{{\mathsf{U}}_A}$, and likewise for ${\mathsf{Tx}}_{\#i}^{{\mathsf{U}}_A}$. We also use the notation ${\mathsf{U}}_A.\mathsf{TxID}$ to denote a ${\mathsf{U}}_A$’s transaction ID according to the internal state of another node;

Status: 

$\mathsf{Status}$ represents what state the user is in from the view of a different node. Each user has three possible states: $\mathsf{Locked}$, $\mathsf{Unlocked}$, and $\mathsf{PreAbort}$. When a node is $\mathsf{Unlocked}$, the node is free to create new transaction requests to send to the network. When a node is $\mathsf{Locked}$, the rest of the nodes will reject transaction requests from it until the status is changed to $\mathsf{Unlocked}$. $\mathsf{PreAbort}$ is the state nodes are set to when their transaction requests have been denied. Once a transaction request has been denied, the node must send out an abort request to the network, to which their status is set to $\mathsf{PreAbort}$. The node must then receive enough authorizations to abort the transaction and then send all authorizations to the network to become $\mathsf{Unlocked}$. When we refer to a specific user’s status, we will use the notation $\mathsf{U}.\mathsf{Status}$;

Penny 

Jar: ${\mathsf{PJ}}^{}$, a collection of non-redeemed transfers to the user, called pennies. This list is held by the other nodes of the network. Each penny in the penny jar is denoted by $p^i$. Each element is of the form $p^i=(\mathrm{penny},\mathrm{block}\mathrm{header})$. A formal description of a penny and block header are included in Figure 3. When we refer to a specific user’s penny jar, we denote it as ${\mathsf{PJ}}^{\mathsf{U}}$. We note that different nodes may have differing penny jars for the same user $\mathsf{U}$. To differentiate the source of the penny jar (penny) we denote it as ${\mathsf{PJ}}_{{\mathsf{U}}_i}^{}$ ($p_{{\mathsf{U}}_i}$);

Blocks: 

The record of transactions which the user has participated in. We use $\mathsf{Chain}$ to denote the complete set of all transactions, or blocks, in a user’s chain in sequential order, and ${\mathsf{B}}_i$ to refer to the i-th block of the user’s chain. We will also adopt the notation of ${\mathsf{B}}_{\mathsf{\Omega }}$ to refer to the last block currently part of a user’s chain. When we need to distinguish multiple users’ chains (blocks) we use the notation ${\mathsf{B}}^{\mathsf{U}}$$({\mathsf{B}}_i^{\mathsf{U}})$. A description of a block and the block header are provided below, in Figure 3. We note here an important difference between Dandelion and other traditional blockchains: while other blockchains’ blocks are collections of global transactions, in the Dandelion protocol, each user has their own individual chain, where each block is a single transaction.

We assume every node maintains a list of all the publicly available information above (i.e., all information barring the users’ secret key) for each other user that is efficiently searchable on inputs $(p{k}_{\mathsf{U}},{\mathsf{Shard}}_{\mathsf{idU}})$. We call this list the node list, $\mathcal{U}$. Whenever a node joins the network, we assume that they obtain a node list generated from $\mathbb{U}$ at the time of joining. In the real-world setting, when a node wishes to join the network, they would use discovery channels to download a copy of other existing node lists (signed by the providing node), and collate these lists to create and publish their own node list. Moreover, in real-world applications, nodes would continuously update and publish their node list while participating in network validation to determine the approximate number of total online nodes. This is used so that nodes can determine whether a transaction has received enough responses and authorizations for finalization. To see why this is necessary, consider a transaction created by an adversary that is sent to one honest node and two corrupted nodes. The adversary can trivially create a scenario where a fake transaction has a consensus of approval from the responses collected. However, as the transaction is fake, it should not be possible for fabricated transactions to obtain majority approval. Thus, utilize each node’s node list to prevent this curating of biased responses.

3.2. Message Flows

We now briefly introduce Dandelion, a permissionless directed acyclic graph (DAG) blockchain protocol, and its message flows, with a series of figures. For readability considerations, we split the complete Dandelion protocol into three sub-protocols: transaction requests, abort requests, and collection requests. We then describe the sub-protocol with three figures: message descriptions, message flows, and how each message is handled. We provide the descriptions for how messages in each sub-protocol are handled in Appendix A.

We begin with the transaction request aspect, as described in Figure 4 and Figure 5, and process according to Figure A1, Figure A2 and Figure A3. The abort sub-protocol is described in Figure 6 and Figure 7, and process according to Figure A4, Figure A5 and Figure A6. Finally, the collection pennies sub-protocol is described with Figure 8 and Figure 9, and process according to Figure A7, Figure A6 and Figure A9.

3.3. Data Structure

Unlike traditional blockchain protocols, which make use of linear chains and have potential new blocks compete for consensus to be added to the single chain each round, Dandelion uses the structure of a DAG. The DAG structure seeks to offer faster confirmation times and increased scalability than traditional linear blockchains without compromising security. In the last several years, there has been an increasing number of protocols built upon DAGs [4,16,17,18,19,20].

DAGs consist of a point set $\mathcal{V}$ and an edge set $\mathcal{E}$. Each tuple $(u,v)$ in the edge set represents a partial-order relationship between u and v, where order is defined as a directed path between u and v.

In the case of Dandelion, each element in the point set corresponds to a transaction $\mathsf{Tx}$, and the directed path or order means that one transaction is linked to another. Furthermore, each user has their own DAG, and for every transaction there must exist a discretely matched pair of transactions from the sending account and the receiving account. Finally, Dandelion allows for these transaction blocks to be created asynchronously.

3.4. Comparisons

We now briefly highlight the unique structural features of Dandelion regarding other DAG-based protocols. We note here that a true comparison between Dandelion and other protocols is not truly possible on a structural level, and a performance comparison is outside the scope of this paper; the main goal of this paper is to prove the security of Dandelion in our model described in Section 4.

Unlike other peer-to-peer protocols, Dandelion operates on an individual level, and does not have a global or network-wide shared ledger of transactions. Instead, each account has its own chain recording each transaction they have participated in, which is stored on the network nodes. Furthermore, each account holder is responsible for advancing the state of their own chain, rather than a protocol determining when to add the next block to the shared chain.

A second fundamental difference is that network nodes do not communicate with one another to process requests. Dandelion uses a distinct consensus mechanism, as opposed to traditional consensus algorithms such as proof of work or proof of stake. Instead, Dandelion uses a so-called “client leader” model, where the account holder is responsible for collecting the responses from validator nodes. The account holder then forwards their collection of responses to the rest of the network, who individually confirm whether there is a two-thirds majority of approval before accepting and continuing.

Finally, as previously mentioned, Dandelion allows for completely asynchronous processing of payments and deposits. As a result of these design choices, a rigorous comparison between the security of Dandelion and other well-known protocols would not be truly meaningful, and a performance comparison is not within the scope of this work.

4. Security Model

In this section, we outline the adversarial powers (via oracles) and security definitions developed for the Dandelion protocol. We begin with global network parameters needed for Dandelion, as well as several artificial parameters necessary for the proof of security.

4.1. Adversary Oracles

In this section of the paper, we present a series of oracles that are given to the adversary attempting to achieve some goal. We define the security criteria and the corresponding experiments following the descriptions of the oracles.

Before beginning the description of our oracles, we provide insight behind this choice of approach. Proofs of security for algorithms, such as DSAs, and (authenticated) key exchange protocols typically use oracles in security experiments, that are given to the adversary. This allows them to interact and control various aspects of the algorithm/protocol. In the case of key exchanges, the adversary can simulate the entire network, issuing messages on behalf of users, corrupt users, and more, effectively giving them near-total control while they attempt to win the security experiment. Our choice of using an oracle representation is to bring security proofs of blockchain protocols in line with other cryptographic algorithms through the use of oracles and formal security experiments.

To this end, we adopt a method similar to key exchange models, where the oracles are able to generate and process any message from the protocol. Thus, our oracles are defined to follow this approach, and provide the adversary oracles that are capable of generating and processing any message from the Dandelion protocol. We note here that our choice of model can be thought of as an oracle-based generalization of Garay et al.’s security model [21], which gives an adversary the ability to broadcast any message they wish, adaptively corrupt nodes, and change the source of any message. However, their model is not truly appropriate for our purposes, as Dandelion does not utilize rounds and a global ledger. Instead, each transaction is completed separately, and we make use of oracles which act on a transactional level.

We first define two additional lists that we require for our security analysis: $\mathbb{C}$, which is a list of users that have been corrupted by the adversary; $\mathbb{T}$, a list of non-active nodes; and ${\mathcal{L}}_{Tx}$, a list of transactions the adversary has created via oracle queries. Each of $\mathbb{C}$, $\mathbb{T}$, and ${\mathcal{L}}_{Tx}$ begins empty and is updated adaptively in response to the actions of the adversary. Importantly, $\mathbb{C}$ allows the adversary to view the corrupted node’s secret keys and to arbitrarily decide the node’s responses to transaction requests. Finally, we note that all transactions require $\mathsf{amnt}>0$, and all other values will result in a reject message ⊥.

$\mathsf{Add}$: 

Generates a new node $\mathsf{U}$, under the control of $\mathcal{A}$. The oracle first checks whether $\frac{\left|\mathbb{C}\right|+1}{|\mathbb{U}\backslash \mathbb{T}|}<\frac{1}{3}$. If yes, then the node’s $\Sigma$ keys are generated, along with its shard ID ${\mathsf{Shard}}_{\mathsf{id}}$; its balance and transaction are each set to 0, $\mathsf{Status}$ is set to $\mathsf{Unlocked}$, and its chain $\mathsf{Chain}$ and penny jar ${\mathsf{PJ}}^{}$ are set to empty. The node is added to both $({pk}_{\mathsf{U}}$, ${sk}_{\mathsf{U}}$, ${{\mathsf{Shard}}_{\mathsf{id}}}^{\mathsf{U}}$, 0, 0, $\mathsf{Unlocked}$, $\text{-}$, $\text{-})\cup \mathbb{U}$ and $(p{k}_{\mathsf{U}},{{\mathsf{Shard}}_{\mathsf{id}}}^{\mathsf{U}})\cup \mathbb{C}$, and $(p{k}_{\mathsf{U}},s{k}_{\mathsf{U}})$ are returned to $\mathcal{A}$. If no, then the oracle returns ⊥.

$\mathsf{Corru}$

$\mathsf{pt}(p{k}_{\mathsf{U}},{{\mathsf{Shard}}_{\mathsf{id}}}^{\mathsf{U}})$: Corrupts a node to give $\mathcal{A}$ the node’s secret key and control over it. The oracle first checks whether the node is in the master list of users $\mathbb{U}$ and whether $\frac{\left|\mathbb{C}\right|+1}{|\mathbb{U}\backslash \mathbb{T}|}<\frac{1}{3}$. If yes, it then returns ${pk}_{\mathsf{U}}$’s corresponding secret ${sk}_{\mathsf{U}}$ and $(p{k}_{\mathsf{U}},s{k}_{\mathsf{U}},{{\mathsf{Shard}}_{\mathsf{id}}}^{\mathsf{U}})\cup \mathbb{C}$. If not, then the oracle returns ⊥.

$\mathsf{Down}$

$(p{k}_{\mathsf{U}},{{\mathsf{Shard}}_{\mathsf{id}}}^{\mathsf{U}})$: Takes a node temporarily offline so that the node will miss the next transaction or collection request, simulating the node missing the next round of network validation. The oracle first checks whether the node is in the master list of users $\mathbb{U}$ and whether $\frac{\left|\mathbb{C}\right|+1}{|\mathbb{U}\backslash \mathbb{T}|}<\frac{1}{3}$. If yes, then the oracle is successful and $(p{k}_{\mathsf{U}},{{\mathsf{Shard}}_{\mathsf{id}}}^{\mathsf{U}})\cup \mathbb{T}$, and it returns 1. Otherwise, the oracle fails and returns 0.

$\mathsf{Build}$

$\mathsf{Tx}((p{k}_{{\mathsf{U}}_A},s{k}_{{\mathsf{U}}_A},{\mathsf{Shard}}_{\mathsf{id}}^{{\mathsf{U}}_A}),(p{k}_{{\mathsf{U}}_B},{\mathsf{Shard}}_{\mathsf{id}}^{{\mathsf{U}}_B}),\mathsf{amnt})$: Creates a transaction request to send $\mathsf{amnt}$ from a corrupted node ${\mathsf{U}}_A$ to another node, ${\mathsf{U}}_B$. First, the oracle confirms both that the user exists, and that $\mathsf{amnt}\le {\mathsf{Balance}}^{{\mathsf{U}}_A}$. If neither is true, then the oracle rejects. Otherwise, the oracle creates the corresponding $\mathsf{Tx}$ and ${\mathsf{Tx}}_{{\mathsf{U}}_A\to {\mathsf{U}}_B}^{\mathrm{Request}}$, and returns a ${\mathsf{Tx}}_{{\mathsf{U}}_A\to {\mathsf{U}}_B}^{\mathrm{Request}}$ message to the adversary and adds $\mathsf{Tx}\cup {\mathcal{L}}_{Tx}$.

$\mathsf{TxAu}$

$\mathsf{thorize}({\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Request}})\to \mathcal{R}$: Returns the responses of all nodes $\mathsf{U}\in \mathbb{U}\backslash (\mathbb{T}\cup \mathbb{C})$ to the transaction request. First, the oracle does the following for each online non-corrupted node: it confirms that each of the users exist, that ${\mathsf{U}}_B.\mathsf{Status}$ is $\mathsf{Unlocked}$, that $\mathsf{amnt}\le {\mathsf{Balance}}^{{\mathsf{U}}_B}$, that $|{\mathsf{PJ}}^{{\mathsf{U}}_A}|<\left|{max}_{\mathrm{PJ}}\right|$, and it verifies the signature. The node then updates its node list. If a node accepts the transaction request as valid, it will return a ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Authorized}}$ message (see Figure 5) with $b=1$, and will set ${\mathsf{U}}_B.\mathsf{Status}=\mathsf{Locked}$. Otherwise, the node sets $b=0$ and sends ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Authorized}}$. We describe how this oracle handles nodes that were previously offline in Appendix B.

$\mathsf{TxFine}$

$\mathsf{alize}(\mathcal{R},{\mathcal{R}}^{\mathcal{A}})$: Creates the message ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Finalize}}$ (see Figure 5) with the list of responses $\mathcal{R}\cup {\mathcal{R}}^{\mathcal{A}}$, computes the final processing fee from the suggested fees by ordering the suggested fees in increasing order, and then takes the median of the first two thirds. It then returns the completed message to the adversary.

$\mathsf{TxCom}$

$\mathsf{plete}({\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Finalize}})$: Completes the transaction. Each node processes ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Finalize}}$ by first checking if each response in $\mathcal{R}\cup {\mathcal{R}}^{\mathcal{A}}$ is from an existing node by checking its own node list. If not, then that response is discarded. Next, they verify the signatures of the nodes they know of, and confirms if over two-thirds of the responses, relative to their node list, in $\mathcal{R}\cup {\mathcal{R}}^{\mathcal{A}}$, accepted the transaction. If yes, then the node computes the next block $\mathsf{B}$ in ${\mathsf{U}}_B$’s chain, updates ${\mathsf{U}}_B$’s balance by subtracting the amount request and the fee calculated, updating the transaction ID, sets ${\mathsf{U}}_B.\mathsf{Status}$ to $\mathsf{Unlocked}$, and adds the transaction to ${\mathsf{U}}_A$’s penny jar to be collected later. Finally, it returns each ${\mathsf{U}}_i$’s response to the adversary ${{\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Finalized}}}^{,{}_i}$, $b=0$ if they are rejected and $b=1$ if accepted. $\mathbb{T}$ is emptied.

$\mathsf{Abort}$

$\mathsf{Tx}(\mathsf{Tx})$: Creates an abort transaction request for transaction $\mathsf{Tx}$. The oracle first checks whether $\mathsf{Tx}\in {\mathcal{L}}_{Tx}$; if not, then the oracle returns $\mathsf{rejectedCause}$. Otherwise, the oracle computes and returns ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{AbortRequest}}$; see Figure 7.

$\mathsf{Abort}$

$\mathsf{Confirmation}({\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{AbortRequest}})$: Returns the responses of all nodes $\mathsf{U}\in \mathbb{U}\backslash (\mathbb{T}\cup \mathbb{C})$ to the abort transaction requests. Each node reviews the transaction $\mathsf{Tx}$ and checks whether the transaction is still in ${\mathsf{U}}_A$’s penny jar and not in ${\mathsf{U}}_B$’s chain, and verifies the signature. If true, then the node sets $b=1$, and ${\mathsf{U}}_i$ creates the response ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{AbortAuthorized}}$ (see Figure 7) with $b=1$. Otherwise, it sets $b=0$, and creates ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{AbortAuthorized}}$ accordingly. All the responses are collected in the set $\mathcal{P}$ and returned to the adversary.

$\mathsf{Abort}$

$\mathsf{Finalize}(\mathcal{P},{\mathcal{P}}^{\mathcal{A}})$: Creates the abort finalize message ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{AbortFinalize}}$ (see Figure 7) under response set $\mathcal{P}\cup {\mathcal{P}}^{\mathcal{A}}$, where ${\mathcal{P}}^{\mathcal{A}}$ are the responses the adversary inputs themselves for the corrupted nodes they control, and returns the completed message to the adversary. ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{AbortFinalize}}$ is then returned.

$\mathsf{Abort}$

$\mathsf{Complete}({\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{AbortFinalize}})$: Completes the abort request. Each node is given a copy of ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{AbortFinalize}}$, and first checks if each response in $\mathcal{P}\cup {\mathcal{P}}^{\mathcal{A}}$ is from an existing node by checking its own node list. If not, then that response is discarded. Next, they verify the signatures of the nodes they know of and confirm if over two-thirds of the responses, relative to their node list in $\mathcal{P}\cup {\mathcal{P}}^{\mathcal{A}}$, accepted the abort. If ${{\mathsf{U}}_B}_i$ accepts, then the transaction is aborted, removed from node ${\mathsf{U}}_A$’s penny jar ${\mathsf{PJ}}^{{\mathsf{U}}_A}$, ${\mathsf{U}}_B.\mathsf{Status}$ is set to $\mathsf{Unlocked}$ and the balance is updated, and the message $b^{\prime }=1$ is outputted by the node. Otherwise, the node ${\mathsf{U}}_i$ does nothing but output $b^{\prime }=0$. The collection of responses is outputted to the adversary.

$\mathsf{Reque}$

$\mathsf{stPennyJar}({pk}_{{\mathsf{U}}_A},{{\mathsf{Tx}}_{\#\mathsf{\Omega }}}^{{\mathsf{U}}_A})$: Creates a penny jar request for node ${\mathsf{U}}_A.$ The oracle first checks whether the node exists (if not, then the oracle returns $\mathsf{rejectedCause}$) and if ${\mathsf{Tx}}_{\#\mathsf{\Omega }}^{{\mathsf{U}}_A}$ is ${\mathsf{U}}_A$’s transaction ID on ${\mathsf{B}}_{\mathsf{\Omega }}^{{\mathsf{U}}_A}$. Otherwise, the oracle returns to the adversary ${\mathsf{PJ}}_{\mathrm{Request}}^{{\mathsf{U}}_A}$; see Figure 9.

$\mathsf{SendP}$

$\mathsf{ennyJar}({\mathsf{PJ}}_{\mathrm{Request}}^{{\mathsf{U}}_A})$: Returns the penny jar that every available node has for node ${\mathsf{U}}_A$. Each node first attempts to verify the signature. If the signature is valid, it outputs ${\mathsf{PJ}}_{{}_i}^{{\mathsf{U}}_A}$; see Figure 9. Additionally, the node sends the corresponding $\mathsf{PennyHash}$ for each penny. Otherwise, it returns $\mathsf{rejectedCause}$. The responses are collected in the collection $\mathbb{P}$ and returned to the adversary.

$\mathsf{Order}$

$\mathsf{Pennies}(\mathbb{P})$: Returns ${\mathsf{U}}_A$’s ordered list of pennies according to the node $\widehat{\mathbb{P}}$ from all collected penny jars, along with the corresponding hash of the penny. The order is determined by the ${\mathsf{U}}_A$s. The oracle then returns $\mathsf{CollectPennies}$ to the adversary; see Figure 9.

$\mathsf{Collec}$

$\mathsf{tPennies}(\widehat{\mathbb{P}},{\sigma }^{op},{pk}_{{\mathsf{U}}_A})$: Sends the ordered list of pennies to the other nodes to redeem all pennies. First, it verifies the signature ${\sigma }^{op}$. If the signature verifies, then ${\mathsf{U}}_i$ updates ${\mathsf{U}}_A$’s chain by hashing ${\mathsf{U}}_A$’s preceding block along with the corresponding block from the sender’s chain for the penny (using the blocker header to find the correct block) and creating the next block for ${\mathsf{U}}_A$. This is repeated for each penny, and during each iteration, ${\mathsf{U}}_A$’s balance and transaction ID are updated appropriately. Then, ${\mathsf{U}}_i$ empties ${\mathsf{U}}_A$’s penny jar ${\mathsf{PJ}}^{{\mathsf{U}}_A}$. We describe how this oracle handles nodes that were previously offline in Appendix B.

$\mathsf{TxHis}$

$\mathsf{tory}({pk}_{{\mathsf{U}}_A},{{\mathsf{Shard}}_{\mathsf{id}}}^{{\mathsf{U}}_A},{\mathsf{U}}_A,i)$: Returns the i-th transaction $\mathsf{Tx}$ for node $({pk}_{{\mathsf{U}}_A}$, ${{\mathsf{Shard}}_{\mathsf{id}}}_{{\mathsf{U}}_A})$ by searching the node’s chain. If there is no such transaction, the oracle returns $\perp .$

$\mathsf{Block}$

$\mathsf{History}({pk}_{{\mathsf{U}}_A},{{\mathsf{Shard}}_{\mathsf{id}}}^{{\mathsf{U}}_A},{\mathsf{U}}_A,i)$: Returns the i-th block in node ${\mathsf{U}}_A$’s chain. If there is no such block, then the oracle returns $\perp .$

$\mathsf{Hash}(\text{-})$: 

Returns $H(m)$.

4.2. Security

In addition to resistance to double-spending attacks, we now provide a list of security properties for the Dandelion protocol. We first provide an informal description of the various properties that have been, we believe, necessary for practical use for the Dandelion protocol, in addition to resistance to double-spending attacks. We then capture these with notions in a formal setting, along with security experiments in which the adversary is given access to the above oracles and must achieve some related goal.

Correctness: 

If $\left|{max}_{\mathrm{PJ}}\right|=\infty$, then all requests that were honestly created will be authorized by honest nodes in the network.

Fault 

Tolerance: An adversary, with some number of corrupted nodes, should not have monopolistic control over the approval of transactions or the processing of abort transaction requests.

Decidability: 

All transaction requests must either be completed or rejected.

Unforgeable 

Transactions: An adversary, with some number of corrupted nodes, cannot issue transaction requests that can become finalized on behalf of non-corrupted nodes.

Non-repudiation: 

An adversary, with some number of corrupted nodes, cannot issue abort transaction requests that are able to become finalized on behalf of non-corrupted nodes.

Unforgeable 

Collection: An adversary, with some number of corrupted nodes, cannot issue a request for the penny jar of honest nodes that causes honest nodes to return the corresponding penny jar.

Immutability: 

An adversary, with some number of corrupted nodes, cannot modify an existing users’ chain.

Quantum 

Resistance: The above properties must hold in the presence of an adversary with quantum computing capabilities.

We call the first three properties the functionality properties, as they ensure a basic level of the usability of the Dandelion protocol. Correctness ensures that honest attempts by potential users should be accepted by others executing the protocol correctly. An honest transaction should be only be rejected if the receiver’s penny jar is full. Thus, we must prove that if the penny jar limit was infinite and these messages were well-formed and valid, then they will always be accepted.

Fault tolerance is a necessary property for basic functionality, as Dandelion is to be a distributed decentralized network, where malicious nodes may attempt to collude and influence the network at large. As such, we must determine the fault-tolerance threshold of Dandelion, the point at which the network is effectively controlled by adversaries.

The final functionality property is that of decidability. Each request must be processed by the other nodes in the network before responding. If there existed a transaction that could not be decided upon, then, by the definition of Dandelion, the requester’s account would become locked. Moreover, the requester must then create an abort transaction message to unlock the node. Thus, we must prove that all transactions are either accepted, rejected, or can be aborted successfully.

The remaining five properties will be referred to as the security properties of Dandelion. We will use the traditional security experiment framework of Setup, Query, Challenge, and Finalize to formalize the first four security proprieties. Regarding quantum resistance, we will make it explicit that we will be considering a probabilistic poly-time adversary with quantum-computing capabilities, and that are capable of performing $\mathsf{Hash}$ queries in superposition. While the following security experiments and the subsequent proofs can be downgraded to consider classic adversaries, we consider it prudent to focus on quantum-capable adversaries as the default, given the impending standardization of quantum-resistant algorithms and the increasing probability of scaleable quantum computers during the intended lifetime of Dandelion.

We first begin with the security experiment for unforgeable transaction requests.

Definition 4 (Unforgeability of Transactions).

Let κ be a security parameter, $\mathcal{C}$ be the challenger of this experiment, Σ be a signature scheme, and H a hash function, and let $\mathcal{A}$ be an adversary interacting with Dandelion via the queries defined in Section 4.1 within the following security experiment ${\mathrm{Expt}}_{Dandelion}^{UnFTx}(\mathcal{A})$:

Setup. 

The challenger generates all the public and private information of all users in the Dandelion network according to the Dandelion protocol. This includes generating the public and secret key for Σ with security parameter κ. The challenger then simulates the network operating by uniformly creating, at random, interactions between nodes (i.e., simulating transaction requests, processing transactions, collecting pennies on arbitrary nodes, etc). After many polynomial transactions, the challenger outputs all public information to the adversary $\mathcal{A}$ and initializes $\mathbb{C}=\mathbb{T}={\mathcal{L}}_{Tx}=\varnothing$;

Query. 

The adversary $\mathcal{A}$ receives the generated public information and may query any of the oracles: $\mathsf{Add}$, $\mathsf{Corrupt}$, $\mathsf{Down}$, $\mathsf{BuildTx}$, $\mathsf{TxAuthorize}$, $\mathsf{TxFinalize}$, $\mathsf{TxComplete}$, $\mathsf{AbortTx}$, $\mathsf{AbortConfirmation}$, $\mathsf{AbortFinalize}$, $\mathsf{AbortComplete}$, $\mathsf{RequestPennyJar}$, $\mathsf{SendPennyJar}$, $\mathsf{CollectPennies}$, $\mathsf{TxHistory}$, $\mathsf{Hash}$, $\mathsf{BlockHistory}$.

Challenge. 

At some point, $\mathcal{A}$ stops and requests a challenge from $\mathcal{C}$. $\mathcal{C}$ then uniformly and at random selects a node, ${\mathsf{U}}^{*}$, from $\mathbb{U}\backslash (\mathbb{C}\cup \mathbb{T})$, whose status is set to unlocked, and gives $\mathcal{A}$ the public information of that node. If no such nodes exist, then $\mathcal{C}$ selects a node at random and generates the transaction abort request on behalf of the node. It then processes this request on behalf of all honest nodes. The adversary is then given back access to their oracles, but is forbidden from corrupting ${\mathsf{U}}^{*}$;

Finalize. 

The adversary eventually stops and outputs a transaction ${\mathsf{Tx}}^{*}\notin {\mathcal{L}}_{Tx}$, a request message ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Request}}$, and a response list ${\mathcal{R}}^{\mathcal{A}}$ for any number of nodes in $\mathbb{C}$. $\mathcal{C}$ accepts these inputs and computes the complete Dandelion transaction request protocol on ${\mathsf{Tx}}^{*}$ and uses ${\mathcal{R}}^{\mathcal{A}}$ as well as the response of honest nodes to compute ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Finalize}}$. After completing, the protocol $\mathcal{C}$ returns 1 if the transaction was accepted and finalized, and 0 otherwise.

We say that $\mathcal{A}$ wins the game if $\mathcal{C}$ returns 1 and loses otherwise. We say $Dandelion$ provides $UnFTx$-security if, for all adversaries, $\mathcal{A}$, the advantage function below is negligible in the security parameter:

$${\mathsf{Adv}}_{Dandelion}^{UnFTx}(\mathcal{A})=\left|Pr\left[{\mathrm{Expt}}_{Dandelion}^{UnFTx}(\mathcal{A})\to 1\right]\right|.$$

We note here that the remaining security experiments have identical Setup and Query phases to Definition 4, and we will omit their description from the remaining definitions for space considerations.

Definition 5 (Non-repudiation of Transactions).

Let κ be a security parameter, $\mathcal{C}$ be the challenger of this experiment, Σ be a signature scheme, and H a hash function, and let $\mathcal{A}$ be an adversary interacting with Dandelion via the queries defined in Section 4.1 within the following security experiment ${\mathrm{Expt}}_{Dandelion}^{NonRep}(\mathcal{A})$:

Challenge. 

At some point, $\mathcal{A}$ stops and requests a challenge from $\mathcal{C}$. $\mathcal{C}$ then uniformly and at random selects a node, ${\mathsf{U}}^{*}$, from $\mathbb{U}\backslash (\mathbb{C}\cup \mathbb{T})$. If this node has a pending transaction ${\mathsf{Tx}}^{*}$ that has not yet been finalized, the challenger then sends ${\mathsf{U}}^{*}$’s public information, along with ${\mathsf{Tx}}^{*}$. Otherwise, if the node is set to unlocked, $\mathcal{C}$ generates a random valid transaction request from ${\mathsf{U}}^{*}$ to another node, ${\mathsf{U}}^{\prime }$, in $\mathbb{U}\backslash (\mathbb{C}\cup \mathbb{T})$, and sends the request to all other honest nodes. The challenger then forwards ${\mathsf{U}}^{*}$’s public information and the transaction ${\mathsf{Tx}}^{*}$ to $\mathcal{A}$. The adversary is then given back access to their oracles, but is forbidden from corrupting ${\mathsf{U}}^{*}$;

Finalize. 

The adversary eventually stops and outputs an abort transaction request ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{AbortRequest}}$ and a response list ${\mathcal{P}}^{\mathcal{A}}$ for any number of nodes in $\mathbb{C}$. $\mathcal{C}$ accepts these inputs and computes the complete Dandelion abort transaction request protocol on ${\mathsf{Tx}}^{*},{\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{AbortRequest}}$, and uses ${\mathcal{P}}^{\mathcal{A}}$ as well as the response of honest nodes to compute ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{AbortFinalize}}$. After completing, the protocol $\mathcal{C}$ returns 1 if the abort transaction request was accepted and finalized and 0 otherwise.

We say that $\mathcal{A}$ wins the game if $\mathcal{C}$ returns 1 and loses otherwise. We say $Dandelion$ provides $NonRep$-security if, for all adversaries, $\mathcal{A}$, the advantage function below is negligible in the security parameter:

$${\mathsf{Adv}}_{Dandelion}^{NonRep}(\mathcal{A})=\left|Pr\left[{\mathrm{Expt}}_{Dandelion}^{NonRep}(\mathcal{A})\to 1\right]\right|.$$

Definition 6 (Unforgeable Collection Transactions).

Let κ be a security parameter, $\mathcal{C}$ be the challenger of this experiment, Σ be a signature scheme, and H a hash function, and let $\mathcal{A}$ be an adversary interacting with Dandelion via the queries defined in Section 4.1 within the following security experiment ${\mathrm{Expt}}_{Dandelion}^{UnCol}(\mathcal{A})$:

Challenge. 

At some point, $\mathcal{A}$ stops and requests a challenge from $\mathcal{C}$. $\mathcal{C}$ then uniformly and at random selects a node, ${\mathsf{U}}^{*}$, from $\mathbb{U}\backslash (\mathbb{C}\cup \mathbb{T})$ and confirms that ${\mathsf{U}}^{*}$ has uncollected pennies in their jar. If there are no such pennies, $\mathcal{C}$ selects another node ${\mathsf{U}}^{\prime }$ in $\mathbb{U}\backslash (\mathbb{C}\cup \mathbb{T})$ that is unlocked, and then generates a valid transaction from ${\mathsf{U}}^{\prime }$ to ${\mathsf{U}}^{*}$ and completes the Dandelion transaction request protocol to add a penny to ${\mathsf{U}}^{*}$’s penny jar. $\mathcal{C}$ then sends ${\mathsf{U}}^{*}$’s public information to $\mathcal{A}$, as well as the transaction ID from the last block in ${\mathsf{U}}^{*}$’s chain, ${\mathsf{Tx}}_{\#\mathsf{\Omega }}^{{\mathsf{U}}^{*}}$. The adversary is then given back access to their oracles, but is forbidden from corrupting ${\mathsf{U}}^{*}$;

Finalize. 

The adversary eventually stops, then outputs ${\mathsf{PJ}}_{\mathrm{Request}}^{{\mathsf{U}}^{*}}$. $\mathcal{C}$ accepts the message and completes the Dandelion request penny jar protocol and returns 1 if the abort was accepted and finalized, and 0 otherwise.

We say that $\mathcal{A}$ wins the game if $\mathcal{C}$ returns 1 and loses otherwise. We say $Dandelion$ provides $UnCol$-security if, for all adversaries, $\mathcal{A}$, the advantage function below is negligible in the security parameter:

$${\mathsf{Adv}}_{Dandelion}^{UnCol}(\mathcal{A})=\left|Pr\left[{\mathrm{Expt}}_{Dandelion}^{UnCol}(\mathcal{A})\to 1\right]\right|.$$

Definition 7 (Immutability of Chains).

Let κ be a security parameter, $\mathcal{C}$ be the challenger of this experiment, Σ be a signature scheme, and H a hash function, and let $\mathcal{A}$ be an adversary interacting with Dandelion via the queries defined in Section 4.1 within the following security experiment ${\mathrm{Expt}}_{Dandelion}^{Immutable}(\mathcal{A})$:

Challenge. 

At some point, $\mathcal{A}$ stops and selects a node ${\mathsf{U}}^{*}$ with a chain $\mathsf{Chain}$ of length $l>1$. The adversary then submits the node ${\mathsf{U}}^{*}$ and its chain, ${\mathsf{Chain}}^{*}$, to the challenger, along with a transaction, ${\mathsf{Tx}}^{*}$, and index $1\ge i\le l-1$;

Finalize. 

The challenger accepts $({\mathsf{U}}^{*},{\mathsf{Chain}}^{*},{\mathsf{Tx}}^{*},i)$ and first confirms the node exists and that ${\mathsf{Chain}}^{*}$ is the current state of the user’s chain. If not, $\mathcal{C}$ returns 0 and $\mathcal{A}$ has lost the security experiment. Otherwise, $\mathcal{C}$ then computes the hash $H({\mathsf{Tx}}^{*},{\mathsf{B}}^{{\mathsf{U}}_i^{*}})$ and compares it with the ${\mathsf{Hash}}_{i+1}$ from block $i+1$ of ${\mathsf{U}}^{*}$’s chain. If $H({\mathsf{Tx}}^{*},{\mathsf{B}}^{{\mathsf{U}}_i^{*}})=has{h}_{i+1}$, then $\mathcal{C}$ returns 1, and 0 otherwise.

We say that $\mathcal{A}$ wins the game if $\mathcal{C}$ returns 1 and loses otherwise. We say $Dandelion$ provides $Immutable$-security if, for all adversaries, $\mathcal{A}$, the advantage function below is negligible in the security parameter:

$${\mathsf{Adv}}_{Dandelion}^{Immutable}(\mathcal{A})=\left|Pr\left[{\mathrm{Expt}}_{Dandelion}^{Immutable}(\mathcal{A})\to 1\right]\right|.$$

5. Proof of Security

In this section, we prove the security of the Dandelion protocol in our model. We first demonstrate that Dandelion satisfies the three functionality properties before moving on to the security properties and, finally, to double-spending attacks. We begin with correctness.

Theorem 1.

Dandelion is correct.

Proof. 

We first assume that $\left|{max}_{\mathrm{PJ}}\right|=\infty$; this represents receivers still having space available in their penny jar. Next, recall the following: the Dandelion protocol has two request messages, a transaction request, ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Request}}$, and an abort request, ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{AbortRequest}}$. In both requests, the sender must provide the following information: $\mathsf{Tx}=({\mathsf{Shard}}_{\mathsf{id}}^{{\mathsf{U}}_B}$, $p{k}_{{\mathsf{U}}_B}$, ${\mathsf{TxID}}^{{\mathsf{U}}_B}$, $\mathsf{amnt}$, and ${\mathsf{Shard}}_{\mathsf{id}}^{{\mathsf{U}}_A}$, $p{k}_{{\mathsf{U}}_A})$. Each request also contains a corresponding “requestTx” or “abortTx”, a signature over the transaction details, and one of the two messages. In either situation, an honest user will include valid details of the transaction, including public account information. Thus, nodes will receive valid inputs, confirm that the transaction details are valid, and verify the signature attached. That is, the nodes will confirm that both accounts exist, that the transaction ID is correct (or update it accordingly), and that the amount is no more than the sender’s balance. Since there is no limit to the number of transactions that the sender can have in their penny jar, the honest request would not be rejected. Thus, Dandelion is correct. □

Theorem 2.

The fault-tolerance threshold of Dandelion is $\frac{N}{3}$.

Proof. 

Recall that, in order for a transaction or an abort to be finalized, the nodes must first receive a ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Finalize}}$ or ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{AbortFinalize}}$ message, containing a list of responses signed by other nodes in the network. The node confirms the existence of the other nodes and verifies the corresponding response and signature from said node. The request is finalized if over two-thirds of the responses in the request authorized the transaction. Each request is intended to be sent across the network to all active nodes, N. This implies that a transaction requires greater than $\frac{N}{3}+1$ nodes to authorize the transaction. Now, let f denote the number of nodes an adversary controls. If $f\ge \frac{N}{3}+1$, then clearly the adversary has complete control over all requests. However, this is also true for $f\ge \frac{N}{3}$, as the adversary is able to act as a tie-breaker to authorize a transaction or to force users to abort transactions as they would be unable to reach a consensus from the network, giving the adversary effective control of the network instead of complete control. Thus, we have that the fault-tolerance threshold is $\frac{N}{3}$. Alternatively, we have that $3f<N$, where N is the number of active online nodes, and f is the number of nodes the adversary controls. □

Corollary 1.

Dandelion is decidable.

Proof. 

Let N denote the number of active online nodes in the network, and let $\mathcal{A}$ be an adversary that controls $f<\frac{N}{3}$ nodes of the network. By Theorem 1, we have that Dandelion is correct, and so all requests that are honestly generated, and well-formed requests will be authorized by honest nodes, provided the receiver has space available in their penny jar. By the assumption that $\mathcal{A}$ controls fewer nodes than the fault-tolerance threshold, and by Theorem 2, it does not have enough control over the network to solely decide which requests are authorized. Moreover, there does exist a sufficient number of honest nodes to either authorize valid transactions or reject invalid transactions. □

We now establish the security properties of Dandelion through a series of security reductions.

Theorem 3.

Let Σ be a signature algorithm that is $\mathsf{EUF}\text{-}\mathsf{CMA}$-secure against quantum-computing-capable PPT adversaries, H be a hash function that is collision-free against quantum-computing-capable PPT adversaries, and $\mathcal{A}$ be a quantum-computing-capable PPT adversary that controls less than $\frac{1}{3}$ of the Dandelion network. Then, except with negligible probability, the Dandelion protocol satisfies the unforgeability of transaction property.

Proof. 

To prove the security against forged transaction requests, we will demonstrate that an adversary capable of doing so can be used as an oracle algorithm to win the $\mathsf{EUF}\text{-}\mathsf{CMA}$-security game (see Definition 2) against $\Sigma$. Let $\mathcal{B}$ be a quantum-computing-capable adversary against the $\mathsf{EUF}\text{-}\mathsf{CMA}$-security of $\Sigma$. We then consider $\mathcal{B}$ while it is in the $\mathsf{EUF}\text{-}\mathsf{CMA}$-security experiment, as described in Figure 1; that is, it is given a public key $p{k}^{*}$ and oracle ${\mathsf{Sign}}^{*}$ programmed with the corresponding secret key $s{k}^{*}$. Now, assume that there exists a quantum-computing-capable PPT adversary $\mathcal{A}$ that can win the $UnFTx$-security of Dandelion by outputting a new transaction request ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Request}}$ and response list ${\mathcal{R}}^{\mathcal{A}}$ that results in the transaction being finalized with non-negligible probability.

$\mathcal{B}$ is able to use $\mathcal{A}$ to win the $\mathsf{EUF}\text{-}\mathsf{CMA}$-security game as follows. First it picks a suitable collision-free hash function H, initializes the following lists—$\mathbb{U},\mathbb{T},\mathbb{C}$, generates $\Sigma$ keys for $N-1$ other nodes, defines the distribution D, and uses $p{k}^{*}$ as the public key for the N-th node. $\mathcal{B}$ then simulates the Dandelion protocol for some polynomial amount of time. This includes generating shard IDs for nodes as it adds them to the list of nodes, assigning account balances, arbitrarily deciding on transactions between random users, and keeps track of all user data, both, private and public. It uses its ${\mathsf{Sign}}^{*}$ oracle to produce signatures on behalf of the account represented with public key $p{k}^{*}$. $\mathcal{B}$ then simulates $\mathcal{A}$ and the ${\mathrm{Expt}}_{Dandelion}^{UnFTx}(\mathcal{A})$ and acts as the challenger. As $\mathcal{B}$ generated all but one node’s public key, it is able to answer all but one of the oracle queries $\mathcal{A}$ may make, including $\mathsf{Add}$ and $\mathsf{Corrupt}$ queries, ensuring $\mathcal{A}$ does not surpass the fault-tolerance threshold. The only exception is for a $\mathsf{Corrupt}$ query on $(p{k}^{*},{\mathsf{Shard}}_{\mathsf{id}}p{k}^{*})$. Thus, the simulation is perfect to $\mathcal{A}$ through both the Setup and Query phases until $\mathcal{A}$ queries $\mathsf{Corrupt}$ on $p{k}^{*}$.

We let E denote the event that $\mathcal{A}$ queries $\mathsf{Corrupt}$ on the account with public key $p{k}^{*}$, and let $q_c$ and $q_a$ denote the number of $\mathsf{Corrupt}$ and $\mathsf{Add}$ queries made, respectively, by $\mathcal{A}$. During the simulation of $\mathcal{A}$ by $\mathcal{B}$, we define an abort and restart condition if E happens, and we wish to bound the probability of this. First, we know that it must hold that $q_c+q_a<\frac{N}{3}$. Thus, the maximum number of $\mathsf{Corrupt}$ queries $\mathcal{A}$ may make is $\frac{N}{3}-1$. We can then upper-bound the probability of E by using a hyper-geometric distribution. There are N total nodes, $\frac{N}{3}-1$ accounts are drawn, and there is only a single success that is $p{k}^{*}$. Thus, we have:

$$Pr\left[E\right]=\left(\genfrac{}{}{0pt}{}{1}{1}\right)\frac{(\genfrac{}{}{0pt}{}{N-1}{\frac{N}{3}-1-1})}{(\genfrac{}{}{0pt}{}{N}{\frac{N}{3}-1})}=\frac{1}{3}-\frac{1}{N}.$$

Therefore, we have an upper bound of $Pr\left[E\right]<\frac{1}{3}$ for $N>3$, and $\mathcal{B}$ will be forced to restart its simulation with probability $\frac{1}{3}$. When E does not occur, then $\mathcal{B}$ will select the node with public key $p{k}^{*}$ as the challenge for $\mathcal{A}$, instead of a truly random non-$\mathcal{A}$-controlled node. $\mathcal{B}$ continues the simulation until $\mathcal{A}$ outputs a ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Request}}$. $\mathcal{B}$ then parses the ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Request}}$ message and forwards $\mathsf{Tx}\parallel$requestTx,${\sigma }^r$ to their own challenger. By assumption, we have that $\mathcal{A}$ can successfully produce a ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Request}}$ and response list that will be accepted by the Dandelion network, which includes a valid signature for a node whose secret keys it does not have knowledge of. Thus, if ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Request}}$ is accepted by the network, then $\mathcal{B}$ will have provided a successful forgery under $p{k}^{*}$. We can then conclude that:

$${\mathsf{Adv}}_{Dandelion}^{UnFTx}(\mathcal{A})\le 3·{\mathsf{Adv}}_{\Sigma }^{\mathsf{EUF}\text{-}\mathsf{CMA}}(\mathcal{B}),$$

where the factor of 3 is to account for the probability of $\mathcal{A}$ querying $\mathsf{Corrupt}$ on $\mathcal{B}$’s challenge public key. □

Theorem 4.

Let Σ be a signature algorithm that is $\mathsf{EUF}\text{-}\mathsf{CMA}$-secure against quantum-computing-capable PPT adversaries, H be a hash function that is collision-free against quantum-computing-capable PPT adversaries, and $\mathcal{A}$ be a quantum-computing-capable PPT adversary that controls less than $\frac{1}{3}$ of the Dandelion network. Then, except with negligible probability, the Dandelion protocol satisfies the non-repudiation of transactions property.

Proof. 

We employ a similar strategy to the one used in Theorem 3. We consider a quantum-computing-capable PPT adversary $\mathcal{B}$ attempting to win the $\mathsf{EUF}\text{-}\mathsf{CMA}$-security experiment on the signature scheme $\Sigma$. We also assume that there exists a quantum-computing-capable PPT adversary $\mathcal{A}$ that is able to win the ${\mathrm{Expt}}_{Dandelion}^{NonRep}(\mathcal{A})$ experiment, as in Definition 5, with non-negligible probability. We will demonstrate a reduction that $\mathcal{B}$ may employ to use $\mathcal{A}$ as an oracle algorithm to win their experiment.

We have $\mathcal{B}$ set up a Dandelion network identically to the way described in Theorem 3. It generates a signing key and account information for N nodes, using its challenge public key, $p{k}^{*}$, as part of the network. It also generates the distribution D. It then simulates Dandelion for polynomial time, making arbitrary valid transactions between nodes before stopping and beginning to simulate $\mathcal{A}$ in the $NonRep$ security experiment over the simulated network.

This simulation is perfect up to $\mathcal{A}$ querying $\mathsf{Corrupt}$ on $p{k}^{*}$, and the probability of this occurring is upper-bounded by $\frac{1}{3}$. If $\mathcal{A}$ does not perform this query, and eventually requests a challenge, $\mathcal{B}$ forwards the account information associated with $p{k}^{*}$ to $\mathcal{A}$, along with a challenge transaction ${\mathsf{Tx}}^{*}$ (that $\mathcal{B}$ may or may not need to generate itself). $\mathcal{A}$ is given back access to its oracles and eventually outputs a ${\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{AbortRequest}}$ message and response list ${\mathcal{P}}^{\mathcal{A}}$, which $\mathcal{B}$ parses and forwards to its own challenger ${\mathsf{Tx}}^{*}\parallel$abortRequest, ${\sigma }^{ar}$. Again, by assumption, $\mathcal{A}$ is able to win the ${\mathrm{Expt}}_{Dandelion}^{NonRep}(\mathcal{A})$ with non-negligible probability, and so it must have produced a valid signature under a public key for which it does not know the secret key. Thus, if $\mathcal{A}$ would win the ${\mathrm{Expt}}_{Dandelion}^{NonRep}(\mathcal{A})$ by having the network accept the abort request as legitimate with that output, then $\mathcal{B}$ will win the $\mathsf{EUF}\text{-}\mathsf{CMA}$ experiment.

We conclude that:

$${\mathsf{Adv}}_{Dandelion}^{NonRep}(\mathcal{A})\le 3·{\mathsf{Adv}}_{\Sigma }^{\mathsf{EUF}\text{-}\mathsf{CMA}}(\mathcal{B}),$$

where the factor of 3 is to account for the probability of $\mathcal{A}$ querying $\mathsf{Corrupt}$ on $\mathcal{B}$’s challenge public key. □

Theorem 5.

Let Σ be a signature algorithm that is $\mathsf{EUF}\text{-}\mathsf{CMA}$-secure against quantum-computing-capable PPT adversaries, H be a hash function that is collision-free against quantum-computing-capable PPT adversaries, and $\mathcal{A}$ be a quantum-computing-capable PPT adversary that controls less than $\frac{1}{3}$ of the Dandelion network. Then, except with negligible probability, the Dandelion protocol satisfies the unforgeable collection of transactions property.

Proof. 

We consider a quantum-computing-capable PPT adversary $\mathcal{B}$ against the $\mathsf{EUF}\text{-}\mathsf{CMA}$-security of $\Sigma$. We also assume that there exists another quantum-computing-capable PPT adversary $\mathcal{A}$ that can win the ${\mathrm{Expt}}_{Dandelion}^{UnCol}(\mathcal{A})$, as in Definition 5, with non-negligible probability. $\mathcal{B}$ sets up a simulation of the Dandelion network and includes its challenge public key $p{k}^{*}$ as one of the nodes in the network. It also generates the distribution D. It runs the simulation for polynomial time before stopping. $\mathcal{B}$ then begins to simulate $\mathcal{A}$ in the $UnCol$-security experiment.

Once again, the simulation is perfect until $\mathcal{A}$ queries $\mathsf{Corrupt}$ on $p{k}^{*}$, which occurs with probability bounded above $\frac{1}{3}$. If $\mathcal{A}$ does not perform this query, and eventually requests a challenge, $\mathcal{B}$ forwards the account information associated with $p{k}^{*}$ to $\mathcal{A}$, along with ${\mathsf{Tx}}_{\#\mathsf{\Omega }}^{{\mathsf{U}}^{*}}$. $\mathcal{B}$ may need to generate a transaction to add a penny to the corresponding node’s penny jar. $\mathcal{A}$ is given back oracle access, and eventually outputs a $\mathsf{RequestPennyJar}$ message. $\mathcal{B}$ then takes this message and submits it to its own challenger. By assumption, $\mathcal{A}$ is able to win the $UnCol$-security experiment with a non-negligible advantage, and so it must produce a valid signature for a node it does not control. Thus, if $\mathcal{A}$ had won in the $UnCol$-security experiment, $\mathcal{B}$ would have submitted a successful forgery in the $\mathsf{EUF}\text{-}\mathsf{CMA}$-security experiment.

We conclude that:

$${\mathsf{Adv}}_{Dandelion}^{UnCol}(\mathcal{A})\le 3·{\mathsf{Adv}}_{\Sigma }^{\mathsf{EUF}\text{-}\mathsf{CMA}}(\mathcal{B}),$$

where the factor of 3 is to account for the probability of $\mathcal{A}$ querying $\mathsf{Corrupt}$ on $\mathcal{B}$’s challenge public key. □

Theorem 6.

Let Σ be a signature algorithm that is $\mathsf{EUF}\text{-}\mathsf{CMA}$-secure against quantum-computing-capable PPT adversaries, H be a hash function that is collision-free against quantum-computing-capable PPT adversaries, and $\mathcal{A}$ be a quantum-computing-capable PPT adversary that controls less than $\frac{1}{3}$ of the Dandelion network. Then, except with negligible probability, the Dandelion protocol satisfies the immutability of chains property.

Proof. 

We once again use a similar approach to those used in the previous Theorems, except we do not consider a quantum-computing-capable PPT adversary, $\mathcal{B}$, against the $\mathsf{EUF}\text{-}\mathsf{CMA}$-security of $\Sigma$, but against the collision-free security experiment in Figure 3. We also assume that there exists a quantum-computing-capable PPT adversary, $\mathcal{A}$, that can win ${\mathrm{Expt}}_{Dandelion}^{Immutable}(\mathcal{A})$-security experiment in Definition 7.

As before, $\mathcal{B}$ simulates the Dandelion network, but this time it generates all nodes’ signing keys and distributions D. This means that there is no $\mathsf{Corrupt}$ query that the adversary can make that will cause $\mathcal{B}$ to restart the simulation. As a result, $\mathcal{B}$ can perfectly simulate the $Immutable$-security experiment by using its own hash oracle to answer hash queries, and answer all other queries itself. Eventually, $\mathcal{A}$ submits a node ${\mathsf{U}}^{*}$, its chain ${\mathsf{Chain}}^{*}$, an index i, and transaction ${\mathsf{Tx}}^{*}$ to $\mathcal{B}$. $\mathcal{B}$ then parses the input and does the following: $\mathcal{B}$ searches ${\mathsf{U}}^{*}$’s chain for block i, ${\mathsf{B}}_i$, and the transaction information from block $i+1$ for the transaction:

$$\widetilde{\mathsf{Tx}}=({\mathsf{Shard}}_{\mathsf{id}}^{\mathrm{send}},p{k}_{\mathrm{send}},{\mathsf{TxID}}^{{\mathsf{U}}_A},\mathsf{amnt},{\mathsf{Shard}}_{\mathsf{id}}^{\mathrm{receive}},p{k}_{\mathrm{receive}}).$$

It then submits the following messages to its own oracle—$m_0={\mathsf{Tx}}^{*},{\mathsf{B}}_i$, and $m_1=\widetilde{\mathsf{Tx}},{\mathsf{B}}_i$. By assumption, $\mathcal{A}$ wins the real $Immutable$-security experiment with non-negligible probability by producing a collision between $H({\mathsf{Tx}}^{*},{\mathsf{B}}_i)$ and the hash value used in the next block. We can, then, conclude that:

$${\mathsf{Adv}}_{Dandelion}^{Immutable}(\mathcal{A})\le {\mathsf{Adv}}_{\mathcal{H}}^{\mathrm{collision}}(\mathcal{B}).$$

Thus, if $\mathcal{A}$ has successfully produced a collision, then $\mathcal{B}$ will also have submitted a collision as well. □

We now, finally, cover the double-spend attack.

Theorem 7.

Malicious parties cannot double-spend in Dandelion.

Proof. 

Let $\mathcal{B}$ denote a quantum-computing-capable PPT adversary that controls less than $\frac{1}{3}$ of the Dandelion network, ${\mathsf{Balance}}^{*}$ be the balance of a single account that $\mathcal{B}$ tries to double-spend from, and ${\mathsf{Tx}}_1$ and ${\mathsf{Tx}}_2$ denote the two transactions attempting to double-spend.

Then, without loss of generality, if $\mathcal{B}$ attempts to collect authorizations for ${\mathsf{Tx}}_1$ first, it sends the corresponding (valid) transaction request ${{\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Request}}}_1$. Any honest nodes that receive the request will set $\mathcal{B}.\mathsf{Status}$ to $\mathsf{Locked}$ and, thus, will not authorize the transaction request ${{\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Request}}}_2$ for ${\mathsf{Tx}}_2$. Likewise, any honest nodes that receive ${{\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Request}}}_2$ first will set $\mathcal{B}.\mathsf{Status}$ to $\mathsf{Locked}$ and, thus, will not authorize the transaction request ${{\mathsf{Tx}}_{{\mathsf{U}}_B\to {\mathsf{U}}_A}^{\mathrm{Request}}}_1$.

Thus, $\mathcal{B}$ will have partitioned the network into two sets, $M_1$ and $M_2$, based on which request the node received first. In order for both transactions to be authorized, and successfully double-spend, it must be that $M_1,M_2>\frac{2N}{3}$. However, $M_1+M_2=N$ and so only one of $M_i>\frac{2N}{3}$ where $i=1$ or 2. Consequently, $\mathcal{B}$ cannot authorize both transaction simultaneously. □

6. Conclusions

In this work, we develop an oracle-based security model for the peer-to-peer blockchain transaction protocol Dandelion.

Our framework provides an oracle model for adversaries to interact with the Dandelion network, allowing for adaptive corruptions, network additions, and take-downs of nodes in the network to simulate a dynamic and asynchronous network. We then define formal security experiments for the ideas of unforgeability, non-repudiation, and immutability for the Dandelion protocol.

As the main result of our paper, we prove both the functional and security criteria of the Dandelion protocol with tight security reductions to the security of its digital signature algorithm and hash function. We also prove resistance to double-spend attacks. In these proofs, we explicitly consider quantum-capable PPT adversaries in order to reflect potential future attacks against Dandelion as quantum-computing technology becomes more robust, and such attacks become more likely.