A brief history of the evolution of proof-of-work in cryptocurrencies. Part 2

Original author: Ray Patterson
  • Transfer
I bring to your attention a translation of the article “ The Proof-of-Work in Cryptocurrencies: Brief History. Part 2 »Ray Patterson from Bytecoin.org .

“A brief history of the evolution of proof-of-work in cryptocurrencies. Part 1 ”is here .


Crossbreeding


By the middle of summer 2013, more than a hundred altcoins were already in service, with almost half appearing in the last couple of months. Needless to say, almost all the "newcomers" were forks of Litecoin and used scrypt? Another trend of the season was PPcoin's newfangled Proof-of-Stake, so the combination of scrypt + PoS could be called the "standard set of beginner alcoiner."

Such (quantitative) popularity of scrypt and the beginning of the exponential growth of Bitcoin complexity led to a simple thought: scrypt-ASICs will appear the very second as soon as it becomes profitable. And although the giant November bubble - when Bitcoin reached $ 1200 - had not even begun to inflate, the search for a new PoW function began again.

How can I diversify the standard hash function? For example…another standard hash function! Sifcoin was the first to propose the idea of ​​successively hashing several popular functions, the role of which were taken by the finalists of the SHA3 contest: Blake, BMW, Groestl, JH, Keccak, Skein. The idea is quite simple: six fundamentally different algorithms are six different ASIC chips, that is (at first glance) a lot and expensive. In addition, if for some algorithm they find a back door (they don’t necessarily break the whole thing, but learn how to solve the “many zeros in the beginning” problem faster), then the whole scheme will more or less hold on.

Pioneers do not always get all the laurels: in the end, this six-hash algorithm gained popularity (and name) in the first fork of Sifcoin - the Quark currency. Conclusion: do not give your products the prefix "sif." Over the course of time, a dozen or two altcoins split off from Quark; one of them greatly surpassed the “dad” in popularity: it is Darkcoin (now called DASH ). The new PoW in it was called X11 and differed, as you might guess, in the number of hash functions used. He did not give anything fundamentally new (except for the order of the rounds), and therefore the prevalence of X11 (approximately in second place after scrypt) should be associated rather with the success of DarkCoin itself, in which there were many other changes (somewhat sensible, somewhat Not really).

X11 appeared at the beginning of 2014 and at first it worked exclusively on the CPU, which made everyone very happy. But in April, the complexity of DarkCoin doubled, which caused reasonable suspicions in the appearance of the GPU miner. Since no one recognized, a competition was announced for the open implementation of such software, money was collected - and a month later the hashrate had already grown by an order of magnitude on the new GPU miner. It turned out to be about 5 times more efficient than the CPU (scrypt - 10 times).

To date, there are many variations on the theme of X11 and Quark; some even have their own unique names: X14, X15 ... At the same time, it is clear to everyone that the algorithm is not at all ASIC-resistant in the full sense of the word. To calculate 11 different hashes instead of one is, roughly speaking, to make the pipeline 11 times longer. In other words, the price threshold for the payback of developing a piece of iron has only moved several times.

Thanks to various marketing techniques, individual SHA-3 finalists became popular in the solo version. For example, Keccak himself, aka SHA-3 himself. Well, everything is clear here: "like SHA-2, only better!". That is, there was no special idea of ​​confronting ASICs, except for the fact that it takes at least a year to develop and start production. But, on the other hand: we have a real fresh modern standard! Also, even a special Skeincon coin appeared, which used, apparently, the Skein algorithm (probably fans of Bruce Schneier).

Variety of species


Evolution made a round, and the thoughts of cryptocurrencies again returned to memory-bound algorithms. Take scrypt, for example: the algorithm is good, just the bad parameters!

Most likely, some kind of thought work was carried out, since cryptocurrencies with just different, static scrypt parameters did not appear. But the idea with dynamic memory was implemented right away in two versions:

  1. Scrypt-n. Recall the three scrypt parameters that were selected in Tenebrix and other Litecoin: N = 1024, r = 1, p = 1. The latter is responsible for the possibility of parallelization, we do not need this. N and r increase the required memory size, and r also increases the number of calls to the Salsa20 mixing function, i.e. has a larger CPU / memory cost coefficient than N. In this regard, it was decided to periodically increase N twice, forcing the algorithm to use just more memory. So, at launch, Vertcoin [9] requires 512Kb (N = 4096), after a year the appetites will increase to 1024Kb, etc. To rewrite the GPU miner, according to the creators, is nothing, but no one will be making a new ASIC every year.
  2. Scrypt-jane. The idea of ​​increasing N is still the same, but the process does not go according to a specific schedule, but is regulated by a pseudo-random formula that non-linearly depends on the current time. And although N is monotonously increasing (all right, “does not decrease”), the periods between recounts are more a divergent series (6.3,, 3,9,3,24,12,36 ...). In addition, scrypt-jane uses several mixing (Salsa20 / 8, ChaCha20 / 8 and Salsa6420 / 8) and hash functions (SHA2, BLAKE, Skein, Keccak) inside.

Another, fundamentally different memory-bound PoW function was Momentum , implemented in BitShares. It is very simple:

  1. Suppose we want to sign data D. First we get H = Hash (D), where Hash () is some cryptographic hash function
  2. Find such different values ​​of A and B that BirthdayHash (A + H) = BirthdayHash (B + H), where BirthdayHash () is a memory-bound function like scrypt.
  3. Now, if Hash (H + A + B) <TargetDifficulty (read - it starts with n zeros), then that's it, victory. Otherwise, we return to step 2.

As you can see, the main work is to search for collisions of two hashes in step 2. Of course, there you need to find not 256 matching bits, but less, but this is also a difficult task. Say, if you need to find a match of the first 64 bits, it will require 2 ^ 64 hash operations ... Or not?

A superhero comes to our aid: the paradox of birthdays . Its essence is that the probability of finding a collision among a certain set quadratically increases with the number of elements (because the number of unique pairs among the set also grows like that). In practice, this gives us the following assessment: to find ANY 64-bit collision with a 50% probability, we need to generate about 2 ^ 32 hashes (4 billion instead of 18 quintillion - that’s such a savings).

Why doesn’t it work with "ordinary" PoW, because there, too, there is essentially a search for collisions? The key word here is “any” conflict. In Bitcoin, you need to find a match with a specific pattern: N zeros at the beginning, and in Momentum, N any first bits must match.

There is an obvious compromise between time and memory. According to the creator, the algorithm should use about 2GB of memory per thread, i.e. an ordinary computer can even perform several parallel searches. At the same time, the destiny of ASICs, the strength of which is far from being remembered, remains only to look and envy (well, or be squared faster).

This approach has one drawback. All previous proof-of-work algorithms worked "instantly"; in the sense that, in fact, they were busting, and each attempt took a fixed time and they all had the same chance for success. Each verified hash is like throwing a cube with 2ˆ256 faces, and at any moment you could “take another dice” (start work on another block) and the chances would not change. What does this mean for the miner? This means that if he receives a new transaction that he wants to include in the block, he will have to update the hashed structure (“take another cube”). This takes a split second, so it can be said that the losses are negligible. In the case of Momentum, everything is not so simple. The next iteration of hashing and adding a new hash to the global 2GB table has a better chance of success than the previous one! Clear, that then updating the block header and starting building the table from scratch is very disadvantageous. If with every roll of the die the chances of finding a solution are increasing, it is more profitable NOT to take a new die. That is, in the end, it is not profitable for the Momentum miner to accept new transactions and “dump” their progress: and in the end, those transactions that were sent BEFORE you start working with this block will fall into the block. For Bitokin, this would mean that the average transaction confirmation time would increase from 10 minutes to 20. that were sent BEFORE you start working with this unit. For Bitokin, this would mean that the average transaction confirmation time would increase from 10 minutes to 20. that were sent BEFORE you start working with this unit. For Bitokin, this would mean that the average transaction confirmation time would increase from 10 minutes to 20.

Minerals


Apart is the one and only PoW function, which appeared in the summer of 2013. Before moving on to it, let's realize one problem in general with proof-of-work. I’ll make a reservation right away that this may not seem to anyone a problem (or even vice versa), i.e. it's about what many people consider a problem.

All this work is useless! Nowhere, except inside the cryptocurrency, nobody needs these hashes. You can, of course, print and hang on the wall the smallest of the hashes found , but they have no practical use. We will not go into philosophical discussions about whether this work should be useful or not at all, but just note the fact that coming up with a PoW function that would be beneficial is not a trivial task.

However, one was found. The developer of SunnyKing (he invented [or, at least, was the first to implement] the Proof-of-stake scheme) presented the following scheme to the public: the proof of the work done is the found chain of primes satisfying some properties. More precisely, it should be a Cunningham sequence of the first or second kind or a combination of them (the so-called bi-twin primes ).

The first is why this is useful. These prime numbers, of course, are not small (otherwise it would be quite easy to find them): of the order of hundreds of digits in decimal notation. However, for RSA encryption this is still not enough, but you need to use random numbers there. Cunningham chains are rather a curious mathematical structure that (in theory) can open the next curtain in number theory. In the end, until the advent of public-key cryptography, this entire area was considered only a “beautiful, useless science,” so any efforts, even of such an “olympiad” nature, are considered worthless.

Now about how exactly you can associate primes with cryptocurrency blocks. Suppose our chain begins with some number P. The hash of the block header (in which the nonce field is enumerated) is interpreted as an integer. And that number should be a divisor of P-1 or P + 1. The complexity of the network is the length of the required chain of primes (it ranges from 7 to 11). That, in general, is the whole idea. Thus, it is impossible (i.e., very difficult) to use a randomly found chain (or even someone else's, from another block) to prove work on your own header.

There are two drawbacks: firstly, we do not know if there is a simpler way to solve the Primecoin problem (this cryptocurrency is called). With hashes, everything is more or less clear: an attack to find the prototype of a cryptographic hash function is almost hopeless (at least, all cryptographic pillars are based on this assumption - and God forbid it collapses!), So there is no chance of picking up a block for an existing hash. But to say the same thing about the Primecoin block (where all P-1 or P + 1 factors are suitable for us) is already difficult.

Secondly, the complexity of mining. As already mentioned, it is proportional to the length of the chain. However, the length is an integer and does not take into account the change in the fractional part. Thus, a change in complexity from 9.0 to 9.99 will be completely invisible, but from 9.99 to 10 it will already drastically affect the overall hash rate and the speed of appearance of new blocks.

In addition, this function, obviously, uses only the CPU power of the computer, no memory. For a long time she did not have a GPU miner, but when he appeared, it became clear that Primecoin is not an anti-ASIC grail. Perhaps that is why he remained in his niche with a couple of forks, and his PoW function did not become popular.

PoWer Sapience


And finally, consider a completely different one branch of the phylogenetic PoW tree for cryptocurrencies: CryptoNight and CuckooCycle , which began to develop in parallel with the others immediately after the failure of scrypt, as a CPU-only algorithm.


CryptoNight is the name of the hash function in the CryptoNote code (don't get confused!), Which includes many other differences with Bitcoin (starting from the fact that it is not fork at all - although now you won’t surprise anyone with it). There is no CryptoNote cryptocurrency as such, but there are several that are built on this technology: Bytecoin, Monero, DigitalNote, etc. ... Each if its own differences, but PoW function is common for everyone.

CryptoNight uses the general idea of ​​scrypt about "a large data table in which random queries are made." However, the creators noted a drawback associated with the linear compromise “time” - “memory”. In scrypt, the main (second) layer creates each new data block based on the previous one. Thus, if we store, for example, only every second block of N, then in 50% of cases we will have to recount it again. There are N such random accesses to the array, so it turns out that having saved half the memory, we calculate N + 1 / 2N = 150% of the blocks, that is, only one and a half times more. Similarly, keeping only every third block, we will not notice this in 33% of cases, in 33% - we will recalculate one extra block, in 33% - two extra ones. That is, the whole work: N + 1 / 3N + 1/3 * 2N = 2N = 200%. Total, as calculated, saving only 1 / s of all data increases the total amount of work only (s-1) / 2 times (perhaps, by the way, that is exactly what scrypt-ASICs work).

In this regard, CryptoNight has three fundamental differences:

  1. The next block is calculated based on ALL previous ones. Thus, the ejection of, say, every second block will lead to the fact that in order to restore the pass, it will be necessary to recount not one block, but all the previous ones at once.
  2. Accesses to the data array are not only read, but also write. So, it turns out that for each element a “second dimension” appears - time; and recounting becomes even more time consuming.
  3. Finally, the total number of calls to the array is much larger than the number of elements in the array (2 ^ 20 versus 2 ^ 15), that is, the resulting array is transformed beyond recognition by the end of the cycle.

In addition, 64-bit operations (multiplication, addition) and AES encryption as a mixing function are used internally. This is a curtsy in the direction of modern processors with built-in relevant instructions (and a stone in the GPU garden). The total memory required by CryptoNight is 2 MB, i.e. approximately the size of the L3 cache per core. Not to say that this is an unattainable height for the ASIC, but still the cost bar is quite high.

In general, CryptoNight can be characterized as a very effective practical algorithm: there is, of course, a GPU miner for it, but it has a serious advantage only in comparison with old processors (32 bits or a small cache). As far as one can judge, all its details are aimed precisely at the practical effectiveness of conventional computers (of which there are billions).

CuckooCycle is, you can say, the exact opposite. Firstly, it has a theoretical information base. Not in the sense that it was developed only in theory (at the moment there are no such cryptocurrencies), but in the fact that its reliability is based on the complexity of solving the information-theoretic problem: searching for cycles in a bipartite graph. Basically, all modern public-key cryptography is designed the same way.
The main idea (if you do not go into graph theory itself) is the same as in Momentum - by using a certain amount of memory we get the optimal algorithm for solving this problem. Computational operations are minimized, therefore, accessing this memory takes the main time. Moreover, the verification of the solution, of course, is much faster.

Main question, which can be asked: is the described algorithm really optimal? Is there any tricky CS article coming up tomorrow with another, more efficient solution that doesn't use much memory? Basically, this is the main thing that distinguishes CuckooCycle and CryptoNight.

Also popular now: