bitblasting

Bitblasting is a technique used in digital logic and formal verification in which a bit-vector or multi-bit operation is transformed into a propositional formula over Boolean variables. Each bit of a vector becomes a separate Boolean variable, and the operation is replaced by an equivalent Boolean circuit or set of CNF constraints. The resulting formula can be analyzed by a SAT solver to answer questions about the original system.

Typically, bitblasting proceeds by fixing a bit-width and translating every gate, wire, and operation into Boolean relations. For example, a 1-bit addition with carry becomes constraints on s0 and c1 from a0, b0, using XOR and AND; full adders for larger widths chain together. The final property, such as an overflow or assertion, is encoded as a clause or set of clauses. The satisfiability of the formula corresponds to the existence of an input assignment causing the property to fail.

Widely used in hardware verification, equivalence checking, and model checking of register-transfer level designs, bitblasting enables the use of highly optimized SAT solvers. It is also used to handle bit-vector theories in SMT solvers by converting to SAT, often with optimizations to reduce formula size. However, the approach can produce very large formulas as width grows, making scalability a concern. Techniques such as slicing, sharing subexpressions, and using symbolic simulation mitigate this blow-up.

Bitblasting is different from high-level symbolic simulation; it is a translation to Boolean logic rather than an abstract interpretation. It is sometimes contrasted with word-level reasoning or algebraic approaches. The term is common in formal verification literature, with bit-blast and alternate spellings such as bit blast or bit blast.