Yongjie Ye, Jingjing Zhang, Weigang Wu, Xiapu Luo · 5 authors
The payment channel, which allows two parties to perform micropayments without involving the blockchain, has become a promising proposal to improve the scalability of decentralized ledgers such as Bitcoin and Ethereum. Payment channels have been extended to the payment network, through which users can utilize existing channels as intermediary links to route coins to others. However, routing payments through multiple channels bears nontrivial overheads. It requires every intermediary channel to lock a portion of its available capacity until the payment is settled. This may lead to deadlock in a concurrent situation. The intermediary nodes in a payment path may also charge fees for routing a payment. The longer the routing path, the more serious the above problems. In this paper, we design and develop a novel off-chain system to shorten the routing path for the payment network. In particular, we propose the channel hub, which is an extension of the payment hub, to allows transferring coins directly from one payment channel to another within the same hub. That is, the channel hub can be viewed as a shortcut device for the underlying payment network. We design a new protocol named Boros to perform secure off-chain cross-channel transfers through the channel hub. We not only present the security definition of the Boros protocol formally but also prove its security using the UC-framework. To demonstrate the feasibility of the Boros protocol, we develop a proof-of-concept prototype running on the Ethereum. Our evaluation shows that our system can effectively shorten the off-chain routing path.
Plasma is a framework for scalable off-chain computation. We describe and evaluate Plasma Cash, an improved Plasma construction which leverages non-fungible tokens and Sparse Merkle Trees to reduce the data storage and bandwidth requirements for users. We analyze the cryptoeconomic exit and challenge mechanisms used to keep user funds secured, even when the Plasma Cash chain's consensus algorithm is compromised. A reference implementation is provided for evaluation. Finally, we briefly discuss further improvements that can be made to the Plasma Cash protocol such as arbitrary denomination payments, less user data checking, fast and optimistic exits.
Smart contracts on a blockchain behave precisely as specified by their code. A vulnerability in this code can lead to unexpected behaviour, which is hard to fix because a blockchain does not allow to change smart contract code after its deployment. Such vulnerabilities have led to several incidents. In the aftermath of such an event, a hard-fork between Ethereum and Ethereum classic was the result. This thesis proposes to develop a new smart contract programming language with the primary focus on safety, auditability, and the intention to prevent as many of the known categories of vulnerabilities by design as possible. The programming language's code is validated during deployment and afterwards isolated from other smart contracts running on the same blockchain to enforce compile-time guarantees during runtime. The designed programming language does evaluate new concepts and paradigms rarely used in non-smart contract environments for their potential benefit in a smart contract environment.
The blockchain data structure maintained via the longest-chain rule---popularized by Bitcoin---is a powerful algorithmic tool for consensus algorithms. Such algorithms achieve consistency for blocks in the chain as a function of their depth from the end of the chain. While the analysis of Bitcoin guarantees consistency with error $2^{-k}$ for blocks of depth $O(k)$, the state-of-the-art of proof-of-stake (PoS) blockchains suffers from a quadratic dependence on $k$: these protocols, exemplified by Ouroboros (Crypto 2017), Ouroboros Praos (Eurocrypt 2018) and Sleepy Consensus (Asiacrypt 2017), can only establish that depth $Θ(k^2)$ is sufficient. Whether this quadratic gap is an intrinsic limitation of PoS---due to issues such as the nothing-at-stake problem---has been an urgent open question, as deployed PoS blockchains further rely on consistency for protocol correctness. We give an axiomatic theory of blockchain dynamics that permits rigorous reasoning about the longest-chain rule and achieve, in broad generality, $Θ(k)$ dependence on depth in order to achieve consistency error $2^{-k}$. In particular, for the first time, we show that PoS protocols can match proof-of-work protocols for linear consistency. We analyze the associated stochastic process, give a recursive relation for the critical functionals of this process, and derive tail bounds in both i.i.d. and martingale settings via associated generating functions.
We live in an era of information and it is very important to handle the exchange of information. While sending data to an authorized source, we need to protect it from unauthorized sources, changes, and authentication. ZKP technique can be used in designing secure authentication systems that dont involve any direct exchange of information between the claimant and the verifier thus preventing any possible leak of personal information. We propose a Zero-Knowledge Proof (ZKP) algorithm based on isomorphic graphs. We suggest most of the computations should be carried out on the users' web browser without revealing the password to the server at any point in time. Instead, it will generate random graphs and their permutations based on the login ID and password.
Danilo Francati, Giuseppe Ateniese, Abdoulaye Faye, Andrea Maria Milazzo · 7 authors
The cloud changed the way we manage and store data. Today, cloud storage services offer clients an infrastructure that allows them a convenient source to store, replicate, and secure data online. However, with these new capabilities also come limitations, such as lack of transparency, limited decentralization, and challenges with privacy and security. And, as the need for more agile, private and secure data solutions continues to grow exponentially, rethinking the current structure of cloud storage is mission-critical for enterprises. By leveraging and building upon blockchain's unique attributes, including immutability, security to the data element level, distributed (no single point of failure), we have developed a solution prototype that allows data to be reliably stored while simultaneously being secured, with tamper-evident auditability, via blockchain. The result, Audita, is a flexible solution that assures data protection and solves challenges such as scalability and privacy. Audita works via an augmented blockchain network of participants that include storage-nodes and block-creators. In addition, it provides an automatic and fair challenge system to assure that data is distributed and reliably and provably stored. While the prototype is built on Quorum, the solution framework can be used with any blockchain platform. The benefit is a system that is built to grow along with the data needs of enterprises, while continuing to build the network via incentives and solving for issues such as auditing and outsourcing.
Atomic Crosschain Transaction technology allows composable programming across private Ethereum blockchains. It allows for inter-contract and inter-blockchain function calls that are both synchronous and atomic: if one part fails, the whole call graph of function calls is rolled back. Traditional Ethereum contract functions can limit which accounts can call them by specialised application program logic. This is important as it allows application developers to specify which callers can execute functions that update contract state. In this paper we introduce the strategy required to restrict which contracts on one blockchain can call a function in a contract that is deployed on another blockchain. We show that validating the Originating Blockchain Id (the blockchain the crosschain function call started on), From Blockchain Id, and From Account provides contracts with certainty that a function call came from a specific contract on a specific blockchain.
We initiate the study of non-interactive zero-knowledge (NIZK) arguments for languages in QMA. Our first main result is the following: if Learning With Errors (LWE) is hard for quantum computers, then any language in QMA has an NIZK argument with preprocessing. The preprocessing in our argument system consists of (i) the generation of a CRS and (ii) a single (instance-independent) quantum message from verifier to prover. The instance-dependent phase of our argument system involves only a single classical message from prover to verifier. Importantly, verification in our protocol is entirely classical, and the verifier needs not have quantum memory; its only quantum actions are in the preprocessing phase. Our second contribution is to extend the notion of a classical proof of knowledge to the quantum setting. We introduce the notions of arguments and proofs of quantum knowledge (AoQK/PoQK), and we show that our non-interactive argument system satisfies the definition of an AoQK. In particular, we explicitly construct an extractor which can recover a quantum witness from any prover which is successful in our protocol. Finally, we show that any language in QMA has an (interactive) proof of quantum knowledge.
We provide several advances to the understanding of the class of Quantum Merlin-Arthur proof systems (QMA), the quantum analogue of NP. Our central contribution is proving a longstanding conjecture that the Consistency of Local Density Matrices (CLDM) problem is QMA-hard under Karp reductions. The input of CLDM consists of local reduced density matrices on sets of at most k qubits, and the problem asks if there is an n-qubit global quantum state that is locally consistent with all of the k-qubit local density matrices. The containment of this problem in QMA and the QMA-hardness under Turing reductions were proved by Liu [APPROX-RANDOM 2006]. Liu also conjectured that CLDM is QMA-hard under Karp reductions, which is desirable for applications, and we finally prove this conjecture. We establish this result using the techniques of simulatable codes of Grilo, Slofstra, and Yuen [FOCS 2019], simplifying their proofs and tailoring them to the context of OMA. In order to develop applications of CLDM, we propose a framework that we call locally simulatable proofs for QMA: this provides QMA proofs that can be efficiently verified by probing only k qubits and, furthermore, the reduced density matrix of any k-qubit subsystem of a good witness can be computed in polynomial time, independently of the witness. Within this framework, we show several advances in zero-knowledge in the quantum setting. We show for the first time a commit-and-open computational zero-knowledge proof system for all of QMA, as a quantum analogue of a “sigma” protocol. We then define a Proof of Quantum Knowledge, which guarantees that a prover is effectively in possession of a quantum witness in an interactive proof, and show that our zero-knowledge proof system satisfies this definition. Finally, we show that our proof system can be used to establish that QMA has a quantum non-interactive zero-knowledge proof system in the secret parameter setting.11The full version of this work can be found in https://arxiv.org/abs/1911.07782.
We provide several advances to the understanding of the class of Quantum Merlin-Arthur proof systems (QMA), the quantum analogue of NP. First, we answer a longstanding open question by showing that the Consistency of Local Density Matrices problem is QMA-complete under Karp reductions. We also show for the first time a commit-and-open computational zero-knowledge proof system for all of QMA as a quantum analogue of a sigma protocol. We then define a Proof of Quantum Knowledge, which guarantees that a prover is effectively in possession of a quantum witness in an interactive proof, and show that our zero-knowledge proof system satisfies this definition. Finally, we show that our proof system can be used to establish that QMA has a quantum non-interactive zero-knowledge proof system in the secret parameters setting.
Our main technique consists in developing locally simulatable proofs for all of QMA: this is an encoding of a QMA witness such that it can be efficiently verified by probing only five qubits and, furthermore, the reduced density matrix of any five-qubit subsystem can be computed in polynomial time and is independent of the witness. This construction follows the techniques of Grilo, Slofstra, and Yuen [FOCS 2019].
Distributed ledger technology offers numerous desirable attributes to\napplications in the enterprise context. However, with distributed data and\ndecentralized computation on a shared platform, privacy and confidentiality\nchallenges arise. Any design for an enterprise system needs to carefully cater\nfor use case specific privacy and confidentiality needs. With the goal to\nfacilitate the design of enterprise solutions, this paper aims to provide a\nguide to navigate and aid in decisions around common requirements and\nmechanisms that prevent the leakage of private and confidential information. To\nfurther contextualize key concepts, the design guide is then applied to three\nenterprise DLT protocols: Hyperledger Fabric, Corda, and Quorum.\n
We present a model/executable specification of smart contract execution in Coq. Our formalization allows for inter-contract communication and generalizes existing work by allowing modelling of both depth-first execution blockchains (like Ethereum) and breadth-first execution blockchains (like Tezos). We represent smart contracts programs in Coq's functional language Gallina, enabling easier reasoning about functional correctness of concrete contracts than other approaches. In particular we develop a Congress contract in this style. This contract -- a simplified version of the infamous DAO -- is interesting because of its very dynamic communication pattern with other contracts. We give a high-level partial specification of the Congress's behavior, related to reentrancy, and prove that the Congress satisfies it for all possible smart contract execution orders.
With the development of science and technology, human beings cannot live without electricity. The introduction of smart grid systems brings new ideas to break the shackle of existing electricity systems. This paper proposes a mechanism with data monitoring and sharing capabilities based on the consortium blockchain, realizing comprehensive monitoring of smart devices, and promoting the effective sharing of electrical data in smart grids. When a smart device is out of order, the smart contract connected to it will be triggered, and the users can check the running status through the smart phone. This approach allows nodes in the consortium blockchain to request transactions, using the prepaid payment smart contract with time-lock script to protect the consumer right of request nodes. In addition, we use a (t, n) -threshold secret sharing scheme to realize multiparty sharing of electrical data. Paillier encryption arithmetic is used to guarantee the confidentiality of messages in node transaction.
Shantanu Pal, Tahiry Rabehaja, Ambrose Hill, Michael Hitchens · 5 authors
With the advancement of the Internet of Things (IoT) in recent years, there is a bigger potential to use online services than ever before. The use of the IoT brings numerous opportunities for both service providers and end users, however, it faces critical questions of security and privacy. Toward this, access control is one of the significant security challenges for the IoT, in particular, considering the characteristics of such IoT systems. To develop a secure access control architecture for the IoT, the propagation of access right delegation is a major issue. Many proposals present access control issues for the IoT but given the specific context of access right delegation, it is still in its infancy. This article presents an approach to address such a delegation issue for the IoT using the blockchain technology. We propose a delegation model that employv the critical issues, e.g., the use of nonunique identities, asynchronous and flexible delegation nature of communication for the IoT without the need of a centralized system. The goal of our primitive is to use attributes for validating the identity of an entity instead of relying on a concrete unique identity of an entity. To provide privacy for the attributes, we propose a dual blockchain architecture that moves the attribute storage and access of the public blockchain and onto a secure private blockchain. To demonstrate the feasibility of our proposed approach, we evaluate the system performances using the Ethereum blockchain network.
Wouter Lueks, Bogdan Kulynych, Jules Fasquelle, Simon Le Bail-Collet · 5 authors
Zero-knowledge proofs are an essential building block in many privacy-preserving systems. However, implementing these proofs is tedious and error-prone. In this paper, we present zksk, a well-documented Python library for defining and computing sigma protocols: the most popular class of zero-knowledge proofs. In zksk, proofs compose: programmers can convert smaller proofs into building blocks that then can be combined into bigger proofs. zksk features a modern Python-based domain-specific language. This makes possible to define proofs without learning a new custom language, and to benefit from the rich Python syntax and ecosystem. The library is available at https://github.com/spring-epfl/zksk
We present a new primitive supporting file replication in distributed storage networks (DSNs) called a Public Incompressible Encoding (PIE). PIEs operate in the challenging public DSN setting where files must be encoded and decoded with public randomness-i.e., without encryption-and retention of redundant data must be publicly verifiable. They prevent undetectable data compression, allowing DSNs to use monetary rewards or penalties in incentivizing economically rational servers to properly replicate data. Their definition also precludes critical, demonstrated attacks involving parallelism via ASICs and other custom hardware. Our PIE construction is the first to achieve experimentally validated near-optimal performance-within a factor of 4 of optimal by one metric. It also allows decoding orders of magnitude faster than encoding, unlike other comparable constructions. We achieve this high security and performance using a graph construction called a Dagwood Sandwich Graph (DSaG), built from a novel interleaving of depth-robust graphs and superconcentrators. PIEs' performance makes them appealing for DSNs, such as the proposed Filecoin system and Ethereum data sharding. Conversely, their near-optimality establishes concerning bounds on the practical financial and energy costs of DSNs allowing arbitrary data.
Organized surveillance, especially by governments poses a major challenge to individual privacy, due to the resources governments have at their disposal, and the possibility of overreach. Given the impact of invasive monitoring, in most democratic countries, government surveillance is, in theory, monitored and subject to public oversight to guard against violations. In practice, there is a difficult fine balance between safeguarding individual's privacy rights and not diluting the efficacy of national security investigations, as exemplified by reports on government surveillance programs that have caused public controversy, and have been challenged by civil and privacy rights organizations. Surveillance is generally conducted through a mechanism where federal agencies obtain a warrant from a federal or state judge (e.g., the US FISA court, Supreme Court in Canada) to subpoena a company or service-provider (e.g., Google, Microsoft) for their customers' data. The courts provide annual statistics on the requests (accepted, rejected), while the companies provide annual transparency reports for public auditing. However, in practice, the statistical information provided by the courts and companies is at a very high level, generic, is released after-the-fact, and is inadequate for auditing the operations. Often this is attributed to the lack of scalable mechanisms for reporting and transparent auditing. In this paper, we present SAMPL, a novel auditing framework which leverages cryptographic mechanisms, such as zero knowledge proofs, Pedersen commitments, Merkle trees, and public ledgers to create a scalable mechanism for auditing electronic surveillance processes involving multiple actors. SAMPL is the first framework that can identify the actors (e.g., agencies and companies) that violate the purview of the court orders. We experimentally demonstrate the scalability for SAMPL for handling concurrent monitoring processes without undermining their secrecy and auditability.
Iddo Bentov, Yan Ji, Fan Zhang, Lorenz Breidenbach · 6 authors
We propose Tesseract, a secure real-time cryptocurrency exchange service. Existing centralized exchange designs are vulnerable to theft of funds, while decentralized exchanges cannot offer real-time cross-chain trades. All currently deployed exchanges are also vulnerable to frontrunning attacks. Tesseract overcomes these flaws and achieves a best-of-both-worlds design by using a trusted execution environment. The task of committing the recent trade data to independent cryptocurrency systems presents an all-or-nothing fairness problem, to which we present ideal theoretical solutions, as well as practical solutions. Tesseract supports not only real-time cross-chain cryptocurrency trades, but also secure tokenization of assets pegged to cryptocurrencies. For instance, Tesseract-tokenized bitcoins can circulate on the Ethereum blockchain for use in smart contracts. We provide a demo implementation of Tesseract that supports Bitcoin, Ethereum, and similar cryptocurrencies.
Zero-knowledge arguments have become practical, and widely used, especially in the world of Blockchain, for example in Zcash. This work revisits zero-knowledge proofs in the discrete logarithm setting. First, we identify and carve out basic techniques (partly being used implicitly before) to optimise proofs in this setting. In particular, the linear combination of protocols is a useful tool to obtain zero-knowledge and/or reduce communication. With these techniques, we are able to devise zero-knowledge variants of the logarithmic communication arguments by Bootle et al. (EUROCRYPT '16) and Bünz et al. (S&P '18) thereby introducing almost no overhead. We then construct a conceptually simple commit-and-prove argument for satisfiability of a set of quadratic equations. Unlike previous work, we are not restricted to rank 1 constraint systems (R1CS). This is, to the best of our knowledge, the first work demonstrating that general quadratic constraints, not just R1CS, are a natural relation in the dlog (or ideal linear commitment) setting. This enables new possibilities for optimisation, as, eg., any degree n2 polynomial f(X) can now be "evaluated" with at most 2n quadratic constraints. Our protocols are modular. We easily construct an efficient, logarithmic size shuffle proof, which can be used in electronic voting. Additionally, we take a closer look at quantitative security measures, eg. the efficiency of an extractor. We formalise short-circuit extraction, which allows us to give tighter bounds on the efficiency of an extractor.
The concept of a blockchain was invented by Satoshi Nakamoto to maintain a distributed ledger. In addition to its security, important performance measures of a blockchain protocol are its transaction throughput and confirmation latency. In a decentralized setting, these measures are limited by two underlying physical network attributes: communication capacity and speed-of-light propagation delay. In this work we introduce Prism, a new proof-of-work blockchain protocol, which can achieve 1) security against up to 50% adversarial hashing power; 2) optimal throughput up to the capacity C of the network; 3) confirmation latency for honest transactions proportional to the propagation delay D, with confirmation error probability exponentially small in the bandwidth-delay product CD; 4) eventual total ordering of all transactions. Our approach to the design of this protocol is based on deconstructing Nakamoto's blockchain into its basic functionalities and systematically scaling up these functionalities to approach their physical limits.
Blockchain is the technology that has attracted enormous interest recently as it provides security and privacy through immutable distributed ledger. It is the backbone of the most popular cryptocurrency, bitcoin. Due to its robust consensus mechanism and tamper proof data storage, it is widely adopted in the applications where trust is given utmost importance.Homomorphic Encryption algorithms can be used to operate on the data that is encrypted without the knowledge of private key. Operations can be performed on encrypted data without decrypting the data. Only client knows about the private key. These two technologies can be used to securely transfer and store data in the cloud systems.In this paper we propose how this blockchain technology and homomorphic encryption can be used to build reliable, tamper-proof and efficient electronic voting system. An electronic voting system should be secure, and itshould not allow duplicate votes and be fully tamper proof, while protecting the privacy of the voters. In this work, we have designed, implemented and tested an electronic voting application and providing hashing for votes and stored in blockchaincloud.If data in database is lost, then it can be retrieved from blockchain cloud.
There has been a massive growth of Internet of Things (IoT) applications recently for both personal and organization use cases. But an IoT network is vulnerable to many privacy and security concerns. While some researchers have tried to define different access control models for IoT and tried to use blockchain in some cases, the solutions presented to date lacks a flexible and robust access control model that can be used for complex organization and cross-organization resource access scenarios and lacks the scalability and performance needed for IoT. This paper introduces a novel entitlement-based access control model that provides an efficient and secure way to delegate resource access rights to any entity. The solution uses service-oriented approach and a combination of public blockchain (with smart contracts) and local off-chain data for entitlements management and control. To analyze the proposed architecture, a large-scale cross-organization IoT scenario is taken into consideration and some qualitative evaluations are presented while implementation with Ethereum blockchain and smart contracts are currently in progress.
Recently, crowd sensing has been intensively researched, due to the rapid growth of sensor-integrated mobile devices. Crowd sensing is a participatory sensing service where a server gathers and analyzes sensing data submitted from mobile devices of lots of users. In crowd sensing, the user's anonymity is desired, since the server gathers sensitive data from the participants including their GPS locations and moving path. However, the anonymous data submission may compromise the trust of the sensing data, because anonymous users may submit inappropriate sensing data, but they cannot be traced. Therefore, as the system to achieve both anonymity and trust in crowd sensing, ARTSense has been proposed. In the system, the trust of the sensing data is assessed on the sensed environment, other users' sensing, and the reputation of the user, and furthermore the reputation of the user is anonymously managed on the feedback from the trust assessment for the data. However, the anonymous reputation system of ARTSense has the efficiency problem, i.e., the user needs to wait a random time after the data submission phase before requesting the reputation update, which causes the communication delay. In this paper, we propose an efficient anonymous reputation system for crowd sensing, which can be integrated to the trust assessment in ARTSense. In the proposed system, during the data submission, the reputation update is anonymously completed. This is because the server does not manage the reputation of each user, but each user manages his/her reputation in the user side, where the the validity of the reputation is ensured by a certificate and anonymously checked by zero-knowledge proofs. Therefore, the proposed system achieves the better efficiency with no delay.
Payment channel with penalizing double-spending has been widely applied in cryptocurrencies for achieving fast payment. However, current payment channel solutions suffer at least one of the following problems: 1) large overheads and communication costs are incurred to thwart double-spending; 2) payees must be defined before building payment channels; 3) a single payment channel does not support multiple payees; 4) no formally theoretical proofs are provided for the security of payment channels (as an open problem mentioned in CCS'15). In this paper, we fill these gaps by introducing a new fast payment protocol named super payment channel. We provide detailed construction based on digital signatures and accountable assertions with formal security proofs. We also implement our proposed protocol in different circumstances and demonstrate that our proposed protocol incurs a small overhead compared to ordinary Bitcoin transactions.
Open access
Blockchain Technology Applications and Security
Cryptography and Data Security
Advanced Steganography and Watermarking Techniques