zkSync Era - Matter Labs

The MESSAGES EVENTS FILTER circuit (log_sorter) is not enforcing the head state of the initial queue received as input to be zero. Even though the LOG DEMULTIPLEXER circuit gives as output all queues that were initially empty, already enforcing the head state to be zero, it is essential to ensure it is atomically checked in each circuit, regardless of where the input is coming from.

Code Location

log_sorter/mod.rs

let structured_input_witness = project_ref!(witness, closed_form_input).cloned();
let initial_queue_witness = project_ref!(witness, initial_queue_witness).cloned();
let intermediate_sorted_queue_state =
    project_ref!(witness, intermediate_sorted_queue_state).cloned();
let sorted_queue_witness = project_ref!(witness, sorted_queue_witness).cloned();

let mut structured_input = EventsDeduplicatorInputOutput::alloc_ignoring_outputs(
    cs,
    structured_input_witness.clone(),
)?;

Boolean::enforce_equal(cs, &structured_input.start_flag, &Boolean::constant(true))?;

let mut initial_queue = StorageLogQueue::from_raw_parts(
    cs,
    structured_input
        .observable_input
        .initial_log_queue_state
        .head_state,
    structured_input
        .observable_input
        .initial_log_queue_state
        .tail_state,
    structured_input
        .observable_input
        .initial_log_queue_state
        .num_items,
)?;

// dbg!(initial_queue.clone().into_state().create_witness());

if let Some(wit) = initial_queue_witness {
    initial_queue.witness = wit;
}

SOLVED: The MatterLabs team solved the issue by enforcing the initial queue head state to zero.

Commit ID : b0a79356613655bddccaab3b89dbf1142b5483fb

Within the LOG DEMULTIPLEXER circuit (demux_log_queue) the demultiplex_storage_logs_inner function is declared but never used. The demultiplex_storage_logs_inner_optimized function is used instead.

Code Location

demux_log_queue/mod.rs

pub fn demultiplex_storage_logs_inner<
    E: Engine,
    CS: ConstraintSystem<E>,
    R: CircuitArithmeticRoundFunction<E, 2, 3, StateElement = Num<E>>,
>(
    cs: &mut CS,
    mut storage_log_queue: StorageLogQueue<E>,
    round_function: &R,
    limit: usize,
) -> Result<[StorageLogQueue<E>; NUM_SEPARATE_QUEUES], SynthesisError> {
    assert!(limit <= u32::MAX as usize);

    let mut optimizer = SpongeOptimizer::new(round_function.clone(), 3);

    let mut rollup_storage_queue = StorageLogQueue::empty();
    // let mut porter_storage_queue = StorageLogQueue::empty();
    let mut events_queue = StorageLogQueue::empty();
    let mut l1_messages_queue = StorageLogQueue::empty();
    let mut keccak_calls_queue = StorageLogQueue::empty();
    let mut sha256_calls_queue = StorageLogQueue::empty();
    let mut ecdsa_calls_queue = StorageLogQueue::empty();

    const SYSTEM_CONTRACTS_OFFSET_ADDRESS: u16 = 1 << 15;

    const KECCAK256_ROUND_FUNCTION_PRECOMPILE_ADDRESS: u16 = SYSTEM_CONTRACTS_OFFSET_ADDRESS + 0x10;
    const SHA256_ROUND_FUNCTION_PRECOMPILE_ADDRESS: u16 = 0x02; // as in Ethereum
    const ECRECOVER_INNER_FUNCTION_PRECOMPILE_ADDRESS: u16 = 0x01; // as in Ethereum

    let keccak_precompile_address = UInt160::from_uint(u160::from_u64(
        KECCAK256_ROUND_FUNCTION_PRECOMPILE_ADDRESS as u64,
    ));
    let sha256_precompile_address = UInt160::from_uint(u160::from_u64(
        SHA256_ROUND_FUNCTION_PRECOMPILE_ADDRESS as u64,
    ));
    let ecrecover_precompile_address = UInt160::from_uint(u160::from_u64(
        ECRECOVER_INNER_FUNCTION_PRECOMPILE_ADDRESS as u64,
    ));

    for _ in 0..limit {
        let execute = storage_log_queue.is_empty(cs)?.not();

        // let n = cs.get_current_step_number();
        let popped = storage_log_queue.pop_first(cs, &execute, round_function)?;
        // dbg!(cs.get_current_step_number() - n); // 291

        let is_storage_aux_byte =
            Num::equals(cs, &aux_byte_for_storage().inner, &popped.aux_byte.inner)?;
        let is_event_aux_byte =
            Num::equals(cs, &aux_byte_for_event().inner, &popped.aux_byte.inner)?;
        let is_l1_message_aux_byte =
            Num::equals(cs, &aux_byte_for_l1_message().inner, &popped.aux_byte.inner)?;
        let is_precompile_aux_byte = Num::equals(
            cs,
            &aux_byte_for_precompile_call().inner,
            &popped.aux_byte.inner,
        )?;

        let is_keccak_address = UInt160::equals(cs, &keccak_precompile_address, &popped.address)?;
        let is_sha256_address = UInt160::equals(cs, &sha256_precompile_address, &popped.address)?;
        let is_ecrecover_address =
            UInt160::equals(cs, &ecrecover_precompile_address, &popped.address)?;

        let is_rollup_shard = popped.shard_id.inner.is_zero(cs)?;

        let execute_rollup_storage =
            smart_and(cs, &[is_storage_aux_byte, is_rollup_shard, execute])?;
        let execute_porter_storage =
            smart_and(cs, &[is_storage_aux_byte, is_rollup_shard.not(), execute])?;
        Boolean::enforce_equal(cs, &execute_porter_storage, &Boolean::constant(false))?;
        let execute_event = smart_and(cs, &[is_event_aux_byte, execute])?;
        let execute_l1_message = smart_and(cs, &[is_l1_message_aux_byte, execute])?;
        let execute_keccak_call =
            smart_and(cs, &[is_precompile_aux_byte, is_keccak_address, execute])?;
        let execute_sha256_call =
            smart_and(cs, &[is_precompile_aux_byte, is_sha256_address, execute])?;
        let execute_ecrecover_call =
            smart_and(cs, &[is_precompile_aux_byte, is_ecrecover_address, execute])?;

        // let n = cs.get_current_step_number();
        rollup_storage_queue.push_with_optimizer(
            cs,
            LogType::RollupStorage as u64,
            &popped,
            &execute_rollup_storage,
            &mut optimizer,
        )?;
        // porter_storage_queue.push_with_optimizer(cs, LogType::PorterStorage as u64, &popped, &execute_porter_storage, &mut optimizer)?;
        events_queue.push_with_optimizer(
            cs,
            LogType::Events as u64,
            &popped,
            &execute_event,
            &mut optimizer,
        )?;
        l1_messages_queue.push_with_optimizer(
            cs,
            LogType::L1Messages as u64,
            &popped,
            &execute_l1_message,
            &mut optimizer,
        )?;
        keccak_calls_queue.push_with_optimizer(
            cs,
            LogType::KeccakCalls as u64,
            &popped,
            &execute_keccak_call,
            &mut optimizer,
        )?;
        sha256_calls_queue.push_with_optimizer(
            cs,
            LogType::Sha256Calls as u64,
            &popped,
            &execute_sha256_call,
            &mut optimizer,
        )?;
        ecdsa_calls_queue.push_with_optimizer(
            cs,
            LogType::ECRecoverCalls as u64,
            &popped,
            &execute_ecrecover_call,
            &mut optimizer,
        )?;
        // dbg!(cs.get_current_step_number() - n); // 96

        // let n = cs.get_current_step_number();
        optimizer.enforce(cs)?;
        // dbg!(cs.get_current_step_number() - n); // 338

        let expected_bitmask_bits = [
            is_storage_aux_byte,
            is_event_aux_byte,
            is_l1_message_aux_byte,
            is_precompile_aux_byte,
        ];

        let (is_bitmask, all_flags_are_false) =
            check_if_bitmask_and_if_empty(cs, &expected_bitmask_bits)?;
        can_not_be_false_if_flagged(cs, &is_bitmask, &Boolean::Constant(true))?;
        can_not_be_false_if_flagged(cs, &all_flags_are_false.not(), &execute)?;
    }

    storage_log_queue.enforce_to_be_empty(cs)?;

    let all_queues = [
        rollup_storage_queue,
        events_queue,
        l1_messages_queue,
        keccak_calls_queue,
        sha256_calls_queue,
        ecdsa_calls_queue,
    ];

    Ok(all_queues)
}

SOLVED: The MatterLabs team solved the issue by removing the unused function.

Commit ID : 06c2e76546369fb112d8ac14fb5388154857435b

The MERKLEIZER circuit (merkleize_l1_messages) does not enforce the initial queue to be empty right after popping all elements. Even though it does it at the end of the circuit, as this circuit is resource-consuming while computing the linear hash and the Merkle tree hash, it would be useful to enforce it before all the hashing functionality for better readability of the overall code and optimization.

Code Location

merkleize_l1_messages/merkleize.rs

for chunk in linear_hash_input[4..].chunks_exact_mut(MESSAGE_SERIALIZATION_BYTES) {
    let can_pop = initial_queue.is_empty(cs)?.not();
    let item = initial_queue.pop_first(cs, &can_pop, round_function)?;
    let serialized = item.serialize(cs)?;
    assert_eq!(chunk.len(), serialized.len());
    for (dst, src) in chunk.iter_mut().zip(serialized.iter()) {
        *dst = Byte::conditionally_select(cs, &can_pop, src, dst)?;
    }
}

let linear_hash = if output_linear_hash {
    println!(
        "Computing linear hash over {} bytes",
        linear_hash_input.len()
    );
    let pubdata_hash = tree_hasher.hash(cs, &linear_hash_input)?;
    let pubdata_hash_as_bytes32 = Bytes32::from_bytes_array(&pubdata_hash);

    pubdata_hash_as_bytes32
} else {
    Bytes32::empty()
};

// a little bit tricky: unsafe cast, but we checked the length, and ABI wise it's guaranteed
// later on we can use split_array_ref

let leafs_only_bytes = &linear_hash_input[4..];
assert!(leafs_only_bytes.len() % MESSAGE_SERIALIZATION_BYTES == 0);

let mut leafs = vec![];
for chunk in leafs_only_bytes.chunks_exact(MESSAGE_SERIALIZATION_BYTES) {
    let leaf_encoding: [_; MESSAGE_SERIALIZATION_BYTES] = chunk.to_vec().try_into().unwrap();
    leafs.push(leaf_encoding);
}

println!("Computing tree over {} leafs", leafs.len());

let calculated_merkle_root =
    circuit_compute_merkle_root_from_leafs_generic::<_, _, H, ARITY>(cs, &leafs, tree_hasher)?;

initial_queue.enforce_to_be_empty(cs)?;

ACKNOWLEDGED: The MatterLabs team acknowledged this issue. It will be addressed while moving to the new proof system.

As i is an uint256, it is already initialized to 0. uint256 i = 0 reassigns the 0 to i which wastes gas.

Code Location

Verifier.sol

• Line 134: for (uint256 i = 0; i < public_inputs.length; i = i.uncheckedInc()) {
• Line 139: for (uint256 i = 0; i < STATE_WIDTH; i = i.uncheckedInc()) {
• Line 164: for (uint256 i = 0; i < proof.quotient_poly_parts_commitments.length; i = i.uncheckedInc()) {
• Line 172: for (uint256 i = 0; i < proof.state_polys_openings_at_z.length; i = i.uncheckedInc()) {
• Line 178: for (uint256 i = 0; i < proof.state_polys_openings_at_z_omega.length; i = i.uncheckedInc()) {
• Line 183: for (uint256 i = 0; i < proof.gate_selectors_openings_at_z.length; i = i.uncheckedInc()) {
• Line 188: for (uint256 i = 0; i < proof.copy_permutation_polys_openings_at_z.length; i = i.uncheckedInc()) {

Plonk4VerifierWithAccessToDNext.sol

• Line 144: for (uint256 i = 0; i < vk.num_inputs; i = i.uncheckedInc()) {
• Line 148: for (uint256 i = 0; i < STATE_WIDTH; i = i.uncheckedInc()) {
• Line 164: for (uint256 i = 0; i < proof.quotient_poly_parts_commitments.length; i = i.uncheckedInc()) {
• Line 171: for (uint256 i = 0; i < proof.state_polys_openings_at_z.length; i = i.uncheckedInc()) {
• Line 175: for (uint256 i = 0; i < proof.state_polys_openings_at_z_omega.length; i = i.uncheckedInc()) {
• Line 178: for (uint256 i = 0; i < proof.gate_selectors_openings_at_z.length; i = i.uncheckedInc()) {
• Line 181: for (uint256 i = 0; i < proof.copy_permutation_polys_openings_at_z.length; i = i.uncheckedInc()) {
• Line 301: for (uint256 i = 0; i < lagrange_poly_numbers.length; i = i.uncheckedInc()) {
• Line 307: for (uint256 i = 0; i < vk.num_inputs; i = i.uncheckedInc()) {
• Line 324: for (uint256 i = 0; i < proof.copy_permutation_polys_openings_at_z.length; i = i.uncheckedInc()) {
• Line 448: for (uint256 i = 0; i < proof.state_polys_openings_at_z.length; ) {
• Line 472: for (uint256 i = 0; i < STATE_WIDTH - 1; i = i.uncheckedInc()) {
• Line 558: for (uint256 i = 0; i < STATE_WIDTH - 1; i = i.uncheckedInc()) {
• Line 613: for (uint256 i = 0; i < STATE_WIDTH; i = i.uncheckedInc()) {
• Line 622: for (uint256 i = 0; i < STATE_WIDTH - 1; i = i.uncheckedInc()) {

PairingsBn254.sol

• Line 240: for (uint256 i = 0; i < elements; ) {

ACKNOWLEDGED: The MatterLabs team acknowledged this issue.