deltadeltaandmoredeltas

These are my notes of the eighth lecture from Coursera’s Bitcoin and Cryptocurrency Technologies during Dec 2016 – Feb 2017. While the lecture is lengthy and I had to watch it a few time to grasp the concepts, I thought it was interesting.

Questions answered in this Post:

• What is bitcoin’s stance on node identity? Why?
• What is a Sybil attack?
• What is implicit consensus?
• What are some attacks discussed that this consensus protocol protects against?
• What is an orphan block?
• What is a zero-confirmation transaction and how to prevent it?

One major point was that bitcoin nodes do not have persistent long-term identities. Because of this, the consensus protocol attributes deviate from what is in the distributed systems consensus protocols. So, while we know that bitcoin is different, why exactly do we care? One thought is that because of this deviation, does this mean the existing algorithms are not compatible and thus something new have to be invented? Why are identities useful for distributed consensus protocols?

Below are the specific examples provided in the lecture:
Pragmatic: some protocols need node identification (id) such as a protocol could say use the lowest ranked ID to do .
Security: assume less than 50% malicious nodes for this protocol to work.
Prevent from a Sybil Attack An adversary makes multiple nodes and uses them to break the system.

Why don’t Bitcoin nodes have identities?

1. Since Bitcoin is a P2P system, no central body to assign identities to nodes
2. Pseudo-anonymity is actually an inherent gol of bitcoin

So instead of that, Arvind suggested something weaker in that the system is able to pick a random node in the system as well as determine who is the owner thus making the all Sybils get a single token. With this procedure then something called implicit consensus can occur.

Implicit Consensus (AKA Simplified Bitcoin Consensus algorithm)

It’s a procedure of adding new blocks to the blockchain in consensus.

1. Random node is selected and make it
2. proposed the next block in the chain
3. Other nodes accept or reject the block by determining whether or not to build on top of it
4. If accept, then this block gets added. If reject, they ignore the block and build over the current chain they have.
5. Nodes acceptance means adding the block’s hash in the next block they create

Why does this work? or how can a malicious adversary subvert the process?

• Stealing Bitcoin – not if the underlying crypto is good
• Denial of Service Attack – not unless all other nodes are malicious
• Double-spend attack – add the heuristic that only add to the longest block

Can Alice simple steal Bitcoins belonging to another user at a different address that she doesn’t control?
Example:
It is not Alice’s turn to propose the next block in this chain.
She can’t steal other bitcoins because she can’t forge their signatures and thus if the underlying crypto is solid, one cannot simple steal Bitcoins

If she hates a node Bob, she can choose not to accept any blocks proposed by Bob. So she’s denying service to Bob.

Thus if Bob’s block doesn’t make it into the next block Alice proposes, he will just wait another block until an honest node gets the chance to propose.

Arvind claims this is nothing more than a little annoyance. I guess in my mind it was larger. First with this little annoyance, I see it as a delay since you’re waiting for the next honest node. The next honest node could take a very long time.

The last one Arvind talks about is the double spending attack.

Alice is a customer of a merchant and Bob is the seller.
Alice goes to Bob’s website and buys for it in Bitcoins.
She creates a Bitcoin transaction from her address to Bob’s address.
Thus it gets broadcasted to the network

C_A -> B

transaction
signed by A
pay to pk_B: H()

This transaction should have existed from a previous transaction. Thus there’s a pointer to that previous block.

Let’s say Alice is now proposing a transaction, decides to ignore the bock with Bob’s stuff and create a new transaction

transaction
signed by A
pay to pk_A: H()

Will they both end up in the long term consensus chain

There is an idea that the honest node will extend the longest valid branch. From the facts of the transaction, both leafs have the same number of transactions. They have the same length.

There is a heuristic where you choose the node that you received first. Thus there is a chance that the other block would get chosen, so what happens with Bob.

The chain with Bob meant that Alice got free software and Bob did not get any payment. The remainder block is called an orphan block.

Thus this would be a successful double spend.
Zero-confirmation transaction Bob would send over the software without waiting to see if Alice’s transaction actually made it into the blockchain. It’s like giving someone a product with only seeing that they have the money in their hand and that they hadn’t actually given it to you.

However, instead Bob should be more careful. He should wait for more confirmations before sending the software. Because he knows that the longer chain gets chosen, then he’s in the clear if he sees that his transaction has more blocks

Double spend probability decreases exponentially with # of confirmation
Most common heuristic: 6 confirmations

Recap

• protection against invalid transactions is cryptographic but enforced by consensus
• Protection against double-spending is purely by consensus
• You’re never 100% sure a transaction is in the consensus branch. Guarantee is probabilistic. 1- (1/2)^6 = .9844

What can a malicious node do?
Ignore the longest valid branch rule when proposing a new block.

These are my notes of the sixth lecture from Coursera’s Bitcoin and Cryptocurrency Technologies during Dec 2016 – Feb 2017. This lecture seemed more like a teaser to the follow up lectures in that much of what was discussed was evaluating the phrase ” Bitcoin coin is decentralized”. What parts of bitcoin are actually decentralized and where are the limitations?

Questions answered in this Post:

• Where does decentralization currently?
• Why is centralization vs. decentralization more a spectrum as opposed to an “all of nothing”?
• When you think “bitcoin decentralized?”, what components support this thought and what go against this notion?

At this point, the last lecture made clear why centralization did not work for bitcoin. Do we really trust Scrooge? NO! His name is Scrooge…

Arvind goes into how bitcoin works with this decentralization. Decentralization is not all-or-nothing. Email is a decentralized protocol (SMTP) but has been dominated by centralized webmail services. Some examples would be like google/hotmail/yahoo.

Questions regarding the decentralization in Bitcoin?

1. Who maintains the ledger?
2. Who has authority over which transactions are valid?
3. Who creates new bitcoins?
4. Who determines how the rules of the system change?
5. How do bitcoins acquire exchange value?

I’ll put in what my answers were prior to the lectures.

1. Some majority of people on the network. When I say network, I guess there is a group of people (IP addresses/public keys) online who have copies of the ledger that they are constantly pinging out.
2. This majority. Perhaps several people have to say yes this transaction is valid. Since these people are perhaps trusted in other networks then they can check the transactions.
3. Miners create bitcoins. I’m not sure who they are or what they are doing besides running massive computations solving math puzzles.
4. Same answer as number 1.
5. Similar to any other traded security product.

Aspects of decentralization in Bitcoin

• Peer-to-peer network: open to anyone, low barrier to entry
• Bitcoin Mining: open to anyone, but inevitable concentration of power in the Bitcoin mining community
• Updates to the software: core developer trusted by the community have great power.

Bitcoin has a peer to peer network meaning that anyone can log on to start up a full node. Thus there is a low barrier to entry and is it open to anyone. While it is open to everyone, there is quite a bit of disc consumption required. This Bitcoin.com link from Feb 2017, indicated that one user calculated their cost to be approximately $20.00/month to run a node using AWS. Since I have never run a full Bitcoin node, I can neither confirm or deny this statement. Another reason it is decentralized in that anyone can mine bitcoin theoretically. However, if you don’t have special hardware and are not part of a mining pool, there is a low probability of success. Lastly was the point regarding updates to the software. This task falls on the core developers who are trusted and supported by the bitcoin community.

Hash Pointers

These are my notes of the fourth lecture from Coursera’s Bitcoin and Cryptocurrency Technologies during Dec 2016 – Feb 2017. The lecture gave me insight on some of the inner workings of blockchain which I greatly enjoyed.

Questions answered in this Post:

• What is a hash pointer?
• Once you have a hash pointer, what can you do with it?
• What is the tamper evident property?

Hash Pointer

Simply, a hash pointer is a kind of data structure that contains two parts

• pointer to where some info is stored
• (cryptographic) hash of the info

One feature of a hash pointer is we can ask to get the info back and verify that the information hasn’t changed. If you’re familiar with basic C programming, the word pointer should be very familiar. Hash pointers are similar to regular pointers which provide the memory address of some information and through the pointer you can access this information when you dereference it.

key idea: build data structures with hash pointers

Linked List with hash pointers

According to CLRS, a linked list is a data structure in which the objects are arranged in a linear order. A singly linked list contains an object with an attribute key and a next pointer. The head of the linked list is a hash pointer.

Tamper Evident Log – log data structure that contains lots of data
If someone messes with data earlier in the log, we want to be able to detect it.

Why does the block chain have this property?

If someone messes with a block in the middle of the chain. If he changes the data, then the hash generated for this block which is stored in the previous node also would need to change. So even though the hash of the previous block and the data block line up, the previous previous block next pointer is based on a hash of the previous block. Because the previous block is composed of both the data and previous Hash (which has a change) these would also indicate tampering. Thus the only way to make this block well is if you change the entire blockchain but at that point then the head of the block chain is incorrect and since this is the value that the users store, the user would be able to detect the tampering.

The head of the block chain is known genesis block.

Binary tree with hash pointer (Merkle Tree)

One takes consecutive pairs of data blocks and computes the hash of them. Thinking about a tree, you combine each pair of leaves to create a code. Combine the two blocks to create two hash pointers. Then, from those two hash pointers which were created from the left and right child, you make a hash pointer of that block where you point to the data. This occurs recursively until you get to some head hash pointer which as previously is what you store.

Bonus: You only need O(logn) data since you need to know the path of the block from the head to the leaf (data).

Advantage of the Merkle Tree

• Tree holds many items but only need to remember the root (I think you get that from the linked list)
• Can verify membership in O(log n) time (this is the advantage over the linked list

Variant: Sorted Merkle Tree

• can verify non-membership in O(log n)
  (show items before, after the missing one)
  One can prove that a block is not in a membership which I guess is just as important as well.

Realistically hash pointers can be used in any acyclic data structure.

Digital Signatures

These are my notes of the second lecture from Coursera’s Bitcoin and Cryptocurrency Technologies during Dec 2016 – Feb 2017.

Questions answered in this Post:

• What is a digital signature?
• What are some of the requirements?
• What are some practical implementations details?

Signature

only you can sign, but anyone can verify it
signature is tied to a particular document (can’t cut and paste to another doc)

If you had a digital signatures then this identity theft crime described below would not be possible:
The scenario works as follows, a person is called and is asked a question that guarantees that they’ll say the word “Yes”. The caller (criminal) will record the person answering “Yes”. Then the criminal will use the voice recording of the confirmation for different electronic bank verifiers. This concept of cut and paste in my example is using a voice recording out of context to commit a crime. With a digital signature, theoretically one cannot take the instance of the signature out of context and use it for other, potentially nefarious, purposes.

API for Digital Signatures

(sk, pk) := generateKeys(keysize)
sk: secret signing key
pk: public verification key

sig:= sign(sk, message)

isValid := verify(pk, message, sig)

These different functions hit the key idea of what is a signature. You generate the key with some size (256 bits) and get two outputs: a secret key and public verify key. Next you can now sign messages which people can verify by using the public verify key and the signature. This signature is tied to a specific document (msg) in this case as well. Thus the generateKeys and sign use randomized algorithms

Requirements for a Digital Signatures

• able to verify valid signatures
• unable to forge signature

“valid signatures verify” – verify(pk, msg, sign(sk, msg)) == true
“can’t forge signatures”
adversary who:
knows pk (public key)
gets to see signatures on other messages of his choice then he can’t produce a verifiable signature on another message

Game we play with an adversary

Challenger (TV judge)
Attacker claims that he can forge signatures

1. (sk, pk) generateKey
2. Judge gets the secret key, the attacker gets the public key
3. The attacker can get signatures on other document. He will see if he can use these the get the signature for this particular document.
4. Lastly the attacker thinks he has the document, then he sends a message and a signature. Thus the challenger can now run isValid to determine is it true.
5. This should not work!

Practical Mentions

1. Algorithms are randomized so you need a good source of randomness
2. Limit on message size so instead use hash(message) to keep the message less than 256 bits
3. fun trick: sign a hash pointer meaning signature “covers the whole structure”
If you sign a hash pointer than the entire data structure is protected. So the entire contents of the block chain is protected.

Bitcoin uses ECDSA standard (Elliptic Curve Digital Signature Algorithm)

relies on hairy math…
good randomness is essential because if you foul this up in generateKeys() or sign() then you probably leaked the private key so your “digital signature” is no longer secure.

Cryptographic Hash Function

These are my notes of the first lecture from Coursera’s Bitcoin and Cryptocurrency Technologies during Dec 2016 – Feb 2017.

Questions answered in this Post:

• What is a cryptographic hash function?
• What are the security properties?
• What are the applications of some of these properties?
• What does SHA-256 do at a simple level?

Hash Function

• takes any string as input
• fixed size output (256 bit bitcoin uses)
• efficiently computable (can figure out output in a reasonable amount of time)

Security Properties

• collision-free
• hiding
• puzzle-friendly

Collision-free

Math definition – nobody can find x and y where x != y and H(x) = H(y)

in words:
nobody can find two different input strings so that if you apply the hash function to them, they have the same output.

the idea that nobody can find really means it’s really really really hard to find it….

Note that there has to be a collisions
since you’re going from a much larger input space t a fixed output space (2^256).

Hiding

Given H(x), it is infeasible to find x.

If r is chosen from a probability distribution that has min-entropy, then given H(r | x), it is infeasible to find x

High min-entropy means that the distribution is “very spread out” so that no particular value is chosen more than negligible probability.

in words: if you are given the hashed version of x then you will be unable to find x

Puzzle Friendly

for every possible output value y,
if k is chosen from a distribution with a high min entropy (super spread out) then it is infeasible to find x such that H(k|x) = y.

If someone wants to target a certain hash function, get some value of y, if part of the input is chosen in a random way, it’s difficult to find another value to target the hash function value.

Given a “puzzle ID” id ( from high min-entropy distribution) and a target set Y:
Try to find a “solution” x such that H(id|x) \in Y.

id | x means id concatenated x

Application of having something collision-free

Hash becomes a message digest meaning that you can use the has as a replacement of the msg
You can use H(x) and H(y) as smaller forms of the input string.

So if H(x) = H(y) then x = y.
Technically H(x) is only 256 bits while the x can be of some large arbitrary length

Application of puzzle friendly

Puzzle friendly property implies that no solving strategy is much better than trying random values of x

Application of the hiding property

In words, the idea is that you want to create a secret message that you can put in a public envelope.

Commitment API – to help explain public envelope example

Want to “seal a value in an envelope” and “open the envelope” later

Commit to a value, reveal it later

(com, key) := commit(msg)
match := verify(com, key, msg)

To seal msg in envelope:
(com, key) := commit(msg) — then publish com

To open envelope:
publish key, msg
anyone can use verify(com, key, msg) to check validity

Want two security properties:
Hiding: given com, infeasible to find msg;
Binding: infeasible to find msg != msg’ such that
verify(commit(msg, msg’) == true

commit(msg) := (H(key | msg), key) where key is 256 bit
verify(com, key, msg) := (H(key|msg) == com)

More about the Security Properties

key is a randomly generated 256 bit value

Hiding: Given H(key | msg) infeasible to find mg
Binding: Infeasible to find msg != msg’ such that
H(key | msg) == H(key | msg’)

Basically can’t find two different messages where you committed to one and verified with another one.

So you use the hash function in both commit and verify

What hash function will we use? SHA-256

Step by Step of what SHA-256 does

1. You have an input message of an arbitrary length
2. You also have a 256 bit value called IV (Initialization Vector (https://en.wikipedia.org/wiki/Initialization_vector)
3. The input string gets broken up into 512 bit blocks and we’ll reference them as block_1, block_2, block_3, and block_n will be the last block. The last block will also contain padding where the last 64 bits is the length of the input message and prior to that is a 1{0*}.
4. The 256 bit value and block_1 come together as inputs to a compression function (c) which basically squashes the 768 bits back into 256 bits.
5. Next the output of c gets mashed with block_2 and to the compression function and out pops a 256 bit value.
6. This continues along the entire length of the message where the last output is Voila, the hash.