let state = QueueState::conditionally_select(
cs,
structured_input.start_flag,
&unsorted_queue_from_passthrough_state,
&unsorted_queue_from_fsm_input_state,
);
Wrap the state and witnesses for it in StorageLogQueue, thereby preparing the input data for inner:
let mut unsorted_queue = StorageLogQueue::<F, R>::from_state(cs, state);
use std::sync::Arc;
let initial_queue_witness = CircuitQueueWitness::from_inner_witness(initial_queue_witness);
unsorted_queue.witness = Arc::new(initial_queue_witness);
let intermediate_sorted_queue_from_passthrough_state = structured_input
.observable_input
.intermediate_sorted_queue_state;
Again, if it is not the rest cycle (start_flag == false), we should choose fsm:
let one = Num::allocated_constant(cs, F::ONE);
let initial_lhs = Num::parallel_select(
cs,
structured_input.start_flag,
&[one; DEFAULT_NUM_PERMUTATION_ARGUMENT_REPETITIONS],
&structured_input.hidden_fsm_input.lhs_accumulator,
);
let initial_rhs = Num::parallel_select(
cs,
structured_input.start_flag,
&[one; DEFAULT_NUM_PERMUTATION_ARGUMENT_REPETITIONS],
&structured_input.hidden_fsm_input.rhs_accumulator,
);
Depending on the flag, we prepare all the information for inner part:
let zero_u32 = UInt32::zero(cs);
let previous_key = UInt32::conditionally_select(
cs,
structured_input.start_flag,
&zero_u32,
&structured_input.hidden_fsm_input.previous_key,
);
let empty_storage = LogQuery::placeholder(cs);
let previous_item = LogQuery::conditionally_select(
cs,
structured_input.start_flag,
&empty_storage,
&structured_input.hidden_fsm_input.previous_item,
);
After inner part we check unsorted_queue and intermediate_sorted_queue.:
let unsorted_is_empty = unsorted_queue.is_empty(cs);
let sorted_is_empty = intermediate_sorted_queue.is_empty(cs);
Boolean::enforce_equal(cs, &unsorted_is_empty, &sorted_is_empty);
We check that permutation accumulators are equal and if the queues are already empty:
let completed = unsorted_queue.length.is_zero(cs);
for (lhs, rhs) in new_lhs.iter().zip(new_rhs.iter()) {
Num::conditionally_enforce_equal(cs, completed, lhs, rhs);
}
Finally, we compute a commitment to PublicInput and allocate it as witness variables.
let input_commitment = commit_variable_length_encodable_item(cs, &compact_form, round_function);
for el in input_commitment.iter() {
let gate = PublicInputGate::new(el.get_variable());
gate.add_to_cs(cs);
}
Inner part
Note: we have specific logic for rollback. When we have an event of some function and then that function makes a return then we should cancel this event. Inside the VM, we create exactly the same event: same key, block number, timestamp, etc. the only change is that the rollback flag is now true. In the inner part, first sort and look for these pairs and self-destruct them.
There are two cases: when unsorted_queue is empty, but it's the only circuit, in this case. Otherwise, we continue, and then it's not trivial.
let no_work = unsorted_queue.is_empty(cs);
let mut previous_is_trivial = Boolean::multi_or(cs, &[no_work, is_start]);
Additional checks for length. We should always check whether the sorted queue and the normal queue are of the same length.
let unsorted_queue_length = Num::from_variable(unsorted_queue.length.get_variable());
let intermediate_sorted_queue_length =
Num::from_variable(intermediate_sorted_queue.length.get_variable());
Num::enforce_equal(
cs,
&unsorted_queue_length,
&intermediate_sorted_queue_length,
);
We can pop elements if unsorted_queue is empty. That’s why every time we set up the flags original_is_empty, sorted_is_empty. We also ensure that items are "write" unless it's a padding.
let original_is_empty = unsorted_queue.is_empty(cs);
let sorted_is_empty = intermediate_sorted_queue.is_empty(cs);
Boolean::enforce_equal(cs, &original_is_empty, &sorted_is_empty);
let should_pop = original_is_empty.negated(cs);
let is_trivial = original_is_empty;
let (_, original_encoding) = unsorted_queue.pop_front(cs, should_pop);
let (sorted_item, sorted_encoding) = intermediate_sorted_queue.pop_front(cs, should_pop);
Check if keys are equal and check a value. We compare timestamps and then resolve logic over rollbacks, so the only way when keys are equal can be when we do a rollback. Ensure sorting for uniqueness timestamp and rollback flag. We know that timestamps are unique across logs, and are also the same between write and rollback. Keys are always ordered no matter what, and are never equal unless it's padding:
let sorting_key = sorted_item.timestamp;
let (keys_are_equal, new_key_is_smaller) =
unpacked_long_comparison(cs, &[previous_key], &[sorting_key]);
new_key_is_smaller.conditionally_enforce_false(cs, should_pop);
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 the VM circuit guarantees uniqueness if it's not a padding. Now ensure sorting:
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);
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);
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 previous_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,
previous_item_is_non_trivial_write,
],
);
same_log.conditionally_enforce_true(cs, is_sequential_rollback);
Decide if we should add the previous into the queue. We add only if the previous one is not trivial, 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,
],
);
Further, we don't need in our LogQueue some fields, so we just clean up:
