Sharding distributed ledgers is the most promising on-chain solution for scaling blockchain technology. In this work, we define and analyze the properties a sharded distributed ledger should fulfill. More specifically, we show that a sharded blockcha
in cannot be scalable under a fully adaptive adversary, but it can scale up to $O(n/log n)$ under an epoch-adaptive adversary. This is possible only if the distributed ledger creates succinct proofs of the valid state updates at the end of each epoch. Our model builds upon and extends the Bitcoin backbone protocol by defining consistency and scalability. Consistency encompasses the need for atomic execution of cross-shard transactions to preserve safety, whereas scalability encapsulates the speedup a sharded system can gain in comparison to a non-sharded system. We introduce a protocol abstraction and highlight the sufficient components for secure and efficient sharding in our model. In order to show the power of our framework, we analyze the most prominent shared blockchains (Elastico, Monoxide, OmniLedger, RapidChain) and pinpoint where they fail to meet the desired properties.
Payment networks were introduced to address the limitation on the transaction throughput of popular blockchains. To open a payment channel one has to publish a transaction on-chain and pay the appropriate transaction fee. A transaction can be routed
in the network, as long as there is a path of channels with the necessary capital. The intermediate nodes on this path can ask for a fee to forward the transaction. Hence, opening channels, although costly, can benefit a party, both by reducing the cost of the party for sending a transaction and by collecting the fees from forwarding transactions of other parties. This trade-off spawns a network creation game between the channel parties. In this work, we introduce the first game theoretic model for analyzing the network creation game on blockchain payment channels. Further, we examine various network structures (path, star, complete bipartite graph and clique) and determine for each one of them the constraints (fee value) under which they constitute a Nash equilibrium, given a fixed fee policy. Last, we show that the star is a Nash equilibrium when each channel party can freely decide the channel fee. On the other hand, we prove the complete bipartite graph can never be a Nash equilibrium, given a free fee policy.
Payment channels allow transactions between participants of the blockchain to be executed securely off-chain, and thus provide a promising solution for the scalability problem of popular blockchains. We study the online network design problem for pay
ment channels, assuming a central coordinator. We focus on a single channel, where the coordinator desires to maximize the number of accepted transactions under given capital constraints. Despite the simplicity of the problem, we present a flurry of impossibility results, both for deterministic and randomized algorithms against adaptive as well as oblivious adversaries.
We prove Bitcoin is secure under temporary dishonest majority. We assume the adversary can corrupt a specific fraction of parties and also introduce crash failures, i.e., some honest participants are offline during the execution of the protocol. We d
emand a majority of honest online participants on expectation. We explore three different models and present the requirements for proving Bitcoins security in all of them: we first examine a synchronous model, then extend to a bounded delay model and last we consider a synchronous model that allows message losses.
Off-chain protocols (channels) are a promising solution to the scalability and privacy challenges of blockchain payments. Current proposals, however, require synchrony assumptions to preserve the safety of a channel, leaking to an adversary the exact
amount of time needed to control the network for a successful attack. In this paper, we introduce Brick, the first payment channel that remains secure under network asynchrony and concurrently provides correct incentives. The core idea is to incorporate the conflict resolution process within the channel by introducing a rational committee of external parties, called Wardens. Hence, if a party wants to close a channel unilaterally, it can only get the committees approval for the last valid state. Brick provides sub-second latency because it does not employ heavy-weight consensus. Instead, Brick uses consistent broadcast to announce updates and close the channel, a light-weight abstraction that is powerful enough to preserve safety and liveness to any rational parties. Furthermore, we consider permissioned blockchains, where the additional property of auditability might be desired for regulatory purposes. We introduce Brick+, an off-chain construction that provides auditability on top of Brick without conflicting with its privacy guarantees. We formally define the properties our payment channel construction should fulfill, and prove that both Brick and Brick+ satisfy them. We also design incentives for Brick such that honest and rational behavior aligns. Finally, we provide a reference implementation of the smart contracts in Solidity.
Micropayment channels are the most prominent solution to the limitation on transaction throughput in current blockchain systems. However, in practice channels are risky because participants have to be online constantly to avoid fraud, and inefficient
because participants have to open multiple channels and lock funds in them. To address the security issue, we propose a novel mechanism that involves watchtowers incentivized to watch the channels and reveal a fraud. Our protocol does not require participants to be online constantly watching the blockchain. The protocol is secure, incentive compatible and lightweight in communication. Furthermore, we present an adaptation of our protocol implementable on the Lightning protocol. Towards efficiency, we examine specific topological structures in the blockchain transaction graph and generalize the construction of channels to enable topologies better suited to specific real-world needs. In these cases, our construction reduces the required amount of signatures for a transaction and the total amount of locked funds in the system.
Clustering, a fundamental task in data science and machine learning, groups a set of objects in such a way that objects in the same cluster are closer to each other than to those in other clusters. In this paper, we consider a well-known structure, s
o-called $r$-nets, which rigorously captures the properties of clustering. We devise algorithms that improve the run-time of approximating $r$-nets in high-dimensional spaces with $ell_1$ and $ell_2$ metrics from $tilde{O}(dn^{2-Theta(sqrt{epsilon})})$ to $tilde{O}(dn + n^{2-alpha})$, where $alpha = Omega({epsilon^{1/3}}/{log(1/epsilon)})$. These algorithms are also used to improve a framework that provides approximate solutions to other high dimensional distance problems. Using this framework, several important related problems can also be solved efficiently, e.g., $(1+epsilon)$-approximate $k$th-nearest neighbor distance, $(4+epsilon)$-approximate Min-Max clustering, $(4+epsilon)$-approximate $k$-center clustering. In addition, we build an algorithm that $(1+epsilon)$-approximates greedy permutations in time $tilde{O}((dn + n^{2-alpha}) cdot log{Phi})$ where $Phi$ is the spread of the input. This algorithm is used to $(2+epsilon)$-approximate $k$-center with the same time complexity.
In this paper, we analyze the topology and the content found on the darknet, the set of websites accessible via Tor. We created a darknet spider and crawled the darknet starting from a bootstrap list by recursively following links. We explored the wh
ole connected component of more than 34,000 hidden services, of which we found 10,000 to be online. Contrary to folklore belief, the visible part of the darknet is surprisingly well-connected through hub websites such as wikis and forums. We performed a comprehensive categorization of the content using supervised machine learning. We observe that about half of the visible dark web content is related to apparently licit activities based on our classifier. A significant amount of content pertains to software repositories, blogs, and activism-related websites. Among unlawful hidden services, most pertain to fraudulent websites, services selling counterfeit goods, and drug markets.
Payment networks, also known as channels, are a most promising solution to the throughput problem of cryptocurrencies. In this paper we study the design of capital-efficient payment networks, offline as well as online variants. We want to know how to
compute an efficient payment network topology, how capital should be assigned to the individual edges, and how to decide which transactions to accept. Towards this end, we present a flurry of interesting results, basic but generally applicable insights on the one hand, and hardness results and approximation algorithms on the other hand.
Payment channels are the most prominent solution to the blockchain scalability problem. We introduce the problem of network design with fees for payment channels from the perspective of a Payment Service Provider (PSP). Given a set of transactions, w
e examine the optimal graph structure and fee assignment to maximize the PSPs profit. A customer prefers to route transactions through the PSPs network if the cheapest path from sender to receiver is financially interesting, i.e., if the path costs less than the blockchain fee. When the graph structure is a tree, and the PSP facilitates all transactions, the problem can be formulated as a linear program. For a path graph, we present a polynomial time algorithm to assign optimal fees. We also show that the star network, where the center is an additional node acting as an intermediary, is a near-optimal solution to the network design problem.
