The 3XORSUM problem aims to find (x, y, z) such that x + y + z = 0 over {0, 1}d, with each variable drawn from one of 3 randomly generated lists. In addition to being of interest in its own right, this problem has cryptographic applications including proof of stake methods in Blockchain.The 3XORSUM problem is also related to the integer 3SUM problem from theoretical computer science on which there is extensive recent literature. It is conjectured that the integer 3SUM problem has complexity $\tilde \Omega \left({{n^2}}\right)$ for lists of size O(n).Wagner [10] has presented an algorithm with complexity Õ(2d/3) for finding a 4XORSUM solution (x + y + z + w = 0) with each variable drawn from one of 4 randomly generated lists of size O(2d/3) with members from {0, 1}d.We present an algorithm which solves the 3XORSUM problem for randomly generated binary vectors from {0, 1}dwith time and memory complexity Õ(n) = Õ(2d/3). This substantially improves results from [1], [8]. Our algorithm has applications to blockchains and other cryptographic problems.
At the heart of Blockchains is the trustless leader election mechanism for achieving consensus among pseudo-anonymous peers, without the need of oversight from any third party or authority whatsoever. So far, two main mechanisms are being discussed: proof-of-work (PoW) and proof-of-stake (PoS). PoW relies on demonstration of computational power, and comes with the markup of huge energy wastage in return of the stake in cyrpto-currency. PoS tries to address this by relying on owned stake (i.e., amount of crypto-currency) in the system. In both cases, Blockchains are limited to systems with financial basis. This forces non-crypto-currency Blockchain applications to resort to "permissioned" setting only, effectively centralizing the system. However, non-crypto-currency permisionless blockhains could enable secure and self-governed peer-to-peer structures for numerous emerging application domains, such as education and health, where some trust exists among peers. This creates a new possibility for valuing trust among peers and capitalizing it as the basis (stake) for reaching consensus. In this paper we show that there is a viable way for permisionless non-financial Blockhains to operate in completely decentralized environments and achieve leader election through proof-of-trust (PoT). In our PoT construction, peer trust is extracted from a trust network that emerges in a decentralized manner and is used as a waiver for the effort to be spent for PoW, thus dramatically reducing total energy expenditure of the system. Furthermore, our PoT construction is resilient to the risk of small cartels monopolizing the network (as it happens with the mining-pool phenomena in PoW) and is not vulnerable to sybils. We evluate security guarantees, and perform experimental evaluation of our construction, demonstrating up to 10-fold energy savings compared to PoW without trading off any of the decentralization characteristics, with further guarantees against risks of monopolization.
We present a blockchain based system that allows data owners, cloud vendors, and AI developers to collaboratively train machine learning models in a trustless AI marketplace. Data is a highly valued digital asset and central to deriving business insights. Our system enables data owners to retain ownership and privacy of their data, while still allowing AI developers to leverage the data for training. Similarly, AI developers can utilize compute resources from cloud vendors without loosing ownership or privacy of their trained models. Our system protocols are set up to incentivize all three entities - data owners, cloud vendors, and AI developers to truthfully record their actions on the distributed ledger, so that the blockchain system provides verifiable evidence of wrongdoing and dispute resolution. Our system is implemented on the Hyperledger Fabric and can provide a viable alternative to centralized AI systems that do not guarantee data or model privacy. We present experimental performance results that demonstrate the latency and throughput of its transactions under different network configurations where peers on the blockchain may be spread across different datacenters and geographies. Our results indicate that the proposed solution scales well to large number of data and model owners and can train up to 70 models per second on a 12-peer non optimized blockchain network and roughly 30 models per second in a 24 peer network.
In this paper, we have achieved privacy protection and high transparency in a permissioned blockchain. There is a sidechain that connects the permissionless blockchain and the permissioned blockchain. The behavior in the permissioned blockchain is almost a black box from the perspective of the permissionless blockchain. While this fact is useful for privacy protection, there is room for improvement in terms of transparency. To improve the transparency of the permissioned blockchain under privacy protection, we consider traceability in the permissioned blockchain consisting of the following three properties: trade privacy (who trades with whom and at what asset amount), preservation (the total amount inside the permissioned blockchain, including deposits and withdrawals to the permissionless blockchain, is immutable), and noninvolvement (some members in the permissioned blockchain are not involved in some trades, and it is possible to prove that specified members performed the transaction). To the best of our knowledge, we are the first to achieve both preservation and noninvolvement while protecting the privacy of transactions. Our approach is as follows. We model traceability based on the hidden Markov model. Because the proof of traceability requires the calculation of more than quadratic degrees, we encrypt this model by homomorphic encryption. The number of participants in the permissioned blockchain corresponds to the number of additions in the model. Then, we can construct the encrypted model by employing somewhat homomorphic encryption. The establishment of the original model is verifiable by applying the noninteractive zero-knowledge proof of the knowledge that the plaintext is equal to zero. This is an adaptation of Benhamouda et al. (Asiacrypt 2014).
Block chain technology, while revolutionizing various sectors, faces significant challenges regarding data privacy and security. As block chain networks become more widespread, the need for privacy-preserving techniques becomes critical to ensure the confidentiality, integrity, and anonymity of user data. This article reviews various privacy-enhancing techniques implemented in block chain networks, including cryptographic protocols, zero-knowledge proofs, and off-chain solutions. The aim is to identify their effectiveness, limitations, and the trade-offs between privacy and performance. Through a comprehensive analysis, this study explores existing methodologies and suggests potential improvements for safeguarding privacy while maintaining the decentralized and transparent nature of block chain systems.
Federated identity management enables users to access multiple systems using\na single login credential. However, to achieve this a complex privacy\ncompromising authentication has to occur between the user, relying party (RP)\n(e.g., a business), and a credential service provider (CSP) that performs the\nauthentication. In this work, we use a smart contract on a blockchain to enable\nan architecture where authentication no longer involves the CSP. Authentication\nis performed solely through user to RP communications (eliminating fees and\nenhancing privacy). No third party needs to be contacted, not even the smart\ncontract. No public key infrastructure (PKI) needs to be maintained. And no\nrevocation lists need to be checked. In contrast to competing smart contract\napproaches, ours is hierarchically managed (like a PKI) enabling better\nvalidation of attribute providers and making it more useful for large entities\nto provide identity services for their constituents (e.g., a government) while\nstill enabling users to maintain a level of self-sovereignty.\n
Yang Zhao, Jun Zhao, Linshan Jiang, Rui Tan · 8 authors
Home appliance manufacturers strive to obtain feedback from users to improve their products and services to build a smart home system. To help manufacturers develop a smart home system, we design a federated learning (FL) system leveraging the reputation mechanism to assist home appliance manufacturers to train a machine learning model based on customers' data. Then, manufacturers can predict customers' requirements and consumption behaviors in the future. The working flow of the system includes two stages: in the first stage, customers train the initial model provided by the manufacturer using both the mobile phone and the mobile edge computing (MEC) server. Customers collect data from various home appliances using phones, and then they download and train the initial model with their local data. After deriving local models, customers sign on their models and send them to the blockchain. In case customers or manufacturers are malicious, we use the blockchain to replace the centralized aggregator in the traditional FL system. Since records on the blockchain are untampered, malicious customers or manufacturers' activities are traceable. In the second stage, manufacturers select customers or organizations as miners for calculating the averaged model using received models from customers. By the end of the crowdsourcing task, one of the miners, who is selected as the temporary leader, uploads the model to the blockchain. To protect customers' privacy and improve the test accuracy, we enforce differential privacy on the extracted features and propose a new normalization technique. We experimentally demonstrate that our normalization technique outperforms batch normalization when features are under differential privacy protection. In addition, to attract more customers to participate in the crowdsourcing FL task, we design an incentive mechanism to award participants.
The Covid-19 pandemic has made individuals and organizations to rethink the way of handling identity verification and credentials sharing particularly in quarantined situations. In this study, we investigate the inefficiencies of traditional identity systems, and discuss how a proper implementation of Blockchain technology would result in safer, more secure, privacy respecting and remote friendly identity systems. As a result, we propose a Blockchain based framework for digital identity verification, record attestation and record sharing, and we explain the framework in details with certain use cases. Our proposed framework promotes individuals to fully control their identity data and govern the level of the identity data sharing.
There is considerable interest today in the use of blockchain technology to provide better visibility into shared information among a number of participants and systems arranged in a decentralized peer-to-peer topology. Several challenges in blockchain technology remain to be addressed, including the interoperability, survivability, and manageability of blockchain systems. Crucial to answering these challenges is the need to understand aspects of the Internet architecture that has made it scalable, resilient, and a commercial success as a global connectivity infrastructure. In this paper, we discuss a design philosophy for interoperable blockchain systems, using the design philosophy of the Internet architecture as the basis to identify key design principles. We recast some of the challenges faced in the design of the Internet architecture to that of the design of an interoperable blockchain architecture. We emphasize interoperability as a crucial requirement for the survivability and manageability of blockchain systems. The goal is to define an interoperable blockchain architecture, in which common components of the blockchain architecture can begin to be standardized, leading to lowering of development costs, better reusability, and higher degree of interoperability.
Sujaya Maiyya, Victor Zakhary, Mohammad Javad Amiri, Divyakant Agrawal · 5 authors
The uprise of Bitcoin and other peer-to-peer cryptocurrencies has opened many interesting and challenging problems in cryptography, distributed systems, and databases. The main underlying data structure is blockchain, a scalable fully replicated structure that is shared among all participants and guarantees a consistent view of all user transactions by all participants in the system. In this tutorial, we discuss the basic protocols used in blockchain, and elaborate on its main advantages and limitations. To overcome these limitations, we provide the necessary distributed systems background in managing large scale fully replicated ledgers, using Byzantine Agreement protocols to solve the consensus problem. Finally, we expound on some of the most recent proposals to design scalable and efficient blockchains in both permissionless and permissioned settings. The focus of the tutorial is on the distributed systems and database aspects of the recent innovations in blockchains.
Fangyu Gai, Cesar Grajales, Jianyu Niu, Jalalzai, Mohammad Mussadiq · 5 authors
Sidechain technology has been envisioned as a promising solution to accelerate today's public blockchains in terms of scalability and interoperability. By relying on the mainchain for security, different sidechains can formulate their own rules to reach consensus. Although the literature has considered the possibility of using consensus protocols in the sidechain, so far a tailor-made consensus protocol for sidechains with high performance and formal security proof has not been attempted. To fill this gap, we introduce Cumulus, a low overhead, highly efficient, security provable sidechain protocol. Cumulus makes use of smart contracts to ensure that only one block proposed in the sidechain will be enforced on the mainchain in each round, thereby achieving consensus in an efficient manner. We give a formal specification of Cumulus which ensures safety and liveness without any online requirements of clients. For security analysis, we provide formal security definitions and proofs under Universally Composable Security (UCS) model. As a proof of concept, we implement Cumulus and evaluate it in an Ethereum testnet.
The emergence of e-commerce and e-voting platforms has resulted in the rise in the volume of sensitive information over the Internet. This has resulted in an increased demand for secure and private means of information computation. Towards this, the Yao's Millionaires' problem, i.e., to determine the richer among two millionaires' securely, finds an application. In this work, we present a new solution to the Yao's Millionaires' problem namely, Privacy Preserving Comparison (PPC). We show that PPC achieves this comparison in constant time as well as in one execution. PPC uses semi-honest third parties for the comparison who do not learn any information about the values. Further, we show that PPC is collusion-resistance. To demonstrate the significance of PPC, we present a secure, approximate single-minded combinatorial auction, which we call TPACAS, i.e., Truthful, Privacy-preserving Approximate Combinatorial Auction for Single-minded bidders. We show that TPACAS, unlike previous works, preserves the following privacies relevant to an auction: agent privacy, the identities of the losing bidders must not be revealed to any other agent except the auctioneer (AU), bid privacy, the bid values must be hidden from the other agents as well as the AU and bid-topology privacy, the items for which the agents are bidding must be hidden from the other agents as well as the AU. We demonstrate the practicality of TPACAS through simulations. Lastly, we also look at TPACAS' implementation over a publicly distributed ledger, such as the Ethereum blockchain.
Adriano Di Luzio, Danilo Francati, Giuseppe Ateniese
This work presents Arcula, a new design for hierarchical deterministic wallets that brings identity-based addresses to the blockchain. Arcula is built on top of provably secure cryptographic primitives. It generates all its cryptographic secrets from a user-provided seed and enables the derivation of new public keys based on the identities of users, without requiring any secret information. Unlike other wallets, it achieves all these properties while being secure against privilege escalation. We formalize the security model of hierarchical deterministic wallets and prove that an attacker compromising an arbitrary number of users within an Arcula wallet cannot escalate his privileges and compromise users higher in the access hierarchy. Our design works out-of-the-box with any blockchain that enables the verification of signatures on arbitrary messages. We evaluate its usage in a real-world scenario on the Bitcoin Cash network.
Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovič · 5 authors
Many blockchain-based algorithms, such as Bitcoin, implement a decentralized asset transfer system, often referred to as a cryptocurrency. As stated in the original paper by Nakamoto, at the heart of these systems lies the problem of preventing double-spending; this is usually solved by achieving consensus on the order of transfers among the participants. In this paper, we treat the asset transfer problem as a concurrent object and determine its consensus number, showing that consensus is, in fact, not necessary to prevent double-spending. We first consider the problem as defined by Nakamoto, where only a single process---the account owner---can withdraw from each account. Safety and liveness need to be ensured for correct account owners, whereas misbehaving account owners might be unable to perform transfers. We show that the consensus number of an asset transfer object is $1$. We then consider a more general $k$-shared asset transfer object where up to $k$ processes can atomically withdraw from the same account, and show that this object has consensus number $k$. We establish our results in the context of shared memory with benign faults, allowing us to properly understand the level of difficulty of the asset transfer problem. We also translate these results in the message passing setting with Byzantine players, a model that is more relevant in practice. In this model, we describe an asynchronous Byzantine fault-tolerant asset transfer implementation that is both simpler and more efficient than state-of-the-art consensus-based solutions. Our results are applicable to both the permissioned (private) and permissionless (public) setting, as normally their differentiation is hidden by the abstractions on top of which our algorithms are based.
A Coordination Blockchain is a blockchain with the task of coordinating activities of multiple private blockchains. This paper discusses the pros and cons of using Ethereum MainNet, the public Ethereum blockchain, as a Coordination Blockchain. The requirements Ethereum MainNet needs to fulfil to perform this role are discussed within the context of Ethereum Private Sidechains, a private blockchain technology which allows many blockchains to be operated in parallel, and allows atomic crosschain transactions to execute across blockchains. Ethereum MainNet is a permissionless network which aims to offer strong authenticity, integrity, and non-repudiation properties, that incentivises good behaviour using crypto economics. This paper demonstrates that Ethereum MainNet does deliver these properties. It then provides a comprehensive review of the features of Ethereum Private Sidechains, with a focus on the potential usage of Coordination Blockchains for these features. Finally, the merits of using Ethereum MainNet as a Coordination Blockchain are assessed. For Ethereum Private Sidechains, we found that Ethereum MainNet is best suited to storing long term static data that needs to be widely available, such as the Ethereum Registration Authority information. However, due to Ethereum MainNet's probabilistic finality, it is not well suited to information that needs to be available and acted upon immediately, such as the Sidechain Public Keys and Atomic Crosschain Transaction state information that need to be accessible prior to the first atomic crosschain transaction being issued on a sidechain. Although this paper examined the use of Ethereum MainNet as a Coordination Blockchain within reference to Ethereum Private Sidechains, the discussions and observations of the typical tasks a Coordination blockchain may be expected to perform are applicable more widely to any multi-blockchain system.
Francisco J. Marmolejo-Cossío, Eric Brigham, Benjamin Sela, Jonathan Katz
The Bitcoin protocol prescribes certain behavior by the miners who are responsible for maintaining and extending the underlying blockchain; in particular, miners who successfully solve a puzzle, and hence can extend the chain by a block, are supposed to release that block immediately. Eyal and Sirer showed, however, that a selfish miner is incentivized to deviate from the protocol and withhold its blocks under certain conditions. The analysis by Eyal and Sirer, as well as in followup work, considers a \emph{single} deviating miner (who may control a large fraction of the hashing power in the network) interacting with a remaining pool of honest miners. Here, we extend this analysis to the case where there are \emph{multiple} (non-colluding) selfish miners. We find that with multiple strategic miners, specific deviations from honest mining by multiple strategic agents can outperform honest mining, even if individually miners would not be incentivised to be dishonest. This previous point effectively renders the Bitcoin protocol to be less secure than previously thought.
Kfir Lev-Ari, Alexander Spiegelman, Idit Keidar, Dahlia Malkhi
Financial institutions are currently looking into technologies for permissioned blockchains. A major effort in this direction is Hyperledger, an open source project hosted by the Linux Foundation and backed by a consortium of over a hundred companies. A key component in permissioned blockchain protocols is a byzantine fault tolerant (BFT) consensus engine that orders transactions. However, currently available BFT solutions in Hyperledger (as well as in the literature at large) are inadequate for financial settings; they are not designed to ensure fairness or to tolerate selfish behavior that arises when financial institutions strive to maximize their own profit. We present FairLedger, a permissioned blockchain BFT protocol, which is fair, designed to deal with rational behavior, and, no less important, easy to understand and implement. The secret sauce of our protocol is a new communication abstraction, called detectable all-to-all (DA2A), which allows us to detect participants (byzantine or rational) that deviate from the protocol, and punish them. We implement FairLedger in the Hyperledger open source project, using Iroha framework, one of the biggest projects therein. To evaluate FairLegder's performance, we also implement it in the PBFT framework and compare the two protocols. Our results show that in failure-free scenarios FairLedger achieves better throughput than both Iroha's implementation and PBFT in wide-area settings.
Zhengbing Hu, Ivan Dychka, Mykola Onai, Yuri Zhykin
One of the most important problems of modern cryptocurrency networks is the problem of scaling: advanced cryptocurrencies like Bitcoin can handle around 5 transactions per second. One of the most promising solutions to this problem are second layer payment protocols: payment networks implemented on top of base cryptocurrency network layer, based on the idea of delaying publication of intermediate transactions and using base network only as a finalization layer. Such networks consist of entities that interact with the cryptocurrency system via a payment channel protocol, and can send, receive and forward payments. This paper describes a formal actor-based model of payment channel network and uses it to formulate a modified payment protocol that can be executed in the network without requiring any information about its topology and thus can hide information about financial relations between nodes.
The global Electronic Health Record (EHR) market is growing dramatically and expected to reach $39.7 billions by 2022. To safe-guard security and privacy of EHR, access control is an essential mechanism for managing EHR data. This paper proposes a hybrid architecture to facilitate access control of EHR data by using both blockchain and edge node. Within the architecture, a blockchain-based controller manages identity and access control policies and serves as a tamper-proof log of access events. In addition, off-chain edge nodes store the EHR data and apply policies specified in Abbreviated Language For Authorization (ALFA) to enforce attribute-based access control on EHR data in collaboration with the blockchain-based access control logs. We evaluate the proposed hybrid architecture by utilizing Hyperledger Composer Fabric blockchain to measure the performance of executing smart contracts and ACL policies in terms of transaction processing time and response time against unauthorized data retrieval.
We develop new foundations on transaction untraceability for CryptoNote-style blockchain systems. In particular, we observe new attacks; develop theoretical foundations to model transaction untraceability; provide the least upper bound of transaction untraceability guarantee; provide ways to efficiently and automatically verify whether a given ledger achieves optimal transaction untraceability; and provide a general solution that achieves provably optimal transaction untraceability. Unlike previous cascade effect attacks (ESORICS' 17 and PETS' 18) on CryptoNote-style transaction untraceability, we consider not only a passive attacker but also an active adaptive attacker. Our observed attacks allow both types of attacker to trace blockchain transactions that cannot be traced by using the existing attacks. We develop a series of new games, which we call "The Sun-Tzu Survival Problem", to model CryptoNote-style blockchain transaction untraceability and our identified attacks. In addition, we obtain seven novel results, where three of them are negative and the rest are positive. In particular, thanks to our abstract game, we are able to build bipartite graphs to model transaction untraceability, and provide reductions to formally relate the hardness of calculating untraceability to the hardness of calculating the number of perfect matchings in all possible bipartite graphs. We prove that calculating transaction untraceability is a #P-complete problem, which is believed to be even more difficult to solve than NP problems. In addition, we provide the first result on the least upper bound of transaction untraceability. Moreover, through our theoretical results, we are able to provide ways to efficiently and automatically verify whether a given ledger achieves optimal transaction untraceability. Furthermore, we propose a simple strategy for CryptoNote-style blockchain systems to achieve optimal untraceability. We take Monero as a concrete example to demonstrate how to apply this strategy to optimise the untraceability guarantee provided by Monero.
Public blockchains in support of Smart Contracts (SC), like Ethereum enable everyone to represent scarce, valuable resources (like cryptocurrencies) as so-called tokens. Token issuing and management was the first blockchain use case. However, programming languages and runtime systems used in the current blockchains for their SCs lack a secure and straightforward way to implement and handle tokens. The unnecessary complexity in doing so can lead to erroneous implementation of tokens and applications built on top of these, including the loss or theft of tokens as it happened. The most known attack was "TheDAO" attack which led to the "loss" of tokens, valued at that time at approximately 60 M US Dollar. A better and secure token representation directly embedded into a SC runtime and SC programming language could prevent loss of tokens. Thus this paper presents an approach including parts of a programming language using it. The core of the model is to use opaque and substructural data types together with an onchain soundness checker to generically represent tokens securely as values similar to integers and booleans. Such opaque data types enforce that only a designated piece of code can create values of that type. The substructural data types allow arbitrary values to express scarcity by preventing the duplication and elimination of values. The on-chain soundness checker ensures that the deployed code does not violate guarantees given by the type system, which includes opaque and substructural data types.
Yan Zhu, Chunli Lv, Zichuan Zeng, Jingfu Wang · 5 authors
Abstract Different from the current cloud storage solutions, which are mostly centralized storage providers, this paper proposes a decentralized storage system based on blockchain technology, which can make full use of the remaining space of personal hard disks of users around the world. Storage provider performs a data integrity certificate to the user, and after verifying that the verification is passed, the user pays the storage fee to the storage provider through the lightning network technology. All proofs and payment information are stored in the blockchain, which guarantees the security and credibility of the system. Compared with the current mainstream distributed storage systems, this scheme has been improved in terms of system access and payment methods.
Blockchains and smart contracts are an emerging, promising technology, that has received considerable attention. We use the blockchain technology, and in particular Ethereum, to implement a large-scale event-based Internet of Things (IoT) control system. We argue that the distributed nature of the "ledger," as well as, Ethereum's capability of parallel execution of replicated "smart contracts", provide the sought after automation, generality, flexibility, resilience, and high availability. We design a realistic blockchain-based IoT architecture, using existing technologies while by taking into consideration the characteristics and limitations of IoT devices and applications. Furthermore, we leverage blockchain's immutability and Ethereum's support for custom tokens to build a robust and efficient token-based access control mechanism. Our evaluation shows that our solution is viable and offers significant security and usability advantages.
With the growth in popularity for cryptocurrencies the need for privacy preserving blockchains is growing as well. Zcash is such a blockchain, providing transaction privacy through zero-knowledge proofs. In this paper we analyze transaction linkability in Zcash based on the currency minting transactions (mining). Using predictable usage patterns and clustering heuristics on mining transactions an attacker can link to publicly visible addresses over 84% of the volume of the transactions that use a ZK-proof. Since majority of Zcash transactions are not yet using ZK-proofs, we show that overall 95.5% of the total number of Zcash transactions are potentially linkable to public addresses by just observing the mining activity.