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.

  • $\begingroup$ 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}$. $\endgroup$
    – fgrieu
    Commented Mar 23, 2021 at 13:58
  • 1
    $\begingroup$ 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 $\endgroup$
    – kelalaka
    Commented Mar 23, 2021 at 14:10
  • $\begingroup$ @fgrieu Can you quantify way above $10^{10}$? We can pick one definition of fan-in $2$ and fan-out $1$. $\endgroup$
    – Turbo
    Commented Mar 23, 2021 at 14:58
  • $\begingroup$ @kelalaka Is the terminology levels similar to depth? $\endgroup$
    – Turbo
    Commented Mar 23, 2021 at 14:58
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Commented Mar 23, 2021 at 15:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.