Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARK) schemes have gained significant adoption in privacy-preserving applications, in decentralized systems (e.g., blockchain), and in verifiable computation due to their efficiency. However, the most efficient zk-SNARKs often rely on a one-time trusted setup to generate public parameters, often known as the ''Powers of Tau'' (PoT) string. The leakage of the secret parameter τ in the string would allow attackers to generate false proofs, compromising the soundness of all zk-SNARK systems built on it.

Regular access to unpredictable and bias-resistant randomness is important for applications such as blockchains, voting, and secure distributed computing. Distributed random beacon protocols address this need by distributing trust across multiple nodes, with the majority of them assumed to be honest. Numerous applications across the blockchain space have led to the proposal of several distributed random beacon protocols, with some already implemented. However, many current random beacon systems rely on threshold cryptographic setups or exhibit high computational costs, while others expect the network to be partial or bounded synchronous. To overcome these limitations, we propose HashRand, a computation and communication-efficient asynchronous random beacon protocol that only demands secure hash and pairwise secure channels to generate beacons. HashRand has a per-node amortized communication complexity of O (λn log(n)) bits per beacon. The computational efficiency of HashRand is attributed to the two orders of magnitude lower time of a one-way Hash computation compared to discrete log exponentiation. Interestingly, besides reduced overhead, HashRand achieves Post-Quantum security by leveraging the secure Hash function against quantum adversaries, setting it apart from other random beacon protocols that use discrete log cryptography. In a geo-distributed testbed of n = 136 nodes, HashRand produces 78 beacons per minute, which is at least 5× higher than Spurt [IEEE S&P'22]. We also demonstrate the practical utility of HashRand by implementing a Post-Quantum secure Asynchronous SMR protocol, which has a response rate of over 135k transactions per second at a latency of 2.3 seconds over a WAN for n = 16 nodes.

Agreement protocols are crucial in various emerging applications, spanning from distributed (blockchains) oracles to fault-tolerant cyber-physical systems. In scenarios where sensor/oracle nodes measure a common source, maintaining output within the convex range of correct inputs, known as convex validity, is imperative. Present asynchronous convex agreement protocols employ either randomization, incurring substantial computation overhead, or approximate agreement techniques, leading to high$\tilde{\mathcal{O}(n^{3})}$communication for an$n$-node system. This paper introduces Delphi, a deterministic protocol with$\tilde{\mathcal{O}(n^{2})}$communication and minimal computation overhead. Delphi assumes that honest inputs are bounded, except with negligible probability, and integrates agreement primitives from literature with a novel weighted averaging technique. Experimental results highlight Delphi's superior performance, showcasing a significantly lower latency compared to state-of-the-art protocols. Specifically, for an$n$= 160-node system, Delphi achieves an 8x and 3x improvement in latency within CPS and AWS environments, respectively.

The target localization primitive is used for detecting and locating an adverse event called a target in a geographic area. This versatile primitive is applicable in the physical security domain (e.g., detecting intruders in an area) or for disaster preemption, such as detecting ignition events of forest fires. Prior systems implemented this primitive over large areas by deploying a network of sensor devices, which detect changes in a specific physical parameter like pressure or temperature induced by a target. However, these systems are not designed for use in adverse environments where one or more sensors can behave in a faulty manner. While many algorithms in the distributed systems literature can be naively used to implement target localization in a fault-tolerant manner, these approaches are energy-intensive as they use computationally expensive cryptographic operations not appropriate for resource-constrained sensors. We present SENSORBFT, an energy-efficient, fault-tolerant approach for target localization. SENSORBFT uses a novel asynchronous approximate agreement protocol that enables correct sensors to achieve an approximate consensus in the presence of faulty sensors. Sensors fulfill their energy budgets by tuning the precision and accuracy of localization, where precision is the difference between honest sensors' outputs and accuracy is the difference between an honest sensor's output and the target's true location. In optimal scenarios, this protocol reduces communication from$O$($n$3) to$O$($n$2) messages per round, where$n$is the number of sensors sharing coverage over a piece of area. In a sensor testbed with$n$= 19 sensors, SENSORBFT consumes 2/5 th the energy consumed by existing solutions for a minor 2% loss in accuracy, significantly enhancing efficiency and coverage.

The Tor network enhances clients’ privacy by routing traffic through an overlay network of volunteered intermediate relays. Tor employs a distributed protocol among nine hard-coded Directory Authority (DA) servers to securely disseminate information about these relays to produce a new consensus document every hour. With a straightforward voting mechanism to ensure consistency, the protocol is expected to be secure even when a minority of those authorities get compromised. However, the current consensus protocol is flawed: it allows an equivocation attack that enables only a single compromised authority to create a valid consensus document with malicious relays. Importantly the vulnerability is not innocuous: We demonstrate that the compromised authority can effectively trick a targeted client into using the equivocated consensus document in an undetectable manner. Moreover, even if we have archived Tor consensus documents available since its beginning, we cannot be sure that no client was ever tricked.We propose a two-stage solution to deal with this exploit. In the short term, we have developed and deployed TorEq, a monitor to detect such exploits reactively: the Tor clients can refer to the monitor before updating the consensus to ensure no equivocation. To solve the problem proactively, we first define the Tor DA consensus problem as the interactive consistency (IC) problem from the distributed computing literature. We then design DirCast, a novel secure Byzantine Broadcast protocol that requires minimal code change from the current Tor DA code base. Our protocol has near-optimal efficiency that uses optimistically five rounds and at most nine rounds to reach an agreement in the current nine-authority system. Our solutions are practical: our performance analysis shows that our monitor can detect equivocations without changing the authorities’ code in five minutes; the secure IC protocol can generate up to 500 consensus documents per hour in a real-world scenario. We are communicating with the Tor security team to incorporate the solutions into the Tor project.

Modern Byzantine Fault-Tolerant State Machine Replication (BFT-SMR) solutions focus on reducing communication complexity, improving throughput, or lowering latency. This work explores the energy efficiency of BFT-SMR protocols. First, we propose a novel SMR protocol that optimizes for the steady state, i.e., when the leader is correct. This is done by reducing the number of required signatures per consensus unit and the communication complexity by order of the number of nodes n compared to the state-of-the-art BFT-SMR solutions. Concretely, we employ the idea that a quorum (collection) of signatures on a proposed value is avoidable during the failure-free runs. Second, we model and analyze the energy efficiency of protocols and argue why the steady-state needs to be optimized. Third, we present an application in the cyber-physical system (CPS) setting, where we consider a partially connected system by optionally leveraging wireless multicasts among neighbors. We analytically determine the parameter ranges for when our proposed protocol offers better energy efficiency than communicating with a baseline protocol utilizing an external trusted node. We present a hypergraph-based network model and generalize previous fault tolerance results to the model. Finally, we demonstrate our approach's practicality by analyzing our protocol's energy efficiency through experiments on a CPS test bed. In particular, we observe as high as 64% energy savings when compared to the state-of-the-art SMR solution for n = 10 settings using BLE.

A random beacon provides a continuous public source of randomness and its applications range from public lotteries to zero-knowledge proofs. Existing random beacon protocols sacrifice either the fault tolerance or the communication complexity for security, or ease of reconfigurability. This work overcomes the challenges with the existing works through a novel communication efficient combination of state machine replication and (Publicly) Verifiable Secret Sharing (PVSS/VSS).

Repeated Modular Squaring is a versatile computational operation that has led to practical constructions of timed-cryptographic primitives like time-lock puzzles (TLP) and verifiable delay functions (VDF) that have a fast growing list of applications. While there is a huge interest for timed-cryptographic primitives in the blockchains area, we find two real-world concerns that need immediate attention towards their large-scale practical adoption: Firstly, the requirement to constantly perform computations seems unrealistic for most of the users. Secondly, choosing the parameters for the bound (T) seems complicated due to the lack of heuristics and experience. We present OpenSquare, a decentralized repeated modular squaring service, that overcomes the above concerns. OpenSquare lets clients outsource their repeated modular squaring computation via smart contracts to any computationally powerful servers that offer computational services for rewards in an unlinkable manner.

A verifiable timed signature (VTS) scheme allows one to time-lock a signature on a known message for a given amount of time T such that after performing a sequential computation for time T anyone can extract the signature from the time-lock. Verifiability ensures that anyone can publicly check if a time-lock contains a valid signature on the message without solving it first, and that the signature can be obtained by solving the same for time T.