Cryptocurrency algorithms

In My Humble Opinion
1

I was just reading about Litecoin using scrypt to try to make it ASIC resistant and then the subsequent ASIC’s that went on the market for that algorithm.

Seems like anything that is done to tweak an algorithm one direction or another (memory vs processing etc.) can be circumvented with special hardware if the market supports the effort (return on investment).

My solution:
Create an algorithm with all kinds of useless complexity that includes memory and processing such that the investment to create special hardware to support that algorithm is prohibitive. For example, an algorithm that relies on the complete complexity of the x86 instruction set, addressing modes and side effects, thus creating a level playing field.

Opinions?

2

Litecoin is basically a fork of Bitcoin. I presume you are talking about tweaking the specific Hashcash algorithm used, but this does not really make a difference to how the whole thing works; it’s just a cryptographic hash function that is used to force the user to burn computing power.

Agreed that people should not have to buy special hardware to use it, but the obvious way to solve that is to do away with the hashcash altogether and not try to implement something functionally identical to Bitcoin.

3

The difficulty is that your algorithm needs to have provable characteristics, and as you increase the complexity of the implementation, that gets way harder. Bitcoin uses the SHA-256 hash, which is a well-tested algorithm, and part of the reason why we’re confident in its characteristics is because the basic operations are so simple: just shifts and bitwise operators.

The more complex the basic ops, the more difficult the analysis. So it’s very likely the algorithm would contain a hole of some kind–a shortcut that allowed skipping some of the computational steps, or even being able to reverse the computation outright. And that would break the whole thing.

I also think it would be pretty much impossible to use all of the complexity of x86 or whatever. There are just too many modes. Your inner computational loop is going to be pretty short, so creating an ASIC that just implements that one loop in hard-coded fashion is still reasonable. I’m not sure how many possible x86 instructions there are but it must be well past the billions. It’s not reasonable to hit every possibility.

4

The underlying code for all major crypto currencies is open source and is occasionally tweaked for efficiency. This is part of the trust for crypto which makes it all but impossible for malicious code to be added. Any code added for useless complexity would rapidly be edited out pretty quickly in the quest for more speed.

What is “open source” and why is it important for cryptocurrency and open blockchain projects?

5

But that is exactly what happened with scrypt, computations were added/structured in a way to emphasize the need for memory (e.g. long string of pseudo-random values with pseudo-random access).

It wasn’t exactly useless, it was purposefully added to increase the cost to create ASICS’s to perform the computations.

6

Good point about complexity and analysis. So I guess the trick is to find the simplest set of operations that require a significant cost to design a specialized circuit. I need to ponder that one.

7

OP was exaggerating if he implied a motive to use “every” instruction. But it would be easy to add complexity to make custom processing much more difficult, and that would only increase the difficulties of shortcuts or reversal. Intel’s BSF opcode (FFS, with the output XOR’ed into a hash) is an example of using a simple opcode to impede customizers, but why not go whole-hog and calculate a Tangent and/or Arcsine (with prescribed arithmetic details) in the SHA-256 inner loop if raw complexity is the goal? :slight_smile:

But (Color me ignorant) I have trouble viewing Bitcoin’s billion-dollar annual transaction costs as a feature rather than a bug. The U.S. Treasury spends less than that printing banknotes.

8

Because, aside from the analysis issue, that only makes things better for ASICs.

The FPTAN instruction on x86 takes dozens of cycles to compute just one. Intel/AMD don’t bother making it faster because it’s a rarely used instruction. But if your algorithm needed it, you could put hundreds or thousands of tangent units on one die, and designed for very high throughput. The ASIC is now tens of thousands of times faster than the CPU, defeating the goal.

If I were going this route, I’d pick ops that were very close to the heart of x86–their addressing ops and some unique bitwise ops, for example. I personally had need for a hash that was very fast on x86. I found one that had an inner loop of (64 bit integer):
x’ = x*m + c

Repeat zillions of times. Now, x86 doesn’t have a fast fused multiply-add instruction. But it does have an address generator instruction that can do:
r = x2[sup]{0, 1, 2, 3}[/sup] + x{0, 1} + c

m, above, must be prime. So if you stick to this variant, it’s super-fast:
r = x2[sup]2[/sup] + x1 + c = x*5 + c

An ASIC would still be faster of course, but in this particular case, x86 does quite well because the inner loop maps nicely to some high-throughput instructions. So this is the kind of thing you’d want to look at, I think.

9

If this was actually true, then Bitcoin mining would have gone away a long time ago. “Mining” is just running deliberately difficult operations that serve no useful purpose and hoping to be the first to finish, the whole mining part of bitcoin is just code added for useless complexity in the first place.

10

That’s not true, I think. The complexity is to make it hard to forge a block chain — system integrity depends on long block chains being reliable (too difficult to forge).

But I don’t understand why it matters whether the algorithm is hard to port to custom fast hardware, assuming it’s still sufficiently difficult. Is it that the fact that many thousands of computers will be “mining” in parallel is key to security?

11

The goal is to keep mining in the hands of a large group of average joe’s vs a small group of entities with a lot of money. The smaller the group that controls mining, the higher the chance of collusion.

SCRYPT was designed to try to avoid what happened with bitcoin which is an ever increasing arms race of specialized (and possibly expensive) hardware that reduces who can affordably do mining.

12

The reasons for the “every instruction” comment:
1 - Complexity
By using every instruction, the ASIC has to essentially emulate most of an x86 CPU which is expensive enough that it’s not worth the money (at least not right now).

2 - Speed
The ASIC creator is most likely not going to substantially increase the performance of x86 due to the fact that Intel isn’t dumb and has market pressure to continue to improve. Which means average joe’s computer would be competitive against any alternate hardware.

13

It depends on what you mean by “need”.

If Bitcoin et al weren’t distributed systems, the hashing would not need to be so difficult. Any single ordinary PC could keep up with the rate. You would still have a hash for self-verification, but it would be fast. Lots of applications (BitTorrent, etc.) use hashing for this reason and they work at high rates.

But Bitcoin is designed to be resistant to a malicious adversary. More specifically, it’s designed so that unless you control more than around half the total computing power in the system, you can’t inject forged data (duplicate transactions, etc.).

It does so by requiring the computed hash to be smaller than a certain integer value. Put another way, it needs a certain number of leading zeroes. Of course if you hash some data you’ll always get the same output, so you pad the input slightly with a bit of useless data that can be changed.

Once someone in the system finds a hash that fits, they are awarded a finders fee (created out of nowhere) by the system. As long as most of the clients are “honest” (or at least not conspiring with each other), it works. That block plus the padding value is added to the blockchain and everyone starts working from there.

If someone wanted to “fork” the blockchain, they could try, but with so few computing resources they would quickly fall behind. No one else would accept hashes with too-few zeroes and they would abandon that fork of the chain.

It’s the leading-zero requirement that’s the useless complexity. No need at all except to require the computing horsepower of the entire system to verify the new blocks, which is how Bitcoin achieves their “proof of work” claims.

One reason why you’d want to make an ASIC-resistant system is because only hard-core users are going to buy it. If it’s 10,000x more efficient than a CPU, then using a CPU is useless–you’ll never pay back the power cost. So the system is controlled by those that can afford ASICs, and that means a concentration of power. It makes it easier to hit that 50% mark. But if a CPU is still pretty good, then anyone with a computer can contribute. No bit party can hope to compete with the computing power of hundreds of millions of computers.

14

A bit of background on hashes in case anyone is unfamiliar.

A hash is a way of converting a chunk of input data into a number. Usually the number is a long one; 64 bits at the minimum and more likely in the 128-256 range. Bitcoin uses 256 bit hashes. You want the number to be well-distributed in their bit space to minimize the chance of a “collision”, which is when two chunks of different data hash to the same value. This is guaranteed to happen since the number has finite bits while the input data is unbounded, but if the hash has good properties then it’s very unlikely to come up.

Hashes used for security also have the property of being irreversible (like my raincoat!). That is, there is no way to pick the output number and then figure out the input data that converts to that. Or rather, no way faster than brute force–trying many combinations until you reach the answer. In fact, good hashes have the additional property that you can’t reverse the hash just to hit some desired property of the output: that is, constraints like “at least 75% of the bits are 1” or “there are 30 leading zeroes”.

So when the Bitcoin network only accepts a hash with (say) 30 leading zeroes, it means that the clients must try roughly 2[sup]30[/sup] combinations before finding one that produces the desired output. Of course this is statistical so it’s possible to get lucky and find one early (or late), but in practice it averages out in the end.

The hash also verifies the block forever. No one can change some past transaction (say, to grant themselves a million bitcoins) because to do so they’d have to replicate the already generated hash, which everyone else has stored. That would require 2[sup]256[/sup] operations; completely unfeasible for anyone.

The network gradually increases the difficulty of the problem to account for increasing computational power and to limit the total number of possible coins. It does so by increasing the leading-zero requirement; every extra zero doubles the required computation.

The irreversibility is the most important component here. Unfortunately, no one has proven the property and it’s probably impossible. Researchers try very hard to find holes, though, and have managed to reduce the effective complexity of SHA-256 from 256 bits to as low as 248.5 bits. This is still computationally infeasible, of course. Also, Bitcoin uses a nested hash which I don’t think is subject to the same attack vectors, so in practice it’s very close to 256 real bits.

15

Someone posted this in another bitcoin thread but I bookmarked it as an excellent tutorial on how blockchains work.

Blockchain 101 - A Visual Demo

16

The more cynical amongst us might see this as them in bed with people who build the ASICs.
Like those shit-sucking scam artists a few years ago who marketed Bitcoin mining hardware but rarely got around to actually shipping anything because they were busy “testing” customer hardware by mining BTC for themselves.
This shit stinks to high heaven.

17

You do not technically need any sort of “mining” action at all in order to implement a cryptocurrency; this feature is peculiar to the Bitcoin protocol and clones thereof. For example (please do not consider this an endorsement either of the code or the way it is being used), consider the open-source(?) Ripple payment protocol (2012): there is a big public ledger of accounts, and transactions are validated by consensus. This provides adequate security if you assume that only a minority of servers are buggy or malicious.

ETA hash trees are used in this protocol, but for actual useful hashing, not to burn resources

18

Understood there are alternate approaches to distributed currency/ledger each with pros and cons (I’m familiar with ripples consensus process).

This thread is specifically about the theoretical challenge of structuring mining algorithms in a way that reduces the advantage of having specialized hardware like ASIC’s.

19

I don’t see how you could design something which runs acceptably on general-purpose hardware which couldn’t be sped up by purpose-built ASICs.

20

Here’s one method:
Make the algorithm substantially dependent on the details of the x86 CPU (e.g. use every instruction and addressing mode and in ways that make an x86 CPU the ideal resource).

To create custom hardware to improve on that would require essentially creating a better/faster x86 CPU than Intel. But given that there is already considerable market pressure and competition (e.g. AMD vs Intel) in the x86 space, the chance that some company could improve on it substantially with a custom chip is unlikely.