According to my favorite microbiologist, Richard Hoover, the fossils are way too big to be sulfur-reducing bacteria. The geologists merely say something like “wow, sulfur-reducing bacteria must have been bigger back then!” which he finds unconvincing. On the other hand, fossilized cyanobacterial mats from stromatolites go back to 3.65 billion years ago, so by no means are these the earliest microfossils.
The relationship between oxygen and sulfur-reducers is simple–oxygen kills them. THey are usually obligatory anaerobes. That’s why they live in the mud at the bottom of lakes. If you look on a periodic table, sulfur is below oxygen, and can do all the things that oxygen does–but with less energy released. The sulfur reducers take elemental sulfur, S_0, and turn it into H2S (hydrogen sulfide, rotten-egg gas). Many hot springs and “extremophile” environments have sulfur-reducing bacteria, perhaps because sulfur gets more soluble at high temperature while oxygen is less soluble. These bacteria are “archaeobacteria”, one of the three roots of the tree of life and presumably not descended from the more common forms of prokaryote.
Other sulfide-oxidizing bacteria can use oxygen to convert H2S + O -> H2O + S, so you find a layered structure to the mud, Sulfur at the bottom, H2S in the middle, and Oxygen at the top. Surprisingly, the longest bacteria in the world (thioploca and thiomargarita up to 0.75mm long) align vertically to form these vertical channels where they move oxygen and and H2S between these two environments in the mud instead of waiting for diffusion to do it.
There must be some underlying explanation for why life forms strive to exist in a world of rocks and methane clouds.
See also: Researchers: Bacteria fossils predate the origin of oxygen. The next big puzzle would be to understand the sulfur-dependent bacteria’s relationship with oxygen-dependent life forms, no? Apart from being alive, the sulfur crowd never amounted to much. Was there something that held them back? Real answers create more questions.