Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

@guildofweavers/genstark

Package Overview
Dependencies
Maintainers
1
Versions
23
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@guildofweavers/genstark - npm Package Compare versions

Comparing version 0.1.0 to 0.2.0

lib/config.js
lib/expressions/index.js
lib/expressions/nodes.js
lib/expressions/parser.js
lib/expressions/tokenizer.js
lib/registers/SpreadConstants.js

58

examples/demo.js

@@ -8,47 +8,27 @@ "use strict";

// ================================================================================================
// This demo stark shows how different types of constant registers can be used. The transition
// This example shows how different types of constant registers can be used. The transition
// function is very simple: it operates with 1 mutable register and 2 readonly registers. The full
// execution trace is shown at the end of this file.
// define a filed in which we'll be working
const modulus = 96769n;
const field = new index_1.PrimeField(modulus);
// define state transition function
function demoTransition() {
const v0 = this.getValue(0);
const k0 = this.getConst(0);
const k1 = this.getConst(1);
// nv0 = v0 + 1 + k0 + 2 * k1
const nv0 = this.add(this.add(this.add(v0, 1n), k0), this.mul(2n, k1));
this.setNextValue(0, nv0);
}
// define state transition constraint
function demoConstraint() {
const v0 = this.getValue(0);
const k0 = this.getConst(0);
const k1 = this.getConst(1);
const nv0 = this.getNextValue(0);
return field.sub(nv0, field.add(field.add(field.add(v0, 1n), k0), field.mul(2n, k1)));
}
// define the STARK for the computation
const demoStark = new index_1.Stark({
field: field,
registerCount: 1,
constantCount: 2,
tFunction: demoTransition,
tConstraints: [demoConstraint],
tConstraintDegree: 1
field: new index_1.PrimeField(96769n),
tExpressions: {
'n0': 'r0 + 1 + k0 + 2 * k1'
},
tConstraints: [
'n0 - (r0 + 1 + k0 + 2 * k1)'
],
tConstraintDegree: 1,
constants: [{
values: [1n, 2n, 3n, 4n],
pattern: 'repeat'
}, {
values: [1n, 2n, 3n, 4n, 5n, 6n, 7n, 8n],
pattern: 'spread'
}]
});
// TESTING
// ================================================================================================
let steps = 2 ** 6, result = 292n;
const steps = 2 ** 6, result = 292n;
// set up inputs and assertions
const inputs = [1n];
const constants = [{
values: [1n, 2n, 3n, 4n],
pattern: 1 /* repeat */
},
{
values: [1n, 2n, 3n, 4n, 5n, 6n, 7n, 8n],
pattern: 2 /* stretch */
}];
const assertions = [

@@ -59,6 +39,6 @@ { step: 0, register: 0, value: 1n },

// generate a proof
const proof = demoStark.prove(assertions, steps, inputs, constants);
const proof = demoStark.prove(assertions, steps, inputs);
console.log('-'.repeat(20));
// verify the proof
demoStark.verify(assertions, proof, steps, constants);
demoStark.verify(assertions, proof, steps);
console.log('-'.repeat(20));

@@ -65,0 +45,0 @@ // EXECUTION TRACE

52

examples/fibonacci.js

@@ -9,36 +9,16 @@ "use strict";

// ================================================================================================
// define a filed in which we'll be working
const modulus = 2n ** 32n - 3n * 2n ** 25n + 1n;
const field = new index_1.PrimeField(modulus);
// define state transition function for Fibonacci sequence:
// each step advances Fibonacci sequence by 2 values
function fibTransition() {
const v0 = this.getValue(0);
const v1 = this.getValue(1);
const v2 = this.add(v0, v1);
const v3 = this.add(v1, v2);
this.setNextValue(0, v2);
this.setNextValue(1, v3);
}
// make sure register 0 is updated correctly
function fibConstraint1() {
const v0 = this.getValue(0);
const v1 = this.getValue(1);
const v2 = this.getNextValue(0);
return this.sub(v2, this.add(v0, v1));
}
// make sure register 1 is updated correctly
function fibConstraint2() {
const v0 = this.getValue(0);
const v1 = this.getValue(1);
const v2 = this.add(v0, v1);
const v3 = this.getNextValue(1);
return this.sub(v3, this.add(v1, v2));
}
// create the STARK for Fibonacci calculation
// This example shows how to create a STARK to verify computation of Fibonacci numbers. Because a
// Fibonacci number depends on 2 values preceding it, we set up the STARK with 2 mutable registers
// holding 2 consecutive Fibonacci numbers. So, in effect, a single step in the computation
// advances the Fibonacci sequence by 2 values.
const fibStark = new index_1.Stark({
field: field,
registerCount: 2,
tFunction: fibTransition,
tConstraints: [fibConstraint1, fibConstraint2],
field: new index_1.PrimeField(2n ** 32n - 3n * 2n ** 25n + 1n),
tExpressions: {
'n0': 'r0 + r1',
'n1': 'r1 + (r0 + r1)'
},
tConstraints: [
'n0 - (r0 + r1)',
'n1 - (r1 + r0 + r1)'
],
tConstraintDegree: 1 // max degree of our constraints is 1

@@ -48,5 +28,5 @@ });

// ================================================================================================
//let steps = 2**6, result = 1783540607n; // ~50 ms to prove, ~12 KB proof size
let steps = 2 ** 13, result = 203257732n; // ~1 second to prove, ~147 KB proof size
//let steps = 2**17, result = 2391373091n; // ~13 seconds to prove, ~290 KB proof size
//const steps = 2**6, result = 1783540607n; // ~50 ms to prove, ~12 KB proof size
const steps = 2 ** 13, result = 203257732n; // ~1 second to prove, ~147 KB proof size
//const steps = 2**17, result = 2391373091n; // ~13 seconds to prove, ~290 KB proof size
// set up inputs and assertions

@@ -53,0 +33,0 @@ const inputs = [1n, 1n]; // step 0 and 1 in Fibonacci sequence are 1

55

examples/mimc.js

@@ -9,5 +9,2 @@ "use strict";

// ================================================================================================
// define a filed in which we'll be working
const modulus = 2n ** 256n - 351n * 2n ** 32n + 1n;
const field = new index_1.PrimeField(modulus);
// define round constants

@@ -18,39 +15,24 @@ const roundConstants = new Array(64);

}
// define state transition function for MiMC computation
function mimcTransition() {
const v = this.getValue(0); // get current state for register 0
const k = this.getConst(0); // get current state for constant 0
// nv = v**3 + k
const nv = this.add(this.exp(v, 3n), k);
// set the next state for register 0
this.setNextValue(0, nv);
}
// define constraint checking function for MiMC computation
function mimcConstraint() {
const v = this.getValue(0); // get current state from register 0
const k = this.getConst(0); // get current state from constant 0
const nv = this.getNextValue(0); // get next state from register 0
// compute: nv - (v**3 + k)
return this.sub(nv, this.add(this.exp(v, 3n), k));
}
// create the STARK for MiMC computation
const mimcStark = new index_1.Stark({
field: field,
registerCount: 1,
constantCount: 1,
tFunction: mimcTransition,
tConstraints: [mimcConstraint],
tConstraintDegree: 3 // max degree of our constraints is 3
field: new index_1.PrimeField(2n ** 256n - 351n * 2n ** 32n + 1n),
tExpressions: {
'n0': 'r0^3 + k0'
},
tConstraints: [
'n0 - (r0^3 + k0)'
],
tConstraintDegree: 3,
constants: [{
values: roundConstants,
pattern: 'repeat'
}]
});
// TESTING
// ================================================================================================
//let steps = 2**6, result = 115147868172009559599970888602262339785331471694954098733392001040646413813295n; // ~100 ms, ~46 KB
let steps = 2 ** 13, result = 95224774355499767951968048714566316597785297695903697235130434363122555476056n; // ~4.5 sec, ~220 KB
//let steps = 2**17, result = 47923185371606372287465305238563325603777484372847211522043297561219208703471n; // ~72 sec, ~394 KB
//const steps = 2**6, result = 115147868172009559599970888602262339785331471694954098733392001040646413813295n; // ~100 ms, ~46 KB
const steps = 2 ** 13, result = 95224774355499767951968048714566316597785297695903697235130434363122555476056n; // ~4.5 sec, ~220 KB
//const steps = 2**17, result = 47923185371606372287465305238563325603777484372847211522043297561219208703471n; // ~72 sec, ~394 KB
// set up inputs and assertions
const inputs = [3n]; // we need to provide starting value for 1 register
const constants = [{
values: roundConstants,
pattern: 1 /* repeat */ // specify that round constants cycle during execution
}];
const assertions = [

@@ -60,5 +42,4 @@ { step: 0, register: 0, value: inputs[0] },

];
// prove that the assertions hold if we execute MiMC computation
// for the given number of steps with given inputs and constants
let proof = mimcStark.prove(assertions, steps, inputs, constants);
// prove that the assertions hold if we execute MiMC computation for the given number of steps
let proof = mimcStark.prove(assertions, steps, inputs);
console.log('-'.repeat(20));

@@ -77,4 +58,4 @@ // serialize the proof

// verify the proof
mimcStark.verify(assertions, proof, steps, constants);
mimcStark.verify(assertions, proof, steps);
console.log('-'.repeat(20));
//# sourceMappingURL=mimc.js.map

89

genstark.d.ts

@@ -19,13 +19,7 @@ declare module '@guildofweavers/genstark' {

/** Number of mutable registers in the computation */
registerCount: number;
/** A set of transition expressions for all mutable registers */
tExpressions: { [register: string]: string };
/** Number of readonly registers in the computation */
constantCount?: number;
/** State transition function for the computation */
tFunction: TransitionFunction;
/** A list of transition constraints for the computation */
tConstraints: TransitionConstraint[];
tConstraints: string[];

@@ -35,3 +29,6 @@ /** Maximum degree of transition constraints */

/** Execution trace extension factor; defaults to 8 */
/** A list of constant definitions for all readonly registers */
constants?: Constant[];
/** Execution trace extension factor */
extensionFactor?: number;

@@ -47,5 +44,2 @@

hashAlgorithm?: HashAlgorithm;
/** Logger for tracking proof / verification processes */
logger?: Logger;
}

@@ -56,3 +50,3 @@

/** Create a STARK based on the provided config parameters */
constructor(config: StarkConfig);
constructor(config: StarkConfig, logger?: Logger);

@@ -64,5 +58,4 @@ /**

* @param inputs Initial values for all mutable registers
* @param constants Definitions for all readonly registers
*/
prove(assertions: Assertion[], steps: number, inputs: bigint[], constants?: Constant[]): StarkProof;
prove(assertions: Assertion[], steps: number, inputs: bigint[]): StarkProof;

@@ -74,5 +67,4 @@ /**

* @param steps Number of steps in the computation
* @param constants Definitions for readonly registers
*/
verify(assertions: Assertion[], proof: StarkProof, steps: number, constants?: Constant[]): boolean;
verify(assertions: Assertion[], proof: StarkProof, steps: number): boolean;

@@ -104,2 +96,4 @@ /** Returns the size in bytes for the provided proof */

export type ConstantPattern = 'repeat' | 'spread';
export interface Constant {

@@ -110,11 +104,6 @@ values : bigint[];

export const enum ConstantPattern {
repeat = 1,
stretch = 2
}
// CONSTRAINTS
// --------------------------------------------------------------------------------------------
export interface Assertion {
/** register index */
/** index of a mutable register */
register: number;

@@ -129,42 +118,2 @@

export interface TransitionFunction {
(this: ExecutionFrame): void;
}
export interface TransitionConstraint {
(this: EvaluationFrame): bigint;
}
// FRAMES
// --------------------------------------------------------------------------------------------
export interface ExecutionFrame extends FrameOps {
/** Get the current value from a mutable register specified by the index */
getValue(index: number): bigint;
/** Get the current value from a readonly register specified by the index */
getConst(index: number): bigint;
/** Set the next value for a mutable register specified by the index */
setNextValue(index: number, value: bigint): void;
}
export interface EvaluationFrame extends FrameOps {
/** Get the current value from a mutable register specified by the index */
getValue(index: number): bigint;
/** Get the current value from a readonly register specified by the index */
getConst(index: number): bigint;
/** Get the next value from a mutable register specified by the index */
getNextValue(index: number): bigint;
}
interface FrameOps {
add(a: bigint, b: bigint): bigint;
sub(a: bigint, b: bigint): bigint;
mul(a: bigint, b: bigint): bigint;
div(a: bigint, b: bigint): bigint;
exp(b: bigint, p: bigint): bigint;
}
// LOW DEGREE PROOF

@@ -195,2 +144,14 @@ // --------------------------------------------------------------------------------------------

export interface TransitionFunction {
(r: bigint[][], k: ReadonlyRegister[], steps: number, field: FiniteField): void;
}
export interface BatchConstraintEvaluator {
(q: bigint[][], r: bigint[][], k: ReadonlyRegister[], steps: number, skip: number, field: FiniteField): void;
}
export interface ConstraintEvaluator {
(r: bigint[], n: bigint[], k: bigint[], field: FiniteField): bigint[];
}
export interface ReadonlyRegister {

@@ -197,0 +158,0 @@ getValue(step: number, skip: boolean): bigint;

4

lib/registers/index.js

@@ -5,4 +5,4 @@ "use strict";

exports.RepeatedConstants = RepeatedConstants_1.RepeatedConstants;
var StretchedConstants_1 = require("./StretchedConstants");
exports.StretchedConstants = StretchedConstants_1.StretchedConstants;
var SpreadConstants_1 = require("./SpreadConstants");
exports.SpreadConstants = SpreadConstants_1.SpreadConstants;
//# sourceMappingURL=index.js.map

221

lib/Stark.js

@@ -6,18 +6,6 @@ "use strict";

const registers_1 = require("./registers");
const frames_1 = require("./frames");
const merkle_1 = require("@guildofweavers/merkle");
const config_1 = require("./config");
const Serializer_1 = require("./Serializer");
const StarkError_1 = require("./StarkError");
// MODULE VARIABLES
// ================================================================================================
const MAX_DOMAIN_SIZE = 2 ** 32;
const MAX_REGISTER_COUNT = 64;
const MAX_CONSTANT_COUNT = 64;
const MAX_CONSTRAINT_COUNT = 1024;
const MAX_CONSTRAINT_DEGREE = 16;
const MAX_EXTENSION_FACTOR = 32;
const MAX_EXE_SPOT_CHECK_COUNT = 128;
const MAX_FRI_SPOT_CHECK_COUNT = 64;
const DEFAULT_EXE_SPOT_CHECK_COUNT = 80;
const DEFAULT_FRI_SPOT_CHECK_COUNT = 40;
// CLASS DEFINITION

@@ -28,22 +16,24 @@ // ================================================================================================

// --------------------------------------------------------------------------------------------
constructor(config) {
const vConfig = validateConfig(config);
constructor(config, logger) {
const vConfig = config_1.parseStarkConfig(config);
this.field = vConfig.field;
this.registerCount = vConfig.registerCount;
this.constantCount = vConfig.constantCount;
this.tFunction = vConfig.tFunction;
this.tConstraints = vConfig.tConstraints;
this.tConstraintDegree = vConfig.tConstraintDegree;
this.constraintCount = vConfig.constraintCount;
this.maxConstraintDegree = vConfig.tConstraints.maxDegree;
this.constants = vConfig.constants;
this.extensionFactor = vConfig.extensionFactor;
this.exeSpotCheckCount = vConfig.exeSpotCheckCount;
this.friSpotCheckCount = vConfig.friSpotCheckCount;
this.extensionFactor = vConfig.extensionFactor;
this.applyTransitions = vConfig.tFunction;
this.applyConstraints = vConfig.tConstraints.batchEvaluator;
this.evaluateConstraints = vConfig.tConstraints.evaluator;
this.hashAlgorithm = vConfig.hashAlgorithm;
this.logger = vConfig.logger;
this.logger = logger || new utils_1.Logger();
}
// PROVER
// --------------------------------------------------------------------------------------------
prove(assertions, steps, inputs, constants) {
prove(assertions, steps, inputs) {
const label = this.logger.start('Starting STARK computation');
const evaluationDomainSize = steps * this.extensionFactor;
const constraintCount = this.tConstraints.length;
const constantCount = this.constants.length;
// 0 ----- validate parameters

@@ -54,3 +44,3 @@ if (assertions.length < 1)

throw new TypeError('Number of steps must be a power of 2');
const maxSteps = MAX_DOMAIN_SIZE / this.extensionFactor;
const maxSteps = config_1.MAX_DOMAIN_SIZE / this.extensionFactor;
if (steps > maxSteps)

@@ -62,14 +52,6 @@ throw new TypeError(`Number of steps cannot exceed ${maxSteps}`);

throw new TypeError(`Inputs array must have exactly ${this.registerCount} elements`);
if (this.constantCount > 0) {
if (!constants)
throw new TypeError(`Constants array must be provided`);
if (!Array.isArray(constants))
throw new TypeError(`Constants parameter must be an array`);
if (constants.length > this.constantCount)
throw new TypeError(`Constants array must have exactly ${this.constantCount} elements`);
for (let i = 0; i < inputs.length; i++) {
if (typeof inputs[i] !== 'bigint')
throw new TypeError(`Input for register r${i} is not a BigInt`);
}
else {
if (constants)
throw new TypeError('Constants parameter was not expected');
}
// 1 ----- set up evaluation context

@@ -84,3 +66,3 @@ const G2 = this.field.getRootOfUnity(evaluationDomainSize);

registerCount: this.registerCount,
constantCount: this.constantCount,
constantCount: constantCount,
hashAlgorithm: this.hashAlgorithm

@@ -92,3 +74,3 @@ };

const zPoly = new components_1.ZeroPolynomial(context);
const cRegisters = buildReadonlyRegisters(constants, context, evaluationDomain);
const cRegisters = buildReadonlyRegisters(this.constants, context, evaluationDomain);
this.logger.log(label, 'Set up evaluation context');

@@ -102,13 +84,8 @@ // 2 ----- generate execution trace

}
// then, apply transition function for each subsequent step
let exeStep;
const executionFrame = new frames_1.ProofFrame(this.field, executionTrace, cRegisters);
// then, apply transition function for all steps
try {
for (exeStep = 0; exeStep < executionDomain.length - 1; exeStep++) {
executionFrame.currentStep = exeStep;
this.tFunction.call(executionFrame);
}
this.applyTransitions(executionTrace, cRegisters, steps, this.field);
}
catch (error) {
throw new StarkError_1.StarkError(`Generation of execution trace failed at step ${exeStep}`, error);
throw new StarkError_1.StarkError('Failed to generate execution trace', error);
}

@@ -130,23 +107,11 @@ // finally, make sure assertions don't contradict execution trace

// 4 ----- compute constraint polynomials Q(x) = C(P(x))
let cIndex;
const nonfinalSteps = evaluationDomainSize - this.extensionFactor;
const frame = new frames_1.ProofFrame(this.field, pEvaluations, cRegisters, this.extensionFactor);
const qEvaluations = new Array(constraintCount);
const qEvaluations = new Array(this.constraintCount);
for (let i = 0; i < this.constraintCount; i++) {
qEvaluations[i] = new Array(evaluationDomainSize);
}
try {
for (cIndex = 0; cIndex < constraintCount; cIndex++) {
let constraint = this.tConstraints[cIndex];
qEvaluations[cIndex] = new Array(evaluationDomainSize);
for (let step = 0; step < evaluationDomainSize; step++) {
frame.currentStep = step;
let q = constraint.call(frame);
if (step < nonfinalSteps && step % this.extensionFactor === 0 && q !== 0n) {
let execStep = step / this.extensionFactor;
throw new StarkError_1.StarkError(`The constraint didn't evaluate to 0 at step ${execStep}`);
}
qEvaluations[cIndex][step] = q;
}
}
this.applyConstraints(qEvaluations, pEvaluations, cRegisters, evaluationDomainSize, this.extensionFactor, this.field);
}
catch (error) {
throw new StarkError_1.StarkError(`Error in constraint ${cIndex}`, error);
throw new StarkError_1.StarkError('Failed to evaluate transition constraints', error);
}

@@ -170,3 +135,3 @@ this.logger.log(label, 'Computed Q(x) polynomials');

const hash = merkle_1.getHashFunction(this.hashAlgorithm);
const serializer = new Serializer_1.Serializer(this.field, this.registerCount, constraintCount);
const serializer = new Serializer_1.Serializer(this.field, this.registerCount, this.constraintCount);
const mergedEvaluations = new Array(evaluationDomainSize);

@@ -249,6 +214,6 @@ const hashedEvaluations = new Array(evaluationDomainSize);

// --------------------------------------------------------------------------------------------
verify(assertions, proof, steps, constants) {
verify(assertions, proof, steps) {
const label = this.logger.start('Starting STARK verification');
const evaluationDomainSize = steps * this.extensionFactor;
const constraintCount = this.tConstraints.length;
const constantCount = this.constants.length;
const eRoot = proof.evaluations.root;

@@ -260,17 +225,5 @@ // 0 ----- validate parameters

throw new TypeError('Number of steps must be a power of 2');
const maxSteps = MAX_DOMAIN_SIZE / this.extensionFactor;
const maxSteps = config_1.MAX_DOMAIN_SIZE / this.extensionFactor;
if (steps > maxSteps)
throw new TypeError(`Number of steps cannot exceed ${maxSteps}`);
if (this.constantCount > 0) {
if (!constants)
throw new TypeError(`Constants array must be provided`);
if (!Array.isArray(constants))
throw new TypeError(`Constants parameter must be an array`);
if (constants.length > this.constantCount)
throw new TypeError(`Constants array must have exactly ${this.constantCount} elements`);
}
else {
if (constants)
throw new TypeError('Constants parameter was not expected');
}
// 1 ----- set up evaluation context

@@ -284,3 +237,3 @@ const G2 = this.field.getRootOfUnity(evaluationDomainSize);

registerCount: this.registerCount,
constantCount: this.constantCount,
constantCount: constantCount,
hashAlgorithm: this.hashAlgorithm

@@ -290,3 +243,3 @@ };

const zPoly = new components_1.ZeroPolynomial(context);
const cRegisters = buildReadonlyRegisters(constants, context);
const cRegisters = buildReadonlyRegisters(this.constants, context);
this.logger.log(label, 'Set up evaluation context');

@@ -304,3 +257,3 @@ // 2 ----- compute positions for evaluation spot-checks

const hash = merkle_1.getHashFunction(this.hashAlgorithm);
const serializer = new Serializer_1.Serializer(this.field, this.registerCount, constraintCount);
const serializer = new Serializer_1.Serializer(this.field, this.registerCount, this.constraintCount);
for (let i = 0; i < proof.evaluations.values.length; i++) {

@@ -346,12 +299,9 @@ let mergedEvaluations = proof.evaluations.values[i];

}
const lPolyCount = constraintCount + 2 * (this.registerCount + bPoly.count);
const lPolyCount = this.constraintCount + 2 * (this.registerCount + bPoly.count);
const lCoefficients = this.field.prng(eRoot, lPolyCount);
this.logger.log(label, `Verified low-degree proof`);
// 7 ----- verify transition and boundary constraints
const pFrame = new frames_1.VerificationFrame(this.field, evaluationDomainSize, pEvaluations, cRegisters, this.extensionFactor);
for (let i = 0; i < positions.length; i++) {
let step = positions[i];
let x = this.field.exp(G2, BigInt(step));
pFrame.currentStep = step;
pFrame.currentX = x;
let pValues = pEvaluations.get(step);

@@ -361,7 +311,13 @@ let bValues = bEvaluations.get(step);

let zValue = zPoly.evaluateAt(x);
// check transition constraints
for (let j = 0; j < constraintCount; j++) {
let qValue = this.tConstraints[j].call(pFrame);
// build an array of constant values for the current step
let cValues = new Array(constantCount);
for (let j = 0; j < constantCount; j++) {
cValues[j] = cRegisters[j].getValueAt(x);
}
// check transition
let npValues = pEvaluations.get((step + this.extensionFactor) % evaluationDomainSize);
let qValues = this.evaluateConstraints(pValues, npValues, cValues, this.field);
for (let j = 0; j < this.constraintCount; j++) {
let qCheck = this.field.mul(zValue, dValues[j]);
if (qValue !== qCheck) {
if (qValues[j] !== qCheck) {
throw new StarkError_1.StarkError(`Transition constraint at position ${step} was not satisfied`);

@@ -408,3 +364,3 @@ }

sizeOf(proof) {
const valueCount = this.registerCount + this.tConstraints.length + proof.evaluations.bpc;
const valueCount = this.registerCount + this.constraintCount + proof.evaluations.bpc;
const valueSize = valueCount * this.field.elementSize;

@@ -415,7 +371,7 @@ const size = utils_1.sizeOf(proof, valueSize, this.hashAlgorithm);

serialize(proof) {
const serializer = new Serializer_1.Serializer(this.field, this.registerCount, this.tConstraints.length);
const serializer = new Serializer_1.Serializer(this.field, this.registerCount, this.constraintCount);
return serializer.serializeProof(proof, this.hashAlgorithm);
}
parse(buffer) {
const serializer = new Serializer_1.Serializer(this.field, this.registerCount, this.tConstraints.length);
const serializer = new Serializer_1.Serializer(this.field, this.registerCount, this.constraintCount);
return serializer.parseProof(buffer, this.hashAlgorithm);

@@ -440,3 +396,3 @@ }

// and, linear combination degree is max(deg(D(x)), steps)
const degree = steps * Math.max(this.tConstraintDegree - 1, 1);
const degree = steps * Math.max(this.maxConstraintDegree - 1, 1);
return degree;

@@ -448,70 +404,2 @@ }

// ================================================================================================
function validateConfig(config) {
if (!config)
throw new TypeError('STARK config was not provided');
if (!config.field)
throw new TypeError('Finite field was not provided');
const registerCount = config.registerCount;
if (registerCount < 1 || registerCount > MAX_REGISTER_COUNT || !Number.isInteger(registerCount)) {
throw new TypeError(`Number of state registers must be an integer between 1 and ${MAX_REGISTER_COUNT}`);
}
const constantCount = config.constantCount || 0;
if (constantCount < 0 || constantCount > MAX_CONSTANT_COUNT || !Number.isInteger(constantCount)) {
throw new TypeError(`Number of state constants must be an integer between 0 and ${MAX_CONSTANT_COUNT}`);
}
if (!config.tFunction)
throw new TypeError('Transition function was not provided');
if (!config.tConstraints)
throw new TypeError('Transition constraints array was not provided');
if (Array.isArray(!config.tConstraints)) {
throw new TypeError('Transition constraints must be provided as an array');
}
if (config.tConstraints.length === 0)
throw new TypeError('Transition constraints array was empty');
if (config.tConstraints.length > MAX_CONSTRAINT_COUNT) {
throw new TypeError(`Number of transition constraints cannot exceed ${MAX_CONSTRAINT_COUNT}`);
}
const tConstraintDegree = config.tConstraintDegree;
if (tConstraintDegree < 1 || tConstraintDegree > MAX_CONSTRAINT_DEGREE || !Number.isInteger(tConstraintDegree)) {
throw new TypeError(`Transition constraint degree must be an integer between 1 and ${MAX_CONSTRAINT_DEGREE}`);
}
let extensionFactor = config.extensionFactor;
if (extensionFactor === undefined) {
extensionFactor = 2 ** Math.ceil(Math.log2(tConstraintDegree * 2));
}
else {
if (extensionFactor < 2 || extensionFactor > MAX_EXTENSION_FACTOR || !Number.isInteger(extensionFactor)) {
throw new TypeError(`Extension factor must be an integer between 2 and ${MAX_EXTENSION_FACTOR}`);
}
if (!utils_1.isPowerOf2(extensionFactor)) {
throw new TypeError(`Extension factor must be a power of 2`);
}
if (extensionFactor < 2 * tConstraintDegree) {
throw new TypeError(`Extension factor must be at least 2x greater than the transition constraint degree`);
}
}
const exeSpotCheckCount = config.exeSpotCheckCount || DEFAULT_EXE_SPOT_CHECK_COUNT;
if (exeSpotCheckCount < 1 || exeSpotCheckCount > MAX_EXE_SPOT_CHECK_COUNT || !Number.isInteger(exeSpotCheckCount)) {
throw new TypeError(`Execution sample size must be an integer between 1 and ${MAX_EXE_SPOT_CHECK_COUNT}`);
}
const friSpotCheckCount = config.friSpotCheckCount || DEFAULT_FRI_SPOT_CHECK_COUNT;
if (friSpotCheckCount < 1 || friSpotCheckCount > MAX_FRI_SPOT_CHECK_COUNT || !Number.isInteger(friSpotCheckCount)) {
throw new TypeError(`FRI sample size must be an integer between 1 and ${MAX_FRI_SPOT_CHECK_COUNT}`);
}
const hashAlgorithm = config.hashAlgorithm || 'sha256';
const logger = config.logger || new utils_1.Logger();
return {
field: config.field,
registerCount: registerCount,
constantCount: constantCount,
tFunction: config.tFunction,
tConstraints: config.tConstraints,
tConstraintDegree: tConstraintDegree,
extensionFactor: extensionFactor,
exeSpotCheckCount: exeSpotCheckCount,
friSpotCheckCount: friSpotCheckCount,
hashAlgorithm: hashAlgorithm,
logger: logger
};
}
function buildReadonlyRegisters(constants, context, domain) {

@@ -521,8 +409,11 @@ const registers = new Array(constants ? constants.length : 0);

let c = constants[i];
if (c.pattern === 1 /* repeat */) {
if (c.pattern === 'repeat') {
registers[i] = new registers_1.RepeatedConstants(c.values, context, domain !== undefined);
}
else if (c.pattern === 2 /* stretch */) {
registers[i] = new registers_1.StretchedConstants(c.values, context, domain);
else if (c.pattern === 'spread') {
registers[i] = new registers_1.SpreadConstants(c.values, context, domain);
}
else {
throw new TypeError(`Invalid constant pattern '${c.pattern}'`);
}
}

@@ -529,0 +420,0 @@ return registers;

2

package.json
{
"name": "@guildofweavers/genstark",
"version": "0.1.0",
"version": "0.2.0",
"description": "zk-STARK generation library",

@@ -5,0 +5,0 @@ "main": "index.js",

152

README.md
# genSTARK
This library is intended to help you quickly and easily generate STARK-based proofs of computation using JavaScript. The goal is to take care of as much boilerplate code as possible, and let you focus on the specifics of the task at hand.
This library is intended to help you quickly and easily generate STARK-based proofs of computation using JavaScript. The goal is to take care of as much boilerplate code as possible, and let you focus on the specific "business logic" of your computations.
### Background
A STARK is a novel proof-of-computation scheme that allows you to create an efficiently verifiable proof that a computation was executed correctly. The scheme was developed by Eli-Ben Sasson and team at Technion-Israel Institute of Technology. STARKs do not require an initial trusted setup, and rely on very few cryptographic assumptions. See [references](#References) for more info.
### Disclaimer

@@ -13,38 +16,23 @@ **DO NOT USE THIS LIBRARY IN PRODUCTION.** At this point, this is a research-grade library. It has known and unknown bugs and security flaws.

# Usage
Here is a trivial example of how to use this library. In this case, the computation is just adding 1 to the current value at each step. That is: x<sub>n+1</sub> = x<sub>n</sub> + 1.
Here is a trivial example of how to use this library. In this example, the computation is just adding 2 to the current value at each step. That is: x<sub>n+1</sub> = x<sub>n</sub> + 2.
```TypeScript
import { Stark, PrimeField, ExecutionFrame, EvaluationFrame } from '@guildofweavers/genstark';
import { Stark, PrimeField } from '@guildofweavers/genstark';
// define a very simple state transition function
function fooTransition(this: ExecutionFrame) {
const v = this.getValue(0); // get value for current step from register 0
const nv = this.add(v, 1n);
this.setNextValue(0, nv); // next state = current state + 1
}
// define a corresponding transition constraint
function fooConstraint(this: EvaluationFrame): bigint {
const v = this.getValue(0); // get value for current step from register 0
const nv = this.getNextValue(0); // get value for the next step from register 0
return this.sub(nv, this.add(v, 1n)); // return nv - (v + 1)
}
// build a STARK for this computation
// define a STARK for this computation
const fooStark = new Stark({
field : new PrimeField(2n**32n - 3n * 2n**25n + 1n),
registerCount : 1, // we only need 1 register
tFunction : fooTransition,
tConstraints : [fooConstraint],
tConstraintDegree : 1 // degree of our constraint is 1
tExpressions : { 'n0': 'r0 + 2' }, // define transition function
tConstraints : ['n0 - (r0 + 2)'], // define transition constraints
tConstraintDegree : 1 // degree of our constraint is 1
});
// create a proof that if we start computation at 1, we end up at 64 after 64 steps
// create a proof that if we start computation at 1, we end up at 127 after 64 steps
const assertions = [
{ register: 0, step: 0, value: 1n }, // value at first step is 1
{ register: 0, step: 63, value: 64n } // value at last step is 64
{ register: 0, step: 63, value: 127n } // value at last step is 127
];
const proof = fooStark.prove(assertions, 64, [1n]);
// verify that if we start at 1 and run the computation for 64 steps, we get 64
// verify that if we start at 1 and run the computation for 64 steps, we get 127
const result = fooStark.verify(assertions, proof, 64);

@@ -109,7 +97,6 @@ console.log(result); // true

| field | A finite field for all math operations during the computation. Currently, only `PrimeField` is available (it is actually just re-exported from the [galois](https://github.com/GuildOfWeavers/galois) project). |
| registerCount | Number of mutable registers for the computation. Must be at least 1, and cannot be greater than 63. The `inputs` array passed to `prove()` method must hold values to initialize all specified registers. |
| constantCount? | Number of readonly registers for the computation. These registers are populated with data based on the `constants` parameter passed to `prove()` and `verify()` methods. This property is optional; the default is 0; the max is 64. |
| tFunction | State [transition function](#Transition-function) for the computation. |
| tConstraints | An array of [transition constraint](#Transition-constraints) functions for the computation. The array must contain at least one element. |
| tExpressions | An object with expressions defining state [transition function](#Transition-function) for all register. The number of registers must be between 1 and 64. |
| tConstraints | An array of [transition constraint](#Transition-constraints) expressions for the computation. The number of constraints must be between 1 and 1024. |
| tConstraintDegree | The highest algebraic degree of the provided transition constraints. |
| constants? | An array of [constant definitions](#Constants) for values that will be available in readonly registers during the computation. If provided, cannot have more than 64 elements. |
| extensionFactor? | Number by which the execution trace is "stretched." Must be a power of 2 at least 2x of the `tConstraintDegree`, but cannot exceed 32. This property is optional, the default is smallest power of 2 that is greater than `tConstraintDegree * 2`. |

@@ -119,3 +106,2 @@ | exeSpotCheckCount? | Number of positions in the execution trace to include into the proof. This property is optional; the default is 80; the max is 128. |

| hashAlgorithm? | Hash algorithm to use when building Merkle trees for the proof. Currently, can be one of two values: `sha256` or `blake2s256`. This property is optional; the default is `sha256`. |
| logger? | An optional [Logger](/lib/utils/Logger.ts) object to collect info about how STARK proof/verification are running. The default logger just prints everything to the console, but you can provide any other object that complies with the Logger interface. |

@@ -125,3 +111,3 @@ ## Generating and verifying proofs

```TypeScript
const proof = myStark.prove(assertions, steps, inputs, constants);
const proof = myStark.prove(assertions, steps, inputs);
```

@@ -135,8 +121,8 @@ The meaning of the parameters is as follows:

| inputs | An array of `BigInt`'s containing initial values for all mutable registers. The length of the array must be the same as `registerCount` specified in STARK config. |
| constants? | An array of [Constant](#Constants) objects defining how readonly registers are populated. The length of the array must be the same as `constantCount` specified in STARK config. If `constantCount=0`, this parameter should be omitted. |
Once you've generated a proof, you can verify it using `Stark.verify()` method like so:
```TypeScript
const result = myStark.verify(assertions, proof, steps, constants);
const result = myStark.verify(assertions, proof, steps);
```

@@ -150,3 +136,2 @@ The meaning of the parameters is as follows:

| steps | The same number of steps that was passed to the `prove()` method. |
| constants? | The same array of [Constant](#Constants) objects that was passed to the `prove()` method. |

@@ -160,65 +145,52 @@ Notice that `inputs` array does not need to be provided to the `verify()` method. Verifying the proof basically attests to something like this:

## Transition function
A core component of STARK's definition is the state transition function. The transition function is called once for each step of the computation, and must update all mutable registers to the next set of values. The function can access the current `ExecutionFrame` via `this` object.
You can use the execution frame to update a mutable register to the next value like so:
A core component of STARK's definition is the state transition function. You can define a state transition function by supplying transition expressions for all mutable registers like so:
```TypeScript
this.setNextValue(index, value);
{
'n0': 'r0 + k0 + 1'
}
```
where, `index` is a 0-based register index, and `value` is the new value for the register.
The above example defines a transition expression for a single register. Here is how to interpret it:
You can also use the execution frame to read current register values like so:
```TypeScript
this.getValue(index); // returns current value from a mutable register at the specified index
this.getConst(index); // returns current value from a readonly register at the specified index
```
* `r0` is a reference to the current value of mutable register 0.
* `n0` is a reference to the next value of mutable register 0.
* `k0` is a reference to the current value of readonly register 0.
Lastly, the execution frame exposes a set of math operations that you can use within the transition function:
So, the expression says: the next value of mutable register 0 is equal to the current value of the register, plus the current value of readonly register 0, plus 1.
You can use simple algebraic operators `+`, `-`, `*`, `/`, `^` to define expressions of any complexity. You can also have up to 64 mutable registers and up to 64 readonly registers. In case of multiple registers, you can refer to them as `r1`, `r2`, `r3`, etc.
One thing to note, you cannot reference future register states within a transition expression. So, something like this would not be valid:
```TypeScript
interface FrameOps {
add(a: bigint, b: bigint): bigint;
sub(a: bigint, b: bigint): bigint;
mul(a: bigint, b: bigint): bigint;
div(a: bigint, b: bigint): bigint;
exp(b: bigint, p: bigint): bigint;
{
'n0': 'r0 + 1',
'n1': 'n0 * 2'
}
```
**Important:** you should rely only on the exposed math operations to calculate the next set of register values. Using other operations or conditional logic may generate proofs that will fail upon verification.
## Transition constraints
Another core component of STARK's definition is a set of transition constraints. A computation is considered valued only if transition constraints are satisfied for all steps (except the last one).
Similarly to transition function, a transition constraint is a function that is called once for each step of the computation. If the constraint function returns 0, the constraint is satisfied, otherwise the constraint fails. At each step, the function can access the current `EvaluationFrame` via `this` object.
An evaluation frame is similar to the execution frame, except instead of `setNextValue()` method, it exposes a `getNextValue()` method:
But you can easily redefine this as a valid expression like so:
```TypeScript
this.getValue(index); // returns current value from a mutable register at the specified index
this.getConst(index); // returns current value from a readonly register at the specified index
this.getNextValue(index); // returns next value from a mutable register at the specified index
{
'n0': 'r0 + 1',
'n1': '(r0 + 1) * 2'
}
```
Also, similarly to the execution frame, evaluation frame exposes a set of math operations that you can use within the transition constraint function:
## Transition constraints
Another core component of STARK's definition is a set of transition constraints. A computation is considered valid only if transition constraints are satisfied for all steps (except the last one).
Similarly to transition function, a transition constraint is defined using algebraic expressions like so:
```TypeScript
interface FrameOps {
add(a: bigint, b: bigint): bigint;
sub(a: bigint, b: bigint): bigint;
mul(a: bigint, b: bigint): bigint;
div(a: bigint, b: bigint): bigint;
exp(b: bigint, p: bigint): bigint;
}
[
`n0 - (r0 + k0 + 1)`
]
```
However, unlike transition function, transition constraints can reference future states of mutable registers.
**Important:** you should rely only on the exposed math operations to perform calculations with the function. Using other operations or conditional logic may generate proofs that will fail upon verification.
**Note:** you should note the highest algebraic degree you use in the constraint expressions and pass it to the `Stark` constructor as `tConstraintDegree` property. For example, if you raise value of some register to power 3 (or perform equivalent computation), your `tConstraintDegree` should be set to 3.
**Note:** you should note the highest algebraic degree of calculations you use in the constraint function and pass it to the `Stark` constructor as `tConstraintDegree` property. For example, if you raise register value to power 3, your `tConstraintDegree` should be set to 3.
## Assertions
Assertions (or boundary constraints) are objects that specify the exact value of a given register at a given step. An assertion object has the following form:
Assertions (or boundary constraints) are objects that specify the exact value of a given mutable register at a given step. An assertion object has the following form:
```TypeScript
interface Assertion {
register: number; // register index
register: number; // index of a mutable register
step : number; // step in the execution trace

@@ -230,5 +202,5 @@ value : bigint; // value that the register should have at the specified step

## Constants
In addition to mutable registers, you can define STARKs with readonly registers. A readonly register is a register whose value cannot be changed during the computation. You can read values from such registers using `getConst()` method of execution and evaluation frames as described previously.
In addition to mutable registers, you can define STARKs with readonly registers. A readonly register is a register whose value cannot be changed by a transition function. You can reference readonly registers in your expressions by using the `k` prefix. For example, `k0`, `k1`, `k2` etc.
You can defined readonly registers by using `Constant` object, which has the following form:
You can defined readonly registers by providing constant definitions to `Stark` constructor. Constant definitions have the following form:
```TypeScript

@@ -243,3 +215,3 @@ interface Constant {

* **repeat** - the constants will be "cycled" during execution. For example, if `values = [1, 2, 3, 4]`, and the execution trace is 16 steps long, the constants will appear in the execution trace as: `[1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]`.
* **stretch** - the constants will be "stretched" during execution. For example, if `values = [1, 2, 3, 4]`, and the execution trace is 16 steps long, the constants will appear as: `[1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 4, 0, 0, 0]`.
* **spread** - the constants will be "spread" during execution. For example, if `values = [1, 2, 3, 4]`, and the execution trace is 16 steps long, the constants will appear as: `[1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 4, 0, 0, 0]`.

@@ -249,14 +221,14 @@ For more explanation see [demo](/examples/demo.ts) example.

# Performance
Some very informal benchmarks run on Intel Core i5-7300U @ 2.60GHz:
Some very informal benchmarks run on Intel Core i5-7300U @ 2.60GHz (single thread):
| STARK | Degree | Registers | Steps | Proof Time | Proof Size |
| --------- | :----: | :-------: | :------------: | :--------: | :--------: |
| MiMC | 3 | 1 | 2<sup>6</sup> | 100 ms | 46 KB |
| MiMC | 3 | 1 | 2<sup>13</sup> | 4.5 sec | 220 KB |
| MiMC | 3 | 1 | 2<sup>17</sup> | 72 sec | 394 KB |
| Fibonacci | 1 | 2 | 2<sup>6</sup> | 50 ms | 12 KB |
| Fibonacci | 1 | 2 | 2<sup>13</sup> | 1 sec | 147 KB |
| Fibonacci | 1 | 2 | 2<sup>17</sup> | 13 sec | 290 KB |
| STARK | Field Size | Degree | Registers | Steps | Proof Time | Proof Size |
| --------- | :--------: | :----: | :-------: | :------------: | :--------: | :--------: |
| MiMC | 256 bits | 3 | 1 | 2<sup>6</sup> | 100 ms | 46 KB |
| MiMC | 256 bits | 3 | 1 | 2<sup>13</sup> | 4.5 sec | 220 KB |
| MiMC | 256 bits | 3 | 1 | 2<sup>17</sup> | 72 sec | 394 KB |
| Fibonacci | 32 bits | 1 | 2 | 2<sup>6</sup> | 50 ms | 12 KB |
| Fibonacci | 32 bits | 1 | 2 | 2<sup>13</sup> | 1 sec | 147 KB |
| Fibonacci | 32 bits | 1 | 2 | 2<sup>17</sup> | 13 sec | 290 KB |
The potential to improve proof time is at least 10x (by moving hashing and math functions out of JavaScript), and potentially as much as 100x (by using SIMD and parallelism).
The potential to improve proof time is at least 10x (by moving hashing and math functions out of JavaScript), and potentially much higher (by using SIMD and parallelism).

@@ -263,0 +235,0 @@ # References

lib/frames/index.js
lib/frames/ProofFrame.js
lib/frames/VerificationFrame.js
lib/registers/StretchedConstants.js
SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc