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.

[1714826603]

1714826603

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

[justusranvier]

Not even necessarily attack the network, but to get data - that's such an obvious move...

What kind of sensitive data could such a company grab from a device that's designed to process the data in a public transaction ledger, that generally receives said data from a public mining pool anyone can join?

[jarhed]

A speedup from 256X to 2560X seems possible.

We are Ethereum ASIC!!!!!

[xeroc]

that's such an obvious move...

Wait .. what?

[TierNolan]

Not if it has a capacitor that keeps the timer ticking... how much energy does a wristwatch need?

Battery backup would be better.  A capacitor is not likely to be able to keep a timer running.

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

It depends on what you mean by ASIC.  The actual IC isn't likely to be able to support such a function.

However, an ASIC miner where you connect an ethernet cable could "phone-home" every so often.

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?

There are limits to what you can do with ICs.

[Altoidnerd]

It doesn't need wires dude.  Wireless communications can be packed into tiny spaces.  Antennas are etched into the substrate.  http://www.semtech.com/images/datasheet/sx1242.pdf

Bitcoin ICs are power hungry, its not hard to allocate a little extra wattage.  Manufacturers routinely lie about power consumption anyway - bitcoin ICs dont even have to.

[Altoidnerd]

What kind of sensitive data could such a company grab from a device that's designed to process the data in a public transaction ledger, that generally receives said data from a public mining pool anyone can join?

Your movements around your house.  How often your body is within 7 feet of the machine.  The number of steps you take each day.  How often you use a microwave.

Again, an easier question may be what can't they do.  It's a black box man.  ICs are not getting less capable.  

I have designed an insanely sensitive (and expensive) burglar alarm in my lab before by accident.  You'd be surprised.

Pick up "Circuit Design for RF Transceivers" by Leenaerts.  Then convince yourself extremely high power ICs can't do the things I just said.

The takeaway: these frightening intrusions are unlikely to be going on now, but are absolutely possible.  The future of humanity is a long time; that which is possible will occur in the future.  Learn from the disclosures of 2013.

Therefore, it is wise to move away from these proprietary, closed source black boxes that we must trust in an open source trustless system.  The potential for technology to be harmful to us without our knowledge is ever increasing.  The reversal of this trend is very much in the spirit of bitcoin.

Don't trust a damn.  Just stick to open source.  

[Sergio_Demian_Lerner]

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., proof-of-burn and proof-of-excellence based submissions will also be welcome in some category.

In the post I present a technique to limit the amount of work a node does, not to do any more work than the attackers work.

I repost part of the paper here:

Gradual verification

When SeqMemoHash or RandMemoHash are used as PoW, an attacker may try
a DoS attack by cheating on the difficulty of the PoW, and forcing the verifier to
invest CPU resources in computing the (invalid) MemoHash digest. One way of
protecting from this attack is by creating a PoW that consist of the concatenation
of all intermediate results produced at steps that are power of two (e.g. at hashing
steps 1,2,4,8, ..), and the final result. For the configuration given in the previous
section, this requires 17 intermediate hash digests and the final hash digest (total-
ing 576 bytes). The verifier must check each intermediate state against the given
values during the computation. This protection assures that the attacker must have
performed at least half of the operations performed by the verifier

Also I added RandMemoHash, which (as I tested it) is almost as fast as scrypt also using Salsa20/8 core.

With the parameters I suggest for ASIC resistance, it takes 30 msec to verify on a PC. Using the Salsa20/8 core, it takes less.

Best regards!

[Altoidnerd]

Let's beat a dead horse.

http://www.storagecraft.com/blog/cpu-sounds-allow-cyber-security-crack-potential/

You certainly wouldn't want one of those in your bitcoin miner - that would totally stink eh?

Now whether you believe this crap or not, the message should be clear. Bitcoin is stuck with ASICs forever now, so lets at least get some that are open source.

The way that could work is that the schematics are fully specified and they are then testable to prove that no added functionality exists.  I think.

[justusranvier]

Your movements around your house.  How often your body is within 7 feet of the machine.  The number of steps you take each day.  How often you use a microwave.

Again, an easier question may be what can't they do.  It's a black box man.  ICs are not getting less capable.  

I have designed an insanely sensitive (and expensive) burglar alarm in my lab before by accident.  You'd be surprised.

Oh, you assuming that home mining is still going to be a thing for much longer.

Yeah, in that case I can see why you'd be as concerned.

The amount of mischief they are capable of in a data center environment is not zero, but not quite so personally intrusive.

[grau]

Don't trust a damn.  Just stick to open source.  

Even open source is usually executed on hardware black boxes. I understand your concern, but believe that bitcoin mining with ASIC is one of the least concerning black boxes.

[Altoidnerd]

Don't trust a damn.  Just stick to open source.  

Even open source is usually executed on hardware black boxes. I understand your concern, but believe that bitcoin mining with ASIC is one of the least concerning black boxes.

I know.  It's not like I'm gonna burn my asic miner.  My points are more for the purpose of future slant we can place on our thinking.  I mean look at my mug.  I loooovvveee ICs.  I just think they need to phased out of open-stuff, or made open somehow, OR alternatively made by companies I might actually trust.

I kinda wanna see TI absolutely flood the market with asics so they are sitting inside gumball machines, traffic lights...everywhere.  That I'd be more likely to trust than random companies popping up with silicon.  

And looking at the track record of bitcoin asic distributers...well what do you see?  Shitheads.  I'd like to see a real IC company step in and end the bullshit.

[justusranvier]

I know.  It's not like I'm gonna burn my asic miner.  My points are more for the purpose of future slant we can place on our thinking.  I mean look at my mug.  I loooovvveee ICs.  I just think they need to phased out of open-stuff, or made open somehow.  Not sure how the latter would work though.

ASICs are a very competitive space right now. Anything that uses extra power and does not increase the hash rate puts an ASIC at a severe disadvantage compared to its competitors. For the specific case of hashing I'm not sure how much of a threat really exists.

Now if specialized hardware is ever used to select transactions and construct blocks, that's something I'd be more concerned about.

[Altoidnerd]

Justus I hear your points.  My anti-asic comments apply more to cryptocurrency as a technology going forward.  For bitcoin you can't look back.

About a year ago I was absolutely puzzled by the economics of money printing machines.  What on earth could that mean?  Well after a year we have seen that what hapened was a NEW brand of engineering firm that both makes ICs and also participates in speculative gambling.

If and when texas instruments steps in, so will national semi and samsung and others...and they will not bother at all to play the bitcoin price game.  Only then will the asics be priced fairly, because producing inane quantities of chips is really dirt cheap for these companies.

TI shipped 6 billion ICs last year.

[justusranvier]

My anti-asic comments apply more to cryptocurrency as a technology going forward.  For bitcoin you can't look back.

We'll see if there is any future in non-Bitcoin cryptocurrencies...

I know all the VCs and traders want that kind of a world, but they might not get what they want.

[Altoidnerd]

Oh, its inevitable...the technology exists. The bitcoin centric mindset is pretty short sighted. If people feel, in any given community, for the rest of time, like they are not being served by bitcoin, they can have their own currency at basically the push of a button.  They will exist and be traded.  They may ever be bigger than BTC, but they're obviously going to exist...I know this because I would make one for just my family, inside my home...

I think it's ridiculous to assume otherwise.  Cities will adopt local ones...there will be crytocurrencies circulating in high schools.  Poor countries and impoverished slums will rock their own coins.  

[oakpacific]

Oh, its inevitable...the technology exists. The bitcoin centric mindset is pretty short sighted. If people feel, in any given community, for the rest of time, like they are not being served by bitcoin, they can have their own currency at basically the push of a button.  They will exist and be traded.  They may ever be bigger than BTC, but they're obviously going to exist...I know this because I would make one for just my family, inside my home...

I think it's ridiculous to assume otherwise.  Cities will adopt local ones...there will be crytocurrencies circulating in high schools.  Poor countries and impoverished slums will rock their own coins.  

They can always be 51% attacked if they are smaller than Bitcoin, or if they are PoS, using even easier means.

[justusranvier]

Oh, its inevitable...the technology exists. The bitcoin centric mindset is pretty short sighted. If people feel, in any given community, for the rest of time, like they are not being served by bitcoin, they can have their own currency at basically the push of a button.  They will exist and be traded.  They may ever be bigger than BTC, but they're obviously going to exist...I know this because I would make one for just my family, inside my home...

I think it's ridiculous to assume otherwise.  Cities will adopt local ones...there will be crytocurrencies circulating in high schools.  Poor countries and impoverished slums will rock their own coins.  

I remember a time when there was no global Internet. Every city had their own little BBS, with a handful of national ones. Each was its own walled garden with little-to-no communication between them.

Then flat rate ISPs showed up and wiped all competition off the map*.

Do you think Compuserve and GEnie and AOL really wanted to have their business model steamrollered like that? Too bad - the network effect was too powerful for them.

The advantages of a single currency are too overwhelming for alternatives to become anything more than hobbyist toys that never amount to more than a rounding error.

Maybe it won't be Bitcoin that becomes that single currency, but anything that aims to overthrow it has a high barrier to overcome.



* For that matter, when was the last time anyone used IPX/SPX? How many people even remember it other than that weird network protocol that you sometimes had to use for Starcraft 1 LAN parties?

[coinrevo]

You're assuming the future is going to be like the past. Next generation cryptocurrencies will remove global dependencies from miners and developers. there will be tech which allows to overcome fundamental weakness in PoW. but it's not going to etherum and some academic figuring out a new PoW algorithm.

[justusranvier]

there will be tech which allows to overcome fundamental weakness in PoW.

Forgive me for being skeptical about claims of Bitcoin's PoW having fatal weaknesses.

Bitcoin could have been invented in 1988 instead of 2008, except that everybody who understood cryptography well enough considered the economic properties Bitcoin possesses to be fatally flawed and so never even tried.

Incidentally, Bitcoin's reliance on economic theories that so many people consider to be a flawed are exactly what enabled it to succeed where ever prior attempt failed..

I wish everybody involved with altcoins who do not understand this dynamic the best of luck, since they'll need it.

[Altoidnerd]

[extee]

PoS is rich get richer.

i keep reading this nonsense.
but 1% yearly interest (for processing transaction fees) with 1% yearly inflation....and you call that rich getting richer? an interest that barely beats inflation to me is not profit. it's failure. the getting richer part would only come from me doing real retributed work in the real world....not from just holding PoS coins lol.
and moreover it is not really "interest"...but the stakes "mining" out the fees for transactions.( stakes are the equivalent of asics minus the hardware cost and needless energy waste.)

moreover big hoarders in ia bitcoin deflatuary system are surely getting richer are they not?  just like in PoS everyone see a return depending on how much they own...and the intesrest is not the biggest factor....but  the rise in price/demand is.
and regarding the gneration of new coins or coins received for processing transactions the rich get even more richer in bitcoin....as only those who can invest in big mining enterprises see any of the new generated coins or transaction fees.
at least in PoS no matter how little my stake is I get 1 % return . in mining a little investment would actually mean a loss. either you have big money to throw in it or you are cut out of the system. stakes are a more fair and democratic and less polluting mining chip.
to me all PoW coins are absolute madness. the hashing was needed to secure the network and carry out transcation...it was a necessary evil 5 years ago. but  since PoS came into play....it is just plain evil (without the the necessary bit)

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.

lol i laughed when reading this considering that both the bitcoins and the mining power are increasingly in the hands of a few. 50 people in bitcoin own 30% of all bitcoins....and we have mining increasingly more centralized with some sort of triopolio of the mining world with the biggest player Ghash.io pretty much in the driving seat.
the few big stakeholders in PoS are actually becoming less few and less big by the day ......and not having mining corporations that could hold us at ransom or start asking for increasingly higher fees whenever coins might start running out is a blessing.  PoS is actually guarantee that currency will stay decentralized. there is nothing a big stakeholder in PoS can do to prevent that....all he can do is buy or sell coins and affect the price....same a big stakeholder in bitcoin can do.  instead big mining corporations can have much higher influence on the bitcoin system.

btw not saying all PoS coin out there are perfect.....but they are on the right direction.