Generalized History Commitment Backend

Background

Today in BOLD, challenges can have subchallenges, and we have a total of 3 levels. We do this because at each challenge, validators have to commit to N state roots of a block's history, which can be very expensive to compute. For example, computing 2048 machine hashes for the execution of a block and collecting them takes around 5 minutes on a modern MacBook Pro.

The way BOLD interfaces with a Nitro backend is via an interface called an L2StateProvider, which gives BOLD Merkleized commitments to an L2 history at a specific message number, and optionally, at specific opcode ranges or opcodes within that message.

For example: if we want to get a history commitment at message number 1 to 2, and for big step range 100 to 101, and for opcodes 0 to 1024 in that range, we would call:

SmallStepCommitmentUpTo(
    ctx context.Context,
    wasmModuleRoot common.Hash,
    messageNumber,
    bigStep,
    toSmallStep uint64,
) (commitments.History, error)

as

SmallStepLeafCommitmentUpTo(
    ctx,
    wasmModuleRoot,
    1,   // message number
    100, // big step number
    1024, // to small step number
)

Problem

The problem is: how do we generalize this to N different challenge levels in the cleanest way possible? Here's an idea:

// MessageNumberRange defines a range of L2 message heights.
type MessageNumberRange struct {
    From uint64
    To   uint64
}

// ClaimHeight defines a range of heights within a challenge
// level. Each challenge leaf makes a certain claim about a
// an edge (or an assertion) at a parent level, and we can
// use this to represent a request.
//
// If `To` is None, it will retrieve all hashes
// within that challenge level.
type ClaimHeight struct {
    From uint64
    To   option.Option[uint64]
}

// HistoryCommitmentProvider can produce history commitments
// at any level of granularity within a range of L2 messages,
// or if claim heights are provided, to machine hashes within
// a message.
type HistoryCommitmentProvider interface {
    HistoryCommitment(
        ctx context.Context,
        wasmModuleRoot common.Hash,
        messageNumberRange MessageNumberRange,
        claimHeights ...ClaimHeight,
    ) (commitments.History, error)
}

For example, if we want to get a history commitment of all state roots in the range of L2 messages 100 to 1024, we would do:

HistoryCommitment(
    ctx,
    wasmModuleRoot,
    MessageNumberRange{From: 100, To: 1024},
) (commitments.History, error)

If we want to get a commitment to all the machine hashes
at challenge level 1, from message 100 to 101:

HistoryCommitment(
    ctx,
    wasmModuleRoot,
    MessageNumberRange{From: 101, To: 101},
    ClaimHeight{
        From: 0,
        To: option.None(),
    },
) (commitments.History, error)

If we want to get a commitment to all machine hashes at level 2, from message 100 to 101 and subchallenge range 2000 to 2001:

HistoryCommitment(
    ctx,
    wasmModuleRoot,
    MessageNumberRange{From: 101, To: 101},
    ClaimHeight{
        From: 2000,
        To: option.Some(2001),
    },
    ClaimHeight{
        From: 0,
        To: option.None(),
    },
) (commitments.History, error)

Although not too ergonomic, it can be made more readable using variables or helper functions to express certain intents:

func allStateRoots() ClaimHeight {
    return ClaimHeight{
        From: 0,
        To:   option.None[uint64](),
    }
}

messageNumberRange := MessageNumberRange{
    From: 1,
    To:   2,
}
blockChallengeRange := ClaimHeight{
    From: 1,
    To:   option.Some(uint64(2)),
}
bigStepRange := ClaimHeight{
    From: 999,
    To:   option.Some(uint64(1000)),
}
smallStepChallengeLeaf, _ := provider.HistoryCommitment(
    ctx,
    wasmModuleRoot,
    messageNumberRange,
    bigStepRange,
    allStateRoots(),
)