Gist Searching in GitHub Provider is now Rate Limited (and doesn't appear to be affected by OAuth authentication)

[CMCDragonkai]

Describe the bug

In our discovery system, we use getIdentityData method from github provider which will look up gists via https://gist.github.com/search.

It seems recently this now has some secondary rate limit applied (https://docs.github.com/en/rest/using-the-rest-api/troubleshooting-the-rest-api?apiVersion=2022-11-28), which is not solvable even with authenticated requests. Atm it is done unauthenticated, because it's basically a public page that we index over.

Gists are not currently searchable via the official GitHub API, so it seems that gist search has basically become impossible to index programmatically now. This is pretty bad. Especially because it's a secondary rate limit.

I tried doing things like:

curl -H "Authorization: token <TOKEN>" "https://gist.github.com/search?q=user%3ACDeltakai+filename%3Acryptolink.txt+Cryptolink+between+Polykey+Keynode+and+Github+Identity&s=updated&o=desc"

But no use, it's just 429 too many requests.

The only other option right now is to change using the API for gists, and because there's no search feature, you have to basically index over all gists via the API, but we could use since to do this efficiently without having to repeat. https://docs.github.com/en/rest/gists/gists?apiVersion=2022-11-28#list-gists-for-a-user. Effectively only going over the new gists representing new claims. The timestamp acts like a cursor.

To Reproduce

1. Try discovering any identity... and you may see WARN:polykey.PolykeyAgent.task v0pocinl3mpo0195g4m2kd1t8k0:Failed - Reason: ErrorProviderCall: Provider responded with 429 Too Many Requests show up in the agent logs.

Expected behavior

It needs to work just like normal and discover without problems.

Screenshots

Notify maintainers

@tegefaulkes

[linear]

ENG-426 Gist Searching in GitHub Provider is now Rate Limited (and doesn't appear to be affected by OAuth authentication)

[CMCDragonkai]

This is a critical issue for all social identity discovery system.

[CMCDragonkai]

Sustainable solution is to switch to using the Github gist API, and using since as a cursor.

This means the graph has to be extended with metadata like the since cursor for a given identity vertex.

[CMCDragonkai]

Technically this could be defined by the GitHubProvider.

[CMCDragonkai]

I think GitHub is basically preventing scraping the gists.

[CMCDragonkai]

We should also take into account this information as part of the metadata of any given provider, so we can track how often we hit the API: https://docs.github.com/en/rest/rate-limit/rate-limit?apiVersion=2022-11-28

[CMCDragonkai]

To get around this atm, you can also do identities discover <NODEID> - in this case it does create a gestalt around a single NodeID and allows sharing. The vault share command should do this automatically if not done.

[CMCDragonkai]

Since the provider requires "state" to keep track of things, the interface needs to be updated to support arbitrary state for the providers. This can be as simple as supporting an arbitrary JSON value that the provider provides the type for.

[aryanjassal]

So, I need to implement a new field 'state' for the github identity provider. In this case, it would store the 'since' as a cursor of kinds, and we can use that combined with the gists REST API as a robust solution for searching for gists. This 'since' can become a field for the state, and the identity provider must be able to validate with any provided state.

Did I understand this correctly, or am I missing something?

[CMCDragonkai]

Well I think it needs to be made generic, so that other providers in the future can be developed along the similar guidelines. That's why I'm saying you'd want to have a state type that is POJO.

[CMCDragonkai]

And then the provider abstract would have to provide default implementation methods of persisting the state.

[CMCDragonkai]

Remember this is like a "resumable" task if you think about it.

[aryanjassal]

Since the provider requires "state" to keep track of things, the interface needs to be updated to support arbitrary state for the providers. This can be as simple as supporting an arbitrary JSON value that the provider provides the type for.

We already have a ProviderPaginationToken which essentially acts as a cursor. After going through the code, the data contained by this token is similar to June 4, 2024 13:59 (in case of another gist I used as an example). So, I can modify this field to act as the state and collapse any other field (if any) which also acts as holding some state for the searching.

let lastProviderPaginationToken = await this.gestaltGraph
  .getIdentity(providerIdentityId)
  .then((identity) => identity?.lastProviderPaginationToken);

This is how we get the first timestamp to search onwards. We just get the next latest timestamp by using cheerio to find the next value.

This behaviour can be basically preserved when using gists. However, the REST API only supports getting data after a timestamp, but we are looking for a gist before with the current approach. However, the GraphQL API does support both a 'before' and 'after' cursor, so we might need to use that instead.

if (paginationToken != null) {
  query += ` updated:<${paginationToken}`;
}

To get discovery to work again, simply updating the API calls should be sufficient, but implementing a state would be important for a robust solution, and might be required by other providers.

---

I'm still unsure about the requirement for the updated field here. If we need to only find a gist, then why can't we merely look for that singular gist? Maybe the timestamp would act as a cursor indicating a cut-off date for the claim data we have. The issue, MatrixAI/Polykey-CLI#181, went through how to handle multiple identity claims, and the most latest one is to be used and others discarded. So the updated cursor is used to ensure the sigchain contains all the relevant data about all claims is present and the most latest one is used. This means we can use either the REST API or the GraphQL one as we only need data after the 'since' timestamp, not before.

API Reference

• https://docs.github.com/en/rest/gists/gists?apiVersion=2022-11-28#list-gists-for-the-authenticated-user
• https://docs.github.com/en/graphql/reference/objects#gist