Most modern fighting games actually handle replays this way, because its significantly cheaper on storage and still deterministic(often they'll have a ver-number appended so that differences can be reverted for playback)
