Basic cryptography and Nakamoto consensus
Cryptographic hash function
• A hash function is a function that o takesanystringasinput,
o has fixed-size output (we’ll use 256 bits), and
Copyright By PowCoder代写 加微信 powcoder
o is efficiently computable.
• A cryptographic hash function H( ) has additional security
properties:
Computationally no one can find x and y such that
x != y and H(x)=H(y)
Hash pointer
• hash pointer is:
* pointer to where some info is stored, and * (cryptographic) hash of the info
• if we have a hash pointer, we can * locate the info, and
* verify that it hasn’t changed
Blockchain
is a linked list with hash pointers
prev: H( )
prev: H( )
prev: H( )
Tampering one block changes the hash values in all subsequent blocks.
What we want from signatures
• Only you can sign, but anyone can verify;
• Signature is tied to a particular document, can’t be cut-and-
pasted to another one.
Public key cryptography API
• (sk, pk) := generateKeys(keysize) sk: secret signing key
pk: public verification key
• sig := sign(sk, message)
• isValid := verify(pk, message, sig)
can be randomized algorithms
• Easy to verify(pk, message, sign(sk, message)) == true
• Computationally impossible to forge signatures.
Decentralized blockchain
• Block: Header + Data + Signature
• Header: Pointer to previous block
= hash of the previous block header and (Merkle root of) data of previous block
• Data: information specific to the block
• Signature: a user signs the block (header+data)
Distributed consensus
• Question: Who maintains the ledger of transactions?
• Distributed Consensus
o Interactive protocol
o Allows distributed non-trusting nodes to reach agreement o Decades of research on “Byzantine Fault Tolerance”
• Permissionless systems also allow decentralized identity.
o Public keys serve as identities
o If one participant can create arbitrary number of identities, need to address the “sybil attack”. One-identity-one-vote is not safe.
Network assumption
• Model 1: Fully connected – everyone can send a direct message to everyone else.
• Model 2: Connected – everyone can reach everyone else via relays (possibly via multiple paths).
• If the network is not connected, nodes cannot reach new agreement.
• Zero delay: if every message reaches the destination with no delay.
• Bounded delay: if every message reaches the destination within a certain delay. Also referred to as synchrony in the BFT literature.
Oracle and proposer
• Oracle selects one of the nodes (public identities) o at random
o everyone can verify the unique winner If the network is not connected, nodes cannot reach new agreement.
• The selected node is the proposer in that slot. It may o assemble a block with validated transactions
o includes hash pointer to previous block o signs the block
o broadcast the block
• Simulated by a distributed lottery. There is a chance multiple nodes win the same lottery.
• Time is slotted.
• Need fairness to all participants.
• Need to be unpredictable. (Predictable winners are easier to bribe.)
• In each slot, each node is chosen with probability q, independent of other nodes, independent of the history.
• The rate of block production is (nq).
• With n nodes in total, if (nq<<1), then with high probability no more than one node is selected in each slot.
time probabilistic model
Continuous
time Poisson point
• When (nq) is very very small, a continuous-time model is very very accurate, and often easier to work with.
• The mining times of blocks form a Poisson point process.
• Nt is a Poisson point process with rate h if:
o It has independent increments over time; o It is stationary;
o As t->0,
P(Nt=0)=1- h t + o(t) P(Nt=1) = h t + o(t) P(Nt>1) = o(t)
• For t>s, Nt-Ns is a Poisson random variable with mean (t-s)h.
Proof of work simulates oracle
o cryptographic hash function creates computational puzzle
o Hash(nonce, block-hash) < Threshold o nonce is the proof of work
o include nonce inside the block
• Threshold
o chosen such that a block is mined successfully on average
once in 10 minutes
o a successfully mined block will be broadcast to all nodes in the network
Properties of
• Random miner selected at each time
• Independent randomness across time and across miners
• Probability of successful mining proportional to fraction of total hash power
• Sybil resistance
• Spam resistance
• Tamper proof
Longest chain protocol
Where should the mined block hash-point to?
Blockchain may have forks
because of network delays
because of adversarial action
Longest chain protocol
attach the block to the leaf of the longest chain in the block tree what if two equal length chains?
Security Analysis: Private Attack
Adversary can point its block to an older part of the chain
Duplicate transaction inserted
Plausible Deniability
network latency
an offline user will not know which block came earlier blocks have no wall clock reference (time stamps).
Security Analysis: k Deep Confirmation Rule
Satoshi’s Table
Security vs latency (Bitcoin)
Assume all block propagation delays are under 10 seconds.
90% honest
75% honest
30 40 50 60 confirmation depth k
probability of safety violation
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com