Unexpected Ways in which Bitcoin Dodged Some Cryptographic Bullets

http://bitcoinmagazine.com/7781/satoshis-genius-unexpected-ways-in-which-bitcoin-dodged-some-cryptographic-bullet/

by icedicedavid • 13 years ago

196 73 13 years ago

Groxx• 13 years ago

Page isn't loading for me :/ cache for anyone else hitting this: http://webcache.googleusercontent.com/search?q=cache:WsX8NCw...

edit: tl;dr of it all is:

1) addresses are hashes of public keys, not public keys themselves, so you can't really figure out the private key even with magic / quantum computing.

2) 21 million BTC * 100 million divisions = 2.1 quadrillion < maximum integer uniquely representable by a (double-precision) float (~2^50.9 < 2^53), handy for simpler programming.

3) elliptic curve chosen wasn't one of the dubious NIST ones.

The article is pretty well written, IMO, and does a reasonable job explaining why these are issues in the first place, and how it avoids them. Probably worth a read unless you grok it all from the tl;dr, and even then since it might help you explain things to others.

raverbashing• 13 years ago

In essence, apart from 2, which wouldn't take too much hindsight to calculate, both items seem to be the work of a real expert in crypto.

Not the ones that go for the "proven" way "because NIST said so" or the "internet specialists" that cry wolf more often than not (and miss or even suggest security holes)

maaku2• 13 years ago

Not really. The original bitcoin client did what was called direct-to-IP transactions, which didn't use hashed pubkeys, and which was vulnerable to man-in-the-middle attacks (oops).

Bitcoin's ECDSA curve was chosen because it was one of the faster ones, not because of any NIST connection (a "real" cryptographer of the day would have probably advised against the secp256k1 curve used in bitcoin in favor of one of the NIST curves, or DJB's curve which is superior in just about every way.

geofft• 13 years ago

1 is a little hokey because in the common case, the hash is just a weakness -- it doesn't add any security against classical computers, for which ECDSA is already hard enough, and it opens the possibility of hash collisions.

I say "common case" because it only really is a win if _both_ quantum computers are in use _and_ you've never spent from the wallet and never will (except possibly to cash out entirely).

sillysaurus2• 13 years ago

Who created Bitcoin?

This comment seems to offer many clues: https://news.ycombinator.com/item?id=5547590

There are two groups that are on the suspects list for having engendered bitcoin, one group centers around Trinity College, another is a bunch of loosely affiliated international collaborators. Both groups are on the record with precursors to bitcoin (papers, software), neither has admitted openly that they were the ones.

Along with https://news.ycombinator.com/item?id=5548093

Investigations into the real identity of Satoshi Nakamoto have been attempted by The New Yorker and Fast Company. Fast Company's investigation brought up circumstantial evidence that indicated a link between an encryption patent application filed by Neal King, Vladimir Oksman and Charles Bry on 15 August 2008, and the bitcoin.org domain name which was registered 72 hours later. The patent application (#20100042841) contained networking and encryption technologies similar to bitcoin's. After textual analysis, the phrase "...computationally impractical to reverse" was found in both the patent application and bitcoin's whitepaper. All three inventors explicitly denied being Satoshi Nakamoto.

Anyone care to speculate whether it's more likely the creators were based in Trinity College rather than being international collaborators?

It's interesting that the controller of the Satoshi persona managed to stay anonymous for so long. I wonder if they were careful to only write forum posts via Tor? Otherwise their IP address might've been logged. An IP address would be enough for an ISP to unmask them (or at least narrow down the suspect list quite a lot). Satoshi also made a lot of source code commits, which seems like another way their IP address could leak.

Afforess• 13 years ago

All three inventors explicitly denied being Satoshi Nakamoto

Obviously if the inventor was not a single person, but the result of a group effort, one could truthfully reply that they were not the inventor.

canttestthis• 13 years ago

Why would you even assume that they replied truthfully?

oskarth• 13 years ago

"...computationally impractical to reverse" was found in both the patent application and bitcoin's whitepaper.

That's the first time I have heard that one. If there are no other textbooks / papers / patents were this phrase is used, this seems like a pretty strong indicator to me. A search on Google Scholar for that exact phrase gives (at the time) the two expected results. http://scholar.google.com/scholar?hl=en&q=%22computationally...

Alternative hypothesis: (a) Nakamoto paid close attention to research, read the patent and liked the phrase. (b) The phrase is common lingo, but Google Scholar doesn't index it. For example, it could be used in a private mailing list. Both (a) and (b) seems like they could quite easily be investigated by someone with domain knowledge together with some knowledge of how patents are distributed.

This seems like too simplistic a reasoning. Anyone care to explain what I am missing?

EDIT: The exact phrase "computationally impractical" seems to be very common, with thousands of citations before 2008 http://scholar.google.com/scholar?q=%22computationally+impra... It seems to me that reversibility might simple have been a "theme" in crypto circles around that time, which could explain the coincidence that two different groups independently glued the phrases together.

BoppreH• 13 years ago

Satoshi mined bitcoins alone for a long time, back when it was easiest. If they did not lose those original coins, they are stupidly rich.

When you hit a jackpot like this, remaining silent and denying everything is one of the most sensible courses of action.

deegles• 13 years ago

People are keeping a close eye on the addresses holding all of those bitcoins. I wonder how he'll avoid being detected when trying to withdraw them.

deelowe2• 13 years ago

I have a related question. Why hasn't the creator(s) come forward? What reason is there for hiding their identity?

I'm starting to add more tin foil to my hat these days and this sort of thing worries me.

wmf• 13 years ago

It's possible that some kind of secondary liability theory could be invented to make Satoshi an accessory to money laundering on a massive scale. But I've also noticed that communities and movements must become stronger when they outgrow their original leader. When you meet the Buddha on the road you're supposed to kill him, but most people won't. So he disappears instead.

mrb4• 13 years ago

He wants to remain anonymous almost certainly because he is estimated to own ~1 million BTC ($200 million!); and a lot of thieves would track/kidnap/torture/murder someone for the chance to steal that amount.

sktrdie• 13 years ago

Their activity on the official Bitcoin forum could probably lead to some analysis on where they are from: https://bitcointalk.org/index.php?action=profile;u=3;sa=stat...

kristianp• 13 years ago

Why is it that an off-topic (and untechnical) thread always seems to go to the top of HN discussions? So irritating.

terabytest• 13 years ago

This is the first article I've ever read that managed to explain cryptographical stuff in simple terms without making my head spin.

jawr• 13 years ago

Seems like there is a cryptographic explanation every few days. It's a popular topic to write about at the moment. This was well written however.

simondlr• 13 years ago

Besides dodging bullets, it amazes me that Satoshi had the foresight to include a scripting language into the outputs of transactions, envisioning a future where contracts could be built onto the blockchain. For a proof-of-concept, Bitcoin didn't need it. It could've just supported the ability for owners of addresses to claim outputs (in a hard-coded manner).

nhaehnle• 13 years ago

The irony, of course, is that last time I checked, large parts of this scripting language were disabled in the official client due to security concerns.

rtpg• 13 years ago

apparently originally he wanted to make a capability for a bunch of different transactions but realized that it would be easier to just stick q scripting language in there. Another data point for the "lazy programmers are the best programmers" thesis

applecore• 13 years ago

Pretty good explanation of the motivation behind scripts:

https://bitcointalk.org/index.php?topic=195.msg1611#msg1611

ploureiro• 13 years ago

"my own BitcoinJS fork (which also adds other improvements) does use plain numbers to store the number of satoshis."

Why wouldn't I feel tempted to use his fork?..

enimodas• 13 years ago

my thoughts exactly. For those who don't know, never ever use floats for things like money. Try in windows calculator for example sqrt(4) - 2 and see why.

Strangely enough he talks about floating point rounding errors in one of the next paragraphs?

vbuterin2• 13 years ago

For those who don't know, never ever use floats for things like money.

This is normally a very good rule to follow. The reason is that floating point is binary, whereas cash is decimal, so even an innocent number like 0.4 has no exact representation in binary (it's actually an infinite tail: 0.011001100110011...).

Here, however, I'm using floats NOT to store decimals; every single value that I store is an integer. There is absolutely no danger in using floating point numbers to store relatively small integers like 1253251126; the issue only arises in the context of very large numbers (specifically, those above 2^53) and decimals. If anyone can come up with a remotely realistic series of integer manipulations that will cause an inaccuracy in Javascript where all values always stay below 2^50.9, I will certainly abandon my choice of moving to integers at once; otherwise, I see no problem.

Luc3• 13 years ago

It's explained rather well in the article, over several paragraphs, why it's okay to use floating point in this case.

The first thing we did in the programming class at university was to learn how the IEEE floating point standard works...

foxylad• 13 years ago

Interesting... 2.1 quadrillion satoshis divided by 20 trillion dollars is about 100, so eventually there will be about the same number of satoshis as there are normal money cents in the world. Very nice symmetry!

nly• 13 years ago

Regarding the choice of the secp256k1 curve: ECDSA signature verification is fairly slow and sipa, one of the Bitcoin developers, has been developing a faster implementation[1]. If anyone has any crypto expertise and can review the code, or otherwuse can provide further optimisations or patches, I'm sure it'd be appreciated.

https://github.com/sipa/secp256k1

daniel-levin• 13 years ago

As a result, most of the decisions that Satoshi Nakamoto made in 2008 we are essentially stuck with.

Every single time I read something about what 'Satoshi Nakamoto' did in designing, implementing and securing Bitcoin, I grow more skeptical that one person, or even a small group of people, created Bitcoin. It is very difficult to believe that something this sophisticated was developed by anyone other than a well financed, possibly nation-state backed organisation.

This article suggests that Bitcoin was made difficult or impossible to fork by-design, which implies that the creator doesn't want to allow anyone to seize control of Bitcoin.

Paradoxically, the more you learn about Bitcoin, the more mysterious it becomes. Who would go through all that trouble to create it? What can they gain from Bitcoin's existence?

mrb4• 13 years ago

I think Bitcoin has been designed by a single person. The source code alone of version 0.1.0 was not very complex, see my post https://news.ycombinator.com/item?id=6561079 And most of the crytographic choices are logical and could have been taken by a person reasonably well-educated in computer security and cryptography who pays attention to details. This is my opinion as a pentester / IT security researcher / developer with experience in cryptography.

"This article suggests that Bitcoin was made difficult or impossible to fork by-design, which implies that the creator doesn't want to allow anyone to seize control of Bitcoin."

Well, source code is easy to change and fork. But because this would create a fork in the block chain, you would end up with a different Bitcoin network that does not recognize transactions of the original Bitcoin network.

"Who would go through all that trouble to create it?"

Version 0.1.0 is only 13k lines of code.

"What can they gain from Bitcoin's existence?"

Someone wanted to experiment with his ideas about a revolutionary peer-to-peer currency/payment network, and maybe hoped to inspire others with his creation? Some people enjoy experimenting with cool ideas just for the heck of it. What was Linus Torvalds thinking he would gain from writing the first version of Linux? Anyway, the success of Bitcoin so far is probably beyond what Satoshi envisioned as probable (although he may have seen it as possible).

throwhalloween4• 13 years ago

If there was one concrete point relevant to Satoshi Nakamoto's identity, especially that it is absolutely _not_ a single person, it's what he has never done...

Not that nobody else has found him out (definitely possible/plausible, and some people claim to have successfully used web tracking bugs to get an IP).

Satoshi Nakamoto:

1. never publicly claimed any credit for the idea of bitcoin... think about it, he doesn't claim he invented the idea, he just put it forward and kind of said, what if... ?

2. never spent or moved his massive holdings of BTC which are easy to identify because they are some of the oldest blocks in the blockchain

3. never exercised his power to shape bitcoin, especially after the end of 2011 - aside from code contributions and that doesn't count since everyone involved can think about it and decide to accept it or not - each code contribution is a potential fork so don't underestimate the care taken on the official bitcoin client

4. never slipped up and revealed his identity or even his _timezone_ !

That's a preponderance of evidence to me. I'll understand if you're not convinced but this is the kind of PR management that a single person just can't pull off!

What can they gain from Bitcoin's existence? Only all the economic benefits from a _viable_ digital currency. All previous attempts at digital currency are weak in comparison. And currency market manipulation is by far the most profitable game, like that even needed to be said.

Who would go through all that trouble? In a world where a US Agency (NSA) has successfully tapped almost the entire internet, maybe it's time to accept that this kind of advanced planning is within reach.

It helps to point out some common misconceptions about Bitcoin. Bitcoin does not guarantee anonymity, despite the p2p elements of the protocol - far from it. Bitcoin is much more flexible than you think, for example the "1" prefix on all addresses currently. Bitcoin does not have to succeed or last forever, the idea has been planted and isn't going away.

All markets are a mix of manipulation and organic behavior. Factor that into your plans and Bitcoin makes a lot more sense.

- posted anonymously

snitko• 13 years ago

So how come Bitcoin is so fundamentally opposed to the concept of state and regulations then? Doesn't make any sense. Where's the catch?

vbuterin2• 13 years ago

The same way Tor is fundamentally opposed to the concept of regulations on speech but is still funded ~60% by the US military. The US government sees the cost of itself losing some control as worth it to deny China control.

gd1• 13 years ago

very difficult to believe that something this sophisticated was developed by anyone other than a well financed, possibly nation-state backed organisation.

Hilarious. A "well financed, nation-state backed organisation" just gave us the Obamacare website.

throwhalloween4• 13 years ago

The same nation-state successfully operates the largest military organization in the world without accidentally detonating any nuclear bombs.

It doesn't all have to be ACA websites.

betterunix• 13 years ago

"Every single time I read something about what 'Satoshi Nakamoto' did in designing, implementing and securing Bitcoin, I grow more skeptical that one person, or even a small group of people, created Bitcoin. It is very difficult to believe that something this sophisticated was developed by anyone other than a well financed, possibly nation-state backed organisation."

Really, you think Bitcoin is that sophisticated? Can you even point to any clearly stated requirements, constraints, or security definition? The original Bitcoin paper did not even describe the system well enough for someone else to implement it; half the specification of the data formats was in the code itself. Nevermind the bad design; the original Bitcoin paper somehow failed to mention or even hint at (or even use the concepts from) the massive body of related work.

All the evidence points to Bitcoin being the work of an amateur, just one hobbyist who hacked together a system based on an idea he had. My guess is that it was a college student who was fascinated by cryptography and had read a few books. This is not necessarily bad -- the same is true of the Linux kernel, after all -- but to claim that Bitcoin is some kind of highly sophisticated system that must have been the work of a government team is just silly.

conformal• 13 years ago

i think your suggestion that bitcoin was created by one or more government agencies is a pretty good bet. it could be some other large, shady organization, but the tech is pretty highbrow and uses a lot of crypto. i have been overseeing the development of the alternative full-node bitcoin implementation, btcd, and it seems pretty clear that there was an enormous amount of novelty, insight, planning and countermeasures included in the initial release. it is unlikely that the initial 0.1.0 code was coded by a single person, but it seems pretty obvious that all the comments were removed.

without having this post balloon in size, i'll leave you with an interesting scenario:

let's say you were a member of some shadowy group and you were tasked with moving funds around the world but you didn't want intelligence services to be able to watch those funds move, e.g. via the SWIFT system. your only alternative is to move funds some other way, using an alternate system. moving physical goods around always carries risks at customs checkpoints and it is slow. this leaves some kind of an electronic value-transfer system. since one of your own group members may be a spy or otherwise untrustworthy, the system must assume everyone is untrustworthy. the obvious way to deal with untrustworthy parties is cryptography. a classic way to pass messages semi-anonymously is to "write on a wall" somewhere that you tell your counterparty to look, but others do not know to check.

if you had such a private / closed-loop value transfer system, the only real caveat is settlements in fiat currency, which all "normal" ppl use to settle transactions. if you aggregate these fiat settlements episodically using a fixed exchange rate, it effectively decouples actual meaningful transactions from the fiat transfers, obfuscating the actual transactions.

adamb_• 13 years ago

Imagine if it really is just one individual hacker that got extremely lucky (both with Bitcoin's success & maintaining their secret identity)... What must that person be thinking right now?

frezik3• 13 years ago

Design by Committee doesn't give you well-thought-out designs. It gives you crap like WEP and USB, where many competing voices try to drive the design in their own way.

In fact, being well-conceived and svelte is evidence that it was just a few very smart people, perhaps just one.

brainburn• 13 years ago

Thus, if your Bitcoin funds are stored in an address that you have not spent from (so the public key is unknown), they are safe against a quantum computer – at least until you try to spend them.

Uhm, no such thing? Every mined bitcoin is instantly sent to an address

yafujifide• 13 years ago

No, freshly mined bitcoins are never 'sent' anywhere - they just appear in the mining address. Thus, the public key is not revealed until they are sent.

misiti3780• 13 years ago

I'm not a crypto expert at all but I do have one question:

If there is a concept of "quantum-safe" (which I did not know until reading this article), why hasn't the broader internet (HTTPS) adopted them? Is there any plans for there adoption in the future?

HNaTTY• 13 years ago

Quantum-safe in the same respect that an md5sum of an ISO cannot reveal the contents of the ISO.

JeremyBanks• 13 years ago

http://en.wikipedia.org/wiki/Post-quantum_cryptography

My understanding is that schemes that would be resistant to quantum attacks are much less efficient, and have more negative tradeoffs, than the systems in use today. Speed is an important property for a most cryptography, so few people would adopt such a system until the threat seems more pressing.

frezik3• 13 years ago

Block ciphers can be easily made quantum-safe by doubling the key size (see "Grover's Algorithm"). We might have to update everyone's browser to support extending AES to 512 bits, but it's doable.

The real problem is public key ciphers that rely on prime number factorization. Eliptic curves are one solution, but the only people who seem to have in-depth knowledge about them are in the NSA.

KMag• 13 years ago

The mathematics are less well researched, and at least for some algorithms the keys are quite large. (For instance, a pretty standard sized Niederreiter key and a single Niederreiter signature put the minimum size for a certificate over 1 MB, which is a lot less onerous than it used to be, but a bit big for doing a lot of copying on cellular networks.)

I haven't heard this expressed anywhere, but it could also be that the McEliece and Niederreiter algorithms have a bit of a feel to them like the Merkle-Hellman knapsack algorithm that was thought for a long time to be secure.

Though, if you're being paranoid and can spare the cycles, it wouldn't hurt to take Elliptic Curve Diffie-Hellman (or ECIES) exchange, encrypt that using RSA (or ElGamal), and then Encrypt that using Niederreiter (or McEliece), like a bunch of Russian dolls nested by key/message size. All three crypto systems would need to be broken in order to recover the key.

tptacek• 13 years ago

Matthew Green and Paulo Barreto were making fun of this on Twitter. No, the use of a hash does not mean bitcoin will survive quantum cryptanalysis. As Green --- not a stranger to the workings of bitcoin --- puts it, "if the elliptic curve discrete log problem is solved, bitcoin is toast".

Further, the "smart" curve choice bitcoin made was simply not using the NIST P-curves. But lots of stuff chose not to use the NIST curves; that's why we have Certicom's curves and the Brainpool curves. Unfortunately, bitcoin didn't do that much better than the NIST P-curves; the Koblitz curves they use also have problems that researchers are exploring.

gigq• 13 years ago

The point in the article was that if you sent the coins to an address that never spent any coins (like the reference client does where it will always create a new "change" address for left over coins from a transaction) then the public key of the address that holds your coins will never be seen on the network.

Perseids2• 13 years ago

For everyone who was also looking for the tweets: https://twitter.com/pbarreto/status/395378161631784960

mkramlich2• 13 years ago

my takeaway from this article just reinforces the perception of Bitcoin I already had, namely: which do I trust more? a monetary system run by engineers & mathematicians. or a monetary system run by politicians/lawyers, government bureaucrats, and an old-money banking aristocracy? Choices, choices...

pilom• 13 years ago

I've worked with a lot of engineers. Most of us aren't really that smart and usually we make problems much more complicated than they need to be.

I'd trust a unique and fairly original monetary system run by good engineers. But most engineers are really not that good.

mkramlich2• 13 years ago

I've seen evidence that suggests the leading engineers behind Bitcoin are good. In contrast, I've seen repeated evidence over decades that the folks leading the US government are dangerously incompetent on things which are incredibly important to get right for all the rest of us, namely the economy, the environment/ecosystem and health care.

Glyptodon• 13 years ago

This is the first time I've seen information addressing quantum computers and bitcoin in a meaningful way (between the linked text and the additional info it links). As a relative layperson when it comes to such things it's nice to finally have some notion of Bitcoin's ability to cope with the quantum world.

Unexpected Ways in which Bitcoin Dodged Some Cryptographic Bullets

Related Stories