MultiLinG - Extracting Linear Relations from Gröbner Bases for Formal Verification of And-Inverter Graphs (Artifact)

MultiLinG is a formal verification tool implemented in C++ designed for efficiently verifying And-Inverter Graphs (AIGs). It leverages algebraic techniques by encoding the circuit as a set of polynomial equations and computing Gröbner bases to extract linear relations that facilitate correctness verification. Unlike traditional approaches that focus on rewriting the specification polynomial, MultiLinG shifts the computational effort towards manipulating the Gröbner basis itself. By employing degree-based term orderings and local Gröbner basis computations using the computer algebra library msolve, MultiLinG minimizes intermediate complexity and enhances scalability when handling large, complex circuits. MultiLinG demonstrates its practical effectiveness through formal verification of arithmetic circuits, particularly multipliers.