程序代写代做代考 data structure algorithm chain 17crypto_L11

17crypto_L11

Crypto Currencies

Crypto & SecDev 2017 © Ron Poet: Lecture 11 1

Barter

� Initially each group of humans produced everything they
needed.

� At some point it became more efficient to specialise.
�One person produces food, the other tools, for example.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 2

�One person produces food, the other tools, for example.
� They need to agree on the relative values of their produce

so that they could exchange them fairly.
�The barter system.

� This only works with a small number of different products.
�Otherwise there are too many different relative values

to remember.

Gold

� It is easier to agree the value of each product in terms of
one special product.
�Gold, for example.

� The relative values of other products can be easily

Crypto & SecDev 2017 © Ron Poet: Lecture 11 3

� The relative values of other products can be easily
calculated from their values in terms of gold.

� Transactions can work over distance and time.
�Convert one product to gold.
�Later, convert the gold to the other product.

� The special product (gold) has to be rare!
�Stones won’t work because it is easy to cheat.

Cash

� Gold is heavy and difficult to transport, when buying
expensive items.

� A piece of paper can substitute for gold.
�Provided it can’t be forged.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 4

�Provided it can’t be forged.
�It must be guaranteed by a trusted authority.
�It can be converted back to gold.

� The authority can increase the amount of cash in
circulation by printing notes without the gold behind them.
�This can lead to inflation and collapse of the currency if

not done wisely.

Credit

� Cash needs an initial production of some goods before a
person can start trading.

�A farmer needs to sell surplus food before they can buy
a plough.a plough.

� Credit lets them buy the plough first, promising to pay the
money back later after they have sold surplus food.

�Needs trust that it will be repaid.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 5

Digital Cash

� Digital cash is like other cash.

�We need to buy some initial digital coins with another
form of money before we can spend them.

� Preventing forgery is harder because it is easier to � Preventing forgery is harder because it is easier to
duplicate a sequence of bits.

� Anonymity is harder since anything that happens online
can leave a trace.

� The easiest ways of implementing digital cash use a trusted
central authority.

�There is little advantage over just using a bank.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 6

Crypto Currencies

� They use a peer to peer system and don’t have a central
authority.

� This requires enough of the nodes to agree on which
transactions have happened.transactions have happened.

�How are disagreements resolved?

� They also need techniques to prevent forgery and double
spending.

� They should also prevent a denial of service attack,
preventing someone from spending their money.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 7

Goofy Coin

� Examples from “Bitcoin and Cryptocurrency
Technologies” Narayanan, Bonneau, Felten, Miller,
Goldfelder.

� Coin Creation:� Coin Creation:

�Goofy generates a unique coin ID.

�He creates a transaction: CreateCoin, CoinID and signs
it with his secret key.

� Spending: Alice gives coin to Bob

�Alice creates a transaction: PayTo, CoinID, Bob and
signs it with her secret key.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 8

Goofy Coin (2)

� If Bob wants to prove he owns the coin

�He presents the transaction where Alice gave the coin
to him.

�He presents the transaction where someone gave the �He presents the transaction where someone gave the
coin to Alice.

�. . .

�He presents the transaction where Goofy created the
coin.

� He can do all of this if he has the public keys of everyone
who is involved.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 9

Goofy Coin (3)

� This is vulnerable to double spending.

� Alice can sign a transaction where she gives the coin to
Carol.

� There are now two transaction involving the same coin.� There are now two transaction involving the same coin.

� Which is the genuine one?

� Also, Goofy, but only Goofy, can create as many coins as
he likes.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 10

Scrooge Coin

� This is similar to Goofy Coin, but Scrooge publishes a
ledger with all transactions that have ever taken place.

� He must sign all the transaction, so that only he can add to
the ledger.the ledger.

� The transactions must be in time order, so that it is
impossible for anyone, including Scrooge, to insert a
transaction at an earlier date and change the past.

� The ledger prevents double spending.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 11

Scrooge Coin: Transactions

� Create Coin: Creates many coins with different people as
owner. Signed by Scrooge.

� Pay Coins: Some coins are destroyed and new coins to the
same value are created and given to various recipients. same value are created and given to various recipients.
Signed by all people whose coins are destroyed.

� The transaction amounts don’t have to be whole coins.

�Alice can destroy 1 coin and pay Bob 0.7 of a coin.

�She can also pay herself 0.3 of a coin and get change.

� The problem is that it is centralised and relies on trusting
Scrooge.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 12

Cryptographic Hashes

� Hash functions are used to generate message digests.

� Collision Resistant: Can’t find two different documents
that have the same hash values.

� Hiding: Can’t find the original input from the hash value. � Hiding: Can’t find the original input from the hash value.
They are one-way functions.

� Puzzle Friendliness: If part of the input is know, it is still
hard to find the rest of the input.

�The known part must be from a random distribution
with enough entropy.

�This is used for Bitcoin Mining.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 13

Linked List

� A linked list is a basic data structure where a series of data
blocks are linked together.

� Each block points to the next one in the chain.

� It is possible to get to all of the blocks if we start with a � It is possible to get to all of the blocks if we start with a
pointer to the first block in the list.

� If each block also contains a hash of the previous block
then it is called a Block Chain.

� It is not possible to insert a block in the middle of the list.

�The hashes would disagree.
Crypto & SecDev 2017 © Ron Poet: Lecture 11 14

Binary Tree

� This is like a linked list, but each block has pointers to two
other blocks.

� In a sorted binary tree, the left and right linked blocks are
in sorted order.in sorted order.

� It is possible to find a block, or prove that a block is not in
a sorted tree, must quicker than a linked list.

�Not all the blocks need to be checked.

� Each block in a binary tree can also contain the hashes of
the two linked blocks. It is then called a Merkle tree.

�It is impossible to insert a block in the tree afterwards.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 15

The Bitcoin Ledger

� The bitcoin ledger is based on hashed linked lists and
Merkel trees.

� The hash function used is SHA-256

� It also uses digital signatures to sign all the transactions.

� It uses the Elliptic Curve Digital Signature Algorithm,
which is a variant of the Digital Signature Algorithm,
which is itself a variant of the El Gamal digital signature
algorithm.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 16

Distributed Consensus

� Bitcoin does not have a centralised authority.

�There are a large number of nodes, all with equal
status.

�They all have a copy of all the bitcoin transactions that �They all have a copy of all the bitcoin transactions that
have ever happened.

� Nodes can come and go at any time.

� New transactions are taking place all the time.

� All nodes need to agree on which transactions are valid.

� Some of the nodes can be malicious and try and steal
bitcoins.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 17

Alice Spends Money with Bob

� Alice creates a transaction with:

�The coin she is going to destroy.

�Creating a new coin going to Bob. Its value must be
less than or equal to the value of the coin she is less than or equal to the value of the coin she is
destroying.

�Creating a new coin going to her. Her change.

� She signs the transaction with her secret key.

� She sends the transaction to all the bitcoin nodes.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 18

Alice Spends Money with Bob (2)

� Bob can get a historical ledger from any one of the bitcoin
nodes and verify that Alice owns the bitcoin she is using.

� He traces all the transactions back to the creation of a
bitcoin.bitcoin.

� He works backwards through all of the relevant
transactions.

� The use of Merkle trees makes this process fast enough.

� If he can’t find the coin or it does not lead back to a Create
Coin transaction then he can reject the sale.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 19

Alice Spends the Same Money with Carol

� What is to stop Alice spending the same bitcoin with
Carol?

� How can Bob, or Carol, discover if the coin has already
been spent?been spent?

� How quickly does it take for Alice’s transaction to get into
the historical ledger?

� It will take some time, and so Bob should hold off from
dispatching the goods to Alice for a while.

�How long will this take?

Crypto & SecDev 2017 © Ron Poet: Lecture 11 20

What Happens with a New Transaction

� Transactions are not added to the blockchain immediately.

� Each node has a collection of recent transaction in addition
to the blockchain of completed blocks.

� Every now and then it collects all the transactions into a � Every now and then it collects all the transactions into a
new block, ready to add it to the chain.

� All nodes are doing this, but only one version is added.

� Even if all the transactions are the same, different nodes
can produce different versions of the new block.

�The transactions can arrive in a different order because
of network latency.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 21

A New Block is Chosen

� One node is chosen and its new block is submitted to all
the other nodes to be added to their chain.

�More on how the node is chosen later.

� Nodes check all the transactions in the proposed block � Nodes check all the transactions in the proposed block
with their collection of new transactions.

�If they match then the node adds the block to its
blockchain.

�If they don’t match then it is not added.

� Different nodes can have different versions of the ledger!

Crypto & SecDev 2017 © Ron Poet: Lecture 11 22

Mismatch: Network Delays

� A node may reject the proposed new block because one of
the transactions has not arrived yet.

� The transaction will eventually arrive.

� It can then add two new blocks when the next block � It can then add two new blocks when the next block
proposal is made.

� So recent transactions may take a bit of time to be added in
all versions of the ledger.

� The most recent part of the blockchain can be inaccurate.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 23

Mismatch: Cheating

� The node proposing the new block might be trying to cheat
and add an invalid transactions.

� The new block will be rejected by the honest nodes.

� Only a small number of nodes will include the cheating � Only a small number of nodes will include the cheating
transaction.

� A client application just needs to check a few versions of
the ledger to get the true picture.

Crypto & SecDev 2017 © Ron Poet: Lecture 11 24

Sybil Attack

� A Sybil attack is where a rouge node creates a large
number of copies of itself.

� The aim is to increase the probability that a rouge node
will be chosen to propose the next block.will be chosen to propose the next block.

� It also aims to generate a false consensus.

� It is a common attack again peer-to-peer networks that
need to arrive at a distributed consensus.

� Bitcoin has a mechanism to prevent a Sybil attack.

Offline Nodes

� Nodes can miss transactions if they are offline when a
transaction is broadcast.

� They can check a number of other nodes to bring their
version of the ledger up to date.version of the ledger up to date.

� They can then start building their collection of transactions
again.

How Long to Wait?

� Bitcoin creates a new block every 10 minutes on average.
� The actual time can vary.
� Just the top blocks in a node’s version of the blockchain

are volatile.are volatile.
� The older ones have settled down because any time delays

have been resolved.
� A general rule of thumb is to wait for 6 new blocks (1

hour) before accepting a transaction as valid.
� This prevents Alice from spending the same bitcoin twice.
� Only one of Bob and Carol will have a valid transaction.

New Block Rewards

� A node that has its new block accepted on the long term
consensus chain is rewarded with 25 bitcoins.

� This is an incentive to create an honest new block.

�If the majority of nodes don’t accept the new block �If the majority of nodes don’t accept the new block
then the node proposing the new block will not get its
25 bitcoins.

� This is the only way new bitcoins are created.

Finite Total Number of Bitcoins

� The new block reward halves every time 210,000 new
blocks have been created.

�210,000 x 10 minutes = about 4 years.

� This is a geometric series and so has a finite sum.� This is a geometric series and so has a finite sum.

�21 million bitcoins.

� No appreciable number of new bitcoins will be created
after 2140.

Transaction Fees

� An alternative way of rewarding the creation of new
blocks is a transaction fee.

� The creator of a transaction can specify a transaction fee.

�Taken from the spender.�Taken from the spender.

�Given to the node creating the new block.

� This is likely to become more important as the new bitcoin
reward gradually declines.

Choosing the New-Block Node

� A node must be the first to solve a computationally
intensive puzzle before its new block is chosen.

� This defeats a Sybil attack.

�The winner is dependent on their available computing �The winner is dependent on their available computing
power, not the number of nodes they control.

� It is a way of choosing a random node without a central
random-node authority.

� This is bitcoin mining.

Hash Puzzles

� Bitcoin uses a hash puzzle as its computationally intensive
problem.

� The node concatenates the hash of the previous block and
hashes of all the transaction in the new block, in order, to hashes of all the transaction in the new block, in order, to
create a new string.

� It then adds an unpredictable string – a nonce, to the string.

� It then calculates the hash of this big string.

� If the hash values falls in a small range of allowed values
then it has solved the puzzle.

� It is trivial to verify the solution.

Hash Puzzles (2)

� This type of puzzle can only be solved with a brute force
attack.

� This is a property of hash functions and the fact the all the
hash values form a random distribution.hash values form a random distribution.

� Currently roughly 1 in 1020 hash puzzles attempts will be a
solution.

How Hard are the Hash Puzzles

� All nodes automatically adjust the size of the target space
after each new block is added to make sure that it takes on
average 10 minutes for a hash puzzle solution to emerge.

� If more computing power is devoted to bitcoin mining then � If more computing power is devoted to bitcoin mining then
the puzzles get harder!

Attack: Stealing a Bitcoin

� Alice can’t steal one of Bob’s bitcoins because she can’t
sign a transaction when it is spent.

� This is a cryptographic security measure.

Attack: Double Spending

� Alice can create two transaction spending the same bitcoin
with both Bob and Carol.

� If Bob and Carol are cautious merchants, they will wait
and hour or so and then make sure that their transaction and hour or so and then make sure that their transaction
has made it to the long term ledger.

� The chance of Alice getting away with it are remote but
not impossible.

� If they hand over the goods straight away then Alice can
get away with it.

� Bitcoin transactions are anonymous.

Attack: Denial of Service

� Alice really doesn’t like Bob and every time she gets to
propose a new block she doesn’t include any of his
transactions, making his bitcoins useless.

� Her new blocks will not be accepted as the consensus and � Her new blocks will not be accepted as the consensus and
so she does not get the new block reward.

� All her expense of bitcoin mining is wasted.

Related Posts