Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Proposal to consider an ASIC-friendly proof of work #3387

Open
iamsmooth opened this issue Mar 12, 2018 · 151 comments
Open

Proposal to consider an ASIC-friendly proof of work #3387

iamsmooth opened this issue Mar 12, 2018 · 151 comments

Comments

@iamsmooth
Copy link
Contributor

@iamsmooth iamsmooth commented Mar 12, 2018

Currently Monero is pending a hard fork to modify the PoW in order to invalidate existing rumored and reported ASIC designs, and in addition to continue making such changes repeatedly to attempt to prevent ASIC development and deployment on the network. For various reasons, there are longer-term concerns with this strategy, particularly going forward, including:

  1. Continued and repeated ad-hoc modifications to the PoW algorithm may accidentally (or even maliciously) introduce exploits.
  2. ASIC developers may build in more flexibility to their designs to be able to accommodate small algorithm tweaks (indeed this may already be the case, we don't know).
  3. Potential for favoritism/corruption if plans for tweaks are leaked or influenced far enough ahead of time that some favored ASIC developers may have enough lead time to produce ASICs, while others do not.
  4. A belief that ASICs may be desirable as a means to facilitate industrial scale mining and growing the network beyond what might be called a hobby mining phase.
  5. Potential for increased monopolization if the strategy is only partially effective (i.e. keeps all but one ASIC developer from succeeding)
  6. Dependence of the network on continued frequent hard forking independent of the need for functional upgrades. This carries with it a greater degree of centralization necessary to design, implement and coordinate these forks, without any real plan to transition beyond it.

For these reasons I would propose that we consider (which does not necessarily mean implement) abandoning the ASIC-hostile approach and instead consider adopting an ASIC-friendly approach in a future hard fork.

By ASIC-friendly, I mean something that not only can reasonably be implemented in an ASIC, but which minimizes barriers to creating ASICs, minimizes their costs, facilitates the development of a wide range of compatible hardware at attractive price points, and minimizes opportunities for clever proprietary advantages. By doing so we may maximize the likelihood of a competitive ASIC market developing and minimize the degree of (temporarily or sustained) monopolization. This could possibly be achieved by using a simple, well-known, and well understood algorithm such as SHA3.

There are numerous other potential advantages and disadvantages of this approach relative to Monero's current PoW algorithm and strategy, which can be discussed in comments.

Postscript: My personal view has always been largely ASIC-hostile (primarily based on my analysis the history of the Bitcoin ASIC market when Monero launched in 2014, but reinforced by the continued evolution of the Bitcoin and other coin ASIC markets over the past four years), however I am open to the possibility that unintended consequences of attempting to maintain this approach may cause more harm than overall benefits, in which case it should be dropped.

@williams-r
Copy link

@williams-r williams-r commented Mar 12, 2018

Points for ASIC-friendliness:

ASIC manufacturing will see more competition, halong mining is already competing with bitmain, and their defensive patent group is promising.

There are no ASIC botnets.

ASICs are worthless the day after they carry out a 51% attack.

Merged mining with bitcoin would means that monero does not have to compete in the same way for the same electricity and capital investment in mining equipment.

Points for ASIC-resistance:

CPUs and GPUs are more difficult to ban than ASICs

the silicon foundries which produce ASICs are quite centralized

Merged mining with bitcoin right now would increase centralization pressure on bitcoin mining from the increased cost of node operation.

@SRCoughlin
Copy link

@SRCoughlin SRCoughlin commented Mar 12, 2018

I propose a process that can satisfy many of these concerns: using a sound game theoretic strategy for ASIC resistance. In my proposal, this would continue the current 6-month release strategy, but would also include the following:

  1. The addition of a large number (N) of known non-ASIC-implemented POW algorithms, equal probability of implementation assigned to each (1/N).

  2. Antagonistic testing of each algorithm to confirm its success and lack of exploitable weakness, and replacement of failed tested algorithms.

  3. Rational cost analysis of implementation of each combination of above algorithms in ASIC/MPW fabrication. (Perhaps also including POC in FPGA to get realistic data.)

  4. Use of a pure RNG to determine the particular algorithm implemented in the release.

This process would allow for openness in discussion of future direction and would allow for greater trust by the community in the stability of upcoming releases. (i.e. No more "last-minute" POW changes.) And its use of the random strategy will negate any serious investment in ASIC development as means of dominance.

This process would not address botnets, partially effective ASIC exploits (discovered post-release), or the need for "industrial scale mining".

Please let me know if you think this might be viable.

@jwinterm
Copy link
Contributor

@jwinterm jwinterm commented Mar 13, 2018

If you would like something that "...not only can reasonably be implemented in an ASIC, but which minimizes barriers to creating ASICs, minimizes their costs, facilitates the development of a wide range of compatible hardware at attractive price points, and minimizes opportunities for clever proprietary advantages." then why do you immediately disregard SHA256 and propose SHA3?

@iamsmooth
Copy link
Contributor Author

@iamsmooth iamsmooth commented Mar 13, 2018

@jwinterm I'm not an expert on this but I've seen various credible claims that SHA256 is not a particularly ASIC-friendly algorithm by design, due to both its internal complexity and susceptibility to various clever optimizations. This has allegedly contributed to the rather less than competitive Bitcoin ASIC market, since barriers to designing competitive SHA256 mining ASICs are higher than they otherwise need to be, and there are too many opportunities to gain an sustainable advantage with proprietary tricks. But who knows, this may be a bogus claim.

SHA3 may or may not be better, but in any case that was only intended as an example which is somewhat more modern by design than SHA256, avoiding some of its pitfalls (for example, length extension attacks, though that in particular may not matter much to PoW).

There may well be better choices, but the particular choice of algorithm that seems somewhat of a diversion from the core question of whether ASIC-friendliness is useful goal and then defining the selection criteria.

@iamsmooth
Copy link
Contributor Author

@iamsmooth iamsmooth commented Mar 13, 2018

@SRCoughlin While your idea is good in theory, I'm not sure about its feasibility in practice. It is hard enough (and may fail) to produce even one well-vetted and carefully-implemented alternative/modification without screwing it up (see #1 in the original issue), much less several.

@jwinterm
Copy link
Contributor

@jwinterm jwinterm commented Mar 13, 2018

There may well be better choices, but that seems somewhat of a diversion from the core question.

This is true, and I think ultimately it's futile to try and constantly fork away from ASICs. The original idea of cryptonight afaik was that it was somewhat equivalent between CPUs, GPUs, and theoretical ASICs, and I think trying to meet that original vision is probably more realistic than trying to constantly fork to prevent ASICs from mining on the network.

@iamsmooth
Copy link
Contributor Author

@iamsmooth iamsmooth commented Mar 13, 2018

@jwinterm

The original idea of cryptonight afaik was that it was somewhat equivalent between CPUs, GPUs, and theoretical ASICs, and I think trying to meet that original vision is probably more realistic than trying to constantly fork to prevent ASICs from mining on the network.

That's somewhat getting at the core of the intended topic of this issue: Is that still considered a useful goal, and if so, is it feasible in practice?

If it is useful and feasible, how should it be done?

@otheATgh
Copy link

@otheATgh otheATgh commented Mar 13, 2018

the silicon foundries which produce ASICs are quite centralized

That's non sense and a non issue, those foundries are the EXACT SAME that fab out the chips for NVIDIA and AMD. NVIDIA and AMD don't seem to be able to scale their productions due to the same issues BTC ASIC factories have atm.

This discussion should have been had in detail way before merging in this untested and unreviewed PoW change.

Using SHA3 or our bastard child of keccak we currently use for the PoW has the advantage that we do not need to implement another unrpoven crypto library besides what we already have.
On the other hand SKEIN seems to be a more sane and even easier to implement in HW as it was meant to be implemented in HW.
Another alternative could be to use a slightly modified double sha256 like Bitcoin as the ASIC chipdesign there is already highly optimized.

I dont think merge mining with BTC makes any sense as i do not think that the same HW should be used for both coins, it gives BTC maximilaists easy access to attack our network.

The whole securing multiple billion dollar networks using a bunch of hobbyiest miners that can easily overtaken renting some AWS instance is a pipedream to me.

So far it seems mostly mined by botnets and shitty JS webminers that steal other peoples resources and can dump them at whatever price because they were essentially free anyway.

@cAP5L0CK
Copy link

@cAP5L0CK cAP5L0CK commented Mar 13, 2018

First of all I strongly favor this conversation.

One of the notable outcomes of ASIC resistance besides botnets have been browser miners. One side effect of dropping the ASIC resistant stance would be to greatly diminish if not eliminate the use web miners both being used nefariously but also in the open like Salon.com etc.

@SRCoughlin
Copy link

@SRCoughlin SRCoughlin commented Mar 13, 2018

The community has opposed the use of ASIC miners due to the nature of centralization that this entails. If ASIC supporters should wish their implementation, it stands to reason that this case be addressed. (Counterexamples of botnets, Salon, etc. are likely not going to convince the community.)

@Hueristic
Copy link

@Hueristic Hueristic commented Mar 13, 2018

No matter what, we should fork away from these current ASIC's, rewarding them is not a good idea.

@metamirror
Copy link

@metamirror metamirror commented Mar 13, 2018

Perhaps the Monero Project should fund the development of its own open source ASIC design. It could also manufacture ASICs and commit to selling all of its chips retail.

@SRCoughlin
Copy link

@SRCoughlin SRCoughlin commented Mar 13, 2018

@metamirror Interesting. Consider: the community creates a number of new POW algorithms and, in tandem with development and testing, openly releases the VLSI designs for FPGA/ASIC (even MPW?) to go along with each (every?) algorithm. After the RNG, miners can either coordinate bulk purchases through the community, or use the VLSI to fab an independent run of chips and create a custom ASIC. The beauty is that in 6 months the next network release (hard fork) would choose another algorithm by RNG, negating the processing advantage of the existing ASICs and requiring new VLSI designs.

This would allow for full ASIC implementation to anyone's content, yet this would also be limited (by the random strategy) to be economically viable for only a small number of miners. Hence, it would be predictable and controllable, and, should any of the above criticism prove valid, could provide reason to delay the given POW algorithm change schedule to avoid issues.

This would be, in essence, a completely open source anti-ASIC strategy and unlike anything attempted before.

@iamsmooth
Copy link
Contributor Author

@iamsmooth iamsmooth commented Mar 13, 2018

@otheATgh Numerically I think renting a bunch of AWS instances is really not a viable attack. In terms of naive cost estimate, perhaps it is feasible, but while AWS may have a million or more high end CPUs or GPUs to use for this (or an even equivalent even-larger number of small ones), actually renting that many at one time is not trivial at all, and may be totally infeasible. It means you are competing with their other customers, some of whom are not particularly cost sensitive in the short term (the don't want their enterprise computing shut down so you can attack a network for an hour).

Setting aside Amazon KYC-ish requirements on large capacity demand (they want to see justification and also that you will not disrupt their service), let's look at some numbers. A high end AWS node generates something like $10000/year revenue if rented long term and $4-5k/year if rented on the spot market. AWS total revenue is something like $20 billion/year not all of which comes from instance fees (some from storage, bandwidth, value-add services, etc.). If it were all high-end node instance fees which of course it isn't, the entire company would only be 2 million nodes, and you would need need to pull something like half of it to pull off an attack which you won't be able to do.

This seems implausible. Even combining other providers it seems far from easy.

You are significantly underestimating the strength of the current 'hobbyist miner' network (though it isn't really that, there are definitely some large scale miners) and the difficulty of renting very large amounts of resources from cloud providers (particularly for short time which they will find disruptive and not allow) in practice.

Nevertheless, given potential price drops, emissions reduction over time, this may become an issue. Also, Ethereum GPU farms have far more than enough capacity, if they decided to be become Ethereum-maximalists doing the attacking instead of the Bitcoin maximalists you mentioned (or just underutilized after Ethereum PoS).

@iamsmooth
Copy link
Contributor Author

@iamsmooth iamsmooth commented Mar 13, 2018

@metamirror

Perhaps the Monero Project should fund the development of its own open source ASIC design. It could also manufacture ASICs and commit to selling all of its chips retail

I don't think the Monero project wants to be a point of centralization on the design and manufacture even if they are being sold. The issue isn't only who is building the miners, it is that someone is doing so and has a lot of control over the market (who gets miners, how many, when, and at what price).

Possibly an open source design could make sense, but I don't know enough about the realities of the ASIC design and manufacturing marketplace to know whether this is useful. More generally (not referring to miners here), I see a lot of people talking about 'open source hardware' and not that many actually doing it, particularly at the ASIC level.

@SRCoughlin
Copy link

@SRCoughlin SRCoughlin commented Mar 13, 2018

@iamsmooth

More generally (not referring to miners here), I see a lot of people talking about 'open source hardware' and not that many actually doing it, particularly at the ASIC level.

While software experience is highly portable and abstract, hardware requires EE skills, which are much more time-consuming and particular. Very few EEs donate their time to open projects.

Possibly an open source design could make sense, but I don't know enough about the realities of the ASIC design and manufacturing marketplace to know whether this is useful.

I do, but donating time for EE work would only make sense as a means to an end. In other words, there has to be very specific reason why EE work is being done. The abstract ideal of decentralization may not be enough to justify this.

As an example of the EE work costs, I give you the (very high) fees associated with the optimal GPGPU code for Cryptonight POW algorithms.

In fact, I'm wondering now if including a (much lower) fee in the POW algorithm and VLSI code would allow for FFS bounties for their own development. This could be interesting, but might also create a conflict-of-interest with the EEs working on these very designs.

@iamsmooth iamsmooth closed this Mar 13, 2018
@iamsmooth iamsmooth reopened this Mar 13, 2018
@iamsmooth
Copy link
Contributor Author

@iamsmooth iamsmooth commented Mar 13, 2018

(sorry closed by accident)

@SRCoughlin "Very few EEs donate their time to open projects"

Donating time and open source are two different things. A very significant portion of Monero development has been paid for.

The abstract ideal of decentralization may not be enough to justify this.

The entire purpose of a decentralized cryptocurrency project (indeed the entire purpose of cryptocurrencies at all) is decentralization. It isn't just an abstract ideal, it is at the very core of the mission statement.

My view is that ASICs only make sense if there is an expectation of a commoditized market developing in a reasonable period of time. That hasn't happened with Bitcoin at all, but maybe it still will.

Unless we have some alternative approach which does get there (and at a much smaller scale than Bitcoin might get there), then I would consider the answer to this issue to be in the negative.

@hyc
Copy link
Collaborator

@hyc hyc commented Mar 13, 2018

@jwinterm

This is true, and I think ultimately it's futile to try and constantly fork away from ASICs. The original idea of cryptonight afaik was that it was somewhat equivalent between CPUs, GPUs, and theoretical ASICs, and I think trying to meet that original vision is probably more realistic than trying to constantly fork to prevent ASICs from mining on the network.

This makes the most sense to me. While the crypto community always admonishes "don't roll your own crypto" I think it's important to highlight that goals of a PoW hash function don't align with the goals of a typical cryptographic hash function. Most hash functions are designed for efficiency of implementation and execution. (Password hashes may be a notable exception to this goal.) We want something that is equally difficult for CPUs, GPUs, and ASICs. AFAICS this means we want something that is branch-heavy, where multiple branches are all equi-probable. That would defeat CPUs' branch predictors, and GPUs are already poor at branchy code. We also want something that is comprised entirely of serial data dependencies, to defeat any CPU instruction-level parallelism. And we want something that cannot be simply reduced to a compact set of lookup tables. I don't think it'd be hard to come up with such a design.

@iamsmooth
Copy link
Contributor Author

@iamsmooth iamsmooth commented Mar 13, 2018

@hyc The cryptographic soundness (at least some aspects of it) is extremely important otherwise the algorithm can be analyzed and shortcuts found which avoid the need to execute some or all of the (branch-heavy, etc.) code you initially assume is necessary to search the space of possible solutions.

That said, something that is both cryptographically sound and better tuned to the needs of PoW (in particular, ignoring efficiency of execution, good point there) is probably possible, but I'm not sure "not difficult". In a sense all previous attempts at ASIC-resistant, GPU-resistant, memory-hard, etc. PoW have been that, and most if not all have failed in some aspect or another. Cryptonight has held up better than most, in terms of maintaining a balance.

Also, I'd guess that intentionally defeating things like instruction-level parallelism in CPUs puts them at a big disadvantage to ASICs and possibly GPUs since those will employe parallelism in hardware (unless there is some method proposed to limit or prevent it, such as a very large non-optimizable scratchpad). To maintain parity, CPUs probably need to take advantage of their accessible parallelism too.

@iamsmooth
Copy link
Contributor Author

@iamsmooth iamsmooth commented Mar 13, 2018

Linking because it is worth reading. I don't necessarily endorse every aspect of it, but I endorse (strongly) at least being familiar with the document :)

https://download.wpsoftware.net/bitcoin/asic-faq.pdf

@ghost
Copy link

@ghost ghost commented Mar 13, 2018

Has there ever been a hybrid PoW scheme that combines an ASIC-unfriendly function with an ASIC-friendly one?

I am thinking of a scheme whereby the first stage of the computation uses an ASIC resistant algorithm, with its output being passed as input to the second stage, which uses an ASIC friendly algorithm. Miners could earn block rewards for performing either (or both) stages.

Consider a bad scenario: a botnet controls a disproportionate amount of the hashrate and/or ASIC farmers do the same. The botnet could never compete with the ASICs on the second stage, but the ASICs would have difficulty competing with botnet on the first stage. Some separation of hashing power would exist, similar to a bicameral legislature.

All Google showed me was hybrid PoW/PoS schemes, so I haven't been able to find anything similar to the one I just described. If someone knows of one, please let me know.

@TheTrueForce
Copy link

@TheTrueForce TheTrueForce commented Mar 14, 2018

Please pardon me lobbing up out of nowhere and leaving this here.
@jsfierro That seems like a good idea, but:
I can see dedicated miners being made to fit that as well. I have no idea if this is actually the case, but it might be feasible to build a custom computer combining a high-end CPU and/or GPU, combined with an ASIC module, and run by custom software. That might defeat the purpose of the two-part algorithm, as the general-purpose(GP) hardware would do its part of the hashing, and then shove that into the ASICs, and pick up the result. Those could be beastly.
I can also see addon boards being made for regular PCs to accelerate mining, much like a GPU accelerates rendering. This could lead to the same situation as the hybrid miner, though.

Please keep in mind that I'm speaking from ignorance(or at best only small knowledge), so I could be barking up the wrong tree entirely. Or possibly just barking.

What if the two-part algo has some kind of requirement that the same hardware can't do both parts?
That each unit of work needs to be performed by two seperate and different pieces of hardware? That would likely elimenate solo mining, and it would also almost require the existence of ASICs. Probably neither are good things. And probably the ASICs would be substantially faster than the GP hardware. That might be an obstacle. On top of that, enforcing the requirement could be a nightmare... I actually have no idea at all how that could be done, if it even can...

@hyc
Copy link
Collaborator

@hyc hyc commented Mar 14, 2018

Having worked on compilers, optimizers, auto-vectorizers, and the lot, I'd say it's harder to write optimization-friendly code. But it's a heavily studied field by now; we can look at any guide to optimizing code for parallelism, and do the opposite. And what we use can of course start with a cryptographic hash (like Keccak/SHA3) on the front, to decorrelate the intermediate data from the input. After that it's just an issue of making sure nothing we do cancels itself out.

@Gingeropolous
Copy link
Collaborator

@Gingeropolous Gingeropolous commented Mar 14, 2018

For me, the problem with an ASIC friendly PoW is that you can never beat the economies of scale that ASICs provide. So even when ASICs become commodified, and every phone has an ASIC because reasons, and lightbulbs and toasters because you have to hash for service, we may have achieved an egalitarian access to the hardware, but we may not have achieved egalitarian access to the nonce space.

When I first encountered Bitcoin, it was post-ASIC. I read about it, saw the mines, and concluded that Bitcoin had already become, and would continue becoming, just another space where the Rich get Richer and the everyperson is forced out. And because ASICs breed centralization, it seemed to me that Bitcoin had failed in its primary purpose - being decentralized.

At first, I didn't get into Monero because of "the privacy". I got into it because the egalitarian PoW aligned with how I understand decentralization.

Finally, I think ASICs give too much power to the miners. Yes, I've read the logic that "well the ASIC can only be used to mine that coin so therefore the miners will always support that coin and their intentions are good" but we shouldn't care what the miners support. The miners get rewarded for providing a service to a decentralized network, where the value is completely dependent on the extent of decentralization.

The network is not rewarded by the service of the miners.

@SRCoughlin
Copy link

@SRCoughlin SRCoughlin commented Mar 14, 2018

@iamsmooth

Linking because it is worth reading. I don't necessarily endorse every aspect of it, but I endorse (strongly) at least being familiar with the document :)

I've completed reviewing this document. It is either incorrect or inapplicable in every claim. While it may have some important information about efficiency when it comes to SHA256 algorithms such as Bitcoin, there is nothing to be learned from it when it comes to Monero and its POW algorithms.

My critiques are as follows:

all ASIC resistance does is increase the startup capital required and therefore increase centralization of manufacturing

Incorrect. ASIC resistance costs labor primarily (designing VLSI, etc.), as ad-hoc production runs of chip fabrication are common now. Capital outlay for the run is not a concern.

it is impossible to create an algorithm which runs at the same speed on general-purpose and dedicated hardware

Inapplicable. It is possible to create algorithms which surpass the economic feasibility of ASIC design within the timeframe of change in POW. If it's not profitable, there is no incentive.

Schemes such as “the developers will just change the proof-of-work algorithm if ASIC’s
appear” do not even make sense — in a decentralized currency the developers have no such
power

Incorrect. This is happening right now.

Memory hardness has the effect of increasing ASIC board footprint, weakening the heat-
dissipation decentralization provided by the thermodynamic limit.

Inapplicable. As above.

Also, memory hard proofs-of-work often require lots of memory on the part of the verifiers, which is bad for decentralization

Partially applicable, but only as for certain implementations. Say, Arduino or other small devices.

memory-hardness worsens the centralizing effects of ASIC’s while weakening the decentralizing effects

Inapplicable. As above.

An algorithm which is highly susceptible to TMTO has poorly defined memory hardness

Incorrect. Testing and optimization can reveal these issues. See Cuckoo Cycle as an example.

@iamsmooth
Copy link
Contributor Author

@iamsmooth iamsmooth commented Mar 14, 2018

@SRCoughlin Cost of labor to design is a capital outlay. Someone is paying for the labor long before revenue. That investment is a form of capital.

Yes the document takes the position that effective ASIC resistance is impossible. That may or may not be correct in practice, but the idea that ineffective ASIC-resistance may make matters worse seems valid to me.

@Gingeropolous "but we may not have achieved egalitarian access to the nonce space"

I don't see how this is ever possible, outside of some sort of KYC for mining (and not even sure how that would be done in a decentralized manner). Even if you can mine on a laptop, nothing prevents someone else from using two laptops and therefore having access to twice the nonce space, right?

@jtgrassie
Copy link
Contributor

@jtgrassie jtgrassie commented Mar 14, 2018

IMHO, the issue is that ASICs currently are very centralized. If there were ASIC products on the market with fair competition then there would be no reason to be ASIC resistant. Currently that's just not the case. The problem is, whilst there is this path of ASIC resistance, what incentive is there for anyone to develop ASICs for Monero mining; zero. It's a double edged sword (or rather chicken and the egg scenario). We either let the current players develop ASICs for Monero and accept it will be centralized to some degree for a period, or we resist, which deters possible ASIC development and competition in the market. I guess I feel a good end-state is multiple ASIC producers, as then ASICs become commoditized, and there's nothing bad about that (hardware the masses can use to mine at commodity prices with better margin, r.e. electricity cost & hardware cost / return).

Let's be honest, mining is already centralized to some degree. GPUs (AMD and Nvidea) and CPUs (really just Intel by the numbers). The price of these, which were once commodity hardware, have been growing due to demand.

Ultimately I feel mining has to be profitable for the masses. If ASICs make it more profitable for the everyman then great. If there is no profit in mining at all then what's the incentive; ideology alone?

Independent miners is more decentralization, which is the ultimate goal.

In summary, I think we are not yet at a place where there is sufficient ASIC competition, and thus decentralization. But to some degree, by being ASIC resistant, we contribute to the problem.

I'd welcome a world where there were more ASIC manufacturers that current GPU/CPU manufacturers! This may be the future!

@iamsmooth
Copy link
Contributor Author

@iamsmooth iamsmooth commented Mar 14, 2018

I'm not sure a competitive/commoditized market for ASICs will ever make sense.

CPUs and to a lesser (but still some) extent GPUs have the markets they do not because of the manufacturing (which is at least as centralized), but because they are general purpose products which lends itself to having many disperse and competing distribution channels. In most even mid-sized cities you can find multiple stores where you can go and and buy CPU and GPUs both as individual components and as part of a system. Plus of course on-line from both many resellers and manufacturers directly. There are thriving gray market channels (probably actual black market too, thinking about hijacked shipments, etc.), a robust and deep used market, etc.

None of this really exists for mining ASICs (just as it doesn't exist for other forms of ASICs) and may never exist, because it is far more specialized (er, "application specific"). It is natural to have a narrower and more structured distribution system which in turn naturally lends itself to a higher degree of centralized control and vertical integration where efficiency trumps reach. Though I guess it is possible to envision enough diversity among types of miners that there might be value in broader distribution (if so, then one likely needs to accept 'hobbyist miners' as an important part of the system).

Still this doesn't change the fact that unsuccessful ASIC-resistance (which some argue is inevitable) may still be worse than ASIC-friendliness.

@tevador
Copy link
Contributor

@tevador tevador commented Oct 16, 2018

@timolson Thanks for the review. I appreciate your comments.

The fact that any heuristics are known should be a concern.

Do you know any NP-hard problems for which there are no heuristics at all? My understanding is that NPP has perhaps the poorest heuristics of all NP-hard problems.
Anyways, most (if not all) cryptographic hash functions are not actually mathematically proven to be secure. At best, they have just resisted years of scrutiny and peer review. Even RSA is not theoretically secure because an efficient factorization algorithm could be found in the future.

In my opinion it's the same with the NPP problem. The best heuristic algorithm has been around since 1982, which is longer than the oldest cryptographic hash functions.

Also, sorting, although well-studied in hardware, is neither simple nor widely commoditized. Optimal sorting networks are only known up to N=17, and above that it's all proprietary heuristic algorithms.

I wasn't aware of the difficulty of hardware sorting. Anyways, I don't think that it would be a big issue because full sorting of the list is only required at the beginning of the algorithm and could be done using any good heuristics. Then, there are N-1 steps where the list is partially sorted and only one iteration of insertion sort is required, which (AFAIK) can be done in one clock cycle using N comparators. Proprietary improvements in the initial sort should not make a significant difference in efficiency.

We need a well-studied problem where a simple optimal implementation is known for finding any solution at all, even if many exist.

It's true, but I'm not sure if such problem that is usable as PoW even exists.

@timolson
Copy link

@timolson timolson commented Oct 17, 2018

I'm not well-versed in the literature and don't know if a suitable problem exists. This is really just a wish list. But I would challenge the idea that an NP problem is required. Even if the solution and validator are both in class P, it's ok as long as the solution polynomial is of higher order than the verification polynomial. Again I don't really know, but it seems like plenty of P-class problems should have known-optimal solutions and plenty of those optimal solutions should be "simple." Most search problems will have fast validation relative to solution time, and although standard hashing against a network target would fit into this category, I don't consider SHA to be simple, and it doesn't have a proven optimal implementation. But even something like finding an FNV hash under the network target... FNV is nothing but a multiply and XOR and is basically "optimal by inspection." It's incredibly tiny and easy to implement. Even if it's your first program in C, you're probably compiling down to optimal object code for a CPU miner. ASIC's would be easy, too. XOR is primal, and multipliers are well-studied and everywhere. There would be no advantage to extract from clever algorithm tricks.

Anyway, maybe such a formal problem and proof doesn't exist and that's why cryptography currently relies on factoring and discrete logs and things like that. But PoW is different from other security objectives, so maybe it's worth rethinking.

@SChernykh
Copy link
Contributor

@SChernykh SChernykh commented Oct 17, 2018

@tevador Using NP-hard problem as PoW is a bad idea. There is no proven lower complexity bound for NP-hard problems, and a breakthrough can happen any time. It's better to search for problems that have known lower bounds like O(N^2) or O(N^3) and use them.

@tevador
Copy link
Contributor

@tevador tevador commented Oct 17, 2018

@timolson Interesting idea with FNV. Is the hash non-reversible, though?

@timolson
Copy link

@timolson timolson commented Oct 17, 2018

@tevador I’m not a cryptographer but would doubt that FNV is secure enough. Almost certainly not. I was just brainstorming, and it’s probably not a good idea. But take it as inspiration?

There are some lightweight ARX hashes that may be suitable... no multipliers only add, rotate and xor. But can we do better than a hash function that has no proof behind it, only “lack of attacks?”

Maybe someone knows of a search problem with a proven solver that’s simple to implement?

@tevador
Copy link
Contributor

@tevador tevador commented Oct 17, 2018

But can we do better than a hash function that has no proof behind it, only “lack of attacks?”

The main problem is that the algorithm must have either an unpredictably random output (to use the standard difficulty algorithm comparing to a threshold) or adjustable complexity / solve time. Otherwise it's not really usable as a PoW by itself even if it fulfills all the conditions you mentioned earlier (simplicity, proven optimal solution, fast verification).

So for the time being we are stuck using cryptographic hashes for the final PoW value and the only way to make the miner simpler than the hash algorithm is to combine it with a simpler problem that is much harder to solve, so the hash calculation time is negligible. However, to keep the verification time low, you need an asymmetric algorithm. This was the rationale behind NPPoW and for example Cuckoo cycle also fits this description.

@stoffu
Copy link
Contributor

@stoffu stoffu commented Oct 18, 2018

@tevador
Just a minor question, I didn't understand your above comment:

So for the time being we are stuck using cryptographic hashes for the final PoW value and the only way to make the miner simpler than the hash algorithm is to combine it with a simpler problem that is much harder to solve, so the hash calculation time is negligible.

which seems to correspond to the following description in NPPoW's README:

The encoded solution is then appended to the block header and the whole header is hashed once again, this time using the SHA3-256 hash function to determine the final PoW.

I don't see the point of this "final PoW" because the work is not targeted at producing small hash values. Doesn't it suffice to include only the nonce and its corresponding solution in the block?

@tevador
Copy link
Contributor

@tevador tevador commented Oct 18, 2018

Doesn't it suffice to include only the nonce and its corresponding solution in the block?

The PoW hash is not included in the block. It's calculated to check if the block meets the required difficulty. The NPP solution is not a hash and cannot be used as one. In order to keep the difficulty targeting mechanism, a random 256-bit value must be produced at the end.

Another option would be to set the difficulty by adjusting B (the number of bits), but this has low granularity (difficulty could be adjusted only in approximately powers of two), so it could skew the block emission frequency. Also pooled mining would be very difficult if not impossible (how do you define a partial solution?).

@timolson
Copy link

@timolson timolson commented Oct 18, 2018

If we’re worried about mining centralization, why aren’t pools demonized as much as ASIC manufacturers? Almost all of them are Stratum based, not getblocktemplate, and Stratum pools can forge malicious blocks without the pool users knowing or approving.

IMHO few people really care about decentralization or they would force pools to use getblocktemplate instead of Stratum. Let’s be honest: most people just want to make “easy” money at home and they tout “decentralization” as a moral excuse. Getblocktemplate puts more work on the client which means less money, and clearly home miners have chosen money over “decentralization.”

Anyone crying about “decentralization” while pointing their home rig to a Stratum pool should STFU and just admit it’s greed that drives them, not some abstract democratization principle.

So really, why should we be worried about whether a PoW is useable in a pool? Shouldn't we design one that's NOT useable by pools?

@juanpc2018
Copy link

@juanpc2018 juanpc2018 commented Oct 19, 2018

the original protocol was getwork, but was replaced...
the replacement was a developer war,
it was getblocktemplate "GBT" vs stratum developers, stratum "won" because it was pushed/supported by largest Bitcoin pool...

...many years later:
doing BitcoinDiamond mining, using a modified ccminer from vvpool, that has both GBT and stratum,
also i use a proxy, that can accept getwork, gbt, and stratum, and convert to stratum to communicate with the pool in stratum or gbt.
when using the ccminer as gbt vs. stratum there are very interesting differences, specially with verbose active on the miner, very interesting,..

BUT...
after lots of mining, my conclusion was:
is better for small miners to get into a pool that has more than 51% of the total miners.
is better for small miners, if the pool has more than 95% of the total miners in 1 pool.

what avoids a 51% attack is Not the pool, is the Node wallets,
what decides the future of the coin, is the Node wallets,

if 99% of the miners are in 1 pool, and all miners have light wallets = just 1 Node Wallet,
if that 1% left has 10k people, each with a Real Node wallet, a Fork or a 51% attack is impossible, if the 1% does Not agree/download the New version.
all miners in 1 pool is bad for other pools, and coin centralization... more on that,

Mining Decentralization is Bad for small miners,
What people that understand coins mean by Decentralization, has a completely different meaning.

where do i start?
the laws of the world...
1-old example:
the alexandria library,
had all the knowledge of the world, at that time, and got burned, oil lamp, burning arrow, does Not matter, all knowledge was lost...
why? because it was Centralized,
"Don`t put all eggs in one basket."

to copy books was slow, by hand, a lifetime work,
when technology advanced enough, printers appear, and to copy books was easy, faster...
information Decentralized...

when technology has advanced enough, Decentralization happens Naturally,
Now there is a library everywhere... with similar knowledge.
when technology is Not advanced enough, Centralization occurs Naturally.

for example the Earth, technology is Not advanced enough, Humans are Centralized in 1 planet.
if a Meteorite is big enough and hits the earth, kills all humans.
see Salvation TV series on NetFlix, https://www.imdb.com/title/tt6170874/

Decentralization allows survival.

Economy, is Not advanced enough, is Centralized by Banks, by government,
but Technology has advanced enough, and is getting slowly but Naturally Decentralized,
if happens another economic crisis like 2008, or an EMP attack, world will choose a Decentralized economy/technology, that can survive,
is just Natural Selection,
each time a New economic crisis Big enough happens again, world economy will become Decentralized, because technology has advanced enough,.

but there are other Centralized vs. Decentralized problems, "layers" inside the Decentralized Economy,
like Miners, Pools, Wallets, Developers, etc...

a proper Decentralized algorithm will give equal opportunity to CPU, GPU & ASIC, or FPGA and other pools,
"in the future everyone will have 15-minutes of fame" -Andy Warhol,
to avoid pool/coin centralization, the algorithm must rotate all miners to a different pool every 15-minutes or 15-days, depends on the pools/nodes available.
Each Node wallet is a Pool automatically, Pool code is included in each Node Wallet, Motivating the use of Node Wallets, "avoiding a 51% attack" and also avoiding coin centralization by only 1-pool with 99% of the miners.

Bitcoin is ASIC centralized,
Ethereum was GPU centralized,
GPU Only coins made GPU prices to increase = BAD for Small Miners.
if there is No small miners, Coins become Centralized, and Market Dumping happens, more on that.
the problem with ASIC or GPU Centralized miners/coins, are several,
for example:
if Bitcoin Price gets High enough, & ALSO very popular, or Traditional Economy becomes too weak, ASIC developers will see that Not selling miners becomes more profitable...

if price is high, but popularity is Not enough, they could develop a secret faster Miner, and use it, Not sell it.
they can Not sell replacement parts, eliminating the competition..
taking over the world.
Centralizing the Network,
if a Small Meteorite or an EMP hits the Only ASIC FARM/Factory in the world, the SHA256 coin will disappear = World Economy Chaos.

The goal of Decentralized Economy is to allow Survival of the Economy,

anything that goes against Decentralization is wrong...
but when all miners are Centralized, "looks wrong" but gains are Decentralized more easy,
i wish i could explain more easy, why something that looks centralized is actually Decentralized...

anyway...
World economic crisis will happen again, is a matter of time, don`t know when,
the problems that caused the 2008, were Not solved, just the symptoms were solved.
when happens again, e-coins will rise when there is a New economic crisis again, but Not all e-coins...
coins that do Not have instant Notification wont survive the 2nd or 3rd wave, small daily transactions, becomes impossible without instant Notification, for example.

e-coins price is "down" now, because 3 reasons, traditional economy is strong now, and most e-coins were centralized by few miners & pools, most had 10k coins, those people are dumping the coins in the traditional economy, lowering the price more...

Bitcoin was Not mass adopted by small daily economy, because 21Million coins are Not enough, making too much decimals, and transaction fees too high, also waiting lines too long but thats another story... solving 1 problem with another, few coins, high fees, long waiting lines with assumed valid blocks, pruning & segwit.
coins that have less than 100million coins, wont survive the 3rd or 4th wave,
because most humans do Not understand 0.0015 btc + fee = Burger + Fries. LOL. Jajajajaja
economy / technology must be easy to understand, to be mass adopted.

each wave ripple, ecoins will become less & less centralized...

https://mining.bitcoin.cz/media/download/mining_proxy.exe
https://github.com/slush0/stratum-mining-proxy
https://en.bitcoin.it/wiki/Getblocktemplate
https://en.bitcoin.it/wiki/Stratum_mining_protocol
https://en.bitcoin.it/wiki/Getwork
https://en.bitcoin.it/wiki/Original_Bitcoin_client/API_calls_list
https://en.bitcoin.it/wiki/Getwork_support

@stoffu
Copy link
Contributor

@stoffu stoffu commented Oct 19, 2018

@tevador

The NPP solution is not a hash and cannot be used as one. In order to keep the difficulty targeting mechanism, a random 256-bit value must be produced at the end.

Oh, I thought the idea was to adjust the difficulty of NPP according to the network's compute power and replace the current hash-based PoW with it. In other words, is your idea to change the current scheme:

  • pick nonce -> compute hash -> accept if below threshold

to something like this?

  • pick nonce -> solve NPP -> compute hash -> accept if below threshold

So, the difficulty adjustment will apply to these two places (NPP and hashing)? How should it be done? I'm new to this idea. Or perhaps, the difficulty of NPP is fixed?

Another option would be to set the difficulty by adjusting B

How about fixing B and adjusting N? AIUI, decreasing N seems to make the problem harder progressively.

Also pooled mining would be very difficult if not impossible (how do you define a partial solution?).

I see this as well, which is also true with Cuckoo Cycle (a relevant post on Monero StackExchange).

@stoffu
Copy link
Contributor

@stoffu stoffu commented Oct 19, 2018

@timolson

I think you misunderstand how pool mining works.

IMHO few people really care about decentralization or they would force pools to use getblocktemplate instead of Stratum.

Pool miners calling getblocktemplate doesn't make sense at all; this PRC is called by the pool operator against the operator's node with the operator's wallet address as the (only one) argument. Each time a new block is found, the operator receives the block reward in full, and pays out to the contributing miners later. If a pool miner were to call getblocktemplate with his own wallet address as the argument, he is effectively solo mining. Pool mining works by having many miners work on the same block template.

Let’s be honest: most people just want to make “easy” money at home and they tout “decentralization” as a moral excuse.

Anyone crying about “decentralization” while pointing their home rig to a Stratum pool should STFU and just admit it’s greed that drives them, not some abstract democratization principle.

The basic assumption in any cryptocurrencies is that all participants are greedy and will cheat/attack the system if they can. The whole point of our effort is to eliminate the possibility of cheating and make the adherence to the same strategy optimal for everybody w.r.t. financial gain. We seek for decentralization because it's fundamentally valuable, not because it's moral.

IMO, pool mining by itself is not a problem as long as miners are reasonably spread out, which is quite a different kind of question.

@timolson
Copy link

@timolson timolson commented Oct 19, 2018

@stoffu
Oh really I don't understand? getblocktemplate was designed to allow clients to choose their own transactions so that they wouldn't have to trust the pool operator's choice. Don't say I misunderstand.
Miners using getblocktemplate is the only way GBT makes sense. It's the whole purpose for GBT. Otherwise just use Stratum and let the pool operator have control of the TX selection.
In GBT, the pool still creates the coinbase but allows clients to choose the TX's so the clients can choose which transactions they think are valid. The pool still gets the coinbase.
Here's a refresher since you clearly don't understand
https://en.bitcoin.it/wiki/Getblocktemplate

@timolson
Copy link

@timolson timolson commented Oct 19, 2018

So it's probably different in Monero. I'll humbly admit very little knowledge of what a Monero block looks like. But GBT vs Stratum for the majority of coins, you are way off base.

@timolson
Copy link

@timolson timolson commented Oct 19, 2018

Maybe this is our misunderstanding: you're talking about the pool operator calling GBT on the daemon, building the block, then using Stratum to broadcast to miners. This is a bastardization of what GBT is about. I'm talking about the original purpose of GBT where it was meant to be a pool protocol for mining clients so that pool operators wouldn't be able to effect a 51% attack containing malicious transactions.

@stoffu
Copy link
Contributor

@stoffu stoffu commented Oct 19, 2018

@timolson

Oh yes, I was assuming you were talking about the Monero daemon RPC of the exact same name. I was unaware of this GBT protocol in Bitcoin which seems to have never been implemented in Monero AFAIK. Indeed, this type of pool can be helpful for decentralization.

I'll humbly admit very little knowledge of what a Monero block looks like.

I'm also largely ignorant about how exactly Bitcoin blocks look like, but apart from the vast differences in the individual transactions' format, the basic structure of blocks should be mostly the same between Bitcoin and Monero in my understanding (merkle root, prev block id, difficulty, timestamp, nonce, etc).

@LordMajestros
Copy link

@LordMajestros LordMajestros commented Oct 19, 2018

If we’re worried about mining centralization, why aren’t pools demonized as much as ASIC manufacturers? Almost all of them are Stratum based, not getblocktemplate, and Stratum pools can forge malicious blocks without the pool users knowing or approving.

IMHO few people really care about decentralization or they would force pools to use getblocktemplate instead of Stratum. Let’s be honest: most people just want to make “easy” money at home and they tout “decentralization” as a moral excuse. Getblocktemplate puts more work on the client which means less money, and clearly home miners have chosen money over “decentralization.”

Anyone crying about “decentralization” while pointing their home rig to a Stratum pool should STFU and just admit it’s greed that drives them, not some abstract democratization principle.

So really, why should we be worried about whether a PoW is useable in a pool? Shouldn't we design one that's NOT useable by pools?

NERVA, Blur and Turtle coin are 3 projects that are experimenting with mining without pools.
The first two are indirect monero clones through masari. The last one is a crypto note clone.
I'm paying attention to them because I'm very interested in seeing how this plays out.
I think pools help to prevent a different kind of centralisation, centralisation of the supply. I think if people solo mine for long stretches of time without rewards they are likely to quit mining altogether. I'm watching to see this proven or disproven.
I'd also like to point out that due to ring signatures in crypto note coins it might be difficult or perhaps impossible for pool operators to censor transactions based on anything other than fees. I might be wrong.

@FromMeanas
Copy link

@FromMeanas FromMeanas commented Oct 19, 2018

If we’re worried about mining centralization, why aren’t pools demonized as much as ASIC manufacturers? Almost all of them are Stratum based, not getblocktemplate, and Stratum pools can forge malicious blocks without the pool users knowing or approving.

IMHO few people really care about decentralization or they would force pools to use getblocktemplate instead of Stratum. Let’s be honest: most people just want to make “easy” money at home and they tout “decentralization” as a moral excuse. Getblocktemplate puts more work on the client which means less money, and clearly home miners have chosen money over “decentralization.”

Anyone crying about “decentralization” while pointing their home rig to a Stratum pool should STFU and just admit it’s greed that drives them, not some abstract democratization principle.

So really, why should we be worried about whether a PoW is useable in a pool? Shouldn't we design one that's NOT useable by pools?

What is your point exactly Tim?
Everyone is greedy so let the _itmains and asic desgners like you dominate the hashrate, the coin supply, in fact dominate everything?

@LordMajestros
Copy link

@LordMajestros LordMajestros commented Oct 19, 2018

@timolson I'd love to hear your thoughts on this https://medium.com/@turtlecoin/introducing-cryptonight-soft-shell-2c2d4c497efd
I think ASICs can be built for this.

@tevador
Copy link
Contributor

@tevador tevador commented Oct 19, 2018

@stoffu

pick nonce -> solve NPP -> compute hash -> accept if below threshold

Yes, that was the original idea. The difficulty of NPP would stay fixed with B = 42 and N = 128 and just the hash threshold would change.

Cuckoo cycle actually uses the same mechanism (with a SHA-256 hash of the cycle solution).

How about fixing B and adjusting N? AIUI, decreasing N seems to make the problem harder progressively.

Adjusting N would also work, but the dependence of NPP difficulty on N is more complex (for example N also affects the value of the critical ratio and size of the search space).

For a fixed value of N, the difficulty would be simply proportional to 2B. The only problem is that with a high enough B, 64-bit integers are no longer enough and CPU performance would drop sharply.

Third option would be to adjust both N and B to set the required difficulty.

@timolson

So really, why should we be worried about whether a PoW is useable in a pool? Shouldn't we design one that's NOT useable by pools?

Someone could argue that pools help decentralization (up to some point), because most small miners wouldn't consider solo mining viable. Without small/hobby miners, it would be just big GPU farms who would mine.

The fact that existing Monero pools are stratum pools is a different point.

@timolson
Copy link

@timolson timolson commented Oct 19, 2018

@FromMeanas
I was challenging the idea we should prioritize a pool friendly PoW. Compared to other coins, Monero has a pretty good distribution of hashrate across pools right now, yet if only 2 of the bigger ones colluded, they have more than 50% easy.
There seems such hatred toward ASIC makers, saying Bitmain is a monopoly (they aren’t) but if people really cared about decentralization and not just their wallets, they would complain about pool power. They don’t. But they should.

There are ways to prevent pools from being malicious even if they have >50% hashrate (getblocktemplate) so as long as we’re talking about PoW and ASIC’s, I thought a quip about pools and pool support was germane.

@LordMajestros
Interesting about the non-pool coins. I’ll bet home miners don’t do it. They want immediate rewards not decentralization.

This doesn’t mean I’m against distributing mining power and coins. Maybe pools are a necessary evil just like ASICs.

@BreakingSiam
Copy link

@BreakingSiam BreakingSiam commented Oct 19, 2018

@timolson
You know some of what I do, so you should understand when I say that I agree with most of your position, but I think you are over generalizing here. Yes, part of it, possibly a very large part, is due to greed, but if that was all it was, then people would simply have bought the miners from Bitmain and continued to make money. After all, they bought the nVidia cards. What's the difference? I have studied this problem in detail.

Bitmain really did bring this problem on themselves, and it isn't fair to disparage those who are reacting to it by calling them greedy. Sadly, I am going to have to stereotype here, but there is no way around it. I've lived in Asia for more than 20 years, and Chinese companies just don't see the world in the same way as we do in the West. In their eyes, things like insider trading, giving mining equipment preferentially to their friends, etc. is not necessarily wrong. That is not to attack the Chinese. Westerners have customs that are equally bizarre. But I will point out that Bitmain has never been fair in the Western sense of the word when selling devices, and people are now naturally suspicious of every mining equipment manufacturer due to this.

The same is not true of pools. When a new pool starts mining, it is quite clear. When a much more efficient ASIC unit comes on line however, it can be disguised such that it can only be seen in hindsight as the difficulty level slowly creeps up. And those who have early access to the miners are very adept at keeping it under the radar for a while.

Until your new vision of a Utopia comes true, where there is a large group of competitive mining manufacturers that are all competing fairly during the day and singing Kumbaya together at night, you need to be a bit more open minded about the feelings of the community. This isn't solely greed. The emotion of fear plays a very large role here as well.

@iamsmooth
Copy link
Contributor Author

@iamsmooth iamsmooth commented Oct 19, 2018

@timolson People have definitely expressed concerns about pool centralization but it is hard to solve. GBT was not a solution because its usage isn't enforced and neither an individual pool nor an individual pool miner has any incentive to use it. Their individual optimization is to stick with stratum. For a pool decentralization solution to work it needs to be enforced (or at least properly incentivized) at the consensus level and also avoid or address various work-arounds and cheats/semi-cheats that people have come up with or will come up with. It's not easy, but a good solution that avoided too many negative unintended consequences would indeed be valuable.

@timolson
Copy link

@timolson timolson commented Oct 20, 2018

@LordMajestros
Soft Shell not convincing
https://medium.com/@timolsoncrypto/turtlecoin-cryptonight-soft-shell-is-nonsense-8e5c3ca5f572
I apologize to the Soft Shell authors for my previous tone. Article is cleaned up.

@dEBRUYNE-1
Copy link
Contributor

@dEBRUYNE-1 dEBRUYNE-1 commented Mar 14, 2019

A relevant discussion currently occurring here:

monero-project/meta#316

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet