How to implement Byzantine Single-decree Paxos?

I have implemented Single-decree Paxos, and have shown it not to fail in a Monte Carlo network simulator. I followed "Paxos Made Simple" http://lamport.azurewebsites.net/pubs/paxos-simple.pdf

I have read: Castro, Miguel; Liskov, Barbara (February 1999). "Practical Byzantine Fault Tolerance" http://pmg.csail.mit.edu/papers/osdi99.pdf

As far as I understand, the paper describes a Byzantine Multi-Paxos algorithm. It includes complexity which I hope I don't need for the single-decree use-case, such as Views and Leaders.

What is required to turn the Single-decree Paxos protocol into a Byzantine Single-decree Paxos protocol?

i.e. Is adding public key signatures to messages, and waiting for f+1 acceptors to agree, sufficient? Or do I need a pre-prepare phase too?

The paper you linked (thanks for that) has this statement "All replicas know the others’ public keys to verify signatures". This means that the protocol uses standard public/private keys for verification.

The pub/pri approach is safe under two assumptions: a) there is a way for each node to safely learn about public keys of other nodes and b) each node has its own private key and the key is secured.

The rest of the approach is standard approach for messages verification: when a node A wants to send a message to node B:

• Node A creates a message
• Node A creates hash of the message
• Node A encrypts the hash with its own private key (we will call encrypted hash - message signature)
• Node A sends to Node B: [message, message signature, from: Node A]
• Node B receives all three parts and verifies them
• Node B creates hash is the message
• Node B uses Node A's public key to decrypt signature of the message
• Node B compares hash from the message and the decrypted hash: if they are the same, then the message for sure came from Node A

That pretty much guarantees that messages came from right nodes.