Loi Luu, Yaron Velner, Jason Teutsch, Prateek Saxena
Cryptocurrencies such as Bitcoin and Ethereum are operated by a handful of mining pools. Nearly 95% of Bitcoin's and 80% of Ethereum's mining power resides with less than ten and six mining pools respectively. Although miners benefit from low payout variance in pooled mining, centralized mining pools require members to trust that pool operators will remunerate them fairly. Furthermore, centralized pools pose the risk of transaction censorship from pool operators, and open up possibilities for collusion between pools for perpetrating severe attacks.
In this work, we propose SMARTPOOL, a novel protocol design for a decentralized mining pool. Our protocol shows how one can leverage smart contracts, autonomous blockchain programs, to decentralize cryptocurrency mining. SMARTPOOL gives transaction selection control back to miners while yielding low-variance payouts. SMARTPOOL incurs mining fees lower than centralized mining pools and is designed to scale to a large number of miners. We implemented and deployed a robust SMARTPOOL implementation on the Ethereum and Ethereum Classic networks. To date, our deployed pools have handled a peak hashrate of 30 GHs from Ethereum miners, resulting in 105 blocks, costing miners a mere 0:6% of block rewards in transaction fees.
Blockchain Technology Applications and Security
Cryptography and Data Security
Advanced Steganography and Watermarking Techniques
We present a zero-knowledge argument for NP with low communication complexity, low concrete cost for both the prover and the verifier, and no trusted setup, based on standard cryptographic assumptions. Communication is proportional to d log G (for d the depth and G the width of the verifying circuit) plus the square root of the witness size. When applied to batched or data-parallel statements, the prover's runtime is linear and the verifier's is sub-linear in the verifying circuit size, both with good constants. In addition, witness-related communication can be reduced, at the cost of increased verifier runtime, by leveraging a new commitment scheme for multilinear polynomials, which may be of independent interest. These properties represent a new point in the tradeoffs among setup, complexity assumptions, proof size, and computational cost. We apply the Fiat-Shamir heuristic to this argument to produce a zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) in the random oracle model, based on the discrete log assumption, which we call Hyrax. We implement Hyrax and evaluate it against five state-of-the-art baseline systems. Our evaluation shows that, even for modest problem sizes, Hyrax gives smaller proofs than all but the most computationally costly baseline, and that its prover and verifier are each faster than three of the five baselines.
The Fiat-Shamir construction (Crypto 1986) is an efficient transformation in the random oracle model for creating non-interactive proof systems and signatures from sigma-protocols. In classical cryptography, Fiat-Shamir is a zero-knowledge proof of knowledge assuming that the underlying sigma-protocol has the zero-knowledge and special soundness properties. Unfortunately, Ambainis, Rosmanis, and Unruh (FOCS 2014) ruled out non-relativizing proofs under those conditions in the quantum setting.
Youngho Yoo, Reza Azarderakhsh, Amir Jalali, David Jao · 5 authors
We present the first general-purpose digital signature scheme \nbased on supersingular elliptic curve isogenies secure against quantum \nadversaries in the quantum random oracle model with small key sizes. \nThis scheme is an application of Unruh’s construction of non-interactive \nzero-knowledge proofs to an interactive zero-knowledge proof proposed \nby De Feo, Jao, and Plut. We implement our proposed scheme on an x86- \n64 PC platform as well as an ARM-powered device. We exploit the stateof-the-art \ntechniques to speed up the computations for general C and \nassembly. Finally, we provide timing results for real world applications.
We describe a new succinct zero-knowledge argument protocol with the following properties. The prover commits to a large data-set M, and can thereafter prove many statements of the form \(\exists w : \mathcal {R}_i(M,w)=1\), where \(\mathcal {R}_i\) is a public function. The protocol is succinct in the sense that the cost for the verifier (in computation & communication) does not depend on |M|, not even in any initialization phase In each proof, the computation/communication cost for both the prover and the verifier is proportional only to the running time of an oblivious RAM program implementing \(\mathcal {R}_i\) (in particular, this can be sublinear in |M|). The only costs that scale with |M| are the computational costs of the prover in a one-time initial commitment to M.
The thesis investigates how a blockchain can be used to build a decentralised public key infrastructure for the web, by proposing a custom federation blockchain relying on honest majority. Our main contribution is the design of a Proof of Stake protocol based on a stake tree, which builds upon an idea called follow-the-satoshi used in previous papers. Digital identities are stored in an authenticated self-balancing tree maintained by blockchain nodes. Our back-of-the-envelope calculations, based on the size of the domain name system, show that the block size must be set to at least 5.2 MB, while each blockchain node with a one-month transaction history would need to store about 243 GB. Thin clients would have to synchronise about 13.6 MB of block headers per year, and download an additional 3.7 KB of proof data for every leaf certificate which is to be checked.
Fan Zhang, Ittay Eyal, Robert Escriva, Ari Juels · 5 authors
Blockchains show promise as potential infrastructure for financial transaction systems. The security of blockchains today, however, relies critically on Proof-of-Work (PoW), which forces participants to waste computational resources.
We present REM (Resource-Efficient Mining), a new blockchain mining framework that uses trusted hardware (Intel SGX). REM achieves security guarantees similar to PoW, but leverages the partially decentralized trust model inherent in SGX to achieve a fraction of the waste of PoW. Its key idea, Proof-of-Useful-Work (PoUW), involves miners providing trustworthy reporting on CPU cycles they devote to inherently useful workloads. REM flexibly allows any entity to create a useful workload. REM ensures the trustworthiness of these workloads by means of a novel scheme of hierarchical attestations that may be of independent interest.
To address the risk of compromised SGX CPUs, we develop a statistics-based formal security framework, also relevant to other trusted-hardware-based approaches such as Intel's Proof of Elapsed Time (PoET). We show through economic analysis that REM achieves less waste than PoET and variant schemes.
We implement REM and, as an example application, swap it into the consensus layer of Bitcoin core. The result is the first full implementation of an SGX-based blockchain. We experiment with four example applications as useful workloads for our implementation of REM, and report a computational overhead of 5-15%.
We present Strain, a new auction protocol running on top of blockchains and guaranteeing bid confidentiality against fully-malicious parties. As our goal is efficiency and low blockchain latency, we abstain from using traditional, highly interactive MPC primitives such as secret shares. We focus on a slightly weaker adversary model than MPC which allows Strain to achieve constant latency in both the number of parties and the bid length. The main idea behind Strain is a new maliciously-secure two-party comparison mechanism executed between any pair of bids in parallel. Using zero-knowledge proofs, Strain broadcasts the outcome of comparisons on the blockchain in a way that all parties can verify each outcome. Strain’s latency is not only asymptotically optimal, but also efficient in practice, requiring a total of just 4 blocks of the underlying blockchain. Strain provides typical auction security requirements such as non-retractable bids against fully-malicious adversaries.
A blockchain is a distributed ledger for recording transactions, maintained by many nodes without central authority through a distributed cryptographic protocol. All nodes validate the information to be appended to the blockchain, and a consensus protocol ensures that the nodes agree on a unique order in which entries are appended. Consensus protocols for tolerating Byzantine faults have received renewed attention because they also address blockchain systems. This work discusses the process of assessing and gaining confidence in the resilience of a consensus protocols exposed to faults and adversarial nodes. We advocate to follow the established practice in cryptography and computer security, relying on public reviews, detailed models, and formal proofs; the designers of several practical systems appear to be unaware of this. Moreover, we review the consensus protocols in some prominent permissioned blockchain platforms with respect to their fault models and resilience against attacks.
Most modern electronic devices can produce a random number. However, it is difficult to see how a group of mutually distrusting entities can have confidence in any such hardware-produced stream of random numbers, since the producer could control the output to their gain. In this work, we use public and immutable cryptocurrency smart contracts, along with a set of potentially malicious randomness providers, to produce a trustworthy stream of timestamped public random numbers. Our contract eliminates the ability of a producer to predict or control the generated random numbers, including the stored history of random numbers. We consider and mitigate the threat of collusion between the randomness providers and miners in a second, more complex contract.
Open access
2 source records
Cryptography and Data Security
Blockchain Technology Applications and Security
Advanced Steganography and Watermarking Techniques
Iddo Bentov, Pavel Hubáček, Tal Moran, Asaf Nadler
We propose Meshcash, a protocol for implementing a permissionless ledger (blockchain) via proofs of work, suitable for use as the underlying consensus mechanism of a cryptocurrency. Unlike most existing proof-of-work based consensus protocols, Meshcash does not rely on leader-election (e.g., the single miner who managed to extend the longest chain). Rather, we use ideas from traditional (permissioned) Byzantine agreement protocols in a novel way to guarantee convergence to a consensus from any starting state. Our construction combines a local “hare” protocol that guarantees fast consensus on recent blocks (but doesn’t, by itself, imply irreversibility) with a global “tortoise” protocol that guarantees irreversibility. Our global protocol also allows the ledger to “self-heal” from arbitrary violations of the security assumptions, reconverging to consensus after the assumptions hold again.
Conventional public-key infrastructure (PKI) designs using certificate authorities and web-of-trust are not optimal and have security flaws. The properties afforded by the Bitcoin blockchain are a natural solution to some of the problems with PKI - in particular, certificate transparency and elimination of single points-offailure. Proposed blockchain-based PKI designs are built as public ledgers linking identity with public key, providing no privacy. We consider cases requiring privacy-aware PKIs, which do not link identity with public key. We show that blockchain technology can be used to construct a privacy-aware PKI while eliminating some of the problems of conventional PKI, and present PB-PKI, a privacy-aware blockchain-based PKI.