We can only really speak about the earliest writing we know of and that basically requires writing in stone.
We have to remember that we only ever have a squinting view at the past because >99% not made from stone of everything has rotted.
I have no doubt that we were writing on paper-like substances long, long before rock carving, but there's simply no remaining evidence of it the we know of.