Summarized by Subhra Mazumdar @subhramazumdar and Sushmita Ruj
TLDR
- Payment Channel Networks or PCNs solve the problem of scalability in Blockchain by executing payments off-chain.
- Due to a lack of sufficient capacity in the network, high-valued payments are split and routed via multiple paths. Existing multi-path payment protocols either fail to achieve atomicity or are susceptible to wormhole attack.
- We propose a secure, efficient and privacy-preserving atomic multi-path payment protocol called CryptoMaze. The protocol avoids the formation of multiple off-chain contracts on edges shared by the paths routing partial payments, guaranteeing unlinkability between partial payments.
Core Research Question
How do multi-path payments in a payment channel network guarantee atomicity and security of partial payments but at the same time ensure efficiency?
Citation
Mazumdar, Subhra, and Sushmita Ruj. “CryptoMaze: Privacy-Preserving Splitting of Off-Chain Payments.” IEEE Transactions on Dependable and Secure Computing (2022). CryptoMaze: Privacy-Preserving Splitting of Off-Chain Payments | IEEE Journals & Magazine | IEEE Xplore
Background
- Payment Channel Network: A payment channel enables several payments between two users without committing every single transaction to the blockchain. Any two users can mutually agree to open a payment channel by locking their coins into a multisignature address controlled by both users. These parties can perform several off-chain payments by locally agreeing on the new deposit balance. Correctness of payments is enforced cryptographically by the use of hash locks, time locks, or scriptless locking. Nodes not directly connected by a payment channel route a payment via an existing set of channels. This set of interconnected payment channels forms a Payment Channel Network or PCN. Lightning Network for Bitcoin and Raiden Network for Ethereum are the two most popular networks.
- Off-chain contracts: These are smart contracts where the logic encoded in the contract is not run by the miners. It is mutually executed by the participants involved in instantiating the contract. The advantage of having off-chain contracts are that computation-intensive tasks can be executed without involving blockchain as long as participants behave honestly. An individual player can prove the correct contract state independently. Cheating is prevented as the state of the contract is signed by all the players. If a party misbehaves by broadcasting a wrong state in blockchain, the counterparty can raise a dispute and publish the valid accepted state. Hashed Timelock Contract (HTLC) is one such example used in PCN for routing payments in the network. The logic used is a hash function, where players need to provide the preimage of the hash to claim coins.
- Multi-path payments: A way of sending (“routing”) high-amount of funds. Because finding a single path that would be able to pay-out (“relay”) adequate funds is tough, the payer instead splits the whole amount into several “partial payments” and routes them through multiple channels.
- Atomicity: All partial payments from a single transaction succeed or fail together. This is a desirable property for a multi-path payment protocol. Applying existing payment protocols like Hashed Timelock Contract on individual paths routing partial payment might not guarantee atomicity. If an instance of the protocol fails in one of the paths, only the partial amount gets transferred to the receiver, violating atomicity.
- Wormhole Attacks: HTLC uses the same commitment across the path routing the payment. Consider an example where U_0 wants to transfer \alpha coins to U_r via nodes U_1, U_2, U_3, ...U_{n-1}, n>3. The coins transferred by U_0 is \alpha+\sum_{i-1}^{n} f(U_i). Node U_3 colludes with U_{n-2} before the protocol starts. In the release phase, U_r decommits and claims the coins. However, node U_{n-2} directly shares the decommitment with U_3. The former cancels the HTLC with node U_{n-3} and the cancellation of HTLC continues till node U_3. So nodes from U_4 to U_{n-3} considers the payment to have failed. U_3 and U_{n-2} steals the fee of all these intermediate nodes, gains \sum_{i=1}^{n} f(U_i). This is termed a wormhole attack.
- Unlinkability of partial payments: A given node will be willing to route full payment instead of partial payments. The success rate is low when payment is split. If a partial payment fails in one of the paths, then the entire payment rolls back. If colluding parties can link partial payments, they will tend to reject such requests and preserve their channel capacity for routing the full amount. Unlinkability must be ensured to prevent censoring split payments.
Summary
- We propose CryptoMaze, an efficient, privacy-preserving, atomic multi-path payment protocol. Our protocol optimizes the setup cost by avoiding the formation of multiple off-chain contracts on a channel shared by partial payments.
- Given a payer wants to transfer some coins to a payee efficiently via the PCN, none of the nodes in the network must learn the identity of the payer, payee, or the coins transferred, and no honest party should lose coins while routing the payment.
- We have modeled CryptoMaze and defined its security and privacy notions in the Universal Composability framework.
- Experimental Analysis on several instances of Lightning Network and simulated networks show that our proposed payment is as fast as Atomic Multi-path Payments. The run time is around 11s for routing a payment of 0.04 BTC in a network instance of 25600 nodes. The communication overhead is within feasible bounds, being less than 1MB.
Method
-
The following steps are followed by an instance of our proposed protocol Cryptomaze:
-
Mapping set of paths to set of edges:
- A distributed routing algorithm is used for getting the set of paths routing the payment from payer to payee.
- Once the algorithm returns the set of paths, edges are scanned in breadth first order starting from the payee and they are recorded in a set PC that is used in next phases.
- Edges are denoted by the nodes X,Y they connect as id_{X, Y}.
-
Preprocessing Phase:
-
Sampling secret values: The payer M samples secret for all intermediate channels routing payment. The payee N samples a secret as well. No one shares the secret.
-
Condtions for off-chain contract: The condition used in the contracts established on each of the channels are denoted as follows: R_{M,A} for id_{M,A}, R_{A,B} for id_{A,B}, R_{A,C} for id_{A,C}, R_{B,D} for id_{B,D}, R_{C,D} for id_{C,D}, and R_{D,N} for id_{D,N}. Conditions based on Discrete Log Hardness. Node A splits the payment and sends it to nodes B and C. The condition R_{M,A} must be constructed so that the secrets provided by either B or C helps A in claiming the amount from M. If A establishes the same contract R with nodes B and C, then R_{M,A} = e_{M,A} * x_A G + R, where G is the generator of elliptic curve group. If B and C collude, they can link their payments. The situation is shown in the figure given below.
-
To avoid the problem, two different conditions R_{A,B} and R_{A,C} are assigned to off-chain contracts on channels id_{A,B} and id_{A,C}. A adjusts the value by adding x_{A,B}G to R_{A,B} and x_{A,C}G to R_{A,C} to ensure equality. Thus, we have R_{M,A} = R_{A,B} + e_{M,A}x_AG + x_{A,B} G where R_{A,B} + x_{A,B}G = R_{A,C} + x_{A,C}G.
-
Let Z = R_{A,B} + x_{A,B}G = R_{A,C} + x_{A,C}G. If we fix the discrete logarithm of Z to x : Z = xG = R_{A,B} + x_{A,B}G = R_{A,C} + x_{A,C}G we can calculate the values x_{A,B} and x_{A,C}. Again, x_A = x_{A,B} + x_{A,C}. Even if the off-chain contracts R_{A,B}, R_{A,C} and R_{M,A} are settled on-chain, still a miner cannot establish linkability between the three. If x_{A,B} and x_{A,C} is not known to the miner, then it can establish a relationship between discrete logarithm of R_{M,A} and discrete logarithm of R_{A,B} or R_{A,C} with negligible probability.
-
-
Contract Forwarding Phase: M forwards condition R_{M,A}, the off-chain contract formed with A, timelock t_{end}+3\Delta, where \Delta is the time taken for a transaction to be confirmed in blockchain. A sends off-chain contracts to B and C, having conditions R_{A,B} and R_{A,C}, having timelocks t_{end}+2\Delta, B sends off-chain contract to D, with condition R_{B,D} and C sends off-chain contract to D as well, with condition R_{C,D}. Finally, D forwards the condition R_{D,N} to N.
-
Release Phase: Initiated only if N has received the full amount. N claims coins from D, and rest of the node follows suit until A has claimed the coins from M. If A gets solution for R_{A,B} from B but C crashes, still he can claim coins from M by solving R_{M,A}.
Results
-
We choose to compare our protocol with Multi-Hop HTLC, Atomic Multi-path Payment and Eckey et al..
-
We take snapshot of Lightning Network dated May 2021 and simulated network instances. For generating synthetic graphs of size ranging from 200 to 25600, the Barábasi-Albert model was used.
-
Our code is available publicly (dropbox link). The following metrics are used to compare the performance of CryptoMaze with state-of-the-art:
-
Optimization of off-chain contracts:
- Payment instances sharing channels for a single payment increased from 0.04% to 38.6%. Channels shared for a given instance increased from 33% to 42.8%. A channel gets shared no more than 4 times.
- For state-of-the-art, the total number of off-chain contracts per payment instance increased up to 54.5%.
- Reason: When the transaction amount per payment was increased, the liquidity of channels decreased. Payments were split into smaller amounts and routed via multiple paths. Thus, we observed that the number of instances where the routes were not edge-disjoint increased.
- With the increase in transaction amount, the number of paths routing a payment increased due to the increase in the split. The number of off-chain contracts established per payment increased for the state-of-the-art protocols.
- When the size of the network increases, the higher the chance of finding routes with higher capacity, the more options of edge-disjoint routes. Hence, a decrease in the number of off-chain contracts is observed.
-
Computation Time:
- The execution time on average of CryptoMaze is 1.85 seconds. The protocol is approximately 3 times faster than Eckey et al. and 17.5 times faster than MultiHop HTLC, as shown in the figure below.
(Computation Time, Lightning Network Snapshot May 2021) - The time taken increases gradually with the increase in the size of the network. The execution time does not exceed 11 seconds upon execution on an instance of size 25600. Run time of AMP is 1.7 times of CryptoMaze, that of Eckey et al.. and Multi-Hop HTLC is 3.5 times and 18 times that of our protocol on an average.
(Computation Time, Simulated Network instances) - Reason: Time taken to execute CryptoMaze is comparable to Atomic Multi-path Payment, sometimes even lower. This is due to mapping the set of routes into a set of edges before establishing the off-chain contracts. All the previous protocols considered each route individually, increasing the setup time. Eckey et al. have a higher run time due to the use of homomorphic encryption. In Multi-Hop HTLC, generating zero-knowledge proofs for the preimage of a given hash value is an expensive process in terms of computation cost.
- The execution time on average of CryptoMaze is 1.85 seconds. The protocol is approximately 3 times faster than Eckey et al. and 17.5 times faster than MultiHop HTLC, as shown in the figure below.
-
Communication overhead:
- It is 93.203KB, on average for CryptoMaze, as shown in the figure below. The overhead is 14.5 times greater than that of Atomic Multi-path Payment and 2 times more than that of Eckey et al. . The communication overhead of Multi-Hop HTLC is 297 times more than CryptoMaze.
(Communication overhead. Lightning Network Snapshot, May 2021) - The communication overhead shown below increases with an increase in the size of the network, with the communication overhead not exceeding 1000KB or 1MB on an instance of size 25600. On average, the communication overhead of CryptoMaze is 5 times of Eckey et al., and 33 times of Atomic Multi-path Payment. However, the overhead is 105 times less compared to Multi-Hop HTLC.
(Communication overhead. Simulated Network instances) - Reason: It is observed that Atomic Multi-Path Payment has the lowest communication overhead because each node forwards just a single commitment to its neighbor in the path routing payment, yet they are susceptible to wormhole attacks; Eckey et al’s protocol has slightly less communication overhead compared to CryptoMaze. However, the drawbacks are that it is computation-intensive. Each node forwarding payments uses homomorphic encryption to encrypt the payment information. The public key of the receiver is forwarded to all the nodes routing partial payments, and colluding parties can link payments by observing the common public key. Lastly, Multi-Hop HTLC has the highest communication cost. The zero-knowledge proof \Pi forwarded to each node has a significant size, plus multiple off-chain contracts are formed on shared edges, increasing the communication overhead. The result demonstrates that though CryptoMaze has slightly higher communication overhead, it is efficient and scalable in terms of computation cost and resource utilization.
- It is 93.203KB, on average for CryptoMaze, as shown in the figure below. The overhead is 14.5 times greater than that of Atomic Multi-path Payment and 2 times more than that of Eckey et al. . The communication overhead of Multi-Hop HTLC is 297 times more than CryptoMaze.
Discussion and Key Takeaways
- Our protocol achieves the followng privacy and security properties: it is atomic, partial payments are unlinkable, none of the participants can identify the payer, payee, or the payment amount, and none of the honest parties lose coins.
- Scriptless lock based on a two-party ECDSA signature can be easily integrated into our framework for conditional payments. Such scriptless scripts are indistinguishable from simple payment transactions when published on the blockchain. This saves blockchain space. Also, payments from payment channel networks cannot be easily distinguished from other transactions in the network.
- The security and privacy of our protocol is proven in the Universal Composability framework. This ensures that the constructions show the behavior as described by the ideal functionality even in complex contexts where several instances of the construction are used concurrently.
Implications and Follow-ups
- We intend to improve the protocol by incorporating a dynamic split of payments, similar to the work in Eckey et al. This will reduce the computation overhead of the sender by eliminating the preprocessing step of constructing conditions for each off-chain contract. The main challenges are to realize such a protocol without violating unlinkability and to decide a bound on the fee charged in the worst case.
- We intend to explore whether a similar construction can be proposed where all the channel’s routing instances of partial payment are updated in constant time instead of having staggering lock times.
- We are looking for opportunities to deploy it as a protocol for multi-path payment in Lightning Networks, and observe the performance in real-time.
Applicability
- High-valued payments can be efficiently routed in the Lightning Network.
- Our protocol does not compromise on scalability as it does not use any expensive cryptographic primitives like homomorphic encryption or zero-knowledge proofs.
- The proposed constructions can be used to implement secure multi-path payments in payment channel networks for different cryptocurrencies that support either Schnorr or ECDSA signatures.
