Eroded channels and chasms from catastrophic floods between martian basins are the strongest evidence yet that there were once large, deep bodies of water on early Mars, according to a new study using the latest imagery and topographic data.

The outflow channels of Mars have been a puzzle ever since they were first spotted in images from the Viking spacecraft four decades ago. In that time every sort of mechanism has been called on to carve them -- among them winds, lava and carbon dioxide-powered debris flows. But none has settled the issue.

"These features have been wracking people's brains since the 70s," said planetary scientist Keith Harrison of the Southwest Research Institute. And they aren't settled yet.

PHOTOS: Weirdest Mars Craters

If it was water that carved them, which seems the most likely candidate, the mystery remains as to where all the water came from. Groundwater has long been the logical choice, but how does groundwater flood out with enough power to erode such giant channels? The answer is lakes. Deep lakes. Five-kilometer-deep lakes. The evidence for these lakes is the channels themselves, which have now been studied using higher-resolution imagery and topographic data than ever before.

"These are mega outflow channels," said Mars researcher Nicholas Warner of NASA's Jet Propulsion Laboratory. "There is the analogy of the Channeled Scablands of Eastern Washington State" which were carved by very short-lived, catastrophic floods. "Those are pretty small in comparison to the five-kilometer-deep channels on Mars."

Warner and his colleagues used the data from cameras on the European Space Agency's Mars express as well as NASA's Mars Reconnaissance Orbiter to digitize and count craters in the eastern Valles Marineris region. Craters are the only way to establish the approximate ages of features on Mars. The craters revealed that the basins were there before the channels, and that the channels were carved from the top-down, as would be expected from a flood from one basin to the next. The detailed results of the study were published in the April 29 online issue of the journal Geology.

PHOTOS: Mars Through Curiosity's Powerful MAHLI Camera

In fact, the whole scenario is being called "fill and spill." Groundwater slowly fills a basin, eventually getting kilometers deep. Then it spills over. Where it spills there is rapid erosion and a channel forms that erodes back toward the lake, increasing the flood and the rush of waters out of the basin, which naturally increases the erosion of the channel. Before you know it, you have a really big chasm.

And these aren't the only flood channels on Mars. There are many basins and many have channels between them, said Warner. In other words, the ground water filled the basins, then one basin overflowed into another, carving a channel that caused the drainage to increase, and that flood caused the next basin below it to overflow into the next basin, carving channels there, and so on and so forth. Whether this happened all at once or in a series of separate and repeated events is unknown.

"There's no clear cut way to tell if it's millions of years or hundreds of days," said Warner. But one thing the channels and craters are suggesting is that water was flowing later and later in Mars' early history.

"There were large amounts of water on Mars early on," commented Harrison. "There is no dispute about that." But was the water in these deep lakes, shallow seas, locked up as ground water, or as ice on the poles? And if it melted into liquid form, as the channels strongly suggest, there is another problem: There is not enough atmosphere on Mars today to keep liquid water from subliming away into the air. Did Mars have a much thicker atmosphere once?

To put it another way: The brain wracking is expected to continue.