Shor's Algorithm

Although my previous post, Quantum Computers, was only a low level introduction to the subject, it piqued my interest. I ended that post with a vague objective for a follow-up:-

In my next post I'll try to learn more about quantum algorithms.

I continued watching videos and quickly discovered that the algorithm with a direct impact on bitcoin is Shor's algorithm (Wikipedia):-

Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm (an algorithm that runs on a quantum computer) for integer factorization formulated in 1994. Informally it solves the following problem: given an integer N, find its prime factors. On a quantum computer, to factor an integer N, Shor's algorithm runs in polynomial time (the time taken is polynomial in log N, which is the size of the input).

Next I found a short video on Youtube starring Peter Shor, What is Shor's factoring algorithm?, but it's much too short to explain the subject properly. Another video, Shor's Algorithm, looked more promising, but required knowledge of math concepts that I wasn't familiar with. Fortunately, it was the last clip in a course playlist, Intro to Quantum Computing (no.23/23), that covered the math from the start. From the first videos in the course, I learned that quantum mechanics are based on linear algebra, a subject I studied many years ago when I was still capable of learning complicated new things.

Although I wasn't able to complete the intro course before writing this post, I found another video that explained the algorithm using more basic math. After one full viewing, I can't say that I've grasped it completely, but I'll watch it a few more times until it sinks in.

44 Quantum factoring : Shor's factoring algorithm (25:42) • 'Quantum Mechanics and Quantum Computation'

The Youtube page for that clip says, 'Published on Nov 26, 2016', which is the date on this current post. (How lucky is that?) It's part of another course playlist, Quantum Mechanics and Quantum Computation, that currently stops at '43 Quantum factoring : Period finding', so I assume it will be updated wth the new clip(s) in due time.

From all of this it looks like the cryptographic underpinnings of bitcoin might indeed be at risk in the not-too-distant future, especially if there is an equivalent of Moore's law that applies to quantum computer hardware. Not to worry too much, because Quantum cryptography (Wikipedia) promises a parallel evolution:-

Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution which offers an information-theoretically secure solution to the key exchange problem. Currently used popular public-key encryption and signature schemes (e.g., RSA and ElGamal) can be broken by quantum adversaries. The advantage of quantum cryptography lies in the fact that it allows the completion of various cryptographic tasks that are proven or conjectured to be impossible using only classical (i.e. non-quantum) communication.

With all of that in mind, I'll continue any further investigation of the quantum world outside the confines of this blog. After two posts on a quantum detour, I'm ready to return to the main subject: bitcoin.

Quantum Computers

In my previous post, Bitcoin in the News : 2016-10, the last news item was,

'Is Bitcoin Doomed?' (newsweek.com) • 'Cyber security experts say bitcoin will disappear when the first quantum computer appears.' • Since I know little about quantum computing, I'll digress for the next few posts to spend time on it.

I spent a pleasant few hours watching Youtube videos on quantum computing and chose the following as a good introduction.

Quantum Computer in a Nutshell (Documentary) (30:01) • 'The reservoir of possibilities offered by the fundamental laws of Nature, is the key point in the development of science and technology.'

The description continued,

Quantum computing is the next step on the road to broaden our perspective from which we currently look at the Universe. The movie shows the history of progress in this fascinating field of science, introduces the most promising models and algorithms, explains the advantages of quantum computers over classical solutions, and finally presents wonderful people thanks to which the quality of our lives is constantly being improved. Even if you don't want to understand the video, please watch till the end at least to realise how big is the human thirst for knowledge.

An important message I picked up from another video was that quantum computers don't replace traditional computers -- they allow us to tackle problems that traditional computers can't handle because of algorithmic complexity. That topic is covered briefly at the end of the video. In my next post I'll try to learn more about quantum algorithms.

Bitcoin in the News : 2016-10 More++

After the previous post, Bitcoin in the News : 2016-10 'Trust Disrupted', what other bitcoin stories were noteworthy last month? The most mentioned was a concept called 'Bitcoin Unlimited'.

• 2016-10-14: ‘Bitcoin Unlimited’ Hopes to Save Bitcoin from Itself (motherboard.vice.com) • 'Bitcoin Unlimited, an alternative to the popular Bitcoin Core client that has been at the epicenter of the block size debate, is taking a more brazen approach compared to the slow process of community deliberation. Bitcoin Unlimited allows miners to decide the size of blocks they create and the upper limit of blocks they’re willing to process on their own and independent of any hard-coded limit.'
  
  
• 2016-10-20: ViaBTC Rises: How A Mysterious Miner Could Decide Bitcoin's Future (coindesk.com) • 'In recent weeks, China's ViaBTC became one of the first providers of mining software to switch its client from the official version provided by Bitcoin Core to an option provided by Bitcoin Unlimited, a rival development group that supports alternative methods of scaling that is focused on creating a more variable bitcoin block size. But unlike Bitcoin Core, Bitcoin Unlimited does not have support for that developer group's signature scaling solution, Segregated Witness, a planned technical fix that would effectively make bitcoin's block size about 1.8 times larger than it is today by changing how information is counted toward this total. Further, because the rules for Segregated Witness require 95% of bitcoin's hashing power to approve the transition, ViaBTC could effectively block its wider release.'

We've already seen 'Segregated Witness' on this blog. I last mentioned it in 2015 Hong Kong Conference (April 2016), including a link to an explanatory video. It was back last month.

• 2016-10-28: Bitcoin Begins Segregated Witness Era, What Happens Now? (cointelegraph.com) • 'October 27, 2016. Segregated Witness (or SegWit) was added to Bitcoin Core. Will that day be the official end of the two-year-old “Block Size Debate?” will yesterday be the first step towards a mainstream-ready global decentralized digital currency? Whether you know it or not, Bitcoin has officially stepped into a new era of expansion and usability with the release of Bitcoin Core 0.13.1. Here, we’ll give you a cliffnotes version of what happens next and if we are even ready for SegWit.'
  
  
• 2016-10-31: Bitcoin is closing in on its 2016 peak. A handful of theories attempt to explain the rally • No.3 of 4: 'A solution to bitcoin's "civil war" is at hand; A long awaited update to the bitcoin core, the software that governs the cryptocurrency, includes a "soft fork" solution to the problem of limited transaction capacity on the bitcoin network. The solution is called "segregated witness" and it allows bitcoin miners and others running the core software to up transaction capacity without running the existential risk of a "hard fork" that would split the currency’s blockchain.'

It looks to me like two competing technological solutions -- code-named 'Bitcoin Unlimited' and 'Segregated Witness' -- are operational and that only one of them will eventually survive. Another example of competing solutions is occurring at the macro-economics level.

• 2016-10-04: Bill Gross Says Bitcoin, Blockchain May Counter Central Banks (bloomberg.com w/ video) • 'New financial technologies such as bitcoin may become increasingly attractive to investors as a protection against central bank low- and negative-interest-rate policies that threaten capitalism, according to billionaire bond manager Bill Gross. Policies by the Federal Reserve, Bank of Japan and European Central Bank are destroying historical business models that foster savings, investment and economic growth, Gross, who runs the $1.5 billion Janus Global Unconstrained Bond Fund, said in an October investment outlook released Tuesday. He said that as investors lose faith in the system, they will increasingly seek havens.'
  
  
• 2016-10-12: Central banks consider Bitcoin’s technology, if not Bitcoin (cnbc.com; reprinting Nathaniel Popper of the New York Times) • 'Bitcoin was created by libertarian-minded programmers with a deep suspicion of central banks and the national currencies they issue. Yet it is central banks that are doing some of the most ambitious work of late in trying to harness the technology introduced by Bitcoin. '
  
  
• 2016-10-19: The European Central Bank Wants Tighter Control over Bitcoin (cryptocoinsnews.com) • 'The European Central Bank (ECB) has proposed a directive of the European Parliament and of the Council stating that ‘virtual currencies do not qualify as currencies from a Union perspective,’ and wants digital currencies to be explicitly defined as not legal currencies or money.'

As long as I'm on the concept of 'competing solutions', there's also a political aspect.

• 2016-10-18: Review: "The Politics of Bitcoin" Offers a Flawed and Misleading Partisan View (bitcoinmagazine.com) • 'David Golumbia, an assistant professor in the Department of English at Virginia Commonwealth University, an aspiring political pundit, and the author of the recently published book, The Politics of Bitcoin: Software as Right-Wing Extremism, denounces Bitcoin in a recent blog post titled Trump, Clinton, and the Electoral Politics of Bitcoin. "[What] concerns me about Bitcoin is how it contributes to the spread of deeply right-wing ideas in economics and political philosophy without those right-wing associations being made at all explicit."'
  
  
• 2016-10-30: Making Sense of Hillary Clinton's Bitcoin Rejection (coindesk.com) • 'For Hillary Clinton's campaign, accepting bitcoin was "too libertarian". That's what we learned last week when it was revealed senior campaign aides for the US presidential candidate considered taking bitcoin campaign donations, but dismissed the idea.'

Given the result of the U.S. election that took place this past week, what Hillary Clinton thinks about bitcoin is no longer relevant. What President-elect Donald J. Trump thinks must be extremely relevant (if he thinks about it at all), and I expect to see something about that in next month's news post. If not, I'll examine the subject myself. Another subject I would like to examine is mentioned in my final link.

• 2016-10-12: Is Bitcoin Doomed? (newsweek.com) • 'Cyber security experts say bitcoin will disappear when the first quantum computer appears.'

That could be the most important message in this current post. Since I know little about quantum computing, I'll digress for the next few posts to spend time on it.

Bitcoin in the News : 2016-10 'Trust Disrupted'

Last month, starting with Bitcoin in the News : 2016-09, I ended up with three 'In the News' posts and I can see I'm on track to do the same this month. After a quiet start to the month's news, things started to pick up:-

• Watch the trailer for our new series ‘Trust Disrupted: Bitcoin & The Blockchain’ (techcrunch.com) • 'What is bitcoin? What is the blockchain? How does it work? Who is behind it? Find the answer to all of these questions and more by tuning into the six-episode series.'

Unfortunately, the embedded video in that link uses a 30 second ad to introduce the 40 second trailer. Another TechCrunch page in the series used the same ad to introduce another clip, with no option to terminate it after a few seconds. Life is too short to lose time on irrelevant ads so I located the same series on Youtube.

Trust Disrupted: Bitcoin and the Blockchain (trailer) (0:39) • 'Traces the rise of Bitcoin and the technology that made it happen: the open, distributed ledger known as the blockchain. As blockchain technology has outpaced Bitcoin, an array of new apps has proliferated across the globe.'

The description continued,

Trust Disrupted is based on the book Digital Gold by Nathaniel Popper. Produced by Stateless Media, it is an exclusive TechCrunch series that offers an in-depth look into the how and why of bitcoin.

The description also included a link to a playlist for the series: Trust Disrupted. After this welcome interruption to the month's quiet start, I discovered another dozen topics worth exploring. I'll continue with those for my next post.