The Hamiltonian formulation of the anti-BRST transformation is given for an arbitrary gauge system with open gauge algebra. This is done by duplicating each first class constraint. One can then introduce a bidegree in the BRST formalism associated with this redundant description of the constraint surface, which has the following properties: (i) the BRST generator OMEGA(T) has bidegree (0, 1) + (1, 0); (ii) the piece of bidegree (1, 0) in OMEGA(T) is the BRST generator of the theory in which the constraints are not duplicated, with the standard non-minimal sector, and (iii) the piece of bidegree (0, 1) in OMEGA(T) is the anti-BRST generator. The most general gauge fixing which preserves both the BRST and anti-BRST symmetries is shown to be of the form [K, OMEGA(T)] where K is chosen such that [K, OMEGA(T)] is a sum of terms of bidegrees (k, k).