skip to main content


Title: Proof-of-Useful-Randomness: Mitigating the Energy Waste in Blockchain Proof-of-Work
Proof-of-Work (PoW) is one of the fundamental and widely-used consensus algorithms in blockchains. In PoW, nodes compete to receive the mining reward by trying to be the first to solve a puzzle. Despite its fairness and wide availability, traditional PoW incurs extreme computational and energy waste over the blockchain. This waste is considered to be one of the biggest problems in PoW-based blockchains and cryptocurrencies. In this work, we propose a new useful PoW called Proof-of-Useful-Randomness (PoUR) that mitigates the energy waste by incorporating pre-computed (disclosable) randomness into the PoW. The key idea is to inject special randomness into puzzles via algebraic commitments that can be stored and later disclosed. Unlike the traditional wasteful PoWs, our approach enables pre-computed commitments to be utilized by a vast array of public-key cryptography methods that require offline-online processing (e.g., digital signature, key exchange, zero-knowledge protocol). Moreover, our PoW preserves the desirable properties of the traditional PoW and therefore does not require a substantial alteration in the underlying protocol. We showed the security of our PoW, and then fully implemented it to validate its significant energy-saving capabilities.  more » « less
Award ID(s):
1917627
NSF-PAR ID:
10312087
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
In Proceedings of the 18th International Conference on Security and Cryptography (SECRYPT 2021)
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Proof of Work (PoW) protocols, originally proposed to circumvent DoS and email spam attacks, are now at the heart of the majority of recent cryptocurrencies. Current popular PoW protocols are based on hash puzzles. These puzzles are solved via a brute force search for a hash output with particular properties, such as a certain number of leading zeros. By considering the hash as a random function, and fixing a priori a sufficiently large search space, Grover’s search algorithm gives an asymptotic quadratic advantage to quantum machines over classical machines. In this paper, as a step towards a fuller understanding of post-quantum blockchains, we propose a PoW protocol for which quantum machines have a smaller asymptotic advantage. Specifically, for a lattice of rank n sampled from a particular class, our protocol provides as the PoW an instance of the Hermite Shortest Vector Problem (Hermite-SVP) in the Euclidean norm, to a small approximation factor. Asymptotically, the best known classical and quantum algorithms that directly solve SVP type problems are heuristic lattice sieves, which run in time 20.292n+o(n) and 2 0.265n+o(n) respectively. We discuss recent advances in SVP type problem solvers and give examples of where the impetus provided by a lattice-based PoW would help explore often complex optimization spaces. 
    more » « less
  2. We propose a proof of work protocol that computes the discrete logarithm of an element in a cyclic group. Individual provers generating proofs of work perform a distributed version of the Pollard rho algorithm. Such a protocol could capture the computational power expended to construct proof-of-work-based blockchains for a more useful purpose, as well as incentivize advances in hardware, software, or algorithms for an important cryptographic problem. We describe our proposed construction and elaborate on challenges and potential trade-offs that arise in designing a practical proof of work. 
    more » « less
  3. Blockchain technology has been recognized as a promising solution to enhance the security and privacy of Internet of Things (IoT) and Edge Computing scenarios. Taking advantage of the Proof-of-Work (PoW) consensus protocol, which solves a computation intensive hashing puzzle, Blockchain ensures the security of the system by establishing a digital ledger. However, the computation intensive PoW favors members possessing more computing power. In the IoT paradigm, fairness in the highly heterogeneous network edge environments must consider devices with various constraints on computation power. Inspired by the advanced features of Digital Twins (DT), an emerging concept that mirrors the lifespan and operational characteristics of physical objects, we propose a novel Miner Twins (MinT) architecture to enable a fair PoW consensus mechanism for blockchains in IoT environments. MinT adopts an edge-fog-cloud hierarchy. All physical miners of the blockchain are deployed as microservices on distributed edge devices, while fog/cloud servers maintain digital twins that periodically update miners’ running status. By timely monitoring of a miner’s footprint that is mirrored by twins, a lightweight Singular Spectrum Analysis (SSA)-based detection achieves the identification of individual misbehaved miners that violate fair mining. Moreover, we also design a novel Proof-of-Behavior (PoB) consensus algorithm to detect dishonest miners that collude to control a fair mining network. A preliminary study is conducted on a proof-of-concept prototype implementation, and experimental evaluation shows the feasibility and effectiveness of the proposed MinT scheme under a distributed byzantine network environment. 
    more » « less
  4. In this work, we propose a blockchain-based solution for securing robot-to-robot communication for a task with a high socioeconomic impact—information gathering. The objective of the robots is to gather maximal information about an unknown ambient phenomenon such as soil humidity distribution in a field. More specifically, we use the proof-of-work (PoW) consensus protocol for the robots to securely coordinate while rejecting tampered data injected by a malicious entity. As the blockchain-based PoW protocol has a large energy footprint, we next employ an algorithmically-engineered energy-efficient version of PoW. Results show that our proposed energy-efficient PoW-based protocol can reduce energy consumption by 14% while easily scaling up to 10 robots.

     
    more » « less
  5. null (Ed.)
    The current centralized model of the electricity market is not efficient in performing distributed energy transactions required for the transactive smart grid. One of the prominent solutions to this issue is to integrate blockchain technologies, which promise transparent, tamper-proof, and secure transaction systems specifically suitable for the decentralized and distributed energy markets. Blockchain has already been shown to successfully operate in a microgrid peer-to-peer (P2P) energy market. The prime determinant of different blockchain implementations is the consensus algorithm they use to reach consensus on which blocks/transactions to accept as valid in a distributed environment. Although different blockchain implementations have been proposed independently for P2P energy market in the microgrid, quantitative experimental analyses and comparison of the consensus algorithms that the different blockchains may use for energy markets, has not been studied. Identifying the right consensus algorithm to use is essential for scalability and operation of the energy market. To this end, we evaluate three popular consensus algorithms: (i) proof of work (PoW), (ii) proof of authority (PoA), and (iii) Istanbul Byzantine fault tolerance (IBFT), running them on a network of nodes set up using a network of docker nodes to form a microgrid energy market. Using a series of double auctions, we assess each algorithm's viability using different metrics, such as time to reach consensus and scalability. The results indicate that PoA is the most efficient and scalable consensus algorithm to hold double auctions in the smart grid. We also identified the minimum hardware specification necessary for devices such as smart meters, which may run these consensus algorithms 
    more » « less