-
Notifications
You must be signed in to change notification settings - Fork 31
/
Week 1 : Crypto and Cryptocurrencies
450 lines (401 loc) · 26.9 KB
/
Week 1 : Crypto and Cryptocurrencies
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
Introduction to Crypto and Cryptocurrencies
---------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------------
1.1 Cryptographic Hash Functions
---------------------------------
* Cryptographic Hash function - mathematical function and takes three attributes:
a. takes any string as input;
b. fixed-size output (could be 256 bits - like bitcoins);
c. efficiently computable (within a reasonable length of time it needs to be computed);
* Hash functions need to be cryptographically secure (Security properties):
a. Collision-free
b. Hiding
c. Puzzle-friendly
a. Collision-free
-------------------
- It can be assumed that the hash function is collision free, since collision occurence is infinitesimal.
- If x != y , then we can assume H(x) != H(Y);
- In case H(X) = H(Y), then assume X = Y;(message digest);
- In Reality (Input) # (X) is much greater than (Output) # Hash function (Y or H(X))- It means there is a chance for collision to occur, but it occurs when 2^130 or more possibilities are taken into consideration and computation effort is a lot.
- Therefore it is safe to assume that hash-functions are collision free.
b. Hiding
------------
- Given H(x), it must be infeasible to find x.
- But in case of a coin-flip, there are only two possiblities -> H("head") or H("tails") where x can be either "head" or "tail"; Here computing the hash of "head" or "tail" can fetch the answer - easy to compute x;
- Better solution - for common value x; Take x and concatenate it with a value r (r is choosen from a distribution thats really spread out).
- If r is chosen from a probability distribution that has high min-entropy(distribution is very spread-out), then given H(r | x), it is infeasible to find x.
- Application : Commitment - Commit to a value , reveal it later.
* Commitment API
------------------
-> 2 things
i. Commit to a message and that returns two values - "commitment" and a "key";
- commitment - envelope put on the table;
- key - secret key for unlocking the envelope;
ii. Allow someone else to verify, given the commitment and key so that the message is as expected.
(com, key) := commit(msg)
match := verify(com, key, msg)
* To seal msg in envelope:
(com, key) := commit(msg) -- then publish
* To open envelope:
publish key, msg
anyone can use verify() to check validity
* Security
- Hiding : Given com, infeasible to find msg.
- Binding : Infeasible to find msg != msg' => verify(commit(msg), msg') == true (not possible);
----------------------------------------------------------------------------------------
* Implementation of commitments - Inorder to implement commitment to a message
- Generate a random 256-bit value "key";
- commit(msg) := (H(key, msg), key) where key is a random 256-bit value;
- verify(com, key, msg) := ( H(key | msg) == com)
- Security properties
----------------------
+ Hiding : Given H(key | msg), infeasible to find msg.
+ Binding : Infeasible to find msg != msg' such that H(key | msg) == H(key | msg')
c. Puzzle-friendly
-------------------
For every possible output value y, if k is chosen from a distribution with high min-entropy(widely spread out distribution), then it is infeasible to find x such that H(k | x) = y; (In case someone is targetting the hash function - and they chose a known value of k it will still be difficult to find the value of x to retrieve the respective y value).
Application : Search puzzle
----------------------------
Given a "puzzle id"(k) (high distribution), and a target set Y:
Try to find a "solution" x such that H(id | x) = Y
- Puzzle-friendly property implies that no solving strategy is much better than trying random values of x.
----------------------------------------------------------------------------------------------------------------------------------------
There are a lot of HASH function, but the one used and bitcoin uses is the SHA-256 hash function;
* SHA-256 hash function
-------------------------
- Takes the message (256 bits) being hashed and breaks it into blocks of 512 bits long;
- Since the message is not necessarily gonna be a multiple of the block-size some padding needs to be appended.
- The padding is gonna consist of
* at the end - 64 bit length field - length of the message in bits;
* before that 1 bit
* followed by some 0 bits; (until it is 512 message block)
* Once it is 512 bit long it is chopped off;
(512 bits) (512 bits) (512 bits)
Message Message Message
Block - I Block - II Block - III
| | |
| | |
\ / \ / \ /
----- 256-bits ------- ------
IV --------> | C | ---------->| C | ------------>| C |------> Hash
(256) ----- ------- ------- (256)
bits bits
* c is a compressor;
Theorem - If c is collision-free, then SHA-256 is collision-free;
(512 bits) (512 bits) (512 bits)
Message Message Message
Block - I Block - II ... Block - n
| | |
| | |
\ / \ / \ /
----- 256-bits ------- ------
IV --------> | C | ---------->| C | ------------>| C |------> Hash
(256) ----- ------- ------- (256)
bits
256 256+512 256 256+512 256 256
* No collison has been ever found with SHA-256 hash function.
-------------------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------------------------------------
1.2 Hash Pointers and Data Structures
-------------------------------------
* Hash Pointer - Data structure - pointer to where information is stored and with pointer we can store a cryptographic hash of the information.
* A regular pointer gives a way to retrieve the information.
* A hash pointer gives a means to retrieve the information as well as verify if the information has changed.
________________________________
| |
\ / H(|) (Hash pointer)
___________
| |
| DATA |
| |
|___________|
* Hash pointers can be used to build various kinds of data structurers. E.g - Linked list, binary search trees, etc implement it as a hash pointers rather than pointers.
* Linked-list as a Hash pointer - Datastructure can be called a block chain
---------------------------------------------------------------------------
H( )
____________ ____________ ____________ ____________ |
| --------|-- | --------|-- | --------|-- | --------|-- |
| |prev:H(|)| | |prev:H(|)| | |prev:H(|)| | |prev:H(|)| |
| ----------- | ----------- | ----------- | ----------- |
| | | | | | | | | | | |<---------
<-| | DATA | <---------------| | DATA | <------------| | DATA | <---------------| | DATA |
| | | | | | | |
|_________| |_________| |_________| |_________|
In a regular linked-list - there are a series of blocks and each block has data as well as a pointer to the previous block in the list, in this case the previous block pointer will be replaced with a hash pointer.
The Hash pointer gives, where it is and wehat the value of the previous block is.
* Application -> Detecting Tampering - tamper-evident log
To build a log adta structure that stores a bunch of data so that data can be appended into the log, but if somebody tampers with that data that is earlier in the log then we can detect it.
-------------------------------------------------------
Block-chain - Evidence tamper property
--------------------------------------
If the adversary wants to tamper with data anywhere in the entire chain , inorder to keep consistency all the hash pointers need to be tampered all the way to the beginning of thechain and ultimatley gonna run into the road block because the head of the list cannot be tampered with.
* Binary tree with Hash Pointers = "Merkle tree" - Ralph Merkel
----------------------------------------------------------------
|
____\ /______
| H( ) H( ) |
|___|______|__|
| |
________________________________________| |_______________________________
| |
______\ /_________ ________\ /________
| H( ) H( ) | | H( ) H( ) |
|____|________|___| |_____|_________|___|
| | | |
________| |__________ _____________________| |_______________
| | | |
______\ /________ ________\ /____ _______\ /__________ _________\ /_______
| H( ) H( )| | H( ) H( ) | | H( ) H( ) | | H( ) H( ) |
|___|_________|_| |___|_______|__| |___|___________|__| |___|____________|_|
| | | | | | | |
| | | | | | | |
\ / \ / \ / \ / \ / \ / \ / \ /
-------- --------- -------- --------- --------- --------- --------- ---------
| | | | | | | | | | | | | | | |
| DATA | | DATA | | DATA | | DATA | | DATA | | DATA | | DATA | | DATA |
| | | | | | | | | | | | | | | |
|________| |_______| |________| |_______| |_________| |________| |________| |________|
- From a bunch of data blocks at the bottom, consecutive pais of the data blocks are taken;
- For these two data blocks a data structure with two hash functions is built, so on till the root of the tree.
- We can traverse down through the hash pointers to any point in the list and ensure that the data has not been tampered with.
- If an adversary tampers with the data, then the hash pointer will be tampered with and so on, one -level upwards, eventually the aversary won't be able to tamper with the hash pointer at the head that we have remembered.
* Proving the membership in a merkel tree
-------------------------------------------
| show O(log n) items
____\ /______
| H( ) H( ) |
|___|_________|
|
________________________________|
|
______\ /_________
| H( ) H( ) |
|____|____________|
|
________|
|
______\ /________
| H( ) H( )|
|___|___________|
|
|
\ /
--------
| |
| DATA |
| |
|________|
We remember the root, and someone wants to convince us that the data block belongs to the merkel tree, then they need to show the data block and verify that the hash matches along all levels;
This takes (log n) items to be shown and therefore (log n) time to verify;
---------------------------------------------------------------------------------------------------------------------------------------
1.3 Digital Signatures
-----------------------
* Requirements from the signature
a. Only you can sigh, but anyone can verify.
b. Signature is tied to a particular document (can't be cut-and-paste to another document).
API for digital signatures
--------------------------
Three operations to be performed
a. Generate keys -> provide the input keysize and this generates two keys sk and pk.
sk : secret signing key (Information kept secret and only for making signature)
pk: public verification key (Everybody is given access, and anyone can verify the signature)
(sk, pk) := generateKeys(keysize)
b. Sign Operation - Take the secret message key and some message that you want to put your signature on. This returns a sig (signature) - string of bits that represents the signature;
sig := sign(sk, message)
c. Verify Operation - Takes something that claims to be a valid signature and verifies if it is correct.
It takes the public key of the signer, message which bears the signature, and takes the supposed signature, then checks for its validity. The public key is required to verify the signature.
isValid := verify(pk, message, sig)
------------------------------------------------------------------------------
(sk, pk) := generateKeys(keysize) -> randomized algorithm
sig := sign(sk, message) -> randomized algorithm
isValid := verify(pk, message, sig) -> deterministic algorithm
------------------------------------------------------------------------------
* Requirements for signatures
------------------------------
a. valid signatures verify : verify(pk, message, sign(sk, message)) == true
b. can't forge signatures : If someone knows pk, gets the signature on messages of choice, can't produce a verifiable signature on another message.
* Signing a hash pointer - signature covers the whole structure.Signing the hash pointer at the end of the block chain, then the result would be that you'll be digitally signing the entire contents of the block chain.
---------------------------------------------------------------------------------------------------------------------------------------
* Bitcoin uses ECDSA standard
- ECDSA - Elliptic Curve Digital Signature Algorithm (US govt standard);
- Good randomness is essential, if bad randomness is used to generatekeys, or in the sign operation - probably the private key could be leaked.
---------------------------------------------------------------------------------------------------------------------------------------
1.4 Public Keys as Identities
------------------------------
* If isValid := verify(pk, message, sig) := true, then pk -> "public name"/ identity from sk (secret key);
* Create new randomized key-pair (sk, pk)
- pk - public "name" (usually better to use Hash(pk) - cause of the size - 256 bits);
- sk - secret key - letsyou "speak for" the identity.
* You can control the identity since only you know sk and if pk looks random nobody needs to know eho you are.
------------------------------------------------------------
* Decentralized Identity Management
------------------------------------
-> Anybody can make a new identity at any time , make as many as you want!
-> No central point of coordination. (No central authority);
-> These identities are called "addresses" in Bitcoin.
-> Address - public key / hash of a public key;
------------------------------------------------------------
* Privacy
---------
-> Addresses not directly connected to real-world identity.
-> But, observer can link together an address's activity over time, and make inferences.
------------------------------------------------------------
Question
If you generate numerous identities(public keys) for yourself and interact online using those identities, what might happen?
a. Others might be able to take over your identities if your randomness is bad. (True)
b. Others may be able to link your identities because public keys generated on the same computer look similar. (False)
c. Others may be able to de-anonymize you by analyzing your activity pattern. (True)
---------------------------------------------------------------------------------------------------------------------------------------
1.5 A Simple Cryptocurrency
----------------------------
* GoofyCoin -> simplest cryptocurrency engine we can imagine.
* Rules on GoofyCoin
---------------------
1. Goofy can create new coins
a. New coins belong to me (Goofy).
b. Created coin data structure -> CreateCoin operation and a unique coin id that Goofy generated; Then there is a digital signature put on it by Goofy, which anyone can verify.
_____________________________
| Signed by pk(goofy) |
|___________________________|
| CreateCoin [uniqueCoinId] |
|___________________________|
2. A coin's owner can spend it
- Whoever owns a coin can pass it on to someone else.
_____________________________
| Signed by pk(goofy) |
|___________________________|
| Pay to pk(Alice): H( | ) | (Goofy pays to Alice) (Alice owns the coin)
|______________________|____|
|
______________________\ /____
| Signed by pk(goofy) |
|___________________________| (Goofy owns the coin)
| CreateCoin [uniqueCoinId] |
|___________________________|
- The recipient can pass on the coin again.
_____________________________
| Signed by pk(Alice) |
|___________________________|
| Pay to pk(Bob) : H( | ) | (Alice pays to Bob) (Bob owns the coin)
|______________________|____|
|
______________________\ /____
| Signed by pk(goofy) |
|___________________________|
| Pay to pk(Alice): H( | ) | (Goofy pays to Alice) (Alice owns the coin)
|______________________|____|
|
______________________\ /____
| Signed by pk(goofy) |
|___________________________| (Goofy owns the coin)
| CreateCoin [uniqueCoinId] |
|___________________________|
------------------------------------------------------------
* Security problem with GoofyCoin
---------------------------------
-> Double spending attack - Alice give a valid coin to both Bob and Chuck
_____________________________ _____________________________
| Signed by pk(Alice) | | Signed by pk(Alice) |
|___________________________| |___________________________|
| Pay to pk(Bob) : H( | ) | | Pay to pk(Chuck) : H( | )|
|______________________|____| |________________________|__|
| |
______________________\ /____ |
| Signed by pk(goofy) |<----------------------------------------------
|___________________________|
| Pay to pk(Alice): H( | ) |
|______________________|____|
|
______________________\ /____
| Signed by pk(goofy) |
|___________________________|
| CreateCoin [uniqueCoinId] |
|___________________________|
------------------------------------------------------------
* ScroogeCoin
--------------
Scrooge publishes a history of all transactions (a block-chain , digitally signed by Scoorge).
H( | )
____________ ___________ ____________ ____________ |
| --------|--- | -------|---- | --------|--- | --------|--- |
| |prev:H(|) | | |prev:H(|) | | |prev:H(|) | | |prev:H(|) | |
| ------------ | ------------ | ------------ | ------------ |
| |transID:71| | |transID:72 | | |transID:73| | |transID:74|<-------
<-| |----------| <------------| |-----------| <-----------| |----------| <------------| |----------|
| TRANS | | TRANS | | TRANS | | TRANS |
|__________| |___________| |__________| |__________|
* optimization : put multiple transactions in the same block as bit coin does.
* Scoorge publishes the history;
* The history allows us to detect double-spending:
- assume Alice owns a coin and she pays it to Bob and later on opays it to Chuck.
- Chuck will be able to notice something is wrong as he will be able to look into the history and see that Alice has already paid that coin to Bob. (Everyone can see that is a double spend) - hence it will be rejected;
* ScroogeCoin - Two kinds of Transactions
-------------------------------------------
1. CreateCoins Transaction:
- each coin is worth a number of scrooge coins.
* Creates new coin
- multiple coins can be created in one transaction.
* It is a valid coin since Scoorge has created it.
_____________________________________
| transID: 72 type:CreateCoin |
|____________________________________|
____________________________________
| coins created |
|____________________________________|
| num | value | recipient |
|__________|___________|_____________|
| 0 | 3.2 | 0x... | <---- coinID 72(0)
| 1 | 1.4 | 0x... | <---- coinID 72(1)
| 2 | 7.1 | 0x... | <---- coinID 72(2)
--------------------------------------
--------------------------------------
2. PayCoins transaction:
* PayCoins transaction consumes (and destroys) some coins, and creates new coins of the same total value (the coins might belong to different people).
_____________________________________
| transID: 72 type:PayCoins |
|____________________________________|
____________________________________
| consumed coinIDs: |
| 68(1), 42(0), 72(3) | <- All these coins are being consumed and destroyed by this PayCoins transactions.
|____________________________________|
| coins created |
|____________________________________|
| num | value | recipient |
|__________|___________|_____________|
| 0 | 3.2 | 0x... |
| 1 | 1.4 | 0x... |
| 2 | 7.1 | 0x... |
--------------------------------------
| signatures |
--------------------------------------
* the new coins created have to add up to the same value as those consumed in the transaction.
* At the bottom there is a set of digital signatures - this transaction needs to be signed by everyone who's paying in a coin. So if you are the owner of one of the coins in the transaction then you need to digitally sign the transaction.
* The Rules of ScroogeCoin PayCoins transaction is valid if:
------------------------------------------------------------
1. consumed coins are valid - (the coins were created in previous transactions);
2. consumed coins were not already consumed in some previous transactions (double spend attack);
3. total values of the coins out of the transaction is same as the total coins that went into the transaction. (total value out = total value in);
4. the transaction is signed by all the owners of the consmed coins.
------------------------------------------------------------------------------------------------------------------------
* Coins are Immutable : (There exists flexibility)
------------------------
- Coins are immutables (not changed, subdivivded, combined);
- Coins are created in one transaction and later consumed in some other transaction.
- Subdivision of coins by using transactions:
a. create a new transaction (coin - value 10 created)
b. consume your coin (consumed - value 10 coin)
c. pay out two new coins to yourself (pay out two value 5 coins);
* Similarly you can combine or pass on a coin by creating a chain of transactions.
* Each of which passes the value on in a form of a nw coin to someone else.
-----------------------------------------------------------------------------------
* The problem above is Scrooge has the authority, but can we decentralize it?
- How everyone can agree upon a single published block chain - history of transactions that have happened?
- How to verify which transactions have occured and are valid?
- How IDs can be assigned to things in a decentralized way?
------------------------------------------------------------------------------------------------------------------------
Question
In ScroogeCoin, you have ten coins each of value 3.0. You’d like to transfer coins of value 5.0 to your friend. This requires:
a. One transaction, one new coin created, and one signature
b. One transaction, two new coins created, and two signatures - Correct
c. Two transactions, two new coins created, and four signatures
d. Two transactions, one new coin created, and two signatures