Analysis of Variance of Graph-Clique Mining for Scalable Proof of Work

Hiroaki Anada, Tomohiro Matsushima, Chunhua Su*, Weizhi Meng, Junpei Kawamoto, Samiran Bag, Kouichi Sakurai

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Recently, Bitcoin is becoming one of the most popular decentralized cryptographic currency technologies, and Bitcoin mining is a process of adding transaction records to Bitcoin’s public ledger of past transactions or blockchain. To obtain a bitcoin, the mining process involves compiling recent transactions into blocks and trying to solve a computationally difficult puzzle, e.g., proof of work puzzle. A proof of work allows miners the ability to quantify how much work a given proof contains. Basically, the required time for mining is decided in advance, but problems will occur if the value is large for dispersion. In this paper, we first accept that the required time between consecutive blocks follows the exponential distribution. That is, the variance is stable as long as the expected time is fixed. Then, we focus on the graph clique mining technique proposed by the literature, like Tromp (BITCOIN 2015) and Bag-Ruj-Sakurai (Inscrypt 2015), which is based on a computational difficulty problem of searching cliques of undirected graphs, where a clique is a subset of vertices. In particular, when the clique size is two, graph clique mining can be used to gain Bitcoins. The previous work also claimed that if the clique size is parameterized and increased, even if the expected time is fixed, the variance would not be stable. However, no qualitative or quantitative results were given to support their claim. Motivated by this issue, in this work, we propose a simple search algorithm for graph cliques mining, and perform a small scale evaluation on Bitcoin and Graph cliques’s solo mining to investigate the variance issue.
Original languageEnglish
Title of host publicationInformation Security and Cryptology. Inscrypt 2018
Volume11449
PublisherSpringer
Publication date2019
Pages101-114
ISBN (Print)978-3-030-14233-9
DOIs
Publication statusPublished - 2019
Event14th International Conference on Information Security and Cryptology - Fuzhou Sandi Ramada Plaza Orlando Hotel, Fuzhou, China
Duration: 14 Dec 201817 Dec 2018
http://xxhb.fjnu.edu.cn/inscrypt2018/

Conference

Conference14th International Conference on Information Security and Cryptology
LocationFuzhou Sandi Ramada Plaza Orlando Hotel
CountryChina
CityFuzhou
Period14/12/201817/12/2018
Internet address
SeriesLecture Notes in Computer Science
Volume11449
ISSN0302-9743

Keywords

  • Blockchain
  • Proof of work
  • Graph-Clique Mining
  • Bitcoin
  • Mining competition

Cite this

Anada, H., Matsushima, T., Su, C., Meng, W., Kawamoto, J., Bag, S., & Sakurai, K. (2019). Analysis of Variance of Graph-Clique Mining for Scalable Proof of Work. In Information Security and Cryptology. Inscrypt 2018 (Vol. 11449, pp. 101-114). Springer. Lecture Notes in Computer Science, Vol.. 11449 https://doi.org/10.1007/978-3-030-14234-6_6
Anada, Hiroaki ; Matsushima, Tomohiro ; Su, Chunhua ; Meng, Weizhi ; Kawamoto, Junpei ; Bag, Samiran ; Sakurai, Kouichi. / Analysis of Variance of Graph-Clique Mining for Scalable Proof of Work. Information Security and Cryptology. Inscrypt 2018. Vol. 11449 Springer, 2019. pp. 101-114 (Lecture Notes in Computer Science, Vol. 11449).
@inproceedings{dca7281e00fa499bbcd5a572a293ac2a,
title = "Analysis of Variance of Graph-Clique Mining for Scalable Proof of Work",
abstract = "Recently, Bitcoin is becoming one of the most popular decentralized cryptographic currency technologies, and Bitcoin mining is a process of adding transaction records to Bitcoin’s public ledger of past transactions or blockchain. To obtain a bitcoin, the mining process involves compiling recent transactions into blocks and trying to solve a computationally difficult puzzle, e.g., proof of work puzzle. A proof of work allows miners the ability to quantify how much work a given proof contains. Basically, the required time for mining is decided in advance, but problems will occur if the value is large for dispersion. In this paper, we first accept that the required time between consecutive blocks follows the exponential distribution. That is, the variance is stable as long as the expected time is fixed. Then, we focus on the graph clique mining technique proposed by the literature, like Tromp (BITCOIN 2015) and Bag-Ruj-Sakurai (Inscrypt 2015), which is based on a computational difficulty problem of searching cliques of undirected graphs, where a clique is a subset of vertices. In particular, when the clique size is two, graph clique mining can be used to gain Bitcoins. The previous work also claimed that if the clique size is parameterized and increased, even if the expected time is fixed, the variance would not be stable. However, no qualitative or quantitative results were given to support their claim. Motivated by this issue, in this work, we propose a simple search algorithm for graph cliques mining, and perform a small scale evaluation on Bitcoin and Graph cliques’s solo mining to investigate the variance issue.",
keywords = "Blockchain, Proof of work, Graph-Clique Mining, Bitcoin, Mining competition",
author = "Hiroaki Anada and Tomohiro Matsushima and Chunhua Su and Weizhi Meng and Junpei Kawamoto and Samiran Bag and Kouichi Sakurai",
year = "2019",
doi = "10.1007/978-3-030-14234-6_6",
language = "English",
isbn = "978-3-030-14233-9",
volume = "11449",
pages = "101--114",
booktitle = "Information Security and Cryptology. Inscrypt 2018",
publisher = "Springer",

}

Anada, H, Matsushima, T, Su, C, Meng, W, Kawamoto, J, Bag, S & Sakurai, K 2019, Analysis of Variance of Graph-Clique Mining for Scalable Proof of Work. in Information Security and Cryptology. Inscrypt 2018. vol. 11449, Springer, Lecture Notes in Computer Science, vol. 11449, pp. 101-114, 14th International Conference on Information Security and Cryptology, Fuzhou, China, 14/12/2018. https://doi.org/10.1007/978-3-030-14234-6_6

Analysis of Variance of Graph-Clique Mining for Scalable Proof of Work. / Anada, Hiroaki; Matsushima, Tomohiro; Su, Chunhua; Meng, Weizhi; Kawamoto, Junpei; Bag, Samiran; Sakurai, Kouichi.

Information Security and Cryptology. Inscrypt 2018. Vol. 11449 Springer, 2019. p. 101-114 (Lecture Notes in Computer Science, Vol. 11449).

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

TY - GEN

T1 - Analysis of Variance of Graph-Clique Mining for Scalable Proof of Work

AU - Anada, Hiroaki

AU - Matsushima, Tomohiro

AU - Su, Chunhua

AU - Meng, Weizhi

AU - Kawamoto, Junpei

AU - Bag, Samiran

AU - Sakurai, Kouichi

PY - 2019

Y1 - 2019

N2 - Recently, Bitcoin is becoming one of the most popular decentralized cryptographic currency technologies, and Bitcoin mining is a process of adding transaction records to Bitcoin’s public ledger of past transactions or blockchain. To obtain a bitcoin, the mining process involves compiling recent transactions into blocks and trying to solve a computationally difficult puzzle, e.g., proof of work puzzle. A proof of work allows miners the ability to quantify how much work a given proof contains. Basically, the required time for mining is decided in advance, but problems will occur if the value is large for dispersion. In this paper, we first accept that the required time between consecutive blocks follows the exponential distribution. That is, the variance is stable as long as the expected time is fixed. Then, we focus on the graph clique mining technique proposed by the literature, like Tromp (BITCOIN 2015) and Bag-Ruj-Sakurai (Inscrypt 2015), which is based on a computational difficulty problem of searching cliques of undirected graphs, where a clique is a subset of vertices. In particular, when the clique size is two, graph clique mining can be used to gain Bitcoins. The previous work also claimed that if the clique size is parameterized and increased, even if the expected time is fixed, the variance would not be stable. However, no qualitative or quantitative results were given to support their claim. Motivated by this issue, in this work, we propose a simple search algorithm for graph cliques mining, and perform a small scale evaluation on Bitcoin and Graph cliques’s solo mining to investigate the variance issue.

AB - Recently, Bitcoin is becoming one of the most popular decentralized cryptographic currency technologies, and Bitcoin mining is a process of adding transaction records to Bitcoin’s public ledger of past transactions or blockchain. To obtain a bitcoin, the mining process involves compiling recent transactions into blocks and trying to solve a computationally difficult puzzle, e.g., proof of work puzzle. A proof of work allows miners the ability to quantify how much work a given proof contains. Basically, the required time for mining is decided in advance, but problems will occur if the value is large for dispersion. In this paper, we first accept that the required time between consecutive blocks follows the exponential distribution. That is, the variance is stable as long as the expected time is fixed. Then, we focus on the graph clique mining technique proposed by the literature, like Tromp (BITCOIN 2015) and Bag-Ruj-Sakurai (Inscrypt 2015), which is based on a computational difficulty problem of searching cliques of undirected graphs, where a clique is a subset of vertices. In particular, when the clique size is two, graph clique mining can be used to gain Bitcoins. The previous work also claimed that if the clique size is parameterized and increased, even if the expected time is fixed, the variance would not be stable. However, no qualitative or quantitative results were given to support their claim. Motivated by this issue, in this work, we propose a simple search algorithm for graph cliques mining, and perform a small scale evaluation on Bitcoin and Graph cliques’s solo mining to investigate the variance issue.

KW - Blockchain

KW - Proof of work

KW - Graph-Clique Mining

KW - Bitcoin

KW - Mining competition

U2 - 10.1007/978-3-030-14234-6_6

DO - 10.1007/978-3-030-14234-6_6

M3 - Article in proceedings

SN - 978-3-030-14233-9

VL - 11449

SP - 101

EP - 114

BT - Information Security and Cryptology. Inscrypt 2018

PB - Springer

ER -

Anada H, Matsushima T, Su C, Meng W, Kawamoto J, Bag S et al. Analysis of Variance of Graph-Clique Mining for Scalable Proof of Work. In Information Security and Cryptology. Inscrypt 2018. Vol. 11449. Springer. 2019. p. 101-114. (Lecture Notes in Computer Science, Vol. 11449). https://doi.org/10.1007/978-3-030-14234-6_6