Bài giảng Mật mã ứng dụng: Giới thiệu sơ lược về mật mã và tiền mật mã - Đại học Bách khoa Hà Nội

M™t mã ˘ng dˆng GiÓi thiªu sÏ l˜Òc v∑ M™t mã và Ti∑n m™t mã

1 / 37

Ngày 28 tháng 12 n´m 2020

Tài liªu tham kh£o

2 / 37

Hàm b´m m™t mã

Hàm b´m là mÎt hàm th‰a mãn ba tính chßt:

¶u vào là mÎt xâu Î dài bßt k˝. • ¶u ra là mÎt xâu Î dài cË ‡nh. Ta s≥ dùng 256 bit. • ây là mÎt hàm tính ˜Òc mÎt cách hiªu qu£. •

Tính an toàn

3 / 37

collision-free (kháng xung Ît) • hiding • puzzle-friendly •

Tính chßt 1: Kháng xung Ît

Vô cùng khó ∫ tìm hai xâu x và y sao cho

x

H(x) = H(y)

y

4 / 37

x = y và H(x) = H( y). 6

Partners

Support

Community

Ubuntu.com

Page History

Login to edit

Search

UbuntuHashes - Community Help Wiki

23/08/2015 09:48

UbuntuHashes

This page contains all of the md5 hashes for the different versions of Ubuntu,

including Kubuntu, Edubuntu, Xubuntu and Lubuntu.

Contents

For more information on checking md5 hashes, please refer to

1. 15.04

HowToMD5SUM. Once you have verified the md5 hash, you may want to

2. 14.04 LTS

3. 12.04 LTS

refer to the BurningIsoHowto.

Tip: Checking hashes for equality: Type ctrl-F to bring up the find box in your browser. Search for the hash as calculated by the md5sum tool (without spaces or extra characters). Only exact matches will be found.

Ÿng dˆng cıa hàm b´m kháng xung Ît

To request an update to this list, please open a bug on the ubuntu-docs package in Launchpad.

15.04

(Vivid Vervet): April 2015 (Supported until January 2016)

md5 Hash

Version

53c869eba8686007239a650d903847fd ubuntu-15.04-desktop-amd64.iso

6ea04093b767ad6778aa245d53625612 ubuntu-15.04-desktop-i386.iso

487f4a81f22f8597503db3d51a1b502e ubuntu-15.04-server-amd64.iso

49de7a0ed202d11456126589e2d1db22 ubuntu-15.04-server-i386.iso

fcfba8de8848944705cd200ff76c53cf

ubuntu-15.04-snappy-amd64-generic.img.xz

ef2a4951a2e889908a55c980d2bea475 ubuntu-15.04-snappy-armhf-bbb.img.xz

30eca69074f37982c4f1ba47737f2ad3 ubuntu-15.04-server-powerpc.iso

5 / 37

af7f4b2b5763ec6d546f87ee2883a774 ubuntu-15.04-server-ppc64el.iso

6e33d625737cc55add023bab7ce43b99 ubuntu-core-15.04-core-amd64.tar.gz

33f29b444066293cdf8c28d3eb3969e8 ubuntu-core-15.04-core-arm64.tar.gz

4db23d435fc00317798d209cb709fc8d ubuntu-core-15.04-core-armhf.tar.gz

118b012b271298e19b220b812166992e ubuntu-core-15.04-core-i386.tar.gz

https://help.ubuntu.com/community/UbuntuHashes

Page 1 sur 24

Tính chßt 2: Hiding

Ta mong muËn tính chßt: • Cho H(x), không th∫ tìm ˜Òc x.

i∑u này không kh£ thi khi không gian input nh‰! •

H(“heads”)

H(“tails”)

6 / 37

Tính chßt 2: Hiding

MÎt hàm b´m gÂi là hiding n∏u

khi gi˙ bí m™t giá tr‡ r ˜Òc chÂn ng®u nhiên, thì cho

H(r x) ta không th∫ tìm ˜Òc x.

Ÿng dˆng: SÏ Á ıy thác

• Mô ph‰ng: "Gißu mÎt giá tr‡ trong phong bì dán kín"và "M phong bì"sau này.

7 / 37

’y thác mÎt giá tr‡ và ti∏t lÎ nó sau này. •

SÏ Á ıy thác

(com, key) := commit(msg)

API:

match := verify(com, key, msg)

•

•

(com, key) := commit(msg)

Gißu msg trong phong bì:

• sau ó công khai com •

M phong bì:

8 / 37

Công khai key, msg • Ai cÙng có th∫ dùng hàm verify() ∫ ki∫m tra tính hÒp lª. •

Tính an toàn cıa SÏ Á ıy thác

(com, key) := commit(msg)

API:

match := verify(com, key, msg)

•

•

Tính an toàn:

9 / 37

• = msg0 sao cho • 6 Hiding: Chø cho com, ta không th∫ tìm ˜Òc msg. Binding: Ta không th∫ tìm ˜Òc msg verify(commit(msg), msg’) == true

SÏ Á ıy thác

Cài ∞t:

commit(msg):=(H(key | msg), H(key)) vÓi key là mÎt giá tr‡ ng®u nhiên 256 bit.

verify(com, key, msg):=(H(key | msg) == com)

•

•

Tính an toàn d¸a trên:

10 / 37

Hiding: Chø cho H(key | msg), không th∫ tìm ˜Òc msg. • = msg’ such that H(key | • 6 Binding: Không th∫ tìm ˜Òc msg msg) == H(key | msg’)

Tính chßt 3: Puzzle-friendly

Puzzle-friendly:

• VÓi mÂi giá tr‡ y cho tr˜Óc và k ˜Òc chÂn ng®u nhiên, thì vô cùng khó ∫ tìm ˜Òc x sao cho H(k x) = y.

Ÿng dˆng: Search puzzle

• Y . Cho mÎt “puzzle ID” id, và mÎt t™p giá tr‡ Y . Hãy tìm mÎt “nghiªm” x th‰a mãn H(id x) • 2

11 / 37

Tính chßt Puzzle-friendly chø ra r¨ng không có chi∏n l˜Òc nào tËt hÏn viªc th˚ mÎt cách ng®u nhiên giá tr‡ cho x.

Hàm b´m SHA-256

Padding (10* | length)

512 bits

Message (block n)

Message (block 1)

Message (block 2)

256 bits

256 bits

c

c

c

IV

Hash

12 / 37

Th£o lu™n

13 / 37

Thi∏t k∏ giao th˘c ∫ chÏi trò chÏi dân gian OØn tù tì qua iªn tho§i.

Con tr‰ b´m

H( )

Con tr‰ b´m là

(data)

mÎt con tr‰ tÓi d˙ liªu, và • mã b´m cıa d˙ liªu. •

N∏u ta có mÎt con tr‰ b´m, ta có th∫

14 / 37

lßy d˙ liªu, và • ki∫m tra xem liªu d˙ liªu có b‡ s˚a Íi. •

Danh sách liên k∏t vÓi con tr‰ b´m = "blockchain"

H( )

prev: H( )

prev: H( )

prev: H( )

data

data

data

15 / 37

Phát hiªn s˚a Íi

H( )

prev: H( )

prev: H( )

prev: H( )

data

data

data

16 / 37

Cây nh‡ phân vÓi con tr‰ b´m = “Merkle tree”

H( ) H( )

H( ) H( )

H( ) H( )

H( ) H( )

H( ) H( )

H( ) H( )

H( ) H( )

(data)

(data)

(data)

(data)

(data)

(data)

(data)

(data)

17 / 37

Là thành viên cıa cây?

Trong O(log n)

H( ) H( )

H( ) H( )

H( ) H( )

(data)

18 / 37

Ch˙ k˛ sË

fi t˜ng:

Chø b§n có th∫ k˛, nh˜ng ai cÙng có th∫ ki∫m tra •

• Ch˙ k˛ ˜Òc g≠n vÓi mÎt tài liªu cˆ th∫: không th∫ copy và paste cho tài liªu khác.

(sk, pk) := generateKeys(keysize)

API:

sig := sign(sk, message)

•

isValid := verify(pk, message, sig)

•

19 / 37

•

Tính an toàn cıa ch˙ k˛ sË

verify(pk, message, sign(sk, message)) == true

Ki∫m tra úng ch˙ k˛ hÒp lª

Không th∫ gi£ m§o ch˙ k˛:

• Dù k¥ tßn công Evil bi∏t pk và có ˜Òc ch˙ k˛ hÒp lª cıa mÎt sË tài liªu (Evil muËn)

20 / 37

Evil cÙng không th∫ t§o ra ch˙ k˛ hÒp lª cho tài liªu mÓi. •

(sk, pk)

challenger

attacker

m0

sign(sk, m0)

m1

sign(sk, m1) . . .

M, sig

M not in { m0, m1, … }

verify(pk, M, sig)

if true, attacker wins

21 / 37

Th¸c t∏

• Bitcoin s˚ dˆng sÏ Á ch˙ k˛ sË ECDSA (Elliptic Curve Digital Signature Algorithm)

• Cˆ th∫, Bitcoin s˚ dˆng ˜Ìng cong chu©n secp256k1: có m˘c an toàn 128 bit

Kích th˜Óc khóa và ch˙ k˛: •

22 / 37

Khóa bí m™t: Khóa công khai, ch˜a nén: Khóa công khai, ã nén: Thông iªp ˜Òc k˛: Ch˙ k˛: 256 bit 512 bit 257 bit 256 bit 512 bit

Dùng khóa công khai nh˜ ‡nh danh

verify(pk, msg, sig) == true

N∏u có sig th‰a mãn •

pk "thông báo"msg

thì ta có th∫ xem nh˜

23 / 37

• ∫ có th∫ thông báo trong vai trò pk, ta ph£i bi∏t khóa bí m™t sk.

Làm th∏ nào ∫ t§o ra mÎt ‡nh danh mÓi?

Sinh ra mÎt c∞p khóa ng®u nhiên sk,pk:

(sk, pk) := generateKeys(keysize)

pk là tên "công khai"mà b§n có th∫ dùng. Ho∞c tËt hÏn n∏u dùng hash(pk) làm tên công khai.

sk cho phép t§o ra thông báo.

•

•

24 / 37

B§n hoàn toàn ki∫m soát ‡nh danh cıa b§n vì chø có b§n bi∏t sk.

Hª thËng qu£n l˛ ‡nh danh phi t™p trung

• Ai cÙng có th∫ t§o ra ‡nh danh mÓi: bßt c˘ lúc nào và bao nhiêu cÙng ˜Òc!

25 / 37

Không c¶n có hª thËng qu£n l˛ trung tâm. • Trong Bitcoin, ‡nh danh ˜Òc gÂi là "‡a chø". •

Tính riêng t˜

• Các ‡a chø không tr¸c ti∏p liên k∏t vÓi ‡nh danh trong th∏ giÓi th¸c.

•

26 / 37

Nh˜ng n∏u quan sát theo thÌi gian ta có th∫ liên k∏t các ho§t Îng t¯ các ‡a chø, và t¯ ó suy ra mËi liên hª gi˙a các ‡a chø vÓi Ëi t˜Òng trong th∏ giÓi th¸c.

GoofyCoin

27 / 37

Goofy có thể tạo ra coin mới

Coin mới thuộc về tôi

signed by pkGoofy

CreateCoin [uniqueCoinID]

28 / 37

Goofy chuy∫n coin cho Alice

Bây giờ Alice là chủ sở hữu

signed by pkGoofy

Pay to pkAlice : H( )

signed by pkGoofy

CreateCoin [uniqueCoinID]

Hình: Alice có th∫ ch˘ng minh mình s h˙u coin b¨ng cách ˜a ra d˙ liªu.

29 / 37

Và Alice chuy∫n coin cho Bob

Bây giờ Bob sở hữu

signed by pkAlice

Pay to pkBob : H( )

signed by pkGoofy

Pay to pkAlice : H( )

signed by pkGoofy

CreateCoin [uniqueCoinID]

Hình: Bob có th∫ ch˘ng minh mình s h˙u coin b¨ng cách ˜a ra d˙ liªu.

30 / 37

Vßn ∑ double-spending

signed by pkAlice

signed by pkAlice

Pay to pkBob : H( )

Pay to pkChuck : H( )

signed by pkGoofy

Pay to pkAlice : H( )

signed by pkGoofy

CreateCoin [uniqueCoinID]

Hình: Alice tiêu mÎt coin hai l¶n.

31 / 37

ScroogeCoin

32 / 37

Scrooge công khai lịch sử của mọi giao dịch (một block chain, được ký bởi Scrooge)

H( )

prev: H( ) transID: 71

prev: H( ) transID: 72

prev: H( ) transID: 73

trans

trans

trans

33 / 37

Giao dịch CreateCoins tạo ra coin mới

Đúng, vì tôi tạo ra.

transID: 73 type:CreateCoins

coins created

num

value

recipient

coinID 73(0)

0

3.2

0x...

coinID 73(1)

1

1.4

0x...

coinID 73(2)

2

7.1

0x...

34 / 37

Giao d‡ch PayCoin Tiêu và phá hıy Coin

transID: 73 type:PayCoins

consumed coinIDs: 68(1), 42(0), 72(3)

HÒp lª n∏u:

coins created

num

value

recipient

coin ˜Òc tiêu là hÒp lª, • v®n ch˜a ˜Òc tiêu, •

0

3.2

0x...

1

1.4

0x...

• tÍng giá tr‡ out = tÍng giá tr‡ in, và

2

0x...

7.1 signatures

35 / 37

• ˜Òc k˛ bi ng˜Ìi s h˙u các coin ˜Òc tiêu

Vßn ∑ cıa ScroogeCoin

•

ScroogeCoin £m b£o chËng ˜Òc double-spending vì mÂi ng˜Ìi ∑u có th∫ nhìn vào blockchain và £m b£o các giao d‡ch là hÒp lª.

• Scrooge không th∫ t§o ra giao d‡ch gi£ vì anh ta không th∫ gi£ m§o ch˙ k˛ cıa ng˜Ìi khác.

Có th∫ t¯ chËi công khai mÎt giao d‡ch nào ó, t§o nhi∑u coin, ho∞c d¯ng c™p nh™t blockchain.

• • •

36 / 37

Nh˜ng Scrooge có quá nhi∑u £nh h˜ng: •

Th£o lu™n

• Hª thËng ScroogeCoin là hª thËng t™p trung. Nó d¸a hoàn toàn vào mÎt bên trung gian tin c™y (Scrooge)!

37 / 37

• Xây d¸ng ti∑n m™t mã ho§t Îng giËng ScroogeCoin nh˜ng không c¶n bên trung gian tin c™y.

M™t mã ˘ng dˆng GiÓi thiªu sÏ l˜Òc v∑ Bitcoin

1 / 37

Ngày 28 tháng 12 n´m 2020

Tài liªu tham kh£o

2 / 37

Bitcoin Paper Wallet

Hình: T§o ra vÓi https://bitcoinpaperwallet.com/

3 / 37

Khóa bí m™t

4 / 37

Chuy∫n ti∑n gi˙a Alice và Bob

Alice và Bob xác định bởi khóa công khai

Chuyển 10 Bitcoins của tôi cho Bob.

1BTC

3BTC

Mạng Bitcoin

1BTC

Alice

5BTC

Được ký bởi khóa bí mật của Alice

5 / 37

Block

Block

Block

Transaction Transaction Transaction

Transaction Transaction Transaction

Transaction Transaction Transaction

Hình: M§ng Bitcoin t§o thêm mÎt Block sau mÈi 10 phút

6 / 37

SÍ cái d¸a trên giao d‡ch (Bitcoin)

1

Inputs: Ø

time

Outputs: 25.0→Alice

2

Inputs: 1[0] Outputs: 17.0→Bob, 8.0→Alice

SIGNED(Alice)

3

Inputs: 2[0] Outputs: 8.0→Carol, 9.0→Bob

SIGNED(Bob)

4

Inputs: 2[1] Outputs: 6.0→David, 2.0→Alice

SIGNED(Alice)

7 / 37

GÎp nhi∑u giá tr‡

time

1

Inputs: ... Outputs: 17.0→Bob, 8.0→Alice

SIGNED(Alice)

...

2

Inputs: 1[1] Outputs: 6.0→Carol, 2.0→Bob

SIGNED(Carol)

...

3

Inputs: 1[0], 2[1]

Outputs: 19.0→Bob

SIGNED(Bob)

8 / 37

Joint Payment

time

1

Inputs: ... Outputs: 17.0→Bob, 8.0→Alice

SIGNED(Alice)

...

2

Inputs: 1[1] Outputs: 6.0→Carol, 2.0→Bob

SIGNED(Carol)

...

3

Inputs: 2[0], 2[1]

Outputs: 8.0→David

SIGNED(Carol), SIGNED(Bob)

9 / 37

Giao d‡ch th¸c t∏

{

metadata

"hash":"5a42590fbe0a90ee8e8747244d6c84f0db1a3a24e8f1b95b10c9e050990b8b6b", "ver":1, "vin_sz":2, "vout_sz":1, "lock_time":0, "size":404, "in":[ {

"prev_out":{

"hash":"3be4ac9728a0823cf5e2deb2e86fc0bd2aa503a91d307b42ba76117d79280260", "n":0

},

"scriptSig":"30440..."

input(s)

}, {

"prev_out":{

"hash":"7508e6ab259b4df0fd5147bab0c949d81473db4518f81afc5c3f52f91ff6b34e", "n":0

}, "scriptSig":"3f3a4ce81...."

} ], "out":[

{

output(s)

"value":"10.12287097", "scriptPubKey":"OP_DUP OP_HASH160 69e02e18b5705a05dd6b28ed517716c894b3d42e OP_EQUALVERIFY OP_CHECKSIG"

}

]

}

10 / 37

Các thao tác vÓi Bitcoin

Sinh c∞p khóa (ho∞c import khóa t¯ mÎt paper wallet). •

• ˜a khóa công khai ("‡a chø") cho ng˜Ìi khác ∫ h có th∫ chuy∫n ti∑n.

Tìm khóa công khai cıa ng˜Ìi khác ∫ chuy∫n ti∑n. • Tìm ki∏m l‡ch s˚ cıa mÎt ‡a chø. •

• Sinh ra mÎt giao d‡ch Bitcoin ∫ g˚i ti∑n ∏n mÎt khóa công khai.

• Dùng mã b´m cıa giao d‡ch nh˜ mÎt "biên lai"∫ tìm ki∏m trên m§ng.

11 / 37

Òi giao d‡ch ˜Òc "confirm". •

Satoshi Nakamoto

Bitcoin: A Peer-to-Peer Electronic Cash System

Satoshi Nakamoto satoshin@gmx.com www.bitcoin.org

Abstract. A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution. Digital signatures provide part of the solution, but the main benefits are lost if a trusted third party is still required to prevent double-spending. We propose a solution to the double-spending problem using a peer-to-peer network. The network timestamps transactions by hashing them into an ongoing chain of hash-based proof-of-work, forming a record that cannot be changed without redoing the proof-of-work. The longest chain not only serves as proof of the sequence of events witnessed, but proof that it came from the largest pool of CPU power. As long as a majority of CPU power is controlled by nodes that are not cooperating to attack the network, they'll generate the longest chain and outpace attackers. The network itself requires minimal structure. Messages are broadcast on a best effort basis, and nodes can leave and rejoin the network at will, accepting the longest proof-of-work chain as proof of what happened while they were gone.

12 / 37

1.

Introduction

Commerce on the Internet has come to rely almost exclusively on financial institutions serving as

trusted third parties to process electronic payments. While the system works well enough for

most transactions, it still suffers from the inherent weaknesses of the trust based model.

Completely non-reversible transactions are not really possible, since financial institutions cannot

avoid mediating disputes. The cost of mediation increases transaction costs, limiting the

minimum practical transaction size and cutting off the possibility for small casual transactions,

and there is a broader cost in the loss of ability to make non-reversible payments for non-

reversible services. With the possibility of reversal, the need for trust spreads. Merchants must

be wary of their customers, hassling them for more information than they would otherwise need.

A certain percentage of fraud is accepted as unavoidable. These costs and payment uncertainties

can be avoided in person by using physical currency, but no mechanism exists to make payments

over a communications channel without a trusted party.

What is needed is an electronic payment system based on cryptographic proof instead of trust,

allowing any two willing parties to transact directly with each other without the need for a trusted

third party. Transactions that are computationally impractical to reverse would protect sellers

from fraud, and routine escrow mechanisms could easily be implemented to protect buyers. In

this paper, we propose a solution to the double-spending problem using a peer-to-peer distributed

timestamp server to generate computational proof of the chronological order of transactions. The

system is secure as long as honest nodes collectively control more CPU power than any

cooperating group of attacker nodes.

1

CÏ ch∏ phi t™p trung trong Bitcoin

M§ng Peer-to-peer: M cho mÂi ng˜Ìi • Mining (ào): M cho mÂi ng˜Ìi •

13 / 37

• C™p nh™t ph¶n m∑m: Nhóm phát tri∫n ˜Òc cÎng Áng tin t˜ng.

Bitcoin là hª thËng Peer-to-peer

signed by Alice Pay to pkBob : H( )

Khi Alice muËn chuy∫n ti∑n cho Bob: Alice phát qu£ng bá giao d‡ch tÓi mÂi nút trong m§ng

T§i mÈi thÌi i∫m:

• MÂi nút ∑u có mÎt dãy các Block mà h ã Áng thu™n. MÈi Block ch˘a mÎt danh sách các giao d‡ch.

14 / 37

• MÈi nút có mÎt t™p các giao d‡ch ch˜a n¨m trong blockchain mà h l≠ng nghe ˜Òc.

Thu™t toán Áng thu™n cıa Bitcoin

Các giao d‡ch mÓi ˜Òc phát qu£ng bá tÓi mÂi nút • MÈi nút t™p hÒp mÎt sË giao d‡ch mÓi vào trong mÎt Block •

• Trong mÈi vòng, mÎt nút ng®u nhiên ph£i phát qu£ng bá Block mà nó t§o ra

• Các nút khác chßp nh™n Block chø n∏u mÂi giao d‡ch trong Block này là hÒp lª (ch˜a ˜Òc tiêu, ch˙ k˛ hÒp lª)

15 / 37

• Các nút th∫ hiªn viªc chßp nh™n Block này b¨ng cách thêm mã b´m cıa Block này trong Block ti∏p theo mà h t§o ra.

Nút không trung th¸c trong m§ng có th∫ làm gì?

CA → B

Double- spending attack

signed by A Pay to pkB : H( )

CA → A’

signed by A Pay to pkA’ : H( )

16 / 37

Các nút trung th¸c trong m§ng s≥ m rÎng theo nhánh hÒp lª dài nhßt.

– góc nhìn cıa ng˜Ìi nh™n Bob

1 confirmation

3 confirmations

CA → B

CA → A’

double-spend attempt

Nhìn thấy giao dịch CA → B 0 confirmations

•

17 / 37

Xác sußt b‡ Double-spending gi£m hàm mÙ theo sË các "confirmation" Quy t≠c chung: 6 confirmation là ı £m b£o ch≠c ch≠n. •

TÍng k∏t

• Viªc chËng giao d‡ch gi£ m§o tuy d¸a trên M™t mã, nh˜ng b≠t buÎc theo cÏ ch∏ Áng thu™n.

• Viªc chËng Double-spending thu¶n túy d¸a trên cÏ ch∏ Áng thu™n.

•

18 / 37

Ta không th∫ ch≠c ch≠n 100% mÎt giao d‡ch nào ó n¨m trong nhánh ã ˜Òc Áng thu™n. Chø ˜Òc £m b£o vÓi mÎt xác sußt nào ó.

Th˜ng 1: cho viªc t§o ra Block mÓi

Ng˜Ìi t§o ra Block mÓi ˜Òc

thêm mÎt giao d‡ch t§o coin vào trong Block • chÂn ‡a chø ng˜Ìi nh™n cho giao d‡ch này. •

Giao d‡ch này có giá tr‡ cË ‡nh: Hiªn t§i là 12.5 BTC, gi£m mÎt n˚a sau mÈi 4 n´m.

19 / 37

Ng˜Ìi t§o Block lßy ˜Òc ph¶n th˜ng này chø n∏u Block n¨m trong nhánh Áng thu™n lâu dài.

First inflection point: reward halved from 50BTC to 25BTC

n o i t a l u c r i c n i s n i o c t i b l a t o T

Year

Th˜ng cho Block mÓi là cách t§o ra các bitcoin. •

20 / 37

• S≥ h∏t vào n´m 2040. S≥ không có thêm bitcoin mÓi tr¯ khi thay Íi lu™t.

Th˜ng 2: Cho phí giao d‡ch

• Ng˜Ìi t§o ra các giao d‡ch có th∫ chÂn ∫ giá tr‡ output nh‰ hÏn giá tr‡ input.

Ph¶n d˜ là phí giao d‡ch và dành cho ng˜Ìi t§o ra Block. • ây là viªc tình nguyªn, giËng nh˜ ti∑n tip. •

21 / 37

• Tuy nhiên ng˜Ìi t§o ra Block có th∫ chÂn giao d‡ch tr£ phí cao ∫ thêm vào Block và ∫ l§i giao d‡ch có phí thßp.

MÎt sË vßn ∑

22 / 37

Làm th∏ nào ∫ chÂn nút ng®u nhiên? • Làm th∏ nào ∫ tránh bài toán free-for-all? • Làm th∏ nào ∫ tránh Sibil attack? •

B¨ng ch˘ng công viªc (Proof-of-work)

•

∫ l¸a chÂn mÎt nút ng®u nhiên: Ta chÂn nút mÎt cách ng®u nhiên theo tø lª tài nguyên cıa mÈi nút. Ta hy vÂng r¨ng không ai có th∫ gi˙ Îc quy∑n tài nguyên này.

23 / 37

ChÂn theo kh£ n´ng tính toán: Proof-of-work • ChÂn theo quy∑n s h˙u: Proof-of-stake •

Hash puzzles

tx

nonce prev_h Tx Tx

tx) < target.

H(nonce |

prev_hash |

∫ t§o ra mÎt Block, ta ph£i tìm giá tr‡ nonce th‰a mãn

Output space of hash

Target space

| · · · |

24 / 37

N∏u hàm b´m an toàn thì ta chø có cách th˚ các giá tr‡ nonce cho ∏n khi g∞p may.

Tính chßt PoW 1: Rßt khó tính toán

•

25 / 37

• Nh˜ tháng 8/2014, kho£ng 1020 hash/block. Chø mÎt sË nút quan tâm ∏n viªc tính toán này. ây là các máy ào (Miner).

Tính chßt PoW 2: Tham sË hóa chi phí tính toán

Các nút t¸ Îng tính toán l§i target sau 2 tu¶n. •

•

26 / 37

Mˆc ích: ThÌi gian trung bình ∫ t§o ra block mÓi là 10 phút. Prob(Alice t§o ra Block ti∏p theo) = tø lª vÓi kh£ n´ng hash mà cô ßy có.

Gi£ s˚ v∑ tính an toàn

27 / 37

Không có cách nào tßn công hª thËng n∏u ph¶n lÓn các Miner (tính trÂng sË theo kh£ n´ng Hash) tuân theo giao th˘c.

Gi£i hash puzzles theo xác sußt

10 minutes

y t i s n e d y t i l i b a b o r P

Time to next block (entire network)

VÓi mÈi miner, thÌi gian trung bình ∫ t§o ˜Òc block là

28 / 37

10 phút tø lª hash mà anh ta có

Tính chßt PoW 3: Dπ ki∫m tra

nonce ˜Òc công khai nh˜ mÎt ph¶n cıa block

prev_hash

tx

H(nonce

tx) < target.

• Các miners khác chø c¶n ki∫m tra •

29 / 37

| | | · · · |

Khi nào thì viªc mining có lÒi?

Giá tr‡ th˜ng cho viªc t§o ra Block mÓi + phí giao d‡ch > chi phí cho ph¶n c˘ng + chi phí iªn

Tuy nhiên viªc này rßt khó ánh giá vì

30 / 37

gÁm chi phí cË ‡nh và chi phí thay Íi • ph¶n th˜ng phˆ thuÎc vào tËc Î b´m tÍng th∫. •

6 b˜Óc ∫ ào Bitcoin

1 L≠ng nghe các giao d‡ch trên m§ng và ki∫m tra tính hÒp lª cıa

2 Duy trì blockchain và l≠ng nghe các Block mÓi. Ki∫m tra tính

các giao d‡ch.

3 Nhóm các giao d‡ch ∫ ˜a vào Block. Ph£i £m b£o các giao

hÒp lª cıa Block mÓi ˜Òc ∑ xußt.

4 Tìm ki∏m giá tr‡ nonce ∫ làm Block cıa mình hÒp lª.

5 Hy vÂng r¨ng các miner khác chßp nh™n Block cıa mình.

6 Profit!

31 / 37

d‡ch trong Block là hÒp lª.

Tìm Block hÒp lª Tính cây Merkle và tìm nonce

32 / 37

80-byte block header

4 bytes: version

4 bytes: timestamp

•

•

32 bytes: previous block hash

4 bytes: difficulty target

•

•

•

32 bytes: merkle tree of transactions

4 bytes: nonce

•

Ví dˆ

02000000 ........................... Block version: 2

b6ff0b1b1680a2862a30ca44d346d9e8 910d334beb48ca0c0000000000000000 ... Hash of previous block’s header 9d10aa52ee949386ca9385695f04ede2 70dda20810decd12bc9b048aaab31471 ... Merkle root

24d95a54 ........................... Unix time: 1415239972 30c31b18 ........................... Target: 0x1bc330 * 256**(0x18-3) fe9f0864 ........................... Nonce

33 / 37

M˘c Î khó

prev_hash

tx

H(nonce

tx) < target.

Miner ph£i tìm nonce th‰a mãn •

| | · · · |

•

| M˘c Î khó cıa target (theo hexa) tháng 8 n´m 2015 là 0000000000000000172EC0000000000000000000000000000000000000000000 T˘c là ta ph£i th˚ kho£ng 267 l¶n thì mÓi tìm ˜Òc nonce hÒp lª.

2 tu¶n

M˘c Î khó ˜Òc thay Íi sau mÈi 2016 Block theo công th˘c: •

34 / 37

previous_difficulty 2016 10 phút next_difficulty = ⇥ ⇥ thÌi gian v¯a ào 2016 Block z }| {

CPU Mining

while (1){

HDR [ kNoncePos ]++; if ( SHA256 ( SHA256 ( HDR )) < target )

return ;

}

35 / 37

Mining Pool

Hình: Nhi∑u ng˜Ìi tham gia ào trên cùng mÎt Block và ˜Òc tr£ ti∑n theo sË l˜Òng Hash.

36 / 37

MÎt sË ‡a chø có ích

• Khóa hÂc Bitcoin and Cryptocurrency Technologies https://www.coursera.org/learn/cryptocurrency

• Live Blockchain http://blockchain.mit.edu/blockchain/

37 / 37

• Bitcoin Developer Guide https://bitcoin.org/en/developer-guide