Bitcoin Forum

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 (http://www.reddit.com/r/Bitcoin/comments/234iem/bitundo_allowing_you_to_undo_bitcoin_transactions/)... 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 (https://131002.net/siphash/siphash.pdf) is ideal, big thanks to tromp's (https://bitcointalk.org/index.php?action=profile;u=207304) paper on cuckoo cycle (https://github.com/tromp/cuckoo/blob/master/cuckoo.pdf) 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.

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'.

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.

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.

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?

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

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.

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-

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

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.



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.

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.

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.

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



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.



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.




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.

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


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.


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...

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).



Wow, this is really interesting!  Convenient timing too :)

So glad you actually wrote a whitepaper (https://github.com/tromp/cuckoo/blob/master/cuckoo.pdf).  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:


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.

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?!


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.


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?

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.

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

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.




 

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

The purpose of the POW is so nobody can fake transactions. Cryptocoin is an attempt at solving the N-thieves problem. This is similar to the Byzantine Generals problem. You're fixated on a purely technical analysis without any concern for the fact that people have to send something that needs to maintain its value much longer than its transit time.

The purpose of POW is to make it difficult to fake transactions at great expense.   With DPOS it becomes impossible to fake transactions in less than 15 minutes compared to bitcoin where it never becomes impossible without manual intervention of checkpoints.   

POW destroys value in a very real sense.  The goal is irreversible consensus.  POW cannot give you that and is very costly. 

Sure, it's a 1024-bit word.  I think of it that way because it's the word size of the memory on the ideal hardware for scrypt(N=1).



True, but only if the word size is much larger than the memory's address size -- otherwise the "map" takes more memory than you save.

So, therefore, make the memory have 2^N words where N is the number of bits read or written in each memory transaction.  So, for example, 2^32 entries each being 32 bits.  Or 2^16 entries of 16 bits each.  Then the "backward pointers" cost as much space as they save.



What is a lookup gap?

Fortunately there are parts of our economy -- like computer DRAM -- that are much bigger than cryptocurrencies.

In order for the bitcoin mining industry to be as big as the DRAM industry each BTC would have to be worth $25,000 each.  And that's only until the next halving, at which point the price has to be $50,000 each.

Proof-of-X for X!=Work is largely off-topic for this thread.  Only POW serves as an origin of scarcity anchored to something physical (computing devices).

No, because the operations are serially dependent.  You don't know the address of the next read until the current one has finished, so having parallel access to two halves of your memory is no help.

let me rephrase it then:

I strongly believe multi-pow will eventually be the best choice because:

-faster
-more secure(proven to be more resilient to 51% attacks than any other pow scheme be it single or chained)
-even more secure(single-pow if algo is flawed it's doomed, chained algos if one algo is flawed it's doomed, multi-pow if one algo is flawed only the portion of the coin that that algo reigns over is compromised)
-even more more secure(if algos are combined to ensure any type of mining hardware is welcome well that makes the network far more secure than single pow since single pows tend to be dominated by one tipe of mining hardware)
-fairer distribution (wider if asic/gpu/cpu algos are all combined)
-better flexibility(in case of algo problems and hardfork only x% of the network is fazed while the rest of the algos continue business as usual)


and so on and so forth, the list is way longer but it's 4 am.
so op please don't delete my post again because it now fits the designated pattern of your thread.

Okay, I was able to make a first pass.  I want to call out three really awesome contributions you've made:

1. Identifying cycles as the structure to be sought (this is a big deal, more on this later)

2. Making the memory size be (at least the high-order part of) the difficulty.  This avoids having to pick magic numbers like "16GB" out of the air.

3. Using siphash() -- very cool, I've updated my initial post to mention this.

Typo: second page, "proof-of-work system. which".  I think the period should be a comma.

Disclaimer: I didn't read the paper on cuckoo hash tables because your description of the proof-of-work (an undirected cycle of length >L in the graph of the converse composition of two hash functions with disjoint ranges) made sense right away.  Let me know if I missed anything as a result.  Or if I misunderstood the POW, but I think I got it.

One thing that nagged me was that the size of the proof scales with L.  Since the proof has to go in the block headers, which even SPV clients need, it's the most space-sensitive part of a cryptocoin.  Could one look for a cycle instead in the graph of a hash function postcomposed with "modulo N" where N is the targeted memory size?  Then you can prove a cycle of length L>L_min by giving any element in the cycle, and a verifier can check your proof with O(log N)-memory and O(L)-time.  This is partly why I'm excited about cycles as the proof.  Also, in a sense this is what scrypt is, except that it asks for a path rather than a cycle and the hash function is H(n)=salsa^n(0) (where salsa^0(x)=x and salsa^(n+1)(x)=salsa(salsa^n(x))) -- the write-phase is a sort of Ackermann construction.  (okay that's not exactly scrypt -- the read phase maintains an accumulator which gets xored in before each salsa20/8).

The cycle-in-a-single-hash-function scheme proposed in the previous paragraph is best implemented with N-many log(L_max)-bit words of memory, so it sort of assumes something close to the "liveness bitvector" approach like Dave used in his comments on the cuckoo cycle… it isn't so much an attack as the intended implementation.  It can't be effectively parallelized since the amount of data you'd need to communicate is proportional to the amount of computation (total)… the communication ends up costing more than the computation you're parallelizing.  But the real drawback is that the memory accesses are not in any way serial.  So the ideal hardware looks like a tiny loop running the hash over and over, blasting addresses at a custom memory.  The memory always writes a "1" to the address given, and reports "hit" when a "1" is written over an existing "1" (memory initializes with all zeroes).  So there's perfect pipelining between the memory and the computation.  That's a big problem.  I suspect the way around it is some Ackermann-like construction.

The other reason I'm excited about cycles is that they don't yield well to divide-and-conquer.  Two halves of an L-cycle are an X-path and Y-path where (X+Y=L)… but long paths are so commonplace that the coordination between two parallel path-finders to see if any of their paths form a cycle is likely to be as expensive as just looking for the cycle.

The scarcity of BTC and POW systems has nothing to do with the POW algorithm and everything to do with the social contract of the nodes.   Having studied POW systems for a very long time to build a memory-hard easy to verify algorithm... I believe I had a lot of success and with small tweaks could achieve it.

This thread, being about POW innovations is really aimed at network security in the most decentralized manner possible.   

DRAM may be a much larger industry and it is unlikely an ASIC could be developed that is more effecient, but no ASIC needs to be developed for EOS to apply.   You don't think someone could build a special-purpose motherboard / CPU designed to minimize overhead costs around the DRAM?   You think large warehouses of case-less, power supply-less, liquid cooled, over-clocked, modules would not make mining at home unprofitable?   You think bulk buys cannot make it significantly cheaper for these large factories?   

The reality of POW is that security is proportional to economic cost and whether the attacker is spending $500 M on SHA256 ASIC or $500M on dedicated hardware the result is the same, $500 million being transferred from shareholders to miners while the network centralizes in the mining pools and barriers to entry are erected. 

If you increase the cost-per-hash with memory-hard POW, you will get fewer hashes but the same level of security and only the most efficient operations will be able to mine profitably.   Once mining profitability for the average home PC is negative the network is depending upon charity to remain decentralized.   Sure anyone can mine, but not everyone can mine profitably. 

With POW the network is not sustainable.

I think cycles could be substituted by other structures, like cliques. Obviously you'd need to use
plain instead of bipartite graphs, and a larger fraction of edges to get something
like a 10-clique occurring with non-negligible probability.

I originally used sha256 to generate edges. I was very happy when I later realized I could use
this lightweight function instead. Being keyed made its use even more natural.

I introduced several typos when hastily rewriting parts of the paper to reflect the shift of focus
from memory-hardness (since it's not as tmto proof as i thought it was) to being graph-theoretical.
So please just gloss over the obvious grammatical mistakes. They'll get fixed in the weeks ahead.


I don't know what you mean by converse composition, given that the two hash functions are not injective.
Also, I look for cycles of length exactly L rather than > L.

Yes, proof size of 168 bytes, or Lx4 bytes in general, is a downside.

If you're suggesting looking for cycles in a hash function with equal domain and range, that
doesn't need any memory. You can use either Floyd's or Brent's cycle detection algorithm in constant space.

That was smolen's remark, not mine:-(

Well, you and I clearly disagree about that.



"Security" is a vague enough term that it's hard to disagree there.



Sure; in fact, I expect them to.  But the whole point is to pick a POW algorithm where the returns of doing this diminish long before the "special-purpose motherboard"'s cost gets anywhere near a quarter or so of the cost of the DRAM.



I think that the people who design pretty cases for miners will find other jobs.

I think that unpowered modules are pretty damn useless.

I think that overvolting DRAMs will actually DECREASE the number of operations in their lifetime before they fail.

I think that water-cooling DRAMs without overvolting will not even double their performance.

I think that moving SHA-256 from a GPU to an ASIC has already produced a 1,000-fold increase in performance-per-square-millimeter-of-silicon.



Nope, not significantly.  DRAM is already a razor-thin-margin business.  That's why I picked it.



I don't think you've been reading this thread.  This makes dedicated hardware a disadvantage.




Yeah, you definitely are not reading the thread.  Go back and read the part that says "has a cost-of-ownership dominated by silicon rather than electricity".

Don't take it personally, but I tend to stop replying to people who aren't at least trying to follow the discussion...

So sorry.  I hate the bitcointalk web interface.  Why did we ever get rid of Usenet?….

Hmm, I see what you mean.
Maybe you don't even need separate filling-memory and reading-memory phases. Something like
(assuming a hash function mapping 1024 bits to 1024 bits):

 

Hmm; that still needs an initialization phase, unless we assume the memory starts out all 0.

But I still don't see these schemes as viable PoWs due to the lack of quick verifiability...
  

If you want the cost to be dominated by silicon.... and the gains from special purpose manufacturing to be small enough that no one will try.  I can run with that.

Suppose a device exists that people already have (DRAM) and an algorithm is developed that uses 0 electricity (so we take it out of the equation) and also has 0 computation cost (so we can take it out of the equation).  This would be the IDEAL device that you are trying to achieve.

The cost of running a miner is now just the consumption of DRAM which is presumably sitting idle on peoples computers.

To attack this network one would need to acquire 51% of the DRAM dedicated to the purpose of securing the network.   

Total Federal employees in the US is 4.3 million and we will assume they each have a computer with DRAM that is unused 75% of the time.   A rapid software push to all government computers would instantly attack a network of 4.3 million honest individuals using their home PC.

Now if you throw in the PCs of all government contractors, state employees (schools/universities), you could probably double that number.   Remember we are just counting unused government resources here.

Now if you consider that it is nothing for the government to spend $100 per adult in the USA to buy the DRAM necessary to match their mining...  that the average individual no longer buys computers, they buy tablets or notebooks which are then left off... it wouldn't be hard at all to match the actual DRAM used by consumers for mining...
Now if you consider that many people will voluntarily support the government's mining efforts to freeze accounts, especially if they get paid...

But you can ignore ALL of that.... the total cost of a 51% attack on this network would simply be for the government to add 10% or perhaps double the mining reward for miners that point their computers at the governments mining pool.   In the case of bitcoin, this could be achieved for $400 million per year right now (perhaps less)... simply because it is more profitable to mine on the government's pool than on the good pools.    Now you have profit vs charity and guess which one will win?

Those that point at honest pools don't get paid out at all if the honest pool includes a spend from a frozen account because the government pool will 'fork' the chain and ignore it.  So you either get 51% or go home.  The government would just keep upping the mining reward until their pool won.  Game over. 

POW = Control by Money, Period.

(still need to catch up on last few posts but this is relevant/breaking news):

15-Apr: it has begun (http://www.reddit.com/r/Bitcoin/comments/234iem/bitundo_allowing_you_to_undo_bitcoin_transactions/)… and much sooner than I thought.

There are simple solutions available and some are already present :)