Tag: Merkle tree

The Kingstons continues their intellectual journey on blockchain in relation to cryptocurrency. The previous days were on foundational topics like the cryptocurrency algorithms, decreasing reward to miners, and most importantly the cryptography that sits behind all cryptocurrencies. Today they are ready to talk about details of mining itself, finally addressing Emily’s question from days ago.

Greg: So does everyone have the chance to watch the video I recommended? Don’t mean to put pressure on you guys.

Jason: I did. You are right and I was able to understand the show most of the time. Now I have something to brag about in my school to other kids.

Emily: It looks like the thing called “nonce” plays a crucial role in mining, Am I right?

Joy: That’s right. To mine is to play with numerous nonces. Similarly, to win in the mining game is to find the “Golden Nonce” that leads to a hash that fits the criterion or the standard hash.  

Emily: But what exactly is “nonce?” The video did not tell us, it just shows up like a magic number.

Greg: Nonce stands for “number used once,” where the first letter “n” is for “number,” and “once” for “one time.” It’s 32-bits — or 4 bytes because one byte is 8 bits and 32 divided by 8 is 4. This is a good size because it’s much smaller than SHA-256 that’s 32 bytes, again 256 divided by 8 is 32, yet big to generate a large number of combinations. Anyone wants to guess how many possible combinations there will be for nonce?

Jason: Let’s see: 32 bits and each bit has two values “0” and “1,” the possible combination will be, let me get it from my phone. “Hey Google, what is 2 to the power of 32?” Wow! It’s 4,294,967,296 or more than 4 billion different values.

Greg: Great! We need that many nonces because each one can be used only once. I hope we can get to the point later that even these many nonces sometimes may not be enough.

Joy: Now we can finally answer Emily’s questions what mining is: It is a process in which miners enter different nonces into the SHA-256 the digital “fingerprint machine” to produce different hashes and one of them may be a or acceptable for validating the entire block of transactions.

Greg: More accurately SHA-256 does not work just with nonce but with the whole block header.

Emily: What is that? I’ve heard block in a blockchain but never block header.

Greg: A block header is a “headshot” of the block with 80 bytes of 6 fields. Sometimes you see people writing down fewer than 6 fields, but they should really have listed all as all are useful. These fields are “software version” that has 4 bytes, “previous block hash” of 32 bytes, “Merkle root” of 32 bytes, “Timestamp” of 4 bytes, “Difficulty target” of 4 bytes, and finally “nonce” of 4 bytes.

Emily: Wow, lots of information here. Do fields with more bytes more important than others?

Greg: Not necessarily. Nonce for example only has 4 bytes but as the video shows it plays a crucial role in mining. The 6 fields in a block header are divided into three types. Nonce is the only one that miners have control. Others are either predetermined like previous block hash or controlled by the system like software version, difficulty target and the Merkle root, or controlled by nature like timestamp. I have a table from the book “Mastering Bitcoin,” 2^nd edition by O’Reilly Media Inc in 2017. But we don’t have to understand all the details for each field, just focus on difficulty target and Merkle root and Nonce.

Size	Field	Description
4 bytes	Version	A version number to track software/protocol upgrades
32 bytes	Previous Block Hash	A reference to the hash of the previous (parent) block in the chain
32 bytes	Merkle Root	A hash of the root of the Merkle tree of this block’s transactions
4 bytes	Timestamp	The approximate creation time of this block (seconds from Unix Epoch)
4 bytes	Difficulty Target	The Proof-of-Work algorithm difficulty target for this block
4 bytes	Nonce	A counter used for the Proof-of-Work algorithm

Jason: Just a curiosity: what exactly is Timestamp? The description says seconds from Unix Epoch.

Greg: The Unix “epoch” timestamp is based on the number of seconds elapsed from January 1, 1970, midnight UTC/GMT.

Emily: After watching the video I think I have an idea of what mining is. You click a button and computer quickly runs through different nonce until it finds one that fits the target of difficulty. What I still don’t understand is how the target hash is set.

Greg: The target is set by the algorithm. Remember we talked about how the level of difficulty is set every two weeks? The reason behind the difficulty target is also simple: We just want to keep the pace of releasing new Bitcoin at ten minutes per block. The Mastering Bitcoin book said it very well: That ten minutes per block is the “heartbeat” of Bitcoin.

Joy: That is a good expression.

Greg: The fun comes when we put nonce and target together to get a complete picture. I find this article by Kirill Eremenko in 2018 that does a fairly very good job explaining how. Another article by Blockchain Council also explains nonce well. I specifically like the simple math classroom analogy it uses.

Jason: I like math. Sowhat is the analogy?

Greg: Very simple and yet very interesting, it says in a math class the teacher gave the following problem for students to solve, and whoever gets the answer first win some award: 315 + ? = 319.

Jason: That’s it? That number is 4! 315 + 4 = 319. I bet even Cleo can solve it.

Greg: Theproblemiseasy, but it offers hints to several important concepts in mining. Turns out that “4” is nonce, “319” is the target of difficulty, and “315” is previous block hash or anything that nonce is added to for mining. Mining is to find the piece of the cryptographic puzzle — the nonce and hash value — to meet the level of target difficulty. Take a look at this picture I draw to see how nonce and target work together to produce acceptable hashes for Proof of Work. This is inspired by a similar drawing in this article but with changes.

Kimberly: What changes have you made from the original?

Greg: The biggest one is to make the target hash an area rather than a single line. This reflects the changing level of target difficulty, called “retargeting,” because a higher level of difficulty means a smaller target hash. So of the two yellow broken lines the one below is harder than the one above.

Emily: It’s never clear to me how to control target hash or level of difficulty. I heard someone saying the other day that it is controlled by the leading zeros in the target hash. Why’s that?

Greg: Because with any number of a fixed length, more leading zeroes always make it smaller. Let’s compare two 5 digit numbers, one is 01234 and the other 00123, which is smaller? Of course the second one with two leading zeroes. I can even change the second number to 00987 and it won’t make a difference. This is why the number of leading zeroes controls level of difficulty. If the algorithm needs to raise the level of difficulty, just add more leading zeroes. Do the opposite and drop at least one leading zero to lower the level of difficulty.

Emily: Oh, that’s it? It sounds so easy.

Joy: It is easy. You often read people saying that mining involves solving complicated math problems. Not true. The math is easy and simple, the solution however requires more computing resources. That’s why I said that both Proof of Work and Proof of Stake are Proof of Resources.

Emily: But I still don’t see how a smaller target hash will make mining more difficult than a larger target?

Greg: Because a smaller target squeezes the space for finding acceptable hashes. Look at the picture again and if the target hash was the yellow broken line above, not below, there would be more acceptable hashes to be found, mining is easier.

Joy: Think of a room with a high ceiling versus another room with a very low ceiling, which room can hold more stuff? The one with high ceiling, right? A larger target hash is like a larger room to accept more hash values.

Greg: Chapter 10 of the book Mastering Bitcoin I mentioned earlier has an excellent analogy I believe would help us all. It tells a dice rolling story. Someone rolls two dice, and the goal is to show a number of dots below a target, just like our proof of work problem. Now, one dice has six sides with 1 to 6 dots on each side. Jason, if I roll two dice at the same time, how many possibilities of dots there will be?

Jason: Well, each dice has 6 possibilities, and two independent dice will have 6 x 6 = 36 possibilities.

Greg: Right. Now let’s say the target is to show 12 dots on two dice rolling together. Is it easy to get a “Golden Nonce,” meaning the right nonce to solve the mining problem of finding acceptable hash value?

Jason: Very easy! The only time one would loss is when she has (6,6), meaning both dice have “6” dots. All other combinations are winning.

Greg: Right! Now let’s lower the target to 11 dots. That would still be easy, as long as they show up anything below 11 dots. Keep lowering down the target until it’s 5 dots, then it’s harder, because most rolls will show up above or equal to 5 dots. Jason, how many rolls would meet the target?

Jason: Let’s see: (1,1) for both dice showing one dot; (1,2) for one dice 1 and the other 2 dots, (1,3) for one with 3 dots and another 1 dot and finally (2,2) for both showing 2 dots. I guess only 4 out of 36 possibilities qualify. 4 divided by 36 is roughly 11%, so nearly 90% of the time one loses.  

Greg: How about a target of 4 dots? Only (1,1) + (1,2) = 2 possibilities to win. For target 3 it drops down to (1,1) = 1 winning possibility.

Emily: I see your point: The smaller the target the harder to get the required nonce to produce satisfied hash values.

Greg: I’m not done yet. Let’s go down to a target of 2 dots on the same pair of dice, then we will see a really tough game, because nobody can win no matter how many times she rolls the dice.

Emily: Interesting! Are you sure about that?

Greg: I’m positive. The book I am citing from claims one possibility of (1,1) will win but that’s not true. Remember the challenge is to go below — not equal to — the target of 2 dots. The only “chances” to win are (1,0) + (0,0) = 2 possibilities but those are impossible since no dice has 0 dot as the minimum dot is 1. That’s why for two dice to show dots below 2 is impossible. Game over and nobody win.

Lily: So does it mean sometimes we will have no winner and no new Bitcoin will be released?

Greg: Of course there will be winner and a new block of transactions will be verified and added to the blockchain. It just means sometimes we will run through all the 4+ billion nonces and still find no acceptable hash below the target.

Lily: It’s amazing that even 4 billion nonces are not enough to solve the mining problem.

Greg: It’s understandable if you know how powerful computers are today. The article by Kirill Eremenko tells us that “even an average mining device can calculate up to 100 million hashes per second, and therefore will go through the Nonce range in 40 seconds. And that’s an average miner. Mining pools and industrial scale mines are able to go through the Nonce range in fractions of a second.”

Lily: Okey, I can see that 4 billion nonce is not that much in the eyes of modern computers. But what we do to make sure we find the right hash to verify the new block of transactions?

Greg: That’s why Proof of Work is not just a game of nonce, we must utilize other things in the block header I was talking about earlier and then use the SHA-256 fingerprinting machine to make sure we get Proof of Work done.

Kimberly: The block header contains a total of 6 fields, we’ve used nonce and previous block hash, what else would we use?

Greg: The first extra field to be utilized is Timestamp. As Eremenko points out, “all we have to do is wait until the timestamp increases. A change in the timestamp will mean that the combination is now different and if we try all 4 billion Nonce values again, every time we will get a brand new hash value.”

Kimberly: Sounds like we solved the problem once and for all.

Greg: Not really. Turned out that even the timestamp, which increases by second, is not updated fast enough. The mining pools, where miners form a club to mine together, can finish running through 4 billion nonce in a fraction of one second. We need other ways to help find the Golden Nonce.

Emily: Wow! Now what?

Greg: If there is a will, there is a way. Turns out that we can use Coinbase transaction to solve the problem.

Emily: What’s that?

Greg: Let’s first find out what Coinbase is. According to this Wikipedia page, Coinbase is “an American company that operates a cryptocurrency exchange platform.” “It is the largest cryptocurrency exchange in the United States by trading volume.” What makes Coinbase transaction special is that it is always the first transaction in each block, and it is created by miners who use it to collect the block reward and other transaction fees.

Emily: How does it work for solving our problems here?

Greg: It may sound complicated, but the idea is simple: We use the Coinbase transaction data as extra space to hold extra nonce.

Lily: How much space can we get from the Coinbase transaction?

Greg: Quite big, it can hold anywhere between 2 and 100 bytes of data. That space is called “extra-nonce space,” which provide an extra nonce mining solution. Say we use 8 bytes of the Coinbase data space, plus 4 bytes of “standard” nonce space, there would be 12×8=96 bits, or “2 to the power of 96” instead of “2 to the power of 32” as previously with the standard nonce.

Lily: Wow, with this much space we don’t have to use the Timestamp.

Greg: That’s right. The other good thing is that Coinbase transaction always enters Merkle Tree, so anytime there is a change in Coinbase transaction, it will change the block hash.

Emily: What’s a Merkle Tree?

Greg: That’s the question for another day. We will also talk about encryption and compare Proof of Work and Proof of Stake.