Tag: Bitcoin

These are my notes of the ninth lecture from Coursera’s Bitcoin and Cryptocurrency Technologies during Dec 2016 – Feb 2017. The lecture answered quite a bit of my questions regarding mining. Prior to this lecture, I knew that people mined by doing some heavy computational. Now, after learning about the background regarding incentives, it actually seems more reasonable. I was most shocked to realize that there will be only 21 million bitcoin create ever unless people change the rules.

Questions answered in this Post:

• High level, how does incentives help?
• What are block rewards and how does the reward gained change?
• What are transaction fees and how do they change?
• What is PoW and PoS and not Prisoner of War and Point of Service?
• How frequently are block created?
• What is a nonce? How is it used?

In the previous section looked at the consensus algorithm.

This lecture discussed a second part of Bitcoin’s decentralization called incentive engineering. What does this incentive engineering mean besides sounding like fancy name for treats?

Previously, it was discussed that there was a assumption that at least 50% of the nodes were honest and that one is able to pick a random node. Also, we would know if there was a Sybil attack as each of the nodes created by the Sybil would still be tracked to only a single user.

Assumption of honesty is problematic especially if there is financial incentive to subvert the system. Since nodes don’t have identities, one is unable to penalize the group that creates the malicious blocks.

Can we reward the blocks on the long standing chain? Yes. Use BitCoins to incentive the nodes that created these blocks

Two Incentive Mechanisms in Bitcoin

Incentive 1: Block Reward

Simply, you get bitcoin for creating a block. The amount of bitcoin you get changes over time. Actually according to < href="http://www.bitcoinblockhalf.com/">BitcoinBlockHalf. The coin reward is currently 12 and it will drop to 6 in 2020.

The block creator only gets to collect the reward only if the block ends up on the long-term consensus branch! Thus one is incentivized to behave honestly and to agree.

There is finite supply of bitcoin: 21 million
Block reward is how new bitcoins are created
Runs out in 2140. No new bitcoins unless the rules will change

Incentive 2: Transaction Fees

The second way is via transaction fees. This mechanism made more sense to me given that when you trade at least on financial markets you have to pay some amount for the processing. Thus the nodes who are doing this service can choose to take some amount for doing the transaction. From looking at things like Ethereum with gas, this is used as well and there exists a market value to see what the transaction price should be set as. If you give more than your transaction will be picked up faster.

Remaining problems

How to pick a random node?

How to avoid a free-for-all due to reward

How do you avoid Sybil attacks? We made an assumption earlier

Then he started talking about something called Proof of Work. That peaked my interested since almost every bitcoin blog/youtube channel talks about this versus Proof of Stake.

Proof of Work

This is supposed to answer how to select a random node. The node will be selected in proportion to a resource that nobody should be able to monopolize on it.

Proof of Work – resource for giving nodes power is computing power
Proof of Stake – resource for giving nodes power is currency ownership

My thought was, wouldn’t someone be able to monopolize on ownership? Like is the actual answer, more is power. Well first let’s talk about what proof of work means.

select nodes based on computing power?

1. Select nodes in proportion to computing power
2. Let nodes compete for right to create block
3. Make it moderately hard to create new identities
   (Attacks on identity creation and on the Sybil attack)

Let’s look at a more concrete example. I agree it sounds vague and I’m lost. Though looking at the next slide that just says hash puzzle and has the words nonce… this does not look that illuminating.

Nonce – specific number (Again, according to Merriam-Webster: the one, particular or present occasion)

So bitcoin achieves Proof-of-Work using hash puzzles. I’ll talk more about the hash puzzle further down.

To create a block to add to the block chain, you need to find “nonce” such that H(nonce | prev_hash | tx| tx…|tx) is very small.

(nonce | prev_hash | list of trxn that comprise the block)

Then take the hash of this whole, long string.

Then the hash if correct, should be a very small number . By very small, I mean that it falls within a certain target space in relationship to the output space of the hash.

If the hash function is secure, the only way to succeed to try enough nonces until you get lucky. The reason for the nonce is that you want to make it moderately difficult.

This is the computational puzzle that the node is required to create a new block.

Proof of Work Properties:

1. Difficult to compute
   Aug 2014: about 10^20 hashes/block
   only some nodes other to compete – miners
2. Parameterizable Cost
   Nodes automatically re-calculate the target every two weeks
   average time between blocks = 10 minutes
3. Easy to verify – once you find the nonce, everyone else can check. Thus no need to have centralization since other miners will verify another miner.

What this means is that if you’re a miner, and you’ve put in some capital, over a two week period, there should be more blocks found. Thus you constantly need to put in more hardware investment to find more blocks.

Prob(Alice wins next block) = fraction of global hash power she controls.

If blocks came close together, there would be less efficient. We like putting hundreds of transactions into the block.

Key Security Assumption

• attacks infeasible if majority of miners weighted by hash power follow the protocol (honest)
• if the majority are honest, because of the competition of competing for block then you know they will come from an honest node

Solving hash puzzles is probabilistic

Need to try them one by one to hope one succeeds

Bernouilli Trials
Poisson Process should shows this exponential distribution

for a individual miner:
mean time to find block = 10 min/fraction of hash power

Proof of work is a way to

• Select nodes in proportion to computing power
• Let nodes compete for the “right” to create blocks

A block in the block chain was found at time t. What is the probability that the next block was found at or before t+10 min? Assume that the total hash power of the network stays constant.

More than 50%

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.