## 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: ```go SmallStepCommitmentUpTo( ctx context.Context, wasmModuleRoot common.Hash, messageNumber, bigStep, toSmallStep uint64, ) (commitments.History, error) ``` as ```go 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: ```go // 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: ```go 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: ```go 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: ```go 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: ```go! 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(), ) ```