How to determine the layers of a circuit? In many cryptographic applications like Multiparty Computation (MPC) or Fully Homomorphic Encryption (FHE), you consider a function $f$ described by a circuit over some algebraic structure, typically a field.

Now, it's very typical that the complexity of the algorithm heavily depends on the depth of the circuit, and not necessarily on its size.
For instance, this is the case in Lattice-based FHE, in which low-depth is required in order to perform the bootstrapping, or in some non-constant round MPC protocols where the number of rounds depends on the depth of the circuit.

Given the above, I have two questions.


Given a circuit for $f$, how can we optimize to get a "shallower" circuit for the same $f$? Are there any tools/algorithms available for this purpose?
Suppose the circuit for $f$ if given as a list of gates, where each gate points to the gate or gates corresponding to its input. How can we determine the layers of the circuit from such representation? Are there any tools/algorithms for this as well?


The second point is particularly relevant for MPC, in which the communication for the gates in the same layer can be parallelized, providing a big improvement.

Thanks!
Given a circuit for f, how can we optimize to get a "shallower" circuit for the same f? Are there any tools/algorithms available for this purpose?


Researchers have already identified this is a relevant problem for MPC and FHE, where low-depth circuits make a big performance difference.
Some works in this direction include [BDKK+18] and [BHWK16], and digging through their reference will reveal more work in that direction.

Some of the techniques in this area include adapting some optimization tools from circuit synthesis in the electrical engineering domain, and there are some other hand-crafted optimizations as well.


  Suppose the circuit for f if given as a list of gates, where each gate points to the gate or gates corresponding to its input. How can we determine the layers of the circuit from such representation? Are there any tools/algorithms for this as well?


I know of two ways of achieving this. 

Greedy algorithm

One that is very intuitive works as follows, at a high level.
Take the input nodes and compute all the addition gates you can compute from these nodes without stumbling upon a multiplication gate. 
Then compute the multiplication gates that only depend on any of the gates found above (including the input gates).
These gates have depth 1.

Then compute all the addition gates that depend on any of all the previous gates, and then compute the multiplication gates that depend only on the gates found up to this point.
These have depth 2.
This iteration is continued until all gates have been processed.

Using dynamic programming

This approach is considered in [KSS13]. 
To each edge $v_{ij}$ going from gate $g_i$ to gate $g_j$, assign a weight of $0$ if $g_j$ is an addition gate, and assign a weight of $-1$ if $g_j$ is a multiplication gate.
Then, it is easy to see that the depth of a gate becomes the (negative of the) shortest distance from the gate to any of the input nodes.
This can be computed via dynamic programming algorithms like Dijkstra algorithm.




[BDKK+18] HyCC: Compilation of Hybrid Protocols for Practical Secure Computation (link)
[BHWK16] Compiling Low Depth Circuits for Practical Secure Computation (link) 
[KSS13] An architecture for practical actively secure MPC with dishonest majority (link)