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

[zerodrama]

If you assume that market participants only buy sandwiches with the most slices then no competitor can produce sandwiches with unapproved vegies or meat.

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.

[bytemaster]

If you assume that market participants only buy sandwiches with the most slices then no competitor can produce sandwiches with unapproved vegies or meat.

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. 

[eldentyrell]

I think what you call a word is a 128 byte block.

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

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

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.

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

What is a lookup gap?

[eldentyrell]

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

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

[eldentyrell]

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?

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.

[foodies123]

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.

[eldentyrell]

So glad you actually wrote a whitepaper.

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

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.

[bytemaster]

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

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

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.

[tromp]

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.

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.

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.

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.

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

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.

[tromp]

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

What is a lookup gap?

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

[eldentyrell]

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

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.

Well, you and I clearly disagree about that.

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

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

You don't think someone could build a special-purpose motherboard / CPU designed to minimize overhead costs around the DRAM?

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.

You think large warehouses of case-less, power supply-less, liquid cooled, over-clocked, modules would not make mining at home unprofitable?

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.

You think bulk buys cannot make it significantly cheaper for these large factories?

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

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,  

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

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.

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

[eldentyrell]

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

What is a lookup gap?

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

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

[tromp]

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

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.

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

Code:

state = hash(header)
do 2^32 times {
  interpret state as 16 pairs (i,v) of 32-bit values; for each pair set mem[i] := v
  state = hash(state)
  interpret state as vector of 32 bit indices; mix in all 32 mem[i]
  state = hash(state)
}

 

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

[bytemaster]

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.

[eldentyrell]

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

15-Apr: it has begun… and much sooner than I thought.

[Fdt]

There are simple solutions available and some are already present