ASIC-hostile & Botnet-hostile coin

[Come-from-Beyond]

Right now we see only 2 options in hashing algos:
- ASIC-hostile (Scrypt)
- Botnet-hostile (SHA-2/3)

I'd like to talk about an improvement in Scrypt-based coins that would let to create a coin with both options.

Imagine that instead of finding a nonce to win a block, u have to find 1500 nonces but every Nth nonce depends on the previous one. Difficulty of finding a nonce should be low enough to find it very quickly (0.1 second, for example). 1500 nonces would be found within 150 second (2.5 minute) in this case.

Workflow looks like this:
1. Find nonce0 with x0 = Scrypt(block_hash + nonce0) < target
2. Find nonce1 with x1 = Scrypt(x0 + nonce1) < target
3. Find nonce2 with x2 = Scrypt(x1 + nonce2) < target
...
1500. Find nonce1499 with x1499 = Scrypt(x1498 + nonce1499) < target

Of course, all these 1500 nonces must be included into the block header.

A botnet master could use their botnet to find the very 1st nonce, but after it's found, the zombie-computer has to send the nonce to all other zombies. Network latency doesn't allow to do it quickly, do u see the point?

Well, I hope u got the idea. Any comments?

[1714662407]

1714662407

[1714662407]

1714662407

[1714662407]

1714662407

[DeathAndTaxes]

A system like that would ensure that all miners are forced to join pools or suffer reduced earnings.  Worse bigger pools would be more successful then small ones, and played out that game will end up with one pool with a super majority of the hashing power.

The reason is that under "1 winning nonce" system (all coins to date) there is no "progress" towards a block.  Thus when a block is solved by another miner you don't lose anything.  Each nonce attempted is an independent lottery ticket and it either instantly wins or it is instantly worthless.  This means large miners don't earn disproportionately more than smaller miners.  Larger miners have less variance, but in the "long run" all miners earn their "fair share" of the network hashrate.  Someone with 10% of hashpower will solve 10% of the blocks and someone with 1/100th of 1% of the hash power will solve 1/100th of 1% of the blocks. One word description: independent trials.

Under a "x winning nonces solve a block" there IS progress towards a block and the larger x is the more progress it takes and thus can be lost.  If you solve 1499 nonces and another miner solves 1500 you will get nothing and he gets everything.  Lets look at a scenario where the entire network consists of two miners/pools.  Pool A has 60% of the total hashpower and pool B has the other 40%.  At first glance you would assume that just like above Pool A would get 60% of the blocks and Pool B would get 40%, however that isn't true.  Pool B will has a 40% chance to solve a SINGLE nonce before Pool A but since it takes 1,500 to solve a block Pool B would need to win this 60/40 flip, 1500 times to get to the finish line first.  While the smaller pool will sometimes get lucky and beat the odds in the long run it will earn less than its share of the hashpower.  I believe it would be ~18% of the blocks with 40% of hashpower (did a quick & disty monte carlo simulations but obviously you could a much longer more complex one).   Now the reality is no miner in Pool B is going to accept less than half the theoretical return, especially when miners in pool A are making 46% more than theoretical fair value.  I mean imagine you have 1 MH/s, you could earn 1 xCoin per day in Pool A, or 3.2 xCoins per day in Pool B.  How long would it take for you to decide to mine in Pool B?   For every miner that leaves Pool B, Pool A's "efficiency" will improve and Pool B's effecinecy will get worse.  Eventually Pool B will collapse and there will be only one pool left.   

At this point no other pool even has a chance of forming.  Say a group of advocates get together 10% of the hashing power to decentralize the network.  They would lose over 90% of the expected return trying to fight Pool A, and Pool A miners would collect a 9% bonus for doing nothing but mining normally.   Now if two pools result in a reduction to one pool, you can work backwards, three pools A, B, C with uneven split, C is the smallest pool under performs and loses miners to the larger two and eventually only A & B remain.  Working all the way back to the genesis block starts with a large number of pools and solo miners but eventually all the hashing power will end up in one pool.  One word description: dependent trials.

Independent trials = no progress towards a block.  More hashing power working on the same block only results in less volatility, the expected reward is not changed.*
Dependent trials = progress towards a block.  More hashing power working on the same block means higher returns per unit of hashing power (at the expense of lower returns per unit of hashing power by smaller miners/pools).

If you doubt the conclusion look at how much concentration of hashing power there is in the top 5 pools for Bitcoin, and this is under a "game" where large pools actually DON'T earn more than smaller pools (per unit of hashing power).  The only advantage large pools have is lower volatility and more consistent payments, even limited to this indirect benefit it has resulted in significant concentration of hashing power.  I think you can see a "game" where the rules are changed so that larger miners/pools actually earn more than smaller pools means will result in only one pool.  If BTC Guild miners earned 20% more than the average miners, and the miners in the smallest pools earned 20% less than the average how big do you think BTC Guild would be today?  How long do you think that would take?


* Some miners just like roulette players convince themselves there is progress and a pool which is unlucky will become lucky as if the failed nonces will influence the randomness of future nonces and solve blocks "faster", just like if you lose a large numer of times in a row at the craps table you are now "due" a winner. That is merely the gambler's fallacy, each event is independent.

[smeagol]

You essentially would ensure that all miners are forced to join pools and bigger pools would be more successful then small ones.  Played out that game will end up with 1 pool with a super majority of the hashing power.

The reason is that under "1 winning nonce" system (all coins to date) there is no "progress" towards a block.  Thus when a block is solved you don't lose anything.  Each nonce attempted is an independent lottery ticket and it either wins or is worthless.  This means large miners don't earn disproportionately more than smaller miners.  They have less variance but in the "long run" someone with 10% of hashpower will solve 10% of the blocks and someone with 1/100th of 1% of the hash power will solve 1/100th of 1% of the blocks. One word description: independent trials.


Under a 1500 winning nonces solve a block there IS progress towards a block.  If you solve 1499 nonces and another miner solves 1500 you will get nothing and he gets everything.  To simplify it imagine a scenario where there are only 2 mining pools.  Pool A has 60% of the hashpower and pool B has 40%.  At first glance you would assume that pool A would get 60% of the blocks and Pool B would get 40%.  That isn't true though.  Pool B will solve 1 NONCE before Pool A 40% of the time but to win the block they would need to win that 60/40 flip 1500 times.  Despite having 40% of the global hashrate they would only get 18% of the blocks.  Of course no miner is going to accept less than half the return so they will leave Pool B for Pool A and eventually there will be one pool.  Now you can work backwards and see that the same scenario applies with more pools so that will lead to less pool.  One word description: dependent trials.

Independent trials = no progress towards a block.  More hashing power simply means less volatility.
Dependent trials = progress towards a block.  More hashing power means higher returns per unit of hashing power (at the expense of lower returns per unit of hashing power by smaller miners/pools).

Look how much concentration of hashing power there is in the top 5 pools for Bitcoin.  This is under a "game" where large pools don't earn more than smaller pools per unit of hashing power.  The only advantage large pools have is lower volatility and more consistent payments.  Even that small edge has resulted in significant concentration.  I think you can see a "game" where the rules change so that larger pools actually earn more than smaller pools means there will be only one pool.

+1
but to solve that you could try having a payout for each solved nonce, getting progressively higher until the final one.  That means that botnets might get the first but will still recieve a VERY small payout.

[Seth Otterstad]

Increasing the amount of bandwidth required to mine will thwart botnets.  If DeathandTaxes' concern can be solved, this would be good and result in a wider initial distribution of coins.  The botnet-thwarting mechanism should be phased out of the alt-coin in favor of low-latency mining on a fixed schedule of say 3 years, since once ASICs are mining it, botnets can't make more money from mining than they can from doing DDOS attacks etc.

Scrypt being ASIC-hostile does not matter.  Yes it is harder and more expensive to make an ASIC for it, but even if the ASIC is only 10x more efficient than a video card, video cards will eventually be obsolete and not able to mine profitably.

[DogtownHero]

the solution


a coin based on Whirlpool T, will be neither mineable by asics or gpus.

an overview
http://en.wikipedia.org/wiki/Whirlpool_(cryptography)

an example implementation in C

First take a look at Merkle–Damgård construction. Virtually all hash functions follow such construction. Informally, it applies a compression function iteratively to reduce the input size to get some fixed-length output. For instance, you can hash a whole DVD (~ 4.3 GB) and get a 128-bit code.

Let M be the input to an MD-based hash function. The MD construction appends a pad and the length of M to it, so as to prevent several attacks.

Whirlpool uses a compression function named W. W is similar to a block cipher named Rijndael, which is now standardized under the name AES (Advanced Encryption Standard). Rijndael has 3 variants: 128-bit, 192-bit, and 256-bit. The inventors of Whirlpool decided that no Rijndael variant is secure enough to be used as the compression function for a hash. Thus, W is designed so as it accepts 512-bit inputs, and produces 512-bit outputs. The key size of W is 512 bits as well.

Whirlpool works as follows. Let M be the input. M is divided into 512-bit segments: M=(M0,M1,…,Mt). Let h0 be some initial value (fixed by Whirlpool standard).

For i=1,2,…,t, apply W iteratively as follows:

Code:

hi=W(hi−1,mi)⊕hi−1⊕mi

where the first input to W is a block-to-be-encrypted, and its second input is the encryption key. ⊕ denotes the XOR operation.

ht is considered as the output of the Whirlpool hash function.

The whole complexity lies in designing W. As pointed out before, it is similar to Rijndael, so you can understand it if you get familiar with Rijndael, on which I have designed a set of slides. The slides are self-contained and do not assume any math background beyond high school.

[DogtownHero]

a little more on whirlpool, pulled this off a crypto site.

The API for using Whirlpool consists of the functions NESSIEInit, NESSIEadd and NESSIEFinalize.

The first function initializes an instance of NESSIEstruct (in the C version). You the enter the data using NESSIEadd. You get the hash using NESSIEfinalize.

The only non-trivial part is how to add the data. The function that adds data gets a vector of bytes and its length in bits; the last byte can be partial, but I guess you have no need for that.

You can add data as many times as you want; adding d1 then d2 then d3 is the same as adding d1d2d3, i.e. it doesn't matter how you break the input. It's like an input stream then gets a vector of bits and takes care of everything else.

Internally, it's a pretty standard hash function built around an AES variant. The hash function works on chunks of 512 bits - you have to be careful about padding if your input isn't an integer multiple of this (if you do this improperly, there are some simple attacks).

The internal state S is also 512 bits, and is init with zero. To process a block B, first encrypt S using some constant round keys; the intermediate results are used as round keys for an encryption of B. Xor the result (B encrypted with round keys generated from S) to S and to B to get the new S. The hash itself is the value of S after the last input block.

All encryptions are with respect to the AES-like cipher, which is pretty similar to AES but uses for example a different S-box and a different MDS (there are other small differences).

obviously it could be as simple as replacing all the hashing functions with the same function for in whirlpool, then rewriting the built in py miner included with all coin src's

i'm sure a brilliant programmer such as sunnyking or mikhael could do something like this with relative ease.

[markm]

Maybe we just need to get block erupters down in price to address the desire for anyone anywhere to very inexpensively get into mining.

Though I suppose if they do get very widely used that will cause more and more machines that happen to get taken over by a botnet to also happen to have a few USB mining ASICs plugged in?

-MarkM-

[DeathAndTaxes]

Maybe we just need to get block erupters down in price to address the desire for anyone anywhere to very inexpensively get into mining.

Though I suppose if they do get very widely used that will cause more and more machines that happen to get taken over by a botnet to also happen to have a few USB mining ASICs plugged in?

-MarkM-

The main problem with botnets is that the zombie owners don't pay any real cost for their infected nodes.  This is why they are so hard to fight.  The targets of botnets pay all the cost of fighting them, the botnets fight with "free" hardware and the cost to each zombie owner is relatively small often it goes unoticed.

Ironically the block eruptor would act like a canary in a coal mine.  Seeing the shares/revenue go to zero would alert the owner that their system is compromised.  If the owner can't get their computer fixed then there would be no reason to leave the eruptor plugged in and running.  They would either unplug it an put it in a drawer or maybe sell it on ebay for $5.  Either way it would be very hard for a botnet operator to contiunally steal a resource the zombie victim is likely to notice.

[markm]

Awesome! Botnet takeover detector only 0.49 bitcoins, get yours now!

Heck throw one in free with every licensed copy of a $99 antivirus package!

-MarkM-

[Come-from-Beyond]

A system like that would ensure that all miners are forced to join pools or suffer reduced earnings.  Worse bigger pools would be more successful then small ones, and played out that game will end up with one pool with a super majority of the hashing power.

The reason is that under "1 winning nonce" system (all coins to date) there is no "progress" towards a block.  Thus when a block is solved by another miner you don't lose anything.  Each nonce attempted is an independent lottery ticket and it either instantly wins or it is instantly worthless.  This means large miners don't earn disproportionately more than smaller miners.  Larger miners have less variance, but in the "long run" all miners earn their "fair share" of the network hashrate.  Someone with 10% of hashpower will solve 10% of the blocks and someone with 1/100th of 1% of the hash power will solve 1/100th of 1% of the blocks. One word description: independent trials.

Under a "x winning nonces solve a block" there IS progress towards a block and the larger x is the more progress it takes and thus can be lost.  If you solve 1499 nonces and another miner solves 1500 you will get nothing and he gets everything.  Lets look at a scenario where the entire network consists of two miners/pools.  Pool A has 60% of the total hashpower and pool B has the other 40%.  At first glance you would assume that just like above Pool A would get 60% of the blocks and Pool B would get 40%, however that isn't true.  Pool B will has a 40% chance to solve a SINGLE nonce before Pool A but since it takes 1,500 to solve a block Pool B would need to win this 60/40 flip, 1500 times to get to the finish line first.  While the smaller pool will sometimes get lucky and beat the odds in the long run it will earn less than its share of the hashpower.  I believe it would be ~18% of the blocks with 40% of hashpower (did a quick & disty monte carlo simulations but obviously you could a much longer more complex one).   Now the reality is no miner in Pool B is going to accept less than half the theoretical return, especially when miners in pool A are making 46% more than theoretical fair value.  I mean imagine you have 1 MH/s, you could earn 1 xCoin per day in Pool A, or 3.2 xCoins per day in Pool B.  How long would it take for you to decide to mine in Pool B?   For every miner that leaves Pool B, Pool A's "efficiency" will improve and Pool B's effecinecy will get worse.  Eventually Pool B will collapse and there will be only one pool left.   

At this point no other pool even has a chance of forming.  Say a group of advocates get together 10% of the hashing power to decentralize the network.  They would lose over 90% of the expected return trying to fight Pool A, and Pool A miners would collect a 9% bonus for doing nothing but mining normally.   Now if two pools result in a reduction to one pool, you can work backwards, three pools A, B, C with uneven split, C is the smallest pool under performs and loses miners to the larger two and eventually only A & B remain.  Working all the way back to the genesis block starts with a large number of pools and solo miners but eventually all the hashing power will end up in one pool.  One word description: dependent trials.

Independent trials = no progress towards a block.  More hashing power working on the same block only results in less volatility, the expected reward is not changed.*
Dependent trials = progress towards a block.  More hashing power working on the same block means higher returns per unit of hashing power (at the expense of lower returns per unit of hashing power by smaller miners/pools).

If you doubt the conclusion look at how much concentration of hashing power there is in the top 5 pools for Bitcoin, and this is under a "game" where large pools actually DON'T earn more than smaller pools (per unit of hashing power).  The only advantage large pools have is lower volatility and more consistent payments, even limited to this indirect benefit it has resulted in significant concentration of hashing power.  I think you can see a "game" where the rules are changed so that larger miners/pools actually earn more than smaller pools means will result in only one pool.  If BTC Guild miners earned 20% more than the average miners, and the miners in the smallest pools earned 20% less than the average how big do you think BTC Guild would be today?  How long do you think that would take?


* Some miners just like roulette players convince themselves there is progress and a pool which is unlucky will become lucky as if the failed nonces will influence the randomness of future nonces and solve blocks "faster", just like if you lose a large numer of times in a row at the craps table you are now "due" a winner. That is merely the gambler's fallacy, each event is independent.

Thank you for your analysis. It seems to me I should find another way to counteract botnets...

[markm]

The approach described at http://www.devtome.com/doku.php?id=cpu_mining seems to be working quite nicely so far.

Once ASICs can reliably be obtained it can also be beefed up by taking the subscription fees necessary to discourage account-spamming and to cover basic hosting and bandwidth 9and which due to fierce bidding for accounts has gone way higher than is actually needed to cover the basics) and buying ASICs.

That way people's subscription fees need not directly cover expenses and provide extra rewards but can indirectly invest in securing the SHA256 based, merged blockchains that presumably will be the preferred coin types in which to receive their rewards/profits.

-MarkM-