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.

1 « J'aime »

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 »

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).

2 « J'aime »

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 :

  • matrice binaire, ce qui permet d’utiliser 1 octet par coefficient sans overhead (et donc remplacement de ×,+ par &&,||)
  • évaluation paresseuse du OU : on s’arrête dès le premier 1 trouvé. Cela a pour effet de rendre chaque itération plus rapide que la précédente, puisque la matrice ne fait que se remplir de 1. (plus il y a de certifications, plus c’est rapide. On part de O(n^3) pour tendre vers O(n^2).)
  • multithread
  • calcul de (M+I)P plutôt que de P+MP, ce qui évite d’avoir à calculer des additions de matrice (O(n^2)) en plus des produits (O(n^3)). M+I étant constant, on le calcule au début (O(n)).
  • on ne recalcule pas un coefficient qui vaut déjà 1

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.

7 « J'aime »