Re:Optical Proof of Work
by tromp on Thursday November 14, 2019 @04:51PM
(#21539864)
> the very fact that you can verify the result means that you can brute force the outcome
No; you cannot brute-force the outcome in any realistic sense. For example, a Cuckoo Cycle [1] proof consists of 42 n-bit indices of edges that together form a cycle in a random bipartite graph on 2^n+2^n nodes, with typically n >= 29. Brute forcing over all possible size-42 subsets of 2^n indices will take well beyond the heat death of the universe. It's way easier to brute force the 256-bit private keys of all bitcoin balances...
No; you cannot brute-force the outcome in any realistic sense. For example, a Cuckoo Cycle [1] proof consists of 42 n-bit indices of edges that together form a cycle in a random bipartite graph on 2^n+2^n nodes, with typically n >= 29. Brute forcing over all possible size-42 subsets of 2^n indices will take well beyond the heat death of the universe. It's way easier to brute force the 256-bit private keys of all bitcoin balances...
[1] https://github.com/tromp/cuckoo