radicle: fault tolerant thresholds — heartwood

There are two areas where we can be more tolerant of delegate namespaces being missing or not validating:

Calculating the canonical HEAD
Fetching from a remote

In 1. the protocol is tolerant in that if the local node does not have the default branch for a delegate, it will still attempt to use any of the delegates it does have to reach the threshold.

This is made safe by ensuring that if the threshold is being updated then the node performing the update must have a threshold of delegates locally in their storage. It also made safe by 2.

In 2. the protocol is tolerant by allowing delegates to be missing from the serving side, as long as they can still meet a threshold of delegates. This is further tolerant, when validating the received data, a threshold of delegates are valid to consider the fetch successful – otherwise it will fail.

 $ git push rad master
 ```
 At this point Alice can follow Bob, fetch his fork, and add him to the delegate
 set:
 If Alice wants to ensure that both her and Bob need to agree on merges
 to the default branch, she must set the `threshold` to `2` when adding
 Bob as a delegate:
 ``` ~alice (fails)
 $ rad id update --repo rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji --title "Add Bob" --description "" --threshold 2 --delegate did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk --no-confirm -q
 ✗ Error: failed to verify delegates for rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji
 ✗ Error: a threshold of 2 delegates cannot be met, found 1 delegate(s) and the following delegates are missing [did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk]
 ✗ Hint: run `rad follow did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk` to follow this missing peer
 ✗ Hint: run `rad sync -f` to attempt to fetch the newly followed peers
 ✗ Error: fatal: refusing to update identity document
 ```
 We can see that `a threshold of 2 delegates cannot be met` when Alice
 attempts to do this. This is because she requires Bob's default branch
 to ensure that the threshold can be met and the canonical version of
 the default branch (`refs/heads/<default branch>` at the top-level of
 the storage) can be updated.
 So, instead Alice needs to first follow Bob and fetch his references:
 ``` ~alice
 $ rad follow did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk --alias bob
 ✓ Follow policy updated for z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk (bob)
 $ rad sync
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkvVv…Z1Ct4tD..
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkuPZ…xEuaPUp..
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkvVv…Z1Ct4tD..
 ✓ Fetched repository from 2 seed(s)
 ✓ Nothing to announce, already in sync with network (see `rad sync status`)
 ✓ Synced with 1 node(s)
 $ rad id update --repo rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji --title "Add Bob" --description "" --threshold 2 --delegate did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk --no-confirm -q
 e7d58faa9a7473d27f5510d676af33282796f
 $ rad sync
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkvVv…Z1Ct4tD..
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkuPZ…xEuaPUp..
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkvVv…Z1Ct4tD..
 ✓ Fetched repository from 2 seed(s)
 ✓ Synced with 2 node(s)
 ✓ Synced with 3 node(s)
 ```
 Bob can confirm that he was made a delegate by fetching the update:
 ``` ~bob
 $ rad sync
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkvVv…Z1Ct4tD..
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkuPZ…xEuaPUp..
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkvVv…Z1Ct4tD..
 ✓ Fetched repository from 2 seed(s)
 ✓ Nothing to announce, already in sync with network (see `rad sync status`)
 ✓ Synced with 1 node(s)
 $ rad inspect --delegates
 did:key:z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi (alice)
 did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk (bob)

 ``` ~eve
 $ rad clone rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji --scope followed
 ✓ Seeding policy updated for rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji with scope 'followed'
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkvVv…Z1Ct4tD..
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkuPZ…xEuaPUp..
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkvVv…Z1Ct4tD..
 ✓ Creating checkout in ./heartwood..
 ✓ Remote alice@z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi added
 ✓ Remote-tracking branch alice@z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi/master created for z6MknSL…StBU8Vi

 $ git push rad master
 ```
 Bob then follows Eve and fetches her fork and adds her as a delegate:
 Bob then adds Eve as a delegate:
 ``` ~bob
 $ rad follow did:key:z6Mkux1aUQD2voWWukVb5nNUR7thrHveQG4pDQua8nVhib7Z --alias eve
 ✓ Follow policy updated for z6Mkux1aUQD2voWWukVb5nNUR7thrHveQG4pDQua8nVhib7Z (eve)
 $ rad sync
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkvVv…Z1Ct4tD..
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkuPZ…xEuaPUp..
 ✓ Fetched repository from 2 seed(s)
 ✓ Nothing to announce, already in sync with network (see `rad sync status`)
 $ rad id update --repo rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji --title "Add Eve" --description "" --delegate did:key:z6Mkux1aUQD2voWWukVb5nNUR7thrHveQG4pDQua8nVhib7Z --no-confirm -q
 cd3c7f9900de0fcb19705856a7cc339a38fb0b3
 $ rad sync
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkvVv…Z1Ct4tD..
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkuPZ…xEuaPUp..
 ✓ Fetched repository from 2 seed(s)
 ✓ Synced with 2 node(s)
 ✓ Synced with 3 node(s)
 ```
 Since the `threshold` is set to `2` it's necessary for Alice to also
 accept this change:
 Notice how there was no need to follow Eve right away in this case?
 This is because Bob can meet the threshold of 2 without Eve, he
 has Alice and his default reference.
 Since there are two delegates when Bob adds Eve, Alice needs to accept
 the change to meet a quorum of votes (`votes >= (delegates / 2) + 1`):
 ``` ~alice
 $ rad sync
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkvVv…Z1Ct4tD..
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkuPZ…xEuaPUp..
 ✓ Fetched repository from 2 seed(s)
 ✓ Nothing to announce, already in sync with network (see `rad sync status`)
 ✓ Nothing to announce, already in sync with 3 node(s) (see `rad sync status`)
 $ rad id list
 ╭────────────────────────────────────────────────────────────────────────────────╮
 │ ●   ID        Title              Author                     Status     Created │

 ╰────────────────────────────────────────────────────────────────────────╯
 ```
 At this point Alice will want to fetch so that she can get Eve's fork:
 At this point, when Alice runs `rad sync`, she will fetch Eve's fork
 since she has become a delegate:
 ``` ~alice
 $ rad sync --timeout 3
 ✗ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkvVv…Z1Ct4tD.. error: missing required refs: ["refs/namespaces/z6Mkux1aUQD2voWWukVb5nNUR7thrHveQG4pDQua8nVhib7Z/refs/rad/sigrefs"]
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkvVv…Z1Ct4tD..
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkuPZ…xEuaPUp..
 ✓ Fetched repository from 1 seed(s)
 ✓ Synced with 1 node(s)
 ! Seed z6MkvVv69U1HGuN6yUd8RiYE8py6QYRzuQoG45xSpZ1Ct4tD timed out..
 ✓ Fetched repository from 2 seed(s)
 ✓ Synced with 3 node(s)
 $ rad inspect rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji --sigrefs
 z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi 1f716870f890be0c13fdd0af9f527af849fec792
 z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk c40018821dc1b41cad75e91e0c9d00827e815324
 z6Mkux1aUQD2voWWukVb5nNUR7thrHveQG4pDQua8nVhib7Z 95cd447c57de8d232c6154f5dba0451aa593520e
 ```
 Note that `z6MkvVv69U1HGuN6yUd8RiYE8py6QYRzuQoG45xSpZ1Ct4tD` fails to
 fetch since it did not have Eve's fork, and similarly, it could not
 fetch from Alice and times out for the same reason. However, Alice was
 able to successfully fetch from `z6MkvVv…Z1Ct4tD`, since it did have
 Eve's fork.
 Since the network is eventually consistent, if Eve decides to `sync`
 (this could also happen through a transient announcement), then we can
 see that both seeds are `synced`:

 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkvVv…Z1Ct4tD..
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MkuPZ…xEuaPUp..
 ✓ Fetched repository from 2 seed(s)
 ✓ Synced with 1 node(s)
 ✓ Synced with 3 node(s)
 $ rad sync status
 ╭────────────────────────────────────────────────────────────────────────────╮
 │ ●   Node                            Address   Status   Tip       Timestamp │
 ├────────────────────────────────────────────────────────────────────────────┤
 │ ●   eve           (you)                                95cd447   now       │
 │ ●   distrustful   z6MkvVv…Z1Ct4tD             synced   95cd447   now       │
 │ ●   seed          z6MkuPZ…xEuaPUp             synced   95cd447   now       │
 ╰────────────────────────────────────────────────────────────────────────────╯
 ╭─────────────────────────────────────────────────────────────────────────────────────────────────╮
 │ ●   Node                            Address                        Status   Tip       Timestamp │
 ├─────────────────────────────────────────────────────────────────────────────────────────────────┤
 │ ●   eve           (you)                                                     95cd447   now       │
 │ ●   bob           z6Mkt67…v4N1tRk                                  synced   95cd447   now       │
 │ ●   distrustful   z6MkvVv…Z1Ct4tD   distrustful.radicle.xyz:8776   synced   95cd447   now       │
 │ ●   seed          z6MkuPZ…xEuaPUp   seed.radicle.xyz:8776          synced   95cd447   now       │
 ╰─────────────────────────────────────────────────────────────────────────────────────────────────╯
 ```

 In the attempt below, to update the identity, we can see that `a
 threshold of 2 delegates cannot be met` when Alice attempts to do
 this. This is because she requires Bob's default branch to ensure that
 the threshold can be met and the canonical version of the default
 branch (`refs/heads/<default branch>` at the top-level of the storage)
 can be updated.
 ``` ~alice (fail)
 $ rad id update --title "Add Bob" --description "Add Bob as a delegate" --delegate did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk --threshold 2
 ✗ Error: failed to verify delegates for rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji
 ✗ Error: a threshold of 2 delegates cannot be met, found 1 delegate(s) and the following delegates are missing [did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk]
 ✗ Hint: run `rad follow did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk` to follow this missing peer
 ✗ Hint: run `rad sync -f` to attempt to fetch the newly followed peers
 ✗ Error: fatal: refusing to update identity document
 ```
 Instead, Alice can simply keep the `threshold` as `1` and still add Bob as a delegate:
 ``` ~alice
 $ rad id update --title "Add Bob" --description "Add Bob as a delegate" --delegate did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk
 ✓ Identity revision 7be665f9fccba97abb21b2fa85a6fd3181c72858 created
 ╭────────────────────────────────────────────────────────────────────────╮
 │ Title    Add Bob                                                       │
 │ Revision 7be665f9fccba97abb21b2fa85a6fd3181c72858                      │
 │ Blob     93d3009787e5d8a481dffc4dd248ea46af592466                      │
 │ Author   did:key:z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi      │
 │ State    accepted                                                      │
 │ Quorum   yes                                                           │
 │                                                                        │
 │ Add Bob as a delegate                                                  │
 ├────────────────────────────────────────────────────────────────────────┤
 │ ✓ did:key:z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi alice (you) │
 ╰────────────────────────────────────────────────────────────────────────╯
@@ -1,13 +1,14 @@
  {
    "payload": {
      "xyz.radicle.project": {
        "defaultBranch": "master",
        "description": "Radicle Heartwood Protocol & Stack",
        "name": "heartwood"
      }
    },
    "delegates": [
 -    "did:key:z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi"
 +    "did:key:z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi",
 +    "did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk"
    ],
    "threshold": 1
  }
 ```
 Alice can still make changes to her working copy, change the canonical
 head, and make patches -- as we can see below:
 ``` ~alice
 $ touch REQUIREMENTS
 $ git add REQUIREMENTS
 $ git commit -v -m "Define power requirements"
 [master 3e674d1] Define power requirements
 file changed, 0 insertions(+), 0 deletions(-)
  create mode 100644 REQUIREMENTS
 ```
 ``` ~alice (stderr) RAD_SOCKET=/dev/null
 $ git push rad master
 ✓ Canonical head updated to 3e674d1a1df90807e934f9ae5da2591dd6848a33
 To rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi
    f2de534..3e674d1  master -> master
 ```
 ``` ~alice
 $ rad sync -a
 ✓ Synced with 1 node(s)
 ```
 ``` ~alice
 $ git checkout -b add-readme
 $ touch README.md
 $ git add README.md
 $ git commit -v -m "Add README file"
 [add-readme 964513c] Add README file
 file changed, 0 insertions(+), 0 deletions(-)
  create mode 100644 README.md
 ```
 ``` ~alice (stderr) RAD_SOCKET=/dev/null
 $ git push rad HEAD:refs/patches
 ✓ Patch b09b2aa0ee055671c811e9ad4ba73eed211ebaa3 opened
 To rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi
  * [new reference]   HEAD -> refs/patches
 ```
 Any other seeds can also still fetch changes from Alice without any
 errors:
 ``` ~seed
 $ rad sync rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji -f
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MknSL…StBU8Vi..
 ✓ Fetched repository from 1 seed(s)
 ```
 We can also inspect the repository to ensure all the data is
 consistent with the change made to the identity.
 The identity has the new delegate, while the `threshold` is still `1`
 ``` ~alice
 $ rad inspect --identity
 {
   "payload": {
     "xyz.radicle.project": {
       "defaultBranch": "master",
       "description": "Radicle Heartwood Protocol & Stack",
       "name": "heartwood"
     }
   },
   "delegates": [
     "did:key:z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi",
     "did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk"
   ],
   "threshold": 1
 }
 ```
 Alice only sees her refs, since she has not synced with Bob's
 references yet:
 ``` ~alice
 $ rad inspect --refs
 z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi
 └── refs
     ├── cobs
     │   ├── xyz.radicle.id
     │   │   └── 0656c217f917c3e06234771e9ecae53aba5e173e
     │   └── xyz.radicle.patch
     │       └── b09b2aa0ee055671c811e9ad4ba73eed211ebaa3
     ├── heads
     │   ├── master
     │   └── patches
     │       └── b09b2aa0ee055671c811e9ad4ba73eed211ebaa3
     └── rad
         ├── id
         └── sigrefs
 ```
 Similarly, she still does not have Bob's `rad/sigrefs`:
 ``` ~alice
 $ rad inspect --sigrefs
 z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi 7ffed605e4871bb0640ee1538181640e239b182c
 ```
 And she can still list the project, without any worries:
 ``` ~alice
 $ rad ls
 ╭───────────────────────────────────────────────────────────────────────────────────────────────────────────╮
 │ Name        RID                                 Visibility   Head      Description                        │
 ├───────────────────────────────────────────────────────────────────────────────────────────────────────────┤
 │ heartwood   rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji   public       3e674d1   Radicle Heartwood Protocol & Stack │
 ╰───────────────────────────────────────────────────────────────────────────────────────────────────────────╯
 ```
 Once Bob clones the repository and creates a fork, i.e. creates a
 branch to `refs/heads/master` for this project, she can then use `rad
 sync` and fetch his references:
 ``` ~bob
 $ rad clone rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji
 ✓ Seeding policy updated for rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji with scope 'all'
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MknSL…StBU8Vi..
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6Mkux1…nVhib7Z..
 ✓ Creating checkout in ./heartwood..
 ✓ Remote alice@z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi added
 ✓ Remote-tracking branch alice@z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi/master created for z6MknSL…StBU8Vi
 ✓ Repository successfully cloned under [..]/bob/heartwood/
 ╭────────────────────────────────────╮
 │ heartwood                          │
 │ Radicle Heartwood Protocol & Stack │
 │ 0 issues · 1 patches               │
 ╰────────────────────────────────────╯
 Run `cd ./heartwood` to go to the repository directory.
 ```
 ``` ~bob
 $ cd heartwood
 $ rad fork
 ✓ Forked repository rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji for z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk
 ```
 ``` ~alice
 $ rad sync -f
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6Mkt67…v4N1tRk..
 ✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6Mkux1…nVhib7Z..
 ✓ Fetched repository from 2 seed(s)
 $ rad inspect --sigrefs
 z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi 7ffed605e4871bb0640ee1538181640e239b182c
 z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk cc068d93ee77dc134518d7d0fbe55b39804baf53
 ```

 ✗ Error: [..]
 ```
 If we attempt to add a delegate that we do not have locally, then we
 will be told that they are missing in our repository:
 ``` (fail)
 $ rad id update --title "Add Eve" --description "Add Eve as a delegate" --delegate did:key:z6MkedTZGJGqgQ2py2b8kGecfxdt2yRdHWF6JpaZC47fovFn
 ✗ Error: failed to verify delegates for rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji
 ✗ Error: missing delegate z6MkedT…47fovFn in local storage
 ✗ Error: fatal: refusing to update identity document
 ```
 If no updates are specified then the update will fail:
 ``` (fail)

                     "at lease one delegate must be present for the identity to be valid"
                 ))?;
                 if let Some(errs) = verify_delegates(&proposal.delegates, &repo)? {
                 if let Some(errs) = verify_delegates(&proposal, &repo)? {
                     term::error(format!("failed to verify delegates for {rid}"));
                     for e in errs {
                         e.print();

 }
 enum VerificationError {
     Missing(Did),
     MissingDefaultBranch {
         branch: radicle::git::RefString,
         did: Did,
     },
     InsufficientDelegates {
         threshold: usize,
         met: usize,
         missing: Vec<Did>,
     },
 }
 impl VerificationError {
     fn print(&self) {
         match self {
             VerificationError::Missing(did) => term::error(format!(
                 "missing delegate {} in local storage",
                 term::format::did(did)
             )),
             VerificationError::MissingDefaultBranch { branch, did } => term::error(format!(
                 "missing {} for {} in local storage",
                 term::format::secondary(branch),
                 term::format::did(did)
             )),
             VerificationError::InsufficientDelegates {
                 threshold,
                 met,
                 missing,
             } => {
                 term::error(format!(
                     "a threshold of {threshold} delegates cannot be met, found {met} delegate(s) and the following delegates are missing [{}]",
                     missing.iter().map(|did| did.to_string()).collect::<Vec<_>>().join(","),
                 ));
                 for did in missing {
                     term::hint(format!(
                         "run `rad follow {did}` to follow this missing peer"
                     ));
                 }
                 term::hint("run `rad sync -f` to attempt to fetch the newly followed peers")
             }
         }
     }
 }
 fn verify_delegates<S>(
     dids: &NonEmpty<Did>,
 fn verify_delegates<S, V>(
     proposal: &Doc<V>,
     repo: &S,
 ) -> anyhow::Result<Option<Vec<VerificationError>>>
 where
     S: ReadRepository,
 {
     let dids = &proposal.delegates;
     let threshold = proposal.threshold;
     let (canonical, _) = repo.canonical_head()?;
     let mut errors = Vec::with_capacity(dids.len());
     let mut local_delegates = 0;
     let mut missing = Vec::with_capacity(dids.len());
     for did in dids {
         match refs::SignedRefsAt::load((*did).into(), repo)? {
             None => {
                 errors.push(VerificationError::Missing(*did));
                 missing.push(*did);
             }
             Some(refs::SignedRefsAt { sigrefs, .. }) => {
                 if sigrefs.get(&canonical).is_none() {

                         branch: canonical.to_ref_string(),
                         did: *did,
                     })
                 } else {
                     local_delegates += 1;
                 }
             }
         }
     }
     if local_delegates < threshold {
         errors.push(VerificationError::InsufficientDelegates {
             threshold,
             met: local_delegates,
             missing,
         });
     }
     Ok((!errors.is_empty()).then_some(errors))
 }

 }
 #[test]
 fn rad_id_threshold() {
     let mut environment = Environment::new();
     let alice = environment.node(config::node("alice"));
     let bob = environment.node(config::node("bob"));
     let seed = environment.node(config::node("seed"));
     let working = tempfile::tempdir().unwrap();
     let working = working.path();
     let acme = RepoId::from_str("z42hL2jL4XNk6K8oHQaSWfMgCL7ji").unwrap();
     // Setup a test repository.
     fixtures::repository(working.join("alice"));
     test(
         "examples/rad-init.md",
         working.join("alice"),
         Some(&alice.home),
         [],
     )
     .unwrap();
     let mut alice = alice.spawn();
     let mut seed = seed.spawn();
     let mut bob = bob.spawn();
     seed.handle.seed(acme, Scope::All).unwrap();
     alice.handle.seed(acme, Scope::Followed).unwrap();
     alice
         .handle
         .follow(seed.id, Some(Alias::new("seed")))
         .unwrap();
     alice.connect(&seed);
     bob.connect(&seed).connect(&alice);
     alice.routes_to(&[(acme, seed.id)]);
     seed.handle.fetch(acme, alice.id, DEFAULT_TIMEOUT).unwrap();
     formula(&environment.tmp(), "examples/rad-id-threshold.md")
         .unwrap()
         .home(
             "alice",
             working.join("alice"),
             [("RAD_HOME", alice.home.path().display())],
         )
         .home(
             "bob",
             working.join("bob"),
             [("RAD_HOME", bob.home.path().display())],
         )
         .home(
             "seed",
             working.join("seed"),
             [("RAD_HOME", seed.home.path().display())],
         )
         .run()
         .unwrap();
 }
 #[test]
 fn rad_id_multi_delegate() {
     let mut environment = Environment::new();
     let alice = environment.node(Config::test(Alias::new("alice")));

 pub struct RemoteRefs(BTreeMap<PublicKey, SignedRefsAt>);
 impl RemoteRefs {
     /// Load the sigrefs for the given `must` and `may` remotes.
     /// Load the sigrefs for each remote in `remotes`.
     ///
     /// The `must` remotes have to be present, otherwise an error will
     /// be returned.
     ///
     /// The `may` remotes do not have to be present and any missing
     /// sigrefs for that remote will be ignored.
     pub(crate) fn load<S>(
     /// If the sigrefs are missing for a given remote, regardless of delegate
     /// status, then that remote is filtered out.
     pub(crate) fn load<'a, S>(
         cached: &Cached<S>,
         Select { must, may }: Select,
         remotes: impl Iterator<Item = &'a PublicKey>,
     ) -> Result<Self, error::RemoteRefs> {
         let must = must.iter().map(|id| {
             cached
                 .load(id)
                 .map_err(error::RemoteRefs::from)
                 .and_then(|sr| match sr {
                     None => Err(error::RemoteRefs::NotFound(*id)),
                     Some(sr) => Ok((id, sr)),
                 })
         });
         let may = may.iter().filter_map(|id| match cached.load(id) {
             Ok(None) => None,
             Ok(Some(sr)) => Some(Ok((id, sr))),
             Err(e) => Some(Err(e.into())),
         });
         must.chain(may)
         remotes
             .filter_map(|id| match cached.load(id) {
                 Ok(None) => None,
                 Ok(Some(sr)) => Some(Ok((id, sr))),
                 Err(e) => Some(Err(e)),
             })
             .try_fold(RemoteRefs::default(), |mut acc, remote_refs| {
                 let (id, sigrefs) = remote_refs?;
                 acc.0.insert(*id, sigrefs);

         self.0.iter()
     }
 }
 pub struct Select<'a> {
     pub must: &'a BTreeSet<PublicKey>,
     pub may: &'a BTreeSet<PublicKey>,
 }

     pub enum Layout {
         #[error("missing required refs: {0:?}")]
         MissingRequiredRefs(Vec<String>),
         #[error("expected threshold of {threshold} of references, missing: {missing:?}")]
         InsufficientRefs {
             threshold: usize,
             missing: Vec<String>,
         },
     }
     #[derive(Debug, Error)]

     /// The set of delegates to be fetched, with the local node
     /// removed in the case of a `pull`.
     pub delegates: BTreeSet<PublicKey>,
     /// The threshold of delegates that needs to be fetched.
     pub threshold: usize,
     /// The data limit for this stage of fetching.
     pub limit: u64,
 }

     }
     fn pre_validate(&self, refs: &[ReceivedRef]) -> Result<(), error::Layout> {
         ensure_refs(
         ensure_threshold(
             self.delegates
                 .iter()
                 .filter(|id| !self.blocked.is_blocked(id))

                 .filter_map(|r| r.name.to_namespaced())
                 .map(|r| r.to_string().into())
                 .collect(),
             self.threshold,
         )
     }

         ))
     }
 }
 fn ensure_threshold<T>(
     wants: BTreeSet<T>,
     haves: BTreeSet<T>,
     threshold: usize,
 ) -> Result<(), error::Layout>
 where
     T: Ord + ToString,
     T: std::fmt::Debug,
 {
     // N.b. there's no threshold to meet. This generally means that
     // the local peer is a delegate and the original threshold is 1,
     // so they don't require the other peer.
     if threshold == 0 {
         return Ok(());
     }
     if wants.is_empty() {
         return Ok(());
     }
     if haves.len() < threshold {
         let missing = wants
             .difference(&haves)
             .map(|ns| ns.to_string())
             .collect::<Vec<_>>();
         return Err(error::Layout::InsufficientRefs { threshold, missing });
     }
     Ok(())
 }

 use gix_protocol::handshake;
 use radicle::crypto::PublicKey;
 use radicle::git::{Oid, Qualified};
 use radicle::identity::{Doc, DocError};
 use radicle::identity::{Did, Doc, DocError};
 use radicle::prelude::Verified;
 use radicle::storage;

         Refs(#[from] radicle::storage::refs::Error),
         #[error(transparent)]
         RemoteRefs(#[from] sigrefs::error::RemoteRefs),
         #[error("failed to get remote namespaces: {0}")]
         RemoteIds(#[source] radicle::git::raw::Error),
         #[error(transparent)]
         Step(#[from] Step),
         #[error(transparent)]

         applied: Applied<'static>,
         /// The set of namespaces that were fetched.
         remotes: BTreeSet<PublicKey>,
         /// Validation errors that were found while fetching for
         /// **non-delegate** remotes.
         warnings: sigrefs::Validations,
         /// Any validation errors that were found while fetching.
         validations: sigrefs::Validations,
     },
     Failed {
         /// Validation errors that were found while fetching for
         /// **non-delegate** remotes.
         warnings: sigrefs::Validations,
         /// Validation errors that were found while fetching for
         /// **delegate** remotes.
         failures: sigrefs::Validations,
         /// The threshold that needed to be met.
         threshold: usize,
         /// The offending delegates.
         delegates: BTreeSet<PublicKey>,
         /// Validation errors that were found while fetching.
         validations: sigrefs::Validations,
     },
 }

         }
     }
     pub fn warnings(&self) -> impl Iterator<Item = &sigrefs::Validation> {
         match self {
             Self::Success { warnings, .. } => warnings.iter(),
             Self::Failed { warnings, .. } => warnings.iter(),
         }
     }
     pub fn is_success(&self) -> bool {
         match self {
             Self::Success { .. } => true,

     ///
     /// The resulting [`sigrefs::RemoteRefs`] will be the set of
     /// `rad/sigrefs` of the fetched remotes.
     #[allow(clippy::too_many_arguments)]
     fn run_special_refs<S>(
         &mut self,
         handle: &mut Handle<S>,
         handshake: &handshake::Outcome,
         delegates: BTreeSet<PublicKey>,
         threshold: usize,
         limit: &FetchLimit,
         remote: PublicKey,
         refs_at: Option<Vec<RefsAt>>,

     {
         match refs_at {
             Some(refs_at) => {
                 let (must, may): (BTreeSet<PublicKey>, BTreeSet<PublicKey>) = refs_at
                     .iter()
                     .map(|refs_at| refs_at.remote)
                     .partition(|id| delegates.contains(id));
                 let sigrefs_at = stage::SigrefsAt {
                     remote,
                     delegates,
                     refs_at,
                     delegates: delegates.clone(),
                     refs_at: refs_at.clone(),
                     blocked: handle.blocked.clone(),
                     limit: limit.special,
                 };
                 log::trace!(target: "fetch", "{sigrefs_at:?}");
                 self.run_stage(handle, handshake, &sigrefs_at)?;
                 let remotes = refs_at.iter().map(|r| &r.remote);
                 let signed_refs = sigrefs::RemoteRefs::load(
                     &self.as_cached(handle),
                     sigrefs::Select {
                         must: &must,
                         may: &may,
                     },
                 )?;
                 let signed_refs = sigrefs::RemoteRefs::load(&self.as_cached(handle), remotes)?;
                 Ok(signed_refs)
             }
             None => {

             .canonical()?
             .ok_or(error::Protocol::MissingRadId)?;
         let is_delegate = anchor.delegates.contains(&Did::from(handle.local()));
         // TODO: not sure we should allow to block *any* peer from the
         // delegate set. We could end up ignoring delegates.
         let delegates = anchor

         log::trace!(target: "fetch", "Identity delegates {delegates:?}");
         // The local peer does not need to count towards the threshold
         // since they must be valid already.
         let threshold = if is_delegate {
             anchor.threshold - 1
         } else {
             anchor.threshold
         };
         let signed_refs = self.run_special_refs(
             handle,
             handshake,
             delegates.clone(),
             threshold,
             &limit,
             remote,
             refs_at,

         // Run validation of signed refs, pruning any offending
         // remotes from the tips, thus not updating the production Git
         // repository.
         // N.b. any delegate validation errors are added to
         // `failures`, while any non-delegate validation errors are
         // added to `warnings`.
         let mut warnings = sigrefs::Validations::default();
         let mut failures = sigrefs::Validations::default();
         let signed_refs = data_refs.remotes;

         // non-pruned, fetched remotes here.
         let mut remotes = BTreeSet::new();
         // The valid delegates start with all delegates that this peer
         // currently has valid references for
         let mut valid_delegates = handle
             .repository()
             .remote_ids()
             .map_err(error::Protocol::RemoteIds)?
             .filter_map(|id| id.ok())
             .filter(|id| delegates.contains(id))
             .collect::<BTreeSet<_>>();
         let mut failed_delegates = BTreeSet::new();
         // TODO(finto): this might read better if it got its own
         // private function.
         for remote in signed_refs.keys() {
             if handle.is_blocked(remote) {
                 log::trace!(target: "fetch", "Skipping blocked remote {remote}");
                 continue;
             }
             let remote = sigrefs::DelegateStatus::empty(*remote, &delegates);
             match remote.load(&self.as_cached(handle))? {
             let remote = sigrefs::DelegateStatus::empty(*remote, &delegates)
                 .load(&self.as_cached(handle))?;
             match remote {
                 sigrefs::DelegateStatus::NonDelegate { remote, data: None } => {
                     log::debug!(target: "fetch", "Pruning non-delegate {remote} tips, missing 'rad/sigrefs'");
                     warnings.push(sigrefs::Validation::MissingRadSigRefs(remote));
                     self.prune(&remote)
                     failures.push(sigrefs::Validation::MissingRadSigRefs(remote));
                     self.prune(&remote);
                 }
                 sigrefs::DelegateStatus::Delegate { remote, data: None } => {
                     log::warn!(target: "fetch", "Pruning delegate {remote} tips, missing 'rad/sigrefs'");
                     failures.push(sigrefs::Validation::MissingRadSigRefs(remote));
                     self.prune(&remote)
                     self.prune(&remote);
                     // This delegate has removed their `rad/sigrefs`.
                     // Technically, we can continue with their
                     // previous `rad/sigrefs` but if this occurs with
                     // enough delegates also failing validation we
                     // would rather surface the issue and fail the fetch.
                     valid_delegates.remove(&remote);
                     failed_delegates.insert(remote);
                 }
                 sigrefs::DelegateStatus::NonDelegate {
                     remote,

                             "Pruning non-delegate {remote} tips, due to validation failures"
                         );
                         self.prune(&remote);
                         warnings.append(warns);
                         failures.append(warns);
                     } else {
                         remotes.insert(remote);
                     }

                     {
                         let ancestry = repository::ancestry(&handle.repo, at, sigrefs.at)?;
                         if matches!(ancestry, repository::Ancestry::Behind) {
                             log::trace!(target: "fetch", "Advertised `rad/sigrefs` {} is behind {at} for {remote}", sigrefs.at);
                             self.prune(&remote);
                             continue;
                         } else if matches!(ancestry, repository::Ancestry::Diverged) {

                     }
                     let cache = self.as_cached(handle);
                     let mut fails = Validations::default();
                     // N.b. we only validate the existence of the
                     // default branch for delegates, since it safe for
                     // non-delegates to not have this branch.
                     let branch_validation =
                         validate_project_default_branch(&anchor, &sigrefs.sigrefs);
                     let fails = sigrefs::validate(&cache, sigrefs)?.map(|mut fails| {
                         fails.extend(branch_validation);
                         fails
                     });
                     if let Some(mut fails) = fails {
                     fails.extend(branch_validation.into_iter());
                     let validations = sigrefs::validate(&cache, sigrefs)?;
                     fails.extend(validations.into_iter().flatten());
                     if !fails.is_empty() {
                         log::warn!(target: "fetch", "Pruning delegate {remote} tips, due to validation failures");
                         self.prune(&remote);
                         valid_delegates.remove(&remote);
                         failed_delegates.insert(remote);
                         failures.append(&mut fails)
                     } else {
                         valid_delegates.insert(remote);
                         remotes.insert(remote);
                     }
                 }

             start.elapsed().as_millis()
         );
         // N.b. only apply to Git repository if no delegates have failed verification.
         if failures.is_empty() {
         // N.b. only apply to Git repository if there are enough valid
         // delegates that pass the threshold.
         if valid_delegates.len() >= threshold {
             let applied = repository::update(
                 &handle.repo,
                 self.tips

             Ok(FetchResult::Success {
                 applied,
                 remotes,
                 warnings,
                 validations: failures,
             })
         } else {
             log::debug!(
                 target: "fetch",
                 "Fetch failed: {} warning(s) and {} failure(s) ({}ms)",
                 warnings.len(),
                 "Fetch failed: {} failure(s) ({}ms)",
                 failures.len(),
                 start.elapsed().as_millis()
             );
             Ok(FetchResult::Failed { warnings, failures })
             Ok(FetchResult::Failed {
                 threshold,
                 delegates: failed_delegates,
                 validations: failures,
             })
         }
     }
 }

             log::warn!(target: "worker", "Rejected update for {}", rejected.refname())
         }
         for warn in result.warnings() {
             log::warn!(target: "worker", "Validation error: {}", warn);
         }
         match result {
             radicle_fetch::FetchResult::Failed { failures, .. } => {
                 for fail in failures.iter() {
             radicle_fetch::FetchResult::Failed {
                 threshold,
                 delegates,
                 validations,
             } => {
                 for fail in validations.iter() {
                     log::error!(target: "worker", "Validation error: {}", fail);
                 }
                 Err(error::Fetch::Validation)
                 Err(error::Fetch::Validation {
                     threshold,
                     delegates: delegates.into_iter().map(|key| key.to_string()).collect(),
                 })
             }
             radicle_fetch::FetchResult::Success {
                 applied, remotes, ..
                 applied,
                 remotes,
                 validations,
             } => {
                 for warn in validations {
                     log::warn!(target: "worker", "Validation error: {}", warn);
                 }
                 // N.b. We do not go through handle for this since the cloning handle
                 // points to a repository that is temporary and gets moved by [`mv`].
                 let repo = storage.repository(rid)?;

     Repository(#[from] radicle::storage::RepositoryError),
     #[error(transparent)]
     RefsDb(#[from] radicle::node::refs::Error),
     #[error("validation of storage repository failed")]
     Validation,
     #[error("validation of the storage repository failed: the delegates {delegates:?} failed to validate to meet a threshold of {threshold}")]
     Validation {
         threshold: usize,
         delegates: Vec<String>,
     },
     #[error(transparent)]
     Cache(#[from] Cache),
 }