臺灣博碩士論文加值系統

有別於雲端運算平台，霧運算平台為使用者對使用者的對等服務網路，為分散式運算系統而不受中央系統所操控。
比特幣為當今最廣為人知的電子加密貨幣，不同於傳統的法幣由中央系統所監控，是透過比特幣參予者自治的分散式交易系統，比特幣經由稱為「挖礦」的過程所產生，透過交易系統的驗證合法性以及儲存紀錄來獲取生產的比特幣。
比特幣的挖礦為用戶付出一定的運算能力來解決特定運算工作量的工作量證明機制問題，藉以避免重複支付以及確認交易行為的合法性，然而，原有的工作量證明機制所運算出的結果僅是為了驗證有效性，而沒有實值上的意義，浪費參予者的運算資源。
本篇論文應用Proof-of-Assignment的機制，由比特幣工作量證明改良的演算法，結合基因演算法讓參予者在挖礦的過程中解決NP問題這種需要大量運算資源的問題，妥善有效的運用運算資源，並整合至比特幣的交易系統，同時結合圖形處理器平行運算的優勢加速運算，並實現在霧運算平台。

Unlike cloud computing platform, vapor computing platform is a peer to peer distributed computing network without centralized server.
Bitcoin is the most well-known crypto currency. Unlike traditional fiat money that monitored by centralized system, Bitcoin is a decentralized peer-to-peer system by participants that all the Bitcoin transaction are verify by peer-serving network. “Mining” is a process of generating Bitcoin through recording transactions and verifying the legality of payments.
Users have to offer their own computing power to confirm the legality of transactions in Bitcoin mining. Mining of bitcoin is to solve proof of work puzzles that users need to expend a certain amount of computational ability to verify payments and prevent double-spending problem. However, the results of original proof of work mechanism are meaningless value in waste of participants’ computing resources.
In this paper, we use proof of assignment algorithm, an enhanced proof of work algorithm, combined with genetic algorithms allow participation by solving NP problems in the process of mining that need a lot of computing resources, proper effective use of computing resources and integrated into Bitcoin system, combined with the advantages of graphics processors to accelerate parallel computing in the vapor computing platform.

摘 要 I
Abstract II
ACKNOWLEDGEMENT III
TABLE OF CONTENTS IV
LIST OF TABLES VI
LIST OF FIGURES VII
Chapter 1. Introduction and Motivation 1
1.1. Introduction 1
1.2. Motivation 3
1.3. Overview 5
Chapter 2. Background and Related Work 6
2.1. Bitcoin 6
2.2. Crypto Currency with Scientific Purpose 7
2.3. Heterogeneous Computing 8
2.3.1. GPGPU 8
Chapter 3. System Design 11
3.1. Encoding NP problem to Genetic Algorithm 11
3.2. Proof-of-Work Model in Bitcoin 14
3.2.1. Proof-of-Work algorithm 14
3.2.2. Proof-of-Work Applied in Bitcoin 15
3.2.3. Proof-of-work Definition in Bitcoin 15
3.3. Proof-of-Assignment Model 18
3.4. Assignment Requirements 21
3.5. Map Stage 22
3.6. Reduce Stage 26
Chapter 4. Implementation and Experiment 29
4.1. Implementation 29
4.2. Experiment Setting 31
4.3. Experiment Results 33
4.3.1 Scalability 34
4.3.2 Performance 35
4.3.3 Stability 42
Chapter 5. Conclusion and Future Work 46
REFERENCES 47

[1]“BOINC, https://boinc.berkeley.edu/, 2005.
[2]Satoshi Nakamoto, “Bitcoin: A peer-to-peer electronic cash system, http://bitcoin.org/bitcoin.pdf, 2009.
[3]“Nvidia CUDA, https://developer.nvidia.com/, 2008.
[4]Adam Back, “Hashcash – A Denial of Service Counter-Measure, http://www.hashcash.org/papers/hashcash.pdf, 2002.
[5]“HSA, http://www.hsafoundation.com/, 2012.
[6]“APU, http://www.amd.com/, 2011.
[7]Jega Anish Dev, “Bitcoin mining acceleration and performance quantification, Electrical and Computer Engineering (CCECE), 2014 IEEE 27th Canadian Conference on, pp. 1-6, 4-7 May 2014.
[8]“Litecoin, https://litecoin.org/, 2011.
[9]Sunny King, “Primecoin: Cryptocurrency with Prime Number Proof-of-Work, http://primecoin.io/bin/primecoin-paper.pdf, 2013.
[10]J. Holland, “Adaption in Natural and Artificial Systems, Ann Arbor: The University of Michigan Press, 1975.
[11]Rattan Preet Singh, “Solving 0–1 Knapsack problem using Genetic Algorithms, Communication Software and Networks (ICCSN), 2011 IEEE 3rd International Conference on, pp. 591-595, 27-29 May 2011.
[12]Feier, M.C., “Solving NP-Complete Problems on the CUDA Architecture using Genetic Algorithms, Parallel and Distributed Computing (ISPDC), 2011 10th International Symposium on, pp. 278-281, 6-8 July 2011.
[13]Gerhard Reinelt, “TSPLIB—A Traveling Salesman Problem Library, INFORMS Journal on Computing, pp. 376–384, 1995.
[14]“Bitcoin Source Github, https://github.com/bitcoin/bitcoin, 2009.
[15]The Bitcoin Foundation, “Bitcoin.org, https://bitcoin.org/en/, 2009.
[16]Yu-Chi Shen, “Proof of Assignment: An Economic Proof-of-Work Based Algorithm Performing Assignments in a Peer-Servicing Network, Institute of Computer Science and Information Engineering, NCKU, 2014.