• Created by: smrc
  • Created on: 03-05-19 10:27
What does a hash function do?
a) Takes any string as input b) produces a fixed-size (encrypted) output c) it is efficiently computable
1 of 73
What 3 security properties must a hash function satisfy to be called "CRYPTOGRAPHIC"?
1. Collision-free 2. Hiding 3. Puzzle-friendly
2 of 73
Define the hash property: Collision-free
Formal: Nobody can find x and y such that: x != (not equal) y and H(x) = H(y) Informally: Nobody can find 2 different strings that hash to the same value Note: 2 different strings can hash to the same value but nobody can find them in reasonable time
3 of 73
Give an example of an application of the Collision-free property
Hash as Message Digest. If we know H(x) = H(y), it's safe to assume x=y. To recognise a file we saw before, just remember its hash (e.g. md5 checksum). Useful because hash is small.
4 of 73
Define the hash property: Hiding
If r is chosen from an appropriate probability distribution, then given H(r||x) (the hash of the bits of r and x concatenated), it is infeasible to find x.
5 of 73
Give an example of an application of the Hiding property
Commitment. Commit to a message, m, and reveal it later. Commit: C = H(k||m) where the key, k, is a random 256-bit number.
6 of 73
Given these elements of a commit, can a message be found and if so by whom? 1. C, k, m 2. C
1. Given C, k, m anyone can later verify the message. 2. Given C, m cannot be found
7 of 73
Can 2 different messages be found with the same C (commit)? Why is this important?
No. This is important because the message m cannot be tampered with or repudiated.
8 of 73
Define the hash property: Puzzle-friendly
For every possible output value y, if k is chosen from a high min-entropy distribution, then it is infeasible to find x such that H(k||x) = y.
9 of 73
What is a high min-entropy distribution/appropriate probability distribution?
A high min-entropy distribution is one that is very spread out so that no particular value has more than negligible probability.
10 of 73
What is a Hash Pointer?
A pointer to where some data is stored and a cryptographic hash of the data.
11 of 73
What is the purpose of hash pointers?
A hash pointer allows us to retrieve the data pointed to and verify it hasn't changed.
12 of 73
What is a block chain? Give a use of a block chain and a real world example of its use.
A link-list built from hash pointers. A block chain provides a tamper evident log, used in Bitcoin.
13 of 73
Define a hash pointer in the context of a block chain.
Each hash pointer is a hash of all the previous block.
14 of 73
Explain the concept of Tamper Detection.
Any change in the data of a block can be detected by checking the hash pointer of the next block. To cover up the tampering it would be necessary to change all the hash pointers in the subsequent blocks. If the hash pointer at the head of the list is
15 of 73
How would you ensure that the list is tamper evident?
If the hash-pointer at the head of the list is tamper-free, then all the list is tamper-evident.
16 of 73
In which data structures can hash pointers be used?
Any (pointer-based) data structure that has no cycles.
17 of 73
What is another name for asymmetric cryptography?
Public Key Cryptography
18 of 73
What combination of keys is used in public key cryptography?
2 keys (a pair), a public key to encrypt and a private key to decrypt (or vice versa).
19 of 73
Describe the relationship between a public key, private key and a message.
Public and private keys are pairs such that a message encrypted with the public key can only be decrypted with the private key of the pair (and vice versa). Infeasible to find the private key from the public key.
20 of 73
Explain the difference between the public key and the private key.
Public key is available/visible to all. Private key only know by its owner.
21 of 73
Explain the process of encryption and decryption in Public Key Cryptography where the sender encrypts with a public key.
1.Sender encrypts message with public key of recipient. 2. Recipient decrypts it with their private key. 3. Only a holder of the private key can decrypt the message. 4. PROVIDES SECURE MESSAGE TRANSMISSION.
22 of 73
Explain the process of encryption and decryption in Public Key Cryptography where the sender encrypts with their private key.
1. Sender encrypts message with their private key. 2. Message can only be decrypted with sender's public key. 3. This verifies the sender and provides non-repudiation.
23 of 73
Non-repudiation ensures that the sender of a message can not deny the creation of the message. (message authentication)
24 of 73
List the disadvantages of public key cryptography.
1. Slow. 2. Cannot be sure of the identity of the sender of a message via public key, as everyone knows this key.
25 of 73
Briefly describe what a Digital Signature is and what it is used for.
1. When a message is sent, a hash function is used to create a message digest. 2. This is encrypted with the sender's private key to create a Digital Signature. 3. Achieves authentication and data integrity.
26 of 73
What is the purpose of a digital signature?
It emulates the conventional signature, verifying to a 3rd party that a message is an unaltered copy produced by the signer.
27 of 73
What is a message digest and what is it used for?
A fixed-length digest (i.e. encrypted summary) of the data produced from a cryptographic hash. It is a secret (known only by signer) bound irreversibly to the message. Encrypted by using signer's private key (to maintain authentication and integrity)
28 of 73
Explain the process of attaching a digital signature to a message.
1. Data 2. Hash function 3. Message digest 4.Sender's private key 5. Digital Signature
29 of 73
Explain the process of verifying a digital signature.
Receiver can: 1. Create message digest from original message using same hash function. 2. Decrypt the original message-digest with the sender's public key. 3. Compare the message digests - if the same then sender is verified and message not altered.
30 of 73
Which Digital Signature standard is used in Bitcoin?
ECDSA - Elliptic Curve Digital Signature Algorithm. Good randomness essential for this algorithm else private key could be compromised.
31 of 73
Public Key = Identity. Explain this concept.
If you can verify a digital signature for a message, m, using the public key, p then i.e. p says "m". p is an identity. To control the identity p you must know the corresponding private key (owner). No need to reveal "real" identity.
32 of 73
Define 'Decentralised Identity Management'. What does this mean for identity creation? Name a 'real life use' of this system.
Decentralised Identity Management = no central point of coordination. Anyone can make a new identity any time they want by creating a new private/public key pair. Used in Bitcoin, where identities are referred to as addresses.
33 of 73
Describe how Double-Spending can occur in a simple cryptocurrency system.
GoofyCoin. Goofy creates coin, pays A. She pays B. Then she pays C using the same coin. Both of the transactions are signed by A. C doesn't realise that the coin was already sent to B, they both claim the coin, both claims valid as chain traced to G.
34 of 73
Describe how a centralised system can solve Double-Spending.
Scrooge - central manager. He publishes the history of all the transactions in a block chain. History is signed by Scrooge. Anyone can check blocks. Scrooge then signs head hash pointer and publishes it. Anyone can follow history to verify.
35 of 73
What makes ScroogeCoin centralised?
Scrooge in control of createCoin transaction and published history.
36 of 73
Describe the createCoin transaction.
Scrooge creates coins. This transaction has transationID and 3 outputs :coinID (of transaction), Value and Recipient.
37 of 73
Describe the function of the PayCoins transaction.
It consumes and destroys some coins, and creates new coins of the same total value.
38 of 73
How would you check if a PayCoins transaction is valid?
Valid if: 1. Consumed Coins are valid 2. Not already consumed 3. Total value is conserved 4. Signed by the owners of all the consumed coins.
39 of 73
What does it mean if coins are immutable?
Coins can't be transferred, subdivided or combined. But using the PayCoins transaction can fix this. Subdivide: consume your own coin and pay back 2 coins with same total value. Combine: Inverse.
40 of 73
Using the PayCoins transaction how can you transfer immutable coins?
Consume your coin and assign a new coin of the same value to someone else. Can give change.
41 of 73
State the 4 requirements of a Decentralised Cryptocurrency.
1. Need to be able to agree on published blockchain of history of transactions 2. Need to agree on which transactions are valid 3. Need to assign IDs in a decentralised way 4. Need mechanism to create new coins.
42 of 73
State the key technical challenge of any decentralised cryptocurrency. And explain how this issue is resolved.
How to achieve DISTRIBUTED CONSENSUS. A protocol for DC terminates when all correct (not malicious) nodes decide on the same value. This value must have been proposed by a correct node.
43 of 73
In general terms, why is consensus hard to achieve?
1. Nodes may crash 2. Nodes may be malicious 3. Network is not perfect (a. Not all pairs of nodes are connected b. Faults in network c. Latency (NO NOTION OF GLOBAL TIME))
44 of 73
What are the two approaches that Bitcoin uses to achieve consensus?
1. Introduces incentives (currency) 2. Embraces randomness (a. confidence in a transaction being accepted as valid is probabilistic b. Consensus happens over long time period - 1hr.)
45 of 73
Briefly explain why Bitcoin is considered to be a P2P system.
When person A wants to pay person B she broadcasts the transaction to all Bitcoin nodes. Similar transactions are broadcast to the Bitcoin nodes all the time.
46 of 73
What attack can be carried out by a malicious node in Bitcoin?
A double-spend attack.
47 of 73
Briefly explain, in general terms, what can be used to incentivise honesty in Bitcoin nodes?
Currency has value. Can use this to incentivise honest behaviour. Pay honest nodes with Bitcoin.
48 of 73
Name two incentives used in Bitcoin.
Block Reward and Transaction Fees.
49 of 73
Briefly explain the Block Reward incentive.
Creator of a block gets to: 1. Include special coin-creation transaction in the block 2. Choose recipient address of this transaction. Value of reward is fixed but halves every 4 years. Reward paid only if block ends up on long term consensus chain.
50 of 73
What is the issue with the supply of Bitcoin?
There's a finite supply of bitcoins (total = 21 million). Runs out in 2040. No new bitcoins unless rules change. Block reward is how new Bitcoins are created.
51 of 73
Briefly explain the Transaction Fees incentive.
Creator of transaction can choose to make output value less than input value. Remainder is TF that goes to block creator. Voluntary (tip). As block reward declines with time TF will become more important in achieving good quality of service.
52 of 73
Define a Sybil attack and give an example of when it could be used.
A Sybil attack is where a malicious adversary creates many identities to make it look like there are lots of participants. Consensus based on voting open to this.
53 of 73
Briefly describe how Bitcoin randomly selects which node adds the next block.
Bitcoin uses Proof-of-Work. To approximate selecting a random node we select nodes in proportion to a resource that nobody can monopolise (we hope). Proof-of-Work is in proportion to computing power.
54 of 73
Define Proof-of-Stake.
Proof-of-Stake is selecting a random node in proportion to ownership. Not used in Bitcoin.
55 of 73
How does Proof-of-Work pick random nodes?
Select nodes in proportion to computing power.
56 of 73
How does Proof-of-Work avoid a free-for-all due to rewards?
Lets nodes compete for a right to create block.
57 of 73
How does Proof-of-Work prevent Sybil attacks?
Makes it moderately hard to create new identities.
58 of 73
Define Hash Puzzles and explain how they are used as a Proof-Of-Work.
To create a block, a node must find a nonce such that H(nonce||prev_hash||tx||...||tx) is very small. tx - transactions in the block. || - concatenate bits. prev_hash is hash pointer to previous block.
59 of 73
What algorithm is used to solve the hash puzzles?
BRUTE FORCE algorithm - If hash function is secure, the only way to succeed is to try enough nonces until you get lucky. e.g. If target space is 1% of output space, we would expect to have to try 100 nonces to get one that satisfies the requirement.
60 of 73
Briefly explain the process of node selection with the Proof-of-Work approach.
1. No central authority picking a random node to create the next block. 2. Instead, nodes compete to solve hash puzzles, and first to succeed creates the next block.
61 of 73
What property gives an advantage to a node when solving hash puzzles?
Hash puzzle can only be solved by brute force algorithm, so the more computer power a node has, the quicker it can solve the puzzles.
62 of 73
Name the three properties of the Proof-of-Work approach.
1. Difficult to compute. 2. Parameterizable cost 3. Trivial to verify
63 of 73
Explain the first property of Proof-Of-Work: Difficult to compute.
As of August 2014: about 10^20 hashes per block. Only some nodes bother to compete (Bitcoin miners).
64 of 73
Explain the first property of Proof-Of-Work: Parameterizable cost.
Nodes automatically re-calculate the target every 2 weeks. As the global computer power devoted to Bitcoin mining increases, the time between blocks tends to decrease. Goal: average time between blocks = 10 mins.
65 of 73
What is the probability that Person A will win the next block?
Prob(person A wins next block) = fraction of global hash power she controls.
66 of 73
What is a key security assumption we make when considering the PoW property: Parameterizable cost?
Attacks are infeasible if majority of miners, weighted by hash power follow the protocol (are honest). In this case the next block is more likely to come from an honest node, rather than a malicious one.
67 of 73
For an individual miner, how would you calculate the mean time to find a block?
Mean time to find block = 10 mins / fraction of hash power.
68 of 73
Explain the first property of Proof-Of-Work: Trivial to verify.
1. Nonce must be published as part of a block. 2. Other miners simply verify that H() with nonce < target. 3. No need for central authority to check if puzzle is solved correctly.
69 of 73
Define the mining economics of Bitcoin.
If mining reward (block reward and transaction fees) > hardware + electricity cost --> Profit
70 of 73
What are the complications to consider in Bitcoin mining economics?
1. fixed vs. variable costs 2. Reward depends on global hash rate, which depends on fraction of global hash power controlled. 3. Reward depends on Bitcoin exchange rate.
71 of 73
What are the 3 types of consensus in Bitcoin?
1. Value of exchange rate 2. State (which transactions are valid as recorded by blockchain). 3. Rules - sometimes these may need to change.
72 of 73
How is Bitcoin bootstrapped (self-sufficient)?
1.Security of block chain 2. Value of currency 3. Health of Mining Eco System
73 of 73

Other cards in this set

Card 2


What 3 security properties must a hash function satisfy to be called "CRYPTOGRAPHIC"?


1. Collision-free 2. Hiding 3. Puzzle-friendly

Card 3


Define the hash property: Collision-free


Preview of the front of card 3

Card 4


Give an example of an application of the Collision-free property


Preview of the front of card 4

Card 5


Define the hash property: Hiding


Preview of the front of card 5
View more cards


No comments have yet been made

Similar Computing resources:

See all Computing resources »See all Emerging Technologies resources »