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 :
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
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.
J’ai testé le calcul de la règle de distance avec la matrice d’adjacence (en Rust, avec des matrices CRC de nalgebra-sparse).
Avec 100 000 membres et un nombre de certifications reçues par membre suivant une loi normale centrée en 7.3 (càd 7.3 certifs par membre en moyenne), les premières étapes sont assez rapides et légères mais ça mange vite mes 16Go de RAM (à la troisième multiplication).
Avec 10 000 membres et autant de certifs par membre, le temps d’exécution est de quelques minutes et ça monte jusqu’à 10Go.
Afin d’éviter d’avoir à stocker une autre matrice contenant tous les membres référents accessibles par chaque membre à toutes les distances inférieures à la puissance qu’on est en train de calculer, j’ai eu l’idée de calculer plutôt A_{n+1}=A_0+A_nA_0. Comme ça, on trouve les chemins de longueur inférieure à n+1. Ça avait l’air d’une optimisation au début mais je pense que ça augmente considérablement le nombre de coefficients non-nuls, donc l’occupation mémoire.
Conclusion : ça prend beaucoup trop de mémoire pour être scalable à plusieurs de dizaines de milliers de membres ou plusieurs dizaines de certifs par membre. Je vais quand même essayer l’autre méthode (sans additionner A0 à chaque étape).
Il faut considérer que plus on aura de membres, et plus ceux qui se proposent de réaliser le calcul de distance pourront être rémunérés pour payer la machine nécessaire. On peut sans problème exigre 32 voir 64 Go de RAM pour chaque acteur qui se propose de calculer la distance.
Je rappelle que le principe de l’oracle c’est de prendre la médiane des réponses (ici la médiane du « xpercent » de chaque membre), de récompenser les acteurs qui ont soumis des résultats proches de la médiane, et de sanctionner ceux qui fournissent des résultats éloignés de la médiane.
TL;DR Je calcule toutes les règles distances en 7 minutes sur un i5 en prenant 287 Mo de RAM.
J’ai implémenté la règle de distance avec des matrices non-compressées (beaucoup plus rapide mais prend plus de place), avec quelques optimisations :
La consommation de RAM est 3×N^2. (donc 287 Mo pour 10 000 membres)
C’est un programme relativement peu coûteux en énergie (par rapport à une simulation physique ou de la crypto par exemple) : même s’il prend 100% du temps CPU, il ne fait que quelques opérations booléennes, beaucoup d’itérations, de branchements et d’accès mémoire. À 100% mon CPU n’était qu’à 73°C alors qu’il peut monter jusqu’à 98°C.
Sur mon ordi (i5-7300HQ, 2.5GHz, 4 cœurs), pour 10 000 membres et 8.6 certifs par membre, ça met 6 minutes 53 secondes.
La seule dépendance Rust est rayon, et il n’y a qu’un petit bout d’unsafe (pour virer des bound checks, avec gain de temps significatif) qu’on doit pouvoir enlever en réfléchissant un peu. Ça rentre dans le cahier des charges d’un oracle hors-blockchain @elois ?
Edit: le code est sur le GitLab. L’algo des matrices donne les mêmes résultats que l’algo d’exploration de graphe.
Un oracle est par définition hors-blockchain, donc c’est une totologie 
Le cahier des charges d’un oracle c’est surtout d’être un logiciel adapté pour adminsys car il doit toujours être disponible pour garantir qu’il fera le calcul qu’il doit faire quand il doit le faire et qu’il publiera bien le résultat sous peine de sanctions financières.
Donc il faut pouvoir le monitorer, le dockerisé, etc.
Vu que tu l’as écrit en rust et que la seule dépendance (rayon) est déjà une dépendance de duniter-v2s, il est peu être finalement préférable de l’intégrer directement au binaire duniter-v2s (si ça n’augmente pas significativement sa taille), ça éviterait de devoir refaire en double tout le travail de monitoring et de dockerisation.
Au final ça ne change pas grand-chose au travail que tu as déjà fait, car il faudrait quand même stocker le résultat dans un fichier, car on ne peut pas le publier dès qu’on l’a calculé.
Le calcul pourrait alors tourner dans le client tout simplement, ce qui éviterait d’avoir à utiliser RPC. Dans ce cas le fichier ne servirait que de sauvegarde au cas où le nœud s’arrête entre le début de la session et la publication du résultat.
En revanche ça nécessite quand même un peu de dev spécifique coté client duniter-v2s.
En effet tu ne peux pas lancer le calcul de distance dans la closure create_inherent_data_provider, car son exécution compte dans le temps de génération du bloc.
Il te faut créer une task et l’ajoutée au task manager de substrate, ça permet en plus de bénéficier du monitoring prometheus sur les tasks.
Regarder ici un exemple pour spawn une task: node/src/service.rs · v0.4.0 · nodes / rust / Duniter v2S · GitLab
La task de calcul de la distance doit bien être spawn blocking, car les calculs coûteux de la distance bloquerait trop longtemps le threadpool tokio dédié à l’exécution des async task (notamment les taches réseau).
Entre spawn_handle et spawn_essential_handle la seule différence est que pour une tache essentielle le nœud s’arrête si elle panic. Ce qui représente une faille de sécurité potentielle si un attaquant arrive à fournir des données qui font paniquer le calcul de distance.
Je recommande donc spawn_handle tout court, car en soi le nœud peut continuer à fonctionner même si la tache de distance panic.
Dans le code de cette task il te faudra souscrire aux notifications liées à la finalité avec la méthode client.finality_notification_stream().
A chaque notif tu récupères le hash du block finalisé et tu consultes le onchain storage associé à ce block hash pour déterminer si un calcul de distance doit être fait et si oui sur quelles données.
Voila j’ai investigué un peu pour te simplifier la tâche, car je pense que tu n’aurais pas trouvé ces éléments tout seul, ni personne d’autre ici (si je me trompe faites le moi savoir, ça me rassurerait de ne plus être le seul expert substrate).
Je pensais que les _blocking n’étaient que des wrappers transformant la fonction en future et ajoutant .await. Donc que bloquant ou pas ne changerait pas l’effet sur les autres tâches (et que rt-multi-thread permet moins de congestion en utilisant plusieurs threads, mais je n’ai pas l’impression qu’on l’utilise).
Non pas du tout, si tu regardes les définitions des types ça attend des futures dans les 2 cas.
Ici c’est relatif au fonctionnement interne de tokio, qui à deux threadpool (les deux sont déjà multi-thread), un pour les taches dont l’exécution est effectivement asynchrone et un pour les autres taches (dites blocking).
Un code est considéré comme effectivement asynchrone s’il occupe très peu de temps cpu entre deux yield.
Je précise que là c’est des notions qui n’ont aucun rapport avec substrate, c’est purement la notion même d’asynchrone, je t’invite à lire des articles sur le sujet, comme celui-ci par exemplei: Async: What is blocking? – Alice Ryhl
Non c’est de la merde, recommence et fait mieux stp. Un peu de sérieux.
Je vais finir par le faire en python.
En fait on va plutôt partir sur l’exploration de graphe à l’ancienne, qui est en temps borné en fonction de N. Les matrices prennent beaucoup trop de mémoire (quadratique, et dès qu’on dépasse les quelques Go ça ne tient plus en RAM donc ça fait exploser le temps d’exécution).
Après je ne perds pas l’espoir d’un algo distribué de produit de matrices à l’aide de sous-matrices, mais ça devient très compliqué, surtout si on veut un résultat vérifiable. (et je ne sais même pas s’il existe un algo pour ça)
Pour info, et pour éviter qu’on ne soit plusieurs à bosser sur la même feature, je me penche sur une 1ère implémentation sans Oracle (à la fois pour me faire la main sur Substrate et pour voir dans quelle mesure ce pourrait être suffisant dans un premier temps).
J’ai déjà pas mal avancé, mais j’ai encore besoin de temps avant de présenter du code.
Suite à la publication des résultats de benchmarks basés sur le pire cas actuel de la toile Ğ1, j’en conclue que nous pouvons effectivement nous passer temporairement d’Oracle.
Je compte proposer une MR prochainement pour intégrer la règle de distance en ce sens.
A voir ensuite, selon le temps et la volonté de chacun, de rester dans ce mode pour la migration de la Ğ1 sur Duniter V2S ou d’ajouter l’Oracle.
Les différents éléments de la version avec oracle sont quasiment tous là, et c’est même plus simple que prévu (pas besoin de RPC). Avant de poursuivre j’aimerais arriver à l’intégrer dans les tests cucumber.
Mais puisque ta version sera prête avant et suffira un moment, je peux aussi prioriser autre chose. (je pense par exemple aux màj de substrate, sur lesquelles il serait bon de ne pas trop prendre de retard)