To validate transactions, cryptocurrencies such as Bitcoin and Ethereum require nodes to verify that a blockchain is valid. This entails downloading and verifying all blocks, taking hours and requiring gigabytes of bandwidth and storage. Hence, clients with limited resources cannot verify transactions independently without trusting full nodes. Bitcoin and Ethereum offer light clients known as simplified payment verification (SPV) clients, that can verify the chain by downloading only the block headers. Unfortunately, the storage and bandwidth requirements of SPV clients still increase linearly with the chain length. For example, as of July 2019, an SPV client in Ethereum needs to download and store about 4 GB of data.Recently, Kiayias et al. proposed a solution known as noninteractive proofs of proof-of-work (NIPoPoW) that allows a light client to download and store only a polylogarithmic number of block headers in expectation. Unfortunately, NIPoPoWs are succinct only as long as no adversary influences the honest chain, and can only be used in chains with fixed block difficulty, contrary to most cryptocurrencies which adjust block difficulty frequently according to the network hashrate.We introduce FlyClient, a novel transaction verification light client for chains of variable difficulty. FlyClient is efficient both asymptotically and practically and requires downloading only a logarithmic number of block headers while storing only a single block header between executions. Using an optimal probabilistic block sampling protocol and Merkle Mountain Range (MMR) commitments, FlyClient overcomes the limitations of NIPoPoWs and generates shorter proofs over all measured parameters. In Ethereum, FlyClient achieves a synchronization proof size of less than 500 KB which is roughly 6,600x smaller than SPV proofs. We finally discuss how FlyClient can be deployed with minimal changes to the existing cryptocurrencies via an uncontentious velvet fork.

Organizational networks are vulnerable to trafficanalysis attacks that enable adversaries to infer sensitive information fromnetwork traffic—even if encryption is used. Typical anonymous communication networks are tailored to the Internet and are poorly suited for organizational networks.We present PriFi, an anonymous communication protocol for LANs, which protects users against eavesdroppers and provides high-performance traffic-analysis resistance. PriFi builds onDining Cryptographers networks (DC-nets), but reduces the high communication latency of prior designs via a new client/relay/server architecture, in which a client’s packets remain on their usual network path without additional hops, and in which a set of remote servers assist the anonymization process without adding latency. PriFi also solves the challenge of equivocation attacks, which are not addressed by related work, by encrypting traffic based on communication history. Our evaluation shows that PriFi introduces modest latency overhead (≈ 100ms for 100 clients) and is compatible with delay-sensitive applications such as Voice-over-IP.

We propose a protocol that allows the participants of a permissionless decentralized system to agree on a set of identities in the presence of a computationally-bounded Byzantine adversary. Our protocol guarantees that the fraction of identities belonging to the adversary in the set of identities is at most equal to the total computational hash power of the adversary.

A major approach to overcoming the performance and scalability limitations of current blockchain protocols is to use sharding which is to split the overheads of processing transactions among multiple, smaller groups of nodes. These groups work in parallel to maximize performance while requiring significantly smaller communication, computation, and storage per node, allowing the system to scale to large networks. However, existing sharding-based blockchain protocols still require a linear amount of communication (in the number of participants) per transaction, and hence, attain only partially the potential benefits of sharding. We show that this introduces a major bottleneck to the throughput and latency of these protocols. Aside from the limited scalability, these protocols achieve weak security guarantees due to either a small fault resiliency (e.g., 1/8 and 1/4) or high failure probability, or they rely on strong assumptions (e.g., trusted setup) that limit their applicability to mainstream payment systems. We propose RapidChain, the first sharding-based public blockchain protocol that is resilient to Byzantine faults from up to a 1/3 fraction of its participants, and achieves complete sharding of the communication, computation, and storage overhead of processing transactions without assuming any trusted setup. RapidChain employs an optimal intra-committee consensus algorithm that can achieve very high throughputs via block pipelining, a novel gossiping protocol for large blocks, and a provably-secure reconfiguration mechanism to ensure robustness. Using an efficient cross-shard transaction verification technique, our protocol avoids gossiping transactions to the entire network. Our empirical evaluations suggest that RapidChain can process (and confirm) more than 7,300 tx/sec with an expected confirmation latency of roughly 8.7 seconds in a network of 4,000 nodes with an overwhelming time-to-failure of more than 4,500 years.

In secure multi-party shuffling, multiple parties, each holding an input, want to agree on a random permutation of their inputs while keeping the permutation secret. This problem is important as a primitive in many privacy-preserving applications such as anonymous communication, location-based services, and electronic voting. Known techniques for solving this problem suffer from poor scalability, load-balancing issues, trusted party assumptions, and/or weak security guarantees. In this paper, we propose an unconditionally-secure protocol for multi-party shuffling that scales well with the number of parties and is load-balanced. In particular, we require each party to send only a polylogarithmic number of bits and perform a polylogarithmic number of operations while incurring only a logarithmic round complexity. We show security under universal compos ability against up to about n/3 fully-malicious parties. We also provide simulation results in the full version of this paper showing that our protocol improves significantly over previous work. For example, for one million parties, when compared to the state of the art, our protocol reduces the communication and computation costs by at least three orders of magnitude and slightly decreases the number of communication rounds.

The problem of dual-hop transmission from a source to a destination via two parallel full-duplex relays in block Rayleigh fading environment is investigated. All nodes in the network are assumed to be oblivious to their forward channel gains; however, they have perfect information about their backward channel gains. We also assume a stringent decoding delay constraint of one fading block that makes the definition of ergodic (Shannon) capacity meaningless. The focus of this paper is on simple, efficient, and practical relaying schemes to increase the expected-rate at the destination. For this purpose, various combinations of relaying protocols and the broadcast approach (multi-layer coding) are proposed. For the decode-forward (DF) relaying, the maximum finite-layer expected-rate as well as two upper-bounds on the continuous-layer expected-rate are obtained. The main feature of the proposed DF scheme is that the layers being decoded at both relays are added coherently at the destination although each relay has no information about the number of layers being successfully decoded by the other relay. It is proved that the optimal coding scheme is transmitting uncorrelated signals via the relays. Next, the maximum expected-rate of ON/OFF based amplify-forward (AF) relaying is analytically derived. For further performance improvement, a hybrid decode-amplify-forward (DAF) relaying strategy, adopting the broadcast approach at the source and relays, is proposed and its maximum throughput and maximum finite-layer expected-rate are presented. Moreover, the maximum throughput and maximum expected-rate in the compress-forward (CF) relaying adopting the broadcast approach, using optimal quantizers and Wyner-Ziv compression at the relays, are fully derived. All theoretical results are illustrated by numerical simulations. As it turns out from the results, when the ratio of the relay power to the source power is high, the CF relaying outperforms DAF (and hence outperforms both DF and AF relaying); otherwise, DAF scheme is superior.

We describe an algorithm for fully-anonymous broadcast in large-scale networks. The protocol is similar to the dining cryptographers networks (DC-Nets) in that both are based on secure multi-party computation (MPC) techniques. However, we address the weaknesses of DC-Nets, which are poor scalability and vulnerability to jamming attacks. When compared to the state-of-the-art, our protocol reduces the total bit complexity from O(n2) to Õ(n) per anonymous message sent in a network of size n at the expense of an increase in total latency from O(1) to polylog(n). Our protocol can tolerate up to 1/3 dishonest parties, which are controlled by a static computationally-unbounded Byzantine adversary.

This paper studies the problem of dual-hop transmission from a source to a destination via two parallel full-duplex relays in block Rayleigh fading environment. All nodes in the network are assumed to be oblivious to their forward-channel gains, however, they have perfect information about their backward-channel gains. We also assume a stringent decoding delay constraint of one fading block that makes the definition of ergodic (Shannon) capacity meaningless. Hence, we adopt the broadcast approach to increase the expected-rate received at the destination. The focus of this paper is on simple, efficient, and practical relaying schemes to increase the average achievable rate at the destination. The maximum expected-rate of ON/OFF based amplify-forward relaying is analytically derived. For further performance improvement, a hybrid decode-amplify-forward relaying strategy, adopting the broadcast approach at the source and relays, is proposed and its maximum throughput and expected-rate are presented. Finally, two different upper-bounds, based on the full cooperation between the relays, are obtained. All theoretical results are illustrated by numerical simulations. As it turns out from the numerical results, when the ratio of the relay power to the source power is low, the proposed hybrid decode-amplify-forward relaying scheme meets the obtained upper-bound.

The point-to-point multiple-input single-output (MISO) channel is investigated in uncorrelated block fading environment with Rayleigh distribution. The maximum throughput and maximum expected-rate of this channel are obtained under the assumption that the transmitter is oblivious to the channel state information (CSI), however, the receiver has perfect CSI. First, we prove that the optimum transmission strategy maximizing the throughput is to use all available antennas and perform equal power allocation with uncorrelated signals. Furthermore, to increase the expected-rate, multi-layer coding is applied. Analogously, we establish that sending uncorrelated signals and performing equal power allocation across all available antennas at each layer is optimum. Finally, a closed form expression for the maximum continuous-layer expected-rate of MISO channels is also obtained.

This paper studies the problem of two-hop transmission from a single-antenna source to a single-antenna destination via two single-antenna relays. The relays operate in a full-duplex mode and they are not capable of buffering data. The links from the source to the relays and from the relays to the destination are considered to be Rayleigh block fading and there is no direct link between the source and the destination. There is also no link between the relays. Consequently, the half-duplex mode is a direct result of the full-duplex mode with frequency or time division. All nodes are assumed to be oblivious to their forward-channel gains, however, they have perfect information about their backward-channel gains. We also assume a stringent decoding delay constraint of one fading block that makes the definition of ergodic (Shannon) capacity meaningless. Hence, we adopt the broadcast approach (multi-layer coding) to maximize the expected-rate received at the destination. For this purpose, the decode-forward (DF) relaying adopting the broadcast approach is proposed. The main feature of the proposed scheme is that the layers being decoded at both relays are added coherently at the destination although each relay has no information about the number of layers being successfully decoded by the other relay. It is proved that the optimum strategy maximizing the throughput and expected-rate is to send uncorrelated signals over the relays. The maximum throughput is analytically formulated. An achievable rate as well as upper-bounds are presented for the maximum expected-rate of the channel.

A flexible rate Slepian-Wolf (SW) code is constructed, which is vital for wireless sensor network applications. The proposed solution is based on an efficient and practical algorithm to compute the syndrome of the rate-compatible convolutional codes (RCPC). Using this algorithm, there is no need to compute the syndrome of punctured version of the mother code for each puncturing matrix, which is complex. Instead, the syndrome of the punctured code is the punctured version of the syndrome of the mother code using the same pattern of puncturing. The algorithm is general for all convolutional codes in Zq. The strategy is also generalized for parallel and serial concatenated convolutional codes. For the cases, where the dependencies among sources are modeled as a virtual discrete channel, a simplified decoding scheme is suggested. This method is generalized to achieve all points on the SW boundary using a simple code design technique. Simulation results demonstrate the performance and effectiveness of the proposed methods.

A simple but powerful scheme for distributed source coding (DSC) based on the concept of binning and syndromes and non traditional turbo codes is proposed. The previous works on the compression with side information using turbo codes and the binning technique are focused on binary turbo codes. The source is considered to be binary or is converted to a binary stream. This conversion, however, reduces the redundancy that could be exploited by the compression algorithm. To achieve higher compression efficiency, the authors propose using a scheme based on a turbo decoder that decides over symbols rather than bits. In the same direction and for further performance improvement, at the cost of increased encoder complexity, they also present a DSC scheme based on non-binary turbo codes. The results demonstrate improved performance. Based on the suggested algorithms, a scheme for gathering real data in wireless sensor networks and assess the corresponding energy savings is proposed.