# Mine Bitcoins with PENCIL and PAPER

Google engineer Ken Shirriff has mined Bitcoins with nothing more than a paper and pencil. While he says the process is about a quintillion times slower give or take than than a Bitcoin mining rig, the algorithm was easy enough to crunch. Shirriff completed a round of SHA-256 in 16 minutes and 45 seconds at which rate a full …

1. #### Prediction

"A cryptographic hash function takes a block of input data and creates a smaller, unpredictable output."

Isn't the output totally predictable, if you know the hash function and the input data?

1. #### @frank ly

Not the point. The point is that inverting the algorithm is ... err ... difficult.

2. #### Re: Prediction

Isn't the output totally predictable, if you know the hash function and the input data

You'd hope so, otherwise the output would be random, and comparing two hashes to see if their input was the same is pointless.

3. #### Re: Isn't the output totally predictable ...?

The output is deterministic (detemined) by the input data, true; but that doesn't mean you can predict it. "Predict" implies knowing in advance of the event (or in this case, the calculation). The computation isn't a prediction of the results it's acutally getting the result.

4. #### Re: Prediction

The output can [should] not be determinable by any means other than actually running the hash function against the data, at which point you haven't predicted it; you've calculated it.

5. #### Re: Prediction

That's where he's sacrificed speed for a genuine improvement on the programming approach. If you run a verified implementation of the algorithm, the output is disappointingly predictable; if you do it manually, the output becomes truly unpredictable. WIN!

2. #### Take that

+1 for spending the effort to remind those pesky machines that anything they can do, a fleshy can do.

Albeit a quintillion times slower, but it's the principle of the thing.

1. #### Re: Take that

That's ok, we can still run up stairs a quintillion times faster than the next Cray computer can. ;)

1. #### Re: Take that @ TechnicalBen

Remember Emo Phillips's one liner?

"A computer beat me at chess; but it was no match for me at kickboxing."

3. "Forget Sudoku,"

Nothing to remember in the first place. It's a crossword puzzle, and trivial.

"crunch SHA-256 algos"

Nah. Doable, but entirely too boring. Crunching numbers is what computers were invented for, remember? I'd rather look out the window, or maintain the mahogany and teak on a boat, when I have a little down-time.

Kids these days ...

1. This post has been deleted by its author

1. #### Re: More fun...

And that's why bananas have skins on!

2. "Forget Sudoku,"

Nothing to remember in the first place. It's a crossword puzzle, and trivial.

Sudoku isn't even vaguely related to a crossword puzzle. It's a Latin square with additional structure and some values masked. Calling Sudoku a crossword puzzle is like claiming TSO and sh are the same because they're both command-line interpreters.

As for whether it's trivial: the constraints are clear, and the problem can obviously be solved by exhaustive search with backtracking, and the search space is limited with a (small) constant maximum depth. So in a formal sense it's trivial. Whether a given puzzle is trivial in practice for a human to solve with pen & paper methods depends on the structure of that puzzle and the solver's capacity for backtracking; it's possible to construct well-formed (single solution) puzzles that require testing eight possible paths (three noncollinear cells each with two possible values that aren't locally constrained further), and that's beyond most people's ability to do mentally, without taking notes.

Solving by machine is simple (which is why I don't trust the statistics collected by websudoku.com, for example - I could easily write a solver in Javascript that solved their puzzles right on the page), but that doesn't mean Sudoku isn't a useful paideia.

I'd rather look out the window, or maintain the mahogany and teak on a boat, when I have a little down-time.

I've found lots of ways to spend my time, too, but I try not to sneer at everyone else's.

4. #### Cogwheels

How long till a someone makes a Babbage type Bitcoin mining rig for fun?

For extra points use nanotech, maybe bucky balls?

1. #### How long till a someone makes a Babbage type Bitcoin mining rig for fun?

in Minecraft.

1. #### Re: How long till a someone makes a Babbage type Bitcoin mining rig for fun?

Well I don't know about Bitcoin mining, but somebody has made a calculator, and you can find loads of various hard drive projects, so I'd say it's only a question of time until we get a Bitcoin miner on a mining game.

5. #### how long...

...till we find out what theorem the worlds bitcoin miners have been tricked into proving?

1. #### Re: how long...

Oh I love that idea @Paul_Shirley....

Now I'm hoping Umberto Eco or Thomas Pynchon weave that into a plot line. It would be shame if it only got the Dan Brown treatment.

I have discovered a truly marvellous proof of this, which this margin is too narrow to contain

1. #### Re: how long...

I suspect it was a reference to a certain Terry Gilliam film.

2. #### Re: how long...

According to Algorithmic Information Theory, they've already proven a whole bunch of 'em. They're just not interesting theorems.

But yes, converting some interesting problem into a cryptocurrency mining problem is a nice idea.

6. One thing I've never seen discussed regarding Bitcoin is what happens if someone finds a way to reverse the hash function or in some other way dramatically reduce the effort required to discover valid source data for a given hash. Over night the value of Bitcoins is going to drop through the floor. In fact I wonder if even the rumour that SHA-256 might be broken would be enough to cause a sudden drop in value. I could imagine manipulation something like this:

1) Start dumping a lot of Bitcoins on the market and claiming that SHA-256 is broken

2) Wait for a price drop

4) Wait for price to go back up

4) Profit :-)

I imagine this would be illegal on the stock market but in the Bitcoin market?

1. Simpler is to start denying the rumours that it is broken. There don't even need to be rumours, the denials will start them if the denials sound suspicious enough.

1. Shhh! I TOLD you to keep quiet!

2. Finding a way to reverse the hash function would mean an earthquake in theoretical computer science. It would be a discovery on the order of cold fusion. Scientists have tried for 30 years to solve such problems, and while we don't actually have proof, there is little chance that it can be done in a reasonable amount of time.

1. #### Reverse SHA256?

Anything is possible, even if very unlikely. If the NSA/GCHQ/Unit 8200/etc. had found a way to compromise some of these central tenets of modern cryptography, do you think they'd let it be known? It'd be the best secret ever.

2. Finding a way to reverse the hash function would mean an earthquake in theoretical computer science. It would be a discovery on the order of cold fusion.

Finding a way to reverse a cryptographic digest would be an earthquake for causality, since by the Pigeonhole Principle it would in effect require time travel, or at least the ability to extract arbitrary information from the past, which in turn breaks thermodynamics.

Finding a way easier than brute force to discover a preimage (not the preimage) of a cryptographic digest has been done for a number of cryptographic digests already. The sky has not fallen.

If the strength of a cryptographic digest were based on some problem with interesting consequences - which probably boils down to something known to be NP-Complete - then a polynomial-effort deterministic algorithm for discovering a preimage would indeed be hugely important for theoretical computer science (and mathematics). As it is, when a crypto hash falls, it's of practical importance if the hash is in use, and of theoretical importance if the attack is new, but it's certainly not cold fusion.

1. #### Hmm

I have theorized that one solution to the Copenhagen Interpretation of quantum mechanics and a possible workaround for the requirement for parallel Universes is that the wavefunction collapse is temporal, ie the answer travels back in non polynomial time to when the question was asked.

So this isnt actually impossible, in fact it might go a long way to solve P=NP if indeed such a system exists.

(cough) D-wave (/cough)

If indeed they have a time machine of sorts then all sorts of interesting possibilities emerge assuming that there isn't some fundamental limit on entanglement of millions rather than hundreds of adiabatic qubits.

3. #### @AC "in the last few minutes" (whatever THAT means, ElReg)

Try it. Report back.

Personally, I feel that anyone dealing in unregulated currency deserves what they get. Have fun!

4. The problem with this strategy is that if you have a large enough stash of Bitcoins that selling it will affect the market price, the same works in reverse. You will have extreme difficulty buying them all back without causing the price to rocket. Quite possibly it will go above what you sold them for before you've managed to retrieve your hoard.

Successfully making the market believe that there may be a risk that SHA-256 is broken may cause it to fall lower than if you had just dumped the Bitcoins without saying anything. But again, there is the opposite effect - when you try to buy them back it will signal that there isn't a problem after all and everyone should pile back in.

Not saying it couldn't work. But so could betting on the 10-1 at Chepstow. Like all currency speculation it's just gambling.

1. Exactly. People wrongly assume that the big holders in a given market can manipulate the market to their advantage by violently selling and buying. While they certainly have the ability to do this in a way that creates violent turmoil in the market, it would in no way be to their advantage.

That's because violently selling your holdings will oversaturate the market and cause you to get a very low price. On the way up, violently buying into the market will result in a shortage and force you to pay a very high price.

So while market juggernauts can certainly manipulate the market, they certainly don't. The only time you see such market manipulation is when the actor has political motivations, not financial motivations.

5. That would be a total disaster for bitcoin. But people have good reason to think it won't happen. Even worse, and possibly more likely since it's newer technology would be someone finding a way to break the epileptic curve encryption used to prove ownership of each address.

1. AFAIK there are a limited number of Bitcoins anyhow, right? So it would just reach the limit quicker and level out sooner?

Or is there something about it I missed?

2. quote: "...finding a way to break the epileptic curve encryption used"

Ok, where do I send the bill for the keyboard? :D

(I think you meant "elliptical")

Here are some other fun challenges young Bitcoiners can do in their spare time!

- Why not write a manifesto detailing how an anarcho-capitalist society will work in practice! Should socialists, conservatives, and other statists be allowed to live, or should they be summarily executed?

- Work out why scams proliferate in the world of Bitcoin, but make sure the existence of the scams >really< show Bitcoin gets stronger!

1. #### Re: Other fun tasks!

quote: "- Why not write a manifesto detailing how an anarcho-capitalist society will work in practice!"

Answer: they already are. Most capitalist societies are de-facto anarcho-capitalist, it's just that one group ("government") has the largest collection of paid enforcers and can thus exert influence over the general population under threat of violence. Note how another group ("criminals") refuses to subject themselves to the rules laid out by the first group and wilfully ignores them, even knowing the consequences will be violent.

Or had you never thought of it that way? The continued existence of criminals shows that all societies have not (and apparently cannot) force people to conform if they do not wish to conform, and thus all societies are at least part anarchy. IMO, anyway.

quote: "- Work out why scams proliferate in the world of Bitcoin, but make sure the existence of the scams >really< show Bitcoin gets stronger!"

Scams also proliferate in the world of money. Actually, scams proliferate in any field where something of "value" exists, whether it has an intrinsic value or has value as a barter token. Any argument regarding the existence of scams affecting the usefulness of Bitcoin as a whole is equally as applicable to USD or GBP (or gold, or camels).

Since we have been using barter systems for hundreds of years, and people have been scamming for hundreds of years, I would conclude that the existence of scams is generally not considered enough to preclude their use. I would assume that this would also hold true for Bitcoin as it has for all of the other barter systems we have in place.

1. #### Re: Other fun tasks!

"it's just that one group ("government") has the largest collection of paid enforcers and can thus exert influence over the general population under threat of violence. Note how another group ("criminals") refuses to subject themselves to the rules laid out by the first group and wilfully ignores them, even knowing the consequences will be violent.

Or had you never thought of it that way?"

1. #### Re: Other fun tasks!

it's just that one group ("government") has the largest collection of paid enforcers and can thus exert influence over the general population under threat of violence. Note how another group ("criminals") refuses to subject themselves to the rules laid out by the first group and wilfully ignores them, even knowing the consequences will be violent.

Or put another way, the monopoly on violence is never total.

Ah, Max Weber, you silver-tongued devil.

(There's been a lot of thinking about the monopoly on violence since Weber introduced the concept in the early twentieth century. The Frankfurt School, Foucault, the poststructuralists... and a lot of novelists, of course. Contemporary thinking usually identifies a lot of exceptions beyond criminal activity per se, but it's the obvious example and nicely illustrates some of the complexities in the operation of political power.)

2. #### "Here are some other fun challenges young Bitcoiners can do in their spare time!"

- Find a way to leave the house and meet girls!

Bitcoin never ceases to amaze me. So much intelligence and ingenuity poured into being colossally stupid.

1. #### Re: "Here are some other fun challenges young Bitcoiners can do in their spare time!"

Bitcoin never ceases to amaze me. So much intelligence and ingenuity poured into being colossally stupid.

So ... it's like most other human activities, eh?

8. #### In a gold rush, people selling spades make money

And on that basis I have a couple of biro's and four pads of paper from a tech vendor presentation that I will sell to the highest bidder.

1. #### Re: In a gold rush, people selling spades make money

Indeed - just look at how much "specialist mining hardware" is now available, even from mainstream hardware retailers (i.e. not just fleabay anymore).

9. #### Proof of Concept

It seems this would be the sort of thing a quantum computer would be ideal to implement. I expect I will wake up to news that some academic type now owns all the BitCoin any day now.

1. #### Re: Proof of Concept

I wonder though it if would hit a few snags. Things like looking up a list is super quick with QM systems. Getting the list in the first place is the slow part with Bitcoin.

But for running transactions, the it would be the fastest thing!

2. #### Re: Proof of Concept

Interesting question. Has anyone demonstrated a nondeterministic algorithm for finding 2-SHA-256 preimages that outperforms brute force? And does it have reasonable characteristics (eg in space requirements)? I haven't heard of one.

Grover's algorithm doesn't look directly applicable to me - I think the necessary precalculation would take as long as brute force. Basically it's equivalent to creating a rainbow table. But I could be wrong; I haven't given it any real thought.

10. #### Just a thought

1) autistic savants are very rarely great (as in genius level) mathematicians

2) It is entirely possible that one day some autistic savant reads this and

3) becomes a billionaire literally overnight after finding a shortcut in the algorithm

AC, because this would make him a bigger target than Assange...

## POST COMMENT House rules

Not a member of The Register? Create a new account here.