111 research outputs found
Revisiting the Nova Proof System on a Cycle of Curves
No full textNova is an efficient recursive proof system built from an elegant folding scheme for (relaxed) R1CS statements. The original Nova paper (CRYPTO'22) presented Nova using a single elliptic curve group of order p. However, for improved efficiency, the implementation of Nova alters the scheme to use a 2-cycle of elliptic curves. This altered scheme is only described in the code and has not been proven secure. In this work, we point out a soundness vulnerability in the original implementation of the 2-cycle Nova system. To demonstrate this vulnerability, we construct a convincing Nova proof for the correct evaluation of 2^{75} rounds of the Minroot VDF in only 116 milliseconds. We then present a modification of the 2-cycle Nova system and formally prove its security. The modified system also happens to be more efficient than the original implementation. In particular, the modification eliminates an R1CS instance-witness pair from the recursive proof. The implementation of Nova has now been updated to use our optimized and secure system. In addition, we show that the folding mechanism at the core of Nova is malleable: given a proof for some statement z, an adversary can construct a proof for a related statement z', at the same depth as z, without knowledge of the witness for z'
BabySpartan: Lasso-based SNARK for non-uniform computation
No full textLasso (Setty, Thaler, Wahby, ePrint 2023/1216) is a recent lookup argument that ensures that the prover cryptographically commits to only small values. This note describes BabySpartan, a SNARK for a large class of constraint systems that achieves the same property. The SNARK is a simple combination of SuperSpartan and Lasso. The specific class of constraint systems supported is a generalization of so-called Plonkish constraint systems (and a special case of customizable constraint systems (CCS)). Whereas a recent work called Jolt (Arun, Setty, and Thaler, ePrint 2023/1217) can be viewed as an application of Lasso to uniform computation, BabySpartan can be viewed as applying Lasso to non-uniform computation
Effects of Nitric Oxide on Right Ventricular Metabolism and Coronary Blood Flow
No full textSetty, Srinath Varadaraj. Effects of Nitric Oxide on Right Ventricular Metabolism and Coronary Blood Flow Doctor of Philosophy (Biomedical Sciences), January, 9, 2001, 123 pp, 3 tables, 16 figures, references, 211 titles. Nitric oxide (NO) formed from L-arginine and released from vascular endothelium causes relaxation of vascular smooth muscle via a cGMP mechanism. However, the of NO as a regulator of coronary blood flow control is unclear. NO has been shown also to reduce oxygen consumption in various in-vitro preparations, but its effect on myocardial oxygen consumption (MVO2) in the left ventricle of the working heart is controversial. The effect of NO on MVO2 in the right ventricle (RV) is unknown. This investigation delineated the effects of NO on RV MVO2 during controlled systemic and coronary hemodynamic conditions. In open chest dogs, NO synthesis was blocked by intracoronary infusion of NO synthesis with Nω-nitro-L-arginine methyl ester (L-NAME, 150 μg/min). To avoid effects of NO synthesis blockade on right coronary blood flow (RCBF), which might have altered RV MVO2, experiments were conducted during adenosine-induced maximal right coronary vasodilation (n=12). RCBF, RV MVO2, and other variables were measured at baseline and at elevated right coronary perfusion pressures (RCP). Under these conditions, L-NAME significantly increased RV MVO2 at baseline and at elevated RCP (P [less than] 0.05 vs. untreated control condition). These results indicate that NO acts to retard RV oxidative metabolism. We further characterized the role of NO on RV MVO2 during increases in RV workload, estimated as a product of heart rate X RV peak systolic pressure X RV dP/dt. RV workload, RCBF, and RV MVO2 were increased by intracoronary norepinephrine infusions at baseline RCP (n=5). L-NAME significantly reduced RCBF (P [less than] 0.05 vs. untreated control condition), and RV MVO2 was significantly higher at any measured RV workload during L-NAME (P [less than] 0.05 vs. untreated control condition). These findings indicate that NO is an important component of RCBF control and that NO blunts norepinephrine-induced increase in RV MVO2. If NO reduced RV MVO2 it may be cardioprotective during moderate right coronary hypoperfusion. Thus, we sought to determine if in fact the RV MVO2 was reduced by NO during moderate right coronary hypoperfusion (n=9). RCP was reduced to 60 (n=5) and 40 mmHg (n=4), and RCBF and RV MVO2 fell as RCP was reduced. L-NAME significantly increased RV MVO2 at RCP of 60 and 40 mmHg (P [less than] 0.05 vs. untreated control condition), although RV workload was not altered. Since NO reduced RV MVO2 without compromising RV mechanical performance, RV oxygen utilization efficiency was enhanced. Taken together, these findings demonstrate that NO has a significant dampening effect on RV MVO2
Makespan reduction using dynamic job sequencing combined with buffer optimization applying genetic algorithm in a manufacturing system
No full textHyperNova: Recursive arguments for customizable constraint systems
No full textWe introduce HyperNova, a new recursive argument for proving incremental computations whose steps are expressed with CCS (Setty et al. ePrint 2023/552), a customizable constraint system that simultaneously generalizes Plonkish, R1CS, and AIR without overheads. HyperNova makes four contributions, each resolving a major problem in the area of recursive arguments.
First, it provides a folding scheme for CCS where the prover’s cryptographic cost is a single multi-scalar multiplication (MSM) of size equal to the number of variables in the constraint system, which is optimal when using an MSM-based commitment scheme. The folding scheme can fold multiple instances at once, making it easier to build generalizations of IVC such as PCD. Second, when proving program executions on stateful machines (e.g., EVM, RISC-V), the cost of proving a step of a program is proportional only to the size of the circuit representing the instruction invoked by the program step ( a la carte cost profile). Third, we show how to achieve zero-knowledge for free and without the need to employ zero-knowledge SNARKs: we use a folding scheme to randomize IVC proofs. This highlights a new application of folding schemes. Fourth, we show how to efficiently instantiate HyperNova over a cycle of elliptic curves. For this, we provide a general technique, which we refer to as CycleFold, that applies to all modern folding-scheme-based recursive arguments
Author Correction Large spontaneous exchange bias in a weak ferromagnet Pb 6 Ni 9 (TeO 6 ) 5 (Scientific Reports, (2017), 7, 1, (8300), 10.1038/s41598-017-09056-w)
No full textIn the original version of this Article, Binoy Krishna Hazra and S. Srinath were incorrectly affiliated with ‘Department of Physics, Indian Institute of Technology Tirupati, TIRUPATI, 517506, India’. The correct affiliation is listed below School of Physics, University of Hyderabad, Hyderabad, 500046, India This error has now been corrected in the PDF and HTML versions of the Article, and in the accompanying Supplementary Information file. © 2019, The Author(s)
Jolt: SNARKs for Virtual Machines via Lookups
No full textSuccinct Non-interactive Arguments of Knowledge (SNARKs) allow an untrusted prover to establish that it correctly ran some witness-checking procedure on a witness. A zkVM (short for zero-knowledge Virtual Machine) is a SNARK that allows the witness-checking procedure to be specified as a computer program written in the assembly language of a specific instruction set architecture (ISA).
A converts computer programs into a lower-level representation such as an arithmetic circuit or generalization thereof. A SNARK for circuit-satisfiability can then be applied to the resulting circuit.
We describe a new front-end technique called Jolt that applies to a variety of ISAs. Jolt arguably realizes a vision called the , which seeks to produce circuits that only perform lookups into pre-determined lookup tables. The circuits output by Jolt primarily perform lookups into a gigantic lookup table, of size more than , that depends only on the ISA. The validity of the lookups are proved via a new called Lasso described in a companion work (Setty, Thaler, and Wahby, e-print 2023). Although size- tables are vastly too large to materialize in full, the tables arising in Jolt are structured, avoiding costs that grow linearly with the table size.
We describe performance and auditability benefits of Jolt compared to prior zkVMs, focusing on the popular RISC-V ISA as a concrete example. The dominant cost for the Jolt prover applied to this ISA (on -bit data types) is cryptographically committing to about six -bit field elements per step of the RISC-V CPU. This compares favorably to prior zkVM provers, even those focused on far simpler VMs
Experimental characterisation of large scale structures in a high Reynolds number turbulent boundary layer
No full textA very large field of view (4δ x 1δ) with a good spatial resolution owing to the use of four 2k x 2k pixel cameras was conducted in a flat plate boundary layer at two Reynolds numbers (Reθ ≈7,500 and 20,000). Comparing the flow statistics with previously obtained hot-wire data under similar flow conditions show good agreement. The goal of this experiment is to detect and characterise the large scale motions which develop in the log region of a high Reynolds number turbulent boundary layer
Understanding Lasso: A Novel Lookup Argument Protocol
No full textIn 2023, Srinath Setty, Justin Thaler, and Riad Wahby published a paper that describes a novel lookup argument with efficient verification called Lasso. We present a focused and accessible overview of the Lasso lookup argument that stands for the foundational component of the Jolt ZK-VM. This article distills the core principles behind Lasso: the sum-check protocol, multilinear polynomials and their extensions, Spark commitment, offline memory-checking, and the evolution of Spark called Surge. By clarifying the underlying protocols and their relationship to innovations like Spark and Surge, we aim to provide researchers and engineers with practical insights into the cryptographic foundations powering both Lasso and the Jolt virtual machine
Spartan: Efficient and general-purpose zkSNARKs without trusted setup
No full textThis paper introduces Spartan, a new family of zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) for the rank-1 constraint satisfiability (R1CS), an NP-complete language that generalizes arithmetic circuit satisfiability. A distinctive feature of Spartan is that it offers the first zkSNARKs without trusted setup (i.e., transparent zkSNARKs) for NP where verifying a proof incurs sub-linear costs—without requiring uniformity in the NP statement’s structure. Furthermore,
Spartan offers zkSNARKs with a time-optimal prover, a property that has remained elusive for nearly all zkSNARKs in the literature.
To achieve these results, we introduce new techniques that we compose with the sum-check protocol, a seminal interactive proof protocol: (1) computation commitments, a primitive to create a succinct commitment to a description of a computation; this technique is crucial for a verifier to achieve sub-linear costs after investing a one-time, public computation to preprocess a given NP statement; (2) SPARK, a cryptographic compiler to transform any existing extractable polynomial commitment scheme for multilinear polynomials to one that efficiently handles sparse multilinear polynomials; this technique is critical for achieving a time-optimal prover; and (3) a compact encoding of an R1CS instance as a low-degree polynomial. The end result is a public-coin succinct interactive argument of knowledge for NP (which can be viewed as a succinct variant of the sum-check protocol); we transform it into a zkSNARK using prior techniques. By applying SPARK to different commitment schemes, we obtain several zkSNARKs where the verifier’s costs and the proof size range from to depending on the underlying commitment scheme ( denotes the size of the NP statement). These schemes do not require a trusted setup except for one that requires a universal trusted setup.
We implement Spartan as a library in about 8,000 lines of Rust. We use the library to build a transparent zkSNARK in the random oracle model where security holds under the discrete logarithm assumption. We experimentally evaluate it and compare it with recent zkSNARKs for R1CS instance sizes up to constraints. Among transparent zkSNARKs, Spartan offers the fastest prover with speedups of -- depending on the baseline, produces proofs that are shorter by --, and incurs the lowest verification times with speedups of --. The only exception is proof sizes under Bulletproofs, but Bulletproofs incurs slower verification both asymptotically and concretely. When compared to the state-of-the-art zkSNARK with trusted setup, Spartan’s prover is faster for arbitrary R1CS instances and faster for data-parallel workloads.
Spartan’s code is available from: https://github.com/Microsoft/Spartan
- …
