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 '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.

Bitcoin Course on Youtube

While waiting for the New Online Bitcoin Course to start, I discovered the old course on Youtube.

Lecture 1 — Intro to Crypto and Cryptocurrencies (58:41) • 'First lecture of the Bitcoin and cryptocurrency technologies online course.'

The description continued,

Published on Feb 16, 2015 • Course website:
https://piazza.com/princeton/spring2015/btctech/home

For the full experience, sign up via the link on that page. If you just want the lectures, simply subscribe to this channel. In this lecture (click the time to jump to the section): [...]

The 'jump to sections' correspond to the section headings of the first chapter of the course textbook. This first lecture and subsequent lectures are on the Youtube channel, Bitcoin and Cryptocurrency Technologies Online Course, which is dedicated to the course. My guess is that this is the first incarnation of the course that eventually appeared on Coursera.

Bitcoin Deanonymization

How's it going with that 'online bitcoin course', last mentioned in Going Deeper into Bitcoin (March 2016)? At that time I wrote,

It took me exactly a week to work through the first two lectures. I'm sure that I won't be able to maintain this pace week after week, and I only skimmed the readings.

I've reached lecture six where I found an interesting image in '6.2 Overview of Bitcoin Deanonymization'. At about 11:40 into the video, the following chart is shown.

A similar chart can be found in the paper A Fistful of Bitcoins: Characterizing Payments Among Men with No Names Sarah Meiklejohn et al. The caption there (p.9) says,

Figure 6: A visualization of the user network. The area of the cluster represents the external incoming value; i.e., the bitcoins received from other clusters but not itself, and for an edge to appear between two nodes there must have been at least 200 transactions between them. The nodes are colored by category: blue nodes are mining pools; orange are fixed-rate exchanges; green are wallets; red are vendors; purple are (bank) exchanges; brown are gambling; pink are investment schemes; and grey are uncategorized.

Also interesting -- to me, at least -- are the 16 bitcoin services listed in the chart:-

bitcoin.de, bitcoinica, bitmit, bitpay, bitstamp, btc-e, deepbit, gibse, instawallet, mtgox, mybitcoin, okpay, ozcoin, satoshi btc dice, silk road, slush

Since few of those are household names, I'll look at them in another post.

2015 Hong Kong Conference

At the end of my previous post, Bitcoin in the News : Satoshi Roundtable, I gave myself the action to look into the meaning of 'Segregated Witness'. While doing that I discovered a couple of posts on the domain gavinandresen.ninja ('Bitcoin developer. All-around geek.') that offer insights by a bitcoin insider.

• Segregated Witness Is Cool (December 2015)
• Satoshi Roundtable Thoughts (March 2016)

That first post links to 'a fantastic presentation on "Segregated Witness" in Hong Kong' by Pieter Wuille, which I embed here.

Scaling Bitcoin - Hong Kong (5:09:16) • 'Streamed live on 6 December 2015'

The presentation starts around 36:00 into the clip. I noted three other related videos on Youtube and tried to put them in order for later viewing; the running time is listed to differentiate them.

• 1:42:17; Day 1 AM, stream starts 15:30
• 2:58:12; Day 1 AM, stream starts 08:00; 'welcome back'
• 3:17:29; Day 1 PM, stream starts 16:11; 'mining panel'
• 5:09:16; Day 2 AM, stream starts 33:30; (agenda displayed 35:35)

The sponsor(?) of the conference is shown as 'Cyberport'. The Wuille presentation is laden with jargon and uses a few acronyms -- UTXO set, P2SH compatible, give time for IBLT, write BIP -- that I need to define. No surprise there. I'll do that in another post. No surprise there either.

Going Deeper into Bitcoin

I ended my previous post, Online Bitcoin Course, with a task to accomplish.

About ten minutes into the first video, I suddenly realized I wasn't understanding the lecture. Then when I reached the end, I couldn't answer the first question. Looks like I'll have to apply some real brainpower to this thing if I want to make it work.

It turned out that I had a preconceived idea about a piece of the logic underlying bitcoin that contained a misperception on my part. Once I recognized this and eliminated it, the rest was easier. The course's 'Welcome' section says,

This week, your main tasks are to watch lectures 1 and 2 and to complete the embedded quizzes. [...] We also encourage you to read the book chapters that closely follow the lectures. For technically complex explanations, you may find it helpful to use the text and go at your own pace.

It took me exactly a week to work through the first two lectures. I'm sure that I won't be able to maintain this pace week after week, and I only skimmed the readings.

The 'Welcome' section points to another resource, Bitcoin.org - Open source P2P money, that I don't remember seeing before. I'll look at this another time.

Online Bitcoin Course

At the end of my previous post, Bitcoin at Princeton, I noted a free online course Bitcoin and Cryptocurrency Technologies. The signup page says,

There’s a lot of excitement about Bitcoin, but also a lot of confusion about what Bitcoin is and how it works. We’re offering this course focusing on the computer science behind Bitcoin to help cut through the hype and get to the core of what makes Bitcoin unique.

The signup process was quick and within minutes I was watching the first video.

'Welcome to Bitcoin and Cryptocurrency Technologies'

The course starts with 'Lecture 1: Intro to Crypto and Cryptocurrencies', where the first video is 'Cryptographic Hash Functions'. I have a degree in math and computer science and have worked all of my professional career with various aspects of computing. About ten minutes into the first video, I suddenly realized I wasn't understanding the lecture. Then when I reached the end, I couldn't answer the first question. Looks like I'll have to apply some real brainpower to this thing if I want to make it work.

Bitcoin in the News : 2016-01 Davos

In the previous post, Bitcoin in the News : 2016-01 More++, I mentioned,

Another source of news was the annual World Economic Forum, Davos, Switzerland. The Davos stories might be worth a separate, deeper look.

For starters, here's a video from the event.

Davos 2016 - The Transformation of Finance (55:54) • 'What trends and uncertainties are shaping the future of financial services?'

The corresponding Youtube page lists the speakers as John Cryan, James P. Gorman, Christine Lagarde, Dan Schulman, and Tom de Swaan; the moderator as Gillian R. Tett. See that page (right click the video) for their titles and functions.

At about 5:40 into the clip, the IMF's Lagarde holds up a print copy of 'Virtual Currencies and Beyond : Initial Considerations'. For more about it, see Publication Date: January 20, 2016 (imf.org), with a link to a PDF version.

Beginning Bitcoin Videos

In First Post, New Blog, I wrote,

I entered the term 'bitcoin' into Youtube and started watching videos. This was more fruitful. General impression: lots of young, fast-talking Silicon Valley types proselytizing on the subject; many references to sinister aspects that make me wonder if it's a sound place to put any money. I'll come back to the videos on my next post.

First, here's a short, simple introduction to the concept.

The Essence of How Bitcoin Works (Non-Technical) (5:24) • 'A brief intro to the main ideas behind How Bitcoin Works, including how money is transferred, who keeps track of it, and how the whole thing is secured.'

A longer version, more technical version by the same video maker can be found at How Bitcoin Works Under the Hood, currently with 659.583 views and 1.274 comments.

For an introduction to the history and some of the social aspects, see Everything You Need to Know About Bitcoin : VICE Podcast 027; 'Reihan Salam sits down with Jerry Brito, one of the leading experts on Bitcoin.'

To hear from some of the main insiders, see The Bitcoin Phenomenon. Near the end we learn,

Starring in order of appearance:- Gavin Andresen, Peter Vessenes, Bennett Hoffman, Angela Keaton, Jeremy Liew, Fred Ehrsam, Erik Voorhees, Trace Mayer; Shot on location at Bitcoin 2013 in San Jose.

After these clips, almost anything featuring Andreas Antonopoulos is worth viewing (except when he's speaking in front of people who are eating -- 'crunch, crunch, slurp, crunch').