Skip to content

Instantly share code, notes, and snippets.

@olabini

olabini/new_entry_guard_selection_algorithm_259.md

Last active February 11, 2016 15:42
Show Gist options
  • Save olabini/343da01de8e01491bf5c to your computer and use it in GitHub Desktop.
Save olabini/343da01de8e01491bf5c to your computer and use it in GitHub Desktop.
Download ZIP
Tor new entry guard selection algorithm
Raw
new_entry_guard_selection_algorithm_259.md

The full algorithm is referred to as ALGO_CHOOSE_ENTRY_GUARD. It is divided into three components, such that the full algorithm is implemented by first invocing ALGO_CHOOSE_ENTRY_GUARD_START, then repeatedly calling ALGO_CHOOSE_ENTRY_GUARD_NEXT and finally calling ALGO_CHOOSE_ENTRY_GUARD_END.

ALGO_CHOOSE_ENTRY_GUARD keeps track of unreachable status for guards in state private to the algorithm - this is initialized every time ALGO_CHOOSE_ENTRY_GUARD_START is called.

  • ALGO_CHOOSE_ENTRY_GUARD_START: (arguments: USED_GUARDS, EXCLUDE_NODES, N_PRIMARY_GUARDS)

    • If selecting directory guards, GUARDS is all guards from the consensus with the V2Flag, otherwise GUARDS is all guards from the consensus
    • Set UTOPIC_GUARDS to be all guards to use under utopic conditions from GUARDS
    • Set DYSTOPIC_GUARDS to be all guards to use under dystopic conditions from GUARDS
    • Set REMAINING_UTOPIC_GUARDS to be UTOPIC_GUARDS without EXCLUDE_NODES and USED_GUARDS
    • Set REMAINING_DYSTOPIC_GUARDS to be DYSTOPIC_GUARDS without EXCLUDE_NODES and USED_GUARDS
    • Create a list of PRIMARY_GUARDS that contain N_PRIMARY_GUARDS that are not bad by:
      • Taking the next entry from USED_GUARDS
      • If USED_GUARDS is empty:
        • randomly select an entry from UTOPIC_GUARDS, weighted by bandwidth
    • Set TRIED_GUARDS to be an empty set
    • Set TRIED_DYSTOPIC_GUARDS to be an empty set
    • Set state = STATE_PRIMARY_GUARDS

  • ALGO_CHOOSE_ENTRY_GUARD_NEXT:

    • If a new consensus has arrived:

      • Update all guard profiles with new bad/non-bad information
      • If any PRIMARY_GUARDS have become bad:
        • Remove the guard from PRIMARY_GUARDS
        • re-fill the list of PRIMARY_GUARDS using the same procedure used in ALGO_CHOOSE_ENTRY_GUARD_START
      • If any USED_GUARDS have become non-bad:
        • add it back to PRIMARY_GUARDS at the place it would have been if it was non-bad when running ALGO_CHOOSE_ENTRY_GUARD_START. If this results in PRIMARY_GUARDS being larger than N_PRIMARY_GUARDS, remove from the end of the list until the list is N_PRIMARY_GUARDS long

    • If it was at least 3 minutes since we tried the primary guards and we are not in STATE_PRIMARY_GUARDS:

      • save previous state
      • set state = STATE_PRIMARY_GUARDS

    • STATE_PRIMARY_GUARDS:

      • return each entry in PRIMARY_GUARDS in turn
        • for each entry, if algorithm doesn't terminate
          • mark entry as "unreachable"
          • add entry to TRIED_GUARDS
          • if the number of entries in TRIED_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME is larger than GUARDS_TRY_THRESHOLD, transition to STATE_TRY_ONLY_TRIED.
      • restore previous state (or STATE_TRY_UTOPIC if no previous)

    • STATE_TRY_UTOPIC:

      • for each entry in TRIED_GUARDS that was marked as unreachable more than 20 minutes ago
        • add it back to REMAINING_UTOPIC_GUARDS
      • return each entry from USED_GUARDS not in PRIMARY_GUARDS in turn
        • for each entry, if algorithm doesn't terminate
          • mark entry as "unreachable"
          • add entry to TRIED_GUARDS
          • if the number of entries in TRIED_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME is larger than GUARDS_TRY_THRESHOLD, transition to STATE_TRY_ONLY_TRIED.
          • if the number of entries in TRIED_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD proportion of UTOPIC_GUARDS, set state = STATE_TRY_DYSTOPIC
      • return each entry from REMAINING_UTOPIC_GUARDS randomly selected, weighted by bandwidth
        • remove the returned entry from REMAINING_UTOPIC_GUARDS
        • for each entry, if algorithm doesn't terminate
          • mark entry as "unreachable"
          • add entry to TRIED_GUARDS
          • if the number of entries in TRIED_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME is larger than GUARDS_TRY_THRESHOLD, transition to STATE_TRY_ONLY_TRIED.
          • if the number of entries in TRIED_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD proportion of UTOPIC_GUARDS, set state = STATE_TRY_DYSTOPIC

    • STATE_TRY_DYSTOPIC:

      • for each entry in TRIED_DYSTOPIC_GUARDS that was marked as unreachable more than 20 minutes ago
        • add it back to REMAINING_DYSTOPIC_GUARDS
      • return each remaining DYSTOPIC entry from USED_GUARDS in turn
        • for each entry, if algorithm doesn't terminate
          • mark entry as "unreachable"
          • add entry to TRIED_DYSTOPIC_GUARDS
          • if the number of entries in TRIED_GUARDS+TRIED_DYSTOPIC_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME is larger than GUARDS_TRY_THRESHOLD, transition to STATE_TRY_ONLY_TRIED.
          • if the number of entries in TRIED_DYSTOPIC_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD proportion of DYSTOPIC_GUARDS:
            • mark all guards in PRIMARY_GUARDS, TRIED_GUARDS and TRIED_DYSTOPIC_GUARDS as not "unreachable"
            • transition to STATE_TRY_ONLY_TRIED.
      • return each entry from REMAINING_DYSTOPIC_GUARDS randomly selected, weighted by bandwidth
        • remove the returned entry from REMAINING_DYSTOPIC_GUARDS
        • for each entry, if algorithm doesn't terminate
          • mark entry as "unreachable"
          • add entry to TRIED_DYSTOPIC_GUARDS
          • if the number of entries in TRIED_GUARDS+TRIED_DYSTOPIC_GUARDS that were tried within GUARDS_TRY_THRESHOLD_TIME is larger than GUARDS_TRY_THRESHOLD, return failure from ALGO_CHOOSE_ENTRY_GUARD.
          • if the number of entries in TRIED_DYSTOPIC_GUARDS is larger than a GUARDS_FAILOVER_THRESHOLD proportion of DYSTOPIC_GUARDS:
            • transition to STATE_TRY_ONLY_TRIED.

    • STATE_TRY_ONLY_TRIED:

      • return the entry from the union of TRIED_GUARDS and TRIED_DYSTOPIC_GUARDS that is oldest in terms of time since we tried it before
        • for each entry, if algorithm doesn't terminate
          • mark entry as "unreachable" again

  • ALGO_CHOOSE_ENTRY_GUARD_END:

    • If circuit is set up correctly, let algorithm know
      • Algorithm marks the guard chosen as used and makes sure it is in USED_GUARDS

In order to clarify how this algorithm is supposed to be used, this pseudo code illustrates the building of a circuit:

OPEN_CIRCUIT: context = ALGO_CHOOSE_ENTRY_GUARD_START()

while True: entryGuard = ALGO_CHOOSE_ENTRY_GUARD_NEXT(context) circuit = buildCircuitWith(entryGuard) if circuit: ALGO_CHOOSE_ENTRY_GUARD_END(context, entryGuard) return circuit

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment