Apparent inconsistency between results, using Cuckoo12

[yeastplume]

As discussed in the grin channel, I've come across something that looks like an inconsistency between implementations that I haven't quite yet figured out. This may not be an issue, but I'd really appreciate if you could look at it.

I've put an example branch here, containing a few changes that I've made in my own branch for grin. The main differences are that it uses its own SHA256 implementation and doesn't append a nonce to the hash (because this is done on the grin side,) but otherwise should work identically:

https://github.com/mimblewimble/cuckoo/tree/cuckoo12-bug

I have 2 targets in the makefile, cuckoo12 and simple12. In both cases, I've just hardcoded a sample header generated by grin, which is valid and has a solution in grin's implementation and in the simple_miner.cpp implementation. If you make and run simple12, you should see the solution... this is the same as appears in grin, and indeed simple miner works when I hook it into grin through my modded plugin implementation.

cuckoo12 is compiled with the same parameters, EDGEBITS=11, and given the same header as simple12.. but it comes up with no solution set.

However, if, in cuckoo.h, I transform EDGEBITS into a global variable instead of a #define, and set it to 12, (i.e. it's 12 at initialisation time,) then set it back to 11 in the main function (set GRIN_MOD to 1) in my modded implementation to do this), then the result set that comes back is identical to the simple12 example.

Again, haven't quite been able to figure out why, but this indicates there's some slight inconsistency somewhere in the cuckoo_miner.cpp implementation, as the hash keys are identical in both examples.

[tromp]

The most important code to get right is the cycle verification. The cycle that your code found doesn't pass verification, according to

./simple12 | grep ^Sol | ./verify12 Verifying size 42 proof for cuckoo12("??dC??% I????nz??????? L?b^:.{?]?@?",0) FAILED due to endpoints don't match up

where I've hardcoded the same fixed header into cuckoo.c to make verify12 with Johns-iMac:src tromp$ g++ -march=native -m64 -std=c++11 -Wall -Wno-deprecated-declarations -D_POSIX_C_SOURCE=200112L -O3 -DPREFETCH -I. -pthread -o verify12 -DEDGEBITS=11 cuckoo.c -lssl -lcrypto

When you find a verifiable cycle that my code fails to find, then I can identify the bug...

[yeastplume]

Thanks for looking at this. I went down the same route a little ways, but then realised the keys in verify weren't matching up with what was used during the cycle finding. I had to change the verify code slightly (as I did in cuckoo_miner.cpp) to ensure a nonce wasn't being added and the passed-in header was being used for the seed as-is. I've pushed up another version with these changes, (and just hard coded the solution set into cuckoo.c, for ease-of-use,) and the nonces do verify once they're using the same key.

[tromp]

Thanks for the updates. I was able get your cycle verified. The reason cuckoo_miner doesn't find it, is that the graph is too small for the trimming to give a big enough reduction in edges. With ntrims increased beyond 7 (as hardcoded in your program), you see this trimming behaviour:

Looking for 42-cycle on cuckoo12("??dC??% I????nz??????? L?b^:.{? ?rR?",0) with 50% edges, 17 trims, 1 threads Using 256 B edge and 512 B node memory, 1-way siphash, and 4-byte counters k0 8597e769806de65a k1 44d2f66cbb879f11 initial load 3200% round 1 partition loads U0 2054% V0 973% round 2 partition loads U0 601% V0 407% round 3 partition loads U0 318% V0 275% round 4 partition loads U0 243% V0 214% round 5 partition loads U0 196% V0 179% round 6 partition loads U0 170% V0 164% round 7 partition loads U0 160% V0 159% round 8 partition loads U0 157% V0 157% round 9 partition loads U0 157% V0 157% round 10 partition loads U0 157% V0 157% round 11 partition loads U0 157% V0 157% round 12 partition loads U0 157% V0 157% round 13 partition loads U0 157% V0 157% round 14 partition loads U0 157% V0 157% round 15 partition loads U0 157% V0 157% round 16 partition loads U0 157% V0 157% round 17 partition loads U0 157% V0 157% nonce 0: 17 trims completed final load 157% overloaded! exiting...0 total solutions

The program aborts because there's not enough edges can be trimmed to bring the load under 100%. For this reason I would recommend a minimum size of 2^20 for cuckoo_miner, although you may find 2^16 working fine as well.