Solution 91353d 7044ed7 eab3c18 11cc7bd5 11dbab29 155aeb72 171fafe9 18423605 1d18e11b 1f498480 209c0518 242e865a 2dda66a3 312e6228 31dbee8c 3585254e 35dc6d39 3f2eaa8b 40a25d6c 43d2b2ab 464b2c17 48ea7ef3 4bce1ea9 4dc4d7e6 546b3e05 55f4daa3 5937c994 66961386 675c49a8 67933a95 6b4fd632 72da1d3b 74b57814 76032cbd 774cacdd 79eb4cf1 7b20cfa7 7b8f8a15 7de1f1f1 7f6b78ef 7f7cc3ef 7fbd9ecb
I found the next one right on the first try: > HEADER="[quote author=tromp link=topic=567434.msg6181952#msg6181952 date=1397282207]"
> ./verify32 -h "$HEADER tromp 0"
...
Verified with cyclehash 0f12c0e2f5120650c54318755d5d284d63ef932365b85fc76e5a6cdd8f5457bc
This one even has 4 starting zero bits in its cyclehash! Solution 3f5f388 77e5632 e4f771e f30924d 1009c98f 104dae88 10f04350 14ea06aa 1b8bf400 1dc7a4bb 1e8a6a30 1ec9d2eb 21911186 22177bd8 22c8bd12 25be4110 273161c9 27f645f1 2ac782bf 2feaf1b7 3143738b 31ba1644 3777861b 3f4f772c 40cb82ad 4317ebc2 4820b25e 492cfb36 4963ddc7 49adcf18 4f6952f1 54ecfd38 55c0dfab 59540177 6157e556 62525136 64ba747a 70cd7e58 789db876 7bd04504 7e8d748c 7fc36867 |
|
|
|
Please have a look!
I'd like to start a little experiment with a blockchain of posts, embedded right into this forum. Each successive post must start by quoting the last line of the previous post, and end with a proof of work based off that post. Specifically, it must be a cuckoo32 proof for a header consisting of the quote tag followed by the author name, followed by any nonce. To generate the last line of this post, I ran > git clone git://github.com/tromp/cuckoo.git
> make cuckoo32
> HEADER="[quote author=tromp link=topic=405483.msg4392708#msg4392708 date=1389205766]"
> for i in {0..99}; do ./cuckoo32 -t 4 -h "$HEADER tromp $i"; done
and waited for a 42-cycle to be found. Since the probability of a 42-cycle is about 2.2%, it should take on average 45 runs to find one. Curiously, I found one after *exactly* 45 tries, as you can see in the transcript at the bottom, which ends this post with the required proof. As there was no previous post in this thread, I instead quoted my original announcement of Cuckoo Cycle from Jan 8. cuckoo32 requires 768MB of memory. You can reduce this to 512MB by running cuckoo32.1 which will take about 50% longer, or to 384MB by running cuckoo32.2, which is much slower still. The load shows how densely loaded the hash table datastructure will be that's used in the final phase to actually find the cycles. This has to drop below 100% for the hash table to work (it actually requires load <90%). The proof can be verified with > make verify32
> ./verify32 -h "[quote author=tromp link=topic=405483.msg4392708#msg4392708 date=1389205766] tromp 45"
and feeding the solution line on standard input. This should output: Verifying size 42 proof for cuckoo32("[quote author=tromp link=topic=405483.msg4392708#msg4392708 date=1389205766] tromp 45") with 50% edges
Solution 91353d 7044ed7 eab3c18 11cc7bd5 11dbab29 155aeb72 171fafe9 18423605 1d18e11b 1f498480 209c0518 242e865a 2dda66a3 312e6228 31dbee8c 3585254e 35dc6d39 3f2eaa8b 40a25d6c 43d2b2ab 464b2c17 48ea7ef3 4bce1ea9 4dc4d7e6 546b3e05 55f4daa3 5937c994 66961386 675c49a8 67933a95 6b4fd632 72da1d3b 74b57814 76032cbd 774cacdd 79eb4cf1 7b20cfa7 7b8f8a15 7de1f1f1 7f6b78ef 7f7cc3ef 7fbd9ecb
Verified with cyclehash 13d4d71265d1bd8f6a75c90e5ae3759086ee3d742dd9405aac9b4519fee56db1
This post will serve as the genesis "block". Non-conforming posts risk being deleted. Happy mining! (I'm afraid there's no reward for "mining" new posts, just bragging right for being in a post blockchain) ... Looking for 42-cycle on cuckoo32("[ quote author=tromp link=topic=405483.msg4392708#msg4392708 date=1389205766] tromp 45") with 50% edges, 8 trims, 3 threads Using 256MB edge and 512MB node memory. initial load 3200% 1 trims: load 947% 2 trims: load 373% 3 trims: load 201% 4 trims: load 126% 5 trims: load 87% 6 trims: load 63% 7 trims: load 48% 8 trims: load 38% 16-cycle found at 2:99% 218-cycle found at 0:99% 452-cycle found at 1:99% 42-cycle found at 0:99% 80-cycle found at 1:99% 3094-cycle found at 0:99% Solution 91353d 7044ed7 eab3c18 11cc7bd5 11dbab29 155aeb72 171fafe9 18423605 1d18e11b 1f498480 209c0518 242e865a 2dda66a3 312e6228 31dbee8c 3585254e 35dc6d39 3f2eaa8b 40a25d6c 43d2b2ab 464b2c17 48ea7ef3 4bce1ea9 4dc4d7e6 546b3e05 55f4daa3 5937c994 66961386 675c49a8 67933a95 6b4fd632 72da1d3b 74b57814 76032cbd 774cacdd 79eb4cf1 7b20cfa7 7b8f8a15 7de1f1f1 7f6b78ef 7f7cc3ef 7fbd9ecb |
|
|
|
TMTO works because scrypt writes the memory in-order from 0 to N-1 then reads them in a pseudorandom/unpredictable order; if you didn't save all the odd-numbered words you can recover any one of them on-demand by reading the word before it and doing the mixing operation. If, on the other hand, you wrote those words in a pseudorandom/unpredictable order as well, TMTO wouldn't be possible (or at least pointlessly time-expensive).
I think what you call a word is a 128 byte block. Whatever order you generate could be trivially stored in a map of N indices, so you could still leave out alternate blocks and use the map to find the block from which to generate a missing one?! So glad you actually wrote a whitepaper. It's a huge pet peeve of mine when people make some big showy announcement about something and the only clear technical explanation is either their source code or a bunch of random postings scattered across reddit and some webforums  . Thank you for taking the time to do this. Thanks! I consider a detailed whitepaper a necessity for getting proper exposure and criticism. The paper needs a lot of updating to take the recent algorithmic improvements into account. I'm still going through the paper (should finish this weekend) but just one nitpick for now: Memory chips, in the form of DRAM, have only a tiny portion of their circuitry active at any time, and thus require orders of magnitude less power.
That can be true but it depends on the access pattern... DRAMs have a lot of internal parallelism, so if you can blast reads/writes at a nice uniform stride that matches the bank size you can actually get more or less the whole thing running at once. GPUs are designed around exploiting this. The cycle time at the pins is way way way shorter than the cycle time of the internal arrays. In fact as you move inward from the pins towards the capacitors each stage of circuitry has a longer cycle time than the previous one (sorta like a pyramid). But yeah, what you say is true if you're doing serially-dependent reads and it's mostly true if the address pattern is pseudorandom. Ah, thanks for elaborating. That explains how Cuckoo Cycle can handle so many threads that are all hammering main memory. With your understanding of parallellizability of memory accesses, do you see possible improvements in the bucketing mechanism in the current implementation? |
|
|
|
Next on the to-do list is another of Dave's suggestions:
to bucketize the array of nodes to work on, to improve
main-memory locality. That will help the edge trimming,
which works on only one edge endpoint at a time,
but won't help the original algorithm, which needs to work
on both edge endpoints at the same time.
So that may well achieve speed-parity...
And so it did! Reducing the number of page faults is a big gain. Actually, the bucketing doesn't affect page faults. Profiling shows that the large speedup is due to big reductions in stalled-cycles-frontend and stalled-cycles-backend. Somehow alternating siphash computations with main memory accesses causes lots of stalls, while doing a bunch of hashes followed by a bunch of main memory accesses is much better. Damn; performance optimization is hard... |
|
|
|
Thanks for your comments; this is the sort of discussion I was looking for.
Thanks for raising some excellent points in your original post and starting this discussion. Sorry, you're right, I got the parameter names mixed up. What I'm talking about doesn't have a separate parameter in the scrypt specification. In scryptROMix step 3:
3. for i = 0 to N - 1 do
j = Integerify (X) mod N
where Integerify (B[0] ... B[2 * r - 1]) is defined
as the result of interpreting B[2 * r - 1] as a
little-endian integer.
T = X xor V[j]
X = scryptBlockMix (T)
end for
There's no reason why that for loop (bolded) has to be from 0..(N-1); the loop could run more or less than N times. That's the parameter (the number of times that loop runs) that I was thinking of reducing. Of course you still have to populate the memory in the first place, which takes N operations, so this isn't a complete solution yet.
Scrypt already allows for some time-memory trade-off (TMTO, or, as Dave suggested, "tomato":-) Reducing iterations will make those trade-offs all the more effective. Hrm, not hashcash based in what sense? If you mean not in the sense of using a SHA-family function then sure, but Litecoin is already "not hashcash based" in that sense.
Of course, Litecoin is very much hashcash-based, as are most PoWs proposed these days. I'm talking about hashcash alternatives like Primecoin, Momentum, or my own design, Cuckoo Cycle ( https://github.com/tromp/cuckoo). I had hoped the latter could require many GBs of memory, but Dave Anderson recently pointed out a huge improvement in the algorithm that slashed the memory requirements by a factor of about 21, meaning it would take half an hour to run a 16GB instance with 20 threads... |
|
|
|
One problem with the above is that you'd need 16GB of storage to check block validity, even for SPV clients on things like cell phones. So that's one problem that would need to be fixed.
Maybe if the r-value (number of rounds) were really low and only a small fraction of the memory cells wound up being read from the block header could include some kind of map showing which memory cells got hit during the hashing operation. Then with the map a low-memory device could check a hash.
Even better, SPV clients could ask full-chain clients to calculate the map for them so it wouldn't have to be stored in the chain. The point is that giving an SPV client a bogus map won't fool them so there's no trust there.
Scrypt already has the lowest possible r=1. Checking validity becomes somewhat cumbersome at scrypt-13 using 1MB. A scrypt-29 using 16GB is basically unverifiable for all practical purposes. You'll need a completely different PoW (i.e. not hashcash based) whose verification time is constant or growing very slowly (e.g. logarithmic) with increasing memory requirements. |
|
|
|
Perhaps multiplexing. Slow memory latency bound means we don't need very fast transient response.
Yes, multiplexing should be quite possible. So you might fit over a thousand cores on a chip, and run over 32 instances. What is the justification for memory interface saturated at 32 cores?
These cores do siphash in hardware, and have vastly simpler control logic, so they generate the memory requests much faster than x86 cpus. The number could be quite a bit less than 32. If you can get it down to a single thread, then that itself brings further simplifications. Tilera cores are 400mW, so 12.8W for 32 cores. That might be load dependent though. Are ARM or Atom CPUs more efficient?
Roughly comparable. Intel's spark is another step up in efficiency, but is not competitive in performance. Hopefully the community can arrange to provide to you access to a TILE-Gx now or in near future.
My best odds would be to write the company and try to get them interested in running the benchmark themselves, as possible promotional material. But considering Cuckoo Cycle hasn't been adopted yet, I doubt they want to invest any effort. |
|
|
|
But it won't be all that much faster or cheaper than some similar
construction of commodity parts, considering how manycore cpus will become popular soon.
If the main per hardware $ cost is memory, then the more threads the lower the cost. Since an ASIC can discard unneeded generality, it should support more threads. The asic could have thousands of cores. But a chip can only have a few 100 IO pins, of which each memory interface needs at least 32. So you'd be limited to running at most, say, 16 Cuckoo instances, each only needing 32 cores to saturate their memory interface. Since memory latency bound is not consuming much electricity, the main electrical load comes from the computation of the hashes, thus ASICs due to their dedicated circuits should be per Watt more efficient than manycore CPUs.
Memory chips run at about 1W each, I think. That's 1W per Gbit. A cuckoo instance (512MB) would take 4W, which I think is already more than the 32 super-simple cores would need. So I disagree with you on where the power mostly goes. For mobile computing, the requirement is power efficiency. Thus the simpler and more CPU cores model may win. Thus your Cuckoo Cycle may become the correct choice in the future for making sure proof-of-work on a mainstream device is not at a disadvantage to economies-of-scale, ASICs, nor GPUs. I urge you to measure and determine if there is an asymptotic limit to the parallel threads, so we can determine at what point your hash becomes the superior choice. Perhaps you can only do this with a simulation, unless you can get your hands on a Tilera CPU but which currently top out at 72 cores.
I would love to bench Cuckoo Cycle on either a Xeon Phi, a dual 15-core Xeon, or a TILE-Gx processor. All are rather hard to find in the wild though (I had acces to a Phi, but it kept crashing on my code:() PS: I corrected the hashing overhead in the new algorithm from 16x to 4x since it only hashes edges which survive the filtering in each round. I measured the fraction of runtime spent NOT accessing main memory (mostly hashing) as 32.5 % So it's still latency dominated, just not as extremely as before (where it was 5% vs 95%) I would be working to share development effort and offload it to the younger guys as much as makes sense.
I'm fast approaching 50 myself:-( |
|
|
|
The most important question is it still parallelizable (multiple threads on same memory) even if slightly sublinear? If yes, then some economy-of-scale can be applied to outperform personal computer CPUs per Watt at least, if not also per hardware $. Even if no longer parallelizable, this might still be true (as you know ASICs can be more power efficient than CPUs because they are dedicated circuits)
It parallellizes well upto 20 threads at least. Haven't tested the new version on anything with more than 20 cores. I expect memory will be saturated before reaching 100 threads. A cuckoo ASIC will be a vastly simplifed manycore cpu. It will do away with the need for virtual memory support, page tables, and big caches (which the current implementation uses just to reduce page faults). It will attach to a bunch of memory chips, but just load and write 32 or 64 bit words rather than whole cachelines. It will have a siphash instruction, and no floating point support. It will be tiny and cheap, a small fraction of the price of the memory it needs. But it won't be all that much faster or cheaper than some similar construction of commodity parts, considering how manycore cpus will become popular soon. Also thanks for introducing me to Cuckoo hashing. Might be able to apply that to my programming work.
Cuckoo Hashing is great for where simplicity is key and you don't need to achieve high loads. For better locality and high loads I think you can't beat Hopscotch hashing... |
|
|
|
However, making a cpu-only algorithm has escaped all those who tried, as far as I know. I have studied many algorithms that attempted to accomplish this and they all fail in some way. The closest I found was the Cuckoo Cycle by tromp. The problem it has it that it only requires memory. And memory can be scaled along with a lower cost processor cores such as the Atom or a custom ASIC that has a DRAM interface for each processing core. Cuckoo Cycle is really only GPU resistant. Also the Cuckoo Cycle white paper admits it is runs faster on multiple threads, even if slightly sublinear when doing so, thus the specialized Tilera CPUs for servers should kick ass on the cpus we use on our computers on a hash rate per $ and per Watt basis. Also I am not confident that some algorithm couldn't subvert the Cuckoo Cycle hash because it is ordered setup. For example, I envisioned using bit strings in place of empty memory locations.
It was in fact subverted in exactly that way! See https://bitcointalk.org/index.php?topic=405483.40The latest algorithm has an edge-trimming filter that uses a bitvector to record which edges cannot be part of a cycle. As such there are no "empty memory locations" at this stage. It gets by with 21x times less memory, and 4x more hashing, at roughly the same speed as before. Maybe you can stop calling it a memory-only coin... |
|
|
|
The new code is up at https://github.com/tromp/cuckoo, as Makefile targets cuckooNN (for various value of NN). The old code is now only useful for small instances and relative easiness > 50% (at which edge trimming fails). Apparently this is due to the use of C++ atomic datatypes. Experiments using plain non-atomic datatypes instead, show negligable differences, so that is now the default. Current performance is listed in the README as 6) running time on high end x86 is 9min/GB single-threaded, and 1min/GB for 20 threads. The big open question is still how well a GPU can perform Cuckoo Cycle. Most main memory accesses in (the current algorithm for) Cuckoo Cycle are to different 64-byte segments (GPU cache line size), making latency of prime importance. And that's where GPUs fare worse than CPUs... |
|
|
|
I haven't figured out how to achieve speed parity:-(
Suggestions for further improvement are more than welcome!
Next on the to-do list is another of Dave's suggestions: to bucketize the array of nodes to work on, to improve main-memory locality. That will help the edge trimming, which works on only one edge endpoint at a time, but won't help the original algorithm, which needs to work on both edge endpoints at the same time. So that may well achieve speed-parity... And so it did! Reducing the number of page faults is a big gain. Edge-trimming is 33% faster single-threaded, but multi-threading speedups are very erratic, e.g. 7-11 threads are all worse than 6 threads, 12 is much faster but then slow down through 19 threads, and finally gain more than double at 20 threads. The new code is up at https://github.com/tromp/cuckoo, as Makefile targets cuckooNN (for various value of NN). The old code is now only useful for small instances and relative easiness > 50% (at which edge trimming fails). |
|
|
|
I haven't figured out how to achieve speed parity:-(
Suggestions for further improvement are more than welcome!
Next on the to-do list is another of Dave's suggestions: to bucketize the array of nodes to work on, to improve main-memory locality. That will help the edge trimming, which works on only one edge endpoint at a time, but won't help the original algorithm, which needs to work on both edge endpoints at the same time. So that may well achieve speed-parity... |
|
|
|
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). Baseline: My code uses 10x less memory and runs 2x slower (on a laptop instead of an i7). At 6x less memory, it should have speed parity. Could be optimized substantially - I sent you some very hacked up code. Happy to post it publicly if anyone's interested, but it's trashy - I just wrote it as a proof of concept for the pre-filtering before invoking the cycle finder. But it gets the point across. A complete working implementation of Dave's scheme is now available on my github. Makefile targets cuckooNN still use the old memory hungry algorithm, while targets tomatoNN use his edge trimming (12 rounds by default). I haven't figured out how to achieve speed parity:-( Suggestions for further improvement are more than welcome! -John |
|
|
|
4) make your pow so hard that solving a single instance on an average CPU
takes more time than the block interval.
(limit it to many-core CPUs and GPUs, but unlike in 2) they need only be 10x faster)
This may also make it pool resistant, if there's no way to prove you did work by submitting shares (reduced difficulty proofs) ... |
|
|
|
|
Or in other words, how to make botnet operators vastly prefer other coins over yours?
I can think of 4 ways.
1) make your coin worthless.
duh!
2) make your pow so highly parallelizable that an average CPU is 100x slower than a GPU
3) make your pow require so much memory that it typically won't fit in memory
(in other words, limit it to high-end desktops, servers and "big" GPUs)
4) make your pow so hard that solving a single instance on an average CPU
takes more time than the block interval.
(limit it to many-core CPUs and GPUs, but unlike in 2) they need only be 10x faster)
Feel free to add to the list if I missed some...
|
|
|
|
Why use scrypt-n?
scrypt-N is a misguided attempt at being ASIC-resistant. It's quite possible to make ASICs that handle any scrypt-N with N in the range (10..20), since one can feasibly fit 128MB on a single chip. At N=20 however, scrypt is already unusable for another reason, namely that verification effort also scales exponentially with N (a fact conveniently ignored by its proponents). X11 is something of a joke. 11 hash functions that are each designed to have efficient ASIC implementations, are still very ASIC friendly in combination. The claimed GPU benefits are due solely to suboptimal implementation. |
|
|
|
To have 50% odds of at least one L-cycle edge, you need to sample about 1.5%
log(n) doesn't cut it.
To quote myself back: "Not guaranteed, but ... can always start over." In other words, you can settle for a 20% chance if you're willing to run the sampling test a few times, if it saves you enough memory. That's why I mentioned 50%. Settling for 20% or 50% makes little difference. You can settle for 0.1% and still the log(n) doesn't cut it. The definition of the problem is to find a cycle, not the cycle.
Again, this makes no difference except for small constant factors, since you expect to find about only 3 cycles on average. Your writeup of Cuckoo Cycle, as of Mar 28 09:28, said:
"We introduce the very first proof-of-work system that is both verify-trivial and tmto-hard."
Period. There were no qualifiers attached to that statement. No conjectures, no conditionals, until section 10, where you note that it's a conjecture.
Yes - if you said "We introduce the first Proof-of-Work scheme based upon graph-theoretical structures. We hypothesize but have not proved that this PoW may lead to certain memory-hardness properties" I'd be totally fine with it, because it would be an accurate description of what you've done.
You're right. I was wrong to claim hardness without proof. I rewrote the README and shall rewrite the paper as well when I have time, possibly dropping the hardness hypothesis. Create a bitvector representing the first half of the nonces. Call it the "lower half".
Iterate on this bitvector using the full nonce state *multiple times* until you have eliminated all candidates in the "lower half" bitvector that you can relative to the full set of candidates in the lower half (some of which are being eliminated) and all candidate nonces in the "upper half" (which you're not eliminating because you don't have memory).
Then, in piecewise fashion, identify a size-appropriate subset of the specific incident edges on the lower half that are causing problems -- in other words, which nonces in the "upper half" are causing collisions in the "lower half" that prevent you from discarding some of the lower-half entries?
For that small subset (of size << 1/2N -- let's say 1/8th N), do the same process: Eliminate them relative to your now-sparsified lower half and the complete upper half. This should allow you to eliminate more of the lower-half edges. Repeat until the lower-half is sufficiently sparse that you can represent it in reasonable compressed space, and move on to the upper half.
Thanks for elaborating on how to pass the incompressibility threshold. Rephrasing, you paint half the edges red and half blue, and eliminate red leaf-edges. Now remaining red edges are separated from the leaves by blue edges. So you identify a small fraction of these separating blue edges that touch a remaining red edge, and paint them purple. Identifying some leaf purple edges let's you eliminate some more green edges. Choose different red edges to paint purple and repeat. If necessary, try to identify blue edges separated by two red edges from a leaf by recursing deeper. |
|
|
|
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
Actually, that could be quite interesting. Since proof size grows quadratically with clique size, you'd want to limit it to cliques of size 10 (giving proofs of 45 nonces). One can set the desired probability of finding such a clique (in the range 1% to 50%) and figure out what number of edges in a large random graph makes that happen. As with Cuckoo Cycle, edge trimming could be successfully applied: repeatedly count vertex degrees (using 4-bit counters) and remove all edges incident to a vertex of degree < k-1, where k is the clique size. Perhaps this even keeps up a high enough reduction rate that you can afford to keep going until either nothing or a clique is left... We could make the following little table of "scientific" coins/PoWs: chain-structure cluster-structure number-theoretic primecoin riecoin graph-theoretic cuckoo cycle cliquecoin |
|
|
|
|
Show Posts
