Turing Tumble Community

Implementing a cryptographic hash function with TT?

Hi Turing Tumble community!

I noticed there are quite a few threads/discussions about TT as a processor, or trying to prove TT turing complete, etc. Additionally, I noticed there is an excellent post by @lennypitt and others regarding using TT to simulate any computer with finitely many pieces[1].

I am new to TT and to the various simulators available, so hopefully those of you who are more experienced can point me in the right direction. I’m looking for a simple, “low-tech,” implementation of h(x) = sha256(sha256(x)) where sha256 is a specifically cryptographic hash function[2], and x is an input of (technically) any length, but, practically, for the purpose I’m interested in would be an input of approximately 80 bytes.

It was suggested to me that TT might be a good fit for such a challenge. Of course, the construction would likely require some extremely large TT board, a lot of marbles, and pieces. However, I’m trying to get a handle on just how big we are talking about, whether it could be realized physically, and determine how long it would take such a large TT to compute such a function.

Any who are familiar with bitcoin may recognize this construction as being used in various parts of the bitcoin protocol, and especially in the mining algorithm. Actually performing the mining operations directly on such a massive TT would, of course, be extremely inefficient. Yet, verifying a hash should hopefully be doable in a reasonable amount of time (say 10 minutes of the machine “running”?)

Of course there are many other hash functions in the world, the construction h(x) above is just an example, but it is the one I’m most interested in using for pedagogical purposes at the moment. If, however, you are aware of a different construction which is considered cryptographically secure and would be easier to implement, please do share!

Ultimately, what I’m trying to uncover is: what is the simplest, yet (currently) cryptographically secure, hash function that we can implement in TT, if any?

As a way to start answering that question, let’s focus on h(x) = sha256(sha256(x)) and see if it can be simulated first, and then move on to the realization of it physically. I noticed that @OUDON 's simulator handles larger board sizes, but can any of the simulators handle something like this?

[1] How to simulate any computer with finitely many pieces
[2] https://en.wikipedia.org/wiki/SHA-2

1 Like