[Narwhal] improve resilience of nodes growing and following DAG

[mwtian]

Currently, the limiting factor to reduce Narwhal round generation speed (hence reducing e2e Narwhal latency) is the resilience of nodes growing and following DAG. It is observed that once more Narwhal rounds are generated per sec, at some limit nodes start to fail behind in following the DAG, resulting in higher e2e latencies. We plan to make the following improvements to help nodes receiving certificate out of order or missing one or more of them to stay up-to-speed with growth of the DAG.

Propagating recently created certificates

• Move Certificate handling from Core into Synchronizer, which allows concurrent processing of certificates and access to metadata.
• When broadcasting created own certificates, allow multiple inflight instead of only keeping the most recent certificate and cancelling the rest.
• Create a buffer to keep track of known certificates that have missing parents, and certificates only known by digests. Their dependencies should be tracked so they can be accepted efficiently when possible.

Improving certificates catchup throughput

• Improve efficiency of certificate verifications during catchup, by verifying higher round certificates and only ensuring digests match for child certificates.
• Flesh out details for chaining certificates from own origin.
• Improve efficiency of certificate fetching by fetching from highest rounds of accepted certificates per origin, instead of trying to fill in certificates within gc_depth.
• Pipeline certificate fetching after verifications are no longer a major factor in catchup time.

[akichidis]

When broadcasting created own certificates, each peer should be sent a bounded list of certificates that they may need, not just the most recently created own certificate.

I assume we'll want to do that only to the nodes who haven't voted for the underlying header, right?

Improve efficiency of certificate verifications during catchup, by verifying higher round certificates and only ensuring digests match for child certificates.

To confirm that child certificate digests match we'll need to have previously the child certificates processed? Trying to see the difference with current approach.

[mwtian]

I assume we'll want to do that only to the nodes who haven't voted for the underlying header, right?

Why is that the case? This should be done against all peers for created certificates that have not been ack'ed, with a max size bound e.g. 100, to avoid the recipient having to rely on the higher latency fetch process.

[mwtian]

To confirm that child certificate digests match we'll need to have previously the child certificates processed? Trying to see the difference with current approach.

The difference is that the previous child certificates do not have to be verified, if their digests are included transitively from verified certificates. The caveat is fetch response served from these data may contain certificates with unverified signatures now, so the recipient of the fetch response needs to be able to handle that.

[mwtian]

Catch up performance will be tracked separately. Currently the bottleneck to catch up performance is payload fetching.