The Subset Sum Ratio problem (SSR) asks, given a multiset $A$ of positive integers, to find two disjoint subsets of $A$ such that the largest-to-smallest ratio of their sums is minimized. In this paper we study the $k$-version of SSR, namely $k$-Subset Sum Ratio ($k$-SSR), which asks to minimize the largest-to-smallest ratio of sums of $k$ disjoint subsets of $A$. We develop an approximation scheme for $k$-SSR running in $O({n^{2k}}/{\varepsilon^{k-1}})$ time, where $n=|A|$ and $\varepsilon$ is the error parameter. To the best of our knowledge, this is the first FPTAS for $k$-SSR for fixed $k>2$. We also study the $k$-way Number Partitioning Ratio ($k$-PART) problem, which differs from $k$-SSR in that the $k$ subsets must constitute a partition of $A$; this problem in fact corresponds to the objective of minimizing the largest-to-smallest sum ratio in the family of Multiway Number Partitioning problems. We present a more involved FPTAS for $k$-PART, also achieving $O({n^{2k}}/{\varepsilon^{k-1}})$ time complexity. Notably, $k$-PART is also equivalent to the Minimum Envy-Ratio problem with identical valuation functions, which has been studied in the context of fair division of indivisible goods. Thus, for the case of identical valuations, our FPTAS represents a significant improvement over the $O(n^{4k^2+1}/\varepsilon^{2k^2})$ bound obtained by Nguyen and Rothe's FPTAS for Minimum Envy-Ratio with general additive valuations. Lastly, we propose a second FPTAS for $k$-SSR, which employs carefully designed calls to the first one; the new scheme has a time complexity of $\widetilde{O}(n/{\varepsilon^{3k-1}})$, thus being much faster when $n\gg 1/ \varepsilon$.

Bitcoin is the first and most popular decentralized cryptocurrency to date. In this work, we extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin backbone , and prove three of its fundamental properties which we call Common Prefix , Chain Quality, and Chain Growth in the static setting where the number of players remains fixed. Our proofs hinge on appropriate and novel assumptions on the “hashing power” of the protocol participants and their interplay with the protocol parameters and the time needed for reliable message passing between honest parties in terms of computational steps. A takeaway from our analysis is that, all else being equal, the protocol’s provable tolerance in terms of the number of adversarial parties (or, equivalently, their “hashing power” in our model) decreases as the duration of a message passing round increases. Next, we propose and analyze applications that can be built “on top” of the backbone protocol, specifically focusing on Byzantine agreement (BA) and on the notion of a public transaction ledger. Regarding BA, we observe that a proposal due to Nakamoto falls short of solving it, and present a simple alternative which works assuming that the adversary’s hashing power is bounded by 1/3. The public transaction ledger captures the essence of Bitcoin’s operation as a cryptocurrency, in the sense that it guarantees the liveness and persistence of committed transactions. Based on this notion, we describe and analyze the Bitcoin system as well as a more elaborate BA protocol and we prove them secure assuming the adversary’s hashing power is strictly less than 1/2. Instrumental to this latter result is a technique we call 2-for-1 proof-of-work (PoW) that has proven to be useful in the design of other PoW-based protocols.

Resource-based consensus is the backbone of permissionless distributed ledger systems. The security of such protocols relies fundamentally on the level of resources actively engaged in the system. The variety of different resources (and related proof protocols, some times referred to as PoX in the literature) raises the fundamental question whether it is possible to utilize many of them in tandem and build multi-resource consensus protocols. The challenge in combining different resources is to achieve fungibility between them, in the sense that security would hold as long as the cumulative adversarial power across all resources is bounded.

Blockchains maintain two types of data: Application data and consensus data. Towards long-term blockchain scalability, both of these must be pruned. While a large body of literature has explored the pruning of application data (UTXOs, account balances, and contract state), little has been said about the permanent pruning of consensus data (block headers). We present a protocol which allows pruning the blockchain by garbage collecting old blocks as they become unnecessary. These blocks can simply be discarded and are no longer stored by any miner. We show that all miners can be light miners with no harm to security. Our protocol is based on the notion of superblocks, blocks that have achieved an unusually high difficulty. We leverage them to represent underlying proof-of-work without ever illustrating it, storing it, or transmitting it. After our pruning is applied, the storage and communication requirements for consensus data are reduced exponentially. We develop new probabilistic mathematical methods to analyze our protocol in the random oracle model. We prove our protocol is both secure and succinct under an uninterrupted honest majority assumption for 1/3 adversaries. Our protocol is the first to achieve always secure, always succinct, and online Non-Interactive Proofs of Proof-of-Work, all necessary components for a logarithmic space mining scheme. Our work has applications beyond mining and also constitutes an improvement in state-of-the-art superlight clients and cross-chain bridges.

We consider the problem of stable matching with dynamic preference lists. At each time-step, the preference list of some player may change by swapping random adjacent members. The goal of a central agency (algorithm) is to maintain an approximately stable matching, in terms of number of blocking pairs, at all time-steps. The changes in the preference lists are not reported to the algorithm, but must instead be probed explicitly. We design an algorithm that in expectation and with high probability maintains a matching that has at most O((log n)^2 blocking pairs.

Abstract We consider the problem of minimizing the communication in single-database private information retrieval protocols in the case where the length of the data to be transmitted is large. We present first rate-optimal protocols for 1-out-of-n computationallyprivate information retrieval (CPIR), oblivious transfer (OT), and strong conditional oblivious transfer (SCOT). These protocols are based on a new optimalrate leveled homomorphic encryption scheme for large-output polynomial-size branching programs, that might be of independent interest. The analysis of the new scheme is intricate: the optimal rate is achieved if a certain parameter s is set equal to the only positive root of a degree-(m + 1) polynomial, where m is the length of the branching program. We show, by using Galois theory, that even when m = 4, this polynomial cannot be solved in radicals. We employ the Newton-Puiseux algorithm to find a Puiseux series for s, and based on this, propose a Θ (logm)-time algorithm to find an integer approximation to s.

We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once Boolean formulae. A read-once Boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond to variables, and the internal nodes are labeled by binary connectives. Under certain assumptions, this representation is unique. Thus, one can define the depth of a formula as the depth of the tree that represents it. The complexity of the evaluation of general read-once formulae, has attracted interest mainly in the decision tree model. In the communication complexity model, many interesting results deal with specific read-once formulae, such as DISJOINTNESS and TRIBES. In this paper we use information theory methods to prove lower bounds that hold for any read-once formula. Our lower bounds are of the form n(f)/cd(f), where n(f) is the number of variables and d(f) the depth of the formula, and they are optimal up to the constant c in the denominator.