Table of Contents
Foreword xv
Preface xvii
Acknowledgments xix
Introduction xxi
1 Overview 1
1.1 Chapter Introduction 1
1.2 Overview of Background 1
1.2.1 Blockchain 1
1.2.2 Modern Cryptography 2
1.3 Motivation and Foundation of This Book 2
1.3.1 General Motivation 2
1.3.2 Basic Foundations 3
1.4 Overview of Designing Practical PKC Scheme 4
1.4.1 Validating a PKC Scheme 4
1.4.2 Steps to Investigate PKC Scheme 5
1.5 Contributions 6
1.6 Chapter Summary 9
2 Preliminaries 11
2.1 Chapter Introduction 11
2.2 Definitions of Research Objects 11
2.2.1 Defining Blockchain 11
2.2.2 Defining PKC Schemes 12
2.3 Complexity Theory 13
2.3.1 Computational Complexity Measurement 14
2.4 Provable Security Theory and Proof Techniques 14
2.4.1 Proof by Security Reduction 15
2.4.2 Proof by Sequences of Games 16
2.4.2.1 Transitions based on Indistinguishability 16
2.4.2.2 Transitions based on Failure Events 17
2.4.3 Proof by Contradiction 18
2.4.4 Proof by Theorem 18
2.4.5 Random Oracle Model 19
2.4.6 Standard Model 19
2.5 Algebraic Notions and Numeric Theory 19
2.5.1 Group, Ring and Fields 20
2.5.1.1 Group 20
2.5.1.2 Ring 20
2.5.1.3 Field 21
2.5.1.4 Bilinear Pairing 21
2.5.1.5 Proof of Knowledge 21
2.5.2 Numeric Theory 22
2.6 Chapter Summary 24
3 Background 25
3.1 Chapter Introduction 25
3.2 Introduction to Blockchain 25
3.2.1 Bitcoin 27
3.2.2 Ethereum 29
3.2.3 Other Cryptocurrencies 32
3.2.3.1 Cryptographic Scheme-Centered Altcoins 32
3.2.3.2 Other Altcoins 34
3.3 Security Vulnerabilities, Attacks & Countermeasures 35
3.3.1 Vulnerabilities of Altcoins 35
3.3.2 Privacy Threat of Altcoins 36
3.3.3 Attacks of Altcoins 37
3.3.4 Countermeasures 39
3.4 Chapter Summary 44
4 Public-Key Signature Scheme for Blockchain 45
4.1 Chapter Introduction 45
4.2 Overview of PKS 45
4.2.1 Introduction to PKS 45
4.2.2 PKS in Blockchain 46
4.2.2.1 Use Case 1: ECDSA in Bitcoin 46
4.2.2.2 Use Case 2: MLSAG in Monero 46
4.2.3 Definition of PKS 47
4.3 Case Analysis: ECDSA 47
4.3.1 Construction of ECDSA 49
4.3.2 Analysis of ECDSA's Security and Efficiency 50
4.4 Case Analysis: BLS 51
4.4.1 Construction of BLS 51
4.4.2 Security Requirement of BLS 52
4.4.3 Security Analysis of BLS 52
4.5 Group Signature and Case Analysis 55
4.5.1 Background of Group Signature 55
4.5.2 Definition of Group Signature 57
4.5.3 Case Study: MLSAG Scheme 58
4.5.3.1 Construction of MLSAG 58
4.5.3.2 Security Analysis of MLSAG 59
4.5.4 Efficiency Analysis of MLSAG 62
4.6 Ring Signature and Case Analysis 63
4.6.1 Background of Ring Signature 63
4.6.2 Case Study: LRRS Scheme 64
4.6.2.1 Construction of LRRS 64
4.6.2.2 Security Requirement of LRRS 65
4.6.2.3 Security Analysis of LRRS 66
4.6.2.4 Efficiency Analysis of LRRS 68
4.7 Chapter Summary 70
5 Public-Key Encryption Scheme for Blockchain 71
5.1 Chapter Introduction 71
5.2 Overview of PKE 72
5.3 Introduction to PKE 72
5.3.1 PKE for Blockchain 72
5.3.1.1 Use Case 1: ECC-Based Encryption in Bitcoin 73
5.3.1.2 Use Case 2: RSA in Blockchain 73
5.3.1.3 Use Case 3: Pedersen Commitments 73
5.3.1.4 Other Cases 73
5.3.2 Definition of PKE 74
5.4 Case Analysis: IBE 75
5.4.1 Background of IBE Scheme 75
5.4.2 Construction of IBE Scheme 76
5.4.2.1 BasicPub Scheme 76
5.4.2.2 BasicIdent Scheme 76
5.4.2.3 FullIdent Scheme 77
5.4.3 Security Analysis of IBE Scheme 77
5.4.3.1 Security Analysis BasicPub 77
5.4.3.2 Security Analysis of BasicIdent 78
5.4.4 Security Analysis of FullIdent 79
5.5 Case Analysis of CS 83
5.5.1 Construction of CS 83
5.5.2 Security Analysis of CS 84
5.6 Case Analysis of HDRS 88
5.6.1 Background of Signcryption 88
5.6.2 Construction of HDRS 88
5.6.3 Security Requirement of HDRS 90
5.6.4 Security Analysis of HDRS 90
5.6.5 Efficiency Analysis of HDRS 92
5.7 Methods to Construct an IND-CCA2 Secure Encryption Scheme 93
5.7.1 Generic Methods to Achieve IND-CCA2 94
5.7.2 Background of IND-CCA2 94
5.7.3 IND-CCA2 from Non-Interactive Zero-Knowledge (NIZK) 96
5.7.4 IND-CCA2 from Random Oracle Model 96
5.7.5 IND-CCA2 from (UHF) 96
5.7.5.1 Universal Hash Function 97
5.7.5.2 UHF Case: CS Scheme and Its Variants 97
5.7.6 IND-CCA2 from Hybrid Encryption (HY) and Use Case 98
5.7.7 IND-CCA2 from ElGamal and Its Extensions 98
5.8 Chapter Summary 99
6 Public-Key Hash Function for Blockchain 101
6.1 Chapter Introduction 101
6.2 Overview of PKH 101
6.2.1 PKH in Blockchain 102
6.2.2 Introduction to PKH 103
6.2.3 Defining PKH 103
6.3 Case Analysis: ACH 104
6.3.1 Construction of ACH 105
6.3.2 Security Analysis of ACH 105
6.4 Case Analysis: HCCH 106
6.4.1 Construction of HCCH 107
6.4.2 Security Requirement of HCCH 107
6.4.3 Security Analysis of HCCH 108
6.4.3.1 Proof of Indistinguishability 108
6.4.3.2 Proof of Public Collision-Resistance 109
6.4.4 Efficiency Analysis of HCCH 110
6.5 Case Analysis: TUCH 111
6.5.1 Construction of TUCH 111
6.5.2 Security Requirement of TUCH 112
6.5.3 Security Analysis of TUCH 113
6.5.3.1 Proof of Indistinguishability for TUCH 113
6.5.3.2 Proof of Collision-resistance 114
6.5.4 Efficiency Analysis of TUCH 114
6.6 Case Analysis: RCH 115
6.6.1 Construction of RCH 115
6.6.2 Security Requirement of RCH 115
6.6.3 Security Analysis of RCH 117
6.6.3.1 Proof of Indistinguishability 117
6.6.3.2 Collision-Resistance between Non-Revoked Hash 118
6.6.3.3 Collision-Resistance between Revoked and Non-Revoked Hash 120
6.6.4 Efficiency Analysis of RCH 120
6.7 Chapter Summary 121
7 Zero-Knowledge Proof for Blockchain 123
7.1 Chapter Introduction 123
7.2 Introduction to ZKP 123
7.3 ZKP in Blockchain 124
7.3.1 Use Case 1: NIZK in ZCoin 124
7.3.2 Use Case 2: zk-SNARK in ZCash 124
7.3.3 Other Use Cases 125
7.4 Introduction to of ZKP 125
7.4.1 Zero-Knowledge Proof and Argument 126
7.4.2 Non-Interactive Zero-Knowledge Proofs (NIZK) 126
7.4.3 Zero-Knowledge Succint Non-Interactive Arguments of Knowledge (zk-SNARK) 128
7.4.4 Known constructions and security of zk-SNARK 128
7.5 Steps to Achieve a zk-SNARK 129
7.5.1 Computation to Algebraic Circuit 129
7.5.2 Algebraic Circuit to R1CS 130
7.5.2.1 What's Arithmetic Circuits? 130
7.5.2.2 Rank 1 Constraint System (R1CS) 131
7.5.3 R1CS to QAP 131
7.5.3.1 Quadratic Arithmetic Program (QAP) 131
7.6 Case Analysis: GS08 Scheme 132
7.6.1 Introduction to GS08 Scheme 132
7.6.2 Definition and Security Requirement of GS08 Scheme 132
7.6.3 Analysis of GR08 Scheme 133
7.6.4 Security Analysis of Groth and Sahai's Scheme 134
7.7 Case Analysis: GR16 Scheme 136
7.7.1 Non-Interactive Zero-Knowledge Arguments of Knowledge 136
7.7.2 Construction of Groth's GR16 Scheme 137
7.7.3 Analysis of GR16's First Construction 137
7.7.4 Analysis of Groth's Second Construction 138
7.8 Case Analysis: CA17 Scheme 139
7.8.1 Prepare to Attack: Building ZK-SNARKs from QAP 140
7.8.2 Potential Attacks: Learning Information by modifying the CRS 141
7.8.3 Open Problems for zk-SNARK 142
7.9 Chapter Summary 142
8 Tools as Optimizations for Blockchain 145
8.1 Chapter Introduction 145
8.2 Main Problems in Blockchain 145
8.2.1 Security Problem 145
8.2.2 Privacy Problem 146
8.2.3 Efficiency and Scalability Problem 147
8.2.4 Inflexibility and Vulnerabilities 147
8.3 Tools to Enhance Security 148
8.3.1 Commitment 149
8.3.2 Trapdoor Commitment 149
8.3.3 Merkle Hash Tree 150
8.3.4 Public-Key Encryption 151
8.4 Tools to Enhance Privacy-Preservation 151
8.4.1 Zero-Knowledge Proof 151
8.4.2 Group Signature, Ring Signature, and Variants 152
8.4.3 Multi-Party Computation (SMPC) 152
8.4.4 Fully Homomorphic Encryption 153
8.5 Tools to Improve Flexibility and Vulnerabilities 153
8.5.1 Chameleon Hash as Solution 153
8.5.2 Malleable Signature as Solution 154
8.5.2.1 Malleable Signature 154
8.5.2.2 Chameleon Signature 155
8.5.2.3 Sanitizable Signature 155
8.5.2.4 Redactable Signature 155
8.5.2.5 Redactable Blockchain 155
8.6 Tools to Improve Efficiency and Scalability 157
8.6.1 Accumulator 157
8.6.2 Bloom Filter 158
8.6.3 Micro Payment 158
8.6.4 Lightning Payment Channel 159
8.7 Chapter Summary 160
9 Regulation and Economies of Blockchain 161
9.1 Chapter Introduction 161
9.2 Background 161
9.3 Blockchain Regulation 162
9.3.1 Global Developments of Regulation on Blockchain 162
9.3.2 Challenge & Open Problem for Regulation 164
9.3.3 Regulatory SandBox and Deployment 165
9.3.4 Redactable Blockchain 167
9.4 Economics 167
9.4.1 Pricing 168
9.4.2 Research of ICO in Blockchains 170
9.4.3 Ponzi Scheme in Blockchains 171
9.4.4 Study of Blockchain Economies 172
9.4.5 Business Process Execution 173
9.4.6 Application associated with Blockchain Economies 174
9.5 Chapter Summary 175
10 Concluding Remarks 177
10.1 Summary of Design and Analysis 177
10.2 Open Problems 180
10.2.1 Challenges in Designing Practical PKS 180
10.2.2 Challenges in Designing Practical PKE 180
10.2.3 Challenges in Designing Practical PKH 181
10.2.4 Challenges in Designing Practical ZKP 181
10.2.5 Challenges in Optimizing Blockchain 182
10.2.6 Challenges in Blockchain Regulation & Blockchain Economies 182
10.3 Conclusion 183
Bibliography 185
