Bus Mapping

Bus mappings

One of the big challenges of building a snark to verify a VM is that you need to be able to read random values / opcodes at any time. To do this we use key-value mappings. Key value mappings are basically random linear combinations of all elements

Plookup key-value mappings

In plookup you can build key-value mappings as follows

def build_mapping():
    keys = [1,3,5]
    values = [2,4,6]
 
    randomness = hash(keys, values)
    
    mappings = []

    for key , value in zip(keys,values):
        mappings.append(key + randomness*value)
    return(mappings)

It can be opened at the cost of 3 plookups

def open_mapping(mappings, keys, values):
    randomness = hash(keys,values)
    index = 1
    # Prover can chose any mapping, key , value
    mapping = plookup(mappings)
    key = plookup(keys)
    value = plookup(values)
    # But it has to satisfy this check
    require(mappings[index] == key[index] + randomness*value[index])
    # with overwhelming probablitiy will not find an invalid mapping.

Bus mapping

bus_mapping[global_counter] = {
    type_flag = ["stack", "memory", "storage"], 
    rw_flag,
    key, 
    value, 
    index: opcode,
    call_id: call_id,
    prog_counter: prog_counter
}

The bus mapping is witnessed by the prover. In the EVM proof, we have to ensure the prover did not include extra variables. To do this, we limit its degree in the L1 EVM and then check every single element in the EVM proof.

The commitment to the bus mapping is a public input to both the state proof and EVM proof.

Select a repo