@inproceedings{14609,
  abstract     = {Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted party. DKG is an essential building block to many decentralized protocols such as randomness beacons, threshold signatures, Byzantine consensus, and multiparty computation. While significant progress has been made recently, existing asynchronous DKG constructions are inefficient when the reconstruction threshold is larger than one-third of the total nodes. In this paper, we present a simple and concretely efficient asynchronous DKG (ADKG) protocol among n = 3t + 1 nodes that can tolerate up to t malicious nodes and support any reconstruction threshold ℓ ≥ t. Our protocol has an expected O(κn3) communication cost, where κ is the security parameter, and only assumes the hardness of the Discrete Logarithm. The
core ingredient of our ADKG protocol is an asynchronous protocol to secret share a random polynomial of degree ℓ ≥ t, which has other applications, such as asynchronous proactive secret sharing and asynchronous multiparty computation. We implement our high-threshold ADKG protocol and evaluate it using a network of up to 128 geographically distributed nodes. Our evaluation shows that our high-threshold ADKG protocol reduces the running time by 90% and bandwidth usage by 80% over the state-of-the-art.},
  author       = {Das, Sourav and Xiang, Zhuolun and Kokoris Kogias, Eleftherios and Ren, Ling},
  booktitle    = {32nd USENIX Security Symposium},
  isbn         = {9781713879497},
  location     = {Anaheim, CA, United States},
  pages        = {5359--5376},
  publisher    = {Usenix},
  title        = {{Practical asynchronous high-threshold distributed key generation and distributed polynomial sampling}},
  volume       = {8},
  year         = {2023},
}

@inproceedings{14735,
  abstract     = {Scaling blockchain protocols to perform on par with the expected needs of Web3.0 has been proven to be a challenging task with almost a decade of research. In the forefront of the current solution is the idea of separating the execution of the updates encoded in a block from the ordering of blocks. In order to achieve this, a new class of protocols called rollups has emerged. Rollups have as input a total ordering of valid and invalid transactions and as output a new valid state-transition.
If we study rollups from a distributed computing perspective, we uncover that rollups take as input the output of a Byzantine Atomic Broadcast (BAB) protocol and convert it to a State Machine Replication (SMR) protocol. BAB and SMR, however, are considered equivalent as far as distributed computing is concerned and a solution to one can easily be retrofitted to solve the other simply by adding/removing an execution step before the validation of the input.
This “easy” step of retrofitting an atomic broadcast solution to implement an SMR has, however, been overlooked in practice. In this paper, we formalize the problem and show that after BAB is solved, traditional impossibility results for consensus no longer apply towards an SMR. Leveraging this we propose a distributed execution protocol that allows reduced execution and storage cost per executor (O(log2n/n)) without relaxing the network assumptions of the underlying BAB protocol and providing censorship-resistance. Finally, we propose efficient non-interactive light client constructions that leverage our efficient execution protocols and do not require any synchrony assumptions or expensive ZK-proofs.},
  author       = {Stefo, Christos and Xiang, Zhuolun and Kokoris Kogias, Eleftherios},
  booktitle    = {27th International Conference on Financial Cryptography and Data Security},
  isbn         = {9783031477539},
  issn         = {0302-9743},
  location     = {Bol, Brac, Croatia},
  pages        = {3--20},
  publisher    = {Springer Nature},
  title        = {{Executing and proving over dirty ledgers}},
  doi          = {10.1007/978-3-031-47754-6_1},
  volume       = {13950},
  year         = {2023},
}

@inproceedings{14829,
  abstract     = {This paper explores a modular design architecture aimed at helping blockchains (and other SMR implementation) to scale to a very large number of processes. This comes in contrast to existing monolithic architectures that interleave transaction dissemination, ordering, and execution in a single functionality. To achieve this we first split the monolith to multiple layers which can use existing distributed computing primitives. The exact specifications of the data dissemination part are formally defined by the Proof of Availability & Retrieval (PoA &R) abstraction. Solutions to the PoA &R problem contain two related sub-protocols: one that “pushes” information into the network and another that “pulls” this information. Regarding the latter, there is a dearth of research literature which is rectified in this paper. We present a family of pulling sub-protocols and rigorously analyze them. Extensive simulations support the theoretical claims of efficiency and robustness in case of a very large number of players. Finally, actual implementation and deployment on a small number of machines (roughly the size of several industrial systems) demonstrates the viability of the architecture’s paradigm.},
  author       = {Cohen, Shir and Goren, Guy and Kokoris Kogias, Eleftherios and Sonnino, Alberto and Spiegelman, Alexander},
  booktitle    = {27th International Conference on Financial Cryptography and Data Security},
  isbn         = {9783031477508},
  issn         = {1611-3349},
  location     = {Bol, Brac, Croatia},
  pages        = {36--53},
  publisher    = {Springer Nature},
  title        = {{Proof of availability and retrieval in a modular blockchain architecture}},
  doi          = {10.1007/978-3-031-47751-5_3},
  volume       = {13951},
  year         = {2023},
}