Shuo Yuan, Bin Cao, Yao Sun, Zhiguo Wan · 5 authors
Introducing blockchain into Federated Learning (FL) to build a trusted edge computing environment for transmission and learning has attracted widespread attention as a new decentralized learning pattern. However, traditional consensus mechanisms and architectures of blockchain systems face significant challenges in handling large-scale FL tasks, especially on Internet of Things (IoT) devices, due to their substantial resource consumption, limited transaction throughput, and complex communication requirements. To address these challenges, this paper proposes ChainFL, a novel two-layer blockchain-driven FL system. It splits the IoT network into multiple shards within the subchain layer, effectively reducing the scale of information exchange, and employs a Direct Acyclic Graph (DAG)-based mainchain as the mainchain layer, enabling parallel and asynchronous cross-shard validation. Furthermore, the FL procedure is customized to integrate deeply with blockchain technology, and a modified DAG consensus mechanism is designed to mitigate distortion caused by abnormal models. To provide a proof-of-concept implementation and evaluation, multiple subchains based on Hyperledger Fabric and a self-developed DAG-based mainchain are deployed. Extensive experiments demonstrate that ChainFL significantly surpasses conventional FL systems, showing up to a 14% improvement in training efficiency and a threefold increase in robustness.
Internet of quantum blockchains (IoB) will be the future Internet. In this paper, we make two new contributions to IoB: developing a block based quantum channel networking technology to handle its security modeling in face of the quantum supremacy and establishing IoB based FinTech platform model with dynamic pricing for stable digital currency. The interaction between our new contributions is also addressed. In doing so, we establish a generalized IoB security model by quantum channel networking in terms of both time and space quantum entanglements with quantum key distribution (QKD). Our IoB can interact with general structured things (e.g., supply chain systems) having online trading and payment capability via stable digital currency and can handle vector-valued data streams requiring synchronized services. Thus, within our designed QKD, a generalized random number generator for private and public keys is proposed by a mixed zero-sum and non-zero-sum resource-competition pricing policy. The effectiveness of this policy is justified by diffusion modeling with approximation theory and numerical implementations.
Unauthorized resource access represents a typical security threat in the Internet of Things (IoT), while distributed ledger technologies (e.g., blockchain and IOTA) hold great promise to address this threat. Although blockchain-based IoT access control schemes have been the most popular ones, they suffer from several significant limitations, such as high monetary cost and low throughput of processing access requests. To overcome these limitations, this paper proposes a novel IoT access control scheme by combining the fee-less IOTA technology and the Ciphertext-Policy Attribute-Based Encryption (CP-ABE) technology. To control the access to a resource, a token, which records access permissions to this resource, is encrypted by the CP-ABE technology and uploaded to the IOTA Tangle (i.e., the underlying database of IOTA). Any user can fetch the encrypted token from the Tangle, while only those who can decrypt this token are authorized to access the resource. In this way, the proposed scheme enables not only distributed, fee-less and scalable access control thanks to the IOTA but also fine-grained attribute-based access control thanks to the CP-ABE. We show the feasibility of our scheme by implementing a proof-of-concept prototype system using smart phones (Google Pixel 3XL) and a commercial IoT gateway (NEC EGW001). We also evaluate the performance of the proposed scheme in terms of access request processing throughput. The experimental results show that our scheme enables object owners to authorize access rights to a large number of subjects in a much (about 5 times) shorter time than the existing access control scheme called Decentralized Capability-based Access Control framework using IOTA (DCACI), significantly improving the access request processing throughput.
Zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) allows a party, known as the prover, to convince another party, known as the verifier, that he knows a private value $v$, without revealing it, such that $F(u,v)=y$ for some function $F$ and public values $u$ and $y$. There are various versions of zk-SNARK, among them, Quadratic Arithmetic Program (QAP)-based zk-SNARK has been widely used in practice, specially in Blockchain technology. This is attributed to two desirable features; its fixed-size proof and the very light computation load of the verifier. However, the computation load of the prover in QAP-based zkSNARKs, is very heavy, even-though it is designed to be very efficient. This load can be beyond the prover's computation power to handle, and has to be offloaded to some external servers. In the existing offloading solutions, either (i) the load of computation, offloaded to each sever, is a fraction of the prover's primary computation (e.g., DZIK), however the servers need to be trusted, (ii) the servers are not required to be trusted, but the computation complexity imposed to each one is the same as the prover's primary computation (e.g., Trinocchio). In this paper, we present a scheme, which has the benefits of both solutions. In particular, we propose a secure multi-party proof generation algorithm where the prover can delegate its task to $N $ servers, where (i) even if a group of $T \in \mathbb{N}$ servers, $T\le N$, collude, they cannot gain any information about the secret value $v$, (ii) the computation complexity of each server is less than $1/(N-T)$ of the prover's primary computation. The design is such that we don't lose the efficiency of the prover's algorithm in the process of delegating the tasks to external servers.
A reputation of high volatility accompanies the emergence of Bitcoin as a financial asset. This paper intends to nuance this reputation and clarify our understanding of Bitcoin's volatility. Using daily, weekly, and monthly closing prices and log-returns data going from September 2014 to January 2021, we find that Bitcoin is a prime example of an asset for which the two conceptions of volatility diverge. We show that, historically, Bitcoin allies both high volatility (high Standard Deviation) and high predictability (low Approximate Entropy), relative to Gold and S&P 500. Moreover, using tools from Extreme Value Theory, we analyze the convergence of moments, and the mean excess functions of both the closing prices and the log-returns of the three assets. We find that the closing price of Bitcoin is consistent with a generalized Pareto distribution, when the closing prices of the two other assets (Gold and S&P 500) present thin-tailed distributions. However, returns for all three assets are heavy tailed and second moments (variance, standard deviation) non-convergent. In the case of Bitcoin, lower sampling frequencies (monthly vs weekly, weekly vs daily) drastically reduce the Kurtosis of log-returns and increase the convergence of empirical moments to their true value. The opposite effect is observed for Gold and S&P 500. These properties suggest that Bitcoin's volatility is essentially an intra-day and intra-week phenomenon that is strongly attenuated on a weekly time-scale, and make it an attractive store of value to investors and speculators, but its high standard deviation excludes its use a currency.
This paper studies to what extent the cost of operating a proof-of-work blockchain is intrinsically linked to the cost of preventing attacks, and to what extent the underlying digital ledger security budgets are correlated with the cryptocurrency market outcomes. We theoretically derive an equilibrium relationship between the cryptocurrency price, mining rewards and mining costs, and blockchain security outcomes. Using daily crypto market data for 2014-2021 and employing the autoregressive distributed lag approach - that allows treating all the relevant moments of the blockchain series as potentially endogenous - we provide empirical evidence of cryptocurrency price and mining rewards indeed being intrinsically linked to blockchain security outcomes.
In this paper, we propose a polar coding based scheme for set reconciliation between two network nodes. The system is modeled as a well-known Slepian-Wolf setting induced by a fixed number of deletions. The set reconciliation process is divided into two phases: 1) a deletion polar code is employed to help one node to identify the possible deletion indices, which may be larger than the number of genuine deletions; 2) a lossless compression polar code is then designed to feedback those indices with minimum overhead. Our scheme can be viewed as a generalization of polar codes to some emerging network-based applications such as the package synchronization in blockchains. Some connections with the existing schemes based on the invertible Bloom lookup tables (IBLTs) and network coding are also observed and briefly discussed.
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.
In the high-stakes race to develop more scalable blockchains, some platforms (Binance, Cosmos, EOS, TRON, etc.) have adopted committee-based consensus (CBC) protocols, whereby the blockchain's record-keeping rights are entrusted to a committee of elected block producers. In theory, the smaller the committee, the faster the blockchain can reach consensus and the more it can scale. What's less clear, is whether such protocols ensure that honest committees can be consistently elected, given blockchain users typically have limited information on who to vote for. We show that the approval voting mechanism underlying most CBC protocols is complex and can lead to intractable optimal voting strategies. We empirically characterize some simpler intuitive voting strategies that users tend to resort to in practice and prove that these nonetheless converge to optimality exponentially quickly in the number of voters. Exponential convergence ensures that despite its complexity, CBC exhibits robustness and has some efficiency advantages over more popular staked-weighted lottery protocols currently underlying many prominent blockchains such as Ethereum.
Divija Swetha Gadiraju, V. Lalitha, Vaneet Aggarwal
Blockchain is a distributed ledger with wide applications. Due to the increasing storage requirement for blockchains, the computation can be afforded by only a few miners. Sharding has been proposed to scale blockchains so that storage and transaction efficiency of the blockchain improves at the cost of security guarantee. This paper aims to consider a new protocol, Secure-Repair-Blockchain (SRB), which aims to decrease the storage cost at the miners. In addition, SRB also decreases the bootstrapping cost, which allows for new miners to easily join a sharded blockchain. In order to reduce storage, coding-theoretic techniques are used in SRB. In order to decrease the amount of data that is transferred to the new node joining a shard, the concept of exact repair secure regenerating codes is used. The proposed blockchain protocol achieves lower storage than those that do not use coding, and achieves lower bootstrapping cost as compared to the different baselines.
Although blockchain, the supporting technology of Bitcoin and various cryptocurrencies, has offered a potentially effective framework for numerous applications, it still suffers from the adverse affects of the impossibility triangle. Performance, security, and decentralization of blockchains normally do not scale simultaneously with the number of participants in the network. The recent introduction of error correcting codes in sharded blockchain by Li et al. partially settles this trilemma, boosting throughput without compromising security and decentralization. In this paper, we improve the coded sharding scheme in three ways. First, we propose a novel 2-Dimensional Sharding strategy, which inherently supports cross-shard transactions, alleviating the need for complicated inter-shard communication protocols. Second, we employ distributed storage techniques in the propagation of blocks, improving latency under restricted bandwidth. Finally, we incorporate polynomial cryptographic primitives of low degree, which brings coded blockchain techniques into the realm of feasible real-world parameters.
An important feature of Proof-of-Work (PoW) blockchains is full dynamic availability, allowing miners to go online and offline while requiring only 50% of the online miners to be honest. Existing Proof-of-stake (PoS), Proof-of-Space and related protocols are able to achieve this property only partially, either putting the additional assumption that adversary nodes to be online from the beginning and no new adversary nodes come online afterwards, or use additional trust assumptions for newly joining nodes.We propose a new PoS protocol PoSAT which can provably achieve dynamic availability fully without any additional assumptions. The protocol is based on the longest chain and uses a Verifiable Delay Function for the block proposal lottery to provide an arrow of time. The security analysis of the protocol draws on the recently proposed technique of Nakamoto blocks as well as the theory of branching random walks. An additional feature of PoSAT is the complete unpredictability of who will get to propose a block next, even by the winner itself. This unpredictability is at the same level of PoW protocols, and is stronger than that of existing PoS protocols using Verifiable Random Functions.
In certain blockchain systems, light nodes are clients that download only a small portion of the block. Light nodes are vulnerable to data availability (DA) attacks where a malicious node hides an invalid portion of the block from the light nodes. Recently, a technique based on erasure codes called Coded Merkle Tree (CMT) was proposed by Yu et al. that enables light nodes to detect a DA attack with high probability. The CMT is constructed using LDPC codes for fast decoding but can fail to detect a DA attack if a malicious node hides a small stopping set of the code. To combat this, Yu et al. used well-studied techniques to design random LDPC codes with high minimum stopping set size. Although effective, these codes are not necessarily optimal for this application. In this paper, we demonstrate a more specialized LDPC code design to improve the security against DA attacks. We achieve this goal by providing a deterministic LDPC code construction that focuses on concentrating stopping sets to a small group of variable nodes rather than only eliminating stopping sets. We design these codes by modifying the Progressive Edge Growth algorithm into a technique called the entropy-constrained PEG (EC-PEG) algorithm. This new method demonstrates a higher probability of detecting DA attacks and allows for good codes at short lengths.
Siyi Yang, Ahmed Hareedy, Robert Calderbank, Lara Dolecek
In order to accommodate the ever-growing data from various, possibly independent, sources and the dynamic nature of data usage rates in practical applications, modern cloud data storage systems are required to be scalable, flexible, and heterogeneous. The recent rise of the blockchain technology is also moving various information systems towards decentralization to achieve high privacy at low costs. While codes with hierarchical locality have been intensively studied in the context of centralized cloud storage due to their effectiveness in reducing the average reading time, those for decentralized storage networks (DSNs) have not yet been discussed. In this paper, we propose a joint coding scheme where each node receives extra protection through the cooperation with nodes in its neighborhood in a heterogeneous DSN with any given topology. This work extends and subsumes our prior work on coding for centralized cloud storage. In particular, our proposed construction not only preserves desirable properties such as scalability and flexibility, which are critical in dynamic networks, but also adapts to arbitrary topologies, a property that is essential in DSNs but has been overlooked in existing works.
Efficient and reliable access control in smart cities is critical for the protection of various resources for decision making and task execution. Existing centralized access control schemes suffer from the limitations of single point of failure, low reliability, and poor scalability. This article, therefore, proposes a distributed and reliable access control framework for smart cities by combining the blockchain smart contract technology and the attribute-based access control (ABAC) model. The framework consists of one policy management contract (PMC) for managing the ABAC policies, one subject attribute management contract (SAMC) for managing the attributes of subjects (i.e., entities accessing resources), one object attribute management contract (OAMC) for managing the attributes of objects (i.e., resources being accessed), and one access control contract (ACC) for performing the access control. To show the feasibility of the proposed framework, we construct a local private Ethereum blockchain system to implement the four smart contracts and also conduct experiments to evaluate the monetary cost as well as to compare the proposed framework with an existing access control list (ACL)-based scheme. The experimental results show that although the proposed scheme consumes more money than the ACL-based scheme at the deployment stage, it introduces less monetary cost during the system running especially for large-scale smart cities.
In this paper we introduce a scheme for detecting manipulated audio and video. The scheme is a synthesis of blockchains, encrypted spread spectrum watermarks, perceptual hashing and digital signatures, which we call an Embedded Blockchain. Within this scheme, we use the blockchain for its data structure of a cryptographically linked list, cryptographic hashing for absolute comparisons, perceptual hashing for flexible comparisons, digital signatures for proof of ownership, and encrypted spread spectrum watermarking to embed the blockchain into the background noise of the media. So each media recording has its own unique blockchain, with each block holding information describing the media segment. The problem of verifying the integrity of the media is recast to traversing the blockchain, block-by-block, and segment-by-segment of the media. If any chain is broken, the difference in the computed and extracted perceptual hash is used to estimate the level of manipulation.
Random K-out graphs are receiving attention as a model to construct sparse yet well-connected topologies in distributed systems including sensor networks, federated learning, and cryptocurrency networks. In response to the growing heterogeneity in emerging real-world networks, where nodes differ in resources and requirements, inhomogeneous random K-out graphs, denoted by $H(n;μ,K_n)$, were proposed recently. Motivated by practical settings where establishing links is costly and only a bounded choice of $K_n$ is feasible ($K_n = O(1)$), we study the size of the largest connected sub-network of $H(n;μ,K_n)$, We first show that the trivial condition of $K_n \geq 2$ for all $n$ is sufficient to ensure that $H(n;μ,K_n)$, contains a giant component of size $n-O(1)$ whp. Next, to model settings where nodes can fail or get compromised, we investigate the size of the largest connected sub-network in $H(n;μ,K_n)$, when $d_n$ nodes are selected uniformly at random and removed from the network. We show that if $d_n=O(1)$, a giant component of size $n- \OO(1)$ persists for all $K_n \geq 2$ whp. Further, when $d_n=o(n)$ nodes are removed from $H(n;μ,K_n)$, the remaining nodes contain a giant component of size $n(1-o(1))$ whp for all $K_n \geq 2$. We present numerical results to demonstrate the size of the largest connected component when the number of nodes is finite.
Furqan Jameel, Muhammad Awais Javed, Sherali Zeadally, Riku Jäntti
Cellular vehicle-to-everything (V2X) communication is expected to herald the age of autonomous vehicles in the coming years. With the integration of blockchain in such networks, information of all granularity levels, from complete blocks to individual transactions, would be accessible to vehicles at any time. Specifically, the blockchain technology is expected to improve the security, immutability, and decentralization of cellular V2X communication through smart contract and distributed ledgers. Although blockchain-based cellular V2X networks hold promise, many challenges need to be addressed to enable the future interoperability and accessibility of such large-scale platforms. One such challenge is the offloading of mining tasks in cellular V2X networks. While transportation authorities may try to balance the network mining load, the vehicles may select the nearest mining clusters to offload a task. This may cause congestion and disproportionate use of vehicular network resources. To address this issue, we propose a game-theoretic approach for balancing the load at mining clusters while maintaining fairness among offloading vehicles. Keeping in mind the low-latency requirements of vehicles, we consider a finite channel blocklength transmission which is more practical compared to the use of infinite blocklength codes. The simulation results obtained with our proposed offloading framework show improved performance over the conventional nearest mining cluster selection technique.
Privacy preservation is a big concern for various sectors. To protect individual user data, one emerging technology is differential privacy. However, it still has limitations for datasets with frequent queries, such as the fast accumulation of privacy cost. To tackle this limitation, this paper explores the integration of a secured decentralised ledger, blockchain. Blockchain will be able to keep track of all noisy responses generated with differential privacy algorithm and allow for certain queries to reuse old responses. In this paper, a demo of a proposed blockchain-based privacy management system is designed as an interactive decentralised web application (DApp). The demo created illustrates that leveraging on blockchain will allow the total privacy cost accumulated to decrease significantly.
Due to the rapid development of the internet of Things (ioT), a massive number of devices are connected to the internet. For these distributed devices in ioT networks, how to ensure their security and privacy becomes a significant challenge. Blockchain technology provides a promising solution to protect the data integrity, provenance, privacy, and consistency for ioT networks. in blockchains, communication is a prerequisite for participants, which are distributed in the system, to reach consensus. However, in ioT networks, most of the devices communicate through wireless links, which are not always reliable. Hence, the communication reliability of ioT devices influences the system security. in this article, we rethink the roles of communication and computing in blockchains by accounting for communication reliability. We analyze the trade-off between communication reliability and computing power in blockchain security, and present a lower bound to the computing power that is needed to conduct an attack with a given communication reliability. Simulation results show that adversarial nodes can succeed in tampering with a block with less computing power by hindering the propagation of blocks from other nodes.
Ranvir Rana, Sreeram Kannan, David Tse, Pramod Viswanath
Propelled by the growth of large-scale blockchain deployments, much recent progress has been made in designing sharding protocols that achieve throughput scaling linearly in the number of nodes. However, existing protocols are not robust to an adversary adaptively corrupting a fixed fraction of nodes. In this paper, we propose Free2Shard -- a new architecture that achieves near-linear scaling while being secure against a fully adaptive adversary. The focal point of this architecture is a dynamic self-allocation algorithm that lets users allocate themselves to shards in response to adversarial action, without requiring a central or cryptographic proof. This architecture has several attractive features unusual for sharding protocols, including: (a) the ability to handle the regime of large number of shards (relative to the number of nodes); (b) heterogeneous shard demands; (c) requiring only a small minority to follow the self-allocation; (d) asynchronous shard rotation; (e) operation in a purely identity-free proof-of-work setting. The key technical contribution is a deep mathematical connection to the classical work of Blackwell in dynamic game theory.
The blockchain paradigm provides a mechanism for content dissemination and distributed consensus on Peer-to-Peer (P2P) networks. While this paradigm has been widely adopted in industry, it has not been carefully analyzed in terms of its network scaling with respect to the number of peers. Applications for blockchain systems, such as cryptocurrencies and IoT, require this form of network scaling. In this paper, we propose a new stochastic network model for a blockchain system. We identify a structural property called \emph{one-endedness}, which we show to be desirable in any blockchain system as it is directly related to distributed consensus among the peers. We show that the stochastic stability of the network is sufficient for the one-endedness of a blockchain. We further establish that our model belongs to a class of network models, called monotone separable models. This allows us to establish upper and lower bounds on the stability region. The bounds on stability depend on the connectivity of the P2P network through its conductance and allow us to analyze the scalability of blockchain systems on large P2P networks. We verify our theoretical insights using both synthetic data and real data from the Bitcoin network.
The growing size of modern datasets necessitates splitting a large scale computation into smaller computations and operate in a distributed manner. Adversaries in a distributed system deliberately send erroneous data in order to affect the computation for their benefit. Boolean functions are the key components of many applications, e.g., verification functions in blockchain systems and design of cryptographic algorithms. We consider the problem of computing a Boolean function in a distributed computing system with particular focus on \emph{security against Byzantine workers}. Any Boolean function can be modeled as a multivariate polynomial with high degree in general. However, the security threshold (i.e., the maximum number of adversarial workers can be tolerated such that the correct results can be obtained) provided by the recent proposed Lagrange Coded Computing (LCC) can be extremely low if the degree of the polynomial is high. We propose three different schemes called \emph{coded Algebraic normal form (ANF)}, \emph{coded Disjunctive normal form (DNF)} and \emph{coded polynomial threshold function (PTF)}. The key idea of the proposed schemes is to model it as the concatenation of some low-degree polynomials and threshold functions. In terms of the security threshold, we show that the proposed coded ANF and coded DNF are optimal by providing a matching outer bound.
Applications from finance to epidemiology and cyber-security require accurate forecasts of dynamic phenomena, which are often only partially observed. We demonstrate that a system's predictability degrades as a function of temporal sampling, regardless of the adopted forecasting model. We quantify the loss of predictability due to sampling, and show that it cannot be recovered by using external signals. We validate the generality of our theoretical findings in real-world partially observed systems representing infectious disease outbreaks, online discussions, and software development projects. On a variety of prediction tasks---forecasting new infections, the popularity of topics in online discussions, or interest in cryptocurrency projects---predictability irrecoverably decays as a function of sampling, unveiling fundamental predictability limits in partially observed systems.