Non equivocation in Narwhal Mempool protocol

General
1

How does Narwhal ensure non-equivocation property from just a certificate forming from n-f validators? I know that from quorum intersection and honest validators signing only one message from each validator at each round, one can ensure that Byzantine nodes cannot form two difference certificates at each round.

However, assume we have 4 validators (A,B, C, and D), where D is Byzantine. If D gets signatures from all validators, including itself, it can form two certificates for the same vertex in each round. Suppose they are in round r. D can send a certificate to A and B using A, B, and D signatures and a certificate to C using A, C, and D signatures. Here, A and B receive different information from C; although the content of a vertex is the same, the reference or edges to the vertex are different, which can make the causal history between A and B vs. C different. I think each validator can ask other validators (A and B ask for C) for the certificate of that block to verify that it is matched. However, this results in increased communication complexity.

1 Like
2

Hey thanks for the question, this is George from Mysten.

I think each validator can ask other validators (A and B ask for C) for the certificate of that block to verify that it is matched. However, this results in increased communication complexity.

So the block formation in Narwhal prevents equivocating blocks:

  • Each block needs to be certified for its author and round, and as you mention this means that only one block from a validator at any round can have a certificate. So there cannot be two certificates for the same author / round.

  • Validators indeed check the certificates of past blocks before including them into their blocks as parents, and it is indeed the case that other validators check that all parents of a block are valid certificates before signing the block to certify it. So a certified block only points to other certified blocks and its full history cannot contain equivocations.

Does that help?

1 Like