2
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • $\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 ♦
    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
    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
    Mar 23, 2021 at 14:58
  • $\begingroup$ @kelalaka Is the terminology levels similar to depth? $\endgroup$
    – Turbo
    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 ♦
    Mar 23, 2021 at 15:05

0

Reset to default

Your Answer

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