由比特幣開始，區塊鏈的技術越來越受到重視。然而，區塊鏈效率與隱私的問題限制了其應用。基於區塊鏈的應用—狼人遊戲，便面臨隱私與效率的問題。在本篇論文中，我們提出了狼人遊戲的協議並實作，示範如何解決區塊鏈應用的速度與隱私問題，我們的作品闡述了我們所採用的方法和碰到的困難，希望可以在區塊鏈研究者和應用開發者碰到隱私與效率議題時有所幫助。
在隱私方面，狼人遊戲的玩家必須隱藏自己的腳色。在本篇論文中，我們的協議採用零知識證明的技術保護玩家的隱私。在效率議題方面，玩家在區塊鏈上浪費許多時間等待狼人遊戲裡的每一個動作，我們藉由區塊鏈的第二層解決方案，讓運算幾乎在鏈下進行，使遊戲在去中心化的情境下，流暢地進行，我們也和其他可能的解法比較時間上的效率，證明我們的協議擁有更好的表現。

Starting with Bitcoin, blockchain technology is gaining more and more attention. However, the problem of blockchain efficiency and privacy limits its application. The blockchain-based application - Werewolf game, also face privacy and efficiency issues. In this thesis, we propose the protocol of Werewolf game and implement Werewolf game to demonstrate how to solve speed and privacy issues of blockchain applications. Our work describes the methods we use and the difficulties we encounter that we hope blockchain researchers and application developers will find practically useful when facing privacy and efficiency issues.
In terms of privacy, every player of Werewolf game must hide his role. In this thesis, our protocol protects privacy of players by zero-knowledge proof. In terms of efficiency issue, players spend a lot of time waiting every operation of Werewolf game on blockchain. We adopt the blockchain second layer solution to make almost all operations can be executed off chain. So game can go smoothly with no central authority. We also compare our time complexity with other schemes and prove our protocol has better performance.

口試委員會審定書 #
中文摘要 ii
英文摘要 iii
第一章 導論 1
第二章 相關作品 3
2.1關注功能的應用 3
2.2關注隱私的應用 4
2.3關注速度的應用 5
第三章 狼人遊戲的挑戰 7
3.1狼人遊戲所代表的功能 8
3.2狼人遊戲的隱私問題 9
3.3狼人遊戲的速度問題 9
第四章 方法 10
4.1處理狼人遊戲中的隱私問題 10
4.2處理狼人遊戲中的速度問題 21
第五章 結果與討論 27
5.1隱私保護的表現 27
5.2速度的表現 27
第六章 結論 29
參考文獻 31

1.Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008.
2.Andrychowicz, Marcin, et al. "Secure multiparty computations on bitcoin." Security and Privacy (SP), 2014 IEEE Symposium on. IEEE, 2014.
3.Andrychowicz, Marcin, et al. "Fair two-party computations via bitcoin deposits." International Conference on Financial Cryptography and Data Security. Springer, Berlin, Heidelberg, 2014.
4.Miller, Andrew, and Iddo Bentov. "Zero-collateral lotteries in Bitcoin and Ethereum." Security and Privacy Workshops (EuroS&PW), 2017 IEEE European Symposium on. IEEE, 2017.
5.Bartoletti, Massimo, and Roberto Zunino. "Constant-deposit multiparty lotteries on Bitcoin." International Conference on Financial Cryptography and Data Security. Springer, Cham, 2017.
6.Bentov, Iddo, and Ranjit Kumaresan. "How to use bitcoin to design fair protocols." International Cryptology Conference. Springer, Berlin, Heidelberg, 2014.
7.Kumaresan, Ranjit, Tal Moran, and Iddo Bentov. "How to Use Bitcoin to Play Internet Poker." Manuscript, www. cs. technion. ac. il/~ ranjit/papers/poker. pdf
(2014).
8.Bentov, Iddo, and Ranjit Kumaresan. "How to use bitcoin to design fair protocols." International Cryptology Conference. Springer, Berlin, Heidelberg, 2014.
9.Kumaresan, Ranjit, and Iddo Bentov. "How to use bitcoin to incentivize correct computations." Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2014.
10.Kumaresan, Ranjit, Tal Moran, and Iddo Bentov. "How to use bitcoin to play decentralized poker." Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. ACM, 2015.
11.Kumaresan, Ranjit, Vinod Vaikuntanathan, and Prashant Nalini Vasudevan. "Improvements to secure computation with penalties." Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2016.
12.Kumaresan, Ranjit, and Iddo Bentov. "Amortizing secure computation with penalties." Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2016.
13.Bentov, Iddo, Ranjit Kumaresan, and Andrew Miller. "Instantaneous decentralized poker." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2017.
14.Zyskind, Guy, and Oz Nathan. "Decentralizing privacy: Using blockchain to protect personal data." Security and Privacy Workshops (SPW), 2015 IEEE. IEEE, 2015.
15.Azaria, Asaph, et al. "Medrec: Using blockchain for medical data access and permission management." Open and Big Data (OBD), International Conference on. IEEE, 2016.
16.Reid, Fergal, and Martin Harrigan. "An analysis of anonymity in the bitcoin system." Privacy, Security, Risk and Trust (PASSAT) and 2011 IEEE Third Inernational Conference on Social Computing (SocialCom), 2011 IEEE Third International Conference on. IEEE, 2011.
17.Barber, Simon, et al. "Bitter to better—how to make bitcoin a better currency." International Conference on Financial Cryptography and Data Security. Springer, Berlin, Heidelberg, 2012.
18.Ron, Dorit, and Adi Shamir. "Quantitative analysis of the full bitcoin transaction graph." International Conference on Financial Cryptography and Data Security. Springer, Berlin, Heidelberg, 2013.
19.https://www.eblong.com/zarf/werewolf.html
20.Wei, Tzer-jen, and Lih-Chung Wang. "A fast mental poker protocol." Journal of Mathematical Cryptology 6.1 (2012): 39-68.
21.Bentov, Iddo, Ranjit Kumaresan, and Andrew Miller. "Instantaneous decentralized poker." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2017.
22.Chaum, David, and Torben Pryds Pedersen. "Wallet databases with observers." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1992.
23.Shamir, Adi, Ronald L. Rivest, and Leonard M. Adleman. "Mental poker." The mathematical gardner. Springer, Boston, MA, 1981. 37-43.
24.Decker, Christian, and Roger Wattenhofer. "A fast and scalable payment network with bitcoin duplex micropayment channels." Symposium on Self-Stabilizing Systems. Springer, Cham, 2015.
25.Cramer, Ronald, Ivan Damgård, and Berry Schoenmakers. "Proofs of partial knowledge and simplified design of witness hiding protocols." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1994.
26.Schnorr, Claus-Peter. "Efficient signature generation by smart cards." Journal of cryptology 4.3 (1991): 161-174.
27.Manuel Blum. Coin flipping by telephone. In Allen Gersho, editor, Advances in Cryptology – CRYPTO’81, volume ECE Report 82-04, pages 11–15. U.C. Santa Barbara, Dept. of Elec. and Computer Eng., 1981.
28.Brassard, Gilles, David Chaum, and Claude Crépeau. "Minimum disclosure proofs of knowledge." Journal of Computer and System Sciences 37.2 (1988): 156-189.
29.https://en.bitcoin.it/wiki/Timelock
30.Yao, Andrew Chi-Chih. "How to generate and exchange secrets." Foundations of Computer Science, 1986., 27th Annual Symposium on. IEEE, 1986.
31.Heilman, Ethan, et al. "TumbleBit: An untrusted Bitcoin-compatible anonymous payment hub." Network and Distributed System Security Symposium. 2017.
32.https://cryptonote.org/whitepaper.pdf
33.Sasson, Eli Ben, et al. "Zerocash: Decentralized anonymous payments from bitcoin." Security and Privacy (SP), 2014 IEEE Symposium on. IEEE, 2014.
34.Fujisaki, Eiichiro, and Koutarou Suzuki. "Traceable ring signature." International Workshop on Public Key Cryptography. Springer, Berlin, Heidelberg, 2007.
35.Jens Groth. Short pairing-based non-interactive zero-knowledge arguments. In Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT ''10, pp. 321-340, 2010.
36.Helger Lipmaa. Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments.In Proceedings of the 9th Theory of Cryptography Conference on Theory of Cryptography, TCC ''12,pp. 169-189, 2012.
37.Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth. Succinct noninteractive arguments via linear interactive proofs. In Proceedings of the 10th Theory of Cryptography Conference, TCC ''13, pp. 315-333, 2013.
38.Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. "The knowledge complexity of interactive proof systems." SIAM Journal on computing 18.1 (1989): 186-208.
39.Poon, Joseph, and Thaddeus Dryja. "The bitcoin lightning network: Scalable off-chain instant payments." draft version 0.5 9 (2016): 14.
40.Poon, Joseph, and Vitalik Buterin. "Plasma: Scalable autonomous smart contracts." White paper (2017).
41.https://l4.ventures/papers/statechannels.pdf
42.Fiat, Amos, and Adi Shamir. "How to prove yourself: Practical solutions to identification and signature problems." Advances in Cryptology—CRYPTO’86. Springer, Berlin, Heidelberg, 1986.
43.https://github.com/yace132/SmartWerewolf/tree/off-chain