The Lightning Network provides almost-instant payments to its parties. In addition to direct payments requiring a shared payment channel, parties can pay each other in the form of multi-hop payments via existing channels. Such multi-hop payments rely on a 2-phase commit protocol to achieve balance security; that is, no honest intermediary party loses her coins. Unfortunately, failures or attacks in this 2-phase commit protocol can lead to coins being committed (locked) in a payment for extended periods of time (in the order of days in the worst case). During these periods, parties cannot go offline without losing funds due to their existing commitments, even if they use watchtowers. Furthermore, they cannot use the locked funds for initiating or forwarding new payments, reducing their opportunities to use their coins and earn fees. We introduce Bailout, the first protocol that allows intermediary parties in a multi-hop payment to unlock their coins before the payment completes by re-routing the payment over an alternative path. We achieve this by creating a circular payment route starting from the intermediary party in the opposite direction of the original payment. Once the circular payment is locked, both payments are canceled for the intermediary party, which frees the coins of the corresponding channels. This way, we create an alternative route for the ongoing multi-hop payment without involving the sender or receiver. The parties on the alternative path are incentivized to participate through fees. We evaluate the utility of our protocol using a real-world Lightning Network snapshot. Bailouts may fail due to insufficient balance in alternative paths used for re-routing. We find that attempts of a node to bailout typically succeed with a probability of more than 94% if at least one alternative path exists.

Payment channel networks (PCNs) are a promising solution to the blockchain scalability problem. In PCNs, a sender can route a multi-hop payment to a receiver via intermediaries. Yet, Lightning, the only prominent payment channel network, has two major issues when it comes to multi-hop payments. First, the sender decides on the path without being able to take local capacity restrictions into account. Second, due to the atomicity of payments, any failure in the path causes a failure of the complete payment. In this work, we propose Forward-Update-Finalize (FUFi): The sender adds redundancy to a locally routed payment by initially committing to sending a higher amount than the actual payment value. Intermediaries decide on how to forward a received payment, potentially splitting it between multiple paths. If they cannot forward the total payment value, they may reduce the amount they forward. If paths for sufficient funds are found, the receiver and sender jointly select the paths and amounts that will actually be paid. Payment commitments are updated accordingly and fulfilled. In order to guarantee atomicity and correctness of the payment value, we use a modified Hashed Time Lock Contract (HTLC) for paying that requires both the sender and the receiver to provide a secret preimage. FUFi furthermore is the first local routing protocol to include fees and specify a fee policy to intermediaries on how to determine their fair share of fees. We prove that the proposed protocol achieves all key security properties of multi-hop payments. Furthermore, our evaluation on both synthetic and real-world Lightning topologies shows FUFi outperforms existing algorithms in terms of fraction of successful payments by about 10%.

Vertical Federated Learning (VFL) enables multiple clients to collaboratively train a global model over vertically partitioned data without leaking private local information. Tree-based models, like XGBoost and LightGBM, have been widely used in VFL to enhance the interpretation and efficiency of training. However, there is a fundamental lack of research on how to conduct VFL securely over distributed labels. This work is the first to fill this gap by designing a novel protocol, called FEVERLESS, based on XGBoost. FEVERLESS leverages secure aggregation via information masking technique and global differential privacy provided by a fairly and randomly selected noise leader to prevent private information from being leaked in the training process. Furthermore, it provides label and data privacy against honest-but-curious adversaries even in the case of collusion of <inline-formula><tex-math notation="LaTeX">$n - 2$</tex-math></inline-formula> out of n clients. We present a comprehensive security and efficiency analysis for our design, and the empirical results from our experiments demonstrate that FEVERLESS is fast and secure. In particular, it outperforms the solution based on additive homomorphic encryption in runtime cost and provides better accuracy than the local differential privacy approach.

In this work, we study the blockchain leader election problem. The purpose of such protocols is to elect a leader who decides on the next block to be appended to the blockchain, for each block proposal round. Solutions to this problem are vital for the security of blockchain systems. We introduce an efficient blockchain leader election method with security based solely on standard assumptions for cryptographic hash functions (rather than public-key cryptographic assumptions) and that does not involve a racing condition as in Proof-of-Work based approaches. Thanks to the former feature, our solution provides the highest confidence in security, even in the post-quantum era. A particularly scalable application of our solution is in the Proof-of-Stake setting, and we investigate our solution in the Algorand blockchain system. We believe our leader election approach can be easily adapted to a range of other blockchain settings. At the core of Algorand's leader election is a verifiable random function (VRF). Our approach is based on introducing a simpler primitive which still suffices for the blockchain leader election problem. In particular, we analyze the concrete requirements in an Algorand-like blockchain setting to accomplish leader election, which leads to the introduction of indexed VRF (iVRF). An iVRF satisfies modified uniqueness and pseudorandomness properties (versus a full-fledged VRF) that enable an efficient instantiation based on a hash function without requiring any complicated zero-knowledge proofs of correct PRF evaluation. We further extend iVRF to an authenticated iVRF with forward-security, which meets all the requirements to establish an Algorand-like consensus. Our solution is simple, flexible and incurs only a 32-byte additional overhead when combined with the current best solution to constructing a forward-secure signature (in the post-quantum setting). We implemented our (authenticated) iVRF proposal in C language on a standard computer and show that it significantly outperforms other quantum-safe VRF proposals in almost all metrics. Particularly, iVRF evaluation and verification can be executed in 0.02 ms, which is even faster than ECVRF used in Algorand.

Payment channel networks (PCNs) enhance the scalability of block-chains by allowing parties to conduct transactions off-chain, i.e, without broadcasting every transaction to all blockchain participants. To conduct transactions, a sender and a receiver can either establish a direct payment channel with a funding blockchain transaction or leverage existing channels in a multi-hop payment. The security of PCNs usually relies on the synchrony of the underlying blockchain, i.e., evidence of misbehavior needs to be published on the blockchain within a time limit. Alternative payment channel proposals that do not require blockchain synchrony rely on quorum certificates and use a committee to register the transactions of a channel. However, these proposals do not support multi-hop payments, a limitation we aim to overcome.

In this paper, we demonstrate that it is in fact impossible to design a multi-hop payment protocol with both network asynchrony and faulty channels, i.e., channels that may not correctly follow the protocol. We then detail two committee-based multi-hop payment protocols that respectively assume synchronous communications and possibly faulty channels, or asynchronous communication and correct channels. The first protocol relies on possibly faulty committees instead of the blockchain to resolve channel disputes, and enforces privacy properties within a synchronous network. The second one relies on committees that contain at most f faulty members out of 3f +1 and successively delegate to each other the role of eventually completing a multi-hop payment. We show that both protocols satisfy the security requirements of a multi-hop payment and compare their communication complexity and latency.

Decentralized and permissionless ledgers offer an inherently low transaction rate, as a result of their consensus protocol demanding the storage of each transaction on-chain. A prominent proposal to tackle this scalability issue is to utilize off-chain protocols, where parties only need to post a limited number of transactions on-chain. Existing solutions can roughly be categorized into: (i) application-specific channels (e.g., payment channels), offering strictly weaker functionality than the underlying blockchain; and (ii) state channels, supporting arbitrary smart contracts at the cost of being compatible only with the few blockchains having Turing-complete scripting languages (e.g., Ethereum). In this work, we introduce and formalize the notion of generalized channels allowing users to perform any operation supported by the underlying blockchain in an off-chain manner. Generalized channels thus extend the functionality of payment channels and relax the definition of state channels. We present a concrete construction compatible with any blockchain supporting transaction authorization, time-locks and constant number of Boolean ∧ and ∨ operations – requirements fulfilled by many (non-Turing-complete) blockchains including the popular Bitcoin. To this end, we leverage adaptor signatures – a cryptographic primitive already used in the cryptocurrency literature but formalized as a standalone primitive in this work for the first time. We formally prove the security of our generalized channel construction in the Universal Composability framework. As an important practical contribution, our generalized channel construction outperforms the state-of-the-art payment channel construction, the Lightning Network, in efficiency. Concretely, it halves the off-chain communication complexity and reduces the on-chain footprint in case of disputes from linear to constant in the number of off-chain applications funded by the channel. Finally, we evaluate the practicality of our construction via a prototype implementation and discuss various applications including financially secured fair two-party computation.

Current permissionless cryptocurrencies such as Bitcoin suffer from a limited transaction rate and slow confirmation time, which hinders further adoption. Payment channels are one of the most promising solutions to address these problems, as they allow the parties of the channel to perform arbitrarily many payments in a peer-to-peer fashion while uploading only two transactions on the blockchain. This concept has been generalized into payment channel networks where a path of payment channels is used to settle the payment between two users that might not share a direct channel between them. However, this approach requires the active involvement of each user in the path, making the system less reliable (they might be offline), more expensive (they charge fees per payment), and slower (intermediaries need to be actively involved in the payment). To mitigate this issue, recent work has introduced the concept of virtual channels (IEEE SP'19), which involve intermediaries only in the initial creation of a bridge between payer and payee, who can later on independently perform arbitrarily many off-chain transactions. Unfortunately, existing constructions are only available for Ethereum, as they rely on its account model and Turing-complete scripting language. The realization of virtual channels in other blockchain technologies with limited scripting capabilities, like Bitcoin, was so far considered an open challenge.In this work, we present the first virtual channel protocols that are built on the UTXO-model and require a scripting language supporting only a digital signature scheme and a timelock functionality, being thus backward compatible with virtually every cryptocurrency, including Bitcoin. We formalize the security properties of virtual channels as an ideal functionality in the Universal Composability framework and prove that our protocol constitutes a secure realization thereof. We have prototyped and evaluated our protocol on the Bitcoin blockchain, demonstrating its efficiency: for n sequential payments, they require an off-chain exchange of 9+2n transactions or a total of 3524+695n bytes, with no on-chain footprint in the optimistic case. This is a substantial improvement compared to routing payments in a payment channel network, which requires 8n transactions with a total of 3026n bytes to be exchanged.

Adaptor signatures, also known as scriptless scripts, have recently become an important tool in addressing the scalability and interoperability issues of blockchain applications such as cryptocurrencies. An adaptor signature extends a digital signature in a way that a complete signature reveals a secret based on a cryptographic condition. It brings about various advantages such as (i) low on-chain cost, (ii) improved fungibility of transactions, and (iii) advanced functionality beyond the limitation of the blockchain’s scripting language. In this work, we introduce the first post-quantum adaptor signature, named $${\mathsf {LAS}}$$. Our construction relies on the standard lattice assumptions, namely Module-SIS and Module-LWE. There are certain challenges specific to the lattice setting, arising mainly from the so-called knowledge gap in lattice-based proof systems, that makes the realization of an adaptor signature and its applications difficult. We show how to overcome these technical difficulties without introducing additional on-chain costs. Our evaluation demonstrates that $${\mathsf {LAS}}$$ is essentially as efficient as an ordinary lattice-based signature in terms of both communication and computation. We further show how to achieve post-quantum atomic swaps and payment channel networks using $${\mathsf {LAS}}$$.

Payment channel networks like Bitcoin’s Lightning network are an auspicious approach for realizing high transaction throughput and almost-instant confirmations in blockchain networks. However, the ability to successfully conduct payments in such networks relies on the willingness of participants to lock collateral in the network. In Lightning, the key financial incentive to lock collateral are low fees for routing payments of other participants. While users can choose these fees, real-world data indicates that they mainly stick to default fees. By providing insights on beneficial choices for fees, we aim to incentivize users to lock more collateral and improve the effectiveness of the network. In this paper, we consider a node that given the network topology and the channel details establishes channels and chooses fees to maximize its financial gain. Our contributions are i) formalization of the optimization problem, ii) proving that the problem is NP-hard, and iii) designing and evaluating a greedy algorithm to approximate the optimal solution. In each step, our greedy algorithm establishes a channel that maximizes the increase to ’s total reward, which corresponds to maximizing the number of shortest paths passing through. Our simulation study leveraged real-world data sets to quantify the impact of our gain optimization and indicates that our strategy is at least a factor two better than other strategies.

In a blockchain network, transaction advertisement is the announcement of the new transactions to the participants (miners) who are responsible to validate them. Existing blockchain protocols lack an incentive-compatible advertisement process where a rational participant would gain from advertising a transaction. The deficiency can be solved by a Sybil-proof rewarding function which divides the transaction fee among the round leader and the nodes who advertise it. Up to now, there have been three rewarding function proposals, all of which require special constraints on the blockchain network model, e.g., tree-structured connections. In this work, we formulate the rewarding function and obtain the necessary conditions for Sybil-proofness and incentive-compatibility properties. To the best of our knowledge, we present the first rewarding function which is suitable for any blockchain network model. We introduce path length dependent rewarding for the nodes involved in the advertisement process, which helps us to overcome the impossibility results given in the previous works. Our rewarding function divides the transaction fee among the nodes who advertise it, the current round leader and the next round leader. In addition to these achievements, unlike previous proposals, our rewarding function provides resistance against the forking attacks where an adversary rejects a valid block and creates a fork to gain the transaction fees in the original block.

Traceability is an increasingly important aspect of the supply chain with several highlights throughout the last few decades. Parties, such as consumers and government agencies, have shown an increase in demand for information regarding their products and materials. Although there exist numerous frameworks for traceability solutions, these frameworks fail to address the concerns with regards to privacy-sensitive information, certificate verifiability, and auditability. Our contribution is in two-fold: a traceability system decouples and the product-auditable pasta protocol. decouples is the first decentralized, unlinkable and privacy-preserving traceability system for the supply chain, to the best of our knowledge. The system incorporates cryptographic techniques to address the aforementioned concerns. Our second contribution is the pasta protocol, which allows unique tracking keys per product, per actor. The protocol also anonymizes the receiver of a transaction. Our complexity analysis and proof-of-concept implementation results show that decouples is a feasible traceability system for the supply chain.

Blockchain technology allows running ordered transactions within an immutable public ledger in a decentralized manner. It consists of two processes: Advertisement where the participants become aware of the new transactions and chain extension where the validated transactions are added into a block by extending the chain. Existing blockchain protocols have mainly focused on the chain extension, though the advertisement process has not been dealt with in depth. More specifically, transaction advertisement is fulfilled in an altruistic manner and the same gossip-like propagation mechanism is used for both transactions and blocks. Consequently, the existing protocols are not only incompatible within a rational setting where participants try to maximize their benefit but also suffering from inefficient bandwidth usage. In this work, we propose Tulip, a two-layered blockchain framework, which enriches any blockchain protocol with respect to the aforementioned advertisement issues. Tulip treats the advertisement and chain extension processes separately. Transactions are collected and verified by a transaction collector, whereas extending the chain with a new block is done by a round leader. In order to achieve a generic framework, we model the basic functionalities of a ledger. These functionalities are realized by any existing blockchain protocol and responsible for the chain extension process. Thanks to the modular structure of Tulip, the chain extension process can be combined with an incentive compatible and bandwidth-efficient advertisement process. Tulip can be built upon any blockchain protocol while preserving the ledger properties persistence and liveness. Moreover, it enhances the liveness into strong liveness property which requires only one honest participant, rather than all, to advertise a transaction. In this manner, to the best of our knowledge, Tulip forms the first blockchain protocol having incentive compatible chain extension and transaction advertisement processes. Finally, we show that Tulip can be used to reduce redundant bandwidth usage by up to 99%.

Smart contracts are applications that are deployed and executed on a blockchain's decentralised infrastructure. Many smart contract applications rely on data that resides outside the blockchain. However, while traditional web applications can communicate with trustworthy data sources directly through the Internet, this is not possible for smart contracts because their execution must be deterministic. Bringing external data into the blockchain has been a topic of research since the first introduction of Ethereum. A system that can provide this data to smart contracts is called an oracle. The primary requirement in designing oracles is that the authenticity of the data must be publicly verifiable, which can be achieved through signatures. However, transmitting data to the blockchain and performing the verification is costly, especially if applications require data from multiple sources. In that case, current approaches would need to retrieve the data from each source separately. In this paper, we present the concept of MUlti-Source oraCLE (MUSCLE) for retrieving data from multiple sources, which we believe to be the first to focus on the multi-source scenario. We implement five variants of MUSCLE, each using a different signature or aggregate signature scheme and compare their performance with two oracles that are based on TLS-N, which represents the current state of the art. Our results show that the ECDSA-based MUSCLE features the lowest total gas expenditure, while the BGLS-based oracle provides lower transaction and storage costs.