Bitcoin Forum

Bitcoin could end centralization of hash power by adopting a new proof of work I have created that would require 10 TB of RAM if someone were able to create Scrypt ASIC capable of 1 Gigahash.  This memory-hard hash function scales memory to the point of requiring GB of memory to efficiently find solutions, but almost no memory to verify.

http://invictus-innovations.com/s/MomentumProofOfWork.pdf

THere is a 30 BTC bounty in the project-development thread related to this proof-of-work.   I am posting in general discussion because of the general usefulness of such a proof of work in the bitcoin space.

Where is the project thread?  It's an interesting concept...

https://bitcointalk.org/index.php?topic=313479.0

So we will have to wait for the new ASICs right?

In b4 "no ASICs can be made for that" bullshit  ::)

I am not well-versed enough to be able to determine the veracity of this from your whitepaper, but if accurate, this is a supremely excellent achievement.

Sure you could create an ASIC, but the transistor count would be dominated by memory.  A single Core i7 can utilize multiple GB of memory within a 5 min block interval.    If you replace the Core i7 with something 10x faster, you would need 40 GB of ram to maintain the same efficiency.  If you don't grow the ram, your performance will only marginally better and nowhere near 10x.  With these numbers the gains from creating a specialized ASIC are much less than in bitcoin land to the point of not being profitable.   RAM is power hungry so ASIC manufactures would be competing against home PCs with 0 capital cost and sometimes free electricity.  

Nonsense, a home pc has limits on RAM, require other hardware etcetc. An ASIC would have exactly only what is required, in this case tons of memory.

Not to downplay your achievement, but your idea here seems almost simple after the fact. What led you down this line of thinking? It is certainly much less complicated than scrypt as PoW, which is a bonus. But scrypt does do a fairly good job as PoW in lieu of SHA256. What need did you see that needed filling? Just a (potentially) truly CPU-dominated, botnet resistant PoW?

Yes you could build an ASIC but the ROI equation would be radically different.  Especially when competing against an army of PCs with no additional capital costs because they are dual use.

The momentum factor prevents manipulation of the BitShares blockchain based market because miners face a major cost to 'stop mining mid block in an attempt to manipulate the market'.

I wanted a fast validating proof of work.

I wanted the most decentralized proof of work I could come up with.   An ASIC for scrypt could be developed much easier than for this proof of work.

I wanted the bottleneck to be a commodity part with dual use.  RAM and memory controllers.

Yes it is very simple and elegant After the Fact...  but I have posted bounties trying to find better proof of work and spent weeks trying to find a way to make a fast to validate memory hard problem.    Then I had to find a way to make it 'scale' the difficulty smoothly.   Lots of little things to make something simple, elegant, and algorithmically secure.

Very interesting Bytemaster.  I look forward to taking a closer look at the nuts & bolts.  Well done!

I've read some of the bitshares stuff but haven't looked too deeply, but if I get this right there is no longer a nonce adjustment then with this PoW, right?


There are other, very beneficial applications to this proof, which lead into...


this. I believe you have made a very, very significant step in this direction.

Again, kudos. If this all checks out by people smarter than me, you have made a very significant contribution to the field of cryptocurrency.

The whitepaper states


Does it mean all 256 bits must be the same?

+1. Would like to hear this as well.

A rack of boxes with 1TB.  You can fairly easily do 1TB per system with a few different boards and the LRDIMM RAM.  Throw 10 of those boxes in a rack with Infiniband networking and you've got 10TB in a rack.  It's expensive, but not overwhelmingly so.  The RAM is the priciest part.  But you could do it in a standard 42U rack.

I don't think we can change the proof of work without hard forking bitcoin...
So i guess we're looking at a new altcoin.. again xD
Or rather an entire avalanche of momentum-pow alt-chains -.-'

Interesting idea, but for crypto-coins a proof-of-work scheme that isn't a random lottery - that is if not every attempt at creating a valid PoW has an equal chance of succeeding - can be really problematic because it means faster miners have an advantage. You give an example of a system where miners wouldn't want to add a transaction to the block they were mining because they'd have to start over. Such a system would mean that whom ever had the fastest implementation of the scheme would find the majority of the blocks, which really rewards people with highly-tuned custom hardware implementations - exactly what you are trying to avoid.

I'm also extremely skeptical of the idea that you've actually created a ASIC resistant scheme. You mention parallelism in your paper as a possible problem, but brush it off assuming that a hash table would be the optimal implementation, and lock contention and "atomic operations" would prevent a highly parallel implementation; I'm very, very skeptical that you're correct.

Fundamentally your design has two basic primatives: the generator function G(m, k)=H(m + k) producing candidate digests, and the content addressable memory (https://en.wikipedia.org/wiki/Content-addressable_memory) that stores potential digests and allows for matches to be searched for. The problem is that a solution is defined as successful if any a and b are found such that G(m, a) & (2^d)-1 == G(m, b) & (2^d)-1 for some difficulty d, a small positive integer. (a minor correction form your paper; you forgot to include the masking operation that makes finding a and b possible at all)

As you hint an ideal operation will run multiple generators in parallel - the problem is that an optimal implementation of the content addressable memory is very probably not a simple hash table. Here we have a situation with really weak demands on the CAM: it's ok if it doesn't always find a match, it's ok if there is no global synchronization, it's ok if sometimes it returns a false positive, and worst of all it doesn't even have to actually store all the data! Dedicated silicon implementations of CAMs are already really common for things like network routers, and they have vastly better performance than lookup tables built from commodity memory and CPU's. They also use a plethora of complex and application specific tricks to get the performance they need, even going as far as to make use of analog computation and probabilistic retrieval.

For instance off the top of my head a very fast design with very good utilization of silicon would be to use a custom ASIC consisting of a number of generator units feeding their results into a probabilistic CAM. A nice trick we can take advantage of is that for each candidate digest the generator function produces, we only actually need to store it's index to recreate it. That is if G(m, i)=d_i, we only need to store i, and we can even cheat further by only storing some of the bits of i, doing a quick brute force search after the fact to figure out which actual i was the match.

Hardware CAMs are usually implemented as a series of cells, with some number of search lines connected to each cell in parallel. Each cell matches the search line against it's own contents, asserting a series of read-out lines if the contents match. Writing a value to a cell is similar to regular memory. Matches are done very quickly, a single cycle, but at the cost of high power consumption as the memory grows larger. In our case we want a match to be done on the value of G(m, i), and we want the CAM cell to return the index i.

Lets suppose the difficulty is such that we're finding 64-bit birthday collisions or 2^32 items for a 50% chance of collision. This means our index values will need to be about 32-bits, as we have to search from 0 to 2^32 for a 50% chance of finding a collision. Naively we've have to store 64 bits per value for the digest, and 32 bits for the index, or 96bits * 2^32 = 48GiB. But we can do a lot better... First of all suppose only store 24 bits of digest in each cell: by the time we've got 2^32 items we'll get on average 2^8 false positives - pretty manageable with some parallelism to test them all. Next we can split our gigantic CAM array into multiple independent arrays, say 256 of them. Now for that 2^8 false positives, we only need to store 16 bits - pretty good! As for the indexes, we can cut down on them too: lets drop the lowest 8 bits, and just bruteforce the solution for the previous candidate digest at a cost of 2^7 average operations. Sure, that wasn't free, but we're now down to just 48 bits per cell, or 24GiB total.

Now I'm not giving you exact numbers, but that's not the point: I'm showing you how what's optimal turns out to be a crazy-looking hyper-optimized set of custom ASICs. Heck, a quick read of the literature on CAM design says that you'd probably go even further in this case, doing really crazy stuff like using multi-level kinda analog DRAM technology in the CAM cells, making convoluted trade-offs between actually storing indexes, or just leaving them implied by what bank the results are being stored in, etc.

I really suspect that rather than creating a ASIC hard design where commodity hardware has the same profitability as anything else, you've actually done the exact opposite and created a PoW function where the optimal implementation costs a tonne of money to implement, involves custom ASICs, and has performance miles ahead of anything else. Even worse is that with the non-lottery-random "momentum" aspect of what you're doing whomever implements this crazy custom hardware first will not only have the highest hashing rate, but they'll also solve the PoW problems the fastest, and hence get nearly all blocks.

Finally note that if G() was made to be made non-parallizable the idea might work, for instance by defining it as G(i)=H(m+k) ^ G(i-1), but then you wouldn't be able to do verification cheaply and might as well just use scrypt.

tl;dr: Cool idea, but the end result is probably the exact opposite of what you want.

Just saw retep's post. I think we reached similar conclusions for somewhat different reasons. Both probably valid.

Here's the link to my argument in the project thread: https://bitcointalk.org/index.php?topic=313479.msg3365654#msg3365654

Still yours is an interesting idea that I'll keep in mind.


Nathaniel

Birthday hash can be any number of bits so long as a collision can be found in a reasonable amount of time. Say 10 seconds for the first collision.

http://cdn.memegenerator.net/instances/400x/29062307.jpg

How did you found out bitcoin's hash power is centralized?

Economics of the situation is that specialized ASIC hardware can never be profitable to purchase as a consumer because the added cost of shipping, marketing, and packaging the ASIC vs a centralized mining farm means that hash power will tend to concentrate in large mining farms tightly connected to the latest manufacturing process.  Improvements in technology mean the lifespan of an ASIC is only about 1 year during which the entire cost of development must be recouped.   

In effect mining will centralize where the cost of power and overhead is minimal. 

Oh, so based on a hunch or laymen theory which has no actual basis or tested scenario in real life you concluded as a fact that Bitcoin is centralized NOW and we need to do something about it NOW before this theoretical problem arises? Gotcha... I'll pass.

The simple fact for which I think you're wrong, is because:
- Most GPU miners are made by ATI (holy shit that's so centralized)
- There are a limited list of models that are popular (30 or so models, less than there will be ASIC models for sure)
- They are deployed in a similar fashion, with similar software, by people who can afford buying several of them
- There are GPU farms created by people because they can afford the budget to do so, housed in the "generic individual domicile" mining farm
- NONE of this matters AT ALL because their choice is mining pool is more important than the hardware, year, miner software or favorite color.

What exactly has changed in terms of the distribution of cutting edge miners within the mining pools?

For example I bought several mining contracts on several hosted ASIC miners, made by several manufacturers and hosted in various places (including and excluding manufacturer recommended farm) pointed at various mining pools. What's wrong with this? What makes this centralized? What difference would there be if ALL ASIC miners are in ONE room or TWO rooms? Doesn't it matter more what mining pool they use?

Hosted ASIC mining contracts is centralized because they could be seized or destroyed by a single national government.   

I think the real goal is that the ideal miner should be general purpose and thus advance technology for all.  GPU mining is not 'centralized' because the GPU has many uses that justify producing consumer grade parts.   

Ask yourself this... how many people must the government control to steal 51% of the hashing power?   

Economies of scale apply to everything and thus tend to result in centralization.   If you have a proof of work that limits the ability to gain improvements by 'scale' that significantly exceed the benefits of individual nodes then you have a win.   My belief is that the two factors are capital cost and electricity costs.   For home PCs the capital costs are 0.  For many people the electric costs are paid by someone else and thus 0.

However, with Bitcoin miners the capital costs are always non-0 and the electric costs highly favor centralized ASICs.

As a result I contend that I have a better decentralization model.

There are several hosting actors, each competing for the same market on good profit margins (difficulty adjustments and price variations assure this). Why does it matter if one actor goes offline? There are many others, only a small to medium percentage of hash power will be temporarily impeding the Bitcoin network.

Consider that there are mining pools that have 30% of the hashpower. Such a pool going down will warp the block time by 30%, you are clearly not worried about this at all, and it's a more likely event than there being only 3 mining farms in the world.

You also sub-estimate how much some people pay for electricity, or even companies, and how cheap they can offer the mining contracts.

I think the real goal is to use the least possible resource waste to obtain the maximum network security. Advances in ASIC technology do just that. An attacker has to invest very little in electricity, very much in hardware and have little negative effect on the network. If we don't use the ASICs, the attacker can use less money for hardware and he will win. You want that?

That comment is just retarded. Centralization is not a nature of the hardware. If it is, then GPU mining is "centralized" because it's all ATI!

See how stupid this argument can be? Centralization would be when all miners go to btcguild and it can control 80% of the network and attack it 3 times a day.

1 or thousands. One developer can push a single change that causes a hard fork (as it happened). One pool operator can luckily get an attack performed. The rest of the network that doesn't act during that time won't be affected at all. It never happened, we don't know.

If you are whiny poor dreamer, whom can't afford an ASIC, you start dreaming up plans to make lots of money on your Pentium-II. Am I right?

This is again, another retarded argument. Let's play back time again:

2009 - Bitcoin appears
2013 - Bitcoin has high end efficient diversified implementations of the latest possible dedicated chip technology

Where have you ever seen such a short and powerful advancement in service technology? Seriously, in just 4 years, something went from obscure to cutting edge end-of-line technology. Look at Litecoin. The Litecoin ASICS are under development. After 4 years of it being launched, it will have several ASICs to boast.

How much time do you think you will buy? 8 years? 12 years?

Do you not understand that a specially built specifically designed computer will be better than the average desktop at mining your algorithm? You only add a hash counter demultiplier compared to bitcoin, and more time lag for emerging of the specialized hardware. Your idea is useless because there can always be ASICs that are better than generic hardware at specific tasks. Which is why they are called ASICs.

Embrace and respect technology, don't be an ignorant fool! Peace!

That is not useless because it means the network has to change hashing algorithms less frequently.  Changing of the algorithm is where I maintain decentralization ultimately, but having some delay is helpful.

I also want an algorithm that prevents manipulation of blockchain based markets by making it 'costly' to restart mining after accepting a set of transactions.

Bitcoin will not change algorithm until it becomes unsecure. There is no reason to do so. The ASIC for the new algorithm will be trivial.

What manipulation are you talking about?

I see someone else commented on the resource waste and efficiency. It doesn't matter if you have 1hash/s or 1Thash/s in each peer, the number of peers owned by an adversary is more important. Look at CPU only coins how they are being ripped apart by botnets.

Imagine a government or Interpol connected network deciding to install a modified miner on their machines, pool together with more hashpower than all your network and force invalid blocks on your blockchain. How do you stop that?

And this is not an algorithm for Bitcoin as bytemaster has stated.


Yes, Bitcoin got absolutely everything right. Stop any form of progress in any way because you're just wasting your time. ::)

I was thinking more like... stop inventing non-existing problems and focus on the ones that are important, not the ones that have already been solved.

Lets see here... you can never force invalid blocks on to a network, the worst case is a double spend attack and that requires an anonymous purchase.   Worst case is a DOS attack.

Please define how a botnet will tear it apart aside from winning all of the mining rewards.

If you have a bunch of bids and asks being broadcast on a blockchain and the miners get to pick the transactions that go into a block, then you do not want them to tweak their blocks frequently, but rather you want them to commit to the next block as soon as the previous block is found.   Hence having some momentum to the proof of work is helpful in preventing manipulation.

You might be confused about the state of art of certain classes of integrated circuits. I'll try to make this simple, as related to cryptography.

Speeding up the processing of a memory-hard algorithm requires two things: (1) faster memory (clock speed), and (2) more memory (parallelism and minimization of data set movement). Consumer RAM ("Memory" as it were) is nearly already AT the state of the art in terms of speed (DDR3 and soon DDR4). Adding MORE of it simply means adding more sticks of RAM. From a customized machine standpoint, this means adding more of the DDR SDRAM ICs (the constituent chips that make up a PC's RAM modules) and optimizing their data transports.

The argument that I recall the Scrypt paper making (and that I see the Momentum paper makes [2nd paragraph of introduction]) is that it becomes economically infeasible to design a system that outperforms a standard PC by such a margin that makes it worthwhile to develop said system. In other words, it costs too much to design a specialized system for a memory-hard algorithm when desktop PCs typically already perform really well with readily-available, relatively cheap hardware.

Q. Is someone going to develop an ASIC to handle the specific functions that the CPU in a desktop PC handles? Are they going to be able to do it faster and cheaper than Intel's latest tech?
A. Probably not, developing for the latest transistor size would be difficult and immensely costly.

Q. Is someone going to develop a memory ASIC that performs better than consumer RAM?
A. Probably not, consumer RAM is already near the state of the art.

Q. If someone DID actually build the above two ASICs and also built an efficient platform around them on such a scale that the (alt-)coin mining market would actually support, would it be economically feasible (that is, would you get at least 100% ROI)?
A. Most certainly not. The licensing alone would kill the hopes for feasibility.

I hope this makes sense. If I have misspoken or misinformed anywhere in the above, please do not hesitate to correct me.

The argument that I don't see made often enough is when economic feasibility isn't the goal, what happens? For instance, if a government wanted to build a system to take over and crumble a cryptocurrency network and [fiat] money was no object -- then yes, they could probably develop such a system. But any economist who knows about the engineering involved (quite a rare subset I would imagine!) would just tell this government to buy as much consumer PC hardware as they could rather than develop new tech. "Why re-invent the wheel?"

p.s. BombaUcigasa, you're coming off very trollish. You ask good questions, but try to lighten up a bit on your accusatory tone and people might take you more seriously. Thanks.

So this is like Nascar restrictor plates? Does it incentivize low end mining?

You can't fit "tons of memory" on a single chip, not even an ASIC, since you are fundamentally constrained by transistor size.

So even with an ASIC, more hashpower can only be achieved with more hardware, and not with architecture alone.  For the 10TB of memory mentioned by the OP you would need to manufacture thousands of chips, ASIC or no ASIC.

Sure, an ASIC would be more efficient than a home PC, but in terms of hash per dollar invested it would perhaps only achieve a factor of 2, not a factor of 10,000 like it's the case with the SHA256 algorithm.

I agree with you that a desktop PC, or let's say a high end desktop PC and not cheapo all-in-one embedded models, are pretty efficient in terms of memory and computing power for the price point, when compared to an ASIC.

However, your point about an ASIC being unfeasible I do not agree with:
- You don't need a 7.1 sound chip, PCI connectors, SATA controllers, fancy BIOS, USB ports, half the northbridge architecture, any kind of storage medium, and many other things in your miner
- You are not restricted to a specific AT form, specification or rule, you can make your case as thermal needs require it to be, you can make smaller and cheaper motherboards
- You don't need super fancy EPUs and VRMs that cope with variable work load modes and power efficiency modes
- You don't need 80% of the CPU's functions to perform a single hash algorithm, things like virtualization, multimedia processing, graphics controller (http://images.bit-tech.net/content_images/2012/04/intel-core-i7-3770k-review/ivb-5w.jpg, http://wccftech.com/images/reviews/hardware/Processor/Intel-Core-i7-975-Extreme-Edition-Processor-Review/Core-Design-Areas.jpg)
- Even if you use a PCI board as implementation, you don't need everything from a GPU, you can discard 40% of the chip/s surface (http://www.ixbt.com/video3/images/titan/diag_smx.png)
- The speed to storage trade-off can be adjusted in any machine, such that it uses less RAM and faster processor, or slower processor and more RAM for the same hashrate

So if you build an ASIC for Scrypt, it will be cheaper to make per unit, use less power and produce more hashes than a generic built PC. Sure, it will have just this purpose, but it will do it better in the long term. If the benefits of owning such a miner for 2 years produce sufficient return to cover the investment then it will be built. KnC miners take like a month to recoup now, don't they?

Most miners are not stupid, they take logical calculated evidence-based decisions. They buy new hardware when they observe opportunity, and stop the hardware or sell it when it is working at a loss. Just like Bitcoin ASICs are removing GPUs from the network, a memory hard algorithm will take out generic desktops from the network using that algorithm in lieu of headless dedicated optimized low-energy ASIC miners.

Q. Is someone going to develop an ASIC to handle the specific functions that the CPU in a desktop PC handles? Are they going to be able to do it faster and cheaper than Intel's latest tech?
A. Yes. KnC, ASICminer and others managed to make dedicated chips that can hash bitcoin faster and cheaper than ATI's chips.

Q. Is someone going to develop a memory ASIC that performs better than consumer RAM?
A. Yes. GPUs already use chips and architectures that offer more than double the speed of consumer montherboard RAM.

Q. If someone DID actually build the above two ASICs and also built an efficient platform around them on such a scale that the (alt-)coin mining market would actually support, would it be economically feasible (that is, would you get at least 100% ROI)?
A. Yes, it could be feasible if it would get 100% ROI.

The question should be: Can a cryptographic blockchain hash algorithm that can run exclusively only on common desktops with maximum efficiency be created?
The answer is: No.

The question is then: Why are we discussing this new proof of work?

I'm not trolling, I'm as sincere as possible even if I look like an asshole. Deceiving people and making fun of them is not my style.

This is the main point where I disagree, and I think proponents of memory-hard hashing algorithms would agree with me. An ASIC with the level of tech (smallest, proprietary transistor techs) required to process a memory-hard algorithm as fast as possible would be prohibitively expensive. You're either licensing the transistor tech from IBM, Toshiba, TSMC, or whomever, or developing your own processes. Expensive one-time costs and expensive platform development costs. If you're considering JUST materials, then yes of course a custom Scrypt ASIC would be cheaper. But since when was a gold coin worth only its weight in gold?

Also:

In my post the discussion was in the realm of processing a memory-hard algorithm. In the first Q, you talk about bitcoin. I am not referring to SHA256 as it is not memory-hard.

In the 2nd Q, I did indeed forget about the RAM on video cards which is faster. However, this is still bleeding-edge AND commodity, with vendors pumping out millions of chips for dirt cheap.

Your answer for the 3rd question is circular.

The libertarian in me wants to say that I disagree on your first posed question. I believe the intent of Bitcoin was to put the power of securing the transaction network in the hands of the people MAKING the actual transactions, rather than a government or bank.
But the technologist in me has a need for (hashing) speed.

The answer to your final question is: because it is novel and innovative.

So what if it is expensive? The argument is it can be built, and it will be better than a PC. The price only matters once we discuss numbers, such as blockchain rewards, fees, and the possible profit made from these. Was it profitable to invest 5 million dollars to make 1000 ASICS worth 5.000$, say 2 years ago when they could capture 15.000$ a day all together? No. Is it profitable now to invest 5 million dollars to make 1000 ASICS worth 5000$ that can capture 120.000$ a day alone? Looks like it is.

Are you trying to keep an algorithm on consumer PCs forever or delaying it from reaching ASIC until a variable time period where it becomes feasible to make such an ASIC?

Option A: Keeping the algorithm on consumer PCs forever:
- impossible, because even with some slight modifications, a special "PC" can be made that is a beast at hashing it, costs less to use and maybe less to be obtained
- impossible, because at a point if it becomes profitable, the more "budget enabled" peers can buy more expensive new powerful PC parts and drive profitability down for the rest and driving them out

Option B: Delaying ASIC for some time:
- since you can't make the algorithm work better on crappier hardware, and because people with more money than sense will profit while the rest will lose, I assume you just want to delay the ASICs for your algorithm.
- as Bitcoin advances in popularity and growth, it will reach more technical people and companies, the speed at which new or adjusted algorithms will reach the ASIC state will increase drastically, to less than 4 years

THe BitSHares network is designed to change hashing algorithms to maintain mining fairness on commodity hardware.   Any delay that reduces the frequency of switching hashing algorithms is beneficial.

MOMCOIN