Goal is to fix Bitcoin and Litecoin so that they cannot be accelerated with special-purpose hardware, because a currency is more secure and less prone to manipulation if a great many people participate in confirming the block chain, as opposed to a few entities with access to special-purpose hardware.
Construct a hash function (or PBKDF) such that any techniques to accelerate it can be redirected to accelerate any computation. We rely on Turing completeness.
A preliminary idea is uses cellular automata. Pseudorandomly populate a region using a random seed derived from the data being hashed. Simulate this initial population for some number of generations. Derive a hash value from the final population.
If we start building special purpose hardware that can simulate cellular automata quickly, then we can start mapping generic computations to cellular automata.
Hashlife algorithms (such as implemented in Golly) provide a time-memory tradeoff. However, I suspect the tradeoff is too severe: more memory provides a speedup that cannot be matched in a million, or a googol, years. Are there certain cellular automata rules for which Hashlife provides less of an advantage? Are they Turing complete?
No comments :
Post a Comment