"According to legend the troubles caused by Majora's Mask were so great the ancient ones, fearing catastrophe, sealed the Mask in shadow forever, preventing its misuse. But now, that tribe from the legend has vanished, so no one really knows the true nature of the Mask's power."
Who was this tribe that used Majora's Mask?
Let's begin with what elements we can consider to be obvious: the Mask Salesman. Perhaps the Masked Salesman himself was a descendant from this tribe, otherwise how else could he have heard the myths and legends regarding the mask, as well as the exact use of the mask in regards to the Hexing Rituals?
Additionally, if the ancient ones sealed the mask away in shadow, and it was never intended to be found again, how would the Mask Salesman know where to find it? He says he went through great lengths to find the mask, so to what extent is the legend of Majora's Mask known in general for the people to search for it?
Again, possibly, with an ancestral link to the tribe, the Salesman possibly had clues to the location of the mask. In addition, we have the infamous Children on the Moon. These Children look almost identical to the Mask Salesman; they have identical red hair in the exact same style, as well as the same yellowish skin.
To further this, after playing Hide and Seek with them, they curiously ask "Will you become a Mask Salesman too?" The connotations and denotations of the word "too" suggests that an acquaintance of the children had become a Mask Salesman before Link, questioning whether this could possibly signify the Mask Salesman himself? It is undeniable that the Moon Children all share the unique features that the Salesman has.
However, the interior of the Moon, and probably everything else inside it, was made by the mask, which could mean that the children themselves were only figments of Majora's psychosis. But we are made aware earlier in the game that the mask starts to control its host and use it as a puppet, after feeding off of it. The Majora's Mask manga, though not necessarily canon, tells us this:
"All who approached the mask, warriors, men and women alike, even with good intentions, were devoured without remorse.
Majora's Mask gained its power from the evil desires that people had in their minds as they were devoured by the beast, or when they cast the hexes."
So perhaps the children in the Moon are merely apparitions of members of the Tribe the mask devoured? Perhaps it was these four people that themselves used the mask for the hexing rituals? If so, this would clearly point to the mask salesman being a member of the tribe. Of course, the Zelda mangas are not generally considered canon, and as such, the excerpt cited above should not be taken as authority.
Although, in Ocarina of Time (and through Tatl's recount of her first encounter with the Skull Kid) we definitely see that the Skull Kid is a rather placid and shy character who is easily intimidated (hence why he was saddened by his lack of a face in Ocarina of Time, with Link spurring his love for masks after selling him the Skull Mask). In this respect, I think we can therefore conclude that the idea of the mask corrupting the hosts is valid, especially given Tael's defense after Skull Kid is defeated atop the Termina Clock Tower that "It wasn't his fault, the power of the Mask made him do it," to which the mask itself replies "He was too weak to use my power."
Another interesting thing about the Mask Salesman is that he is able to freely travel from Hyrule to Termina and back. Link only discovered the portal to Termina after pursuing Skull Kid, who was personal friends with the Four Giants. This begs the question of how someone unaffiliated with any divine (or otherwise) alignment would know of the inter-dimensional door. Furthermore, the Salesman has no Terminan counterpart, whereas a majority of characters from Hyrule do. This arguably suggests that the Mask Salesman is not even a resident of Hyrule, but perhaps from a completely separate dimension altogether.
In addition, the Mask Salesman himself does not seem to display normal facial expressions like everyone else. For example, when Anju is given a letter by Kafei, her neutral face becomes one of surprise in a very natural way - and yet, when the Salesman emotes, the expressions on his face change very statically - like a mask, almost - with which his dispositions similarly transforms abruptly, as he transforms from a fretful, humble man, to a somewhat manic, almost violent... thing.
Interestingly, in the manga, after Majora is defeated inside the Moon, the ending is drastically different to the ending of the game: the Fierce Deity, after seeing the Mask Salesman appear, strikes him down, but the Salesman simply takes back his mask, laughs manically and disappears.
And my last argument for this: the tribe that vanished is never given a name - the Mask Salesman's tribe is never revealed, and it is arguable that he is too distinctive to be a normal Hylian/Terminan.
On the other hand, we have a tiny in-game allusion to the Ikana Kingdom and the Garo Nation, which when investigated, in my humble opinion, reveals a great deal more about the nature of the two extinct races and their relationship with the mask.
We are of course aware that a great war took place between Ikana and a spy nation, and that the kingdom was completely overwhelmed and decimated. The enemy nation must have possessed a power besides their own prowess to completely destroy the Ikanans.
We are told that the dead are walking in Ikana, and are full of regrets, and this is partly the work of Sharp. After freeing the composer, Flat, from his prison, we are told that his brother, Sharp, sold his soul to the devil in order to gain power; in the manga, the mask was also known as the Devil's Mask.
So, already, we have established some connection to Sharp and the mask way before Link had come to Termina, and after selling his soul, Sharp troubled the dead, who became filled with regret. It should be noted that Twinmold seals away the Giant of Ikana, so Ikana is doomed to regret their lives and roam as un-dead, and that Twinmold is created by the mask to seal the Giant away.
Going back to my earlier point about the Garo nation, we are told that today, the Garo are nothing but empty shells. We know that Majora's Mask devours its hosts, and begins using them as puppets. Therefore, is it possible that the Garo are the tribe that used the mask for hexes?
Nowhere is it said that the people of Ikana, or the Gibdos, are empty. The reason that the Garo are specifically referenced to being empty could be that Majora's Mask fed off them, as it gave them the power to overthrow their enemies. As stated, the user of the mask would have its life essence drained by the mask. The results of this for the Garo Nation were quite literal - they were left soulless.
We could assume that the Garos used the mask to hex the Ikana people themselves, which is why the Kingdom of Ikana was so easily defeated. Yet after the war, the Garo themselves died, which would explain why "the tribe from the legends vanished." The race literally died out, which would be why no-one can find traces of either tribe, or, as a result, the nature of the mask itself.
There is a strong case supporting that the tribe of the Moon Children and the Mask Salesman are the Tribe that vanished from the Legends, though it should be mentioned that the Garo Nation and Ikana would likely have had some connections to the mask as well.
However, in Twilight Princess, we are told of a race of Hyrulians that were banished to a shadow version of Hyrule called the Twilight. This can function as a possible explanation for the tribe that vanished from legend. We are told in Twilight Princess by Lanayru, a Light Spirit, that a band of dark magic users set out to conquer the land and acquire the Triforce. To their avail, however, the Goddesses intervened and sealed this tribe of magic users away in shadow.
The Twilight Realm is interchangeably referred to as the Shadow Realm, and the Mask Salesman explicitly says that the "troubles caused by the Mask were so great, that the ancient ones fearing catastrophe, sealed the Mask away in Shadow."
The ancient ones could very well be the Goddesses, and the Shadow a reference to the Twilight Realm. Furthermore, the salesman then says that "the tribe had vanished" which is why no-one knows the true nature of the mask. Could this be a reference to the fact that the tribe of magic users in Twilight Princess were also sealed in the Shadow Realm?
In addition, there is an uncanny similarity between the Majora's Mask and the Fused Shadows, hence why many thought that there was a connection between Midna and the mask, even thinking the Fused Shadow shard she wore was a broken piece of the mask itself. In fact, the accompanying imagery of the Lanayru's tale even depicts Midna's piece of the Fused Shadows to block the sunlight. Which symbolizes the domination of the then-world with the dark magic, and given the infamous ties and affiliations to the mask and Midna's Fused shadow - aesthetic based or otherwise - it could again perhaps reference the mask itself.
The markings on the mask are also present on the Fushed Shadow, like the distinctive 'almond-eye' and the smaller, intricate markings playing down the side of both pieces. While this inherently doesn't mean the two are the same, it certainly points that the two were designed with similar aesthetics in mind. And seeing as both use the power of dark and shadow elements, I think this certainly insinuates that both were created by a common, if not the same, tribe.
In addition, the Fused Shadows are constantly referred to as being old magic; Zant himself even states that the fused shadows are "our old magic" and seeing as Ocarina of Time (and thus, Majora's Mask) takes place a good few centuries or so before TP, and the fact that the tribe is considered ancient during the OoT/MM era, they could be one and the same tribe.
Moreover, it's said in the creation legend that the goddesses departed to the heavens when "their labors were complete", and seeing that they were still around at the time of the dark interlopers, the tribe must have existed close to the time after Hyrule was created, hence why the tribe disappeared too quickly.
This suggests a definite link between the tribe that vanished from legend, the tribe of magic users from TP's legend, and the Majora's Mask.