This paper describes the requirements for electronic commerce protocols in business-to-business markets. A protocol comprises rules for communication between com- munication partners. In the world of electronic commerce such protocols need to be designed for the support of auto- mated communication between information systems of different participants. We want to set a focus on protocols for negotiation processes in electronic procurement. These processes are not supported appropriately in traditional standard protocols like ANSI X.12. We outline the re- quirements for an open and extensible protocol that com- prises electronic negotiation on multiple attributes of a deal.