The familiar form of the poem (The Riddle of Strider) runs:
All that is gold does not glitter,
Not all those who wander are lost;
The old that is strong does not wither,
Deep roots are not reached by the frost.
From the ashes a fire shall be woken,
A light from the shadows shall spring;
Renewed shall be blade that was broken,
The crownless again shall be king.
Whereas the earliest form is:
All that is gold does not glitter;
all that is long does not last;
All that is old does not wither;
not all that is over is past.
to which was later added a second quatrain:
Not all that have fallen are vanquished;
a king may yet be without crown,
A blade that was broken be brandished;
and towers that were strong may fall down.
There is a vast change between these versions which I would like to consider. Looking at the origin of the poem it would appear that “The Riddle of Strider” fails as a riddle compared with the Anglo-Saxon Riddles, which are generally given in the 1st person and are more cryptic in their format, often employing double-entendre that would shame a Carry On writer. It does however very closely follow the pattern of Anglo-Saxon gnomic poetry, especially the collection known as Maxims II, (Cotton Tiberius B i fol.115a-115b). Here we find simple sayings which are clumped together in loosely related sections. Here we learn that "Winter is the coldest time, spring the frostiest" or "The tree belongs in the soil, spreading its leaves", "The king belongs in his hall, giving out rings" "The sword belongs in the lap, a noble iron weapon." Tolkien more clearly uses this format when he has Treebeard teach Merry and Pippin "The Lore of Living Creatures."
Tolkien's lines are a little more sparse and to the point, but all eight of the original lines and the first four of the final poem could happily sit in company with these Maxims. If anything the original is a few gnomic sayings with the idea that have been collected together around a common theme rather than a riddle, and as I have mentioned the final form does not particularly meet the needs of a riddle. "All that is long does not last" is about as sensible as "Many a mickle makes a muckle" and it really does not suit the positive image that is being made of things that survive in dire circumstances - similarly the tumbling towers of the last line is a thing that is old that fails rather than is renewed. It is not difficult to see why they would be lost over time and replaced with more positive lines about light springing from shadows and wanderers not being lost. "Not all that is over is past" is a good line, but it lost out to the rhyming scheme changing, so it gave way to "deep roots are not touched by the frost," which is great when set against the symbol of the White Tree of Gondor and the finding of the sapling in the snowy wastes of Mindolluin.
It is interesting that both the original and the final contain snatches of alliteration: gold/glitter, long/last fallen/vanquished (?), king/crown, blade/broken/brandished. However there are lines that fail completely in any such scheme (I considered whether old and wither could be consider alliterative in w’s role as a semi-vowel, but as this does not occur in Old English poetry, I have rejected it. The f/v alliteration is similarly dubious, but I have allowed it on the basis of there being no letter v in Old English). If the second line of the second quatrain is re-written "From the ashes a fire shall awaken" then we see alliteration again, but "be woken" is needed to achieve a rhyme with "broken." In terms of Bilbo being the author, he may have taken an original alliterative line and changed it to fit his intent and his rhyming scheme. Perhaps the original gnomic line could have been something like "From ashes a fire may awaken." The only Maxim relating to fire refers to its power: "Fire shall crumble wood" (Maxims I - The Exeter Book, fol.88b-92b).
If the original form of the poem is a collection of maxims, the final version has developed into something a little different. It has two distinct quatrains, the first being like the original; gnomic sayings brought together around a common theme. However the second quatrain is a great departure both from riddles and from maxims. It is a prophesy, or if not quite that then a statement of intent. There is no may about this (weak conditional future), it is all shall (strong conditional future). The only thing standing in the way is the tradition that has surrounded the Shards of Narsil: that they can only be reforged when re-united with Isildur’s Bane. Bilbo may even have been made aware of this without him realising that “his little ring” is this very bane.
It begs the question: who wrote the Riddle of Strider? The obvious (pedantic) answer is of course J.R.R. Tolkien, but that is not what I am trying to tease out. Just as an author has to speak through the mouth of his characters, he must also write from them. Thus Gandalf's letter to Frodo is written "in his style" as Strider says. In the same way Tolkien wrote the poem from the hand of Bilbo Baggins, an old hobbit whose learning is very different from his own. My take is that Bilbo composed the original form of the poem based on old hobbit sayings. Some of these alliterate because they date back to the time that the hobbits lived in the Vale of Anduin and were known (if largely ignored by) the Eotheod, the ancestors of the Rohirrim. The latter still use alliteration in their poems (“From Dark Dunharrow in the Dim morning” “Out of Doubt out of Dark to the Day’s rising”) whereas the hobbits have abandoned it other than incidentally in their songs. (“In western lands beneath the Sun the flowers may rise in Spring” “Old troll Sat alone on his Seat of stone”) (st does not alliterate with s in OE poetry). The non-alliterative lines of the poems are gnomic sayings dating to later periods, particularly since the settlement at Bree and the founding of the Shire. “Towers that were strong may fall down” certainly could refer to the ruinous towers of Rhudaur that they saw en route; they may not have seen towers in Wilderland.
Bilbo subsequently reshaped his “riddle” over the years, certainly before Gandalf first heard it and commited it to memory. In this time, perhaps aware of the condition that Elrond placed upon the marriage of Aragorn to Arwen, Bilbo reworked the whole to be more encouraging for his friend. Aragorn certainly is set on a path by Elrond's pronouncement that can only lead to either his death or to his emergence as King of Gondor and Arnor (and thus the husband of Arwen). Those prophetic sounding lines are certainly very stirring and effective, but unlike any of the ones from the first quattrain, they would not make for an inspirational line to put on a poster that you might put by your desk.