Bitcoin Q&A: Nonces, mining, and quantum computing
Articles,  Blog

Bitcoin Q&A: Nonces, mining, and quantum computing


“Who generates the nonce?” “If my pool generates the random number,
how is it protected from us knowing it?” “What makes that random number tamper-proof?” “Does the whole network
contribute to the random number?” All right. The nonce, the random number, is calculated
independently, billions of times per second by each… mining hardware system. When [someone] is mining, they are coordinating with
a very large number of computers over a network. These mining computers calculate billions of nonces per
second. There is nothing manual about this, by the way. When we say “a miner” or “mining,” when a nonce is
being calculated, there is no one sitting [at a table]… doing a calculation, validating transactions, and
checking a proof [on paper or a computer interface]. These are completely automated operations; computers
calculate billions of [possible] nonces per second. What is the purpose of the nonce?
The nonce is simply a very large random number. The space for nonce values is 32 bits, which means
there are 4 billion possible combinations; there is also some extra space in the block’s
[the coinbase script] which is called “extra nonce.” Extra nonce allows you to expand the
[nonce space] to much more than 32 bits. [Miners generate] many billion billions of combinations.
You may hear me say “billion billion” again in this , because these numbers are truly very large. The purpose of [iterating on] the nonce is to
[add it] to the block header in a specific [field], and then calculate a new block header hash. When you repeatedly hash the [other] block header
[fields] plus the nonce, you will get 256-bit numbers. [Those] numbers must start with a lot of zeros.
If it doesn’t [match with the threshold], you try again with a different nonce. [When mining], the only part of the
header you can change is the nonce. So a miner will construct a block, putting [unconfirmed
transactions from the mempool inside the block], putting other information into the
header such as the timestamp, etc. Once they have the header, they [could] plug in
any nonce they want; let’s say the number 1. Then they calculate the header hash and
[check] if it matches this special pattern, which starts with a lot of zeros. The chances of it starting with a zero [become] lower
the more zeroes you expect at beginning of the number. Let’s say you are just looking for one bit to be 0. About half of the hashes you produce will have
a zero bit in the beginning; half will have a one bit. If you want two zeros, that is a one-in-four chance.
If you want three zeros, a one-in-eight chance. If you want four zero bits in the beginning,
then that is a one-in-sixteen chance. By the time you reach the [number of zeros] with
blocks mined today, you are looking at probabilities… of about one-in-five septillion nonces
having that many zeros at the beginning. How do you find one [such nonce] in five septillion
[iterations]? Well, you try a septillion hashes per second. You try many possible nonces, [as fast as your hardware
can handle], with the header you have constructed. One of the miners will be lucky in [each ten-minute
round] of those attempts and find a nonce that, when fitted into the candidate block they
have constructed, will produce a header… that has [enough] zeros in the beginning to
match the difficulty required by the network. That is the winning valid block. As soon as they find it,
they can [propagate it to the rest of the network]. The random number isn’t tamper-proof or secret.
The mining pool doesn’t pick this random number. Every mining machine out there is trying
billions of these random numbers every second. They will discard all the results until they find
one that produces a hash [with enough zeros]. “Is it possible to develop a mining
algorithm for guessing the nonce, which will fast-track solving
the [proof-of-work] challenge?” “Could that be related to the recent
shattering of the SHA-1 [hash algorithm]?” That is an excellent question. Yes, it is possible to create
a shortcut that allows you to predict the nonce value… that is required in order to produce
proof-of-work for a specific target. That would involve breaking SHA-256. The SHA-1 hash algorithm was recently
‘SHAttered,’ as the popular expression goes, meaning SHA-1 has been compromised in
such a way that you can create a collision. [A collision] is where you can produce [the
same output hash value from two different inputs]. Producing [an identical fingerprint from two different
inputs], a hash collision as it is called, is a fatal flaw. If you discover a fatal flaw in an algorithm,
as it has been in SHA-1, then it is no longer… a suitable cryptographic hash function to use… for the purposes of fingerprinting
documents, digital keys, or in SSL certificates. The integrity of messages validated through
those cryptographic hash algorithms, like SHA-1, can no longer be [trusted] for those purposes,
because it has been fatally compromised. However, Bitcoin mining uses SHA-256, which
is much more complicated to compromise. Every cryptographic algorithm has a certain shelf life;
on average, it is twenty to twenty-five years… before it can no longer be considered secure. Depending on the algorithm, the shelf life
may be a bit more or less than that. [When] weaknesses are discovered, that shortens
the shelf life and makes it easier to compromise. Most cryptographic algorithms are based on a kind of
trapdoor mathematical function that has no short-cut, where the amount of computation required to go one
way through the algorithm versus the opposite way… is immense. As long as you can’t find shortcuts, that algorithm
is secure up to a certain amount of computation. If there is no shortcut, SHA-256 will continue
to be secure for decades and decades longer. If a short-cut is found, that doesn’t [necessarily] mean
it is fatal and will invalidate [use of] the algorithm. It may weaken it by a certain percentage; [maybe it
becomes] twice as easy to find a [specific] hash [value]. Maybe it becomes four times as easy. That will certainly
weaken the algorithm and shortened its shelf life. As computing power [and capacity] continues
to develop, at some point it would be [inviable]. So far, no short-cut has been discovered in SHA-256.
One of the reasons we know that is because of Bitcoin, which represents a global [cryptographic] piñata stuffed
with $15 billion; if you bash SHA-25 with a short-cut, you can break it open and collect some percentage
of that value before Bitcoin collapses catastrophically. Essentially, it is a honeypot. Bitcoin is a global test
that tells us SHA-256 is still secure. How do you know? Bitcoin is worth $15 billion. No one has cracked it yet. At some point, it may become obvious that SHA-256
is no longer secure and reaching the end of its life, or we find new [attack] vectors that may
make it insecure in a decade or a longer. [When that happens], the Bitcoin developers,
in collaboration with the rest of the community, would need to modify the proof-of-work algorithm
and replace it with a more modern hash algorithm. Certainly, that would be a very big undertaking. [Anyway], that is how we know there
is [currently] no shortcut to SHA-256. If Bitcoin was using SHA-1 today, some miner out there
would have been able to break it very quickly. At which point, it is no longer
useful as a mining algorithm. “Is Bitcoin an incentive for the
development of the quantum computer?” “Being a possible threat to the network’s security,
doesn’t this accelerate the race towards [building one]?” “Do miners think about this at all?” Great question. Effectively, Bitcoin is a honeypot. It provides a bounty
for anyone who produces [various types of attacks], whether it is a SHA-256 collision that we were talking
about before, or a quantum computing short-cut to… the elliptic curve digital signature algorithm. That may result in a compromise or
weakening of some parts of Bitcoin. Certainly that provides an incentive.
You can think of Bitcoin as a test. Bitcoin tells us that SHA-256 is [currently] secure,
that ECDSA is [currently] secure, from these threats. How do we know that? Because it continues
to maintain security with over $15 billion in value. Therefore, we can assume that these
[algorithms] have not been compromised yet. Does Bitcoin accelerate their development? Probably.
Although, most of the really interesting developments… in quantum computing can deliver a far greater
reward for those who develop them than $15 billion. Quantum computing has very broad applications. Furthermore, the application of quantum computing
to [attack] Bitcoin is [probably] marginal at best. First of all, SHA-256 and cryptographic hash
algorithms like SHA are not particularly easy… to optimize using quantum algorithms. The elliptic curve digital signature algorithm (ECDSA)
and elliptic curve cryptography can be massively… optimized with quantum computing. In fact, quantum algorithms for doing elliptic curve
factoring do exist, and will allow someone to break… elliptic curve cryptography eventually. For now, the elliptic curves that we use are far
greater than any quantum computer can factor. so that is not a risk [right now].
At some point, it would become a risk. [When someone has] very powerful
quantum computers which can do that, then the security of elliptic curve
cryptography is no longer good. But elliptic curve cryptography can be
replaced in Bitcoin with other algorithms. Because public keys are not demonstrated to the network until an amount [from one of its addresses]… is spent, by following the best practice of only using
an address once, then your public key is only shown… to the network when you have already spent that bitcoin;
[therefore, nothing is stolen if ECDSA is broken]. Even if someone was able to break the public keys
[produced by] the elliptic curve signature algorithm, you wouldn’t [be able to steal any] bitcoin
if addresses are only ever used once. Bitcoin addresses are secured through
two applications of hashing algorithms: SHA-256 and RIPEMD-160 Those, as well as the mining algorithm, are far less
susceptible to quantum algorithm optimizations, as far as we know. It may be a very long time until quantum
cryptography has any impact on Bitcoin. The other [aspect] to consider is, it also depends
on how broadly quantum [computing] is available. If quantum computing is broadly available, then just
as you can make better algorithms for cracking keys, you can also make better algorithms for making keys. You could make quantum cryptography algorithms. If quantum computing becomes broadly available,
then I can use it for encryption and digital signatures. [In that scenario, the fact that] others have quantum
computing would not make any difference, My cryptography, digital signatures and mining algorithm
[have been] adjusted to secure [the network again]. [The problem] is really the unequal
availability of quantum cryptography, which is a whole other topic that is for another session.

23 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *