Un lancer de dés où tous les validateurs tombent d’accord

Solucky est une loterie quotidienne sur Solana. Chaque jour UTC est une manche : les joueurs achètent des tickets numérotés, et après minuit un ticket est tiré pour remporter la cagnotte. On vient de la reconstruire à partir de son prototype de 2022, et ce qui mérite d’être raconté, c’est le tirage. Une blockchain est faite pour que chaque validateur exécute le même code sur les mêmes données et arrive à la même réponse. Une loterie a besoin d’une réponse que personne ne pouvait connaître à l’avance, ni orienter. Voici comment Solucky en obtient une, et où sont ses limites.

D’où le hasard ne peut pas venir

Un programme ne peut pas appeler un générateur de nombres aléatoires. Chaque validateur rejoue chaque transaction et doit arriver au même état : toute entrée d’un tirage doit donc être une donnée que tout le cluster partage déjà. Les candidats évidents échouent pour une même raison : on peut les connaître avant que la transaction ne s’exécute. Le slot du sysvar Clock avance de un en un, son horodatage est public, et une transaction doit normalement porter un blockhash récent pour être acceptée. Un joueur pourrait simuler le tirage, et ne le laisser passer que s’il gagne. Même SlotHashes, le sysvar que Solucky lit bel et bien, ne contient que des slots déjà passés.

Il existe deux réponses classiques. Avec le commit–reveal, chaque joueur publie le hash d’un secret, révèle ce secret à la clôture des ventes, et le tirage les mélange tous. Personne ne peut orienter le résultat seul, mais le dernier à révéler le voit en premier et peut refuser. Une fonction aléatoire vérifiable, ou VRF, confie le secret à un oracle : il répond à une graine par une sortie et une preuve, et chacun peut vérifier avec sa clé publique qu’aucune autre sortie n’était possible. L’oracle ne peut pas choisir le nombre. Il peut seulement ne pas répondre. Solucky n’utilise ni l’un ni l’autre. Il coupe le tirage en deux dans le temps : d’abord il fixe un slot qui n’existe pas encore, puis il lit le hash de ce slot une fois qu’il existe.

Un slot que personne n’a encore vu

Les tickets d’un jour ne s’achètent que tant que l’horloge du cluster est encore dans ce jour : les ventes s’arrêtent d’elles-mêmes à minuit UTC. Chaque achat est intégré à un SHA-256 cumulatif que la manche garde sous le nom entropy : la valeur précédente, l’acheteur, le nombre, le slot et l’adresse du ticket. Après minuit, n’importe qui peut appeler close_round. Il vérifie l’horloge et fixe target_slot, huit slots plus loin. À ce moment-là, les ventes sont closes, et le hash du slot visé n’existe pas encore.

Une fois ce slot passé, n’importe qui peut appeler draw_round. Il lit le hash du slot dans SlotHashes, la liste des 512 derniers slots produits et de leurs hashs. Si le slot fixé a été sauté, il prend le premier slot produit après lui. Puis il hache le tout et garde les huit premiers octets :

let (slot, slot_hash) = {
    let data = ctx.accounts.slot_hashes.try_borrow_data()?;
    find_slot_hash(&data, round.target_slot).ok_or(SoluckyError::RandomnessUnavailable)?
};

let randomness = hashv(&[
    &round.entropy,
    &slot_hash,
    &slot.to_le_bytes(),
    round_key.as_ref(),
])
.to_bytes();
let seed = u64::from_le_bytes(randomness[..8].try_into().unwrap());
let winning_index = (seed % u64::from(round.ticket_count)) as u32;

Chaque validateur lit le même sysvar, donc tous tombent sur le même indice. Le champ entropy n’ajoute aucun secret, puisque toutes ses entrées sont publiques : il lie le résultat à la liste exacte des tickets vendus, et c’est le hash du slot qui apporte le hasard. L’indice désigne un achat, pas un nombre, et le nombre gagnant est lu ensuite sur ce ticket. Il y a donc toujours exactement un gagnant, jamais d’égalité, et comme une manche n’existe qu’à partir de son premier ticket vendu, rien n’est reporté. Vos chances, ce sont vos tickets sur l’ensemble des tickets vendus ce jour-là. N’importe qui peut ensuite envoyer claim_prize, qui verse la cagnotte, moins une commission de la maison d’au plus 10 %, au propriétaire de ce ticket et à personne d’autre.

Huit octets, modulo n

Cette dernière ligne mérite un second regard. Réduire un nombre uniforme modulo n n’est exactement équitable que si n divise l’intervalle. Un petit cas montre le biais. Tirez un octet, 256 valeurs, et réduisez-le modulo 3 :

256 = 3 × 85 + 1
P(0) = 86/256    P(1) = P(2) = 85/256

Le ticket 0 a 86/85 fois autant de chances de gagner que les autres, soit environ 1,2 % de plus. Plus généralement, écrivons 2⁶⁴ = q·n + r : les r premiers indices reçoivent une valeur de plus que les autres, d’où un avantage de 1/q. Une manche compte ses tickets dans un u32, donc n est inférieur à 2³², q est supérieur à 2³², et l’avantage reste sous 2⁻³², moins d’une part sur quatre milliards. Solucky ne le corrige pas par échantillonnage par rejet, qui écarterait toute graine supérieure ou égale à q·n et hacherait à nouveau. Sur 64 bits, le biais existe, et il est minuscule.

Qui peut encore peser sur le tirage

Ce tirage est équitable face aux joueurs, pas face aux validateurs. Le hash d’un slot est un bank hash : il dépend des transactions du bloc, et c’est le leader de ce slot qui les choisit. Un leader qui détient un ticket peut calculer le résultat de chaque bloc qu’il pourrait publier avant d’en publier un, ou sauter le slot, et le tirage passe alors au suivant, qui peut aussi être le sien, puisque les leaders produisent quatre slots d’affilée. Et comme le calendrier des leaders est connu à l’avance, un validateur qui envoie lui-même close_round peut viser ses propres slots.

Le second point faible, c’est le temps. Dès que le slot fixé existe, n’importe qui peut calculer le gagnant avant de tirer. SlotHashes ne garde que 512 slots, et close_round ne fixe un nouveau slot qu’une fois que le sysvar prouve que l’ancien a disparu pour de bon : personne ne peut jeter un résultat connu avant l’heure. Mais un joueur à qui le résultat déplaît pourrait s’abstenir et espérer que personne ne tire à temps. Face à cela, tirer est ouvert à tous : le dépôt fournit un crank, un script qui clôt, tire et paie chaque manche terminée, et n’importe quel joueur peut faire de même depuis l’app.

Ce tirage est équitable face aux joueurs, pas face aux validateurs.

Tout ce que le tirage a utilisé reste dans le compte de la manche : entropy, le slot lu, son hash et le résultat. La page de la manche, dans l’app, recalcule le dernier SHA-256 et le modulo dans votre navigateur, et dit s’ils correspondent. Cela vérifie le calcul. Le hash du slot, lui, a été lu par le programme dans le sysvar, et entropy peut être reconstruit à partir des transactions buy_ticket de la manche, dans l’ordre, même si le dépôt ne fournit pas encore d’outil pour cela. Pour des cagnottes en argent réel, notre README le dit sans détour : remplacer ce tirage par un oracle VRF comme Switchboard On-Demand ou ORAO VRF. Le tirage tient en une fonction. Pour l’instant, l’app publique tourne sur devnet, avec des SOL de test.