Lamport's Byzantine Consensus algorithm with Signatures

Introduction

In my previous articles I introduced Lamport’s Byzantine Generals problem and implemented the oral-messages algorithm in Python:

• Lamport's Byzantine Generals algorithm in Python — a basic implementation of the recursive majority protocol.
• A more general implementation of Lamport's Byzantine Consensus algorithm in Python — a refactored version with support for arbitrary values, multiple initiators, and concurrent rounds.
• Applications of Byzantine Consensus — a discussion of where the oral-messages algorithm does and does not apply in practice.

This time, we look at Lamport’s second solution: Byzantine Consensus with signatures.

In the oral-messages model, each message is just a claim:

• Node 1 says, “Node 0 told me to attack.”
• Node 2 then says, “Node 1 told me that Node 0 told them to attack.”

The algorithm works, but traitors can flip values arbitrarily, and to overcome that we require $N \geq 3M+1$ nodes and an exponential message cascade.

With signatures, the situation changes dramatically. Each message is cryptographically signed by its author, and signatures cannot be forged by traitors. Instead of passing along claims about what others said, nodes can forward the original signed message itself, appending their own signature. This removes the possibility of equivocation: if a correct node signs “attack”, no traitor can make it look like it signed “retreat.”

This simple addition radically reduces both the requirements and the complexity of the algorithm.

The code is on Github: mtrencseni/dca/byzantine/sign

Algorithm

The signed version of Lamport’s algorithm works as follows:

1. Node requirement. Agreement among the honest nodes requires only $N \geq M + 2$. That means even if there are many traitors, as long as two honest nodes exist, they can still agree.
2. Signature verification. Any message with an invalid signature is discarded immediately.
3. Forwarding. If the signatures check out, the node accepts the message, adds the king’s proposed value to its set of received values, and forwards the message with its own signature appended.
4. Deduplication. If a node has already seen the same signed value, duplicate messages can be ignored. In practice this collapses the exponential message tree of the oral-messages algorithm to something much leaner.

5. Decision rule. Once the cascade ends, each honest node applies a common choice() function to its set of received values. A simple rule is:

   • If there is exactly one value, return it.
   • Otherwise (zero or multiple values), return "retreat".

Let’s walk through an example with $(N, M) = (4, 2)$ — 2 traitors and 2 honest nodes:

1. Case 1: Honest king. The king signs “attack” and sends it to everyone. Traitors cannot forge his signature, so the only choice they have is to forward the real message or drop it. Either way, the honest nodes both receive “attack” and decide “attack.”
2. Case 2: Traitor king. Suppose the king signs “attack” to one honest node and “retreat” to the other. The honest nodes forward what they received, so eventually both hold the set {“attack”, “retreat”}. Applying choice(), they both output “retreat.”
3. Case 3: Partial delivery. If the king only sends to one honest node, that node forwards the message to the other. Both end up agreeing on the same value.

The crucial property is: because traitors cannot forge signatures, all honest nodes end up with the same set of signed values. Their decision function may not always pick the “best” value, but it guarantees consistency.

Why Signatures Matter

Compared to the oral-messages algorithm:

• Weaker requirement. Oral messages require $N \geq 3M+1$; signed messages only need $N \geq M+2$.
• Fewer messages. With signatures, the recursive cross-checking is unnecessary. Each valid message is self-authenticating.
• Simpler logic. Instead of recursive majority, we only need a deterministic choice() function over a set of values.

This is why Lamport observed that with unforgeable signed messages, the problem is solvable for any number of generals and traitors.

Code

Disclaimer: This is a toy implementation intended for learning. While it uses digital signatures, it is not suitable for production use.

Implementing the signed version of Lamport’s Byzantine Consensus algorithm is relatively straightforward, and I’ve built it on top of the simple oral-messages implementation from the earlier article. There is one small deviation: in theory, if a node receives a value it has already seen, it can effectively drop that message and not send it onward, thus cutting of that sub-tree of the message cascade. I chose not to do this. Instead, every message is always forwarded, ensuring the full cascade runs to completion. This way, generals can deterministically know when a round has finished, without relying on timeouts or additional coordination.

First, the nodes have to generate their own private keys and other nodes have to be able to retrieve their public keys so their signatures can be verified. I use the nacl package, which uses the Ed25519 algorithm:

from nacl import signing

private_key = signing.SigningKey.generate()
public_keys_cache = {}
public_keys_cache[id] = bytes(private_key.verify_key)

Nodes can retrieve each other's public keys through an HTTP endpoint:

@app.route("/public_key")
def public_key():
    return jsonify({"node_id": id, "public_key": base64.b64encode(bytes(private_key.verify_key)).decode()})

A helper function to retrieve each other's public keys with caching:

def get_public_key(node_id):
    global public_keys_cache
    if node_id in public_keys_cache:
        return public_keys_cache[node_id]
    public_key_b64 = requests.get(f"http://127.0.0.1:{8000+node_id}/public_key").json()["public_key"]
    public_key = base64.b64decode(public_key_b64)
    public_keys_cache[node_id] = public_key
    return public_key

When a message is received, the sender also sends their signature along in the URL. Then, this outermost signature is verified:

@app.route("/order/<signature_b64>", methods=["POST"])
def order(signature_b64):
    msg = request.get_json()
    if not verify_signature(msg["node_id"], msg, signature_b64):
        return "Signature does not match", 401
    process_message(msg["path"], msg)
    message_cascade(msg, signature_b64)
    if all_messages_received():
        global done
        done = True
    return jsonify(ok=True)

The subsequent process_message() unpacks the message, recursively verifying the signatures of included messages, until it gets to the innermost message (sent by the king). The contained value is then added to received_values:

def process_message(path, msg):
    if "value" in msg:
        value = msg["value"]
        received_values[tuple(path)] = value
    elif "msg" in msg:
        contained_msg = msg["msg"]
        if not verify_signature(contained_msg["node_id"], contained_msg, msg["signature_b64"]):
            return 
        else:
            process_message(path, msg["msg"])

The following message_cascade() is the same logic as in the original oral-messages version of the algorithm:

def message_cascade(msg, signature_b64):
    path = list(msg["path"])
    k = 1 + m - len(path)
    if k > 0:
        broadcast(path + [id], msg, signature_b64)

The code above uses verify_signature():

def verify_signature(node_id, payload, signature_b64):
    public_key = get_public_key(node_id)
    verify_key = signing.VerifyKey(public_key)
    try:
        signature_b64_padded = signature_b64 + "=" * (-len(signature_b64) % 4)
        verify_key.verify(canonical_json(payload), base64.urlsafe_b64decode(signature_b64_padded))
        return True
    except BadSignatureError:
        return False

Finally, the decision logic is straightforward:

def choice(vals):
    if len(vals) == 1:
        return next(iter(vals))
    # retreat if there are no values
    # retreat if there are more than 1 values (=the king is a traitor)
    return "retreat"

@app.route("/decide", methods=["POST"])
def decide():
    assert(done)
    global value
    if value is None:
        value = choice(set(received_values.values()))
    return jsonify(value=value)

Note that the message cascade logic and number of messages sent is the same as before.

Runs

I have also modified the driver program, so both N and M can be passed. A run with $(N, M) = (5, 3)$

$ python3 driver.py 5 3
Traitors: {2, 3, 4}
Decisions:
General 0 decided attack
General 1 decided attack
General 2 is a traitor
General 3 is a traitor
General 4 is a traitor
SUCCESS: all non-traitor generals decided to attack!

A run with $(N, M) = (10, 4)$

$ python3 driver.py 10 4
Traitors: {0, 1, 3, 4}
Decisions:
General 0 is a traitor
General 1 is a traitor
General 2 decided retreat
General 3 is a traitor
General 4 is a traitor
General 5 decided retreat
General 6 decided retreat
General 7 decided retreat
General 8 decided retreat
General 9 decided retreat
SUCCESS: all non-traitor generals decided to retreat!

As in the previous implementation, if the king is a traitor, it sends conflicting messages (now signed), in which case "retreat" should be the outcome.

Conclusion

The signed-messages version of Lamport’s Byzantine Consensus algorithm shows how adding cryptography changes the game. The oral-messages model requires a large majority of honest participants and an exponential message cascade. With signatures, the requirements collapse: as long as two honest nodes exist, they will agree.

This insight is more than historical curiosity. It foreshadows how modern Byzantine Fault Tolerant protocols — PBFT, Tendermint, HotStuff — lean heavily on digital signatures. By guaranteeing authenticity and preventing equivocation, signatures enable consensus to be reached with far fewer messages and under much weaker assumptions.

In practice, we don’t use Lamport’s signed algorithm directly, but its lesson is enduring: cryptography makes consensus simpler, faster, and stronger.

Appendix

As already mentioned above, this is not a production ready implementation. Some of the reasons:

• Key substitution / MITM: Fetching /public_key over plain HTTP lets an on-path attacker swap in their own key. They can then rewrite traffic and re-sign it so verification still “passes.”
• No binding of identity to key: Nothing cryptographically ties node_id to the public key. An attacker who controls the network can impersonate a node.
• Traitor nodes can fake keys: Traitor nodes could return different public keys to different honest nodes, causing them to think the other honest one is a traitor.
• No TLS: Anyone can read/alter requests, replay them, or change targets; i.e. HTTP is used instead of HTTPS.
• No replay defense: the implementation contains nonce fields as an indicator they should be used, but they are not checked. A better method is a pair of (round_id, nonce), where all honest nodes know which round_id to expect.
• Ad-hoc JSON canonicalization: sort_keys=True is okay for Python-to-Python, but floats, Unicode normalization, and number formatting can desync across languages.
• No rotation/revocation: If a private key leaks during the run, an attacker can sign new messages forever. There’s no way to roll keys or mark old ones invalid.
• CPU DoS: Verification is cheap but not free; an attacker could flood /order.
• Nonce quality: we use random instead of secrets, nonces may collide or be guessable.
• Error handling leakage: Detailed error text can aid attackers.
• ...