The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Scalable Bias-Resistant Distributed Randomness
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Bitcoin: A Peer-to-Peer Electronic Cash System
Wright, C. S. (2008) · SSRN Electronic Journal · doi:10.2139/ssrn.3440802 · Cited by 13,922
Shamir, A. (1979) · Communications of the ACM · doi:10.1145/359168.359176 · Cited by 13,756
Tor: The Second-Generation Onion Router
Dingledine, R., Mathewson, N., & Syverson, P. (2004) · doi:10.21236/ada465464 · Cited by 4,104
How To Prove Yourself: Practical Solutions to Identification and Signature Problems
Fiat, A., & Shamir, A. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-47721-7_12 · Cited by 3,943
Safeguarding cryptographic keys
BLAKLEY, G. R. (1979) · 1979 International Workshop on Managing Requirements Knowledge (MARK) · doi:10.1109/mark.1979.8817296 · Cited by 3,499
Practical Byzantine fault tolerance
Castro, M., & Liskov, B. H. (1999) · Operating Systems Design and Implementation · doi:10.5555/296806.296824 · Cited by 3,205
Short Signatures from the Weil Pairing
Boneh, D., Lynn, B., & Shacham, H. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-45682-1_30 · Cited by 2,993
Wallet Databases with Observers
Chaum, D., & Pedersen, T. P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48071-4_7 · Cited by 1,292
On Scaling Decentralized Blockchains: (A Position Paper)
Croman, K., Decker, C., Eyal, I., Gencer, A. E., Juels, A., Kosba, A., Miller, A., Saxena, P., Shi, E., Gün Sirer, E., et al. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-53357-4_8 · Cited by 1,165
Desmedt, Y., & Frankel, Y. (2007) · Lecture Notes in Computer Science · doi:10.1007/0-387-34805-0_28 · Cited by 1,131
A practical scheme for non-interactive verifiable secret sharing
Feldman, P. (1987) · 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) · doi:10.1109/sfcs.1987.4 · Cited by 1,125
Verifiable secret sharing and multiparty protocols with honest majority
Rabin, T., & Ben-Or, M. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73014 · Cited by 930
Curve25519: New Diffie-Hellman speed records
Bernstein, D. J. (2006) · Lecture Notes in Computer Science · doi:10.1007/11745853_14 · Cited by 859
A Threshold Cryptosystem without a Trusted Party
Pedersen, T. P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46416-6_47 · Cited by 777
Verifiable secret sharing and achieving simultaneity in the presence of faults
Chor, B., Goldwasser, S., Micali, S., & Awerbuch, B. (1985) · 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) · doi:10.1109/sfcs.1985.64 · Cited by 771
Efficient Identification and Signatures for Smart Cards
Schnorr, C. P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46885-4_68 · Cited by 751
Micali, S., Rabin, M., & Vadhan, S. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814584 · Cited by 716
Multi-signatures in the plain public-Key model and a general forking lemma
Bellare, M., & Neven, G. (2006) · Proceedings of the 13th ACM conference on Computer and communications security · doi:10.1145/1180405.1180453 · Cited by 654
Helios: Web-based open-audit voting
Adida, B. (2008) · Cited by 543
Publicly Verifiable Secret Sharing
Stadler, M. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68339-9_17 · Cited by 531
Coin flipping by telephone a protocol for solving impossible problems
Blum, M. (1983) · ACM SIGACT News · doi:10.1145/1008908.1008911 · Cited by 518
A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic Voting
Schoenmakers, B. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48405-1_10 · Cited by 448
Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement Using Cryptography
Cachin, C., Kursawe, K., & Shoup, V. (2005) · Journal of Cryptology · doi:10.1007/s00145-005-0318-0 · Cited by 437
Secure Distributed Key Generation for Discrete-Log Based Cryptosystems
Gennaro, R., Jarecki, S., Krawczyk, H., & Rabin, T. (2007) · Journal of Cryptology · doi:10.1007/s00145-006-0347-3 · Cited by 428
Secure and Efficient Asynchronous Broadcast Protocols
Cachin, C., Kursawe, K., Petzold, F., & Shoup, V. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_31 · Cited by 371
Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing
Kokoris-Kogias, E., Jovanovic, P., Gailly, N., Khoffi, I., Gasser, L., & Ford, B. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.06997 · Cited by 309
Self-citationKeeping Authorities "Honest or Bust" with Decentralized Witness Cosigning
Syta, E., Tamas, I., Visher, D., Wolinsky, D. I., Jovanovic, P., Gasser, L., Gailly, N., Khoffi, I., & Ford, B. (2016) · 2016 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2016.38 · Cited by 244
Self-citationAnalysis of the Linux random number generator
Gutterman, Z., Pinkas, B., & Reinman, T. (2006) · 2006 IEEE Symposium on Security and Privacy (S&P'06) · doi:10.1109/sp.2006.5 · Cited by 219
Vuvuzela: scalable private messaging resistant to traffic analysis
van den Hooff, J., Lazar, D., Zaharia, M., & Zeldovich, N. (2015) · Proceedings of the 25th Symposium on Operating Systems Principles · doi:10.1145/2815400.2815417 · Cited by 216
Transaction protection by beacons
Rabin, M. O. (1983) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(83)90042-9 · Cited by 206
Efficient identification andsignatures for smart cards
Schnorr, C. P. (1990) · International Cryptology Conference · Cited by 202
Elligator: elliptic-curve points indistinguishable from uniform random strings
Bernstein, D. J., Hamburg, M., Krasnova, A., & Lange, T. (2013) · Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security - CCS '13 · doi:10.1145/2508859.2516734 · Cited by 191
Herbivore: A Scalable and Efficient Protocol for Anonymous Communication
Goel, S., Robson, M., Polte, M., & Sirer, E. G. (2003) · eCommons (Cornell University) · Cited by 162
Dissent in numbers: making strong anonymity scale
Wolinsky, D. I., Corrigan-Gibbs, H., Ford, B., & Johnson, A. (2012) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · doi:10.5555/2387880.2387898 · Cited by 162
Self-citationSCRAPE: Scalable Randomness Attested by Public Entities
Cascudo, I., & David, B. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-61204-1_27 · Cited by 154
On Bitcoin as a public randomness source.
Bonneau, J., Clark, J., & Goldfeder, S. (2015) · Cited by 126
Stinson, D. R., & Strobl, R. (2001) · Lecture notes in computer science · doi:10.1007/3-540-47719-5_33 · Cited by 122
Dual EC: A Standardized Back Door
Bernstein, D. J., Lange, T., & Niederhagen, R. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-49301-4_17 · Cited by 91
Distributed Key Generation for the Internet
Kate, A., & Goldberg, I. (2009) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2009.21 · Cited by 88
A TorPath to TorCoin: Proof-of-Bandwidth Altcoins for Compensating Relays
Ghosh, M., Richardson, M., Ford, B., & Jansen, R. (2014) · Cited by 61
Self-citationHighly dynamic distributed computing with byzantine failures
Guerraoui, R., Huc, F., & Kermarrec, A.-M. (2013) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/2484239.2484263 · Cited by 45
On the Use of Financial Data as a Random Beacon.
Clark, J., & Hengartner, U. (2010) · Cited by 41
Cited by
OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding
Kokoris-Kogias, E., Jovanovic, P., Gasser, L., Gailly, N., Syta, E., & Ford, B. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.000-5 · Cited by 1,253
Self-citationA Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks
Wang, W., Hoang, D. T., Hu, P., Xiong, Z., Niyato, D., Wang, P., Wen, Y., & Kim, D. I. (2019) · IEEE Access · doi:10.1109/access.2019.2896108 · Cited by 995
Solutions to scalability of blockchain: a survey
Zhou, Q., Huang, H., Zheng, Z., & Bian, J. (2020) · IEEE Access · doi:10.1109/access.2020.2967218 · Cited by 689
Boneh, D., Bonneau, J., Bünz, B., & Fisch, B. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-96884-1_25 · Cited by 413
SBFT: A Scalable and Decentralized Trust Infrastructure
Golan Gueta, G., Abraham, I., Grossman, S., Malkhi, D., Pinkas, B., Reiter, M., Seredinschi, D.-A., Tamir, O., & Tomescu, A. (2019) · 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN) · doi:10.1109/dsn.2019.00063 · Cited by 362
Metadata
- Authors
- Syta, E., Jovanovic, P., Kogias, E. K., Gailly, N., Gasser, L., Khoffi, I., Fischer, M. J., & Ford, B.
- Venue
- 2017 IEEE Symposium on Security and Privacy (SP)
- Publisher
- IEEE
- Published
- 2017-05
- Volume
- 2016
- Pages
- 444-460
- ISSN
- 1081-6011 (ISSN-L)
- OpenAlex
- W2717184009
- Cited by
- 290
- References
- 42
- FWCI
- 12.58
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.