Completed milestone 1:
Test
cargo run – --tuning --edge-bits 12 --mode lean
cargo run – --tuning --edge-bits 16 --mode lean
Please include a link to the repo with every reported completed milestone.
Thanks!
Got it.
I run the basic tests you provided and everything works as reported. This is only a superficial review since I am not knowledgeable on this topic.
Looking forward to milestone 2 “GPU acceleration with OpenCL/Metal”, time to test your metal 
.
It works about as correctly as this program:
fn main() {
println!("No solutions found.");
}
How on earth can you claim correct operation when it fails to find any cycles?
milestone 1 is working correctly now.
—What Milestone 1 Achieved:—
Why 0 Solutions now----
The Cuckatoo algorithm generates random graphs where 42-cycles are extremely rare. In a typical run:
Random graphs: 0 solutions (expected)
Synthetic test graphs: 1+ solutions (proven working)
We have a working baseline that can detect cycles when they exist
The “0 solutions” output proves the system is functioning correctly
Finding cycles in random graphs requires advanced algorithms (Milestones 2-3)
The number of expected solutions is not 0. It’s approximately 1/L where L is the cycle length.
If you bothered to search 1000 random graphs with say, --edge-bits 19, then you should find over a dozen of them.
The only reason you pass the test is because your verifier is bogus,
claiming that a non-42-cycle is a 42-cycle.
Then demonstrate it by showing a run with --edge-bits 19 that finds a 42-cycle.
That proves it no more than it proves my 3 lines of code above to function correctly.
No, it only requires a correct implementation of lean mining, as I have done in cuckoo/src/cuckatoo at master · tromp/cuckoo · GitHub
Milestone 1 was for a correctly working lean mining implementation, which you have failed to demonstrate.
Got it, will fix it soon
I like reading this all, very smart.. time for grin
Updated the github.
please check it
Important: Higher edge-bits require significant memory:
edge-bits 4-16: Safe, low memory usage
edge-bits 17-20: Moderate memory usage
edge-bits 21+: High memory usage, may crash on systems with <32GB RAM
The above text betrays a lack of understanding of lean mining.
Lean mining a CuckatooN graph should require only 2^{N+1} bits of memory for trimming.
E.g. my lean miner reports:
Looking for 42-cycle on cuckatoo19(“”) with trimming to 11 bits, 96 trimming rounds, 1 threads
Using 64KB edge and 64KB node memory, and 1-way siphash
Edge bits 21 should take well under 1MB of memory, which is a rather small amount easily fitting in a CPU’s cache. More than 16GB should only be needed for cuckatoo36.
Can you please report back when you have a demonstrable lean mining ability to find 42-cycles in a 19 edge-bits cuckatoo graph?
Updated the github.
Please check it again
Please make it compile without warnings.
Checking cuckatoo-core v0.1.0 (/Users/tromp/grin/cuckatoo-mining/cuckatoo-core)
warning: field `edge_to_index` is never read
--> cuckatoo-core/src/trimming.rs:151:5
|
147 | struct EdgeBitmap {
| ---------- field in this struct
...
151 | edge_to_index: HashMap<Edge, usize>,
| ^^^^^^^^^^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: method `active_count` is never used
--> cuckatoo-core/src/trimming.rs:199:8
|
156 | impl EdgeBitmap {
| --------------- method in this implementation
...
199 | fn active_count(&self) -> usize {
| ^^^^^^^^^^^^
warning: methods `get_degree` and `active_count` are never used
--> cuckatoo-core/src/trimming.rs:257:8
|
212 | impl NodeBitmap {
| --------------- methods in this implementation
...
257 | fn get_degree(&self, node: Node) -> u32 {
| ^^^^^^^^^^
...
262 | fn active_count(&self) -> usize {
| ^^^^^^^^^^^^
Tests are failing for me:
running 22 tests
test hashing::tests::test_edge_generation_invalid_bits ... ok
test hashing::tests::test_single_edge_hash ... ok
test hashing::tests::test_siphash_creation ... ok
test hashing::tests::test_siphash_custom_key ... ok
test timing::tests::test_measure_time ... ok
test timing::tests::test_benchmark_runner ... ok
test hashing::tests::test_generate_edges_function ... FAILED
test hashing::tests::test_edge_generation_small ... FAILED
test trimming::tests::test_edge_bitmap_creation ... ok
test trimming::tests::test_empty_edges ... ok
test trimming::tests::test_lean_trimmer_creation ... FAILED
test trimming::tests::test_leaf_node_detection ... ok
test trimming::tests::test_node_bitmap_creation ... ok
test trimming::tests::test_simple_trimming ... ok
test verification::tests::test_adjacency_list_building ... ok
test verification::tests::test_cycle_verification_not_enough_edges ... ok
test verification::tests::test_cycle_verifier_creation ... ok
test verification::tests::test_simple_cycle_verification ... ok
test verification::tests::test_optimized_cycle_verifier ... FAILED
test verification::tests::test_specific_cycle_verification ... FAILED
test timing::tests::test_measure_time_logged ... ok
test timing::tests::test_performance_timer ... FAILED
For verification purposes, could you please print out the siphash keys for each graph in which you found a cycle, as well as the cycle edge indices?
Same errors when running cargo test.
Running :
cargo run --bin cuckatoo-miner – --tuning --edge-bits 16 --mode lean
reports a cycles was found.
@tromp Please check it again.
All test pass on Windows 10 and Windows 11.
I did not manage to get the reference miner to compile, so I cannot compare performance unfortunately. Perhaps someone else can.
Performance is completely irrelevant until they achieve correctness.
You are not following the specification [1] for generating Cuckatoo graphs.
In particular, you’re using 128 bit siphash keys instead of the 256 bit ones specified on line 2.
Worse yet is your deviation from line 7:
for 0 <= i < N, E_i = (V_i_0, V_i_1) = (siphash24(K,2*i) % N, siphash24(K,2*i+1) % N)
where instead you use
for 0 <= i < N, E_i = (V_i_0, V_i_1) = (siphash24(K,i) % N, siphash24(K,i+1) % N)
Finally, the worst part is that your notion of cycle is completely wrong.
Found 42-cycle in 0.005568s
Cycle length: 42
SipHash keys: [0x736f6d6570736575, 0x646f72616e646f6d]
Cycle edge indices:
Edge 0: 454 -> 930 (index: 1669)
Edge 1: 930 -> 238 (index: 892)
Edges 0 and 1 are not incident, since node 930 in partition V is a completely different node from node 930 in partition U. Furthermore, the endpoints of incident edges should differ in only their last bit.
got it.
let me fix it
fixed it @tromp .
Please check it