Research Summary - Anonymous Multi-hop Locks for Blockchain Scalability and Interoperability

TLDR
Payment Channel Networks such as Bitcoin’s Lightning Network exhibit serious privacy and security issues. The authors demonstrate how an anonymous multi-hop lock (AMHL) can thwart existing issues and wormhole attacks, a new form of collaborative payment fee theft.

Citation

  • Malavolta, Giulio & Moreno Sanchez, Pedro & Schneidewind, Clara & Kate, Aniket & Maffei, Matteo. (2019). Anonymous Multi-hop Locks for Blockchain Scalability and Interoperability. NDSS 2019.

Link

Core Research Question

  • How can you design a Payment Channel Network that provides meaningful and provable security and privacy for different cryptocurrencies?

Background

  • (Two-party) Payment channels are jointly-controlled cryptocurrency deposits whose ownership is negotiated in a peer-to-peer protocol between two parties. Parties exchange blockchain transactions that make the last ownership distribution of the deposit enforceable on the blockchain in case of dispute. A change of ownership distribution in favor of one of the parties is considered an off-chain payment to this party.
  • Payment Channel Networks are networks of two-party payment channels that allow for off-chain payments between parties who do not share a direct payment channel, but are connected by a path of two-party payment channels. To perform such multi-hop payments, intermediate users forward off-chain payments from the sender to the receiver via their respective two-party payment channels. Intermediate users are incentivized to participate in such multi-hop payments with small payment fees.
  • The Lightning Network is a payment channel network implemented on top of Bitcoin. It secures multi-hop payments using Hash-time-lock contracts.
  • A Hash-time-lock contract (HTLC) is a Bitcoin Script that allows for redeeming the corresponding output if the preimage of some hash value Y=H(x) can be provided before time t. To perform a multi-hop payment in a payment channel network, users first perform conditional off-chain payments along the payment path by exchanging HTLC-transactions conditioned on some value y chosen by the sender. Once all these conditional off-chain payments are performed along the payment path, the sender releases the preimage x of Y to the receiver. This allows the receiver to complete the conditional off-chain payment with the last user on the path when releasing x to them. In this way the conditional payments along the path can be consecutively completed. The individual HTLC timeouts are set such that every intermediate user still has enough time to enforce the payment on the blockchain in case that their successor did so.

Summary

  • Bitcoin’s Lightning Network exhibits privacy and security issues.
  • It is possible for intermediate users to link concurrent payments in the network using the hash values of the HTLC contracts. There’s also a new security attack, called a wormhole attack which allows intermediate users on the payment path to steal fees from intermediate users by collaborating.
  • In multi-hop payments where the payer does not conduct an initial communication round with users along the payment path, wormhole attacks are inevitable.
  • The authors propose a new cryptographic primitive anonymous multi-hop lock (AMHL) that extends the essence of the mechanism for conditional payments (as previously implemented by the HTLC contracts) to temporarily lock the funds parties along the payment path in their respective payment channels. In this context, a conditional payment is abstracted as a lock with some lock condition, and the completion of a conditional payment corresponds to releasing using a key that satisfies the condition.
  • To overcome the wormhole attack, the primitive AMHL includes an initial setup phase in which the sender communicates with the users along the payment path.
  • AMHLs (that satisfy all the security and privacy notions) can be realized by different cryptographic constructions, one general construction based on homomorphic one-way functions (such as discrete logarithms) and two constructions based on signature schemes (the Schnorr and the ECDSA digital signature scheme).
  • The performance of the different constructions is evaluated in terms of computation time, communication overhead, computation cost, and memory consumption to show that the constructions are practical and improve over existing privacy-preserving solutions for multi-hop payments in payment channel networks.

Method

  • The paper makes use of several methods:
    • An attack description of the wormhole attack in which the authors detail out how two collaborating malicious users can steal the payment fees from honest users.
    • The logical proof of the inevitability of the described attack in a scenario with only two rounds of communication - a locking and and an unlocking phase.
      The authors show that in such a scenario the information that the individual users need for releasing a lock cannot depend on path-specific information and hence is always transferable between parties.
    • The formal characterization of a cryptographic primitive and of security and privacy notions for this primitive. The authors specify the AMHL as a collection of probabilistic polynomial time algorithms and define the security and privacy properties in terms of an ideal functionality that enforces these notions.
    • The formal presentation of cryptographic constructions and cryptographic proofs in the Universal Composability Framework to show that the previously defined primitive can be realized by the presented constructions. Simply put, the authors prove that the presented constructions show the same behavior as the ideal functionality even when being used as a building block of a larger system.
    • An empirical performance evaluation of the cryptographic constructions based on a prototype implementation. Using a Python implementation, the authors measure the time and memory consumption for the parties in an AMHL protocol as well as the communication overhead. They further evaluate the overall overhead in terms of communication and computation for multi-hop payments in a payment channel network based on AMHL compared to other solutions for multi-hop payments proposed in the literature.

Results

  • The wormhole attack on the Lightning Network. This attack enables collaborating intermediate users on the payment path to steal the fees from honest intermediate users on the path. In the attack a malicious party, when receiving the preimage x from their successor, directly forwards the preimage x to a collaborating party instead of continuing to complete the payments along the path. As a consequence all intermediate users between the collaborating parties are prevented from completing their conditional payments and hence from collecting their fees. Instead, the party that received the preimage x can resume the completion of the payment and collect all remaining fees.
  • The AMHL primitive and corresponding security and privacy notions for it are defined. The AMHL primitive describes algorithms for an initial setup phase, as well as for creating and releasing locks.
    The security and privacy notions that are defined are the following:
    • Atomicity: This notion ensures that no intermediate user can lose funds since it requires that every user can complete the conditional payment (“release the lock”) with their predecessor when their successor on the path released the lock with him.
    • Consistency: This notion rules out the wormhole attack since it requires that no user can release the lock with their predecessor if their successor on the path did not release the lock with them before.
    • Relationship Anonymity: This notion ensures the unlinkability of different concurrent payments by requiring that all conditional payments (locks) should be indistinguishable.
  • Different cryptographic constructions are formally defined and proven to satisfy the aforementioned security and privacy notions. These constructions are:
    • A general construction that realizes lock conditions using homomorphic one-way functions (e.g., discrete logarithm). This construction can be used to realize AMHLs in cryptocurrencies whose scripting languages support such functions, such as Ethereum.
    • A construction that embeds lock conditions into Schnorr signatures.This construction had already been discussed in the community.
      *A novel construction that embeds lock conditions into ECDSA signatures. This allows for realizing AMHLs in Bitcoin (since ECDSA is the signature scheme used for transaction signing in Bitcoin)

Discussion & Key Takeaways

  • The wormhole attack on the Lightning network is particularly severe since it eliminates the incentive for intermediate users to participate in multi-hop payments since they could always potentially lose their payment fee to an attacker. Without a payment fee there is no reason for a user to participate as an intermediary in a payment since this causes collateral costs for the intermediate user who needs to lock a certain amount of funds for some time during the payment. Further, an honest intermediate user cannot distinguish the situations where a payment failed for legitimate reasons (e.g. the receiver went offline) and the scenario where the attack is performed (and the attacker collected the fees meant for the honest user instead). For this reason attackers cannot be held accountable.
  • The proposed constructions that embed the lock conditions into signatures (here Schnorr and ECDSA signatures) constitute so called scriptless scripts:
    This is as a functionality similar to the one implemented in an HTLC contract using a (Bitcoin) script is achieved by constructing an uncompleted signature which can only be completed when satisfying a pre-specified condition.
    Such scriptless scripts have the advantage that when transactions containing such scripts are published on the blockchain that they are indistinguishable from simple payment transactions. This does not only save blockchain space, but also improves the fungibility of the currency since such payments stemming from payment channel networks cannot be easily distinguished from other transactions in the network.
  • Since the security and privacy of the different constructions is proven in the Universal Composability framework, these constructions can be used to securely build bigger applications (in particular payment channel networks) from them. The universal composability proof 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 & Follow-ups

  • The presented impossibility result shows that in the case where the payment path is determined by dynamic there is no way of avoiding the wormhole attack. Consequently, for secure multi-hop payments the payment path needs to be fixed upfront and hence the sender needs to have a reliable knowledge of the network topology and the capacities of the individual channels in the network in order to select a payment path which is likely to lead to a successful payment. It would be interesting to explore whether there are still meaningful (weaker) security and privacy notions that can be achieved in the setting of dynamic routing.
  • It could be interesting to study other privacy notions than relationship anonymity.
  • The presented constructions do not allow to implement secure payment channel networks for all known cryptocurrencies, in particular not for Monero. It would be interesting to develop a (provably secure) instantiation of the AMHL primitive that is compatible with Monero.

Applicability

  • The proposed constructions can be used to implement secure multi-hop payments in payment channel networks for different cryptocurrencies that support either Schnorr or ECDSA signatures or that come with a scripting language that supports some homomorphic one-way function.
  • The proposed ECDSA-based construction has already been implemented and tested in the Lightning Network [28, 29].
  • The presented constructions can also be used to implement cross-currency atomic swaps and cross-currency payment channel networks that allow for off-chain payments between the users of different cryptocurrencies.

[28] C. Fromknecht, “Instantiating scriptless 2p-ecdsa: fungi- ble 2-of-2 multisigs for bitcoin today,” Talk at Scaling- Bitcoin 2018, https://tokyo2018.scalingbitcoin.org/transcript/ tokyo2018/scriptless- ecdsa.

[29] “tpec: 2p-ecdsa signatures,” Github repository, https:// github.com/cfromknecht/tpec.

5 Likes