If you wrote a reversible SHA-256 algorithm, how many "metadata" bits would be required for reversability? I was reading about reversible computing while thinking about FPGA circuits. I realized that it would be possible to write a reversible SHA-256 algorithm if you stored some additional information as "garbage". E.g. The algorithm/circuit would compute a SHA-256 hash, but it would also produce some metadata that allows you to walk backwards through the logic gates and arrive at the original preimage.

A NOT gate is already reversible, and an XOR gate just needs to pass one of it's inputs as an output. Toffoli gates can be used for everything else, so any boolean function can be made reversible. A fully unrolled SHA-256 algorithm is just a boolean function with an input and output.

If you used reversible gates for every step in a SHA-256 circuit, how many garbage bits would be in the output? And would it be possible to compress this data?

Let's say you have a 447-bit preimage (so one 512-bit chunk.) Would it be possible to compress the garbage from a reversible SHA-256 circuit into less than 447 bits, so that [SHA-256 hash plus garbage bits] would be enough to reconstruct the preimage? (If not, then you may as well just store the original preimage.)

Another way of framing this question: How many bits of information about the preimage are stored in a SHA-256 hash?
If you wrote a reversible SHA-256 algorithm, how many "metadata" bits would be required for reversability?


If you would write such an algo, it would not be SHA-256 anymore. Also, it would lose its cryptographic usefulness. 

SHA-256 is a non-reversible, one-way compression function. Voiding the non-reversability would void the core functionality that makes SHA-256 a cryptographically secure hash.

In  the end you would end up having a non-lossy, two-way compression function — and a bad one too as it would waste too much space compared to simple compression functions like (for example) ZIP.

Also, since the goal ends up right there, it is not about cryptography anymore… rendering any further discussion about your idea off-topic.

TL;DR: 


Assuming you do not modify SHA-256 and simply rely on your "metadata" for reconstruction, the size of your "metadata" would be equal to the size of the input.
Modifying SHA-256 itself to optimize the space needed for any kind of "metadata" is not an option, as the algo would lose its cryptographic usefulness (and not be SHA-256 anymore anyway). 




Besides that, your question seems to try work around something which has been asked several times before.

For example, see Would it be possible to generate the original data from a SHA-512 checksum?.

So, in a broad sense your question is a duplicate of all existing questions asking about restoring the original input data from a cryptographically secure hash output.

Any other interpretation of your question (in its current state) would make it an information theory question which would be more on-topic at Computer Science StackExchange.