Calcul de distance via oracle

Je rajoute ce point à la liste des éléments à revoir éventuellement, suite au message d’Eloïs :

@elois : pourquoi un oracle ? ne peut-on pas directement avoir une entrée dans le storage représentant la WoT binaire que l’on stocke habituellement ?

Cela ne me choque pas d’avoir un poids élevé pour cette opération de calcul de distance associée à l’adhésion (surtout le renouvellement).

Puisque la question revient :

Cette méthode (calculer la puissance stepMax de la matrice d’adjacence de la TdC et compter les coefficients non nuls correspondant à un membre référent sur la ligne du candidat) a plusieurs avantages :

  • le temps de calcul de la puissance ne dépend que de N (O(N^2)), alors que l’exploration du graphe est plus ou moins longue et est en temps exponentiel dans le pire des cas
  • le calcul se fait sur tous les membres en même temps
  • possibilité d’exploiter le GPU et le SIMD (mais est-ce possible dans le runtime ? si non, dans un oracle ?)
  • si on regroupe tous les R membres référents d’un côté de la matrice, il suffit de vérifier, pour chaque ligne correspondant à un candidat, que dans l’ensemble de colonnes des référents, il y a moins de 20% de zéros (O(R))

Dites si ce n’est pas clair, je peux faire un schéma.

Edit: puisque ce calcul est long mais rentable si besoin de calculer plein de règles de distance en même temps, il pourrait être fait par intervalle minimal de X blocs. On n’a aucun besoin de valider une règle de distance en 30 secondes.

Edit2: en fait il faut recompter les référents accessibles pour chaque puissance 1,2,3,4,5. Cette opération prend donc plus d’espace. Au total, ça nous fait un temps O(stepMax.N²+stepMax.C.R) et un espace O(N²+C.R).

Par contre stocker bêtement les coefficients de la matrice prend trop de place (23Mo pour 5000 membres, 1Go pour 33000 membres). Donc il faut la stocker sous une forme compressée, ce qui ralentit les calculs.

À propos de visualisation de la matrice d’adjacence et de ses puissances, ceci devrait t’intéresser @tuxmain : extra/matrix_exponent.ipynb · master · Hugo Trentesaux / jucube · GitLab

1 « J'aime »

Parce que les calculs très coûteux (de l’ordre de plusieurs secondes de temps cpu), ne doivent pas être réalisés on-chain, au risque de ne pas pouvoir produire le prochain bloc et de bloquer tout le réseau (le temps d’exécution total d’un bloc devant rester inférieur à 6 secondes sinon le bloc est considéré invalide.

C’est pour cela que substrate a mis en place la notion de « offchain workers », c’est du code qui est dans le runtime (donc protocolaire), mais exécuté off-chain par tout ou partie des autorités, puis chaque autorité doit injecter un inherent dans un de ses prochains bloc pour publier son résultat.
Dès que l’on observe la publication de N résultats identiques (N devant être une proportion suffisante des autorités censées faire le calcul), alors le résultat est considéré comme « acté » et ses conséquences appliquées onchain.

L’idée étant que si plusieurs résultats différents sont donnés, les autorités ayant publié un résultat minoritaire sont sanctionnées.

Afin d’éviter d’occuper toutes les autorités à faire le même calcul coûteux en même temps, l’idéal est de sélectionner qui doit faire le calcul via une VRF, chaque autorité doti alors publier sa VRF, avec le résultat du calcul ou non selon que sa VRF indique si elle devait faire le calcul ou non.

Non ce n’est pas possible dans le runtime, ni même dans un offchain_worker, mais on peut aussi faire le calcul en natif coté client* et passer par le inherent_data_provider pour injecter le résultat. Il faut juste une runtime_api pour savoir si un calcul doit être fait et pour récupérer les données d’entrée.

C’est un peu plus de boulot (les offchain worker nous mache une parie du travail), mais ça reste tout à fait possible, j’ai déjà fait quelque chose de similaire pour moonbeam.

*ATTENTION: ce qu’on appelle client dans le jargon substrate, c’est en fait le nœud (sans le runtime), rien à voir avec ce que l’on appelle clients dans la Ğ1 (qu’on appelle plutôt « wallets » où « apps »).

OK, alors concernant le calcul de WoT il faudra traiter les adhésions une par une du coup ? Afin d’avoir des données cohérentes.

edit : je veux dire, maximum une adhésion par bloc, et pas d’autres dans un bloc suivant tant que le résultat n’est pas acté.

Je pense plutôt à une queue des identités en attente de validation de la distance, qui serait traitée tous les N blocs, par exemple toutes les 12h. le calcul se distance se ferait alors pour toutes les identités dans la queue en même temps.

1 « J'aime »