---
_id: '8297'
abstract:
- lang: eng
  text: "Designing a secure permissionless distributed ledger (blockchain) that performs
    on par with centralized payment\r\nprocessors, such as Visa, is a challenging
    task. Most existing distributed ledgers are unable to scale-out, i.e., to grow
    their totalprocessing capacity with the number of validators; and those that do,
    compromise security or decentralization. We present OmniLedger, a novel scale-out
    distributed ledger that preserves longterm security under permissionless operation.
    It ensures security and correctness by using a bias-resistant public-randomness
    protocol for choosing large, statistically representative shards that process
    transactions, and by introducing an efficient crossshard commit protocol that
    atomically handles transactions affecting multiple shards. OmniLedger also optimizes
    performance via parallel intra-shard transaction processing, ledger pruning via
    collectively-signed state blocks, and low-latency “trust-butverify” \r\nvalidation
    for low-value transactions. An evaluation ofour experimental prototype shows that
    OmniLedger’s throughput\r\nscales linearly in the number of active validators,
    supporting Visa-level workloads and beyond, while confirming typical transactions
    in under two seconds."
article_processing_charge: No
author:
- first_name: Eleftherios
  full_name: Kokoris Kogias, Eleftherios
  id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
  last_name: Kokoris Kogias
- first_name: Philipp
  full_name: Jovanovic, Philipp
  last_name: Jovanovic
- first_name: Linus
  full_name: Gasser, Linus
  last_name: Gasser
- first_name: Nicolas
  full_name: Gailly, Nicolas
  last_name: Gailly
- first_name: Ewa
  full_name: Syta, Ewa
  last_name: Syta
- first_name: Bryan
  full_name: Ford, Bryan
  last_name: Ford
citation:
  ama: 'Kokoris Kogias E, Jovanovic P, Gasser L, Gailly N, Syta E, Ford B. OmniLedger:
    A secure, scale-out, decentralized ledger via sharding. In: <i>2018 IEEE Symposium
    on Security and Privacy</i>. IEEE; 2018:583-598. doi:<a href="https://doi.org/10.1109/sp.2018.000-5">10.1109/sp.2018.000-5</a>'
  apa: 'Kokoris Kogias, E., Jovanovic, P., Gasser, L., Gailly, N., Syta, E., &#38;
    Ford, B. (2018). OmniLedger: A secure, scale-out, decentralized ledger via sharding.
    In <i>2018 IEEE Symposium on Security and Privacy</i> (pp. 583–598). San Francisco,
    CA, United States: IEEE. <a href="https://doi.org/10.1109/sp.2018.000-5">https://doi.org/10.1109/sp.2018.000-5</a>'
  chicago: 'Kokoris Kogias, Eleftherios, Philipp Jovanovic, Linus Gasser, Nicolas
    Gailly, Ewa Syta, and Bryan Ford. “OmniLedger: A Secure, Scale-out, Decentralized
    Ledger via Sharding.” In <i>2018 IEEE Symposium on Security and Privacy</i>, 583–98.
    IEEE, 2018. <a href="https://doi.org/10.1109/sp.2018.000-5">https://doi.org/10.1109/sp.2018.000-5</a>.'
  ieee: 'E. Kokoris Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta, and B. Ford,
    “OmniLedger: A secure, scale-out, decentralized ledger via sharding,” in <i>2018
    IEEE Symposium on Security and Privacy</i>, San Francisco, CA, United States,
    2018, pp. 583–598.'
  ista: 'Kokoris Kogias E, Jovanovic P, Gasser L, Gailly N, Syta E, Ford B. 2018.
    OmniLedger: A secure, scale-out, decentralized ledger via sharding. 2018 IEEE
    Symposium on Security and Privacy. SP: Symposium on Security and Privacy, 583–598.'
  mla: 'Kokoris Kogias, Eleftherios, et al. “OmniLedger: A Secure, Scale-out, Decentralized
    Ledger via Sharding.” <i>2018 IEEE Symposium on Security and Privacy</i>, IEEE,
    2018, pp. 583–98, doi:<a href="https://doi.org/10.1109/sp.2018.000-5">10.1109/sp.2018.000-5</a>.'
  short: E. Kokoris Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta, B. Ford,
    in:, 2018 IEEE Symposium on Security and Privacy, IEEE, 2018, pp. 583–598.
conference:
  end_date: 2018-05-24
  location: San Francisco, CA, United States
  name: 'SP: Symposium on Security and Privacy'
  start_date: 2018-05-20
date_created: 2020-08-26T11:46:35Z
date_published: 2018-07-26T00:00:00Z
date_updated: 2021-01-12T08:17:56Z
day: '26'
doi: 10.1109/sp.2018.000-5
extern: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2017/406
month: '07'
oa: 1
oa_version: Preprint
page: 583-598
publication: 2018 IEEE Symposium on Security and Privacy
publication_identifier:
  isbn:
  - '9781538643532'
  issn:
  - 2375-1207
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: 'OmniLedger: A secure, scale-out, decentralized ledger via sharding'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...
---
_id: '8306'
abstract:
- lang: eng
  text: Bias-resistant public randomness is a critical component in many (distributed)
    protocols. Generating public randomness is hard, however, because active adversaries
    may behave dishonestly to bias public random choices toward their advantage. Existing
    solutions do not scale to hundreds or thousands of participants, as is needed
    in many decentralized systems. We propose two large-scale distributed protocols,
    RandHound and RandHerd, which provide publicly-verifiable, unpredictable, and
    unbiasable randomness against Byzantine adversaries. RandHound relies on an untrusted
    client to divide a set of randomness servers into groups for scalability, and
    it depends on the pigeonhole principle to ensure output integrity, even for non-random,
    adversarial group choices. RandHerd implements an efficient, decentralized randomness
    beacon. RandHerd is structurally similar to a BFT protocol, but uses RandHound
    in a one-time setup to arrange participants into verifiably unbiased random secret-sharing
    groups, which then repeatedly produce random output at predefined intervals. Our
    prototype demonstrates that RandHound and RandHerd achieve good performance across
    hundreds of participants while retaining a low failure probability by properly
    selecting protocol parameters, such as a group size and secret-sharing threshold.
    For example, when sharding 512 nodes into groups of 32, our experiments show that
    RandHound can produce fresh random output after 240 seconds. RandHerd, after a
    setup phase of 260 seconds, is able to generate fresh random output in intervals
    of approximately 6 seconds. For this configuration, both protocols operate at
    a failure probability of at most 0.08% against a Byzantine adversary.
article_processing_charge: No
author:
- first_name: E.
  full_name: Syta, E.
  last_name: Syta
- first_name: P.
  full_name: Jovanovic, P.
  last_name: Jovanovic
- first_name: Eleftherios
  full_name: Kokoris Kogias, Eleftherios
  id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
  last_name: Kokoris Kogias
- first_name: N.
  full_name: Gailly, N.
  last_name: Gailly
- first_name: L.
  full_name: Gasser, L.
  last_name: Gasser
- first_name: I.
  full_name: Khoffi, I.
  last_name: Khoffi
- first_name: M. J.
  full_name: Fischer, M. J.
  last_name: Fischer
- first_name: B.
  full_name: Ford, B.
  last_name: Ford
citation:
  ama: 'Syta E, Jovanovic P, Kokoris Kogias E, et al. Scalable bias-resistant distributed
    randomness. In: <i>2017 IEEE Symposium on Security and Privacy</i>. IEEE; 2017:444-460.
    doi:<a href="https://doi.org/10.1109/SP.2017.45">10.1109/SP.2017.45</a>'
  apa: 'Syta, E., Jovanovic, P., Kokoris Kogias, E., Gailly, N., Gasser, L., Khoffi,
    I., … Ford, B. (2017). Scalable bias-resistant distributed randomness. In <i>2017
    IEEE Symposium on Security and Privacy</i> (pp. 444–460). San Jose, CA, United
    States: IEEE. <a href="https://doi.org/10.1109/SP.2017.45">https://doi.org/10.1109/SP.2017.45</a>'
  chicago: Syta, E., P. Jovanovic, Eleftherios Kokoris Kogias, N. Gailly, L. Gasser,
    I. Khoffi, M. J. Fischer, and B. Ford. “Scalable Bias-Resistant Distributed Randomness.”
    In <i>2017 IEEE Symposium on Security and Privacy</i>, 444–60. IEEE, 2017. <a
    href="https://doi.org/10.1109/SP.2017.45">https://doi.org/10.1109/SP.2017.45</a>.
  ieee: E. Syta <i>et al.</i>, “Scalable bias-resistant distributed randomness,” in
    <i>2017 IEEE Symposium on Security and Privacy</i>, San Jose, CA, United States,
    2017, pp. 444–460.
  ista: 'Syta E, Jovanovic P, Kokoris Kogias E, Gailly N, Gasser L, Khoffi I, Fischer
    MJ, Ford B. 2017. Scalable bias-resistant distributed randomness. 2017 IEEE Symposium
    on Security and Privacy. SP: Symposium on Security and Privacy, 444–460.'
  mla: Syta, E., et al. “Scalable Bias-Resistant Distributed Randomness.” <i>2017
    IEEE Symposium on Security and Privacy</i>, IEEE, 2017, pp. 444–60, doi:<a href="https://doi.org/10.1109/SP.2017.45">10.1109/SP.2017.45</a>.
  short: E. Syta, P. Jovanovic, E. Kokoris Kogias, N. Gailly, L. Gasser, I. Khoffi,
    M.J. Fischer, B. Ford, in:, 2017 IEEE Symposium on Security and Privacy, IEEE,
    2017, pp. 444–460.
conference:
  end_date: 2017-05-26
  location: San Jose, CA, United States
  name: 'SP: Symposium on Security and Privacy'
  start_date: 2017-05-22
date_created: 2020-08-26T12:26:08Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2021-01-12T08:18:02Z
day: '01'
doi: 10.1109/SP.2017.45
extern: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2016/1067
month: '06'
oa: 1
oa_version: Preprint
page: 444-460
publication: 2017 IEEE Symposium on Security and Privacy
publication_identifier:
  isbn:
  - '9781509055340'
  issn:
  - 2375-1207
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: Scalable bias-resistant distributed randomness
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...