3 ms·
Interesting. I wonder how a sat solver would do with this problem.
by DanWaterworth 11y ago
Interesting. I wonder how a sat solver would do with this problem.
- metafex 11y agoNot much better i guess? You'd have to model in the SAT-solver what is already more or less efficiently done here. My best guess would be that the SAT-solver would be a lot slower, as this PoW system is mostly based on memory latency. From the paper: "Runtime is linear in graph size and dominated by random access latency"
- DanWaterworth 11y agoI think it's worth trying. I'm not confident that it would be faster, but perhaps a SAT-solver would be able to more efficiently prune the search space meaning fewer random accesses.
- tromp 11y agoThat seems backwards. The random memory accesses are used to prune the search space.
- tromp 11y agoHow would you express a 42 cycle in SAT? How much memory would that take for a billion node graph? The Cuckoo Cycle algorithm only needs 128MB and a few seconds to solve this.
- DanWaterworth 11y ago> How would you express a 42 cycle in SAT? That's easy. You just need to design a combinational circuit that verifies that a particular list of nodes forms a cycle. > How much memory would that take for a billion node graph? Naively, a lot. Thinking about it, way too much memory to be in any way practical. However, there may be a good way to solve it with an incremental solver or, instead of materialising the graph, you could encode the siphash function in the sat solver. Then it would use much less memory. If that works well though, it would compromise the original goal of the project.
- tromp 11y agoI don't see how that could possibly work well with all the overhead. Remember that the reference algorithm can be viewed as an exceedingly optimized SAT solver, using exactly one boolean variable to say whether a particular edge is used in the cycle or not.