[tor-dev] Implementation plan for prop271 "Another algorithm for guard selection"

[George Kadianakis]

Hello people,

our new guard algorithm proposal (prop271) is getting finalized and we are planning to
move to implementation soon. You can find the proposal here:
          https://gitweb.torproject.org/torspec.git/tree/proposals/271-another-guard-selection.txt

You can also find the STRIKE team's implementation of proposal 259 here:
    https://github.com/twstrike/tor_for_patching
Ideally we should borrow as much code as possible from their implementation.

To move forward with engineering, here follows an initial thirteen step
implementation plan for proposal 271.

Where it made sense, I tried to provide links to current functions that can be
used, or to code that the STRIKE team wrote and can be reused or studied.

Let me know what I should make clearer or where I should go further in depth.

---

Design decisions:

An initial design decision here is whether we should make a new file for this
feature or use the old entrynodes.c file? A related question here is whether
both algos should co-exist, or should the new one replace the old? I leave both
decisions to the person who writes the code.

---

Implementation plan:

1) Create main guard selection state data structure (instead of using global variables)
** Ideally there should be no global variables, so that in the future we can have multiple parallel guardsets (e.g. prop247)
** Thoughtworks: guard_selection_t

2) Sample SAMPLED_GUARDS from GUARDS
** Fill in state for each sampled guard (added_on_date, etc.)
** Save/load SAMPLED_GUARDS to/from state
** Unittests for sampling/saving/loading
** Thoughtworks function: fill_sampled_guards_from_entrynodes()
** Thoughtworks unittest: test_fill_in_sampled_set()

3) Derive FILTERED_GUARDS / USABLE_FILTERED_GUARDS from SAMPLED_GUARDS
** The filtering function can be called at any point (e.g. ON_CONSENSUS)
** Write unittests ensuring correctness of filtering
** See populate_live_entry_guards()
** Thoughtworks function: filter_set() / filter_sampled()

4) Maintain set of PRIMARY_GUARDS
** Functions to extract set of (live) primary guards out of FILTERED_GUARDS
** Unittest
** Thoughtworks function: retry_primary_guards() / next_primary_guard()
** Thoughtworks unittests: test_next_primary_guard()

5) Selecting guards for circuits
** Meant to replace choose_random_entry_impl()
** See section SELECTING in prop271
** Add new circuit states to or_circuit_t
** Implement the guard selection logic
** Unittests on circuit state machine
** Unittests on guard selection logic

6) Update guard state when a circuit fails/succeeds
** Section ON_FAIL and ON_SUCCESS
** See entry_guard_register_connect_status()
** Unittest

7) Maintain CONFIRMED_GUARDS
** Add guard to CONFIRMED_GUARDS when circuit succeeds
** Fill in state info for each confirmed guard (confirmed_on_date, etc.)
** Migration from old state format to new
** Thoughtworks unittest: test_used_guards_parse_state()

8) Retry schedule for guards (section RETRYING)
** See entry_is_time_to_retry()
** Unittest

9) Update list of waiting circuits (section UPDATE_WAITING)
** Implementation of guard "higher priority" ordering (see CONFIRMED)
** Unittest

10) Update state whenever we get a new consensus (section ON_CONSENSUS)
** Update SAMPLED_GUARDS elements (section SAMPLED)
** Remove obsolete/expired guards
** See entry_guards_compute_status() / remove_obsolete_entry_guards()
** Thoughtworks function: entry_guards_update_profiles()

11) Bridge support
** Thoughtworks function: fill_in_from_bidges()

12) Separate state instances when EntryNodes/ExcludeNodes/etc are used
** See prop271 MEANINGFUL_RESTRICTION_FRAC etc.

13) Glue things together!
** Add clean and meaningful logging so that we can *heavily* field test the feature in our machines