I like the idea of focusing on providing trustless commitment infrastructure. Here is a high-level pen and paper strawman of one way to approach implementing the pessimistic block validity approach.
The plan is to first define a representation of a commitment in protocol. Then have attesters evaluate the representation to enforce it.
In protocol representation
Let’s start with the whole block auction example. In this case, we have between the proposer and the winning bidder Bob a series of promises to do things by certain time.
- Bob promises to produce a signed block B by time \delta
- Proposer promises to propose B as the next block
- Bob promises to pay proposer X ETH when B becomes the next block
And what happens if promises are not kept.
- If Bob failed a promise, he needs to pay
- If Proposer failed a promise, he needs to pay
Generalizing this a bit. We have between proposer and Bob
- a finite series of action to be performed
- state changes from successful actions
- time limit to perform an action or dependencies between actions
- penalty for failure to perform an action successfully
I think 1-4 covers a sufficiently large space of commitments, at least all the ones I can think of. 
If we assume the coverage is sufficient, then the next step would be to turn 1-4 into something computable within protocol. This is mostly straightforward with 1 subtle point. There are 2 types of actions.
- For some actions, all we care about is the end state. For example, for the action of producing a block, all we care about is whether we got a block signed by Bob or not. We don’t care if Bob actually built the block or subcontracted the building to someone else. For these actions, a check on the end state is sufficient to determine if the action has been successfully performed.
- For the rest, the end state alone is not sufficient to determine if an action has been successfully performed. For example, for the action Bob pays proposer X ETH, it’s not sufficient to check the end balance of Bob and proposer because there could be multiple ways to reach that end balance and not all ways are desirable.
Due to this difference, we need different ways to handle the 2 types of actions. With that in mind, here is one way represent 1-4 in protocol. We define a representation V of a commitment as follows.
- Path dependent actions: pre-agreed upon transactions between parties to the commitment. An example would be a payment transaction from a builder to the proposer. This captures the parts of a commitment where the action end state alone is insufficient to determine if an action has been performed successfully. Each transaction carries a signature that’ll identify it within a block.
- Validity assertions: pre-agreed upon validity assertions represented as code that takes blockchain states (ex. block / messages / slot number) and signatures of transactions in 1 as input and returns True / False / NA. True iff assertion is true. False iff assertion is false. NA iff assertion can’t be evaluated from the input. For example, an assertion might be missing a dependency or can’t be evaluated at the current time. This captures the parts of a commitment where the action end state alone is sufficient to determine if an action has been performed successfully. I think we can further constraint the code to be pure in the functional programming sense. So it should have no visible side effects and always return the same value for the same input.
- Dependencies: A DAG representing pre-agreed upon dependencies between validity assertions. Nodes are assertions. Edges are dependencies. Note that because signature of transactions in 1 can be inputs to code in 2. Some dependencies involving transactions in 1 can be modeled in the DAG if we choose.
- Penalties: pre-agreed upon code that executes if one or more validity assertions return False. For example, if a builder fails to deliver, he still pays.
We say V is satisfied iff all validity assertions evaluate to True before the commitment expires.
With this representation in mind, we can modify Vitalik’s Two-slot PBS proposal to implement commitment enforcement of a single block commitment between proposer and 1 other party as follow. Let me know if I’m on or close to the right path.
Sequence of events in a slot pair
slot 0
- Proposer enters into a commitment with Bob and publishes a beacon block containing V and another block P containing the penalties.
- Attesters evaluate the DAG in V starting at the “root” nodes and in breath-first order, stop when either getting a False or blocked by NA on all further evaluations, vote for the beacon block unless an assertion returned False. If an assertion retuned False, vote for P.
slot 1
- If enough attesters in slot 0 voted for P, then P becomes the next block.
- Otherwise, Bob sees enough attesters voted for V and publishes an intermediate block containing promised content and as many attestations on V as he can find.
- Attesters evaluate the DAG in V and vote for the intermediate block iff all assertions return True. Otherwise vote for P.
- Aggregation of intermediate block attestations
- Bidding starts for the next slot pair
I think this is generalizable to enforcing multiple parallel commitments between proposer and multiple parties. The main issue there appears to be we need a generic way to combine the outputs of the commitments into a single block. This is similar as the new “template” block feature mentioned in the main post. It’s a separate problem that I’m not addressing here.
Another open issue is around penalty execution failures. Do we leave it up to the parties entering into a commitment or provide some guarantee in protocol? More thinking is needed there.
Now let’s do a couple of examples to make this more concrete.
Example 1
Basic whole block auction: assume Bob is the winning bidder. Then V consists of
- Path dependent actions: payment transaction from Bob to the proposer. I assume Bob ensures that this transaction only executes successfully in his block.
- Validity assertions:
a. View of attester at time \delta in slot 1 contains block B signed by Bob (Bob publishes in time)
b. Fork choice output for attester at time \delta in slot 1 is B (only allows Bob to build the block)
c. B contains the payment transaction from Bob to the proposer and the transaction succeeded - Dependencies: a → b → c
- Penalties:
if 2a or 2c returns False (Bob fails his part of the commitment) Bob pays the proposer else if 2b returns False (Proposer fails its commitment) proposer is slashed
Example 2
Block SNARK proof auction: assume Bob is the winning bidder. Then V consists of
- Path dependent actions:
a. payment transaction from proposer to Bob
b. penalty payment transaction from Bob to proposer - Validity assertions:
a. if view of attester at time \delta in slot 1 contains verified SNARK signed by Bob (Bob publishes in time) and
b. Fork choice output for attester at time \delta in slot 1 contains the payment transaction 1a and the transaction succeeded - Dependencies: a → b
- Penalties:
if 2b returns False (proposer doesn't pay) execute transaction 1a (enforce proposer payment) // note that if we reach here, Bob is guaranteed to be paid if 2a returns False (no SNARK) execute transaction 1b (penalizes Bob)
There are some high-level points that needs more thinking and clarification and many important details that need to be worked out. But this is already getting long. I’d to get some feedback as I think more about it.
Thanks for reading!