I had envisaged storing the standard chess opening code (D01 or whatever) as part of the game record. That way there is a small storage cost, but very small processing cost (similar to computing the FEN, less than checking for legality, I would imagine.) The opening code could be displayed in games lists at a modest bandwidth cost.
I am not sure whether using the FEN or the move list is better. After a few moves, the FENs would no longer appear in a list of openings, but all move lists must have a leading string that will match. On the other hand, using the move list would fail for unusual transpositions. Whenever you have a FEN that doesn't match or a move list that is not an exact match, you stick with the previously computed opening code, so maybe it's down to the size of the representation of an opening: a move list will be more compact than a FEN for the first few moves.