In that post I showed a comparison between the reference and tmto implementation at memory parity, which showed a factor 70 slowdown and a factor 1-1/e reduced solution finding rate (due to sampling a fraction 1/42 of all vertices as starting points for the depth 21 breadth first search).
Discounting for the lower solution finding rate, the tmto implementation was 111 times slower.
I tried another approach, which turns out to be superior. First of all, assume that the graph we're working on has a unique 42 cycle, and we hope to find it by sampling a small fraction of nodes, and exploring their local neighbourhood with a depth-limited breadth-first-search (BFS). Instead of doing a depth 21 BFS , which (roughly) requires starting from a node on the 42-cycle, we can do a much deeper search, say depth 42. Then we'll find the 42-cycle as long as we start from any node with distance at most 21 to the 42-cycle, which seems much more likely. Apart from doubling the BFS depth, there is another difference. In the former approach, we only care about nodes on the cycle, and can eliminate any that are known to be off the cycle, such as those with only one incident edge. In the latter approach, we cannot eliminate these. So the BFS tree will be much larger in size relative to the starting set, not only due to doubled depth, but to less elimination as well. To keep space usage down, we thus need to shrink the starting sets even more. I ran some experiments which indicate that the increased likelihood of finding the cycle more than makes up for having smaller starting sets. The updated tomato_miner.h can now use k times less memory with a (discounted) slowdown of roughly 25*k. Further details will appear in the whitepaper, in a week or two. With this progress on the time-memory trade-off, the partial bounty payout, and the relaxation of the slowdown, I'm reducing the TMTO bounty from $1000 to $500. |
|
|
|
This miner will be available as tomato_miner.h / tomato_miner.cpp
I will experiment with this some more before updating the TMTO bounty...
Weird, the post I was quoting has disappeared entirely. In that post I showed a comparison between the reference and tmto implementation at memory parity, which showed a factor 70 slowdown and a factor 1-1/e reduced solution finding rate (due to sampling a fraction 1/42 of all vertices as starting points for the depth 21 breadth first search). Discounting for the lower solution finding rate, the tmto implementation was 111 times slower. For completeness, I include below the output of the reference implementation running on 2 threads, showing a factor 61 difference (rather than the 70 single threaded). -John > time ./cuckoo25.1 -t 2 -h 157
Looking for 42-cycle on cuckoo25("157") with 50% edges, 11 trims, 2 threads
Using 2MB edge and 2MB node memory.
initial load 6400%
round 1 part U0 load 5222%
round 1 part U1 load 4045%
round 1 part V0 load 2970%
round 1 part V1 load 1895%
round 2 part U0 load 1508%
round 2 part U1 load 1121%
round 2 part V0 load 934%
round 2 part V1 load 746%
round 3 part U0 load 641%
round 3 part U1 load 535%
round 3 part V0 load 469%
round 3 part V1 load 403%
round 4 part U0 load 359%
round 4 part U1 load 315%
round 4 part V0 load 284%
round 4 part V1 load 253%
round 5 part U0 load 230%
round 5 part U1 load 208%
round 5 part V0 load 191%
round 5 part V1 load 174%
round 6 part U0 load 161%
round 6 part U1 load 147%
round 6 part V0 load 137%
round 6 part V1 load 127%
round 7 part U0 load 118%
round 7 part U1 load 110%
round 7 part V0 load 103%
round 7 part V1 load 96%
round 8 part U0 load 91%
round 8 part U1 load 85%
round 8 part V0 load 80%
round 8 part V1 load 76%
round 9 part U0 load 72%
round 9 part U1 load 68%
round 9 part V0 load 64%
round 9 part V1 load 61%
round 10 part U0 load 58%
round 10 part U1 load 55%
round 10 part V0 load 53%
round 10 part V1 load 50%
round 11 part U0 load 48%
round 11 part U1 load 46%
round 11 part V0 load 44%
round 11 part V1 load 42%
4-cycle found at 1:90%
166-cycle found at 0:98%
42-cycle found at 1:98%
76-cycle found at 1:99%
Solution 223e7 56b1b 86b2f cb0a2 106629 233b7e 253ee1 290e4e 2e15cc 2efe4b 32bc8e 356dfd 35ef96 3dd854 534d37 57ee85 5abaa1 5d7d49 60ca66 662933 718651 78554b 7d8e01 7f7360 886c55 8a6448 8e4fd2 9674a2 98e431 b00d71 b16050 b1b561 b362d4 b9e539 ca3ab0 cb4f28 d2a53b d53bc3 e213cc e40bf1 ed5b2a faef36
real 0m6.957s
user 0m10.709s
sys 0m0.077s
|
|
|
|
This miner will be available as tomato_miner.h / tomato_miner.cpp
I will experiment with this some more before updating the TMTO bounty...
The tomato miner is now up, and bounty miner is restored as a copy of cuckoo miner. The TMTO bounty in the OP has been updated, allowing an extra factor 10 of slowdown. Below is the slightly improved output of the tomato miner, shown running almost twice as fast by using 2 threads. Happy continued bounty hunting! -John > time ./tomato25 -t 2 -h 157
Looking for 42-cycle on cuckoo25("157") with 50% edges, 1/64 memory, 24/512 parts, 2 threads
Using 4MB node memory.
vpart 0 depth 21 load 78%
4-cycle found at 1:5
4-cycle found at 1:6
4-cycle found at 1:7
4-cycle found at 1:8
4-cycle found at 1:9
4-cycle found at 1:10
4-cycle found at 1:11
4-cycle found at 1:12
4-cycle found at 1:13
4-cycle found at 1:14
4-cycle found at 1:15
4-cycle found at 1:16
4-cycle found at 1:17
4-cycle found at 1:18
4-cycle found at 1:19
4-cycle found at 1:20
vpart 1 depth 21 load 78%
vpart 2 depth 21 load 78%
vpart 3 depth 21 load 75%
vpart 4 depth 21 load 77%
vpart 5 depth 21 load 76%
vpart 6 depth 21 load 78%
vpart 7 depth 21 load 76%
vpart 8 depth 21 load 77%
vpart 9 depth 21 load 79%
vpart 10 depth 21 load 78%
vpart 11 depth 21 load 76%
vpart 12 depth 21 load 76%
vpart 13 depth 21 load 77%
vpart 14 depth 21 load 76%
vpart 15 depth 21 load 78%
vpart 16 depth 21 load 78%
vpart 17 depth 21 load 78%
vpart 18 depth 21 load 78%
vpart 19 depth 21 load 75%
vpart 20 depth 21 load 77%
vpart 21 depth 21 load 75%
vpart 22 depth 21 load 76%
42-cycle found at 1:20
vpart 23 depth 21 load 79%
Solution 223e7 56b1b 86b2f cb0a2 106629 233b7e 253ee1 290e4e 2e15cc 2efe4b 32bc8e 356dfd 35ef96 3dd854 534d37 57ee85 5abaa1 5d7d49 60ca66 662933 718651 78554b 7d8e01 7f7360 886c55 8a6448 8e4fd2 9674a2 98e431 b00d71 b16050 b1b561 b362d4 b9e539 ca3ab0 cb4f28 d2a53b d53bc3 e213cc e40bf1 ed5b2a faef36
real 7m5.287s
user 12m27.616s
sys 0m2.345s
|
|
|
|
Set up mining rigs in Vegas. 25 cents gets you 2kWh and a certain number of hashes. Keep popping quarters 'til you get a block. When you win, nothing comes out, cause it's virtual.
Would be nice to have a paper wallet popping out... |
|
|
|
Thinking that the average person is ever going to be able to profitably mine a CPU only coin seems like wishful thinking.
People like to play in lotteries... |
|
|
|
You are reading it wrong, modern dual/quad core ARM chips would mine with comparable mining power to ordinary botnet node, considering that they will mine while phone is absolutely idle (night) they may even be on par with desktop computers which have to do something else while they mine.
Botnet mining also needs to remain stealthy and fly under the radar. Memory intensive PoWs are particularly troublesome because you cannot easily throttle RAM usage like you can CPU usage. Users are very likely to notice when you accidentally send their machine into swap-hell... |
|
|
|
Or have an emission curve with a slow, flat initial period before ramping up to real.
Imagine if XMR's curve had looked like:
days 0-30: 1 xmr/block
days 31-90: 1 + 16 * (day-30)/60) xmr/block
days 91 onwards: using the existing XMR mechanism
I agree wholeheartedly. Except the reward should converge to something nonzero. With some small percentage of coins inevitably getting lost every year, perpetual debasement serves long-term security while avoiding deflation. |
|
|
|
What are the opinions on cloak here?
They have a pretty nice logo... |
|
|
|
A close-friend and work colleague of mine are in preparation stages of developing a new coin. The purpose of the coin will be to spend within snow sports merchandise and eventually holidays.
I think you need a little more focus. Snow Sports is too big a market. How about a coin for purchasing extra-large non-fat latte's at ski-lodges? |
|
|
|
For each level of the breadth, use one O(N) pass through the entire edge set by generating the edges and matching them against the leading edge nodes in the BFS tree.
This description alone is effective for edge trimming, but building on this for directly detecting 42-cycles requires more careful specification of how to handle the BFS graph representation and what to do about cycles in it.
Hmm, seems we were overlooking the obvious. You can just feed all the edges generated in each pass (having one endpoint already present in subset P or as a key in cuckoo_hash) to my cycle finder (lines 357-390 of cuckoo_miner.h, tweaked to ignore duplicates/2-cycles). It doesn't care where the edges come from or how they are located between successive D_i layers. It will even happily report cycles that bounce back and forth multiple times between layers. This should be relatively easy to code... Having a rough version done, it looks like the slowdown for saving a factor k in memory is roughly k times L, where L is cycle length. So, to use only half the memory of the edge-trimming implementation causes two orders of magnitude slowdown. If this is the best one can do, then Cuckoo Cycle is still memory-hard in a practical sense, with cycle-length becoming a memory-hardness parameter. I'll have more detailed numbers after fine-tuning the implementation... |
|
|
|
But I was trying to re-introduce the higher-level issue that, while the graph is random, a solver always has two options: continue working on the current graph or throw it away and try a new one.
Indeed. And this could very well be taken to the extreme with the cuckoo tmto you identified; when looking at vertex subsets of size N/k, only look at the first one, and skip all the k-1 others, since they will have less chance (even if ever so slightly, due to partial overlap) of producing a solution. The only cost to switching to the next graph is one sha256 to compute a new siphash key... |
|
|
|
AFAIK the probability of there being a k-cycle in a bipartite undirected G(n,p) graph, where k > 3 has not been proven, so we don't have a strong basis to judge the bounds of an ideal solution for Cuckoo Cycle. This is were I would love to be proven wrong, as it would lay to rest the possibility of there being unknown backdoors in Cuckoo Cycle.
By backdoor, do you mean time-memory trade-offs? These do not depend in any way on the exact value of the probability of the Cuckoo graph having a k-cycle. The whitepaper already has numerical approximations for those probabilities, which suffice for any run-time or memory-use analysis... I share some of optimiz3's concerns. Let me give an incorrect hypothetical example: I think you're misreading my answer. I was telling optimiz3 that it doesn't matter whether the probability is 2.4% or 2.6%, so he should not require me to prove some exact closed form expression for the probability and just accept my numerical approximations as being good enough for analyzing resource usage. As to your hypothetical graph-statistics filter, that is not something I worry about in the least:-( |
|
|
|
For each level of the breadth, use one O(N) pass through the entire edge set by generating the edges and matching them against the leading edge nodes in the BFS tree.
This description alone is effective for edge trimming, but building on this for directly detecting 42-cycles requires more careful specification of how to handle the BFS graph representation and what to do about cycles in it.
Hmm, seems we were overlooking the obvious. You can just feed all the edges generated in each pass (having one endpoint already present in subset P or as a key in cuckoo_hash) to my cycle finder (lines 357-390 of cuckoo_miner.h, tweaked to ignore duplicates/2-cycles). It doesn't care where the edges come from or how they are located between successive D_i layers. It will even happily report cycles that bounce back and forth multiple times between layers. This should be relatively easy to code... |
|
|
|
This description alone is effective for edge trimming, but building on this for directly detecting 42-cycles requires more careful specification of how to handle the BFS graph representation and what to do about cycles in it.
Indeed. I checked that the Yuster/Zwick paper doesn't add anything relevant for us over the Monien paper (it extends results for dense graphs), so I'm studying Monien's "how to find long paths efficiently" paper now... btw - I wasn't actually clear on the definition of the CC PoW in one way: Is a valid proof any sequence of unique edges that form a cycle, or must the cycles be completely node-disjoint as well?
As the OP mentions, the verification checks that each node is incident to exactly two edges, so yes, the cycle must be node disjoint. |
|
|
|
Thanks, Dave. I appreciate the quick release. Will start going over it tonight.
You're on to something here! In fact, l think you may be able to avoid the original union-find like algorithm, and try to recognize 42 cycles starting from any D21 set. If a node in D21 has 2 or more neighbours in D20, then you can work your way back and try to find disjoint paths back to the same starting node in P. (it suffices to check disjointness within each Di) This approach sounds pretty similar to what Monien and Yuster/Zwick were doing, so I'm going to have to go back and study those papers in detail. Some more notes: If you have for instance |P| = N/1000, then it's not wise to try all 1000 subsets P. If there is a 42 cycle then you have a good chance of having one of its nodes in one of the first 100 subsets. It's going to be interesting to analyze whether a bunch of ASICs implementing this approach is going to outperform the reference implementation on an FPGA plus a few hundreds DRAM chips, taking into account both fabrication costs and power usage of all components involved. I remain hopeful that the constant factor overhead of this TMTO may preserve CC's ASIC resistance. |
|
|
|
http://www.cs.cmu.edu/~dga/crypto/cuckoo/analysis.pdfVery hackish proof-of-concept: http://www.cs.cmu.edu/~dga/crypto/partitioned.jlI'm releasing this well in advance of what I would normally do for academic work because I think it's worth pushing the discussion of proof-of-work functions forward fast -- crypto moves too fast these days -- but please be aware that it's not done yet and requires a lot more polish. The bottom line is as I suggested above: It successfully TMTO's but still requires something like 1-3% of the "full" graph space, because that's what gets passed to the solver after edge trimming. I don't think this is the final word in optimizing for cuckoo cycle -- I believe there are some further nifty optimizations possible, though I think this gets the first primary attack vector down. John, I'd love your feedback on whether this is clear and/or needs help, or if you find some of the handwavy O(N) parts too vague to constitute a real threat. I plan to clean it up more, but, as noted, I figured that it's better to swallow my perfectionism and push the crappy version out there faster to get the dialogue rolling, since I don't have coauthors on it to push it in the right direction.  Feedback appreciated! Thanks, Dave. I appreciate the quick release. Will start going over it tonight. |
|
|
|
- Using the equivalent of 7 iterations of edge trimming
- N= 2^28, E=2^27
- Using k=sqrt(N), requiring roughly 2^14 *words* of memory (so sqrt(N) * log(N))
- Processes in O(2^28 * 2^14) steps
- Reduces the graph down to about 2.5% of its original size. <-- requires 0.025N\logN words to represent, of course...
The current code already trims the edges down to about 1.6%, in order to allow the cycle finding to run in the same memory footprint as the edge trimming. To run the cycle finding in only 2^14 words, you'd have to trim WAY more?! The way in which it's not a perfectly linear TMTO is that I have to go to a word representation of the graph, not the bitvector I introduced earlier. It's a little more nuanced than that, but this is the core.
That would make the situation very similar to that of Momentum, where the linear TMTO applies to the original implementatoin using N=2^26 words, but not to your trimming version using N+2N/k bits (assuming it recomputes SHA hashes instead of storing them). I'll write the whole thing up, share my PoC source code, and if you feel like throwing me some of the bounty, cool.
For a linear TMTO of my original non-trimming Cuckoo Cycle implementation I will offer a $666 bounty. ... wish there were some venue to publish this stuff in. You could do as I did and publish on the Cryptology ePrint Archive. That's good for exposure, but, lacking peer-review, not so good for academic merit:-( |
|
|
|
I'd be happy to generalize the bounty as follows:
$1000/E for an open source implementation that uses at most N/k bits
while running up to 1.5*k^E times slower, for any k>=2 and E>=1.
Or is that still too strict for your taste?
Yes, but N/k bits with an O(k log N) slowdown. Proof-of-concept implementation with no mind at all paid to efficiency, but showing clearly the attack vector and its resulting complexity. In other words - close to linear, but not quite. I see. That would indeed be very interesting, even if not a practical attack. But to be precise, is there a dependence on k in the hidden constant? Can you set k equal to log(N), or sqrt(N)? |
|
|
|
Would you consider extending the applicability of your time/memory tradeoff bounty to a theoretical improvement to the asymptotic bounds for the time-memory tradeoff, with a low-speed demonstrator, but not an insanely tuned implementation, proving the feasibility of a sub-quadratic TMTO (but superlinear - i'm guessing some extra log(n) factor) for the edge pruning component of Cuckoo Cycle?
Are you asking for a bounty for using N/k bits and an o(k^2) slowdown? The problem with asymptotic running times is that they're hard to verify:-( I'd be happy to generalize the bounty as follows: $1000/E for an open source implementation that uses at most N/k bits while running up to 1.5*k^E times slower, for any k>=2 and E>=1. Or is that still too strict for your taste? |
|
|
|
|
Show Posts
