Precedence et la preuve de vote

Civicpower
6 min readMay 2, 2022

--

Mise à jour 08/12/23 : une version définitive de l’étude sur Precedence et ses preuves d’existence a été publiée par Jérémie Albert et Serge Chaumette à l’occasion de la conférence ACSAC 2023.

Introduction

Precedence permet de structurer des informations en utilisant le même paradigme que dans les technologies de blockchain. Chaque enregistrement est un ensemble arbitraire d’informations binaires qui peut être cryptographiquement lié à un ou plusieurs enregistrements précédents. Un enregistrement est persisté dans un bloc. Un bloc est un ensemble d’enregistrements et peut contenir un ou plusieurs enregistrements. Chaque bloc est cryptographiquement lié au bloc précédent (à l’exception du premier qui est explicitement identifiable comme premier bloc).

L’ensemble des enregistrements que constitue un bloc est structuré sous la forme d’un Merkle Patricia Trie (strictement identique à ceux utilisés dans Ethereum). Cette structuration permet le calcul d’un nombre (appelé root hash), souvent représenté sous forme hexadécimale, qui représente l’ensemble des enregistrements du bloc; chaque modification aussi mineure soit-elle d’un enregistrement impacte la valeur de ce nombre de telle sorte que (i) il n’est pas possible d’impacter un enregistrement sans impacter la valeur du root hash et (ii) il n’est pas possible de déterminer, à partir de ce nombre, l’ensemble des enregistrements qui permet son calcul (on appelle cette classe de fonctions des fonctions à sens unique).

Ce format de données permet d’extraire une preuve d’existence cryptographique de chaque enregistrement dans un bloc. Cela signifie qu’il est possible de mathématiquement démontrer qu’un enregistrement fait partie d’un bloc et que cette preuve est irréfutable car non forgeable à partir d’autres enregistrements.

inBlocks SaaS

Comme vu précédemment, precedence permet de construire des preuves d’existence d’enregistrements à l’intérieur de blocs dont l’ensemble des éléments qui le constitue est résumable à un simple nombre (de 256 bits). La démonstration de la connaissance, l’existence de ce nombre à un instant donné permet de démontrer l’existence de l’ensemble des enregistrements qui ont permis son calcul. Afin de démontrer à tout tiers la valeur de cet horodatage il est nécessaire d’utiliser un tiers de confiance admis de tous. inBlocks utilise Ethereum comme support pour l’enregistrement de ces root hash. La nature immuable des enregistrements (appelés transactions) des blocs Ethereum permet de rendre irréfutable la date à laquelle ce nombre (root hash) a été calculé et ainsi la date à laquelle les enregistrements liés ont pu être créés.

À fins d’optimisation des écritures dans la blockchain Ethereum, la plateforme inBlocks propose un modèle un deux niveaux dans lequel les écritures réalisées dans une blockchain precedence privée permettent de constituer des blocs et de calculer pour chacun le root hash qui est alors automatiquement intégré sous forme d’enregistrement dans une instance precedence mutualisée (et ainsi multi blockchain privées) qui est celle utilisée comme source d’informations pour l’écriture des root hash dans la blockchain Ethereum. Cette architecture permet un volume d’écriture par seconde très important en comparaison de ce que peuvent enregistrer les blockchains de niveau 1 de type Ethereum.

Precedence appliqué au vote en ligne

L’utilisation de Precedence dans le cadre du vote en ligne permet de sécuriser le votant sur plusieurs aspects du processus. Cette première implémentation permet de démontrer à chaque votant :

  • qu’il a été comptabilisé parmi les votants (preuve d’émargement électronique),
  • que son vote n’a pas été modifié (preuve de vote électronique),
  • que son vote a été comptabilisé (preuve de résultats).

Preuve d’émargement électronique

Lors d’un vote en ligne, chaque votant se voit remettre une preuve d’émargement électronique.

Les informations contenues dans l’émargement sont les suivantes:

  • user_civicid : son identifiant sous forme de pseudonyme,
  • ballort_shortcode : l’identifiant de la consultation,
  • ballot_title : le titre de la consultation,
  • ballot_description : la description de la consultation,
  • ballot_engagement : l’engagement de la personne physique ou morale à l’initiative de la consultation à l’issue de la consultation,
  • vote_creation_date : la date de création de la consultation.

L’ensemble de ces informations constitue un enregistrement au sens de l’enregistrement precedence défini préalablement. Cela signifie qu’aucune des informations contenues dans cet enregistrement ne peut être modifiée sans invalider la preuve d’existence de cet émargement électronique.

Preuve de vote électronique

La preuve de vote électronique permet de démontrer l’existence de l’enregistrement constitué des informations suivantes:

  • ballot_shortcode,
  • ballot_title,
  • ballot_description,
  • ballot_engagement,
  • vote_creation_date,
  • questions
  • question_title : titre de la question
  • options
  • option_title : libellé de la réponse
  • vote_choice_option_id : ID du choix de la réponse du participant
  • vote_participation : ID de l’enregistrement de l’émargement électronique dans Precedence.

Comme pour la preuve d’émargement, aucune des informations contenues dans cet enregistrement ne peut être modifiée sans invalider la preuve d’existence et d’intégrité de ce bulletin de vote électronique.

Preuve de comptage des voix / de résultat

La preuve de comptage des voix / résultats permet de démontrer la prise en compte des choix des votants dans les résultats.

L’enregistrement est constitué des informations suivantes :

  • timestamp : horodatage
  • ballot_finished : vote clos (oui/non),
  • ballot_title,
  • ballot_description,
  • ballot_engagement,
  • vote_creation_date,
  • asker_name : nom de l’organisateur,
  • nb_participation : nombre de participants ayant voté,
  • questions
  • question_title,
  • question_nb_vote : nombre de réponses à cette question
  • question_somme_voix : somme des ID des réponses des participants, pour cette question,
  • options
  • option_title,
  • option_nb_vote : combien de fois cette réponse a été choisie
  • option_somme_voix : somme des ID des réponses des participants, pour ce choix de réponse,
  • vote_choice_options : ID des réponses des participants, pour ce choix de réponse,
  • vote_participations : tous les ID des enregistrements dans Precedence des émargements électroniques pour cette consultation,
  • vote_choices : tous les ID des enregistrements dans Precedence des bulletins de vote électronique pour cette consultation.

Là encore, aucune des informations contenues dans cet enregistrement ne peut être modifiée sans invalider la preuve d’existence de cette certification électronique des résultats.

Fonctionnement général d’une preuve d’existence construite par la plateforme inBlocks

Lors de la création d’un enregistrement Precedence à partir d’une donnée D, les informations suivantes sont calculées puis enregistrées :

  • id: identifiant de l’enregistrement (fourni ou généré aléatoirement),
  • seed* : graine d’obfuscation des données définie aléatoirement
  • hash* : hash de la donnée D
  • chains* : ensemble des sous-chaînes de l’enregistrement (possiblement vide)
  • previous* : liste du ou des identifiants des enregistrements représentant le même actif (possiblement vide)
  • address : clef publique correspondante à la clef privée utilisée pour la signature du hash du document D (optionnelle)
  • signature : signature du hash du document D (optionnelle).

L’ensemble des informations marquées d’une astérisque sont calculées à partir de la source de l’information indiquée et d’un nombre aléatoire sur 256 bits (appelé seed) de telle sorte que chaque enregistrement, même si dupliqué dans Precedence, soit unique. Seule la valeur de l’identifiant id ne peut être identique entre deux enregistrements.

Ces informations, représentées au format JSON, constituent un document que nous appelons E. À partir de ces informations, un enregistrement Precedence est créé dont la clef est l’identifiant (id) et la valeur est le hash (SHA-256) de E.

La preuve d’existence de ce document permet de démontrer l’ensemble des informations listées ci-dessus; dont l’existence du hash du document D et ainsi le document D (fonction de hachage à sens unique).

Création d’un enregistrement dans Precedence

On suppose ici la création d’un enregistrement pour le document D et dont l’identifiant est I.

Soit H1 = sha256(D) et H2 = sha256(id) et seed un nombre aléatoire de grande taille (0 < seed < 2²⁵⁶)

Precedence construit le document clef/valeur E (au format JSON) suivant:
{
“id”: H2,
“seed”: sha256(SEED, SEED)
“hash”: sha256(SEED, H1),
“chains”: {},
“previous”: [],
}

Exemple de résultat :
{
“id”: “5c89750b07bced2dbaa5d16eb46826fe3f06297cf5f930defe7169158b24fd9d”,
“seed”: “bdec0dd5015e69d32ec8fd8a868ac44e0962ea64320e109ab48d789eab6b4421”,
“hash”: “3de8d12c829a8e06ffeabac575aa3852f90d57160767832d6bdfde44bb3cc116”,
“chains”: {},
“previous”: [],
}

La valeur de seed est stockée afin de démontrer la valeur de H1 (la valeur démontrable est sha256(SEED, H1).

L’ensemble des informations contenues dans ce document sont démontrables, il en aurait été de même pour les champs chains et previous s’il avaient été renseignés.

Une fois cet enregistrement créé, il est intégré dans un Merkle Patricia Trie avec comme clef id et comme valeur sha256(E).

La construction de ce bloc permet le calcul du root hash du Merkle Patricia Trie contenant l’enregistrement précédent. Nous appelons R1 ce nombre.

Precedence créée alors un enregistrement E2 dans une instance de Precedence commune à l’ensemble des blockchains privées. Cet enregistrement a le format suivant :

Soit SEED2 un nombre aléatoire. On appelle F le document suivant construit et calculé par precedence :
F = {
“id”: ID1,“seed”: sha256(SEED2, SEED2)
“hash”: sha256(SEED2, sha256(E)),
“chains”: {},
“previous”: [],
}

Pour finir, un nouveau bloc sur cette blockchain commune est créé et ainsi le Merkle Patricia Trie qui inclut ID1, sha256(F) et donc le root hash de celui-ci que nous appelons H3.

L’information H3 est directement dépendante de l’ensemble des enregistrements du bloc qu’elle représente. Or chaque enregistrement correspond au root hash d’un bloc du blockchain de niveau inférieur. Ainsi, il existe une preuve d’existence multi-niveau entre l’enregistrement initial du document D et l’écriture horodaté immuable et irréfutable de H3 dans la blockchain Ethereum.

--

--