Ethereum “Dagger” PoW function is flawed (technical off-topic)

[Sergio_Demian_Lerner]

One of the features in Ethereum is the use of a PoW function specially designed to be memory-hard. While this may be true (though a formal proof is missing and the design document is quite incomplete), the authors completely forgets another key property a PoW function must provide: it must be sequential-memory hard. This means that not only the function should require large amounts of RAM, but it must not allow easy parallelization. Dagger seems to provide almost the best possible scenario for parallelization. In Dagger, a certain amount of RAM is filled by pseudo-random data derived from the header and the nonce. This data is produced in rounds. Each round, a number of elements from the previous round outputs are hashed together to produce the elements of the following round. These hashes can be performed in parallel. An optimized implementation for an ASIC (or FPGA) is evident for anyone with some discrete logic design background. A speedup from 256X to 2560X seems possible.

I posted more on this issue here:

http://bitslog.wordpress.com/2014/01/17/ethereum-dagger-pow-is-flawed/

My own proposal (SeqMemoHash) solves this problem (http://bitslog.wordpress.com/2013/12/31/strict-memory-hard-hash-functions/)

Best regards,
 Sergio.

[1714815456]

1714815456

[1714815456]

1714815456

[cdog]

Although I cant proclaim a technical understanding of the issue, making your research public is certainly appreciated. Ethereum seems quite ambitious, to say the least

[Vitalik Buterin]

Our updates:

1. The problem that I have with scrypt or SeqMemoHash is that they are not memory-hard enough; they are just as memory-hard to verify as they are to compute, which puts a natural cap on how high the parameters can be tweaked. The reason why I came up with Dagger in the first place was to create a PoW that is memory-hard to compute but memory-easy to verify, since you only need a small amount of memory for one nonce, so that you can tweak up the memory requirement per thread to an extremely high value.
2. We did make a simplication and improvement to Dagger (basically, we linearized the tree, so a node always theoretically can depend on the node right before it); this should mitigate this attack somewhat, and parameter tweaks that sacrifice some of its memory-hardness to compute or memory-easiness to verify can be used to mitigate the attack further as much as necessary, in the limit turning Dagger into yet another Scrypt clone.
3. We are actively researching proof of stake, and I came up with Slasher as a proof of concept next-generation PoS algorithm; we may use PoS in combination with PoW.
4. (MOST IMPORTANT) We will actually be holding a proof-of-work contest, where research groups from universities will be invited to come up with ASIC-resistant proofs of work and panels of judges will determine winners. We will have funds to pay substantial prizes, so we hope to attract a large amount of interest. Proof-of-stake, proof-of-burn and proof-of-excellence based submissions will also be welcome in some category.

[Come-from-Beyond]

We are actively researching proof of stake, and I came up with Slasher as a proof of concept next-generation PoS algorithm; we may use PoS in combination with PoW.

So u don't use an already tested solution (Peercoin's PoS), who will do the peer review then? Sunny King? Balthazar?

[grau]

4. (MOST IMPORTANT) We will actually be holding a proof-of-work contest, where research groups from universities will be invited to come up with ASIC-resistant proofs of work and panels of judges will determine winners. We will have funds to pay substantial prizes, so we hope to attract a large amount of interest. Proof-of-stake, proof-of-burn and proof-of-excellence based submissions will also be welcome in some category.

Would you please point me to arguments supporting the need of ASIC resistance?

What is PoS good for as extending any number of forks simultaneously with it costs just as much as extending the trunk?

[TierNolan]

What is PoS good for as extending any number of forks simultaneously with it costs just as much as extending the trunk?

He covers that.  A miner is only allowed to sign one fork for a given height.  If you sign 2, there is a penalty for the miner.

It requires nodes to track multiple forks though, so they can detect the double spend (mine) attempt.

[Come-from-Beyond]

It requires nodes to track multiple forks though, so they can detect the double spend attempt.

They could use Transparent Mining to counteract multiple forks attack.

[coinrevo]

what is the model of "transparent" fundraising? fundraising when even proof of work/proof of stake is not fixed and source is not open is pretty much a red flag given historic precedent. note that historically some of these projects turned from proof of work to proof of stake. all new models would want to avoid the same historic failures and make sure they are not considered to be the same model.

[Ursium]

what is the model of "transparent" fundraising? fundraising when even proof of work/proof of stake is not fixed and source is not open is pretty much a red flag given historic precedent. note that historically some of these projects turned from proof of work to proof of stake. all new models would want to avoid the same historic failures and make sure they are not considered to be the same model.

RE: source, the current state of the code is freely available on https://github.com/ethereum/.

[grau]

What is PoS good for as extending any number of forks simultaneously with it costs just as much as extending the trunk?

He covers that.  A miner is only allowed to sign one fork for a given height.  If you sign 2, there is a penalty for the miner.

It requires nodes to track multiple forks though, so they can detect the double spend (mine) attempt.

I am not sure that cuts it. A big stake gives access to deterministic yield enhancing strategies even more than a huge mining capacity in PoW. Just like playing no-limit poker against a huge stack is not fun.

[TierNolan]

I am not sure that cuts it. A big stake gives access to deterministic yield enhancing strategies even more than a huge mining capacity in PoW. Just like playing no-limit poker against a huge stack is not fun.

It would depend on the statistics, but requiring one fork only to be signed covers (or at least helps with) the "nothing at stake" problem.

[xeroc]

I see PoS to be superior to PoW .. Why not use 100% PoS much like nxt?

[Altoidnerd]

Would you please point me to arguments supporting the need of ASIC resistance?

Integrated circuits are black boxes, the enemy of open source technology.

[justusranvier]

Would you please point me to arguments supporting the need of ASIC resistance?

What is PoS good for as extending any number of forks simultaneously with it costs just as much as extending the trunk?

PoS and ASIC resistance is desirable to people who feel that Bitcoin's biggest flaw is not enough communism.


If you believe in the concept of market failure, and don't see the contradiction between a desire for a decentralized currency and the desire for a cartel of large stakeholders to be able to maintain control, then PoS is a perfect fit.

[Altoidnerd]

PoS is rich get richer.  Cash doesn't earn interest; interest bearing accounts are bank-y.

Innovation is needed, rather than choosing between two defective systems.

And my Anti-Asic feelings are because fabrication of CMOS gates is extremely specialized, and once they're packaged, you cannot prove they don't do fucked up things.  Their fabrication is essentially irreversible ... everything about ICs is incompatible with "trustless systems."

[TierNolan]

And my Anti-Asic feelings are because fabrication of CMOS gates is extremely specialized, and once they're packaged, you cannot prove they don't do fucked up things.  Their fabrication is essentially irreversible ... everything about ICs is incompatible with "trustless systems."

ASICs are just used for hashing.  All the "intelligence" is in the part of the system that creates the blocks.  That is the miner software (open source) or the maybe the firmware (coinbase changes only).

You give your ASIC a block header and have it find a nonce that hashes to the target.

The ASIC knows nothing about the block it is hashing against.

What specific attack or you thinking of?

There is an argument that going to 64 bit nonces would potentially help.  32 bit nonces may require that more functionality is added to the miners.  Even then, it is likely that they would just have the ability to update the extra-nonce in the coinbase.

[Altoidnerd]

What specific attack or you thinking of?

The list is infinite, because they can do anything; but just for an example, a loop counter with a shutdown...

"aw my asic broke. better buy a new one."

The technology is closed source.  It could be literally set to explode at a certain time, or include a small transmitter to wirelessly send data.  Need I go on?

It's impossible to imagine everything that an IC could be doing without your knowledge.  Using IC's requires trust...and the makers of bitcoin hardware are random startups that just got rich.  They're not TI.

[Altoidnerd]

Here's a creative one.  An ASIC manufacturer distributes many ASICs under a different company name, which are all set to stop working at 2 pm on april 4, 2016, at which time someone suddenly has most of the network, and years of foresight to plan for the event.

It's tin foily to go on.  All I am suggesting is move away from integrated circuits all together...whenever possible...because they are trust boxes in a trustless system.  Accept it as an axiom that ICs = bad; period.

Edit: ah..and furthermore, bitcoin IC makers know PRECISELY how their customers will use the device too.  24/7 doing exactly xyz...this is unlike any other situation with integrated circuits...it's particularly worrisome for me, because I am all too aware of the insane capabilities of modern ICs.

[TierNolan]

Here's a creative one.  An ASIC manufacturer distributes many ASICs under a different company name, which are all set to stop working at 2 pm on april 4, 2016, at which time someone suddenly has most of the network, and years of foresight to plan for the event.

That would stall the block chain.  It would have to be combined with owning a pool with a large portion of the network power.

How are you planning to sync all the ASICs?  A counter would stop when the ASIC is not connected.

It does point at the potential risk to ASICs which have network controllers.

[Altoidnerd]

How are you planning to sync all the ASICs?  A counter would stop when the ASIC is not connected.

Not if it has a capacitor that keeps the timer ticking... how much energy does a wristwatch need?  A digital timer needs way less.

Asics not connected long term wont have the desired effect of shutting off simultaneously - so that case doesn't matter anyway.

Forget attacking the network for a moment...If I headed up a company that made bitcoin ICs, I would definitely be looking into how to pack extra functionality into them to collect data, at the very least.  Not even necessarily attack the network, but to get data - that's such an obvious move...

I mean its easier to just admit asics are dangerous than list all the risks... unless they are open source.  Then they could be OK; otherwise, do as cee-lo would do, and forget them.  You know?