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.5.7 to 0.6.0

19

genstark.d.ts

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

* @param assertions Boundary constraints for the computation
* @param initValues An array containing initial values for all mutable registers
* @param publicInputs An array containing values for all specified public registers
* @param secretInputs An array containing values for all specified secret registers
* @param inputs TODO
* @param auxPublicInputs TODO
* @param auxSecretInputs TODO
*/
prove(assertions: Assertion[], initValues: bigint[], publicInputs?: bigint[][], secretInputs?: bigint[][]): StarkProof;
prove(assertions: Assertion[], inputs: any[], auxPublicInputs?: bigint[][], auxSecretInputs?: bigint[][]): StarkProof;

@@ -76,5 +76,5 @@ /**

* @param proof Proof of the computation
* @param publicInputs An array containing values for all specified public registers
* @param auxPublicInputs TODO
*/
verify(assertions: Assertion[], proof: StarkProof, publicInputs?: bigint[][]): boolean;
verify(assertions: Assertion[], proof: StarkProof, auxPublicInputs?: bigint[][]): boolean;

@@ -92,5 +92,6 @@ /** Returns the size in bytes for the provided proof */

export interface StarkProof {
evRoot : Buffer;
evProof : BatchMerkleProof;
ldProof : LowDegreeProof;
evRoot : Buffer;
evProof : BatchMerkleProof;
ldProof : LowDegreeProof;
traceShape : number[];
}

@@ -97,0 +98,0 @@

4

lib/components/CompositionPolynomial.js

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

// --------------------------------------------------------------------------------------------
evaluateAt(x, pValues, nValues, sValues, context) {
evaluateAt(x, pValues, nValues, hValues, context) {
// evaluate transition constraints at x
const qValues = context.evaluateConstraintsAt(x, pValues, nValues, sValues);
const qValues = context.evaluateConstraintsAt(x, pValues, nValues, hValues);
// adjust transition constraint degrees

@@ -114,0 +114,0 @@ for (let { degree, indexes } of this.constraintGroups) {

21

lib/Serializer.js

@@ -13,3 +13,4 @@ "use strict";

this.stateWidth = config.stateWidth;
this.secretInputCount = config.secretInputCount;
this.iRegisterCount = config.iRegisterCount;
this.sRegisterCount = config.sRegisterCount;
this.hashDigestSize = hashDigestSize;

@@ -45,2 +46,7 @@ }

}
// trace shape
offset = buffer.writeUInt8(proof.traceShape.length, offset);
for (let level of proof.traceShape) {
offset = buffer.writeUInt32LE(level, offset);
}
// return the buffer

@@ -84,2 +90,10 @@ return buffer;

}
// trace shape
const traceDepth = buffer.readUInt8(offset);
offset += 1;
const traceShape = new Array(traceDepth);
for (let i = 0; i < traceDepth; i++) {
traceShape[i] = buffer.readUInt32LE(offset);
offset += 4;
}
// build and return the proof

@@ -94,3 +108,4 @@ return {

remainder: friRemainder
}
},
traceShape: traceShape
};

@@ -101,3 +116,3 @@ }

getValueCount() {
return this.stateWidth + this.secretInputCount;
return this.stateWidth + this.sRegisterCount + this.iRegisterCount;
}

@@ -104,0 +119,0 @@ }

62

lib/Stark.js

@@ -30,7 +30,8 @@ "use strict";

throw new TypeError('Source script cannot be an empty string');
let extensionFactor = security ? security.extensionFactor : undefined;
let sOptions;
if (optimization) {
const wasmOptions = buildWasmOptions(optimization);
// instantiate AIR object
this.air = air_script_1.parseScript(source, undefined, wasmOptions);
// instantiate AIR module
this.air = air_script_1.parseScript(source, { wasmOptions, extensionFactor });
if (!this.air.field.isOptimized) {

@@ -40,3 +41,3 @@ console.warn(`WARNING: WebAssembly optimization is not available for the specified field`);

// instantiate Hash object
sOptions = validateSecurityOptions(security, this.air.maxConstraintDegree);
sOptions = validateSecurityOptions(security, this.air.extensionFactor);
const wasmOptions2 = buildWasmOptions(optimization); // TODO: use the same options as for AIR

@@ -49,4 +50,4 @@ this.hash = merkle_1.createHash(sOptions.hashAlgorithm, wasmOptions2);

else {
this.air = air_script_1.parseScript(source);
sOptions = validateSecurityOptions(security, this.air.maxConstraintDegree);
this.air = air_script_1.parseScript(source, { extensionFactor });
sOptions = validateSecurityOptions(security, this.air.extensionFactor);
this.hash = merkle_1.createHash(sOptions.hashAlgorithm, false);

@@ -75,3 +76,3 @@ }

// --------------------------------------------------------------------------------------------
prove(assertions, initValues, publicInputs, secretInputs) {
prove(assertions, inputs, auxPublicInputs, auxSecretInputs) {
const log = this.logger.start('Starting STARK computation');

@@ -83,7 +84,7 @@ // 0 ----- validate parameters

throw new TypeError('At least one assertion must be provided');
if (!Array.isArray(initValues))
if (!Array.isArray(inputs))
throw new TypeError('Initialization values parameter must be an array');
// 1 ----- set up evaluation context
const field = this.air.field;
const context = this.air.createContext(publicInputs || [], secretInputs || [], this.extensionFactor);
const context = this.air.initProof(inputs, auxPublicInputs || [], auxSecretInputs || []);
const evaluationDomainSize = context.evaluationDomain.length;

@@ -94,3 +95,3 @@ log('Set up evaluation context');

try {
executionTrace = context.generateExecutionTrace(initValues);
executionTrace = context.generateExecutionTrace();
validateAssertions(executionTrace, assertions);

@@ -108,4 +109,4 @@ }

// 4 ----- build merkle tree for evaluations of P(x) and S(x)
const sEvaluations = context.getSecretRegisterTraces();
const eVectors = [...field.matrixRowsToVectors(pEvaluations), ...sEvaluations];
const hEvaluations = context.hiddenRegisterTraces;
const eVectors = [...field.matrixRowsToVectors(pEvaluations), ...hEvaluations];
const hashedEvaluations = this.hash.mergeVectorRows(eVectors);

@@ -123,3 +124,3 @@ log('Serialized evaluations of P(x) and S(x) polynomials');

const lCombination = new components_1.LinearCombination(eTree.root, cPoly.compositionDegree, cPoly.coefficientCount, context);
const lEvaluations = lCombination.computeMany(cEvaluations, pEvaluations, sEvaluations);
const lEvaluations = lCombination.computeMany(cEvaluations, pEvaluations, hEvaluations);
log('Combined P(x) and S(x) evaluations with C(x) evaluations');

@@ -150,3 +151,4 @@ // 7 ----- Compute low-degree proof

evProof: eProof,
ldProof: ldProof
ldProof: ldProof,
traceShape: context.traceShape
};

@@ -156,3 +158,3 @@ }

// --------------------------------------------------------------------------------------------
verify(assertions, proof, publicInputs) {
verify(assertions, proof, auxPublicInputs) {
const log = this.logger.start('Starting STARK verification');

@@ -166,3 +168,3 @@ // 0 ----- validate parameters

const extensionFactor = this.extensionFactor;
const context = this.air.createContext(publicInputs || [], extensionFactor);
const context = this.air.initVerification(proof.traceShape, auxPublicInputs || []);
const evaluationDomainSize = context.traceLength * extensionFactor;

@@ -178,9 +180,9 @@ const cPoly = new components_1.CompositionPolynomial(this.air.constraints, assertions, eRoot, context, utils_1.noop);

const pEvaluations = new Map();
const sEvaluations = new Map();
const hEvaluations = new Map();
for (let i = 0; i < proof.evProof.values.length; i++) {
let mergedEvaluations = proof.evProof.values[i];
let position = augmentedPositions[i];
let [p, s] = this.parseValues(mergedEvaluations);
let [p, h] = this.parseValues(mergedEvaluations);
pEvaluations.set(position, p);
sEvaluations.set(position, s);
hEvaluations.set(position, h);
}

@@ -209,7 +211,7 @@ log(`Decoded evaluation spot checks`);

let nValues = pEvaluations.get((step + extensionFactor) % evaluationDomainSize);
let sValues = sEvaluations.get(step);
let hValues = hEvaluations.get(step);
// evaluate composition polynomial at x
let cValue = cPoly.evaluateAt(x, pValues, nValues, sValues, context);
let cValue = cPoly.evaluateAt(x, pValues, nValues, hValues, context);
// combine composition polynomial evaluation with values of P(x) and S(x)
lcValues[i] = lCombination.computeOne(x, cValue, pValues, sValues);
lcValues[i] = lCombination.computeOne(x, cValue, pValues, hValues);
}

@@ -267,13 +269,14 @@ log(`Verified transition and boundary constraints`);

const stateWidth = this.air.stateWidth;
const secretInputCount = this.air.secretInputCount;
const sRegisterCount = this.air.sRegisterCount;
const iRegisterCount = this.air.iRegisterCount;
let offset = 0;
const pValues = new Array(stateWidth);
for (let i = 0; i < stateWidth; i++, offset += elementSize) {
for (let i = 0; i < pValues.length; i++, offset += elementSize) {
pValues[i] = utils_1.readBigInt(buffer, offset, elementSize);
}
const sValues = new Array(secretInputCount);
for (let i = 0; i < secretInputCount; i++, offset += elementSize) {
sValues[i] = utils_1.readBigInt(buffer, offset, elementSize);
const hValues = new Array(sRegisterCount + iRegisterCount);
for (let i = 0; i < hValues.length; i++, offset += elementSize) {
hValues[i] = utils_1.readBigInt(buffer, offset, elementSize);
}
return [pValues, sValues];
return [pValues, hValues];
}

@@ -284,3 +287,3 @@ }

// ================================================================================================
function validateSecurityOptions(options, maxConstraintDegree) {
function validateSecurityOptions(options, extensionFactor) {
// execution trace spot checks

@@ -302,5 +305,4 @@ const exeQueryCount = (options ? options.exeQueryCount : undefined) || DEFAULT_EXE_QUERY_COUNT;

// extension factor
let extensionFactor = (options ? options.extensionFactor : undefined);
if (!extensionFactor) {
extensionFactor = 2 ** (Math.ceil(Math.log2(maxConstraintDegree)) + 1);
throw new TypeError(`Extension factor is undefined`);
}

@@ -307,0 +309,0 @@ return { extensionFactor, exeQueryCount, friQueryCount, hashAlgorithm };

6

lib/utils/sizeof.js

@@ -32,3 +32,7 @@ "use strict";

size += ldProof;
return { evProof, ldProof: { lcProof, levels: ldLevels, total: ldProof }, total: size };
// trace shape
let traceShape = 1; // trace depth
traceShape += proof.traceShape.length * 4;
size += traceShape;
return { evProof, ldProof: { lcProof, levels: ldLevels, total: ldProof }, traceShape, total: size };
}

@@ -35,0 +39,0 @@ exports.sizeOf = sizeOf;

4

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

@@ -30,3 +30,3 @@ "main": "index.js",

"dependencies": {
"@guildofweavers/air-script": "0.4.x",
"@guildofweavers/air-script": "0.5.x",
"@guildofweavers/galois": "0.4.x",

@@ -33,0 +33,0 @@ "@guildofweavers/merkle": "0.3.x"

114

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 specific "business logic" of your computations.
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 your computations.

@@ -26,4 +26,7 @@ ### Background

// define transition function
transition 1 register in 64 steps {
out: $r0 + 2;
transition 1 register {
for each ($i0) {
init { $i0 }
for steps [1..63] { $r0 + 2 }
}
}

@@ -33,3 +36,3 @@

enforce 1 constraint {
out: $n0 - ($r0 + 2);
for all steps { transition($r) = $n }
}

@@ -43,3 +46,3 @@ }`);

];
const proof = fooStark.prove(assertions, [1n]);
const proof = fooStark.prove(assertions, [[1n]]);

@@ -60,15 +63,15 @@ // verify that if we start at 1 and run the computation for 64 steps, we get 127

Starting STARK computation
Set up evaluation context in 10 ms
Generated execution trace in 39 ms
Set up evaluation context in 146 ms
Generated execution trace in 52 ms
Computed execution trace polynomials P(x) in 7 ms
Low-degree extended P(x) polynomials over evaluation domain in 92 ms
Serialized evaluations of P(x) and S(x) polynomials in 83 ms
Built evaluation merkle tree in 85 ms
Computed 40 evaluation spot checks in 4 ms
Computed composition polynomial C(x) in 496 ms
Combined P(x) and S(x) evaluations with C(x) evaluations in 42 ms
Computed low-degree proof in 314 ms
STARK computed in 1175 ms
Low-degree extended P(x) polynomials over evaluation domain in 83 ms
Serialized evaluations of P(x) and S(x) polynomials in 92 ms
Built evaluation merkle tree in 87 ms
Computed composition polynomial C(x) in 574 ms
Combined P(x) and S(x) evaluations with C(x) evaluations in 50 ms
Computed low-degree proof in 231 ms
Computed 48 evaluation spot checks in 2 ms
STARK computed in 1327 ms
--------------------
Proof serialized in 7 ms; size: 86.12 KB
Proof serialized in 8 ms; size: 94.58 KB
--------------------

@@ -78,9 +81,9 @@ Proof parsed in 6 ms

Starting STARK verification
Set up evaluation context in 2 ms
Set up evaluation context in 9 ms
Computed positions for evaluation spot checks in 1 ms
Decoded evaluation spot checks in 0 ms
Verified evaluation merkle proof in 3 ms
Verified transition and boundary constraints in 10 ms
Verified low-degree proof in 16 ms
STARK verified in 36 ms
Decoded evaluation spot checks in 1 ms
Verified evaluation merkle proof in 4 ms
Verified transition and boundary constraints in 52 ms
Verified low-degree proof in 14 ms
STARK verified in 85 ms
--------------------

@@ -140,14 +143,21 @@ STARK security level: 96

| assertions | An array of [Assertion](#Assertions) objects (also called boundary constraints). These assertions specify register values at specific steps of a valid computation. At least 1 assertion must be provided. |
| initValues | An array of `BigInt`'s containing initial values for all mutable registers. |
| publicInputs? | An array containing values for all specified public registers. This parameter is optional and can be skipped if no public input registers have been defined. |
| secretInputs? | An array containing values for all specified secret registers. This parameter is optional and can be skipped if no secret input registers have been defined. |
| inputs | An array containing initialization values for all `$i` registers. Must contain at least one set of values. |
| auxPublicInputs? | An array containing initialization values for all `$p` registers. This parameter is optional and can be skipped if no public auxiliary inputs have been defined. |
| auxSecretInputs? | An array containing initialization values for all `$s` registers. This parameter is optional and can be skipped if no secret auxiliary inputs have been defined. |
### Initial values and inputs
Handling of initial values and inputs deserves a bit more explanation. As described above, there are 3 ways to supply inputs to `STARK.prove()` method:
### Inputs
Handling of inputs deserves a bit more explanation. As described above, there are 3 ways to supply inputs to `STARK.prove()` method:
* `initValues` parameter is always required. It is basically used to define step 0 or the execution trace. Thus, the number of values provided must match the number of mutable registers in the STARK.
* The other two parameters provide values for the input registers defined in the STARK. To learn more about these, refer to [Readonly registers](https://github.com/GuildOfWeavers/AirScript#readonly-registers) section of AirScript documentation. These parameters are required only if STARK's definition includes input registers.
* `inputs` parameter is always required. It is used to initialize the execution trace for different instances of the computation. The structure of `inputs` must match the structure of input loops defined in transition function. For more information, see [Input loops](https://github.com/GuildOfWeavers/AirScript#input-loops) section of AirScript documentation.
* The other two parameters provide values for the input registers defined in the STARK. To learn more about these, refer to [Readonly registers](https://github.com/GuildOfWeavers/AirScript#readonly-registers) section of AirScript documentation. These parameters are required only if STARK's definition includes auxiliary input registers.
For example, the fragment below specifies that a STARK must have 3 readonly registers, but that the values for these registers are not available at the STARK's definition time (the `[...]` indicate that the values will be provided later):
For example, the fragment below specifies that a STARK must have a single `$i` register of depth 0, and 3 auxiliary input registers. Moreover, prefixes `$p` and `$s` specify that 2 of the auxiliary registers are *public* (the values will be known to the prover **and** the verified), and 1 of the registers is *secret* (the values will be known **only** to the prover).
```
transition 1 register {
for each ($i0) {
init { $i0 }
for steps [1..63] { $r0 + 2 }
}
}
using 3 readonly registers {

@@ -159,21 +169,20 @@ $p0: repeat [...];

```
Moreover, by using prefixes `$p` and `$s` it also specifies that 2 of the registers are *public* (the values will be known to the prover **and** the verified), and 1 of the registers is *secret* (the values will be known **only** to the prover).
So, based on this definition, the parameters for `STARK.prove()` method should be supplied like so:
Based on this definition, the parameters for `STARK.prove()` method should be supplied like so:
```TypeScript
// let's say we have 2 mutable registers
let initValues = [1n, 2n];
// let's say we want to run the computation for 2 sets of inputs
let inputs = [[1n], [2n]];
// define values for public input registers
// define values for public auxiliary inputs
let pValues1 = [1n, 2n, 3n, 4n];
let pValues2 = [1n, 2n, 3n, 4n, 5n, 6n, 7n, 7n];
// define values for secret input registers
// define values for secret auxiliary inputs
let sValues = [10n, 11n, 12n, 13n];
// generate the proof
let proof = fooStark.prove(assertions, initValues, [pValues1, pValues2], [sValues]);
let proof = fooStark.prove(assertions, inputs, [pValues1, pValues2], [sValues]);
```
When the proof is generated, the provided values will "appear" in registers `$p0`, `$p1`, and `$s0` to be used in transition function and transition constraints. The rules for how this happens are also described in the [Readonly registers](https://github.com/GuildOfWeavers/AirScript#readonly-registers) section of AirScript documentation.
When the proof is generated, the provided values will "appear" in registers `$i0`, `$p0`, `$p1`, and `$s0` to be used in transition function and transition constraints. The rules for how this happens are also described in the [Input loops](https://github.com/GuildOfWeavers/AirScript#input-loops) and [Readonly registers](https://github.com/GuildOfWeavers/AirScript#readonly-registers) sections of AirScript documentation.

@@ -185,3 +194,3 @@

```TypeScript
const result = myStark.verify(assertions, proof, publicInputs?);
const result = myStark.verify(assertions, proof, auxPublicInputs?);
```

@@ -194,7 +203,7 @@ The meaning of the parameters is as follows:

| proof | The proof object that was generated by the `prove()` method. |
| publicInputs? | An array containing values for all specified public registers. This parameter is optional and can be skipped if no public input registers have been defined. |
| auxPublicInputs? | An array containing initialization values for all `$p` registers. This parameter is optional and can be skipped if no public auxiliary inputs have been defined. |
Verifying a proof basically attests to something like this:
>If you start with some set of initial values (known to the prover), and run the computation for the specified number of steps, the execution trace generated by the computation will satisfy the specified assertions.
>If you start with some set of inputs (known to the prover), and run the computation for the specified number of steps, the execution trace generated by the computation will satisfy the specified assertions.

@@ -217,10 +226,10 @@ ## Assertions

| ----------------------------- | :--------: | :----: | :-------: | :------------: | :--------: | :--------: |
| MiMC | 128 bits | 3 | 1 | 2<sup>13</sup> | 1.2 sec | 86 KB |
| MiMC | 128 bits | 3 | 1 | 2<sup>17</sup> | 19 sec | 137 KB |
| MiMC | 256 bits | 3 | 1 | 2<sup>13</sup> | 9.2 sec | 107 KB |
| MiMC | 256 bits | 3 | 1 | 2<sup>17</sup> | 178 sec | 162 KB |
| Merkle Proof (Rescue, d=8) | 128 bits | 4 | 8 | 2<sup>8</sup> | 530 ms | 53 KB |
| Merkle Proof (Rescue, d=16) | 128 bits | 4 | 8 | 2<sup>9</sup> | 1.1 sec | 63 KB |
| Merkle Proof (Poseidon, d=8) | 128 bits | 7 | 12 | 2<sup>9</sup> | 1.3 sec | 74 KB |
| Merkle Proof (Poseidon, d=16) | 128 bits | 7 | 12 | 2<sup>10</sup> | 2.6 sec | 82 KB |
| MiMC | 128 bits | 3 | 1 | 2<sup>13</sup> | 1.3 sec | 95 KB |
| MiMC | 128 bits | 3 | 1 | 2<sup>17</sup> | 23 sec | 147 KB |
| MiMC | 256 bits | 3 | 1 | 2<sup>13</sup> | 11.5 sec | 108 KB |
| MiMC | 256 bits | 3 | 1 | 2<sup>17</sup> | 230 sec | 165 KB |
| Merkle Proof (Rescue, d=8) | 128 bits | 5 | 8 | 2<sup>8</sup> | 300 ms | 60 KB |
| Merkle Proof (Rescue, d=16) | 128 bits | 5 | 8 | 2<sup>9</sup> | 600 ms | 72 KB |
| Merkle Proof (Poseidon, d=8) | 128 bits | 8 | 12 | 2<sup>9</sup> | 900 ms | 74 KB |
| Merkle Proof (Poseidon, d=16) | 128 bits | 8 | 12 | 2<sup>10</sup> | 1.8 sec | 84 KB |

@@ -234,3 +243,3 @@ STARKs in the above examples have security parameters set to provide ~96 bits security.

# References
This library is largely based on Vitalik Buterin's [zk-STARK/MiMC tutorial](https://github.com/ethereum/research/tree/master/mimc_stark). Other super useful resources:
This library is originally based on Vitalik Buterin's [zk-STARK/MiMC tutorial](https://github.com/ethereum/research/tree/master/mimc_stark). Other super useful resources:

@@ -251,3 +260,8 @@ * STARKs whitepaper: [Scalable, transparent, and post-quantum secure computational integrity](https://eprint.iacr.org/2018/046.pdf)

Other STARK libraries:
* [Hodor](https://github.com/matter-labs/hodor) from Matter Labs.
* [OpenZKP](https://github.com/0xProject/OpenZKP) from 0xProject.
# License
[MIT](/LICENSE) © 2019 Guild of Weavers
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