<div class="csl-bib-body">
<div class="csl-entry">Chatterjee, D., Banerjee, P., & Mazumdar, S. (2023). <i>Chrisimos: A useful Proof-of-Work for finding Minimal Dominating Set of a graph</i>. arXiv. https://doi.org/10.34726/5301</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/190685
-
dc.identifier.uri
https://doi.org/10.34726/5301
-
dc.description
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)
-
dc.description.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
dc.description.sponsorship
Europäischer Forschungsrat (ERC)
-
dc.description.sponsorship
FWF - Österr. Wissenschaftsfonds
-
dc.description.sponsorship
Christian Doppler Forschungsgesells
-
dc.description.sponsorship
Wirtschaftsagentur Wien Ein Fonds der Stadt Wien
-
dc.description.sponsorship
Wirtschaftsagentur Wien Ein Fonds der Stadt Wien
-
dc.language.iso
en
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
Blockchain
en
dc.subject
Useful Proof-of-Work
en
dc.subject
Graphs
en
dc.subject
Dominating set
en
dc.subject
NP-complete problem
en
dc.title
Chrisimos: A useful Proof-of-Work for finding Minimal Dominating Set of a graph
en
dc.type
Preprint
en
dc.type
Preprint
de
dc.rights.license
Creative Commons Namensnennung 4.0 International
de
dc.rights.license
Creative Commons Attribution 4.0 International
en
dc.identifier.doi
10.34726/5301
-
dc.identifier.arxiv
2308.04407
-
dc.contributor.affiliation
Birla Institute of Technology and Science, Pilani - Goa Campus, India
-
dc.contributor.affiliation
Indian Statistical Institute, India
-
dc.relation.grantno
771527
-
dc.relation.grantno
P31621-N38
-
dc.relation.grantno
CDL-BOT
-
dc.relation.grantno
ViSP
-
dc.relation.grantno
1360366
-
tuw.project.title
Foundations and Tools for Client-Side Web Security
-
tuw.project.title
Cryptographic Foundations for Future-proof Internet Security
-
tuw.project.title
Blockchaintechnologien für das Internet der Dinge
-
tuw.project.title
Forschungszentrum für Cybersicherheit und Datenschutz in Wien
-
tuw.project.title
Vorbereitung für die Einreichung eines Kompetenzzentrums Comet K1 - Arbeitstitel Minerva
-
tuw.researchTopic.id
C5
-
tuw.researchTopic.name
Computer Science Foundations
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-06 - Forschungsbereich Security and Privacy
-
tuw.publisher.doi
10.48550/arXiv.2308.04407
-
dc.identifier.libraryid
AC17205277
-
dc.description.numberOfPages
20
-
tuw.author.orcid
0000-0003-4335-5541
-
tuw.author.orcid
0000-0001-6142-9378
-
tuw.author.orcid
0000-0002-3089-2535
-
dc.rights.identifier
CC BY 4.0
de
dc.rights.identifier
CC BY 4.0
en
dc.description.sponsorshipexternal
Austrian Science Fund (FWF)
-
dc.description.sponsorshipexternal
BITS Pilani, KK Birla Goa Campus, Goa, India
-
dc.relation.grantnoexternal
W1255
-
dc.relation.grantnoexternal
FR/SCM/11-Apr-2023/CSIS (OPERA)
-
tuw.publisher.server
arXiv
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.mimetype
application/pdf
-
item.grantfulltext
open
-
item.fulltext
with Fulltext
-
item.openairecristype
http://purl.org/coar/resource_type/c_816b
-
item.openaccessfulltext
Open Access
-
item.cerifentitytype
Publications
-
item.languageiso639-1
en
-
item.openairetype
preprint
-
crisitem.author.dept
Birla Institute of Technology and Science, Pilani - Goa Campus
