How can we know (with absolute certainty) that our logic is correct?
Certainty applies to beliefs, so I will assume that "absolute certainty" is code word for knowledge.
We usually believe our logic to be correct. However, most people do not really think about logic per se. Rather, they tend to consider only arguments and reasonings, and tend to express agreement or disagreement according to whether they agree or not with the conclusion. In other words, most people couldn't care less about logic per se. If not for Ancient Greek philosophers and in particular Aristotle, we might still be unaware of it today, using it but never considering it in itself.
The question is further complicated by the long history of formal logic. Most people confuse formal logic with logic itself. However, it is clear that most people make routine logical inferences even though they have no training in formal logic. Plato noticed that people without education could give logical answers. One of the first recorded ad absurdum argument was a century before Aristotle in a poem deriding Homer's idea that the gods had the same appearance as human beings--cows and horses would say that the gods had the same appearance as respectively cows and horses, and it is not possible for the gods to have the same appearance as humans, cows and horses.
Formal logic is at best a model of our logic, and as such may be correct or incorrect of it. However, it is trivial to admit that we do not know whether any formal logic is correct in this sense and I will assume that this is not the question.
So I take the question to be whether we know that the innate logic of our deductive reasoning is correct.
We can treat logic in this sense as a cognitive sense, somewhat similar to vision, memory, etc. As such, we can say that we are essentially dependent on our senses to the point that we do not have any alternative. If we were to distrust our vision, we would have nothing to replace it, at least given the current state of our technology. And so it is for our logic. We may like to fancy that a better logic is possible, but even if there was one, we could only apply it vicariously through our own logic, much in the same way as we play games. The difficulty would be in accepting any conclusion derived using this different logic that would be false according to our own logic. I doubt anyone would accept that. We would probably be unable to decide whether it is really better.
We usually trust our vision but we now understand that it provides an image of the world in the same sense that a map is an image of the territory while not being the territory itself. Is our vision correct of the world? Definitely not, but what we need is to be able to use it to survive, prosper and reproduce. It is in fact so good that we have been able to use it, together with our other senses, to produce scientific theories that greatly improve our ability to predict some events in the future.
However, logic is completely unlike any one of our other senses, although each of them is pretty unlike any other. The point however is that logic does not provide us with an image of the world. Rather, it allows us to build models of it on the basis of the data we get from our other senses. Scientific theories provide a good example of the process by which we start with one model and update it to take into account any new data coming in, sometimes revising almost completely our model. This is what our logic allows us to do. This is what everybody does. Scientists work in a professional and systematic way where the process itself is scrutinised and improved. Outside science, we cannot usually afford the time necessary to carry any systematic investigation to build models. Rather, our brain does it without us necessarily being aware that it is doing it.
Another use of logic is in allowing us to convince other people through verbal arguments. This effectively allows humans to pool their cognitive powers in a way beyond what other animal species can do. Our current civilisation is a demonstration of the effectiveness of this process. All sciences and professional activities rely also on this particular use of our logic.
The result on the face of it is quite good. Human beings have survived in a difficult environment for at least 500,000 years. That we make mistakes it apparent in pretty much everything we do. However, the effectiveness of our logic is that we can modify our models to take into account any new data that contradict them. Scientists do it, business people do it, engineers do it, and the brain of every human being does it even when the subject is not aware of the process. Even dogmatic religious people do it. If they didn't, they would be dead.
So the notion that our logic has to be correct or incorrect is a misconception. Our vision is not strictly speaking correct, but we can use it to survive in the real world, or at least so it seems. It should be noticed that every one of us has plenty of opportunities to disagree with the logic employed by everyone, and I don't know of anyone who seriously disagree with the validity of the modus ponens (Vann McGee's contention to the contrary was a fallacious argument). Mathematicians, who may be regarded as the most systematic users of our logic, rely essentially on the modus ponens, 2,400 years after it was first proposed as a logical truth by Ancient Greece logicians. Formal logic is correct or incorrect, at least to the extent that it purports to provide a model of our logic. But our logic is either useful or useless, effective or not effective. In all appearances, it is very useful and very effective.
It should be noticed that if we tried to verify that our logic is consistent, we would have to use it to carry out this verification because we have no alternative method to do the job, and we would presumably fail to see any problem even if there was one.
Further, we can take our environment to have provided a very comprehensive test-bench that effectively verified that it worked during at least the last 500,000 years. If it didn't work in the natural environment of the Earth, we would not have survived and the human species would have quickly disappeared. The fact that we are here and very successful proves that our logic works, that it is useful, that it is very effective.
It is perfect? That we don't know. However, it should be noticed that humans have come to apply their logic well beyond our natural environment, in particular to new technologies and to sciences, in particular to General Relativity and Quantum Physics, even though these as extremely puzzling aspects of the real world. General Relativity and Quantum Physics both have practical applications and it cannot be doubted that scientists got at least something right in this context.
So, no, we don't know that our logic is correct, but we don't need to. Instead, we need to be able to use it to survive, prosper and reproduce, and we certainly do that every day of our lives.