I feel like this sort of thing already exists? or is it not that simple to do
I'm encoding messages into bitcoin addresses but that dude seems to have done it the way only miners can do it. When a miner finds a block, it can always put some message with it similarly to how Satoshi did it.