Attacker can manipulate the sorted queue in log sorter to emit reverted logs and events

[c4-submissions]

Lines of code

https://github.com/code-423n4/2023-10-zksync/blob/1fb4649b612fac7b4ee613df6f6b7d921ddd6b0d/code/era-zkevm_circuits/src/log_sorter/mod.rs#L331-L456

Vulnerability details

Impact

Attacker can manipulate the sorted queue in log sorter, constraints are not strong enough and reverted l1 logs and events can still be emitted.

Proof of Concept

Let's see what we have enforced in this circuit. For a unique timestamp, either there is only a write log, we should add it to the queue; or there is a write log and a rollback log, which means revert took place, we should ignore it.

        // We compare timestamps, and then resolve logic over rollbacks, so the only way when
        // keys are equal can be when we do rollback
        let sorting_key = sorted_item.timestamp;

        // ensure sorting for uniqueness timestamp and rollback flag
        // We know that timestamps are unique accross logs, and are also the same between write and rollback
        let (keys_are_equal, new_key_is_smaller) =
            unpacked_long_comparison(cs, &[previous_key], &[sorting_key]);

        // keys are always ordered no matter what, and are never equal unless it's padding
        new_key_is_smaller.conditionally_enforce_false(cs, should_pop);

At first, we enforce the timestamps in the sorted queue are in ascending orders, which means write log and rollback log of the same timestamp should be adjacent.

        // there are only two cases when keys are equal:
        // - it's a padding element
        // - it's a rollback

        // it's enough to compare timestamps as VM circuit guarantees uniqueness of the if it's not a padding
        let previous_is_not_rollback = previous_item.rollback.negated(cs);
        let enforce_sequential_rollback = Boolean::multi_and(
            cs,
            &[previous_is_not_rollback, sorted_item.rollback, should_pop],
        );
        keys_are_equal.conditionally_enforce_true(cs, enforce_sequential_rollback);

Here, for two consecutive element A, B in the queue, if A is not rollback and B is rollback, we enforce that A, B shares the same timestamp.

        let same_log = UInt32::equals(cs, &sorted_item.timestamp, &previous_item.timestamp);
        let values_are_equal =
            UInt256::equals(cs, &sorted_item.written_value, &previous_item.written_value);
        let negate_previous_is_trivial = previous_is_trivial.negated(cs);
        let should_enforce = Boolean::multi_and(cs, &[same_log, negate_previous_is_trivial]);
        values_are_equal.conditionally_enforce_true(cs, should_enforce);

Here, for two consecutive element A, B in the queue, if they share the same timestamp, we enforce that they have the same written value. (This is already guaranteed by the earlier circuits)

        let this_item_is_non_trivial_rollback =
            Boolean::multi_and(cs, &[sorted_item.rollback, should_pop]);
        let negate_previous_item_rollback = previous_item.rollback.negated(cs);
        let prevous_item_is_non_trivial_write = Boolean::multi_and(
            cs,
            &[negate_previous_item_rollback, negate_previous_is_trivial],
        );
        let is_sequential_rollback = Boolean::multi_and(
            cs,
            &[
                this_item_is_non_trivial_rollback,
                prevous_item_is_non_trivial_write,
            ],
        );
        same_log.conditionally_enforce_true(cs, is_sequential_rollback);

This is almost the same as the second one.

        // decide if we should add the PREVIOUS into the queue
        // We add only if previous one is not trivial,
        // and it had a different key, and it wasn't rolled back
        let negate_same_log = same_log.and(cs, should_pop).negated(cs);
        let add_to_the_queue = Boolean::multi_and(
            cs,
            &[
                negate_previous_is_trivial,
                negate_same_log,
                negate_previous_item_rollback,
            ],
        );

Finally, for two consecutive element A, B in the queue, if A is write and A, B are different, we add A to the result queue.

We use w to denote write and r to denote rollback, two adjacent letters share the same timestamp. An ideal sorted queue would be like wr wr w w w wr. The system worked well in this case. However, what if someone submit wr rw wr rw as the sorted queue? All the four logs here are reverted, so no log should be added to the result queue. However, this sorted queue satisfy all the constraints, and it will add the second and the fourth log to the result queue. (Try it yourself!)

To conclude, the constraints are not strong enough and attacker can manipulate the sorted queue to emit already reverted l1 logs and events.

Tools Used

Manual

Recommended Mitigation Steps

Enforce that the first popped element is write and there are no two consecutive rollbacks in the sorted queue.

Assessed type

Context

[c4-pre-sort]

bytes032 marked the issue as primary issue

[c4-pre-sort]

bytes032 marked the issue as sufficient quality report

[c4-sponsor]

miladpiri (sponsor) confirmed

[GalloDaSballo]

The Warden has demonstrated a lack of contraints that would allow, per their own words to:

manipulate the sorted queue to emit already reverted l1 logs and events.

This allows for undefined behaviour, which may lead to exploits, leading me to believe that High Severity is appropriate

[c4-judge]

GalloDaSballo marked the issue as selected for report