How to perform consensus inside the narwhal dag on the output of execution?

[piersy]

Description

It would be nice to be able to leverage the DAG based consensus within narwhal for reaching consensus on the execution result (from now on referred to as XR for brevity) of transactions ordered by narwhal.

Currently it looks like this is not implemented because at a minimum some extra data would need to be included in the DAG probably inside collections, and right now a collection seems to be just a single batch message and batch messages only contain transactions and a digest. https://github.com/MystenLabs/narwhal/blob/6e86be42032de550764368c4a8a66e1472c68445/types/proto/narwhal.proto#L35-L38

I see 2 possible approaches to this (of course there are probably many more), both assume that the XRs are included in collections.

• Expect the XRs to be included in a collection some number of rounds after a collection is selected by the DAG based consensus(tusk/bullshark/... etc). Nodes now only certify collections at the required round with XRs that match theirs. Once a collection that includes the XR receives 2f+1 certifications the XR can be considered confirmed.
  • Could block DAG construction while nodes perform execution.
  • Because all nodes need to produce execution output in the same round, slow nodes will hold up DAG construction of faster nodes.
  • Because collection validity now depends on a correct execution result, collections with invalid execution results wont get sequenced, meaning that the transactions in that collection that would have previously made it into the DAG will get dropped.
• Nodes include the XR in a collection immediately after completing execution. Certification of a collection does not take into account the XR (if any). The XR is considered confirmed when the DAG based consensus selects a collection to be executed whose sub DAG contains collections from at least 2f+1 distinct nodes with a matching XR.
  • This approach allows for DAG construction to proceed irrespective of how long execution takes.
  • This approach includes all received transactions in the DAG, irrespective of the outcome of execution.