Zelda Gaiden was the title for a cancelled Nintendo 64DD game from the Legend of Zelda series. It was planned to be an add-on to the critically acclaimed The Legend of Zelda: Ocarina of Time. The game was cancelled due to the failure of the Nintendo 64DD. However, the game evolved into the critically acclaimed The Legend of Zelda: Majora's Mask.
During the development of Majora's Mask's predecessor, The Legend of Zelda: Ocarina of Time, Ocarina of Time was intended to be the launch title for a disk-based add-on for the Nintendo 64, simply titled the Nintendo 64DD. The development was moved over to a cartridge for performance reasons, but because of this, the game lost some space. Despite being released on a 32-megabyte cartridge (the largest amount of space Nintendo had ever used in a cartridge at the time), the game suffered from the downgrade in space, going from 64-megabytes to only half as much, and caused the omission of several cut-scenes, enemies, features, the Unicorn Fountain, and two whole dungeons: the Ice Temple and the Wind Temple (rumor says that a third dungeon was also cancelled, called the Sky Temple).
Despite this, Nintendo wasn't going to give up, and to make up for the lack of space, they planned on releasing not one, but two add on disks for Ocarina of Time. One of the add-ons was simply called "Ura Zelda" (which literally translates to "Other Zelda"), and the other was called "Zelda Gaiden" (which translates to "Zelda Side-story").
While it's unknown what happened to Ura Zelda after its cancellation (some speculate it became The Legend of Zelda: Ocarina of Time Master Quest for the GameCube), Zelda Gaiden was continued. However, Eiji Aonuma, dungeon designer of Ocarina of Time, felt that the game was to simalar to Ocarina of Time, and asked Shigeru Miyamoto to make a different game altogether. Miyamoto agreed, but challenged him to make the game in only a year. Aonuma accepted this challenge and set to work. The team used the same game engine and recycled several graphics (which led to some minor mistakes, such as the banner over Romani Ranch reading "Welcome to Kakariko Village" in one of the alphabets used in the fictional language Hylian, the language of games in The Legend of Zelda franchise). The game met a similar fate to Ocarina of Time, being ported to a cartridge instead of a disk (due to its prolonged development as a disk based game, the final cartridge version required the Nintendo 64 Expansion Pak to run). The title was changed to The Legend of Zelda: Majora's Mask, and released in Japan on April 27th, 2000, followed by a release in other regions soon after, to critical acclaim.
Miscellaneous vut stuff
Unlike Ocarina of Time, there seems to be very little early footage from this game, and most of what's been found out was from screenshots.
The long, gray stones you can see in this image were cut from the Stone Temple Tower dungeon, but are still in the games files.
This strange, early image shows the moon without a face. Although it seems just to be concept art, it does suggest that the nightmare fuel face of Termina's moon may have been added later on.
There is a glitch in the game that stops time altogether. This is actually part of a lost feature of the game: one real-time week to beat the whole game. This is proven further by the tiny Moon, which likely would've been this large on the first of the week.
A strange, much earlier image, shows a very... colorful area that houses the shadow temple in the final.
As there is little known about the earliest versions of the game, there is a lot of speculation as to some of the unused items. Some, like the different instruments shown assigned to the C buttons, wasn't a major change and either freed up inventory space or was a cosmetic change to the ocarina in different forms. There was once an adult Link mask, which was removed and technically became the Fierce Deity mask, the original version dubbed unnecessary since young Link could use all the items needed, unlike the last game. The forms have changed little in them, aside from Goron Link once using the Megaton Hammer (the final product merely uses the same impact graphic and effects). There are some theories that the Gibdo mask may have been a transformation mask at some stage, but there is no proof of this. As the game is very side-quest heavy, many think it might have more actual major quests that needed the masks, but no one knows if that is true. There was also a fishing mini-game, and includes a Hylian loach in a bottle, which is missing from the data of the American version of the game. The mini-game was called Jabu-Jabu Fishing, and it was said that if you caught Jabu-Jabu himself, you'd get an unknown reward.
There is so much that was cut from this game left in the files, most being dug out only recently, that covering it all in this article would be impossible, but the following references cover a lot that was left out, including: the Great Fairy cut scenes, early items, leftovers from OoT, other images and the early version of Romani Ranch.
(I don't know what else to add since the first link here covers a ton of stuff I can't really be bothered to put into this... Feel free to try your hand at this mess.)