Full_Casper_Chain_V2_fr.md

Chaîne Casper complète v2

Traduction de Full Casper chain v2 par Vitalik Buterin (https://notes.ethereum.org/SCIg8AH5SA-O4C1G1LYZHQ?both#)

Ci-après le document de travail décrivant la spécification de la chaîne Casper+Sharding, version 2. Contrairement à la version antérieure, essentiellement fondée sur la chaîne Ethereum en preuve de travail en tant que chaîne centrale, cette spécification emploie comme base une chaîne complètement preuve d'enjeu fondée sur un phare (beacon) RANDAO, des attestations et le mécanisme de Casper FFG, avec un lien relativement simple vers la chaîne en PoW intégrant le référencement de blocs et des dépôts à sens unique.

Description générale de la structure

Il existe une chaîne centrale en PoS qui stocke et gère l'ensemble courant des validateurs PoS actifs. Le seul mécanisme disponible pour devenir un validateur initialement consiste à envoyer une transaction de 32 ETH sur la chaîne principale en PoW. Ceci fait, dès que la chaîne en PoS traite ce bloc, on est mis en file d'attente et finalement accepté comme validateur actif jusqu'ầ un retrait volontaire ou forcé dans le cas d'une pénalité pour inconduite.

La principale source de charge sur la chaîne en PoS vient des liaisons transversales (cross-links). Une liaison transversale est un type de transaction qui dit « Voici le hash, l'empreinte, d'un bloc récent sur le fragment X. Voici les signatures d'au moins 2/3 d'un échantillon sélectionné aléatoirement de M validateurs (p.ex. M = 1024) qui attestent la validité de la liaison transversale. » Chaque fragment est lui-même une chaîne en PoS et les chaînes fragments sont le lieu de stockage des transactions et des comptes. Les liaisons transversales servent à « confirmer » des segments des chaînes fragments dans la chaîne principale et sont également le moyen principal par lequel les fragments peuvent communiquer entre eux.

Note : le code Python sur https://github.com/ethereum/beacon_chain ne reflète pas l'intégralité des derniers changements. S'il existe une différence, ce document devrait refléter les dernières modifications.

Terminologie

• Validateur (Validator) - un participant au système de consensus Casper/sharding. On peut en devenir un en déposant 32 ETH dans le mécanisme de Casper.
• Ensemble des validateurs actifs (Active validator set) - ceux des validateurs qui participent actuellement et par lesquels le mécanisme Casper cherche à produire et à attester des blocs, des liaisons transversales et des autres objets de consensus.
• Notaire (Notary) - Un signataire d'une liaison transversale
• Comité (Committee) - Un sous-ensemble échantillonné (pseudo-)aléatoirement de l'ensemble des validateurs actifs. Quand on se réfère collectivement à un comité, comme dans « ce comité atteste X », cela est censé signifier « un sous-ensemble de ce comité qui contient assez de validateurs pour que le protocole le reconnaisse comme représentant le comité ».
• Proposant (Proposer)- Le validateur qui crée un bloc.
• Attestataire (Attester) - Un validateur faisant partie d'un comité qui doit signer un bloc.
• Chaîne phare (Beacon chain)- La chaîne centrale en PoS qui est la base du système de fragmentation.
• Chaîne fragment (Shard chain) - L'une des chaînes sur lesquelles les transactions ont lieu et où les données des comptes sont stockées.
• Chaîne principale (Main chain) - Employé ici pour désigner la chaîne en PoW existante, bien qu'il faille noter son caractère temporaire ; à terme, la chaîne phare sera la chaîne principale.
• Liaison transversale (Cross-link) - Un ensemble de signatures d'un comité attestant d'un bloc dans une chaîne fragment, qui peut être incluse dans la chaîne phare. Les liaisons transversales représentent le principal moyen par lequel la chaîne phare « est mise au courant » de l'évolution de l'état des chaînes fragment.
• Époque (Epoch) - Une période de 100 blocs.
• Finalisé (Finalized) - Voir la finalisation de Casper ici : https://arxiv.org/abs/1710.09437
• SHARD_COUNT - Une constante donnant le nombre de fragments. Actuellement 1024.
• NOTARIES_PER_CROSSLINK - Une constante donnant la taille de l'ensemble des notaires pour une liaison transversale. Actuellement 1024.

Changements de la chaîne principale

Cette proposition de PoS/Sharding peut être implémentée séparément de la chaîne principale. Seuls deux changements à la chaîne principale sont requis (et le second n'est techniquement pas nécessaire).

• Sur la chaîne principale un contrat est ajouté ; ce contrat vous permet de déposer 32 ETH ; la fonction deposit prend en arguments (i) pubkey, (ii) withdrawal_shard_id (int), (iii) withdrawal_addr (address) et (iv) randao_commitment (bytes32)
• Les clients de la chaîne principale implémenteront une méthode, prioritize(block_hash, value). Si le bloc est disponible et a été vérifié, cette méthode donne la valeur à son score et ajuste récursivement les scores de tous les descendants. Cela permet également au gadget de finalité de la chaîne phare en PoS de finaliser implicitement les blocs de la chaîne principale.

Chaîne phare

La chaîne phare est la « chaîne principale » du système de PoS. Les principales responsabilités de la chaîne phare sont :

• Stocker et maintenir l'ensemble des validateurs actifs, en file d'attente et partis ;
• Traiter les liaisons transversales (voir plus haut) ;
• Traiter son propre consensus bloc par bloc ainsi que le gadget de finalité de FFG.

Voici les champs allant dans chaque bloc de chaîne phare :

fields = {
    # Empreinte du bloc parent
    'parent_hash': 'hash32',
    # Nombre de sauts (pour le mécanisme de PoS complet)
    'skip_count': 'int64',
    # Révélation de l'engagement de Randao
    'randao_reveal': 'hash32',
    # Champ de bits de ceux du comité d'attestation qui ont participé
    'attestation_bitfield': 'bytes',
    # Leur signature agrégée
    'attestation_aggregate_sig': ['int256'],
    # Vote agrégé de fragment
    'shard_aggregate_votes': [AggregateVote],
    # Référence au bloc de la chaîne principale
    'main_chain_ref': 'hash32',
    # Empreinte de l'état
    'state_hash': 'bytes',
    # Signature du proposant
    'sig': ['int256']
}

L'état de la chaîne phare est éclatée en deux parties, crystallized state et active state. L'état actif change à chaque bloc alors que l'état cristallisé ne change qu'à chaque époque (100 blocs). Voici l'état actif :

fields = {
    # Hauteur du bloc
    'height': 'int64',
    # État du phare RANDAO global
    'randao': 'hash32',
    # Quels validateurs ont effectué un vote FFG pendant cette époque (en champ de bits)
    'ffg_voter_bitfield': 'bytes',
    # Attestataires du bloc à la dernière époque
    'recent_attesters': ['int24'],
    # Stocage de données sur les liaisons transversales en cours pendant cette époque
    'partial_crosslinks': [PartialCrosslinkRecord],
    # Nombre total de sauts (utilisé pour déterminer l'horodatage minimal)
    'total_skip_count': 'int64',
    # Proposants de blocs à la dernière époque
    'recent_proposers': [RecentProposerRecord]
}

Chaque PartialCrosslinkRecord est un objet contenant des informations sur les liaisons transversales mises en place pendant cette époque :

fields = {
    # Le fragment pour lequel la liaison transversale est construite
    'shard_id': 'int16',
    # Empreinte du bloc
    'shard_block_hash': 'hash32',
    # Ceux des votants éligibles qui votent pour lui (champ de bits)
    'voter_bitfield': 'bytes'
}

Chaque RecentProposerRecord est un objet contenant des informations sur les proposants de blocs récents :

fields = {
    # CIndex des proposants
    'index': 'int24',
    # Nouvel engagement RANDAO
    'randao_commitment': 'hash32',
    # Delta du solde
    'balance_delta': 'int24'
}

Et voici l'état cristallisé :

fields = {
    # Liste des validateurs actifs
    'active_validators': [ValidatorRecord],
    # Liste des validateur inscrits mais non encore acceptés
    'queued_validators': [ValidatorRecord],
    # Liste des validateurs supprimés  en attendant un retrait
    'exited_validators': [ValidatorRecord],
    # La permutation des validateurs utilisée pour déterminer l'origine 
    # des liaisons transversales vers des fragments à cette époque
    'current_shuffling': ['int24'],
    # L'époque courante
    'current_epoch': 'int64',
    # La dernière époque justifiée
    'last_justified_epoch': 'int64',
    # La dernière époque finalisée
    'last_finalized_epoch': 'int64',
    # La dynastie courante
    'dynasty': 'int64',
    # Le fragment suivant d'où partira cette affectation de liaison transversale
    'next_shard': 'int16',
    # Le point de contrôle FFG courant
    'current_checkpoint': 'hash32',
    # Enregistrements sur la liaison transversale la plus récente pour chaque fragment
    'crosslink_records': [CrosslinkRecord],
    # Solde total des dépôts
    'total_deposits': 'int256',
    # Utilisé pour sélectionné les comités pour chaque fragment
    'crosslink_seed': 'hash32',
    # Dernière époque à laquelle la _seed_ de liaison transversale a été réinitialisée
    'crosslink_seed_last_reset': 'int64'
}

Chaque ValidatorRecord est un objet contenant des informations sur un validateur :

fields = {
    # La clef publique du validateur
    'pubkey': 'int256',
    # Le fragment auquel le solde du validateur sera envoyé
    # après le retrait
    'withdrawal_shard': 'int16',
    # Et l'adresse
    'withdrawal_address': 'address',
    # La mise en gage du validateur au phare RANDAO courant
    'randao_commitment': 'hash32',
    # Solde courant
    'balance': 'int64',
    # Dynastie où le validateur peut 
    # (être accepté | être supprimé | retirer son solde)
    'switch_dynasty': 'int64'
}

Et un CrosslinkRecord contient des informations sur la dernière liaison transversale pleinement formée à avoir été soumise à la chaîne :

fields = {
    # À quelle époque le liaison transversale a été soumise
    'epoch': 'int64',
    # L'empreinte du bloc
    'hash': 'hash32'
}

La racine de l'état est égale à la concaténation de blake(serialize(crystallized_state)) et de blake(serialize(active_state)). Notons que cela signifie que, la plupart du temps, quand l'état cristallisé n'a pas changé, il n'a pas besoin d'être recalculé. L'état actif est généralement assez petit (p.ex. ~1 MB pour maximum théorique de 4M validateurs, ~100KB en étant plus réaliste) et l'état cristallisé est plus grand, atteignant des dizaines de mégaoctets.

Traitements de la chaîne phare

Les traitements sur la chaîne phare sont fondamentalement similaires aux traitements sur une chaîne en PoW par bien des aspects. Les clients téléchargent et traitent les blocs, et maintiennent une vue de la « chaîne canonique » courante, se terminant à la « tête » courante. Cependant, en raison des relations de la chaîne phare avec la chaîne en PoW existante et de sa nature de chaîne en PoS, il existe des différences.

Pour qu'un bloc sur la chaîne phare puisse être traité par un nœud, trois conditions doivent être remplies :

• Le parent pointé par le parent_hash a déjà été traité et accepté ;
• Le bloc de la chaîne principale vers lequel pointe main_chain_ref a déjà été traité et accepté ;
• L'heure de l'horloge locale du nœud est supérieure ou égale à l'horodatage minimum tel qu'il est calculé par GENESIS_TIME + height * PER_HEIGHT_DELAY + total_skips * PER_SKIP_DELAY.

Si ces trois conditions ne sont pas remplies, le client doit retarder le traitement du bloc jusqu'à ce qu'elles le soient.

La production de blocs diffère significativement en raison du mécanisme de preuve d'enjeu. À chaque fois que le client change sa vue de la tête (voir la section sur le choix de la branche plus loin pour la manière dont est définie la tête), il doit calculer les proposants du bloc pour toutes les valeurs de skip_count de 0 à M pour un M suffisamment grand (voir les algorithmes ci-dessous). Soit i le skip_count où le client est sélectionné. Quand l'horodatage atteint minimum_timestamp(head) + PER_HEIGHT_DELAY + i * PER_SKIP_DELAY, et si la tête n'a pas encore changé, alors le client doit publier un nouveau bloc.

Quand un client change sa vue de la tête, il doit aussi calculer la liste des attestataires (un ensemble de validateurs qui doit approuver sur la tête ; voir ci-dessous pour les détails) et immédiatement publier une attestation pour ce bloc en signant la forme sérialisée du bloc parent avec leur clef.

Beacon chain fork choice rule

Quand la chaîne phare deviendra un système en PoS autonome, la règle du choix de la branche sera une règle simple de bloc de plus haut score, ce score étant le même que dans Casper FFG.

score = last_justified_epoch + height * ε

Tant qu'elle est implémentée comme tag-along de la chaîne en PoW, la règle du choix de la branche est une règle de choix de branche dépendante : la tête de la chaîne phare est le bloc dont le score est le plus haut avec une main_chain_ref qui est dans la chaîne principale dont le score est le plus haut.

En raison d'une condition de validité supplémentaire qui impose que la main_chain_ref d'un bloc phare soit égale à ou un descendant de celle de son parent, cela implique que la main_chain_ref de chaque bloc dans cette chaîne phare soit à l'intérieur de la chaîne principale de plus haut score. Cela garantit que la chaîne phare suit la chaîne principale en PoW réellement canonique.

Cela peut être « mis à jour en ligne » grâce aux algorithmes suivants. D'abord, il est important de garder la trace non seulement de la tête des chaînes phare et principale mais également des blocs à toutes les hauteurs. Cela peut être maintenu par l'algorithme suivant, à lancer à chaque changement de la tête.

def update_head(chain, old_head, new_head):
    a, b = old_head, new_head
    while a.height > b.height:
        a = get_parent(a)
    while b.height > a.height:
        b = get_parent(b)    
    while a != b:
        a, b = get_parent(a), get_parent(b)
    b = new_head
    new_chain = []
    while b.height > a.height:
        new_chain = [b] + new_chain
        b = get_parent(b)
    chain = chain[:a.height + 1] + new_chain

Quand on reçoit un nouveau bloc de chaîne phare, on ne change la tête que si sont score représente une amélioration par rapport à celui de la tête et si la main_chain_ref du nouveau bloc se trouve dans la chaîne principale :

def should_I_change_head(main_chain, old_beacon_head, new_beacon_block):
    return get_score(new_beacon_block) > get_score(old_beacon_head) and \
        new_beacon_block.main_chain_ref in main_chain

Après une réorganisation de la chaîne principale, on réorganise aussi la chaîne phare :

def reorg_beacon_chain(main_chain, beacon_chain):
    old_head = beacon_chain[-1]
    while beacon_chain[-1].main_chain_ref not in main_chain:
        beacon_chain.pop()
    queue = [beacon_chain[-1]]
    new_head = beacon_chain[-1]
    while len(queue) > 0:
        b = queue.pop(0)
        for c in get_children(b):
            if c.main_chain_ref in main_chain:
                if get_score(c) > get_score(new_head):
                    new_head = c
                queue.append(c)
    update_head(beacon_chain, old_head, new_head)

Fonction de transition d'état de la chaîne phare

Nous définissons maintenant la fonction de transition d'état. Au plus haut niveau, la transition d'état est constituée de deux parties :

1. La transition d'époque, qui ne se produit que si active_state.height % SHARD_COUNT == 0 et qui affecte l'état cristallisé et l'état actif ;
2. Le traitement des bloc, qui se produit à chaque bloc (si, durant un bloc de transition d'époque, il se produit après la trnasition d'époque) et n'affecte que l'état actif.

La transition d'époque est généralement centrée sur les changements de l'ensemble des validateurs, y compris l'ajustement des soldes et l'ajout et le retrait des validateurs, ainsi que le traitement des liaisons transversales et la mise en place des points de contrôle FFG, et le traitement par bloc est généralement centré sur la sauvegarde des enregistrements temporaires liés à l'activité propre aux blocs dans l'état actif.

Fonctions helper

Nous commençons par définir des algorithmes helper. D'abord, un algorithme pour mélanger pseudo-aléatoirement l'ensemble des validateurs en fonction d'une seed donnée :

def get_shuffling(seed, validator_count):
    assert validator_count <= 16777216
    rand_max = 16777216 - 16777216 % validator_count
    o = list(range(validator_count)); source = seed
    i = 0
    while i < validator_count:
        source = blake(source)
        for pos in range(0, 30, 3):
            m = int.from_bytes(source[pos:pos+3], 'big')
            remaining = validator_count - i
            if remaining == 0:
                break
            if validator_count < rand_max:
                replacement_pos = (m % remaining) + i
                o[i], o[replacement_pos] = o[replacement_pos], o[i]
                i += 1
    return o

Cet algorithme sera utilisé pour sélectionner les comités des fragments et pour sélectionner les proposants et les attestataires des blocs. Voici l'application de la méthode pour choisir l'ensemble des attestataires pour un bloc donné et le proposant pour le fils à N-sauts de ce bloc.

def get_attesters_and_proposer(crystallized_state, active_state, skip_count):
    attestation_count = min(len(crystallized_state.active_validators), ATTESTER_COUNT)
    indices = get_shuffling(active_state.randao, len(crystallized_state.active_validators))
    return indices[:attestation_count], indices[attestation_count + skip_count]

Pour les liaisons transversales entre fragments, le processus est un peu plus compliqué. D'abord nous choisissons l'ensemble des fragments actifs pendant chaque époque. Nous voulons cibler un nombre fixe de notaires par liaison transversale mais cela signifie que, puisqu'il y a un nombre fixe de fragments et un nombre variable de validateurs, nous ne pouvons pas passer par chaque fragment à chaque époque. Nous devons donc d'abord sélectionner les fragments qui feront l'objet d'une liaison transversale à une époque donnée :

def get_crosslink_shards(crystallized_state):
    start_from = crystallized_state.next_shard
    count = len(crystallized_state.active_validators) // NOTARIES_PER_CROSSLINK
    if start_from + count <= SHARD_COUNT:
        return list(range(s, s+count))
    else:
        return list(range(start_from, SHARD_COUNT)) + list(range(start_from + count - SHARD_COUNT))

Puis nous calculons l'ensemble des notaires pour chacun de ces fragments :

def get_crosslink_notaries(crystallized_state, shard_id):
    crosslink_shards = get_crosslink_shards(crystallized_state)
    if shard_id not in crosslink_shards:
        return None
    all = len(crystallized_state.current_shuffling)
    start = all * crosslink_shards.index(shard_id) // len(crosslink_shards)
    end = all * (crosslink_shards.index(shard_id)+1) // len(crosslink_shards)
    return crystallized_state.current_shuffling[start: end]

Le current_shuffling est recalculé au départ d'une transition de dynastie.

Traitement par bloc

Le traitement des blocs se décompose en trois parties.

Vérification des signatures des attestations

Le nombre attendu d'attestataires pour un bloc est min(len(crystallized_state.active_validators), ATTESTER_COUNT), cette valeur étant attester_count. On vérifie que le tableau d'octets attestation_bitfield de longueur (attester_count + 7) // 8.???? On l'interprète comme une liste de bits allant de gauche à droite (c.à.d. que le bit 0 est attestation_bitfield[0] >> 7, bit 9 est attestation_bitfield[1] >> 6, etc). On vérifie que tous les bits aprèsattester_count-1 sont à zéro. On vérifie que le nombre total d'attestateurs (c.à.d. le nombre total de bits à 1 est au moins attester_count / (2 + block.skip_count).

On interprète les bits à un dans le champ de bits comme un sous-ensemble des attestateurs échantillonné avec get_attesters_and_proposer (voir plus haut) ; on extrait les indices des attestateurs puis on extrait leurs clefs publiques depuis crystallized_state.active_validators. On additionne ces clefs publiques pour fabriquer une clef agrégée. On vérifie par BLS l'attestation_aggregate_sig dans le bloc en utilisant la clef agrégée comme une clef publique et le bloc parent sérialisé comme le message. On s'assure que la vérification passe.

On ajoute un ProposerRecord à la liste recent_proposers stockant l'index des proposants, la nouvelle préimage RANDAO du proposant et le nombre d'attestataires dont sont inclues les signatures. On ajoute les indices des attestataires (dans l'ordre dans lequel ils apparaissent dans le champ de bits) à recent_attesters.

Vérification des enregistrements de liaisons transversales partielles

Un bloc peut avoir 0 ou plus objets AggregateVote, où chaque objet AggregateVote possède les champs suivants :

fields = {
    'shard_id': 'int16',
    'shard_block_hash': 'hash32',
    'notary_bitfield': 'bytes',
    'aggregate_sig': ['int256']
}

Pour chacun de ces votes :

• On utilise get_shard_attesters pour obtenir la liste des indices des attestataires de liaisons transversales. On vérifie la signature agrégée pour les attestataires de blocs ci-dessus ;
• Sur un objet PartialCrosslinkRecord existe déjà pour les mêmes ID et empreinte de bloc, on ajoute à son voter_bitfield les indices locaux des validateurs qui ont participé au AggregateVote (c'est-à-dire voter_bitfield |= AggregateVote.notary_bitfield). Si un PartialCrosslinkRecord n'existe pas encore, on en crée un ;
• On ajoute aussi les indices des votants dans le active_state.ffg_voter_bitfield ;
• On ajoute un delta de solde donnant au proposant du bloc une récompense de n s'il y a un total de n votants qui n'ont pas encore voté.

On sauvegarde la nouvelle liste d'objets PartialCrosslinkRecord dans l'ordre trié par shard_block_hash.

Divers

• On incrémente la hauteur; 
• On vérifie la signature du bloc lui-même en utilisant le bloc avec les octets de signature mis à zéro comme données de signature ;
• On incrémente le décompte total de saut du nombre de sauts du bloc ;
• On vérifie que la révélation RANDAO du bloc est la préimage de l'empreinte de la mise en gage RANDAO sauvegardée du proposant. On XOR la révélation RANDAO du bloc dans l'état RANDAO actif et la révalation RANDAO devient la nouvelle mise en gage du proposant.

Transitions d'époques

Quand la hauteur de bloc courante (c.à.d. la hauteur de l'état actif) est à 0 mod SHARD_COUNT, nous exécutons une transition d'époque qui se décompose en plusieurs parties :

Calculer les récompenses pour les votes FFG

• Calculer les dépôts totaux de chaque validateur ayant participé pendant la dernière époque (d'après le champ de bits des votants FFG dans l'état actif). Si cette valeur est ≥ 2/3 des dếpôts totaux de tous les validateurs, crystallized_state.justified_epoch est mis à crystallized_state.current_epoch (note : il s'agit toujours de l'époque précédente à ce point du calcul). Si celà se produit, et si l'époque justifiée était précédemment crystallized_state.current_epoch - 1, crystallized_state.finalized_epoch devient égal à cette valeur.
• Calculer les online_reward et offline_penalty en se basant sur les incitations de Casper FFG et les quadratic leak rules (restent à spécifier complètement) ;
• Ajouter la online_reward à chaque validateur qui a participé pendant l'époque précédente et soustraire la offline_penalty de ceux qui n'ont pas participé.

Calculer les récompenses pour les liaisons transversales

Répéter pour chaque fragment :

• Calculer les online_reward et offline_penalty pour cette liaison transversale ;
• Prendre la liaison transversale partielle avec le plus de vote (en classant les liaisons par ordre d'empreinte de point de contrôle). Récompenser tous les validateurs qui ont participé à cette liaison transversale partielle ; pénaliser les autres.
• Si une liaison transversale atteint ≥ 2/3 de son échantillon, pondéré par les dépôts totaux (en excluant les deltas de solde qui font partie de cette transition d'époque), on la sauvegarde comme la liaison transversale la plus récente.

Traiter les deltas de soldes

Incrémenter le solde de tous les recent_attesters de 1. Incrémenter le solde de tous les recent_proposers de balance_delta dans l'objet RecentProposerRecord.

Calculs liés aux seed des liaisons transversales

Si current_epoch - crosslink_seed_last_reset est une exacte puissance de deux, alors en utilisant temp_seed = blake(crosslink_seed + bytes([log2(current_epoch - crosslink_seed_last_reset)])) on pose current_shuffling = get_shuffling(temp_seed, len(new_active_validators)). Notons que tous ceux des comités temporaires sont prévisibles par la crosslink_seed mais leur positionnement augmente exponentiellement (c.à.d. de 10001 à 10002, de 10002 à 10004, de 10004 à 10008, de 10008 à 10016…).

Le backoff exponentiel garantit que, s'il n'y a pas eu de liaison transversale pendant N époques, le comité suivant aura ~N/2 époques pour traiter et vérifier les ~N époques d'historique pour ce fragment, ce qui signifie que la quantité de travail par seconde que les nœuds du comité doivent effectué est limité.

Transistion de dynastie

Si les conditions suivantes sont toutes les deux vraies :

• Les deux dernières époques étaient justifiées ;
• La hauteur de la liaison transversale la plus récemment enregistrée pour chaque fragment est plus grande ou égale à crosslink_seed_last_reset.

Alors :

• Incrémenter crystallized_state.dynasty ;
• Passer par tous les queued_validators dans l'ordre du premier au dernier. Tout validateur dont switch_dynasty est égal ou antérieur à la nouvelle dynastie est immédiatement ajouté à la fin de active_validators (en mettant switch_dynasty à l'entier le plus élevé possible) jusqu'à un maximum de (len(crystallized_state.active_validators) // 30) + 1 (remarquez que comme queued_validators est trié, il suffit soit de vérifier les validateurs en file d'attente au départ jusqu'à ce que vous en ayez traité suffisamment, soit d'en atteindre un dont le switch_dynasty soit plus avancé que la dynastie courante) ;
• Passer par tous les active_validators et déplacer ceux dont (i) le solde est égal à ≤ 50% de leur solde initial, ou (ii) switch_dynasty est égal ou inférieur à la dynastie courante, vers exited_validators, en montant à un maximum de (len(crystallized_state.active_validators) // 30) + 1 validateurs.

Divers

• Incrémenter l'époque courante ;
• Donner à current_checkpoint la valeur de l'empreinte du bloc précédent ;
• Réinitialiser les deltas de soldes, le champ de bits des votants FFG et la liste des liaisons transversales partielles ;
• Mettre à jour les mises en gage RANDAO des validaeurs d'après les valeurs de RecentProposerRecord.

Analyse de l'overhead

Avec un validateur par 32 ETH, trois cas se présentent à nous :

• 31250 validateurs (1M ETH), cas minimal ;
• 312500 validateurs (10M ETH), cas moyen ;
• 4000000 validateurs (en posant 128M ETH comme limite d'émission), au pire des cas : absolument tout le monde mise.

La taille de l'état actif est :

'height': 8 octets
'randao': 32 octets,
'ffg_voter_bitfield': 1/8 octets par validateur,
'recent_attesters': 3 octets/attestataire, ~130 attestataires/bloc, 100 blocs/époque:
                    39000 octetx
'partial_crosslinks': PartialCrosslink * (nombre de validateurs / 1024)
'total_skip_count': 8 octets
'recent_proposers': (3 + 32 + 3) octets par RecentProposerRecord *
                    100 proposants = 3800 octets

Les liaisons transversales ajoutent :

'shard_id': 2 octets,
'shard_block_hash': 32 octets,
'voter_bitfield': 1/8 octet/validateur * 1024 validateurs = 128 octets

Chaque liaison transversale fait donc 162 octets et les données fixes 42848 octets. Par validateur, nous avons 1/8 d'octet dans le champ de bits FFG et 162/1824 ~= 0.158 octets par validateur dans la liaison transversale partielle, un total de ~0.283 octet par validateur. Nous obtenons donc pour la taille totale de l'état actif :

• 1M ETH: 42848 + 31250 * 0.283 = 51692 octets
• 10M ETH: 42848 + 312500 * 0.283 = 131286 octets
• 128M ETH: 42848 + 31250 * 0.283 = 1174848 octets

La taille de l'état cristallisé est :

'active_validators': [ValidatorRecord],
'queued_validators': [ValidatorRecord],
'exited_validators': [ValidatorRecord],
'current_shuffling': 3 octets par validateur,
'current_epoch': 8 octets,
'last_justified_epoch': 8 octets,
'last_finalized_epoch': 8 octets,
'dynasty': 8 octets,
'next_shard': 2 octets,
'current_checkpoint': 32 octets,
'crosslink_records': [CrosslinkRecord],
'total_deposits': 32 octets,
'crosslink_seed': 32 octets,
'crosslink_seed_last_reset': 8 octets

Cela représente un coût fixe de 141 octets hors liaisons transversales et validateurs.

Un ValidatorRecord contient :

'pubkey': 32 octets,
'withdrawal_shard': 2 octets,
'withdrawal_address': 20 octets,
'randao_commitment': 32 octets,
'balance': 8 octets,
'switch_dynasty': 8 octets

Ce qui fait 102 octets au total. Nous supposerons que les ensembles en file d'attente et en instance de sortie sont vides dans un but de simplicité et nous nous concentrons sur l'ensemble actif.

Un CrosslinkRecord est simplement :

'epoch': 8 octets,
'hash': 32 octets

Donc la liste crosslink_records ne fait que 40 octets par fragment. Le nombre total de fragments est déterminé par le nombre maximum de validateurs : 128 millions / 32 / 1024 ~= 4000 fragments et crosslink_records prendrait donc 160000 octets.

D'où, avec un coût fixe de 160141 octets et un coût variable de 102 octets par validateur, nous obtenons une taille totale de l'état cristallisé :

• 1M ETH: 160141 + 102 * 31250 = 3347641 octets
• 10M ETH: 160141 + 102 * 312500 = 32035141 octets
• 128M ETH: 160141 + 102 * 4000000 = 408160141 octets

Donc même dans le cas le plus extrême, l'état de la chaîne phare peut tenir dans la RAM d'un ordinateur relativement vieux. Un hachage Blake de 400 Mo ne prend que ~1,0 seconde lors de tests sur ma machine, (Thinkpad X270), un résultat de pire des cas très acceptable pour quelque chose qui n'est censé se produire que tous les 100 blocs, bien que nous puissions encore améliorer l'efficacité ici par l'emploi judicieux d'arbres de Merkle.

Un bloc contient :

'parent_hash': 32 octets,
'skip_count': 8 octets,
'randao_reveal': 32 octets,
'attestation_bitfield': 1/8 octet par participant, donc 16 octets,
'attestation_aggregate_sig': 64 octets,
'shard_aggregate_votes': [AggregateVote],
'main_chain_ref': 32 octets,
'state_hash': 64 octets,
'sig': 64 octets

Un AggregateVote est :

'shard_id': 2 octets,
'shard_block_hash': 32 octets,
'notary_bitfield': 1/8 octet/validateur * 1024 validateurs,
'aggregate_sig': 64 octets

Un bloc sans les votes agrégés va jusqu'à 312 octets. Chaque vote agrégé fait 226 octets ; nous attendons nombre de validateurs / 1024 votes agrégés par époque (et 1/100 de cela par bloc), et nous obtenons pour la taille moyenne des blocs :

• 1M ETH: 312 + 31250 * 226 / 1024 / 100 = 380 octets
• 10M ETH: 312 + 312500 * 226 / 1024 / 100 = 1002 octets
• 128M ETH: 312 + 4000000 * 226 / 1024 / 100 = 9140 octets

Le traitement des blocs demande :

• Le re-hachage de l'état actif ;
• Le re-hachage de l'état cristallisé (uniquement lors d'une transition d'époque) ;
• La vérification d'une signature BLS pour le bloc, plus une pour les attestations, plus une pour chaque enregistrement de liaison transversale. Dans le cas le plus favorable, 5 par bloc, dans le plus défavorable, 41 par bloc ;
• 2 opérations ECADD par époque (c.à.d. 0.02 par bloc) par validateur pour la vérification des signatures agrégées, plus un nombre fixe de ~128 opérations ECADD par bloc. Dans le cas le plus favorable, ~753 (équivalent à <1 signature ECDSA), en moyenne ~6378 (~5-10 signatures ECDSA), dans le cas le plus défavorable, ~80128 (~50-100 signatures ECDSA) ;
• Beaucoup d'opérations relativement peu coûteuses impliquant de boucler sur les validateurs, filtrer sur les champs de bits, etc. etc.

---

Note : Ceci est complet à 80%. Les sections principales qui manquent sont :

• La logique des formats des chaînes fragments, qui propose les blocs des fragments, etc. (dans une version initiale, nous pourrions au besoin nous contenter de racines d'arbres de Merkle de blobs de données pour faire des liaisons transversales ; en tous les cas, on peut voir philosophiquement le principe fondamental des chaînes fragments comme un outil de coordination servant à choisir les blobs de données à proposer comme liaisons transversales) ;
• La logique d'acceptation des validateurs en attente de la chaîne principale ;
• Les conditions de slashing ;
• La logique de retrait des dépôts vers les fragments ;
• Les preuves de détention par validateur.