Week 7 Proof of Stake
PoW: energy inefficient
PoS: Energy efficient alternative
PoS version of longest-chain protocol
Copyright By PowCoder代写 加微信 powcoder
Proof of Stake
● Proof of Stake (PoS)
energy efficient alternative
replacement to PoW
● Simple way to implement PoS
within the longest chain protocol
● Vulnerabilities
nothing at stake (NaS) attack grinding attack
prediction and bribing
● PoS cryptos (market cap in Feb. 2023): Ethereum 2.0 ($188 B), Cardano ($12 B), Solana ($8 B), …
Recall: Proof of Work
● Find nonce such that
H(hash(parent.header), Merkle root of TXs, nonce) < threshold
● Finding nonce entails work;
● Nonce is the proof of work.
● PoW is a Sybil resistant leader election mechanism;
● PoW regulates blockchain growth, forking, security, etc.
Proof of Stake
Doing work is replaced by owning coins; block proposers own coins .
Level of participation proportional to stake
higher probability of being a proposer
(Do we need to worry about centralization?)
Advantages:
energy efficient
capital efficient -- no need for mining hardware
Each coin is uniquely associated with a pair of public and private keys.
H(hash(parent.header), Merkle root of tx, public key) < threshold
Problem: Grinding
Can try different set of tx such that Merkle root of tx works out
“correctly”. There are 2k choices.
Also, a set of k transactions have k! permutations.
If k is large, it’s a race to try as many choices as quickly as possible. This is called “grinding.”
That sounds like PoW, not PoS!
• Let us leave the transactions out to use: H(hash(parent.header), public key) < threshold
• Problem: Liveness
o This is unlike PoW where nonce can be tried at will.
o Just one trial to form a block; what if no current public key satisfies this? The blockchain will eventually stall.
• Let us include the timestamp to try: H(hash(parent.header), timestamp, public key) < threshold
• The number of trials is linear in time.
• There will always be a time when the inequality is feasible.
1. Block content is not tamper-resistant against an adaptive adversary;
2. Public election: vulnerable to bribery/corruption.
Crypto Primitive
• Key-Evolving Signatures (KES)
o pk remains the same
o sk updated in every step, old sk erased
o impossible to forge old signatures with new keys
• KES used for signing blocks
• KES help achieve adaptive security - the chain of past
transaction blocks is essentially immutable.
• But future successful public keys are still predictable!
Crypto primitive
• Should not include the public key in a block.
• Use Verifiable Random Function (VRF) to turn a public election into a
private election.
VRFprove( sk , x ) → ( y , ! ) VRFverify( pk , x , y , ! ) → True/False
• A node with a secret key sk can call VRFprove(sk, ·) to generate a pseudorandom output ysk(·) along with a proof πsk(·). Other can check that the output has been generated by VRF, by calling VRFverify(pk, ·,Fsk(·),πsk(·)).
• The output of a VRF is computationally indistinguishable from a random number even if the public key pk and the function VRFprove is revealed.
VRF(secret key, hash(parent.header), timestamp) < threshold Now good, except for ...
Nothing at Stake
VRF(hash(parent.header), timestamp, secret key) < threshold Longest chain rule
parent is tip of longest chain Adversary deviates
can grow on all blocks (even Genesis)
No computation limit to deviation unlike PoW
We have a Nothing at Stake (NaS) problem!
Honest participants
grow chain as a Poisson process
growth rate linear in time
can (in principle) grow a tree of blocks number of blocks grows exponentially in time how about the height?
allows adversary to compete with honest participants unevenly
NaS Tree G
A scalable PoS blockchain in the open setting, Fan and Zhou, 2016
Longest chain
!"# " is the
adversarial mining rate;
# is the time interval of interest;
! =2.71828.
NaS Tree and Longest Chain
• Under private mining attack, the honest chain grows at rate h; the adversarial tree’s height grows at rate ea.
Security of
Honest participants
grow chain as a Poisson process
growth rate linear in time h" Adversary
grows a NaS tree in private
longest chain length #$"
Assuming the block propagation delay is zero, we have security against the private-mining attack as long as:
The same condition has been proved to guarantee security against all attacks under the zero-delay assumption (proved in Bagaria et al 2020, Dembo et al 2020).
Security against all attacks if h > #$ Can we make “#” smaller or go away?
Key idea: Reduce the number of randomness sources the adversary can grind on.
Idea 1: Only use randomness from genesis block
VRF(hash(Genesis), timestamp, secret key) < threshold
Longest Chain
h>#$ or & < * ≈27% &'( *'+
5 days Epoch 2
Stütz, Rainer, et al. "Stake Shift in Major Cryptocurrencies: An Empirical Study." arXiv preprint arXiv:2001.04187 (2020).
Ouroboros Attack
k+1 bribes for k-deep rule
Security against all attacks
Key idea: Reduce the number of randomness sources Idea 2: c-correlation
the security
Update the randomness of a block only at blocks
with height multiples of c
Bagaria, Vivek, , , Sewoong Oh, , , Xuechao Wang, and . "Proof-of-stake longest chain protocols: Security vs predictability." In Proceedings of the 2022 ACM Workshop on Developments in Consensus, pp. 29-42. 2022.
correlation
Analysis of private
Godfather-block: height(b)%c=0
Only fork at the parents of godfather-blocks
Security guaranteed if h > a !c “c=1/(1+!c): threshold for private NaS attack
Dynamic stake
• Flaw of static stake
o Prevent nodes from leaving and joining
o A coin with no actual stake can participate forever
• What if stake is updated immediately?
o Grinding attack: once the adversary is elected as a leader
at round i, it can include transactions at round i to transfer all stake to a coin that has a higher chance of winning the election at round i + 1
• What if stake is updated with a delay of s blocks?
o Long range attack: have a private chain with s blocks
● Stake is updated with a delay of s blocks
● Chain rule: When comparing two chains, both chains are truncated up to s blocks after the fork. Whichever truncated chain is mined in shorter time (and hence denser) is chosen to be mined on.
truncation
Dynamic availability
Badertscher, Christian, ̌i, , , and . “Ouroboros genesis: Composable proof-of-stake blockchains with dynamic availability.” In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 913-930. 2018.
Deb, Soubhik, , and . “PoSAT: proof-of-work availability and unpredictability, without the work.” In the 25th International Conference Financial Cryptography and Data Security, March 1–5, 2021.
Crypto Primitive
Verifiable Delay Function (VRF)
VDF( sk , x ) → ( y , ! )
Verify( pk , x , y , ! ) → True/False steps
● Proof of sequential work
Takes L steps
Takes much less than L
with arrow
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com