Given L=42 in the cuckoo cycle problem with N < 2^32, if a graph G contains an L-cycle, a random sample of x% of the edges in the graph will contain at least two edges in that L-cycle with probability > 999,999 / 1,000,000. Math edit: Replaced 10% with x% -- there is some x for which this is true.  You can go check the math yourself - it's just a binomial with p=x%. You need about 33% for 1 in a million odds of less than 2 L-cycle edges in your sample. Does this mean anything? I don't know -- but it tells me *immediately* that the problem requires a different kind of analysis than what you would do for Momentum! For example, what if you started by sampling lg(n) edges and then growing and pruning that set through 42 rounds? With some reasonable probability, you'd extend into one of the cycles. Not guaranteed, but it doesn't have to be guaranteed - I can always start over.
To have 50% odds of at least one L-cycle edge, you need to sample about 1.5% log(n) doesn't cut it. Not at all. The primes have an entirely different goal. The point is that you're advertising cuckoo cycle as having a certain set of desirable properties. Someone shopping for a PoW wants a certain set of properties - some people want the social/scientific good of primes.
So you're saying I mismarketed Cuckoo Cycle. I could have said. Let's have a PoW based not on number-theoretical, but on graph-theoretical structures. Existence of a certain small-size subgraph in a large random graph makes for an easily verifiable PoW. We could look for cliques, or for ... cycles! Then you'd be fine with it?! Yes. It's non-trivial to "store this bit vector in a compact way" but it can be done. See the SDSL link I provided, for example.
In the first round of full U and V trimming, you pass through a state of the bit vector having about half 0s and half 1s. At that point it's completely incompressible. Even with a 10% vs 90% distribution (that takes at least 2 full rounds to reach) it may be too impractical to compress. |
|
|
|
Given L=42 in the cuckoo cycle problem with N < 2^32, if a graph G contains an L-cycle, a random sample of x% of the edges in the graph will contain at least two edges in that L-cycle with probability > 999,999 / 1,000,000. Math edit: Replaced 10% with x% -- there is some x for which this is true. You can go check the math yourself - it's just a binomial with p=x%. You need about 33% for 1 in a million odds of less than 2 L-cycle edges in your sample. Does this mean anything? I don't know -- but it tells me *immediately* that the problem requires a different kind of analysis than what you would do for Momentum! For example, what if you started by sampling lg(n) edges and then growing and pruning that set through 42 rounds? With some reasonable probability, you'd extend into one of the cycles. Not guaranteed, but it doesn't have to be guaranteed - I can always start over.
To have 50% odds of at least one L-cycle edge, you need to sample about 1.5% log(n) doesn't cut it. Not at all. The primes have an entirely different goal. The point is that you're advertising cuckoo cycle as having a certain set of desirable properties. Someone shopping for a PoW wants a certain set of properties - some people want the social/scientific good of primes.
So you're saying I mismarketed Cuckoo Cycle. I could have said. Let's have a PoW based not on number-theoretical, but on graph-theoretical structures. Existence of a certain small-size subgraph in a large random graph makes for an easily verifiable PoW. We could look for cliques, or for ... cycles! Then you'd be fine with it?! Yes. It's non-trivial to "store this bit vector in a compact way" but it can be done. See the SDSL link I provided, for example.
In the first round of full U and V trimming, you pass through a state of the bit vector having about half 0s and half 1s. At that point it's completely incompressible. Even with a 10% vs 90% distribution (that takes at least 2 full rounds to reach) it would be practically infeasible to compress. |
|
|
|
Neither of us knows the answer to this question. There is a chance that it's stronger. But there's also a very real chance that the requirement to find a cycle, instead of a simple collision, will mean that the approach can yield to something with sublinear memory requirements and, in fact, underperform compared to Momentum in its memory requirements.
We know finding two incident edges in a graph is (way) easier than finding a 42-cycle. So I don't know what you mean by underperform. Sure, but again: The best way to design a strong algorithm in a security context is not to generate ideas until you find one you cannot disprove. It's to start from things that are known to be hard and to base the security of your algorithm upon the hardness of those things.
I feel that unnecessarily limits the PoW landscape. And could have left prime-based PoWs out in the cold as well. I've already told you how to modify the algorithm I explained to use 1/2 bit per nonce with a 4x slowdown. The idea generalizes to using 1/k memory for a > k^2 slowdown. This is a good tradeoff, but it's not the be-all-end-all.
Are you referring to this paragraph of your blog? "(There is a way to slightly reduce the memory demands: Split the bit vector in half, and record the live bits only for the first half across multiple iterations of the test, using the full second half. Then store this bit vector in a compact way, and perform the computation on the second half. This doesn't extend very far past a factor of two reduction, but it does require only a roughly linear increase in the amount of computation and could possibly get the storage needed down to about 300MB for 2^32.)" |
|
|
|
But, more generally: I think it's great that you've put the proposal document out publicly for comment before it's adopted. That's the right place to start. But I think it should be taken one step farther. Consider the approach Colin Percival used in developing scrypt: A PoW for serious consideration in a cryptocurrency needs a stronger proof of hardness. I don't put things like Riecoin and Primecoin in this batch, because their goal is social good more than a particular technical goal of memory use"
Cuckoo Cycle is no less safe to deploy than either prime-based or hash-cash proofs-of-work. It needs a minimum amount of work, namely computing millions of siphashes. Dynamic difficulty adjustment will take care of as-yet-undiscovered optimizations to the current (and new) algorithm. It's true I haven't done anywhere near as thorough a job as Colin. My hat off to him. My notion of tmto-hardness is stronger than his though. I aim to require a barrier that polynomial trade-offs can not cross (but phrased in concrete terms rather than quantified formulas and big-Oh notations). The least I can do is encourage the search for a disproof. As the current README shows: "Cuckoo Cycle remains tmto-hard assuming at least one bit per nonce is required. I offer a $1000 bounty for an implementation using less, with at most 100x slowdown." I know, that's a very modest sum. And much less than was offered for Momentum. But then I've seen what happened with that one... PS: concerning social good. I'd love for a "research coin" to come out that can serve as a laboratory for new ideas, maybe one running only on testnet. It could perhaps be based on NXT source code, with a PoS/PoW hybrid instead of pure PoS, and Myriad's support for multiple PoW algorithms... |
|
|
|
Isn't Primechain/Primecoin the only hashing algorithm that GPU is no faster than CPU with current software?
The jury is still out on Cuckoo Cycle, as little effort has been put into GPU implementations. A direct port of the current latency-bounded CPU implementation performs much worse than the CPU one, but that's not saying much... Cuckoo Cycle isn't used by and coins yet, is it? Nope:-( |
|
|
|
Isn't Primechain/Primecoin the only hashing algorithm that GPU is no faster than CPU with current software?
The jury is still out on Cuckoo Cycle, as little effort has been put into GPU implementations. A direct GPU port of the current latency-bounded CPU implementation performs much worse than the CPU one, but that's not saying much... |
|
|
|
Isn't Primechain/Primecoin the only hashing algorithm that GPU is no faster than CPU with current software?
The jury is still out on Cuckoo Cycle, as little effort has been put into GPU implementations. A direct port of the current latency-bounded CPU implementation performs much worse than the CPU one, but that's not saying much... |
|
|
|
But, more generally: I think it's great that you've put the proposal document out publicly for comment before it's adopted. That's the right place to start. But I think it should be taken one step farther. Consider the approach Colin Percival used in developing scrypt: A PoW for serious consideration in a cryptocurrency needs a stronger proof of hardness. I don't put things like Riecoin and Primecoin in this batch, because their goal is social good more than a particular technical goal of memory use, but the care that went into scrypt's theoretical evaluation is worth modeling. I think there are some very serious approaches that might keep time linear or sublinear and reduce memory to sublinear -- but whether or not one person can think of an attack is not the right approach for determining whether the idea is resistant to attack.
Additionally, the designer (me in this case) is probably in a bad position to find attacks because they want the neat algorithm with nice properties that they found to be the optimal one, and this wishful thinking clouds their mind... Back to the drawing board... |
|
|
|
Dave has shown my algorithm is not as tmto-hard as I thought it was. Excellent work, Dave! For now, I amended my README at https://github.com/tromp/cuckoo with the following UPDATE: Dave Anderson proposed an alternative algorithm on his blog http://da-data.blogspot.com/2014/03/a-public-review-of-cuckoo-cycle.htmlthat uses significantly less memory than mine at potentially less than an order of magnitude slowdown. I hope to soon implement his algorithm and quantify the "tomato" (his pronouncable spelling of tmto, or time-memory trade-off). |
|
|
|
The beefiest GPU card only has 6GB of memory.
Your typical botnet computer has less than 4GB of free memory.
A proof-of-work that requires more than 6GB of memory is
automatically gpu-proof and botnet-resistant.
Strangely, no coin has adopted such a proof-of-work...
Lol, that would be stupid, it would keep out the people that want to CPU mine in the first place... I have a nice desktop with 32GB of memory. I'd certainly like to mine something that takes 7GB and uses very little power. Even a machine with 8GB that boots into a tiny OS can run a 7GB proof-of-work. 16GB of memory only costs about $100 - $150. The only people I'm keeping out are those with mediocre PCs or those that don't want to make any investment to be able to mine... |
|
|
|
Protoshares and Memorycoin(2) run very memory intensive hash algorithms for every cpu thread running on the wallet qt miner it was suggested to have 1 gb RAM. I believe the OP is looking for something that would be mineable for an average computer that could not be taken advantage of by botnets, and which would take a long time for a gpu miner to be created. Or be disadvantageous to run a gpu to mine.
(also i know asics memory is on die, im saying it would be a neat feature if a future scrypt n miner was able to put in better memory as needed)
I already proposed a Proof-of-Work that satisfies the above requirements, over 2 months ago. It's called Cuckoo Cycle. You can find a whitepaper and implementation at https://github.com/tromp/cuckoo |
|
|
|
Oh yeah, right, they ended up aiming to max the memory bandwidth as the bottleneck and allow both CPUs and GPUs to participate.
How is it though that ordinary folk who have machines with more than 6 gigs of RAM resist becoming botnet zombie machines?
Who is intended to mine this thing? Don't gamers have typically at least 8 gigs of RAM? Are gamers resistant to having their machines captured by botnets?
-MarkM-
Plenty of machines with 6-8GB fall victim to botnets. But generally speaking, the more powerful your desktop, the more you will look after its well-being. Assume a Proof-of-Work requires 7GB with constant random memory accesses. Unless you have strictly more than 8GB, and 7GB freely available, this will send your computer into swap-hell as it constantly swaps pages to disk and back (1GB is usually reserved for the OS and other basic stuff). This will make your computer not just very slow, but totally unusable. You will take notice and find the offender. Especially if you're a gamer... |
|
|
|
|
The beefiest GPU card only has 6GB of memory.
Your typical botnet computer has less than 4GB of free memory.
A proof-of-work that requires more than 6GB of memory is
automatically gpu-proof and botnet-resistant.
Strangely, no coin has adopted such a proof-of-work...
|
|
|
|
I don't think any coin so far is ASIC resistant.
There are several, like Primecoin and Riecoin. And my Cuckoo Cycle proof-of-work, which is not used by any coin. |
|
|
|
Hirocoin claims to be GPU coin....  Hirocoin and Darkcoin use the X11 algorithm. X11 does not give GPUs a huge advantage over CPUs. All these 11 hash functions have efficient circuit implementation as a design criterion. So they're all very ASIC friendly, just like SHA256. If the GPU implementation doesn't have a huge advantage over CPUs, it can only be due to lack of proper optimization. This is all the "X11 whitepaper" has to say about X11: Darkcoin uses a new chained hashing algorithm approach, with many new scientific hashing algorithms for the proofofwork. X11 consists of blake, bmw, groestl, jh, keccak, skein, luffa, cubehash, shavite, simd, and echo. Because it is more complicated than a SHA256 ASIC implementation, the use of X11 will prevent the use of ASIC miners for the short-term to midterm future. It will also allow for a longer period of mining for CPU/GPU users. GPU miners that mine with the X11 algorithm are currently experiencing reduced power usage (up to 50%) and reduced heat generation compared to scrypt. |
|
|
|
I mean, with all the bitcoincloneshitcoins out there why hasn't anyone considered to copy paste the revolutionary design of NXT and try to find a way to avoid too much centralization of coins?
Nxt is less centralized than Bitcoin or Dollar https://i.imgur.com/PbzxwIy.pngThere are also a few bugs deliberately placed in the Nxt source code. There is some sort of prize for guessing them before they are revealed around easter time. Any cloners need to find them and fix them. The third and last flaw (possibility to "mine" for being the next forger) was identified just days ago... |
|
|
|
The Scrypt ASIC arms race has started. Those with GPUs will want to either sell their GPUs or more likely look for another coin to mine.
But which is the best coin to mine and hold for the long-term, whilst also helping out on lower electricity costs?
This is for Proof of Work only.
Did I miss any you think should be on the list? Let me know.
The most energy efficient PoW for a GPU is one that saturates the memory with random accesses, and minimizes energy-wasting computation, hence none of the above. |
|
|
|
oha,you are too old.
there have over 20copies ,you can find them youself.
as nem, nex ,nxtl,nas,ndc,ifc,......so many
But none with PoW added on, or replacing PoS? |
|
|
|
take a look at x11 coins, hirocoin in particular. insanely asic hostile
More like "insane to think it's asic hostile":-) 11 hash functions that are each by design very asic friendly... |
|
|
|
Which of the 11 hash functions in X11 do you suppose is ASIC resistant?
If you can make an ASIC for each of the 11 hash functions, then you can trivially make an ASIC to do all of them at the same time...
X11 is also easily targeted by FPGAs, which will significantly outperform GPUs. Let's instead consider the resistance of my Cuckoo Cycle proof-of-work ( https://github.com/tromp/cuckoo): An ASIC for something like cuckoo728 (graph size 7x2^{28} ), which requires 7GB for a single instance, could not be self contained. It would be like a vastly simplified CPU with perhaps 1024 cores, that runs 32 instances of cuckoo728 at once, each one running with 32 threads. It would have to be connected to 32x7GB, or nearly 256GB of memory, which would totally dominate the cost. Intel is already planning to introduce cpus with hundreds of cores, so such an ASIC would not offer enough performance advantage to justify its development cost. Similarly, no current GPU card has enough memory to run cuckoo728, and future ones with twice the memory of the current max (6GB) would only be able to run a single instance (the algorithm doesn't allow a time-memory trade-of). Even that may not be competitive with a CPU, which has much better memory latencies. The vastly superior memory bandwidth of a GPU is mostly wasted on Cuckoo Cycle, which makes completely random accesses. Another problem with GPUs is that they cannot deal well with data dependent code flow, which features prominently in Cuckoo Cycle. |
|
|
|
|
Show Posts
