Chapter 8: Alternative Mining Puzzles
Mining puzzles are at the very core of Bitcoin because their difficulty limits the ability of any one party to control the consensus process. Because Bitcoin miners earn rewards for the puzzles that they solve, we expect that they’ll spend considerable effort trying to find any available shortcuts to solve these puzzles faster or more efficiently, in the hope of increasing their profits. On the other hand, if there’s work that helps the network but doesn’t directly help them solve puzzles any faster, miners might be incentivized to skip it to minimize their costs. So the design of the puzzle plays an important role in steering and guiding participation in the network.
In this chapter, we’re going to discuss a variety of possible alternative puzzle designs, assuming we could modify Bitcoin’s puzzle or even design a new puzzle from scratch. A classic design challenge has been to make a puzzle which is ASIC‐resistant, leveling the playing field between users with ordinary computing equipment and users with optimized custom hardware. What else could we design the puzzle to achieve? What other kinds of behaviors would we like to encourage or discourage? We’ll talk about a few examples with various interesting properties, from decreasing energy consumption to having some socially‐useful side effects to discouraging the formation of mining pools. Some of these are already used by altcoins, while others are research ideas that might turn out to be used in the future.
8.1 Essential Puzzle Requirements
Copyright By PowCoder代写 加微信 powcoder
We’ll start by looking at some essential security requirements for mining puzzles. It doesn’t do us any good to introduce fancy new features if the puzzle doesn’t still satisfy the basic requirements that it needs to keep Bitcoin secure.
There are many possible requirements, some of which we’ve talked about in Chapters 2 and 5. Mining puzzles need to be quick to verify because every node on the network validates every puzzle solution — even nodes that aren’t involved in mining directly, including SPV clients. We would also like to have adjustable difficulty so that the difficulty of the puzzle can be changed over time as new users enter the network with increasing amounts of hash power contributed. This enables the puzzle to be difficult enough that attacks on the block chain are costly, but puzzle solutions are still found at a fairly steady rate (about once every ten minutes in Bitcoin).
What exactly is Bitcoin’s mining puzzle? So far we’ve just called it “Bitcoin’s puzzle.” More precisely, we can call it a partial hash‐preimage puzzle,since the goal is to find preimages for a partially specified hash output — namely, an output below a certain target value. Some other rare property could also work, such as finding a block whose hash has at least k bits set to zero, but comparing the output to a target is probably the simplest.
It’s easy to see how Bitcoin’s SHA‐256 hash‐based mining puzzle already satisfies these two requirements. It can be made arbitrarily more difficult by tweaking a single parameter (the target). Checking solutions is trivial, requiring just a single SHA‐256 computation and a comparison, no matter how difficult the puzzle was to solve.
Progress‐freeness.Another central requirement is more subtle: the chance of winning a puzzle solution in any unit of time should be roughly proportional to the hash power used. This means that really large miners with very powerful hardware should only have proportional advantage in being the next miner to find a puzzle solution. Even small miners should have some proportional chance of being successful and receiving compensation.
To illustrate this point, let’s think about a bad puzzle that doesn’t satisfy this requirement. Consider a mining puzzle that takes exactly nsteps to find a solution. For example, instead of finding a block whose SHA‐256 hash is below a certain target, we could require computing nconsecutive SHA‐256 hashes. This wouldn’t be efficient to check, but nevermind that for now. The bigger problem here is that since it takes exactly nsteps to find a solution, then the fastest miner in the network will always be the one who wins the next reward. It would soon become clear which miner was solving every puzzle, and other miners would have no incentive to participate at all.
Again, a good puzzle gives every miner the chance of winning the next puzzle solution in proportion to the amount of hash power they contribute. Imagine throwing a dart at a board randomly, with different size targets which correspond to the mining power held by different miners. If you think about it, this requirement means the odds of solving the puzzle must be independent of how much work you have already spent trying to solve it (because big miners will have always spent more work). T h i s i s w h y a g o o d m i n i n g p u z z l e i s c a l l e d pr o g r e s s ‐ f r e e .
From a mathematical perspective, this means that a good mining puzzle must be a memoryless process— anything else would inevitably reward miners for past progress in some way. Therefore any feasible puzzle will inherently involve some sort of trial‐and‐error. The time to find a solution will therefore inevitably form an exponential distribution as we saw in Chapter 2.
Adjustable difficulty, fast verification, and progress‐freeness are three crucial properties of Bitcoin mining puzzles. SHA‐256‐based partial pre‐image finding certainly satisfies all three. Some people argue that other properties which Bitcoin’s mining puzzle satisfies are also essential, but we’ll discuss other potential requirements as they come up while we explore other potential functions.
8.2 ASIC‐resistant puzzles
We’ll start with the challenge of designing an ASIC‐resistantpuzzle, which has been by far the most widely discussed and sought after type of alternative mining puzzle. As we discussed in Chapter 5, Bitcoin mining was initially done primarily with ordinary computers, eventually extended to GPUs and customized FPGA devices, and now is almost exclusively done by very powerful optimized ASIC chips.
These ASICs are so much more efficient than general purpose computing equipment that mining with an ordinary computer (or even some early generation ASICs) is no longer worth the price of electricity, even if the hardware is free.
This transition has meant that most individuals participating in the Bitcoin ecosystem (for example customers or merchants transacting using Bitcoin) no longer have any role in the mining process. Some people feel this is a dangerous development, with a smaller group of professional miners controlling the mining process. In Satoshi Nakamoto’s original papers on Bitcoin, the phrase “one‐CPU‐one‐vote” was used, which has sometimes been taken to mean Bitcoin should be a democratic system owned by all of its users.
Others feel the rise of ASICs is inevitable and not to the detriment of Bitcoin, and that the desire for ASIC‐resistance is simply people wanting to go back to “the good old days.” Without taking a side on whether ASIC‐resistance is desirable, we can dive into the technical challenges and some of the proposed approaches for achieving this goal.
What does ASIC‐resistance mean?Generally speaking, we want to disincentivize the use of custom‐built hardware for mining. Interpreting this strictly would mean designing a puzzle for which existing general‐purpose computers are already the cheapest and most efficient devices. But this would be impossible. After all, general purpose computers already have special‐purpose optimizations. Not all products have the same optimizations and they change with time. For example, in the past decade Intel and AMD have both added support for special instructions (often called “adding hardware support”) to compute the AES block cipher more efficiently. So some computers will always be less efficient than others at mining. Besides, it’s hard to imagine designing a mining puzzle that would rely on features like the speakers and screen that most individual’s personal computers contain. So special‐purpose machines stripped of these features would still probably be cheaper and more efficient.
So in reality our goal is a more modest one: coming up with a puzzle that reduces the gap between the most cost‐effective customized hardware and what most general‐purpose computers can do. ASICs will inevitably be somewhat more efficient, but if we could limit this to an order of magnitude or less it might still be economical for individual users to mine with the computers they already have.
Memory‐hard puzzles.The most widely used puzzles which are designed to be ASIC‐resistant are called memory‐hardpuzzles — puzzles that require a large amount of memory to compute, instead of, or in addition to, a lot of CPU time. A similar but different concept is memory‐boundpuzzles in which the time to access memory dominates the total computation time. A puzzle can be just memory‐hard without being memory‐bound, or memory‐bound without being memory‐hard, or both. It’s a subtle but important distinction arising from the fact that even if CPU speed is the bottleneck for computation time,the costof solving a large number of such puzzles in parallel might still be dominated by the cost of memory, or vice versa. Typically for a computational puzzle we want something that is memory‐hard andmemory‐bound, ensuring that a large amount of memory is required and this is the limiting factor.
Why might memory‐hard and memory‐bound puzzles help ASIC resistance? The logical operations required to compute modern hash functions are only a small part of what goes on in a CPU, meaning that for Bitcoin’s puzzle, ASICs get a lot of mileage by not implementing any of the unnecessary functionality. A related factor is that the variation in memory performance (and cost per unit of performance) is much lower than the variation in computing speeds across different types of processors. So if we could design a puzzle that was memory‐hard, requiring relatively simple computation but lots of memory to compute, this means that the cost of solving a puzzle would improve at the slower rate of memory cost improvements.
SHA‐256 is decidedly not memory‐hard, as we’ve seen, requiring only a tiny 256‐bit state which easily fits into CPU registers. But it isn’t too difficult to design a memory‐hard proof‐of‐work puzzle.
Scrypt.The most popular memory‐hard puzzle is called scrypt. This puzzle is already widely used in Litecoin, the second most popular cryptocurrency, and a variety of other Bitcoin alternatives.
Scrypt is a memory‐hard hash function, originally designed for hashing passwords in a way that is difficult to brute‐force, so the mining puzzle is the same Bitcoin’s partial hash‐preimage puzzle except with scrypt replacing SHA‐256.
The fact that scrypt existed prior to Bitcoin and has been used for password hashing gives some confidence in its security. Password hashing has a similar goal of ASIC‐resistance, because for security we want an attacker with customized hardware to not be able to compute password hashes much faster than the legitimate user or server, who presumably have only general‐purpose computers.
Scrypt basically works in two steps. The first step involves filling a large buffer of random access memory (RAM) with random data. The second step involves reading from (and updating) this memory in a pseudorandom order, requiring that the entire buffer is stored in RAM.
Figure 8.1: Scrypt pseudocode
1defscrypt(N,seed):
2 V = [ 0 ] * N / / i n i t i a l i z e m e m o r y b u f f e r o f l e n g t h N
//Fillupmemorybufferwithpseudorandomdata
3V[0]=seed 4fori=1toN:
5 V[i]=SHA‐256(V[i‐1])
//Accessmemorybufferinapseudorandomorder 6X=SHA‐256(V[N‐1])
7fori=1toN:
8 j=X%N //ChoosearandomindexbasedonX
9 X=SHA‐256(X^V[j])//UpdateXbasedonthisindex
10returnX
Figure 8.1 shows Scrypt pseudocode. It demonstrates the core principles but we’ve omitted a few details: in reality scrypt works on slightly larger blocks of data and the algorithm for filling up the buffer is slightly more complex.
To see why scrypt is memory‐hard, let’s imagine trying to compute the same value without using the
buffer V. This would certainly be possible — however, in line 9, we would need to recompute the
value V[j] on the fly, which would require computing j iterations of SHA‐256. Because the value of j
during each iteration of the loop will be pseudorandomly chosen between 0 and N‐1, this will require
about N/2 SHA‐256 computations. This means computing the entire function will now take N * N/2 = 2
N/2 SHA‐256 computations, instead of just 2N if a buffer is used! Thus, the use of memory converts 2 2
scrypt from an O(N) function to an O(N). It should be simple to choose N large enough that the O(N) is slow enough that using memory is faster.
Time‐memory tradeoffs.While it would be much slower to compute scrypt without the help of a large memory buffer, it is still possible to use less memory at the cost of slightly more computation. Suppose that we use a buffer of size N/2 (instead of size N). Now, we could store only the values V[j] if j is even, discarding the values for which j is odd. In the second loop, about half of the time an odd value of j will be chosen, but this is now fairly easy to compute on the fly — we simply compute SHA‐256(V[j‐1]) since V[j‐1] will be in our buffer. Since this happens about half the time, it adds N/2 extra SHA‐256 computations.
Thus, halving our memory requirement increases the number of SHA‐256 computations by only a
quarter (from 2N to 5N/2). In general, we could store only every kth row of the buffer V, using N/k
memory and computing (k+3)N/2 iterations of SHA‐256. In the limit, if we set k = N, we’re back up to 2
our earlier calculation where the running time becomes O(N). These numbers don’t apply precisely for scrypt itself, but the asymptotic estimates do.
There are alternate designs that mitigate the ability to trade off memory with time. For example, if the buffer is continually updated in the second loop, it makes the time‐memory tradeoff less effective as the updates will have to be stored.
Verification cost.Another limitation of scrypt is that it takes as much memory to verify as it does to compute. In order to make the memory hardness meaningful, N will need to be fairly large. This means that a single computation of scrypt is orders of magnitude more expensive than a single iteration of SHA‐256, which is all that is needed to check Bitcoin’s simpler mining puzzle.
This has some negative consequences, as every client in the network must repeat this computation in order to check that a claimed new block is valid. This could slow down propagation and acceptance of new blocks and increase the risk of forks. It also means every client (even lightweight SPV clients) must have enough memory to compute the function efficiently. As a result, the amount of memory N which can be used for scrypt in a cryptocurrency is somewhat limited by practical concerns.
Until recently, it wasn’t known if it was possible to design a mining puzzle that was memory‐hard to compute but fast (and memory‐easy) to verify. This property is not useful for password hashing, which had been the primary use case for memory‐hard functions before their use in cryptocurrencies.
In 2014, a new puzzle called Cuckoo Cycle was proposed by . Cuckoo Cycle is based on the difficulty of finding cycles in a graph generated from a cuckoo hash table, a data structure which itself was only proposed in 2001. There isn’t any known way to compute it without building up a large hash table, but it can be checked simply by checking that a (relatively small) cycle has been found.
This might make memory‐hard or memory‐bound proof of work much more practical for use in Bitcoin consensus. Unfortunately, there is no mathematical proof that this function can’t be computed efficiently without using memory. Often, new cryptographic algorithms appear secure, but the community is not convinced until they have been around for many years without an attack being found. For this reason, and due to its recent discovery, Cuckoo Cycle has not been used by any cryptocurrency as of 2015.
Scrypt in practice.Scrypt has been used in many cryptocurrencies, including several popular ones such as Litecoin. The results have been somewhat mixed. Scrypt ASICs are already available for the parameters chosen by Litecoin (and copied by many other altcoins). Surprisingly, the performance improvement of these ASICs compared to general purpose computers has been equal to or larger than that for SHA‐256! Thus, scrypt was decidedly not ASIC‐resistant in the end, as least as used by Litecoin. The developers of Litecoin initially claimed ASIC‐resistance was a key advantage over Bitcoin, but have since admitted this is no longer the case.
This may be a result of the relatively low value of N (the memory usage parameter) used by Litecoin, requiring only 128kB to compute (or less if a time‐memory tradeoff is used, which was commonly done on GPUs to get the entire buffer to fit into a faster cache). This has made it relatively easy to design lightweight mining ASICs without a complicated memory access bus needed to access gigabytes of RAM, as general purpose computers have. Litecoin developers didn’t choose a value that was much higher (which would make ASICs more difficult to design) because they considered the verification cost impractical.
Other approaches to ASIC‐resistance. Recall that our original goal was simply to make it hard to build ASICs with dramatic performance speedups. Memory‐hardness is only one approach to this goal, and there are others.
The other approaches, unfortunately, are not very scientific and have not been as rigorously designed or attacked as memory‐hard functions. The most well known is called X11, which is simply a combination of eleven different hash functions introduced by an altcoin called Darkcoin (later renamed DASH) and since used by several others. The goal of X11 is to make it considerably more complicated to design an efficient ASIC as all 11 functions must be implemented in hardware. But this is nothing more than an inconvenience for hardware designers. If an ASIC were built for X11, it would surely make CPU and GPU mining obsolete.
Sidebar: where did X11’s hash functions come from? From 2007 to 2012, the US National Institute of Standards ran a competition to choose a new hash function family to be the SHA‐3 standard. This produced a large number of hash functions which were submitted as candidates, complete with design documents and source code. While many of these candidates were shown not to be cryptographically secure during the competition, 24 survived without any known cryptographic attacks. X11 chose eleven of these, including Keccak, the ultimate competition winner.
Another approach which has been proposed, but not actually implemented, is to have a mining puzzle that’s a moving target. That is, the mining puzzle itself would change, just as the difficulty periodically changes in Bitcoin. Ideally, the puzzle would change in such a way that optimized mining hardware for the previous puzzle would no longer be useful for the new puzzle. It’s unclear exactly how we would actually change the puzzle once every so often in order to obtain the security requirements we need. If the decision were to be made by the developers of an altcoin, it might be an unacceptable source of centralization. For example, the developers might choose a new puzzle for which they have already developed hardware (or just an optimized FPGA implementation), giving them an early advantage.
Perhaps the sequence of puzzles could be generated automatically, but this seems difficult as well. One idea might be to take a large set of hash functions (say,
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com