Distributed Ledger Technologies (DLT) and Decentralized File Storages (DFS) are becoming increasingly used to create common, decentralized and trustless infrastructures where participants interact and collaborate in Peer-to-Peer interactions. A prominent use case is represented by decentralized data marketplaces, where users are consumers and providers at the same time, and trustless interactions are required. However, data in DLTs and DFS are usually unstructured and there are no efficient mechanisms to query a certain type of data for the search in the market. In this paper, we propose the use of a Distributed Hash Table (DHT) as a layer on top of DLTs where, once the data are acquired and stored in the ledger, these can be searched through multiple keyword based queries, thanks to the lookup functionalities offered by the DHT. The DHT network is a hypercube overlay structure, organized for an efficient processing of multiple keyword-based queries. We provide the architecture of such solution for a decentralized data marketplace and an analysis based on a simulation that proves the viability of the proposed approach.
Matthew Tsao, Kaidi Yang, Stephen Zoepf, Marco Pavone
The era of big data has brought with it a richer understanding of user behavior through massive datasets, which can help organizations optimize the quality of their services. In the context of transportation research, mobility data can provide municipal authorities (MAs) with insights on how to operate, regulate, or improve the transportation network. Mobility data, however, may contain sensitive information about end users and trade secrets of mobility providers (MPs). Due to this data privacy concern, MPs may be reluctant to contribute their datasets to MA. Using ideas from cryptography, we propose an interactive protocol between an MA and an MP, in which MA obtains insights from mobility data without MP having to reveal its trade secrets or sensitive data of its users. This is accomplished in two steps: 1) a commitment step and 2) a computation step. In the first step, Merkle commitments and aggregated traffic measurements are used to generate a cryptographic commitment. In the second step, MP extracts insights from the data and sends them to MA. Using the commitment and zero-knowledge proofs, MA can certify that the information received from MP is accurate, without needing to directly inspect the mobility data. We also present a differentially private version of the protocol that is suitable for the large query regime. The protocol is verifiable for both MA and MP in the sense that dishonesty from one party can be detected by the other. The protocol can be readily extended to the more general setting with multiple MPs via secure multiparty computation.
Payment channel networks (PCNs) have emerged as a scalability solution for blockchains built on the concept of a payment channel: a setting that allows two nodes to safely transact between themselves in high frequencies based on pre-committed peer-to-peer balances. Transaction requests in these networks may be declined because of unavailability of funds due to temporary uneven distribution of the channel balances. In this paper, we investigate how to alleviate unnecessary payment blockage via proper prioritization of the transaction execution order. Specifically, we consider the scheduling problem in PCNs: as transactions continuously arrive on both sides of a channel, nodes need to decide which ones to process and when in order to maximize their objective, which in our case is the channel throughput. We introduce a stochastic model to capture the dynamics of a payment channel under random arrivals, and propose that channels can hold incoming transactions in buffers up to some deadline in order to enable more elaborate processing decisions. We describe a policy that maximizes the channel success rate/throughput for uniform transaction requests of fixed amounts, both in the presence and absence of buffering capabilities, and formally prove its optimality. We also develop a discrete event simulator of a payment channel, and evaluate different heuristic scheduling policies in the more general heterogeneous amounts case, with the results showing superiority of the heuristic extension of our policy in this case as well. Our work opens the way for more formal research on improving PCN performance via joint consideration of routing and scheduling decisions.
Credit networks rely on decentralized, pairwise trust relationships (channels) to exchange money or goods. Credit networks arise naturally in many financial systems, including the recent construct of payment channel networks in blockchain systems. An important performance metric for these networks is their transaction throughput. However, predicting the throughput of a credit network is nontrivial. Unlike traditional communication channels, credit channels can become imbalanced; they are unable to support more transactions in a given direction once the credit limit has been reached. This potential for imbalance creates a complex dependency between a network's throughput and its topology, path choices, and the credit balances (state) on every channel. Even worse, certain combinations of these factors can lead the credit network to deadlocked states where no transactions can make progress. In this paper, we study the relationship between the throughput of a credit network and its topology and credit state. We show that the presence of deadlocks completely characterizes a network's throughput sensitivity to different credit states. Although we show that identifying deadlocks in an arbitrary topology is NP-hard, we propose a peeling algorithm inspired by decoding algorithms for erasure codes that upper bounds the severity of the deadlock. We use the peeling algorithm as a tool to compare the performance of different topologies as well as to aid in the synthesis of topologies robust to deadlocks.
Dániel Kondor, Nikola Bulatovic, József Stéger, István Csabai · 5 authors
Bitcoin and Ethereum transactions present some of the largest real-world complex networks that are publicly available for study, including a detailed picture of their time evolution. As such, they have received a considerable amount of attention from the network science community along with analyses from economic and cryptographic perspectives. Among these studies, in an analysis on the early instance of the Bitcoin network, we have shown the clear presence of the preferential attachment, or the “rich-get-richer” phenomenon. Now, we revisit this question, using a recent version of the Bitcoin network that has grown almost 100-fold since our original analysis. Furthermore, we additionally carry out a comparison with Ethereum, the second most important cryptocurrency. Our results show that preferential attachment continues to be a key factor in the evolution of both the Bitcoin and Ethereum transactoin networks. To facilitate further analysis, we publish a recent version of both transaction networks, and an efficient software implementation that is able to evaluate linking statistics necessary for learn about preferential attachment on networks with several hundred million edges.
Catarina Oliveira, João Torres, Maria Inês Silva, David Aparício · 6 authors
Money laundering is a global phenomenon with wide-reaching social and economic consequences. Cryptocurrencies are particularly susceptible due to the lack of control by authorities and their anonymity. Thus, it is important to develop new techniques to detect and prevent illicit cryptocurrency transactions. In our work, we propose new features based on the structure of the graph and past labels to boost the performance of machine learning methods to detect money laundering. Our method, GuiltyWalker, performs random walks on the bitcoin transaction graph and computes features based on the distance to illicit transactions. We combine these new features with features proposed by Weber et al. and observe an improvement of about 5pp regarding illicit classification. Namely, we observe that our proposed features are particularly helpful during a black market shutdown, where the algorithm by Weber et al. was low performing.
Alex Auvolat, Yérom-David Bromberg, Davide Frey, François Taı̈ani
Recent works have proposed new Byzantine consensus algorithms for blockchains based on epidemics, a design which enables highly scalable performance at a low cost. These methods however critically depend on a secure random peer sampling service: a service that provides a stream of random network nodes where no attacking entity can become over-represented. To ensure this security property, current epidemic platforms use a Proof-of-Stake system to select peer samples. However such a system limits the openness of the system as only nodes with significant stake can participate in the consensus, leading to an oligopoly situation. Moreover, this design introduces a complex interdependency between the consensus algorithm and the cryptocurrency built upon it. In this paper, we propose a radically different security design for the peer sampling service, based on the distribution of IP addresses to prevent Sybil attacks. We propose a new algorithm, $\scriptstyle{BASALT}$, that implements our design using a stubborn chaotic search to counter attackers' attempts at becoming over-represented. We show in theory and using Monte Carlo simulations that $\scriptstyle{BASALT}$ provides samples which are extremely close to the optimal distribution even in adversarial scenarios such as tentative Eclipse attacks. Live experiments on a production cryptocurrency platform confirm that the samples obtained using $\scriptstyle{BASALT}$ are equitably distributed amongst nodes, allowing for a system which is both open and where no single entity can gain excessive power.
Modern mathematics is built on the idea that proofs should be translatable into formal proofs, whose validity is an objective question, decidable by a computer. Yet, in practice, proofs are informal and may omit many details. An agent considers a proof valid if they trust that it could be expanded into a machine-verifiable proof. A proof's validity can thus become a subjective matter and lead to a debate, which may be difficult to settle. Hence, while the concept of valid proof is well-defined, the process to establish validity is itself a complex multi-agent problem. We introduce the SPRIG protocol. SPRIG allows agents to propose and verify succinct and informative proofs in a decentralized fashion; the trust is established by agents being able to request more details in the proof steps; debates, if they arise, must isolate details of proofs and, if they persist, go down to machine-level details, where they are automatically settled. A structure of bounties and stakes is set to incentivize agents to act in good faith. We propose a game-theoretic discussion of SPRIG, showing how agents with various types of information interact, leading to a proof tree with an appropriate level of detail and to the invalidation of wrong proofs, and we discuss resilience against various attacks. We then analyze a simplified model, characterize its equilibria and compute the agents' level of trust. SPRIG is designed to run as a smart contract on a blockchain platform. This allows anonymous agents to participate in the verification debate, and to contribute with their information. The smart contract mediates the interactions, settles debates, and guarantees that bounties and stakes are paid as specified. SPRIG enables new applications, such as the issuance of bounties for open problems, and the creation of derivatives markets, allowing agents to inject more information pertaining to proofs.
Advancements in distributed ledger technologies are driving the rise of blockchain-based social media platforms such as Steemit, where users interact with each other in similar ways as conventional social networks. These platforms are autonomously managed by users using decentralized consensus protocols in a cryptocurrency ecosystem. The deep integration of social networks and blockchains in these platforms provides potential for numerous cross-domain research studies that are of interest to both the research communities. However, it is challenging to process and analyze large volumes of raw Steemit data as it requires specialized skills in both software engineering and blockchain systems and involves substantial efforts in extracting and filtering various types of operations. To tackle this challenge, we collect over 38 million blocks generated in Steemit during a 45 month time period from 2016/03 to 2019/11 and extract ten key types of operations performed by the users. The results generate SteemOps, a new dataset that organizes more than 900 million operations from Steemit into three sub-datasets namely (i) social-network operation dataset (SOD), (ii) witness-election operation dataset (WOD) and (iii) value-transfer operation dataset (VOD). We describe the dataset schema and its usage in detail and outline possible future research studies using SteemOps. SteemOps is designed to facilitate future research aimed at providing deeper insights on emerging blockchain-based social media platforms.
In this work, we consider community detection in blockchain networks. We specifically take the Bitcoin network and Ethereum network as two examples, where community detection serves in different ways. For the Bitcoin network, we modify the traditional community detection method and apply it to the transaction social network to cluster users with similar characteristics. For the Ethereum network, on the other hand, we define a bipartite social graph based on the smart contract transactions. A novel community detection algorithm which is designed for low-rank signals on graph can help find users' communities based on user-token subscription. Based on these results, two strategies are devised to deliver on-chain advertisements to those users in the same community. We implement the proposed algorithms on real data. By adopting the modified clustering algorithm, the community results in the Bitcoin network is basically consistent with the ground-truth of betting site community which has been announced to the public. At the meanwhile, we run the proposed strategy on real Ethereum data, visualize the results and implement an advertisement delivery on the Ropsten test net.
Konstantinos Stylianou, Leonhard Spiegelberg, Maurice Herlihy, Nic Carter
When network products and services become more valuable as their userbase grows (network effects), this tendency can become a major determinant of how they compete with each other in the market and how the market is structured. Network effects are traditionally linked to high market concentration, early-mover advantages, and entry barriers, and in the cryptoasset market they have been used as a valuation tool too. The recent resurgence of Bitcoin has been partly attributed to network effects too. We study the existence of network effects in six cryptoassets from their inception to obtain a high-level overview of the application of network effects in the cryptoasset market. We show that contrary to the usual implications of network effects, they do not serve to concentrate the cryptoasset market, nor do they accord any one cryptoasset a definitive competitive advantage, nor are they consistent enough to be reliable valuation tools. Therefore, while network effects do occur in cryptoasset networks, they are not a defining feature of the cryptoasset market as a whole.
The anonymity of blockchain has accelerated the growth of illegal activities and criminal behaviors on cryptocurrency platforms. Although decentralization is one of the typical characteristics of blockchain, we urgently call for effective regulation to detect these illegal behaviors to ensure the safety and stability of user transactions. Identity inference, which aims to make a preliminary inference about account identity, plays a significant role in blockchain security. As a common tool, graph mining technique can effectively represent the interactive information between accounts and be used for identity inference. However, existing methods cannot balance scalability and end-to-end architecture, resulting high computational consumption and weak feature representation. In this paper, we present a novel approach to analyze user's behavior from the perspective of the transaction subgraph, which naturally transforms the identity inference task into a graph classification pattern and effectively avoids computation in large-scale graph. Furthermore, we propose a generic end-to-end graph neural network model, named $\text{I}^2 \text{BGNN}$, which can accept subgraph as input and learn a function mapping the transaction subgraph pattern to account identity, achieving de-anonymization. Extensive experiments on EOSG and ETHG datasets demonstrate that the proposed method achieve the state-of-the-art performance in identity inference.
As one of the most important and famous applications of blockchain technology, cryptocurrency has attracted extensive attention recently. Empowered by blockchain technology, all the transaction records of cryptocurrencies are irreversible and recorded in the blocks. These transaction records containing rich information and complete traces of financial activities are publicly accessible, thus providing researchers with unprecedented opportunities for data mining and knowledge discovery in this area. Networks are a general language for describing interacting systems in the real world, and a considerable part of existing work on cryptocurrency transactions is studied from a network perspective. This survey aims to analyze and summarize the existing literature on analyzing and understanding cryptocurrency transactions from a network perspective. Aiming to provide a systematic guideline for researchers and engineers, we present the background information of cryptocurrency transaction network analysis and review existing research in terms of three aspects, i.e., network modeling, network profiling, and network-based detection. For each aspect, we introduce the research issues, summarize the methods, and discuss the results and findings given in the literature. Furthermore, we present the main challenges and several future directions in this area.
Digital identity seems like a prerequisite for digital democracy: how can we ensure "one person, one vote" online without identifying voters? But digital identity solutions - ID checking, biometrics, self-sovereign identity, and trust networks - all present flaws, leaving users vulnerable to exclusion, identity loss or theft, and coercion. These flaws may be insurmountable because digital identity is a cart pulling the horse. We cannot achieve digital identity secure enough for the weight of digital democracy, until we build it on a solid foundation of "digital personhood." While identity is about distinguishing one person from another through attributes or affiliations, personhood is about giving all real people inalienable digital participation rights independent of identity, including protection against erosion of their democratic rights through identity loss, theft, coercion, or fakery. We explore and analyze alternative approaches to "proof of personhood" that may provide this missing foundation. Pseudonym parties marry the transparency of periodic physical-world events with the power of digital tokens between events. These tokens represent limited-term but renewable claims usable for purposes such as online voting or liquid democracy, sampled juries or deliberative polls, abuse-resistant social communication, or minting universal basic income in a permissionless cryptocurrency. Enhancing pseudonym parties to provide participants a moment of enforced physical security and privacy can address coercion and vote-buying risks that plague today's E-voting systems. We also examine other proposed approaches to proof of personhood, some of which offer conveniences such as all-online participation. These alternatives currently fall short of satisfying all the key digital personhood goals, unfortunately, but offer valuable insights into the challenges we face.
Anton Hasselgren, Paul Kengfai Wan, Margareth Horn, Katina Kralevska · 5 authors
The transparent and decentralized characteristics associated with blockchain can be both appealing and problematic when applied to a healthcare use-case. As health data is highly sensitive, it is therefore, highly regulated to ensure the privacy of patients. At the same time, access to health data and interoperability are in high demand. Regulatory frameworks such as GDPR and HIPAA are, amongst other objectives, meant to contribute to mitigating the risk of privacy violations of health data. Blockchain features can likely improve interoperability and access control to health data, and at the same time, preserve or even increase, the privacy of patients. Blockchain applications should address compliance with the current regulatory framework to increase real-world feasibility. This exploratory work indicates that published proof-of-concepts in the healthcare domain comply with GDPR, to an extent. Blockchain developers need to make design choices to be compliant with GDPR since currently, none available blockchain platform can show compliance out of the box.
Ultra-dense edge computing (UDEC) has great potential, especially in the 5G era, but it still faces challenges in its current solutions, such as the lack of: i) efficient utilization of multiple 5G resources (e.g., computation, communication, storage and service resources); ii) low overhead offloading decision making and resource allocation strategies; and iii) privacy and security protection schemes. Thus, we first propose an intelligent ultra-dense edge computing (I-UDEC) framework, which integrates blockchain and Artificial Intelligence (AI) into 5G ultra-dense edge computing networks. First, we show the architecture of the framework. Then, in order to achieve real-time and low overhead computation offloading decisions and resource allocation strategies, we design a novel two-timescale deep reinforcement learning (\textit{2Ts-DRL}) approach, consisting of a fast-timescale and a slow-timescale learning process, respectively. The primary objective is to minimize the total offloading delay and network resource usage by jointly optimizing computation offloading, resource allocation and service caching placement. We also leverage federated learning (FL) to train the \textit{2Ts-DRL} model in a distributed manner, aiming to protect the edge devices' data privacy. Simulation results corroborate the effectiveness of both the \textit{2Ts-DRL} and FL in the I-UDEC framework and prove that our proposed algorithm can reduce task execution time up to 31.87%.
Due to high utility in many applications, from social networks to blockchain to power grids, deep learning on non-Euclidean objects such as graphs and manifolds, coined Geometric Deep Learning (GDL), continues to gain an ever increasing interest. We propose a new Lévy Flights Graph Convolutional Networks (LFGCN) method for semi-supervised learning, which casts the Lévy Flights into random walks on graphs and, as a result, allows both to accurately account for the intrinsic graph topology and to substantially improve classification performance, especially for heterogeneous graphs. Furthermore, we propose a new preferential P-DropEdge method based on the Girvan-Newman argument. That is, in contrast to uniform removing of edges as in DropEdge, following the Girvan-Newman algorithm, we detect network periphery structures using information on edge betweenness and then remove edges according to their betweenness centrality. Our experimental results on semi-supervised node classification tasks demonstrate that the LFGCN coupled with P-DropEdge accelerates the training task, increases stability and further improves predictive accuracy of learned graph topology structure. Finally, in our case studies we bring the machinery of LFGCN and other deep networks tools to analysis of power grid networks - the area where the utility of GDL remains untapped.
It is widely accepted that Ethereum mining is highly centralized. Nonetheless, centralization has been mostly characterized by exclusively looking at the influence that independent miners or mining pools can have over the network. Moreover, models of mining behavior assume that miners are either unrelated or only relate via mining pools under highly structured and transparent agreements. If these assumptions and the predictions they entail were to be completely accurate, there would not be any evidence of on-chain transactions between miners, other than the ones expected from mining pool payouts. By looking at on-chain transactions between miners in the Ethereum Network we find that aside from the payouts from mining pools to small miners, there are also transactions that define relationships between mining pools, independent miners and between independent miners and mining pools. Furthermore, by characterizing the topology of the network of miner transactions, we find the emergence of highly connected clusters that control significant amounts of hashing power and exhibit relationships in the opposite direction of what theoretical models predict. This more nuanced characterization of mining centralization can help identify network vulnerabilities and inform protocol redesigns.
Taehyun Kim, Hyomin Shin, Hyung Ju Hwang, Seungwon Jeong
Steemit is a blockchain-based social media platform, where authors can get author rewards in the form of cryptocurrencies called STEEM and SBD (Steem Blockchain Dollars) if their posts are upvoted. Interestingly, curators (or voters) can also get rewards by voting others' posts, which is called a curation reward. A reward is proportional to a curator's STEEM stakes. Throughout this process, Steemit hopes "good" content will be automatically discovered by users in a decentralized way, which is known as the Proof-of-Brain (PoB). However, there are many bot accounts programmed to post automatically and get rewards, which discourages real human users from creating good content. We call this type of bot a posting bot. While there are many papers that studied bots on traditional centralized social media platforms such as Facebook and Twitter, we are the first to study posting bots on a blockchain-based social media platform. Compared with the bot detection on the usual social media platforms, the features we created have an advantage that posting bots can be detected without limiting the number or length of posts. We can extract the features of posts by clustering distances between blog data or replies. These features are obtained from the Minimum Average Cluster from Clustering Distance between Frequent words and Articles (MAC-CDFA), which is not used in any of the previous social media research. Based on the enriched features, we enhanced the quality of classification tasks. Comparing the F1-scores, the features we created outperformed the features used for bot detection on Facebook and Twitter.
Bitcoin, as one of the most popular cryptocurrency, is recently attracting much attention of investors. Bitcoin price prediction task is consequently a rising academic topic for providing valuable insights and suggestions. Existing bitcoin prediction works mostly base on trivial feature engineering, that manually designs features or factors from multiple areas, including Bticoin Blockchain information, finance and social media sentiments. The feature engineering not only requires much human effort, but the effectiveness of the intuitively designed features can not be guaranteed. In this paper, we aim to mining the abundant patterns encoded in bitcoin transactions, and propose k-order transaction graph to reveal patterns under different scope. We propose the transaction graph based feature to automatically encode the patterns. A novel prediction method is proposed to accept the features and make price prediction, which can take advantage from particular patterns from different history period. The results of comparison experiments demonstrate that the proposed method outperforms the most recent state-of-art methods.
The vast majority of applications at this moment rely on centralized servers to relay messages between clients, where these servers are considered trusted third-parties. With the rise of blockchain technologies over the last few years, there has been a move away from both centralized servers and traditional federated models to more decentralized peer-to-peer alternatives. However, there appears to be a trilemma between security, scalability, and decentralization in blockchain-based systems. Deconstructing this trilemma using well-known threat models, we define a typology of centralized, federated, and decentralized architectures. Each of the different architectures has this trilemma play out differently. Facing a possible decentralized future, we outline seven hard problems facing decentralization and theorize that the differences between centralized, federated, and decentralized architectures depend on differing social interpretations of trust.
Given that Proof-of-Work (PoW) and Proof-of-Stake (PoS) are plutocratic, and other common consensus protocols are mostly permission-based, we look for a consensus protocol that will suit the needs of e-Democracy. In particular, what we need is a distributed ledger that will record and, to the possible extent, execute the public will. We propose a combination of any given permission-based protocol together with a trust graph between the nodes, which supplies the required permission for new nodes. As a result, the consensus protocol reaches consensus at every iteration between a known list of agents and then updates this list between iterations. This paper is based on prior work that shows the conditions under which a community can grow while maintaining a bounded number of byzantines. It combines a permission-based consensus protocol (such as pBFT) with a community expansion algorithm (such as the one in the prior work) to arrive at a consensus protocol in which the set of agents can change in time, while being sybil-resilient.
Bitcoin and its decentralized computing paradigm for digital currency trading are one of the most disruptive technology in the 21st century. This article presents a novel approach to developing a Bitcoin transaction forecast model, DLForecast, by leveraging deep neural networks for learning Bitcoin transaction network representations. DLForecast makes three original contributions. First, we explore three interesting properties between Bitcoin transaction accounts: topological connectivity pattern of Bitcoin accounts, transaction amount pattern, and transaction dynamics. Second, we construct a time-decaying reachability graph and a time-decaying transaction pattern graph, aiming at capturing different types of spatial-temporal Bitcoin transaction patterns. Third, we employ node embedding on both graphs and develop a Bitcoin transaction forecasting system between user accounts based on historical transactions with built-in time-decaying factor. To maintain an effective transaction forecasting performance, we leverage the multiplicative model update (MMU) ensemble to combine prediction models built on different transaction features extracted from each corresponding Bitcoin transaction graph. Evaluated on real-world Bitcoin transaction data, we show that our spatial-temporal forecasting model is efficient with fast runtime and effective with forecasting accuracy over 60 percent and improves the prediction performance by 50 percent when compared to forecasting model built on the static graph baseline.
Muhammad Baqer Mollah, Jun Zhao, Dusit Niyato, Yong Liang Guan · 8 authors
Internet of Vehicles (IoV) is an emerging concept that is believed to help realize the vision of intelligent transportation systems (ITSs). IoV has become an important research area of impactful applications in recent years due to the rapid advancements in vehicular technologies, high throughput satellite communication, the Internet of Things, and cyber-physical systems. IoV enables the integration of smart vehicles with the Internet and system components attributing to their environments, such as public infrastructures, sensors, computing nodes, pedestrians, and other vehicles. By allowing the development of a common information exchange platform between vehicles and heterogeneous vehicular networks, this integration aims to create a better environment and public space for the people as well as to enhance safety for all road users. Being a participatory data exchange and storage, the underlying information exchange platform of IoV needs to be secure, transparent, and immutable in order to achieve the intended objectives of ITS. In this connection, the adoption of blockchain as a system platform for supporting the information exchange needs of IoV has been explored. Due to their decentralized and immutable nature, IoV applications enabled by blockchain are believed to have a number of desirable properties, such as decentralization, security, transparency, immutability, and automation. In this article, we present a contemporary survey on the latest advancement in blockchain for IoV. Particularly, we highlight the different application scenarios of IoV after carefully reviewing the recent literature. We also investigate several key challenges where blockchain is applied in IoV. Furthermore, we present the future opportunities and explore further research directions of IoV as a key enabler of ITS.