CPU friendly Altcoin in development

[markm]

Separate securing the network/ledgers/transactions from handing out minted coins.

The securing part should be as low energy as possible, maybe do it like Ripple claims to, if nothing else maybe you'll help discover a flaw in Ripple's proposed method.

For handing out coins, employ people. Rich folk can hire people, true, but at least that creates jobs.

Because really the whole CPU vs GPU vs FPGA vs ASIC is rooted in people, not in hardware at all. It is all about the politics sociology etc of who profits from the hardware, who has easy access to it and such, not about the hardware itself per se.

-MarkM-

[ilostcoins]

I doubt botnet resistance is possible, unless you make it such that normal people can't take part with their PC. You want broader participation for a coin to have better chance of success.

[markm]

I doubt botnet resistance is possible, unless you make it such that normal people can't take part with their PC. You want broader participation for a coin to have better chance of success.

The 1% are only 1%, that is not broad.

Appeal to the starving, the children, the outcaste, make it unappealing to the rich, the well fed, the well-to-do at first, so that its appeal to them ends up coming from how many millions of people they can sell their howerver they got rich well fed etc to by adopting this currency that all those potential customers, who are currently ignored due to having no money, can become customers by means of once they have been given money by this method of giving money only to those who so desperately need it that they are willing to sit down 16 hours a day doing Turing Tests, or whatever...

-MarkM-

[DeathAndTaxes]

From what I heard scrypt miners use the L3 cache of the GPU/CPU, not the RAM. Could it be possible that if enough memory has to be used the performance difference between GPUs and CPUs disappears?
Also, an algo favoring lots of RAM could be interesting, if one exists.

exactly!
I made somewhere point on this forum that there should be coin that uses for example 16GB of RAM so that we cant implement this in gpu ?
Or more likely cant do ASICs hmmmm or meaby not

Anyway coin that would require at least 8GB memory would be nice alternative
Based od AES ? (i7 have hardware acceleration) ?

You wouldn't need 6GB.  The latency on main memory for a GPU is horribly bad so bad that any process which needs random access to GPU main memory will be annihilated by a CPU in terms of performance.  GPU memory is designed to stream textures and as such it couples massive bandwidth with extreme latency.  Scrypt was designed to fill the L3 cache of a CPU.  The developers of alt-coins had to intentionally lower the memory requirements by 99% to make GPU competitive.  Yes Litecoin and clones use about 128KB of cache.  The MINIMUM memory requirement for Scrypt is 12MB.  It doesn't take 16GB.  Try it out yourself or check out various hacking forums the OpenCL performance for Scrypt (2^14, 8, 1) is beyond pathetic.  A cheap CPU will run circles around it.  

Of course this makes it optimal for botnets so maybe a higher memory requirement (say 4GB/8GB) may be an idea so that it requires a relatively high end computer.  Scrypt is configurable you can make the scratchpad as large as you want (even up to TB of space required). It would be trivial for enthusiast to add more memory/disk but I imagine the average botnet node is a relatively weak/older system.  The % which have 4/8GB or more of main memory are probably small.  One could even design the algorithm to become more memory hard over time (i.e. double memory requirement every 2 block years).

[DeathAndTaxes]

The securing part should be as low energy as possible, maybe do it like Ripple claims to, if nothing else maybe you'll help discover a flaw in Ripple's proposed method.

The lowest cost method is a centralized ledger.  That is the PayPal/Ripple/Federal Reserve method.  Securing a blockchain in a decentralized will always involve a cost.  Maybe it won't be an electrical cost, maybe it will be a different kind of cost but a cost is inevitable.

[markm]

The securing part should be as low energy as possible, maybe do it like Ripple claims to, if nothing else maybe you'll help discover a flaw in Ripple's proposed method.

The lowest cost method is a centralized ledger.  That is the PayPal/Ripple/Federal Reserve method.  Securing a blockchain in a decentralized will always involve a cost.  Maybe it won't be an electrical cost, maybe it will be a different kind of cost but a cost is inevitable.

So you're categorising Ripple as a centralised ledger? Maybe a store-and-forward network or other distribution network of a centralised ledger, but in essence a centralised ledger?

I am not disagreeing just seeking clarity.

Where is the line between a centralised ledger and any consensus, once it has been reached?

Cannot one simply consider the aggregate of contributors to the consensus as a centralisation?

Like, if consensus is reached so certainly by ASICs that GPUs etc really cannot sway it, it is really a centralised ledger whose centre lies in the ownership/control of ASICs?

-MarkM-

[ilostcoins]

I doubt botnet resistance is possible, unless you make it such that normal people can't take part with their PC. You want broader participation for a coin to have better chance of success.

The 1% are only 1%, that is not broad.

Appeal to the starving, the children, the outcaste, make it unappealing to the rich, the well fed, the well-to-do at first, so that its appeal to them ends up coming from how many millions of people they can sell their howerver they got rich well fed etc to by adopting this currency that all those potential customers, who are currently ignored due to having no money, can become customers by means of once they have been given money by this method of giving money only to those who so desperately need it that they are willing to sit down 16 hours a day doing Turing Tests, or whatever...

-MarkM-

I said "broader". That's a implicit comparison of 2 scenarios where in one, most PC today can take part, and the other where more specialized hardware is necessary. An advantage of CPU friendly coin would be more people can get decent mining results with the PC they already have, hence more people can take part easily.

Besides, what does "the starving" have to do with this topic?

[mechs]

Some of you like to see an altcoin that is truly GPU,FGPA,ASIC resistant. We would like to see such a coin too so we have started experimenting. We are working on the hashing function right now. It's radix sort based. We use 64 random numbers between 10000 and 75536 (16^4+10k). This 512 char long decimal number is the 'key'. (If we subtract the 10k on each number block and convert it to hex, it's a 256 long hex string in total [or in other words: 1024 bits].) We then change each number block with a specific simple math function and radix sort them by LSD. This gives us a 'hash' (same structure as 'key'). Using a difficulty is already in place. The above explained process for getting a hash out of a key is also depending on the difficulty. The higher the difficulty the more often the hashing has to be done before getting back a hash (simply said). Validating a hash is based on simple math functions depending on the difficulty. The higher the difficulty the less hashes are valid (simply speaking).

I just want to make sure we are on the right track with this.

Possible improvements: I would like to implement tacotime's mentioned tree search algorithm in topic 64239. But it has to be implemented in a way the search is mandatory and that's very hard to do. We may also should use radix sort MSD and LSD instead of LSD only. What do you think?

Do you have any idea what we should change/add to the hashing function?

I think Primecoin looks to be a very CPU friendly coin. 

[DeathAndTaxes]

So you're categorising Ripple as a centralised ledger? Maybe a store-and-forward network or other distribution network of a centralised ledger, but in essence a centralised ledger?

I would call it a distributed centralaised ledger.  This may seem an oxymoron but the point is that there is a redundant network of ripple "servers" (not be be confused with client nodes) however the server source code remains closed source and only OpenCoin or agents of OpenCoin run the servers.

I would liken in to a private content distribution system being distributed but still under centralized control.  The advantages are no need for mining, no need for proof of work.  What the centralized network says is the status of coins is the status with no appeals or overrides.

There is no need for "proof" because all servers are trusted authorities.  They are all run by the same entity and there is no reason or scenario where they will provide conflicting ledgers.   At a high level one could say the purpose of "proof of work/stake/etc" is to resolve conflicts in the consensus.  There will never be conflicts in a distributed centralized network.

[JohnyBigs]

Hence eMunie, it heavily relies on Hard Drives, instead of CPU's and GPU's

[markm]

I doubt botnet resistance is possible, unless you make it such that normal people can't take part with their PC. You want broader participation for a coin to have better chance of success.

The 1% are only 1%, that is not broad.

Appeal to the starving, the children, the outcaste, make it unappealing to the rich, the well fed, the well-to-do at first, so that its appeal to them ends up coming from how many millions of people they can sell their howerver they got rich well fed etc to by adopting this currency that all those potential customers, who are currently ignored due to having no money, can become customers by means of once they have been given money by this method of giving money only to those who so desperately need it that they are willing to sit down 16 hours a day doing Turing Tests, or whatever...

-MarkM-

I said "broader". That's a implicit comparison of 2 scenarios where in one, most PC today can take part, and the other where more specialized hardware is necessary. An advantage of CPU friendly coin would be more people can get decent mining results with the PC they already have, hence more people can take part easily.

Besides, what does "the starving" have to do with this topic?

Because forget a PC, think a smartphone or handheld. Who even has desktop machines anymore other than geeks?

-MarkM-

[markm]

So you're categorising Ripple as a centralised ledger? Maybe a store-and-forward network or other distribution network of a centralised ledger, but in essence a centralised ledger?

I would call it a distributed centralaised ledger.  This may seem an oxymoron but the point is that there is a redundant network of ripple "servers" (not be be confused with client nodes) however the server source code remains closed source and only OpenCoin or agents of OpenCoin run the servers.

I would liken in to a private content distribution system being distributed but still under centralized control.  The advantages are no need for mining, no need for proof of work.  What the centralized network says is the status of coins is the status with no appeals or overrides.

There is no need for "proof" because all servers are trusted authorities.  They are all run by the same entity and there is no reason or scenario where they will provide conflicting ledgers.   At a high level one could say the purpose of "proof of work/stake/etc" is to resolve conflicts in the consensus.  There will never be conflicts in a distributed centralized network.

Oh you are confusing the company-operated network based on the Ripple protocol with the protocol itself.

I was meaning the proposed consensus mechanism, the protocol, not the control-freaks currently reneging in releasing the source code.

If they don't release code that doesn't necessarily mean the actual protocol proposed cannot work, does it? Or is their failure to release the code maybe because the protocol is bullshit, they actually are having to not really do it as described because as described it cannot work, the whitepaper or whatever description of the purported consensus is just smokescreen flim flam or something?

If the approach works, then even if new code has to be written from scratch to implement the approach in free open source form it could be done, right?

So i am not on about some specific proprietary software that implements the protocol but the actual purported protocol...

-MarkM-

[DeathAndTaxes]

If they don't release code that doesn't necessarily mean the actual protocol proposed cannot work, does it? Or is their failure to release the code maybe because the protocol is bullshit, they actually are having to not really do it as described because as described it cannot work, the whitepaper or whatever description of the purported consensus is just smokescreen flim flam or something?

I think the latter.  In looking at the white paper, FAQ, and wiki there are some significant "issues" with their explanation of achieving consensus.  Of course it "might" work but the devil is in the details and being closed source there is no way to expose those details to sunlight.

So it is more like "trust us it works, the magic black box says so" and "at some point in the future which will not be named and may change at our sole decree" we will let untrusted people run servers because it won't be a problem.  If you have doubts see the first quote.

If the approach works, then even if new code has to be written from scratch to implement the approach in free open source form it could be done, right?

Well we don't know it works.  As described I see a lot of potential issues.

Just one example:

What happens if say 33% of the nodes saw transaction A, 33% saw transaction B, and 34% saw transaction C first where all 3 conflict?
Then no transaction will get voted in, and the deterministic algorithm will pick only one which will be a candidate for the next ledger.
How does the deterministic algorithm for including transactions in the ledger work?
Basically it applies transactions in an order designed for maximum efficiency until no new transactions get in. Transactions can pass, hard fail, or soft fail. If they pass, they're included. If they hard fail, they're dropped. if the soft fail, they stay as candidates.
Once a transaction gets in, all that conflict with it will hard fail.
The current algorithm is hash order first, with any soft fails repeated in account/sequence order. When no new transactions succeed in a pass, the operation completes.

Ok so in the event two or more nodes (servers) disagree consensus will be acheived by a deterministic algorithm.  The conflicting transactions will be sorted by hash order and the included in order until tx can't be included due to conflict.

Ok so I am going to send you coins, I generate tx until I make one with a high tx hash.  I then double spend it with a tx to myself that happens to have a low tx hash.  If I can ensure that no consensus is acheived (partial sbyill) attack then the deterministic algorithm will always pick my double spend over your tx

As described this is a massive vulnerability, one sure to be exploited once the server source code is open sourced and anyone can run a server (or 10,000 servers in a botnet). Now maybe the FAQ is just incomplete but since the server source code is closed source nobody can say for sure how weak this is.

https://ripple.com/wiki/Consensus

[eule]

You wouldn't need 6GB.  The latency on main memory for a GPU is horribly bad so bad that any process which needs random access to GPU main memory will be annihilated by a CPU in terms of performance.  GPU memory is designed to stream textures and as such it couples massive bandwidth with extreme latency.  Scrypt was designed to fill the L3 cache of a CPU.  The developers of alt-coins had to intentionally lower the memory requirements by 99% to make GPU competitive.  Yes Litecoin and clones use about 128KB of cache.  The MINIMUM memory requirement for Scrypt is 12MB.  It doesn't take 16GB.  Try it out yourself or check out various hacking forums the OpenCL performance for Scrypt (2^14, 8, 1) is beyond pathetic.  A cheap CPU will run circles around it.

This begs the question: Was this known to the devs of Litecoin and/or Tenebrix? I mean, why else did they intentionally lower the memory requirements? Big scam after all (hurr durr gpu resistant)?

[DeathAndTaxes]

You wouldn't need 6GB.  The latency on main memory for a GPU is horribly bad so bad that any process which needs random access to GPU main memory will be annihilated by a CPU in terms of performance.  GPU memory is designed to stream textures and as such it couples massive bandwidth with extreme latency.  Scrypt was designed to fill the L3 cache of a CPU.  The developers of alt-coins had to intentionally lower the memory requirements by 99% to make GPU competitive.  Yes Litecoin and clones use about 128KB of cache.  The MINIMUM memory requirement for Scrypt is 12MB.  It doesn't take 16GB.  Try it out yourself or check out various hacking forums the OpenCL performance for Scrypt (2^14, 8, 1) is beyond pathetic.  A cheap CPU will run circles around it.

This begs the question: Was this known to the devs of Litecoin and/or Tenebrix? I mean, why else did they intentionally lower the memory requirements? Big scam after all (hurr durr gpu resistant)?

I have never got a satisfactory answer.  I will point out that it is intentional though.  The default parameters for Scrypt are (N=2^14, r=8, p=1), the parameters used by Litecoin are N=2^10, r=1, p=1).

I am not sure if was a scam but the end result is the same, Litecoin is 99% less memory hard then the default Scrypt and about 1/7000th as memory hard as the parameters recommended by the author for high security (not realtime) applications.

[markm]

Just one example:

What happens if say 33% of the nodes saw transaction A, 33% saw transaction B, and 34% saw transaction C first where all 3 conflict?
Then no transaction will get voted in, and the deterministic algorithm will pick only one which will be a candidate for the next ledger.
How does the deterministic algorithm for including transactions in the ledger work?
Basically it applies transactions in an order designed for maximum efficiency until no new transactions get in. Transactions can pass, hard fail, or soft fail. If they pass, they're included. If they hard fail, they're dropped. if the soft fail, they stay as candidates.
Once a transaction gets in, all that conflict with it will hard fail.
The current algorithm is hash order first, with any soft fails repeated in account/sequence order. When no new transactions succeed in a pass, the operation completes.

Ok so in the event two or more nodes (servers) disagree consensus will be acheived by a deterministic algorithm.  The conflicting transactions will be sorted by hash order and the included in order until tx can't be included due to conflict.

Ok so I am going to send you coins, I generate tx until I make one with a high tx hash.  I then double spend it with a tx to myself that happens to have a low tx hash.  If I can ensure that no consensus is acheived (partial sbyill) attack then the deterministic algorithm will always pick my double spend over your tx

As described this is a massive vulnerability, one sure to be exploited once the server source code is open sourced and anyone can run a server (or 10,000 servers in a botnet). Now maybe the FAQ is just incomplete but since the server source code is closed source nobody can say for sure how weak this is.

https://ripple.com/wiki/Consensus

You are reading it, or reading into it, differently than I am.

Specifically, you do not mention what I had thought was fundamental: that if two disagree neither of them get in, because only consensus gets in.

You seem to assume being earlier in the queue, whether by high hash or other ordering / collating sequence, gets you in.

In my concept of the protocol, that only lets you not get disqualified yet; once a conflicting item does get looked at, boom, you and it both get disqualified as not being in consensus with each other.

So if the processing can catch up to the whole queue, it is left with all current items that do not conflict with each other and a bunch of chaff consisting of items that conflict either with history (already done-deal blocks / timeslices) or with other items currently up for consideration.

So to get in ahead of an item that contradicts your item you have to get the processing node to strike either your node or the node that sent the item that conflicts with yours from its trusted nodes list. it comes down to one of those two nodes is lying or if both items arrived from the same node than that node not winnowing out the chaff itself before passing items to me.

Until my user tells me which node to trust over the other node, i have to assume both nodes are compromised or they are not both in the same actual network of trust.

So unless my user specifically tells me to always trust the beagle boys, or at least to always believe them over scrooge mcduck, I have to just figure both have some problem in that they seem unable to reach consensus with each other...

As for 10,000 server botnets, if I have told my node that both the beagle boys and scrooge mcduck being in consensus is a significant consensus, but I have never even admitted to my node that I know any of these 10,000 bots, they only count at all if they can convince both the beagle boys and uncle scrooge of their version of reality...

-MarkM-

[FreeTrade]

Why not use Scrypt as intended.  Scrypt with default variables has beyond horrible performance on GPUs.  Litecoin developers modified it to make it roughly 128x less memory resistant (using only 128KB total).

I'm working on this too and the problem I'm anticipating is that it will take time to verify the hash. The performance I'm seeing running scrypt to require 256MB of memory is a hash time of at least 0.5 seconds . . . . time increasing linearly with memory required . . that's not so bad for mining where you can just have a low difficulty, but creates a problem for clients verifying the block chain - it makes it a slower process, and could start to bite as the block chain gets longer.

[FreeTrade]

Do you have any idea what we should change/add to the hashing function?

I'm working on this same problem, and I think you're taking a viable approach. You might want to hash on the way into your function and on the way out so you don't need to worry about cryptography and focus on making a GPU resistant algorithm.

Hash = SHA256(MAKEWORK(SHA256(Block)))

Where MAKEWORK is your GPU resistant algorithm.

[FreeTrade]

You wouldn't need 6GB.  The latency on main memory for a GPU is horribly bad so bad that any process which needs random access to GPU main memory will be annihilated by a CPU in terms of performance.  GPU memory is designed to stream textures and as such it couples massive bandwidth with extreme latency.  Scrypt was designed to fill the L3 cache of a CPU.  The developers of alt-coins had to intentionally lower the memory requirements by 99% to make GPU competitive.  Yes Litecoin and clones use about 128KB of cache.  The MINIMUM memory requirement for Scrypt is 12MB.  It doesn't take 16GB.  Try it out yourself or check out various hacking forums the OpenCL performance for Scrypt (2^14, 8, 1) is beyond pathetic.  A cheap CPU will run circles around it.  

Some interesting stats here -
https://github.com/floodyberry/scrypt-jane

If I'm reading these correctly, they confirm my tests that it takes about 2 seconds per hash per GB memory required on a modern processor.

Interested to know what you think would be a good memory requirement/time tradeoff to resist GPUs but maintain a good block validation time.

One could even design the algorithm to become more memory hard over time (i.e. double memory requirement every 2 block years).

Yacoin? Nfactor started a little low though.

[msweb]

FreeTrade: Thanks for your input and it's nice to see other people working on that too. We may should exchange our results. I like to do the programming very low level for that purpose. While assembler is a little bit too freaky and time intense to code with, we are doing it on very low leveled c. P.e.: We don't use any strings at all yet and just std math operations besides the radix sort. Your mentioned SHA hashing doesn't make sense within the proof of work algorithm itself in my eyes. The created algo has to be as good as the well known hashing operations in terms of irreversibility and unique hashes anyway and then nothing else is needed around it. I think our current mechanism is already very good in terms of that.