Paper 2023/113

Homomorphic Sortition – Single Secret Leader Election for PoS Blockchains

Luciano Freitas, Télécom ParisTech
Andrei Tonkikh, Télécom ParisTech
Adda-Akram Bendoukha, CEA LIST
Sara Tucci-Piergiovanni, CEA LIST
Renaud Sirdey, CEA LIST
Oana Stan, CEA LIST
Petr Kuznetsov, Télécom ParisTech

In a single secret leader election protocol (SSLE), one of the system participants is chosen and, unless it decides to reveal itself, no other participant can identify it. SSLE has a great potential in protecting blockchain consensus protocols against denial of service (DoS) attacks. However, all existing solutions either make strong synchrony assumptions or have expiring registration, meaning that they require elected processes to re-register themselves before they can be re-elected again. This, in turn, prohibits the use of these SSLE protocols to elect leaders in partially-synchronous consensus protocols as there may be long periods of network instability when no new blocks are decided and, thus, no new registrations (or re-registrations) are possible. In this paper, we propose Homomorphic Sortition -- the first asynchronous SSLE protocol with non-expiring registration, making it the first solution compatible with partially-synchronous leader-based consensus protocols. Homomorphic Sortition relies on Threshold Fully Homomorphic Encryption (ThFHE) and is tailored to proof-of-stake (PoS) blockchains, with several important optimizations with respect to prior proposals. In particular, unlike most existing SSLE protocols, it works with arbitrary stake distributions and does not require a user with multiple coins to be registered multiple times. Our protocol is highly parallelizable and can be run completely off-chain after setup. Some blockchains require a sequence of rounds to have non-repeating leaders. We define a generalization of SSLE, called Secret Leader Permutation (SLP) in which the application can choose how many non-repeating leaders should be output in a sequence of rounds and we show how Homomorphic Sortition also solves this problem.

Available format(s)
Publication info
FHEFully Homomorphic EncryptionSSLESingle Secret Leader ElectionByzantineBlockchainProof of Stake
Contact author(s)
lfreitas @ telecom-paris fr
tonkikh @ telecom-paris fr
sara tucci @ cea fr
renaud sirdey @ cea fr
oana stan @ cea fr
petr kuznetsov @ telecom-paris fr
2023-01-30: approved
2023-01-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Luciano Freitas and Andrei Tonkikh and Adda-Akram Bendoukha and Sara Tucci-Piergiovanni and Renaud Sirdey and Oana Stan and Petr Kuznetsov},
      title = {Homomorphic Sortition – Single Secret Leader Election for {PoS} Blockchains},
      howpublished = {Cryptology ePrint Archive, Paper 2023/113},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.