Credit networks are distributed systems of trust between users, where a user extends financial credit, or guarantees assets to other users whom it deems credit worthy, with the extended credit proportionate to the amount of trust that exists between the users [2,24]. Distributed credit networks (DCNs') are essentially peer-to-peer lending networks, where users extend credit, borrow money and commodities from each other directly, while minimizing the role of banks, clearing-houses, or bourses. The rising popularity of DCNs stem from their capability to enable direct exchanges between users, sidestepping the waiting times and arbitrage fees charged by traditional, regulated financial institutions, in exchange for users accepting counter-party credit risks. In a credit network, two users, Alice and Bob can trade directly with each other, if there exists a direct trust relationship between them, otherwise a path between them through network peers, built on credit relationships between intermediate users, is established to transfer credit.
A DCN provides the basic infrastructure for building distributed payment networks, where the payment between users could be remittances of diverse nature (e.g, fiat currency, cryptocurrency, assets' transfer, such as stocks and bonds). The goal of such remittance networks is to create a distributed financial ecosystem, best exemplified by the increasingly popular Ripple payment settlement network [18].
Credit networks have found use in several applications, such as designing and securing social networks [13], Sybil tolerant networks [24], and content rating systems [8]. Popular blockchainbased payment settlement networks (e.g., Ripple [18], Stellar [21]) use credit networks as underlying infrastructure to represent credit between users. Other examples being TrustDavis [3], Bazaar [17], and Ostra [12]. Furthermore, traditional banking systems have begun integrating blockchain-based payment settlement networks such as Ripple into their set of services [19]-an increasingly popular trend.
Conceptually, a credit network can be modeled as a directed graph where users represent vertices, weighted edges represent the credit amount that a user is willing to offer its adjacent neighbor, and the directionality of the edge represents the direction of credit flow. The amount of credit between a given pair of users is usually proportional to the degree of trust that exists between them. A user can route payments to another user over a path in the network that has sufficient credit. Once a payment gets routed from a sender to a receiver, all edges along the path will get decremented by the transmitted amount.
Both centralized and decentralized credit networks currently exist. In the centralized version [12,17], a service provider, e.g., a bank, constructs and maintains a database of all link weights, facilitates transactions between users, and performs updates to users' credit links post transactions. In the decentralized version [15,18,21], users maintain their own credit links, find credit routes cooperatively, and perform updates locally. Evidently, since there is no central server to manage the network/users, find paths, and route payments, operation and maintenance of such distributed credit networks is more challenging, but the design offers better privacy guarantees and is intuitively more resilient against failures. In this paper we focus on this decentralized version.
Challenges: For broad-based acceptance and use, any credit network has to handle the following three major challenges: (a) Concurrency: In a credit network, several concurrent transactions could occur (e.g., Ripple's XRP processes 1500 transactions per second), with many of them potentially using the same credit links. The network design ought to support this, while ensuring the integrity and atomicity of every transaction -ensure either all credit links get decremented along the path between sender and receiver, or none at all. This guarantees that the right receiver gets the payment, and prevents double-spending of credits. (b) Efficient routing: Routing of a credit payment, requires finding of a path between a sender and receiver that has sufficient credit, in an efficient way. This needs to be done in a network where the users know only their immediate neighbors, and the network topology is dynamic due to user churn. (c) Privacy: We believe that, at a minimum, a well-designed DCN needs to guarantee sender and receiver privacy (does not reveal their identities), as well as privacy of the amount transacted between them. The DCN also needs to ensure un-linkability of transactions, guarantee the privacy of the intermediate users in the path, as well as hide the network topology from adversaries. We note that today's blockchain-based networks, such as Ripple make their entire transaction history and network topology public.
Contributions: In this paper, we present BlAnC, a fully decentralized blockchain-based credit network that provides:
(1) User and transaction privacy, while providing transaction integrity, and accountability. We also allow users to dynamically choose their transaction amounts, based on current available liquidity in the network. (2) On-demand routing, that can swiftly adapt to changing network topology, with quick on-boarding/off-boarding of users, and very low maintenance overhead. (3) Capability for concurrent transactions. (4) Distributed blockchain-based approach to publicly document transactions and identify malicious actors in transactions, while preserving both user and transaction privacy.
In essence, we propose an alternative to proposed landmarks based routing and DCN maintenance techniques [10,20,23], by having a subset of users facilitating transactions, termed routing helpers (RHs). The set of helpers can change over time, and our protocols are resilient against possible collusion of the helpers. We also discuss possible optimizations of our work.
Outline: In Section 2, we review relevant work in the area of credit networks. In Section 3, we give our system model and assumptions. In Section 4, we review the adversary model, and required privacy/security properties. In Section 5, we present our protocols. In Section 6, we present our security analysis in the universal composability framework. In Section 7, we analyze the time, space, message, and communication overheads of BlAnC. In Section 8, we present our experiments and performance analysis. In Section 9, we discuss possible optimizations and extensions to BlAnC, and in Section 10, we conclude the paper, and discuss future work.
Since a credit network is essentially a flow network, intuitively, one can use Ford-Fulkerson method [6], or push-relabel algorithms [7],
for computing available credit on a path, but their computation costs (O(V E 2 ), O(V 3 ), respectively, in a graph G(V , E)) do not scale well to large, dynamic, distributed networks (millions of nodes).
Prihodko et al. [5] proposed Flare, a routing algorithm for the Lightning Network, in which each node keeps track of its k neighbors, and maintains links to beacon nodes. Flare reveals the value of a link to users to all nodes in the neighborhood, and works only for Bitcoin transactions. Malavolta et al. [11] propose payment-channel networks that make a tradeoff between privacy and concurrency; additionally their network topology is publicly known to every user in the credit network. Designing a distributed credit network, that maintains user and transaction privacy, while supporting concurrency is a challenge.
There is extensive literature on privacy-preserving transactions in Bitcoin which we do not review here, since credit networks have different structure and privacy needs as compared to cryptocurrencies, which do not require credit links or IOU paths, secure path-finding, etc. In Bitcoin and other cryptocurrencies, any user can buy/sell goods and services to other users, whereas in a credit network, users cannot transact with each other, unless they can find a path between them. Although, unlike Bitcoin and fiat currency used by banks, credit networks enable users to transact in different currencies expeditiously (e.g., 3-5 seconds for XRP payments, vs. 3-5 days for bank wires), and with much lower transaction fees.
Credit networks are broadly divided into centralized and decentralized architectures. In the centralized version, there has been work into reducing the reliance on the central, trusted server by using trusted hardware and oblivious computations [14,24]. In the distributed setting, mechanisms using landmark routing [23] to perform route computation between users and landmark(s), and stitching the paths together to route between users, have been proposed. The landmarks-analogous to real-world banks-have less control over the network than in the centralized setting. We now discuss the prior work most relevant to this paper [10,20].
SilentWhispers [10] presented a DCN architecture using landmark routing, in which a subset of paths between a sender and receiver is calculated, via several landmarks. At regular time intervals, each landmark starts two instances of breadth-first-search (BFS) rooted at itself. One between the sender and itself, and the other between the receiver and itself. These two paths are stitched together to form a complete path between sender and receiver. While SilentWhispers provides transaction integrity, accountability, as well as sender/receiver and transaction value privacy, it does not provide mechanisms for concurrent transactions (essential for scalability). It is also vulnerable to deadlocks, and requires users to join the network only at fixed time intervals. Additionally, prior to going offline, a user needs to hand over her signing keys, and other transaction-related data to the landmarks, which will impersonate the user during absence.
Roos et al. [20] presented a DCN which uses graph embedding for efficient routing, with support for concurrent transactions. The embedding algorithm constructs a rooted spanning tree of the network graph. Nodes are addressed based on their distance from the root and routing is performed based on prefixes. In [20], (a) senders pick random credit amounts to transmit along a path, without knowing whether there is adequate liquidity on the chosen path, which leads to a high rate of transaction failure, (b) there is a waiting time imposed on a user to join the network, and (c) a path is greedily chosen based on a heuristic estimate of closeness to the receiver. In a network without high dynamicity, this could lead to linkability of transactions, and eventually compromise sender/receiver privacy.
In contrast, in our approach BlAnC, the maximum credit available on a path is computed during the Find Route phase (first phase), and users can dynamically choose their transaction amount. Further, the on-boarding process does not require a user to wait. We do not pre-compute routes; all routing is done on-demand at the start of a transaction.
While [10,20] represent progress in this area, their solutions do not provide resilience against transaction failures, capabilities such as rollbacks and timeouts, and cannot easily be adapted to real-world credit networks. We have proactively chosen to design a blockchain-based solution, to create a secure, anonymous, and distributed events ledger for BlAnC, with built-in anonymity. Thus our system can be augmented to fit in with real-world, well-regarded blockchain-based credit networks [18,21].
A credit network is a directed graph where the vertices of the graph represent the users or member nodes of the credit network, the weighted edges represent the flow of credit between the nodes. A directed edge with weight γ from node j to node k signifies that k has extended γ credits to j. The in-degree of k signifies the number of nodes that k has extended credit to, while the out-degree of k signifies the number of nodes that have extended credit to k. A node can lose no more than the total credit it has extended to its neighbors. Our DCN consists of nodes with credit relationships, credit senders and receivers, and a group of volunteering nodes called routing helpers who facilitate transactions between them. We assume all credit amounts are non-negative integers. We also assume that credit transfer between a sender-receiver pair happens over multiple paths to increase value privacy. We give our table of notations in Table 1.
Routing Helpers: We assume the existence of a dynamic set of routing helpers (RHs) who help route transactions (RHs do not know the identities of the sender, receiver, and any intermediate nodes on the path). Any well-connected node can volunteer to be an RH by writing a "volunteer" message to the Blockchain containing its public key. A sender-receiver pair creates a credit transfer path between itself using an on-demand routing protocol with the help of intermediate RHs. Credit may be distributed across multiple paths to improve unlinkability and transaction privacy. In BlAnC, the RHs help set up checkpoints, which minimize the number of rollbacks, shorten the length of a path segment along which a failed transaction (or path set-up) needs to be re-tried, and provide resilience. For simplicity, we do not discuss routing fees or mining incentives in this paper. Incorporating these into an implementation of BlAnC would be trivial, using techniques such as [4].
Blockchain: All nodes, in BlAnC are part of a Blockchain (BC). Unlike in Bitcoin, where transactions are written to the BC, in BlAnC, the miners write signed messages to the BC, converting it into a distributed events ledger. Each node is subscribed to the BC, so whenever a new block is written to the BC, all the nodes in the network will get notified. When a node needs to write a message, The RHs or any nodes in the network can become miners who help in writing transactions from the message pools. The system model calls for a low mining difficulty in the credit network for near instantaneous generation of new blocks on the BC. This will facilitate fast transactions and rollbacks. As the miners themselves are part of the DCN, thus high mining complexity (proof-of-work) is not essential in BlAnC. The block chain will be used for proof of transactions (and misbehavior); any adjudication and punitive enforcement of misbehavior is out of scope of this work. BlAnC is designed for decentralized anonymity, using a database for credit link weight storage might be more efficient but it leaks private information.
Joining/leaving the network: A node which needs to join any DCN needs to find at least one network node that is willing to extend credit to, and/or receive credit from it. In BlAnC, the joining and the existing node share their pseudonymous identities and their corresponding real identities (verification keys), along with the agreed link weights for the credits between them. The new node also joins the BC network to receive update messages from the BC (including updates about RHs). A node leaving the DCN permanently just needs to set its link weights to zero and inform its neighbors to do the same for its incoming links. Any node going offline temporarily cannot be part of any ongoing transactions in the network. Before going offline, the node needs to inform its neighbors not to send any Find Route packets to it until it comes back online. We discuss handling disconnections, etc., in Section 5.5.
In our system, the adversary can adaptively corrupt a subset of users. Once user i is corrupted, its credit links will be controlled by the adversary, the adversary can misreport i's link credit value, not respond to requests, relay fraudulent messages to neighbors, and try to re-route payments to other adversary(s). An adversary can also corrupt RHs, who could possibly collude with other malicious users, but we assume a honest majority of RHs. We assume that an adversary cannot corrupt all users in the DCN, and thus may know partial network topology, but does not have global knowledge.
We assume that all users have a long-term verification/signing key-pair, and user i's long-term key-pair is denoted by (vk i , sk i ). Further, all users have pseudonymous, temporary key-pairs; let us denote the temporary verification/signing key-pair of user i by (V K i , SK i ). The temporary key-pair is signed by the long-term signing key: σ ← Siдn sk i (V K i ). This effectively ties the temporary keys (identities) to the real/longterm identity. Each user i exchanges its temporary key-pair with all of its neighbors, who in turn verify i's pair using i's long-term verification key. A user's pseudonym and temporary key-pair do not change unless there is a dispute or user failure. The temporary verification key of each RH in the system is known to all users, along with the permanent public encryption key of the RH. Sender and receiver in a transaction share each other's temporary key-pairs. Desired Security/Privacy properties: We now outline the privacy and security properties provided by our system. Sender/receiver privacy: An adversary will not know the real or pseudonymous identities of the sender/receiver in any successful transaction, unless she is their next-hop neighbor (all neighbors know each others' identities). Link privacy: An adversary only knows the value of credit links adjacent to her. Value privacy: An adversary not on the sender-receiver path does not know the amount being transacted. A corrupted node on a sender-receiver path will know the fraction of the amount transacted through her (unavoidable), but will not know the sender/receiver identities. Also, an adversary cannot compute the total credit transferred between two node pairs without compromising at least one node on all the credit fraction paths (the sender-receiver pair transfer credit concurrently along multiple paths to improve unlinkability). Accountability: An adversary cannot re-route payments or misreport her credit link value without being detected by her honest neighbors. Malicious users violating the protocol can be identified and barred from being in the credit paths.
Integrity/Rollback: If a transaction does not go through successfully (after multiple retries), every credit links on the sender-receiver path will get rolled back to its original value. If a transaction goes through successfully, the credit links on the path will get decremented by the credit amount correctly.
The operations of BlAnC can be summed up using three broad phases: Find Route, Hold, and Pay, which we discuss here.
In this phase, at a high-level a sender Alice needs to send receiver Bob an amount α, shares of which will be transmitted along different paths. Alice and Bob agree on the number of paths, n, and pick two RHs for each path (to break up the path and improve unlinkability).
The maximum transmittable amount along each path, α i (where i ∈ [1.
.n]), will be determined dynamically by Alice and Bob after the RHs find a path between Alice and Bob, and report to them the maximum available credit on that path. As shown in the illustration in Figure 1, Alice and Bob use RHs Charlie and Denise. The route between Alice and Bob is segmented at the two RHs: segment between Alice and Charlie (seg AC ), segment between Charlie and Denise (seg CD ), and segment between Denise and Bob (seg DB ). Alice broadcasts a find message towards Charlie on seg AC ; the message is broadcasted forward by each neighbor that receives it until the copies reach Charlie. Bob performs a similar broadcast of the findReceive message towards Denise on seg DB . Both RHs only act on the first find or findReceive messages they receive, and drop all later duplicate messages. For readability, only a single path (seg AC , seg CD , seg DB ) between Alice and Bob is shown.
In case the find or findReceive did not reach the intended routing helper, Alice or Bob respectively, can update the hopMax value in the tuple before re-broadcasting it. When the find message reaches Charlie, he retrieves the maximum credit available on seg AC , C s = 65, and forwards the find message to Denise. The max. credit available on seg CD is 45, so Denise sets C s = 45, and forwards a findReply message to Charlie, who in turn forwards the message back to Alice. The max. available credit on the path from Alice to Denise (seg AC , seg CD ) is 45. Denise replies to Bob with maximum credit available on seg DB , C r = 30. Finally, Alice and Bob compute min(C s , C r ) = 30. Step 5: Alice and Bob compute out-of-band,
Alice and Bob will repeat Algorithm 1 until α is met, or will choose to transmit α .
Algorithm 1 presents the algorithm (see Table 1 for notations). The steps are self-explanatory. Due to space constraints, we have given the other algorithms invoked within Algorithm 1 in the Appendix A.
After the Find Route phase, the path between Alice and Bob is identified. Now, we need to ensure that all the nodes on the path from Alice to Bob commit to the current transaction by signing contracts with their neighbors on the path. The idea is neighbors j and k (represented by (j, k)) each sign a contract which specifies their current and future link weights (after the transaction), represented as cw jk and f w jk respectively, and store each other's signatures on the contract. This contract will be written to the BC in the event of a dispute or transaction failure, thus providing accountability.
We give a pictorial representation of the Hold Phase that happens from both Alice and Bob in Figure 2. Alice constructs a hold tuple with α i = 30 and forwards it on the Alice-Denise path (in the figure, α i is contained in every contract H jk , for neighbors j, k). Each neighboring node-pair on the Alice-Denise path creates hold contracts between themselves. In parallel, Bob creates a holdReceive tuple with α i = 30, and forwards it on the Bob-Denise path, seg DB . Each node on the Bob-Denise segment seg DB segment writes the corresponding contract, signatures of its neighbor and itself on the contract (σ j , σ k , for neighbors j, k) into it's log file for accountability. Each RH writes a message to the BC whenever they receive hold and/or holdReceive tuples indicating the successful reception of the tuple by them.
Algorithm 2 and Algorithm 3 show the sender and receiver portions of the hold phase. Charlie, on receiving hold, calls MultiSig(), and updates txid, writes a signed message to BC using BC.write((V Alice and Bob pick a pre-image, x ← {0, 1} λ out-of-band, and compute txid ← H (x) (Line 3 in Algorithm 2). Note that after successful completion of the transaction, Bob will write x to the BC, which will help all nodes on the path verify that the transaction concluded successfully. Alice sends a hold message on the seg AC to Charlie, who will in turn forward it to Denise on seg CD (Line 3 in Algorithm 2). The hold message helps create pairwise contracts for nodes on intermediate edges on the path from Alice to Denise; the contracts are binding for them. The hold messages follow the path used by txid on seg AC , and txid on seg CD in the Find Route Phase. When Charlie or Denise receive the hold message, they write a signed message to the BC, which indicates to all nodes on the previous segment that the hold message reached the target RH. In the MultiSig algorithm (Line 5, 7, 12 in Algorithm 2), nodes exchange pairwise signatures on contracts; this step is intuitive, and is given in Algorithm 5. The hold message will update the transaction id stored by the nodes along the path to the actual transaction id, txid. The intermediate nodes follow the same procedure as those on seg AC , except with txid instead of txid .
Denise receives the holdReceive tuple and then creates hold contract with the neighbor on txid path. On receiving the hold from the neighbor on seg CD Denise establishes a full path marked by txid from Alice to Bob. Finally, Denise writes a signed message to BC by calling BC.write((V
Similarly, Bob will send a holdReceive message on seg DB , which will follow the path with txid and create pairwise contracts for each link on the path (Line 3 in Algorithm 3). The nodes on seg DB will also get updated with the actual transaction id, txid. When Denise receives the holdReceive message, she writes a signed message to the BC, thus indicating to all nodes on the seg DB segment that the holdReceive message reached the target RH. The hold and holdReceive messages from Alice and Bob, respectively, contain a tD parameter. This parameter indicates the time at which the hold contracts will timeout if the nodes don't see a signed hold message (for nodes on seg AC and seg CD ) or a signed holdReceive message (for nodes on seg DB ) corresponding to txid from their target RH. At the conclusion of the Hold phase, the three different paths from the Find Route phase coalesce into a single path marked by txid from Alice to Bob through Charlie and Denise.
At the end of the Hold phase, all nodes on the path from Alice to Bob would have committed α i credits to the current transaction, txid, by signing contracts with neighbors on the path. In the Pay phase, Alice sends a pay tuple along the path to Bob: pay(txid, α i , tD) to complete the transaction. Algorithm 4 shows the steps of the Pay phase; we give a pictorial representation of the Pay phase in Figure 3. Each node first signs pay contracts, corresponding to its previously signed hold contracts, with neighbors on the path and changes its link weights: this step is intuitive, and is given in Algorithm 5. Whenever Charlie or Denise receive the pay message, they write a signed message to the BC, thus indicating to all nodes on the previous segment that the pay message reached the target RH. The pay message from Alice, contains a tD parameter indicating the time at which the pay contracts will timeout if the nodes don't see a signed pay message for txid from their target RH.
Because of low mining complexity in the BC, we assume that there will not be any shortage of miners. Thus ensuring timely propagation of new blocks containing latest messages from nodes within the network. The relatively higher volume of messages in BC can be dealt by creating an archived snapshot of BC at certain fixed time intervals and starting a new one-block chain. In this model, individual resource constrained user nodes need not store the entire BC, but only the compacted chain from the last snapshot. However, unconstrained devices (users, RHs) can store longer chains of the BC to act as a source of truth for older transaction data.
Whenever a new block is mined, and written onto the BC, the underlying BC protocol's consensus algorithm synchronizes it across the network. The proposed credit network can be deployed on any existing BC as long as it can accommodate certain features such as supporting individual nodes writing signed messages to the BC as opposed to writing transactions, and also have low mining complexity. However, if the nodes on any segment do not see a hold message from their target RH before timing out, they drop the hold contracts and reservation on their links, since the transaction timed-out in their segment, and the Find Route phase will be retried on that segment. All the nodes on the specific timed-out segment also publish the dropped contracts onto the BC. This will expose the offending node's (node which caused the time-out) ephemeral identity and thus its neighbors will not forward the find tuple to this node for the current transaction when the Find Route phase is retried in current segment. The offending node's privacy in the network is still maintained and only its immediate neighbors find out that the node timed-out in the current transaction. The offending node could be an RH, then the sender-receiver can try again or abort the transaction and start with a new set of RHs.
To illustrate, if Charlie had written the hold message to BC and Denise did not, then Charlie will retry for seg C D by repeating the Find Route phase, and Hold phase to Denise, to find an alternate path. If the timeout occurs after Denise has written a hold message on the BC, but the holdReceive message is not complete, then Bob will retry the transaction for seg DB on its end. Timeout in Pay Phase: On timeout, each node j on a path txid on the timed-out segment, will call BC.write (txid||H jk ||P jk ) if they had a pay contract or just BC.write (H jk ) if they did not receive a pay message from neighboring node. In the pay phase, seg AC or seg C D time-out if target RH (Charlie or Denise, respectively) did not write a signed pay message to the BC indicating successful reception of pay message. Segment seg DB times-out if nodes on the segment do not see a success message on the BC from Bob, with a correct pre-image for txid. When the current transaction cannot be completed because either the timeout occurred on seg AC , or if there are no alternate viable paths on seg C D or seg DB , Alice or Bob can abort the transaction. To abort transaction and initiate a rollback of any changes in the network (from pay contracts affecting link weights) tied to txid, Bob or Alice write the tuple: (txid, x, failurerollback) to the BC using BC.write. All nodes on path should delete hold contracts and revert back to previous link weights if they had any pay contracts associated with transaction txid.
Alternatively, if the timeout occurred on seg C D or seg DB , then Charlie or Denise, respectively, will retry to find an alternate path. Since all contracts were written to the BC, all honest nodes in the path know which node timed out the transaction (faulty node), either by malicious behavior or by going offline, the honest nodes will route retry packets to neighbors other than the identified faulty node to prevent subsequent failures. If Charlie wrote the pay message to the BC, then Charlie will retry the Find Route, and Hold phases to Denise to find an alternative path, before retrying the Pay phase again.
In the absence of malicious nodes in the network, only six messages will be written to the BC. Three messages are written by the RHs after the Hold and two message in the Pay phases. The sixth message is the success message written by Bob to the BC informing the rest of the nodes on the path about the transaction being successful. Since no node involved in the transaction exposed their identity, there is no need to change any node's pseudonymous identities. However, if the transaction was retried, that is, a timeout occurred, all nodes involved in the transaction will need to update their pseudonymous identities and share new pseudonymous identities with each other and their neighbors. This rekeying will help reduce linkability between transactions as now all the nodes' previous pseudonymous identities are in the BC.
txid, tS Output : Tuple (σ j , σ k , contract) stored at node j and k Parties : Node j and k
Malicious RHs: In case of misbehaving RHs where the RHs neglects to write hold/pay tuple reception messages to the BC, other nodes on the path would timeout. They would then dump all the hold/pay contracts for the given transactions on to the BC. This would show that all nodes on the went through with the transaction and it was the misbehaving RH who did not update the transaction on the BC.
There is a possibility of an RH changing its public identity and coming back as a new one after it is identified as malicious. However, if users choose well-known RHs (e.g., one that has written many transactions to the BC), then the impact of such a malicious RH can be significantly mitigated. Even in the presence of misbehaving RHs the sender/receiver do not end up losing any credits as the transaction will either get re-routed or aborted in case of failure.
We prove the security of our constructions in the Universal Composability (UC) framework [1] which is a well-known framework used to analyze the security of distributed protocols. The UC paradigm elegantly captures the conditions under which a given distributed protocol is secure, by comparing it to an ideal realization of the protocol. To this end, the UC framework defines two "worlds": the real-world, where the protocol, π to be proved secure runs, and the ideal-world, where the entire protocol, ϕ is executed by an ideal, trusted functionality, where all users only talk to the ideal functionality via secure and authenticated channels. The goal then is to prove that no distinguishing algorithm, commonly called as "environment", Z, can successfully distinguish between the execution [18], the max. number of paths, and hence n, for a single transaction is 7), d denotes node degree, k is the number of nodes on a single path (k ⊆ M, |k | << |M |), c is the max. path length between sender and receiver (from Ripple [18], the max. path length is 10).
Time Space Messages Regular users Charlie (RH) Denise (RH) Find Phase
(EXEC) of the two worlds. The notion of UC security is captured by the pair of definitions below: Definition 6.1. (UC-emulation [1]) Let π and ϕ be probabilistic polynomial-time (PPT) protocols. We say that π UC-emulates ϕ if for any PPT adversary A there exists a PPT adversary S such that for any balanced PPT environment Z we have EXEC ϕ, S, Z ≈ EXEC π, A, Z Definition 6.2. (UC-realization [1]) Let F be an ideal functionality and let π be a protocol. We say that π UC-realizes F if π UC-emulates the ideal protocol for F .
We define a distributed credit network functionality F DCN in the ideal world, which consists of F FindRoute , F Hold , F Pay , and F BC . An adversary can corrupt regular users and routing helpers at any time, upon which the user's responses to queries by F DCN will be generated by the adversary. We assume F DCN maintains an adjacency matrix of all users in the network, where the entries of the matrix are the link weights, which is regularly updated when F FindRoute and F Pay are called. The definitions of F FindRoute , F Hold , F Pay , and F BC , discussion about their design choices and correctness, and the proof of the following theorem is available in the Section 12. Theorem 6.3. Let F DCN be an ideal functionality for BlAnC. Let A be a probabilistic polynomial-time (PPT) adversary for BlAnC, and let S be the ideal-world PPT simulator for F DCN . BlAnC UC-realizes F DCN , for any PPT distinguishing environment Z. Sketch: At a high level, the proof shows that no PPT distinguishing environment Z can distinguish between the outputs of the ideal-world simulator, S, and a BlAnC adversary A. Ideal-world S mirrors the actions of a real-world A, and we show that if A cheats in the real-world, S would also break the security of the F DCN , which is not possible.
In this section, we analyze the performance of our system with respect to time, space, message, and communication complexities. Time is measured in terms of the average execution time of a cryptographic operation, the space is measured in terms of the total storage required, the message complexity is measured in number of messages, in the worst case, and the communication complexity is the number of bytes of information transmitted. Table 2 shows the asymptotic time, space and message complexities. Table 3 shows the number of encryptions, decryptions, signatures, and hashes at each node during the Find Route, Hold, and Pay phases. Table 4 shows the communication complexity in bytes at different nodes. Joining the network: When a new node joins the credit network, it shares pseudonymous keys, verification keys, and link weights with nodes that it will be connected to in the network and stores these values. This is a one time setup cost and is linear in the number of neighbors the new node will have in the network. The node also joins the blockchain which incurs a constant time/space overhead and is a one time setup cost.
Key exchange after timeout: When a transaction times out, all nodes involved in the transaction would have published their hold and pay contracts to the BC, exposing their pseudonyms. After termination of a timed out transaction, regardless of whether it was finally successful or aborted, all involved nodes need to establish new pseudonyms with their neighbors. The time complexity of this step is linear in the number of nodes in the path and degree of each node, O(k • d), where d is maximum node degree in the DCN.
The cryptographic operations used in the protocol, which are AES-256, SHA-256, RSA-2048 and ECDSA were implemented using C++ Open-SSL libraries [22]. The simulations were performed on a desktop class machine with Intel(R) Core(TM) i7-7600U CPU @ 2.80GHz and 8GB RAM. We use ns-3 [16], a discrete event network simulator to test BlAnC. The simulations were run on a 100 node network with the nodes connected over WiFi. Based on the fact that the Internet's diameter is around 18, in our simulation setup, the sender and receiver are at a distance of 15 hops away from each other, on a path passing through the two RH. This distance accounts for path stretch from Alice to Bob when using two RHs. The network's physical layer delay characteristics are set to the Constant Speed Propagation Delay Model and loss characteristics are set to the Log Distance Propagation Loss Model, both available in the ns-3 codebase. The channel coding was set to Orthogonal frequency-division multiplexing at a data rate of 6 Mbps. The simulations were run with multiple concurrent transactions taking place at the same time. A total of 200 transactions were simulated.
Table 5 shows the timings for the cryptographic operations performed by nodes on a transaction path for the different phases during a BlAnC transaction (emulated on the same desktop class machine). As reflected in the figure, the cryptographic operations in the Hold phase and Pay phases contribute very little to the time delay, that is, ∼ 37 ms as opposed to 4 ms in the Find Route phase. The time delay in the Find Route phase is largely attributed to the ad hoc, on demand path finding technique of BlAnC. This delay is a trade-off to ensure that the privacy of sender and receiver is protected as each transaction triggers a new set of path searches and the paths to chosen RHs are not pre-determined. Figure 4 shows that majority of the time delay in BlAnC comes from the network when compared to delay incurred due to cryptographic operations. The error bars represent the standard deviations of the delay. From the ns-3 simulations, we observed that the total time taken by the Find Route phase to conclude was on average 7.303 secs. This is the time taken by Alice and Bob to determine the maximum value of α i credit that can flow between Alice and Bob in the chosen path for the transaction in question. The delay of 7.303 secs includes network delay, while the delay contributed by cryptographic operations was approximately 4.158 ms. In comparison to SilentWhispers [10] which takes 1.349 seconds (the authors only measured cryptographic costs) to determine α i on a path of length 10 hops (BlAnC is three orders of magnitude faster).
The Hold and Pay phases took a total duration of 1.253 secs each. So a complete transaction on average takes 9.809 secs to finish. We did not include the time delays for the BC as those delays would not affect the flow of credit from sender to receiver unless there is an occurrence of a timeout during the transaction.
In the Find Route phase, the cost of finding a path from sender/receiver to their respective RHs, in the worst case could be O(d c ), where d is the maximum degree of a node on the path, and c is the maximum hop count. In practice, c could be set as the maximum length of a path between two nodes, which, according to empirical data collected from Ripple's datasets is 10 [10,18]. This is a one-time cost, which, we believe, will be amortized over time by having the sender/receiver store information about the paths to their respective helpers, over the course of their transactions. The sender/receiver would then only have to follow a fixed path to their RH, and would incur a cost of O(d c ) infrequently. Another way to optimize this cost would be for every node in the network to choose a random d ′ , such that d ′ < d, and send find probes only to the set of neighbors in d ′ .
Each node in the credit network that is involved in a transaction, could keep track of the identity of the RH and the interface it reached the RH from. By using this information as a forwarding table, the number of broadcasts could be decreased in a stable credit network where the links state do not vary frequently. Broadcasts could be used in-case of a stale forwarding table, in which case the sender would retry the Find Route phase with a broadcast instead of a directed find message. This would also reduce the cost of the protocol in the Find Route phase if the intermediate nodes do not need to use broadcasts and already have a path available to a known RH. Each node could also build a history of all the RHs it has used for prior transactions, and prefer to use the ones with which the transactions completed successfully instead of trying to send payment through new RHs.
Graph embedding, as used in [20] could be used in our Find Route phase to construct an optimal path between the sender/receiver and their respective RHs. One could construct a spanning tree of the network rooted at the RHs, and either used tree-base embedded routing (strictly following the edges of the spanning tree), or a more flexible approach, where one greedily chooses the shortest path between two nodes, regardless of whether the shortest path uses edges present in the spanning tree or not.
Since the BC is being used to publish transaction-related messages, the storage of the BC can become challenging, along with the scaling of the DCN. To tackle this problem, the BC can be compressed at regular time epochs as we discussed before. At the end of a time epoch, all nodes would cease transacting and make sure all the payments and links are settled. At this point, the BC can be wiped off and all old data can be compressed and stored with certain nodes which have enough storage, and are willing to store the older BC. The hash of the old BC can be provided at the start of the new BC linking the two together. At the start of the new epoch, all RHs need to declare themselves as RHs again, as there is no historical information available to new nodes joining the credit network in the new epoch.
In this paper, we propose BlAnC, a novel, fully decentralized blockchainbased credit network that preserves user and transaction anonymity, enables on-demand and concurrent transactions to happen seamlessly, and can identify malicious network actors that do not follow the protocols and disrupt operations. We performed security analysis to demonstrate BlAnC's strength and presented scalability metrics. Simulation/emulation-based analysis of the latency of transactions in the DCN demonstrate BlAnC's scalability.
In the future, we intend to implement BlAnC in a real-world testbed like Hyperledger [9] and test impact of real-world network dynamics on the protocols' stability and scalability.
We give details of the algorithms called in the steps of Algorithm 1. All the algorithms below will have common inputs, CI defined as: Algorithm 6: In the Find Route phase, we have three separate transaction ids, txid ′ , txid ′′ , txid ′′′ for finding routes on seg AC , seg C D , and seg DB respectively. Later, in the Hold and Pay phases, the three transaction ids will coalesce into a single id, txid. This is done to hide txid from nodes that may not be on the actual path during the Hold and Pay phases, but might receive a find broadcast message in the Find Route phase.
For finding a route to their RHs, Alice (Line 2-6) and Bob (Line 7-11) broadcast find and findReceive tuples containing the payment information to all their neighbors (with whom they have links), who will then forward the tuples to their neighbors, and so on, until the tuples reach the respective RHs. Bob's outgoing tuple is called findReceive, to distinguish it from find, since the payment will be credited to Bob via his incoming links, as opposed to Alice, whose payment will get debited via her outgoing links. The distance the find and findReceive tuples have to travel is determined by a system-wide parameter, hopMax, which is set by the originator of a tuple. If hopMax is underestimated by an originator (i.e., the find, findReceive tuples cannot reach their destination since hopMax is too low), then the originator will retry after a reasonable time interval. The find and findReceive tuples consist of 5 variables: the transaction id for payment of α i , public keys of RHs, the current running value of the max. available credit on the path, the maximum hop count, and encrypted info by Alice or Bob for their RHs. This encrypted info includes a unique symmetric key generated by the sender, a challenge nonce (y) and timestamp of the generated tuple by the original sender, encrypted by the public key of the target RH. currMax s denotes a running value of the maximum credit available at each intermediate node's outgoing links, on the seg AC , seg C D paths.
Algorithm 7: Starting from Alice, each intermediate node j will reserve, or subtract currMax s from its max. available credit, currMax j , if currMax j > currMax s (Line 3-9), else j will reserve its max. available credit for this transaction. It will then set currMax s to be the minimum of (currMax s , currMax j ). Similarly, currMax r is the running value of the available max. credit at each intermediate node on the Bob-Denise path (Line 13-18). In case the actual payment does not come before the timeout each node in the path will add the reserved amount back to its credit links.
Algorithm 8, Algorithm 9: Once Charlie receives the find tuple, he picks a random txid ′′ and modifies find tuple received from Alice before forwarding it towards Denise to construct seg C D subpath (Alg 8 Line 2). Denise receives the find tuple from Alice and constructs a findReply tuple which consists of currMax s representing the max. credit available on seg AC and seg C D along with some encrypted information for Alice. Denise forwards this tuple along seg C D back towards Charlie along the single path that reached Denise from Charlie represented by nodes with txid ′′ (Alg 8 Line 3-12). Denise also receives findReceive tuple from Bob and will reply with the maximum available credit on seg BD along with encrypted information for Bob in a findReply tuple (Alg 9 Line 6-12). The findReply tuples will be sent only to the first neighbor from whom the corresponding find/findReceive tuple for that transaction id was received. A findReply tuple consists of 4 variables: the transaction id for payment of α i , public keys of RHs, the current running value of currMax s or currMax r , and some information encrypted by RHs for the sender or receiver. Reserve currMax j by min(currMax s , currMax j ), set currMax s = min(currMax s , currMax j ).
8
Construct tuple:
9
Send tuple to all neighbors to whom j has an outgoing credit link. Reserve currMax j by min(currMax r , currMax j ), set currMax r = min(currMax r , currMax j ). Construct tuple: findReceive(txid ′′′ , V K D , reserve(currMax r ), hopMax-1, C B ).
18
Send tuple to all neighbors to whom j has an incoming link.
(1) F FindRoute : The ideal functionality, F FindRoute , is given in Figure 5. The goal of F FindRoute is to find paths between Alice and Bob, and compute the maximum transactable amounts along the paths.
In the first step, the sender Alice, sends the ideal functionality the amount to be transacted, α, the receiver's identity, and the number of shares n of α. She also sends F FindRoute the identities of the RHs that Alice and Bob have agreed to use for each share. In Step 2, for each share, F FindRoute starts an instance of BFS rooted at Alice, and sends each node the transaction id, the id of its parent, and the id of the target RH for this segment, Charlie. When Charlie gets the find(•, •, •, •, •) tuple from Alice, he does:
The find tuple is then sent to all Charlie's neighbors.
Send tuple to all neighbors. end end /* Max. in path between RH s */ Store tuple (txid ′′ , K ABD , y, V K C , reserve(currMax s )).
10
Construct tuple:
, where
The findReply tuple will be Charlie, on receipt of Denise's findReply() does:
Retrieve txid ′ stored in same tuple as txid ′′ , sets his copy of currMax s to be the currMax s received from Denise.
Compose reply to Alice:
5
The findReply tuple will be forwarded only to those neighbors on the path from Charlie-Alice, who have used txid ′ . /* Receiver's RH sending reply */ 6
In parallel, Denise, on receiving Bob's message will retrieve 12 Compose reply to Bob findReply(txid
The findReply tuple will be forwarded only to those neighbors on the path from Denise-Bob, who have used txid ′′′ .
13 end 14 end
with the ids of its children (degree of the node) and the link weights of each connecting edge. Alternatively, the node can reply with (txid, ⊥, ⊥), upon which F FindRoute will ignore this node and continue visiting the other children of its parent node. In addition to modeling malicious nodes, this also models nodes that get disconnected from the network, or faulty nodes. F FindRoute stores a tuple for each visited node, j, (j p , j, currMax j ), and also updates the adjacency matrix with the current link weight values. In Step 3, once the RH, Charlie is reached, F FindRoute computes the max. value that can be transacted along the Alice-Charlie segment, which is the minimum of all the stored currMax values seen so far, currMax 1 , and sets α i = currMax 1 .
Note that there could be possibly multiple routes to Charlie, F FindRoute will terminate this segment after the first time Charlie is reached. Similarly, F FindRoute will find a path between Charlie and Denise, and Denise and Bob, and will find the max. value that can be transacted between them, currMax 2 and currMax 3 (Step 4, 5). Finally, it computes α i = min(currMax 1 , currMax 2 , currMax 3 ), and informs Alice and Bob about α i (Step 6). Note that any node can give fake ids of its children and cause delays, but F FindRoute will terminate once the max. path length, hopMax has been reached.
(2) F Hold : The F Hold functionality is given in Figure 6. For each share of the total amount, the goal of the F Hold functionality is to create pairwise contracts between neighboring nodes that commit to transacting that share.
In the first step, F Hold divides the path into three segments: Alice-Charlie, Charlie-Denise, and Denise-Bob, so that if a hold-failure occurs in any of the segments (e.g., due to unresponsive, or malicious nodes), only that segment will be re-tried upto a threshold number of times. For each share, starting from Alice, the ideal functionality sends each pair of neighboring nodes (j, k), a tuple consisting of the transaction id, the amount α i , and a contract, C h jk , consisting of the current link weight, lw c jk and the future link weight (after the Pay phase), lw f jk between j and k. In Step 2, each node can choose to either accept or reject the contract (if a node doesn't respond within a time period, F Hold assumes its response is ⊥). If a node along the Alice-Charlie segment, rejects the contract, F Hold sends failure messages to all nodes along the segment, writes a holdfail message to the blockchain and terminates. If any node along the Charlie-Denise and/or Denise-Bob segment rejects the contract, F Hold will retry the failed segment a fixed number of times, while the nodes in the successful segments will hold on to their contracts. When a node receives a failure message from F Hold , it will drop its held contracts. If no node rejects the hold contract, F Hold stores a tuple (txid, write, C h jk ) for every pair of nodes j, k. When Bob is reached, he can either choose to accept or reject the contract (Step 3). If Bob accepts, all stored tuples are written to the blockchain, and F Hold notifies each node along the path individually that the hold operation was successful (Step 4). Note that the contracts are established iteratively in a pairwise manner to enable any node along the path to potentially abort the hold operation. (3) F Pay : The F Pay functionality is given in Figure 7. For each share, the goal of F Pay is to finalize the transaction by subtracting the credit values on links along the path from Alice to Bob, and writing it to the blockchain. F Pay works similar to F Hold , the only difference being that at the successful completion of F Pay for all nodes, the matrix stored by F DCN will be updated with the new, decremented link weights. (4) F BC : The blockchain functionality is given in Figure 8. F BC receives messages from F Hold and F Pay . F BC writes tuples to the blockchain, and sends a copy of the new block to nodes (as in the other other ideal functionalities, we assume that all communication between F BC and nodes take place via secure and authenticated channels). This is done by sending (update, B). The node can either accept the update, or decline (unresponsive, disconnected, or non-cooperating nodes). When a new node joins the network, or a dormant node wishes to update itself, it can request a copy of the full blockchain by sending a read message to F BC .
In this section, we give the motivation and reasoning behind some of our design choices for the ideal functionalities.
F FindRoute Ideal Functionality
(1) Sender Alice sends a tuple (α, ID Bob , n) to F FindRoute . For each i ∈ [1.
.n], Alice sends a tuple (ID Charlie , ID Denise ) to F FindRoute (RHs could be different for each share i). (2) For each i ∈ [1..n], F FindRoute starts an instance of breadth first search (BFS), rooted at Alice. F FindRoute will send each node j, a tuple (txid, j p , ID Charlie ).
Each node replies to F FindRoute with a tuple (txid, (j 1 , currMax 1 ), . . . , (j d , currMax d )), or it replies with (txid, ⊥, ⊥), where d is the degree of j. In the latter case, F FindRoute backtracks to the parent node, and ignores this child. For each visited node j, F FindRoute stores a tuple (j p , j, currMax j ). F FindRoute also updates the matrix stored by F DCN with the currMax (link weight) values. (3) Once Charlie is reached, or the maximum path length, hopMax, has been exceeded, F FindRoute terminates the BFS for the Alice-Charlie segment. In the former case, F FindRoute computes the minimum of all the stored currMax values so far, to find the max. value that can be transacted along the Alice-Charlie segment, currMax 1 , and sets α i = currMax 1 .
In the latter case, F FindRoute aborts. (4) Next, F FindRoute starts an instance of BFS rooted at Charlie, with the goal of finding a path between Charlie and Denise, which proceeds similar to Step 2. If Charlie replies with (txid, ⊥, ⊥), F FindRoute will ask Alice to select a new RH in place of Charlie, and will re-compute α i . Once Denise is reached, or the max. path length, hopMax, has been exceeded, F FindRoute terminates the BFS for the Charlie-Denise segment. In the former case, F FindRoute computes the minimum of the stored currMax values along the Charlie-Denise segment to compute the max. value that can be transacted between Charlie and Denise, currMax 2 . If currMax 2 < α i , it sets α i = currMax 2 . If the hopMax has been exceeded without reaching Denise, F FindRoute will retry finding a path between Charlie and Denise a fixed number of times; if all are unsuccessful, F FindRoute aborts. (5) F FindRoute then finds a path between Denise and Bob in a similar manner, and computes the max. value that can be transacted along that path, currMax 3 . If Denise replies with (txid, ⊥, ⊥), F FindRoute will ask Alice to select a new RH in place of Denise, and will re-compute α i . If currMax 3 < α i , it sets α i = currMax 3 . (6) F FindRoute sends a tuple (txid, α i , ID Charlie , ID Denise ) to Alice and Bob. They can respond with (txid, findaccept) or (txid, ⊥). If F FindRoute receives a (txid, ⊥) from either of them, it aborts. Else it sends them both (txid, findsuccess), outputs all stored tuples of the form (j p , j, currmax j ) on the path from Alice to Bob, and the final value of α i , and terminates. (1) Each node decides on the fly the next node to route to in F FindRoute . This is because each node should be able to decide if it wants to be part of a transaction or not. F FindRoute (1) F BC can receive 4 kinds of write messages: (txid, holdfail), (txid, hold), (txid, payfail), (txid, pay) from F Hold and F Pay respectively. F BC writes the tuple to the blockchain and sends a copy of the newest block B to every node in the credit network by sending a tuple (update, B) to all nodes in the credit network. (2) Each node in the network either replies with (agree, B) or (⊥, ⊥). In the former case, the node updates its copy of the blockchain, has the latest copy of the blockchain stored locally, and is as such synced with the blockchain. However, if the reply was (⊥, ⊥), the node now has an outdated copy of the blockchain and can to be referred to as an outdated node.
(3) If a new node joins the credit network or an outdated node wants to get synced with the blockchain, it sends a message (read) to F BC . F BC now sends a message (update, B ′ ) where B ′ is the copy of the entire blockchain so the new/outdated node is synced with the blockchain.
In this section, we give an informal overview of why our definition of the ideal functionalities preserves the claimed privacy/security properties. The formal theorem statement and its proof is given in Section B.3. F DCN consists of 4 ideal functionalities F FindRoute , F Hold , F Pay and F BC . There are certain pieces of information that are unavoidable to reveal; in fact the construction of the ideal functionalities would be unrealistic without revealing this information. All four ideal functionalities reveal the transaction id, txid, which is a randomly generated hash digest to all nodes in a path. This will only tell nodes along a path that a certain transaction has traversed them, but cannot tell anything more than that. With this in mind, we recollect that we define value privacy to mean that no node not along a path will learn anything about the value transacted for a particular transaction. Now let us consider each of them with respect to the desired security/privacy properties:
(1) F FindRoute : F FindRoute preserves sender/receiver privacy, since it never reveals the sender/receiver identity to any node in the network. Link privacy is preserved, since every node (including sender/receiver) only knows its parent and children. (2) F Hold , F Pay : The F Hold and F Pay functionalities do not reveal sender/receiver information to any node in the network. They reveal the value, α i traversed along a path, and every node knows the weights on the links connecting it to to its parent and children, but nothing more. Every node also doesn't get any information about the network topology, other than its own outgoing and incoming links. (3) F BC : When messages get written to the blockchain, only the txid and holdfail, payfail, hold, pay messages are written to the blockchain. These messages just tell nodes in the network that some transaction, txid, was written to the blockchain, and whether its hold and pay phases went through or not. This doesn't reveal sender/receiver identity, or the value transacted, or any information about network topology.
Proof of Theorem 6.3.
Proof. We need to prove that no environment, Z can distinguish between the outputs of the ideal-world simulator, S, and the real-world probabilistic polynomial-time (PPT) adversary, A. We consider a simulator, S that internally runs A, and, with the help of the ideal-world functionality F DCN , provides whatever inputs A asks for in a run of the real-world protocol. A will then run the real-world protocol, possibly corrupting users, and will generate outputs in each phase of the protocol, which are given to S. Finally, S takes A's outputs and forwards them to F DCN (consisting of F FindRoute , F Hold , F Pay ), who completes the simulation of the protocol in the ideal-world.
Our goal here is to show that if A tries to cheat at any point in the execution of the real-world protocol, it will result in both, the idealworld and real-world aborting. In other words, it is not possible for A to cheat in the real-world in such a way that the ideal-world and real-world simulations go through properly. It follows that if S can exactly mirror the actions of A in the real-world (successfully completing when A completes, and aborting when A tries to cheat, or A aborts), then no environment Z can successfully distinguish between the two worlds, except with negligible probability, where the probabilities are taken over the random coins of A.
Let us consider a complete run of the ideal world and real-world protocols consisting of the Find Route phase, the Hold phase and the Pay phase.
• Find Route phase: In the Find Route phase, S will generate the set of inputs for A: the set of RHs, the number of paths to be found, n, security parameter λ, hash function H , a public ledger BC, and the max. path length, hopMax.
Since all of these parameters are public, S can generate them by itself. A then picks two RHs, Charlie and Denise, generates random txid ′ and txid ′′ along the Alice-Charlie and Bob-Denise path, constructs the find and findReceive tuples, and gives them to S. Now, S needs to simulate this correctly in the ideal-world. S will pick the same RHs that A picked, Charlie and Denise, and call F FindRoute with parameters (txid, α, ID Bob , n, ID Charlie , ID Denise ). Note that S uses a single txid, while forwarding information to F FindRoute , since in the ideal-world, F FindRoute , and not the RHs find routes. But S will record txid ′ and txid ′′ , and will use them while giving A the results of F FindRoute 's run. F FindRoute then starts an instance of breadth first search (BFS) rooted at sender Alice, and each node j along the Alice-Charlie path will receive tuples (txid, j p , ID Charlie ), where j p is j's parent. The BFS proceeds as described in Figure 5; once done, F FindRoute updates its matrix with link weights. At some point, either Charlie will be reached, or hopMax will get exceeded. In the former case, S will store the value of α i , and continue the simulation with F FindRoute on the Charlie-Denise and Denise-Bob paths. In the latter case (which occurs if A has corrupted nodes along the path), F FindRoute will abort. S notifies A of the failure, and terminates the idealworld execution, following which A will have to halt the real-world execution, since a path has not been found from Alice to Charlie. After Charlie has been reached, F FindRoute will continue with the simulation, finding paths from Charlie to Denise and Denise to Bob in a similar way, in serial order. At any point of hopMax gets exceeded without reaching the target (i.e., A corrupts nodes along the way, which forward F FindRoute between themselves, or A aborts), S notifies A that the protocol has failed, which results in both, ideal and real worlds aborting. Finally, S will forward to A the results of F FindRoute 's execution: n full paths from Alice to Bob, and α 1 , . . . , α n . Note that before forwarding to A, S will replace txid with txid ′ , txid ′′ and txid ′′′ along the three path segments, respectively. One can see that there is no way A can cause F FindRoute to run indefinitely, or find paths to wrong users (e.g., instead of Bob, the credit gets routed to A). This ensures integrity of the transaction. Also, corrupted nodes not directly on a path, will not be given any information by F FindRoute , and hence will not know the value transacted through them. Recollect that in our adversary model, it is unavoidable that nodes sitting on a path will know the value transacted through them. Finally, unless A corrupts the next-hop neighbor of either sender or receiver, A is not given any information about the identities of Alice and Bob by S, i.e., in F FindRoute , every node only knows its parent and children, and has no information about other nodes. Hence, S exactly mirrors the actions of A in the ideal-world, aborts at any attempt to cheat by A. It follows that no environment Z can successfully distinguish between the actions of A in the real-world and S in the ideal-world. • Hold phase: In the Hold phase, S will begin by providing A the set of RHs, the number of paths, n, and the amount to be transacted along each path, α 1 , . . . , α n , hash function H , public blockchain, BC. The main point to notice here is that we are giving the adversary all amounts along all paths; this is because we assume a strong adversary, where A can corrupt nodes along all paths between Alice and Bob, in which case A will know all the α i values. A starts the execution by re-using its txid pr ime , txid ′′ , txid ′′′ and keys from the Find Route phase. It constructs the hold tuple for Alice, which is forwarded to S. On receiving the hold tuple, S constructs a tuple (txid, α i ,H jk = (cw jk ,f w jk )), where j is k's preceding node. These tuples are sent starting from Alice's neighbor up until Bob. S re-uses the txid it stored from the find phase. An interesting point is where does S get (cw jk , f w jk ) from? S contacts F DCN , which maintains the matrix of link weights, and gets cw jk from the matrix; f w jk is set to be cw jk -α i , which can be locally computed by S. Now, S forwards the tuples to F Hold , who sends the tuples starting from Alice's neighbor, up until Bob is reached. The ideal-world simulation proceeds as described in Figure 6. If any node along the path replies with a (txid,H jk , ⊥) (which means A has corrupted the node), F Hold aborts the transaction (after a number of re-tries, if applicable), informs A of the failure, calls F BC and writes (txid, holdfail) to the blockchain. This will force A to abort the real-world protocol. If Bob is successfully reached, accepts the hold contract, and the final write call to F BC is successful, S sends A the tuple (txid, α i ,H jk ).
It follows that if A causes any nodes along the path to be unresponsive, does not follow the route created by F FindRoute , or otherwise tries to route F Hold in a circular fashion among corrupt nodes, S will terminate the ideal-world simulation, which will force A to abort the real-world execution. Since the Hold phase has failed, A cannot continue further with the Pay phase. We note that since we are considering a strong adversary, who corrupts nodes along all paths, A will know the values of α 1 , . . . , α n . In practice, this might rarely be the case, and A will only know the values transmitted along those paths on which it has planted corrupted nodes. • Pay phase: The simulation works very similar to the hold phase. □