"And the next thing you know, you’re at the zoo, shaving a yak, all so you can wax your car."

That said, it depends on your goals. Writing pragmatic, limited test cases for protocols is super hard, due as you say to the lack of constraints.

But if your goal from the outset is to write a definitive, exhaustive test suite then it's a far more mechanical task (much the way that writing a chess AI is hard if you want it to run on a desktop computer, but writing a program to play perfect chess only requires a simple understanding of graph searching if you don't care how fast it is.) Just start from the start of the protocol and work your way through one statement of a time, enumerate all the different ways that an implementation could cock it up, and write a test for each. Of course there are still engineering decisions to be made but you don't have to pick the perfect solution to each. A solution is enough, you (or someone else) can always improve it later.