# Depth of $\operatorname{SHA-256}$ implementation by fan-in $2$ and fan-out $1$ Boolean circuits?

A fan-in $$2$$ and fan-out $$1$$ Boolean circuit is a circuit consisting of $$\operatorname{AND}$$, $$\operatorname{OR}$$ and $$\operatorname{NOT}$$ gates where number of inputs to $$\operatorname{AND}$$ and $$\operatorname{NOT}$$ are constrained to be $$2$$ and number of output gates any of the gates can be connected to is $$1$$.

I am wondering if $$\operatorname{SHA-256}$$ is implemented as a multi-output (all hash bits computed by one circuit) fan-in $$2$$ Boolean circuit what would its depth be?

Can its depth be in the low $$10$$s while the number of gates could be in say range $$10^6$$ to $$10^9$$?

Direct sequential implementation of rounds would warrant a depth of at least $$64$$ since $$\operatorname{SHA-256}$$ employs $$64$$ rounds.

It has to be a clever optimized design.

• Many definitions of fan-in 2 count NAND and NOR gates as depth 1. I even was taught to count AND and OR as depth 2 (on the grounds that AND is often physically implemented as NAND followed by NOT), and having a discussion this was unwaranted given modern technology where the cost of routing signals dominates logic. I don't know how to make a definitive answer to the question as in the title, but I'm ready to bet the house that for depth of 10 (or even 32), the answer is way above $10^{10}$. – fgrieu Mar 23 at 13:58
• I'm guessing that you are going to implement it homomorphically. Here is an article about it: doi.org/10.1007/978-3-642-45239-0_3 – kelalaka Mar 23 at 14:10
• @fgrieu Can you quantify way above $10^{10}$? We can pick one definition of fan-in $2$ and fan-out $1$. – 1.. Mar 23 at 14:58
• @kelalaka Is the terminology levels similar to depth? – 1.. Mar 23 at 14:58
• Sorry my best justification is qualitative: cost at fixed depth is likely exponential (or worse) with the number of rounds, and 64 is a lot. Also consider the reference pointed by kelalaka uses hundreds of gates for a single round with depth >40. – fgrieu Mar 23 at 15:05