Chatterjee, D., Banerjee, P., & Subhra Mazumdar. (2023). Chrisimos: A useful Proof-of-Work for finding Minimal Dominating Set of a graph. arXiv. https://doi.org/10.34726/5301
Blockchain; Useful Proof-of-Work; Graphs; Dominating set; NP-complete problem
en
Abstract:
Hash-based Proof-of-Work (PoW) used in the Bitcoin Blockchain leads to high energy consumption and resource wastage. In this paper, we aim to re-purpose the energy by replacing the hash function with real-life problems having commercial utility. We propose Chrisimos, a useful Proof-of-Work where miners are required to find a minimal dominating set for real-life graph instances. A miner who is able to output the smallest dominating set for the given graph within the block interval time wins the mining game. We also propose a new chain selection rule that ensures the security of the scheme. Thus our protocol also realizes a decentralized minimal dominating set solver for any graph instance. We provide formal proof of correctness and show via experimental results that the block interval time is within feasible bounds of hash-based PoW.
en
Project title:
Foundations and Tools for Client-Side Web Security: 771527 (Europäischer Forschungsrat (ERC)) Cryptographic Foundations for Future-proof Internet Security: P31621-N38 (FWF - Österr. Wissenschaftsfonds) Blockchaintechnologien für das Internet der Dinge: CDL-BOT (Christian Doppler Forschungsgesells) Forschungszentrum für Cybersicherheit und Datenschutz in Wien: ViSP (Wirtschaftsagentur Wien Ein Fonds der Stadt Wien) Vorbereitung für die Einreichung eines Kompetenzzentrums Comet K1 - Arbeitstitel Minerva: 1360366 (Wirtschaftsagentur Wien Ein Fonds der Stadt Wien)
-
Project (external):
Austrian Science Fund (FWF) BITS Pilani, KK Birla Goa Campus, Goa, India
-
Project ID:
W1255 FR/SCM/11-Apr-2023/CSIS (OPERA)
-
Additional information:
The paper got accepted in The International Symposium on Intelligent and Trustworthy Computing, Communications, and Networking (ITCCN-2023) held in conjunction with the 22nd IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom-2023)
CC BY 4.0
