Turing Tumble Community

Implementing a cryptographic hash function with TT?

Education
#1

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
Turing Tumble CPU
#2

Start with a more modest goal?
This seems hugely ambitious. Perhaps start with a more modest goal. A 4 bit hash of an arbitrary input.
This scenario has an unlimited supply of red and blue balls. All balls are intercepted. An arbitrary length string is generated manually by pressing the blue and red levers to generate a pattern of 1s and 0s (the Message). The board contains a collection of bits and gears (with a defined starting configuration of orientations)
As the Message is streamed through the board, a given “hash function” of the message can be read out (by examining the orientation of the pieces on the board) as it changes as each ball of the message is parsed through the hash function.
A quick look at hash functions suggests some (eg Blake variants) can be set to arbitrary lengths. I suspect even 4 bits probably wouldn’t fit on a standard board.
Step 1: Anyone got a good basis for picking a particular hash function?
Step 2: Lets try to design a board that does it for, say, a 4 bit hash.
Then see where we can go from there.