Altcoin POW innovations headed in the wrong direction. Let a chip designer pick.

[eldentyrell]

Moderation promise: I will not moderate except to delete posts that try to derail the thread by advertising an altcoin

Update, 15-Apr: it has begun... sooner than I thought.

I think the POW innovations have it all wrong. You can't prevent ASICs; there is no ASIC-proof POW. But that isn't the point.

The point should be to ensure that some near-ideal mining device:

  (a) already exists in mass production, with another use,
  (b) isn't susceptible to botnet-mining, and
  (c) has a cost-of-ownership dominated by silicon rather than electricity.

I fear very much what happens once the difficulty plateaus and the only people who can still mine are those with $0.02/kwh electricity and most users are facing electricity costs five times higher than revenues. Nobody "mines for fun" to any meaningful degree in that situation. The hydroelectric warehouses buy up all the idled ASICs from high-electric-cost owners at bargain prices and we wind up with five or six giganto-mines. Then the next time the BTC/USD exchange rate takes a sudden plunge -- for any reason -- those five operators can't cover their electric costs and the rational choice for them and their shareholders is to mount a 51% attack.  The scariest part is that since a 51% attack isn't illegal shareholders can actually sue mine managers for not doing this (at least in the US where managers of for-profit non-B corporations have a duty to act in the corporation's financial interest).

We're relying on altruism more than we think, folks.

If the POW is engineered so that the ideal mining device already exists people won't have to take a gamble with sketchy outfits like BFL. If it has other uses they won't be tempted to sell when operation becomes unprofitable, or they'll sell on ebay to people applying it to a non-mining use.

Unfortunately the people cooking up idiotic monstrosities like scrypt-jane and X11 have absolutely no clue what they're doing. Hey look I'll gang together ten ASIC-friendly algorithms and that just has to be ten times better, guys!

(edit: stuff above here is the main point of this post/thread; what follows is just an initial stab, probably wrong, at solving it)

One possibility is a scrypt-like algorithm but with:

• An utterly massive N-value, like 16GB or more, beyond the amount of memory in most botnet-slaves and impossible to hide the performance impact in the rest.
• Anti-TMTO modifications so you can't trade X times less memory for ~X times more computation.
• The simplest possible blockMix() operation between memory-data-out and memory-address-in -- much less than salsa20/8.  Probably siphash is ideal, big thanks to tromp's paper on cuckoo cycle for this idea!

Then the ideal mining device looks like a very cheap (~$50) backplane full of commodity DRAM DIMMs. The DRAM industry has the largest economies of scale of anything in semiconductor computing, bar none.  Way beyond CPUs, GPUs, FPGAs; no ASIC startup will ever come close to their economies of scale.  The key is making sure that putting extra intelligence on the DRAM chips (yes, you can do this) doesn't win you any advantage.  That ensures that the mining industry has nothing to gain by diverging from the DRAM industry, and a lot to lose from economies of scale.

Anti-TMTO can be implemented in a very basic way by using serially-chained addressing for not just the read-phase but the write-phase too.  There are probably better ways to do it.  If the algorithm's dependencies are sufficiently serially threaded through the memory then very little of the silicon is active (switching) at any point in time, so you'll draw very little electricity.  I'd have to run the numbers here but the goal is to ensure that the total cost of electricity over the expected dielectric lifetime (at 24x7x365 operation) is significantly less than the cost of the memory chips.  I think that's doable.

You'd still need to buy a cheapo backplane to mine, but those things are easy for any PCB shop to design, slap on an old FPGA (or even CPU) to use as a memory controller, you're good to go.  Product development costs would be in the $5,000-$10,000 range instead of the $5mm-$10mm range.  Heck you could solder them up yourself.  Great maker project.

[brokedummy]

Sorry to make you make a new thread. You said there is no asic-proof pow, so I wanted to point out the one coin that gives diminishing rewards the more hash you try to throw at it, in case you had not heard about it. Sorry, I'll let you get back to your 'conversation'.

[eldentyrell]

Sorry to make you make a new thread. You said there is no asic-proof pow, so I wanted to point out the one coin that gives diminishing rewards the more hash you try to throw at it, in case you had not heard about it.

This thread is about choice of POW algorithm.

I'm aware of what you're talking about -- it doesn't change the POW algorithm, it changes the incentive structure.

Bitcoin's incentive structure works very well, and the numerous altcoins broken by Artforz back in the GPU mining days show that the incentive structure is a delicate thing.  Moreover simply fiddling with the incentive structure doesn't change the fact that (if the coin became sufficiently popular and valuable) mining would still be undertaken exclusively by those with the cheapest electricity.

[eldentyrell]

One problem with the above is that you'd need 16GB of storage to check block validity, even for SPV clients on things like cell phones.  So that's one problem that would need to be fixed.

Maybe if the r-value (number of rounds) were really low and only a small fraction of the memory cells wound up being read from the block header could include some kind of map showing which memory cells got hit during the hashing operation.  Then with the map a low-memory device could check a hash.

Even better, SPV clients could ask full-chain clients to calculate the map for them so it wouldn't have to be stored in the chain.  The point is that giving an SPV client a bogus map won't fool them so there's no trust there.

[brokedummy]

Sorry to make you make a new thread. You said there is no asic-proof pow, so I wanted to point out the one coin that gives diminishing rewards the more hash you try to throw at it, in case you had not heard about it.

This thread is about choice of POW algorithm.

I'm aware of what you're talking about -- it doesn't change the POW algorithm, it changes the incentive structure.

Bitcoin's incentive structure works very well, and the numerous altcoins broken by Artforz back in the GPU mining days show that the incentive structure is a delicate thing.  Moreover simply fiddling with the incentive structure doesn't change the fact that (if the coin became sufficiently popular and valuable) mining would still be undertaken exclusively by those with the cheapest electricity.

OK, I think I understand the topic a little better now. Most people on the forum are worried about scrypt asics coming in and lowering the price and profitability of their coins, which I had an answer for(I think). You are worried about asics coming in and centralizing mining like what is happening with BTC and single entities controlling large portions of the nethash i.e. ghash.io. It does make sense to move your mining operation to the most efficient locations with the cheapest electricity and we can't all move there. I don't really have an answer for this.

I haven't been around as long to know Artforz but I am assuming he 51% attacked a bunch of coins that nobody wanted to mine anymore because they were too top heavy?

[eldentyrell]

I haven't been around as long to know Artforz but I am assuming he 51% attacked a bunch of coins that nobody wanted to mine anymore because they were too top heavy?

No, these coins were all on the uptrend (at least in terms of difficulty).  They just fiddled with parameters they didn't fully understand.  People monkeyed around with the block reward adjustment rate, and then he used his huge GPU farm to timewarp their chain.

  https://bitcointalk.org/index.php?topic=43692.msg521772#msg521772

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

[raze182]

Unfortunately the people cooking up idiotic monstrosities like scrypt-jane and X11 have absolutely no clue what they're doing. Hey look I'll gang together ten ASIC-friendly algorithms and that just has to be ten times better, guys!

I can't speak for scrypt-jane, but X11 wasn't designed to be ASIC-proof. It was designed to delay the implementation of ASICs for coins (specifically Darkcoin). The dev said himself that he expects X11 ASICs eventually and they may even be beneficial once coin distribution has matured.

[markm]

What makes electricity "cheap" ?

In theory if massive users of electricity all started setting up shop where elecrtricity is cheap that should drive up demand there, shouldn't it?

Is there a limit on how much "cheap" electricty the current "cheap electricity" locations can generate before they start being more expensive or simply get bid up in price by demand greater than they can cater to?

-MarkM-

[eldentyrell]

I can't speak for scrypt-jane, but X11 wasn't designed to be ASIC-proof. It was designed to delay the implementation of ASICs for coins (specifically Darkcoin).

That sounds like splitting hairs.  Or like litecoin's belated claims that it was never meant to be GPU-resistant.

[eldentyrell]

In theory if massive users of electricity all started setting up shop where elecrtricity is cheap that should drive up demand there, shouldn't it?

There's really only once place in the USA with electricity that cheap -- Eastern Washington.  They've got lots of hydroelectric and due to historical-legal factors the generating plants are owned by nonprofit local utilities districts whose goal is just to break even.  Outside the US there aren't many places where the power is that cheap without government subsidies.

"Setting up shop" involves a very large fixed cost that must be amortized over a large operation.  Moving to Eastern Washington State isn't something a hobby miner can do.  It isn't even something most small-time professional miners can do.  You have to either buy real estate or sign a commercial lease.  It imposes economies of scale exogenous to the economics of the cryptocurrency, which creates an artificial centralizing force.

So, indeed, the market will react.  It will react by centralizing bitcoin.  Altcoins that seek to improve on bitcoin should consider this incentive structure and ask whether they can make a better choice that avoids it.

Is there a limit on how much "cheap" electricty the current "cheap electricity" locations can generate before they start being more expensive or simply get bid up in price by demand greater than they can cater to?

It isn't so much the generation (there's at least a terawatt of the cheap stuff) but rather the distribution lines and the local utility's service delivery points.  It takes a long time for the latter to be installed, there are regulations and permits, etc.  Most of this infrastructure can't react nearly as fast as the mining market changes.  You might even get people speculating on it and buying up land with existing service delivery, or land that blocks the right-of-way for installing new delivery (eminent domain is a slow process).

And again, even without this you've already filtered out anybody who isn't willing to buy land or sign a lease in Eastern Washington.  That's a huge blow to decentralization right off the bat.

Lastly, even if we wind up with fifty megamines instead of five, they'll still all be located within a 75 mile radius.  That is REALLY scary from a collusion standpoint.

[zerodrama]

What makes electricity "cheap" ?

In theory if massive users of electricity all started setting up shop where elecrtricity is cheap that should drive up demand there, shouldn't it?

Is there a limit on how much "cheap" electricty the current "cheap electricity" locations can generate before they start being more expensive or simply get bid up in price by demand greater than they can cater to?

-MarkM-

In the real world, that involves getting a new address, renewing your driver's license, making sure your health insurance transfers, getting a different job, finding a new apartment, selling your car, buying another one, loading up your valuables, discarding old stuff.

Gee, I wonder why no one does that so often.

Most people put up with what they have until they have to move.

Which means whoever just moved in will eventually pay more than they were paying where they moved from.

[tromp]

One problem with the above is that you'd need 16GB of storage to check block validity, even for SPV clients on things like cell phones.  So that's one problem that would need to be fixed.

Maybe if the r-value (number of rounds) were really low and only a small fraction of the memory cells wound up being read from the block header could include some kind of map showing which memory cells got hit during the hashing operation.  Then with the map a low-memory device could check a hash.

Even better, SPV clients could ask full-chain clients to calculate the map for them so it wouldn't have to be stored in the chain.  The point is that giving an SPV client a bogus map won't fool them so there's no trust there.

Scrypt already has the lowest possible r=1.
Checking validity becomes somewhat cumbersome at scrypt-13 using 1MB.
A scrypt-29 using 16GB is basically unverifiable for all practical purposes.

You'll need a completely different PoW (i.e. not hashcash based) whose verification time
is constant or growing very slowly (e.g. logarithmic) with increasing memory requirements.

[eldentyrell]

Thanks for your comments; this is the sort of discussion I was looking for.

One problem with the above is that you'd need 16GB of storage to check block validity, even for SPV clients on things like cell phones.  So that's one problem that would need to be fixed.

Maybe if the r-value (number of rounds) were really low and only a small fraction of the memory cells wound up being read from the block header could include some kind of map showing which memory cells got hit during the hashing operation.  Then with the map a low-memory device could check a hash.

Even better, SPV clients could ask full-chain clients to calculate the map for them so it wouldn't have to be stored in the chain.  The point is that giving an SPV client a bogus map won't fool them so there's no trust there.

Scrypt already has the lowest possible r=1.

Sorry, you're right, I got the parameter names mixed up.  What I'm talking about doesn't have a separate parameter in the scrypt specification.  In scryptROMix step 3:


    3. for i = 0 to N - 1 do
          j = Integerify (X) mod N
                 where Integerify (B[0] ... B[2 * r - 1]) is defined
                 as the result of interpreting B[2 * r - 1] as a
                 little-endian integer.
          T = X xor V[j]
          X = scryptBlockMix (T)
        end for


There's no reason why that for loop (bolded) has to be from 0..(N-1); the loop could run more or less than N times.  That's the parameter (the number of times that loop runs) that I was thinking of reducing.  Of course you still have to populate the memory in the first place, which takes N operations, so this isn't a complete solution yet.

You'll need a completely different PoW (i.e. not hashcash based)

Hrm, not hashcash based in what sense?  If you mean not in the sense of using a SHA-family function then sure, but Litecoin is already "not hashcash based" in that sense.

whose verification time is constant or growing very slowly (e.g. logarithmic) with increasing memory requirements.

Yes, I certainly agree that this must be true.

I think the key is to have the hash operation h(x) emit some additional small certificate c that a verifier v(x,y,c) can use to confirm that h(x)=y using logarithmic memory -- whereas computing h(x) without the certificate (or y) requires linear memory.  So it's a trapdoor function from a space complexity perspective.  Surely such a thing must exist; I need to dig the literature.

[tromp]

Thanks for your comments; this is the sort of discussion I was looking for.

Thanks for raising some excellent points in your original post and starting this discussion.

Sorry, you're right, I got the parameter names mixed up.  What I'm talking about doesn't have a separate parameter in the scrypt specification.  In scryptROMix step 3:


    3. for i = 0 to N - 1 do
          j = Integerify (X) mod N
                 where Integerify (B[0] ... B[2 * r - 1]) is defined
                 as the result of interpreting B[2 * r - 1] as a
                 little-endian integer.
          T = X xor V[j]
          X = scryptBlockMix (T)
        end for


There's no reason why that for loop (bolded) has to be from 0..(N-1); the loop could run more or less than N times.  That's the parameter (the number of times that loop runs) that I was thinking of reducing.  Of course you still have to populate the memory in the first place, which takes N operations, so this isn't a complete solution yet.

Scrypt already allows for some time-memory trade-off (TMTO, or, as Dave suggested, "tomato":-)
Reducing iterations will make those trade-offs all the more effective.

Hrm, not hashcash based in what sense?  If you mean not in the sense of using a SHA-family function then sure, but Litecoin is already "not hashcash based" in that sense.

Of course, Litecoin is very much hashcash-based, as are most PoWs proposed these days.

I'm talking about hashcash alternatives like Primecoin, Momentum, or my own design,
Cuckoo Cycle (https://github.com/tromp/cuckoo).

I had hoped the latter could require many GBs of memory,
but Dave Anderson recently pointed out a huge improvement in the algorithm
that slashed the memory requirements by a factor of about 21, meaning it would take
half an hour to run a 16GB instance with 20 threads...

[eldentyrell]

Scrypt already allows for some time-memory trade-off (TMTO, or, as Dave suggested, "tomato":-)

Right, that's why you need ANTI-TMTO modifications in order to force a minimum amount of memory (to thwart botnet-mining).

TMTO works because scrypt writes the memory in-order from 0 to N-1 then reads them in a pseudorandom/unpredictable order; if you didn't save all the odd-numbered words you can recover any one of them on-demand by reading the word before it and doing the mixing operation.  If, on the other hand, you wrote those words in a pseudorandom/unpredictable order as well, TMTO wouldn't be possible (or at least pointlessly time-expensive).

I'm talking about hashcash alternatives like Primecoin, Momentum, or my own design,
Cuckoo Cycle (https://github.com/tromp/cuckoo).

Wow, this is really interesting!  Convenient timing too

So glad you actually wrote a whitepaper.  It's a huge pet peeve of mine when people make some big showy announcement about something and the only clear technical explanation is either their source code or a bunch of random postings scattered across reddit and some webforums .  Thank you for taking the time to do this.

I'm still going through the paper (should finish this weekend) but just one nitpick for now:

Memory chips, in the form of DRAM, have only a tiny portion of their circuitry active at any time, and thus require orders of magnitude less power.

That can be true but it depends on the access pattern...  DRAMs have a lot of internal parallelism, so if you can blast reads/writes at a nice uniform stride that matches the bank size you can actually get more or less the whole thing running at once.  GPUs are designed around exploiting this.  The cycle time at the pins is way way way shorter than the cycle time of the internal arrays.  In fact as you move inward from the pins towards the capacitors each stage of circuitry has a longer cycle time than the previous one (sorta like a pyramid).

But yeah, what you say is true if you're doing serially-dependent reads and it's mostly true if the address pattern is pseudorandom.

[tromp]

TMTO works because scrypt writes the memory in-order from 0 to N-1 then reads them in a pseudorandom/unpredictable order; if you didn't save all the odd-numbered words you can recover any one of them on-demand by reading the word before it and doing the mixing operation.  If, on the other hand, you wrote those words in a pseudorandom/unpredictable order as well, TMTO wouldn't be possible (or at least pointlessly time-expensive).

I think what you call a word is a 128 byte block. Whatever order you generate could be trivially stored in a map of N indices,
so you could still leave out alternate blocks and use the map to find the block from which to generate a missing one?!

So glad you actually wrote a whitepaper.  It's a huge pet peeve of mine when people make some big showy announcement about something and the only clear technical explanation is either their source code or a bunch of random postings scattered across reddit and some webforums .  Thank you for taking the time to do this.

Thanks! I consider a detailed whitepaper a necessity for getting proper exposure and criticism.
The paper needs a lot of updating to take the recent algorithmic improvements into account.

I'm still going through the paper (should finish this weekend) but just one nitpick for now:

Memory chips, in the form of DRAM, have only a tiny portion of their circuitry active at any time, and thus require orders of magnitude less power.

That can be true but it depends on the access pattern...  DRAMs have a lot of internal parallelism, so if you can blast reads/writes at a nice uniform stride that matches the bank size you can actually get more or less the whole thing running at once.  GPUs are designed around exploiting this.  The cycle time at the pins is way way way shorter than the cycle time of the internal arrays.  In fact as you move inward from the pins towards the capacitors each stage of circuitry has a longer cycle time than the previous one (sorta like a pyramid).

But yeah, what you say is true if you're doing serially-dependent reads and it's mostly true if the address pattern is pseudorandom.

Ah, thanks for elaborating. That explains how Cuckoo Cycle can handle so many threads that are all hammering main memory.
With your understanding of parallellizability of memory accesses, do you see possible improvements in the bucketing
mechanism in the current implementation?

[zerodrama]

True decentralization is free market competition and the enemy of free market competition is barriers to entry.  Proof of work is a barrier to entry.

Proof of work is like slicing meat for a sandwich.
Sandwich is like free market.

I want my meat to be sliced in the same thin sizes.
No competition whatsoever.

I want choices of meat and vegetables.
I do not want competition in my sandwich.

I want competition between sandwiches.
You broke the metaphor and now you have to fix it.

[smolen]

TMTO works because scrypt writes the memory in-order from 0 to N-1 then reads them in a pseudorandom/unpredictable order; if you didn't save all the odd-numbered words you can recover any one of them on-demand by reading the word before it and doing the mixing operation.  If, on the other hand, you wrote those words in a pseudorandom/unpredictable order as well, TMTO wouldn't be possible (or at least pointlessly time-expensive).

I think what you call a word is a 128 byte block. Whatever order you generate could be trivially stored in a map of N indices,
so you could still leave out alternate blocks and use the map to find the block from which to generate a missing one?!

Worse, N/(lookup gap), so for lookup gap 4 this map will take only 256 bytes.

[bytemaster]

True decentralization is free market competition and the enemy of free market competition is barriers to entry.  Proof of work is a barrier to entry.

Proof of work is like slicing meat for a sandwich.
Sandwich is like free market.

I want my meat to be sliced in the same thin sizes.
No competition whatsoever.

I want choices of meat and vegetables.
I do not want competition in my sandwich.

I want competition between sandwiches.
You broke the metaphor and now you have to fix it.

Economies of scale (EOS) is a barrier to entry... proof of work always benefits from EOS

Once EOS results in centralization (pools + asic) no one else can safely create POW chains without approval of the industry POW giants.


POW is like having someone producing sliced meat for sandwiches...
EOS + POW means the producer of the cheapest sliced meat owns the production of sandwiches because they can undercut all competitors prices...
If you assume that market participants only buy sandwiches with the most slices then no competitor can produce sandwiches with unapproved vegies or meat.




 

[smolen]

Then the ideal mining device looks like a very cheap (~$50) backplane full of commodity DRAM DIMMs.

Wouldn't separate DRAM chips with independent buses be more effective?