It’s completely trivial. The obvious and correct place is in the commit object just like author and date and such, since renaming is semantically part of the commit, not the tree:
commit 0123456789abcdef0123456789abcdef01234567
parent fedcba9876543210fedcba9876543210fedcba98
author Nemo <nemo@example.invalid> 1234567890 +0000
committer Nemo <nemo@example.invalid> 1234567890 +0000
rename-from path1.old
rename-to path1.new
rename-from path2.old
rename-to path2.new
Commit message
And you don’t
detect moves (because that’s madness), but require that people record them deliberately, just like every other VCS has done. There’s even git-mv already, it just skips a step that every other VCS’s equivalent command would do. (And technically this all works out because the index is a commit, so you can record the rename normally.)
Of course, all of this assumes that moving a file is a meaningful operation. Perhaps ideally (for most languages and systems) you’d track this in far smaller chunks, so that you can track changes to a function even when it alone was moved to a different file. But things like Git aren’t interested in those kinds of semantics, and work technically at the file level, more or less, so I think it should track renames because in practice straightforward renames are super common, but often also involve other changes that thwart rename detection. Years ago Linus explained why he didn’t like storing moves (someone else has linked it), but I’m largely not sold with his reasoning—the theory of the perfect has hindered the useful, and file renames are commonly meaningful in ways more than he said.