How is the rock a witness?
Rashi citing Targum Yonasan: It will be for us like the two Luchos ha'Bris, for is written on it similar to 1 all the words that Hashem spoke with us.
Malbim: The rock, with Yehoshua's Sefer inside, will be a witness, just like "Lako'ach Es Sefer ha'Torah ha'Zeh v'Samtem Oso mi'Tzad Aron Bris Hashem
Lev Yitzchak: The Ran (Sanhedrin 78a) says that "Kol" can be the entire matter, or [any] part of it. The Targum here implies that it can be the essence (a concentration).
What words did Hashem speak with them?
Rashi, from Midrash Shmuel 9:4: They are these words that I spoke to you, as Hashem's Shali'ach (so it is as if Hashem spoke with us).
Malbim: They are all Hashem's words in this Sefer, including this Perek ("Ko Amar Hashem" - verse 2).
Lev Yitzchak: They are the 613 Mitzvos. Aseres ha'Dibros are a concentration of them (roughly one part in 60; there are 613 letters from the Aleph of Anochi until the Kaf of Kol
