-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathalgorand.txt
182 lines (167 loc) · 9.38 KB
/
algorand.txt
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
Algorand
========
What are advantages/disadvantages of using credit cards over the Internet?
+ Works much of the time
+ Good buyer protection
- Bad seller protection (buyer can contest charges and usually win)
- Card numbers easy to steal (requires complex fraud detection)
- High transaction charges
- International payments are hard (many don't go through)
- Requires trusted third party
- Controlled by bank (e.g., can't buy spam pharmaceuticals... maybe good?)
- No privacy
How do in-person cash transactions compare?
- Doesn't work over Internet
- Transactions are final, so no post-transaction buyer protection
though particularly for small transactions, this may be fine
+ Seller is protected (assuming no counterfeiting)
+ Payment always goes through
+ No trusted third party involved in transaction
+ Private (anonymous)
Suppose we replaced credit card numbers with public/private key pairs?
Bank gives you hypothetical card-sized secure computer with input, display
Sign each transaction with amount, recipient, comment
What would this fix?
Credit card numbers would be harder to steal
Lower fraud could lead to lower (but still non-zero) transaction fees
Could also lower fraud-detection false positives
Could give merchants protection (eliminate "card not present" transactions)
Remaining problems?
Privacy, third party trust, bank control, transaction charges
What challenges arise if we try to get rid of the bank?
1. How does payee turn a digital signature into, say, USD?
2. How does payee even know payer has enough money to cover transaction?
What is Bitcoin, and how does it address these problems?
BTC is a new currency, with cryptographically limited supply
Coins are associated with public signature keys
Coins transferred by signing new public key with old private key
#1 isn't addressed directly, that is topic of Wednesday's lecture
Instead, bitcoins themselves have value
Limited supply and social convention create value in bitcoins
Bitcoin exchanges will wire you USD for BTC and vice versa
Value fluctuates wildly (has gone from from $1,000 to $11,000 this year)
#2 solved by "distributed timestamp server"
Before getting into how BTC implements it, why does a timestamp server help?
Gives consensus on immutable record of all past transactions and their order
Example: Preventing the double-spending problem
Public key A is worth 1 BTC
A pays 1 BTC to B, walks away with some goods
A tries to pay 1 BTC to C, walk away with more goods
With timestamp server, everyone agrees A->C message later than A->B
Hence A->C is not valid, because A is already spent
How does bitcoin's distributed timestamp server work? Proof-of-work Mining
Flood new transactions
History progresses in blocks of new transactions:
block = { H(previous-block), nonce, H*(new-transactions) }
Note inclusion of previous block makes this a *block chain*
By convention, only accept block if H(block) < target-value
Currently H(block) must start with >72 0 bits.
So must try an expected five hextillion (5*10^21) nonces to find good one
Finding these nonces, known as "mining", is computationally very hard
So incentivize finding the next block with bitcoins!
First transaction in block is special "coinbase" transaction
Creates 12.5 new BTC paid to block miner
https://bitcoin.org/en/developer-reference#serialized-blocks
Note: adjust target-value as more miners come on-line
In practice, new blocks mined every 7-10 minutes or so
Given two incompatible block chains, always take longest one
How does this solve the double-spending problem?
Well-behaved nodes ordinarily shouldn't fork block chain
Assume ill-behaved nodes have less aggregate compute than well-behaved ones
(Though 49% limit is inadequate http://arxiv.org/abs/1311.0243)
If bad buys don't immediately fork chain and double spend, can't catch up
After receiving payment, before handing over goods,
wait for several new blocks (e.g., ~1hr) to cement payment in history
And note mining payouts incentivize honest behavior even by greedy miners
Still a bunch of problems with bitcoin
1. Most people care about existing fiat currencies (USD, EUR), not BTC
Don't want to assume any exchange risk on fluctuating value of BTC
2. Don't want to download entire history to verify transactions
3. Trust people for reasons other how much CPU power they waste
4. Make transactions clear quickly (seconds, not 10 min - 1 hr like BTC)
5. Huge amount of energy wasted on mining!
Let's solve #4-5 with Byzantine agreement
Can we run PBFT?
Problem: who are the 3f+1 nodes and how do we know 2f+1 are honest?
Can't just enumerate the Bitcoin users
Idea: have the coin owners be nodes in PBFT
Instead trusting hashing power owners to mine coins, trust coin owners
If you have a lot of coins, probably don't want to mess up blockchain
This is known as "proof of stake" instead of proof of work
But will PBFT scale to 10,000+ nodes? With difficulty
Straw man: coin owners elect council to run PBFT (basically peercoin [32])
How do you know whom to vote for? Council could have bad actors
What do you do after a fork?
Even without fork, council picks block, could censor certain transactions
Straw man 2: select council by lowest Hash(prev-block, node-pubkey) (homework)
Key problem: attacker can predict how block affects council membership
If attacker ever controls council, can manipulate next block to keep power
Censor transactions, sign forks, etc.
How does Algorand address these issues? Sortition
Requires a VRF--what's this?
Generate() -> (pk, sk)
VRF(sk, x) -> (pi, r) where w/o pi or sk, r looks like random function of x
Verify(pk, r, pi, x) -> Bool (true if r was valid)
Key property: pk holder can't predict, sk holder can't manipulate
What is sortition?
Users commit to pk before knowing x
E.g., x = seed||round||previous-block||role
Choose the "best" tau values of r for different nodes' VRF output
Note best could just be lowest value of x
Slight optimization--get j shots at being best if you have j coins
Saves you from having j different public keys
Important sortition parameters
tau = target expected number of committee members
T = fraction of expected committee size required for quorum
What are the different ways in which Algorand uses sortition?
Choosing a candidate block
Choosing a a smaller "committee" whose votes count in BA*
Choosing a new seed periodically
Example: each node broadcasts block proposal only if good sortition hash
E.g., set so expected number of values is tau_{process}
Sortition hash also works as block *priority*
actually hash of (r||j) for best j, to weight by number of coins owned
What if zero block proposals? Can always go with empty block
What if malicious highest-priority proposer?
Can propose two conflicting blocks
Okay if this becomes a throwaway round (agree on empty block)
Sortition will pick a different highest priority proposer next round
But must maintain safety!
How does BA* ensure safety?
* First, reduce the question to a binary decision problem
- Everybody in the committee votes for highest priority block in REDUCTION1
Does some block get t_step fraction of council?
Then vote for it in REDUCTION2
Otherwise, if timeout w/o quorum at either step, return empty_block
Result: network synchronous + honest proposer => choose block value
otherwise => choose empty_block
Guarantee: won't see multiple non-empty blocks
Caveat: Some good nodes could see block while others see empty_block
* Next, binary agreement on result of previous step or empty_block
Algorithm 8 looks a bit like Mostefaoui (from Honey Badger)
Try block_hash/empty_hash/one of two selected by common coin
Except common coin exploits VRF, doesn't need real common coin alg.
If common coin fails, just affects liveness
But note Algorithm 8 not safe on its own
Maybe one node sees block_hash, remaining time out and choose empty_hash
To fix: differentiate case when you voted same in all rounds (cool technique)
Alg. 8 returns a "FINAL" value if never voted for any other value
Alg. 3 then holds *second* vote on whether quorum saw final vote
If second vote succeeds, means quorum voted for r AND nothing else
Use bigger tau for FINAL vote, so even harder for committee to be bad
If second vote fails, return only *tentative* consensus
Can't act on tentative consensus, since can fork--what to do?
May get stuck (since nodes will reject blocks with wrong parent)
* Section 8.2: run a meta-level BA* to select among forks
Kick of meta-BA* much less frequently, with more secure seeds, etc.
Allows nodes to pick a chain (reset some tentative suffix of history)
Resets some suffix of tentative main BA*
Note 8.2 only needs tentative consensus
Bad consensus => main BA* won't make progress
Because nodes reject blocks that have the wrong parent pointer
Okay because next meta-BA* can fix the problem
Why is BA* not safe in a completely asynchronous model?
Attacker can make rounds fail large number of times until bad committee
Why doesn't BA* face the problem under it's limited synchrony assumption?
Because each seed is used only a finite number of times
E.g., algorithm 8 even hangs after too many rounds