Skip to content

Proto/compare-operations: add comparison of valid operations

Context

When determining the content of a block to be baked,
it is relevant to sort valid operations to determine the most profitable ones,
for both the baker and the chain's liveness.

This MR implements a comparison for validated operations, providing a strict order.
This comparison is state-free as it relies on the operations' validation passes, static parameters, and hashes.
Only operations with the same hash compare as equal.
This MR also replaces acceptable_passes by acceptable_pass returning an optional integer instead of a list of integer.
This MR also removes relative_position_within_block and replaces it by compare_by_passes when only the ordering by pass is required and by compare_operations when a total order on operations is required.
compare_by_passes is not exported in the environment.
Finally, this MR also implements operation generators to perform tests on generated operations.

Manually testing the MR

Test that compare_operation provides a strict order via a series of generated unit tests on generated operations:

dune exec src/proto_alpha/lib_protocol/test/unit/main.exe -- test "\[Unit\] compare operations"

Test that compare_operation complies with its specification: The branch pipelining@compliance-compare-operations contains:

  • The Coq specification: a Coq model of compare_operation with proof of providing a decidable strict order; in src/proto_alpha/lib_protocol/test/pbt/spec.
  • a specification compliance test validates that compare_operation behaves as its extracted model on the generated operation via generated unit tests on generated unit tests on generated operations.
dune exec  src/proto_alpha/lib_protocol/test/pbt/test_compare_operations.exe

Checklist

  • Document the interface of any function added or modified (see the coding guidelines)
  • Document any change to the user interface, including configuration parameters (see node configuration)
  • Provide automatic testing (see the testing guide).
  • For new features and bug fixes, add an item in the appropriate changelog (docs/protocols/alpha.rst for the protocol and the environment, CHANGES.rst at the root of the repository for everything else).
  • Select suitable reviewers using the Reviewers field below.
  • Select as Assignee the next person who should take action on that MR
Edited by vbot

Merge request reports

Loading