New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.Learn More →
@guildofweavers/genstark
Advanced tools
@guildofweavers/genstark - npm Package Compare versions
Comparing version 0.2.0 to 0.3.0
@@ -13,8 +13,4 @@ "use strict"; | ||
| field: new index_1.PrimeField(96769n), | ||
| tExpressions: { | ||
| 'n0': 'r0 + 1 + k0 + 2 * k1' | ||
| }, | ||
| tConstraints: [ | ||
| 'n0 - (r0 + 1 + k0 + 2 * k1)' | ||
| ], | ||
| tFunction: 'out: $r0 + 1 + $k0 + 2 * $k1', | ||
| tConstraints: 'out: $n0 - ($r0 + 1 + $k0 + 2 * $k1)', | ||
| tConstraintDegree: 1, | ||
@@ -21,0 +17,0 @@ constants: [{ |
@@ -15,10 +15,10 @@ "use strict"; | ||
| 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)' | ||
| ], | ||
| tFunction: ` | ||
| a0: $r0 + $r1; | ||
| out: [a0, a0 + $r1]; | ||
| `, | ||
| tConstraints: ` | ||
| a0: $r0 + $r1; | ||
| out: [$n0 - a0, $n1 - (a0 + $r1)]; | ||
| `, | ||
| tConstraintDegree: 1 // max degree of our constraints is 1 | ||
@@ -25,0 +25,0 @@ }); |
@@ -17,8 +17,4 @@ "use strict"; | ||
| field: new index_1.PrimeField(2n ** 256n - 351n * 2n ** 32n + 1n), | ||
| tExpressions: { | ||
| 'n0': 'r0^3 + k0' | ||
| }, | ||
| tConstraints: [ | ||
| 'n0 - (r0^3 + k0)' | ||
| ], | ||
| tFunction: 'out: $r0^3 + $k0', | ||
| tConstraints: 'out: $n0 - ($r0^3 + $k0)', | ||
| tConstraintDegree: 3, | ||
@@ -25,0 +21,0 @@ constants: [{ |
@@ -19,7 +19,7 @@ declare module '@guildofweavers/genstark' { | ||
| /** A set of transition expressions for all mutable registers */ | ||
| tExpressions: { [register: string]: string }; | ||
| /** An arithmetic script defining state transition function for the computation */ | ||
| tFunction: string; | ||
| /** A list of transition constraints for the computation */ | ||
| tConstraints: string[]; | ||
| /** An arithmetic script defining transition constraint for the computation */ | ||
| tConstraints: string; | ||
@@ -124,2 +124,9 @@ /** Maximum degree of transition constraints */ | ||
| // UTILITIES | ||
| // -------------------------------------------------------------------------------------------- | ||
| export const inline: { | ||
| vector(v: bigint[]): string; | ||
| matrix(m: bigint[][]): string; | ||
| }; | ||
| // INTERNAL | ||
@@ -126,0 +133,0 @@ // -------------------------------------------------------------------------------------------- |
@@ -7,2 +7,4 @@ "use strict"; | ||
| exports.Stark = Stark_1.Stark; | ||
| var utils_1 = require("./lib/utils"); | ||
| exports.inline = utils_1.inline; | ||
| var merkle_1 = require("@guildofweavers/merkle"); | ||
@@ -9,0 +11,0 @@ exports.MerkleTree = merkle_1.MerkleTree; |
| "use strict"; | ||
| Object.defineProperty(exports, "__esModule", { value: true }); | ||
| const expressions_1 = require("./expressions"); | ||
| const script_1 = require("./script"); | ||
| const utils_1 = require("./utils"); | ||
@@ -78,29 +78,36 @@ // MODULE VARIABLES | ||
| // transition function | ||
| if (!config.tExpressions) | ||
| throw new TypeError('Transition function was not provided'); | ||
| const tExpressions = new Map(Object.entries(config.tExpressions)); | ||
| const registerCount = tExpressions.size; | ||
| if (registerCount === 0) { | ||
| throw new TypeError('At least one register must be defined in transition function'); | ||
| if (!config.tFunction) | ||
| throw new TypeError('Transition function script was not provided'); | ||
| if (typeof config.tFunction !== 'string') | ||
| throw new TypeError('Transition function script must be a string'); | ||
| let tFunction, registerCount; | ||
| try { | ||
| const tFunctionScript = new script_1.Script(config.tFunction, constantCount); | ||
| registerCount = tFunctionScript.outputWidth; | ||
| if (registerCount > MAX_REGISTER_COUNT) { | ||
| throw new TypeError(`Number of state registers cannot exceed ${MAX_REGISTER_COUNT}`); | ||
| } | ||
| tFunction = buildTransitionFunction(tFunctionScript); | ||
| } | ||
| if (registerCount > MAX_REGISTER_COUNT) { | ||
| throw new TypeError(`Number of state registers cannot exceed ${MAX_REGISTER_COUNT}`); | ||
| catch (error) { | ||
| throw new Error(`Failed to build transition function: ${error.message}`); | ||
| } | ||
| const tFunction = buildTransitionFunction(tExpressions, constantCount); | ||
| // transition constraints | ||
| if (!config.tConstraints) | ||
| throw new TypeError('Transition constraints array was not provided'); | ||
| const cExpressions = config.tConstraints; | ||
| if (Array.isArray(!cExpressions)) { | ||
| throw new TypeError('Transition constraints must be provided as an array'); | ||
| throw new TypeError('Transition constraints script was not provided'); | ||
| if (typeof config.tConstraints !== 'string') | ||
| throw new TypeError('Transition constraints script must be a string'); | ||
| let tBatchConstraintEvaluator, tConstraintEvaluator, constraintCount; | ||
| try { | ||
| const tConstraintsScript = new script_1.Script(config.tConstraints, constantCount, registerCount); | ||
| constraintCount = tConstraintsScript.outputWidth; | ||
| if (constraintCount > MAX_CONSTRAINT_COUNT) { | ||
| throw new TypeError(`Number of transition constraints cannot exceed ${MAX_CONSTRAINT_COUNT}`); | ||
| } | ||
| tBatchConstraintEvaluator = buildBatchConstraintEvaluator(tConstraintsScript); | ||
| tConstraintEvaluator = buildConstraintEvaluator(tConstraintsScript); | ||
| } | ||
| const constraintCount = cExpressions.length; | ||
| if (constraintCount === 0) | ||
| throw new TypeError('Transition constraints array was empty'); | ||
| if (constraintCount > MAX_CONSTRAINT_COUNT) { | ||
| throw new TypeError(`Number of transition constraints cannot exceed ${MAX_CONSTRAINT_COUNT}`); | ||
| catch (error) { | ||
| throw new Error(`Failed to build transition constraints script: ${error.message}`); | ||
| } | ||
| const tConstraints = parseTransitionConstraints(cExpressions, registerCount, constantCount); | ||
| const tBatchConstraintEvaluator = buildBatchConstraintEvaluator(tConstraints); | ||
| const tConstraintEvaluator = buildConstraintEvaluator(tConstraints); | ||
| // execution trace spot checks | ||
@@ -141,95 +148,60 @@ const exeSpotCheckCount = config.exeSpotCheckCount || DEFAULT_EXE_SPOT_CHECK_COUNT; | ||
| // ================================================================================================ | ||
| function buildTransitionFunction(expressions, constantCount) { | ||
| const registerCount = expressions.size; | ||
| function buildTransitionFunction(script) { | ||
| const registerCount = script.outputWidth; | ||
| const assignments = new Array(registerCount); | ||
| const regRefBuilder = function (name, index) { | ||
| if (name === 'n') { | ||
| throw new Error('Transition expression cannot read next register state'); | ||
| if (name === '$n') { | ||
| throw new Error('Transition function script cannot reference future register states'); | ||
| } | ||
| else if (name === 'r') { | ||
| return `r[${index}][i]`; | ||
| else if (name === '$r') { | ||
| return `$r[${index}][$i]`; | ||
| } | ||
| else if (name === 'k') { | ||
| return `k[${index}].getValue(i, true)`; | ||
| else if (name === '$k') { | ||
| return `$k[${index}].getValue($i, true)`; | ||
| } | ||
| throw new Error(`Register reference '${name}${index}' is invalid`); | ||
| }; | ||
| let i = 0; | ||
| try { | ||
| for (; i < registerCount; i++) { | ||
| let expression = expressions.get(`n${i}`); | ||
| if (!expression) | ||
| throw new Error('transition expression is undefined'); | ||
| let ast = expressions_1.parseExpression(expression, registerCount, constantCount); | ||
| assignments[i] = `r[${i}][i+1] = ${ast.toCode(regRefBuilder)}`; | ||
| } | ||
| const scriptCode = script.toCode(regRefBuilder); | ||
| for (let i = 0; i < registerCount; i++) { | ||
| assignments[i] = `$r[${i}][$i+1] = ${script.outputVariableName}[${i}]`; | ||
| } | ||
| catch (error) { | ||
| throw new Error(`Failed to build transition expression for register n${i}: ${error.message}`); | ||
| } | ||
| const cBody = ` throw new Error('Error in transition function at step ' + i + ':' + error.message);`; | ||
| const lBody = ` for (; i < steps - 1; i++) {\n ${assignments.join(';\n')};\n }`; | ||
| const fBody = `let i = 0;\ntry {\n${lBody}\n}\ncatch(error){\n${cBody}\n}`; | ||
| return new Function('r', 'k', 'steps', 'field', fBody); | ||
| const cBody = `throw new Error('Error in transition function at step ' + $i + ':' + error.message);`; | ||
| const lBody = `for (; $i < $steps - 1; $i++) {\n${scriptCode}\n${assignments.join(';\n')};\n}`; | ||
| const fBody = `let $i = 0;\ntry {\n${lBody}\n}\ncatch(error){\n${cBody}\n}`; | ||
| return new Function('$r', '$k', '$steps', '$field', fBody); | ||
| } | ||
| function parseTransitionConstraints(expressions, registerCount, constantCount) { | ||
| const constraintCount = expressions.length; | ||
| const output = new Array(constraintCount); | ||
| let i = 0; | ||
| try { | ||
| for (; i < constraintCount; i++) { | ||
| let expression = expressions[i]; | ||
| if (!expression) | ||
| throw new Error('transition constraint is undefined'); | ||
| output[i] = expressions_1.parseExpression(expression, registerCount, constantCount); | ||
| } | ||
| } | ||
| catch (error) { | ||
| throw new Error(`Failed to parse transition constraint ${i}: ${error.message}`); | ||
| } | ||
| return output; | ||
| } | ||
| function buildBatchConstraintEvaluator(expressions) { | ||
| const constraintCount = expressions.length; | ||
| function buildBatchConstraintEvaluator(script) { | ||
| const constraintCount = script.outputWidth; | ||
| const assignments = new Array(constraintCount); | ||
| const validators = new Array(constraintCount); | ||
| const regRefBuilder = function (name, index) { | ||
| if (name === 'n') { | ||
| return `r[${index}][(i + skip) % steps]`; | ||
| if (name === '$n') { | ||
| return `$r[${index}][($i + $skip) % $steps]`; | ||
| } | ||
| else if (name === 'r') { | ||
| return `r[${index}][i]`; | ||
| else if (name === '$r') { | ||
| return `$r[${index}][$i]`; | ||
| } | ||
| else if (name === 'k') { | ||
| return `k[${index}].getValue(i, false)`; | ||
| else if (name === '$k') { | ||
| return `$k[${index}].getValue($i, false)`; | ||
| } | ||
| throw new Error(`Register reference '${name}${index}' is invalid`); | ||
| }; | ||
| let i = 0; | ||
| try { | ||
| for (; i < constraintCount; i++) { | ||
| assignments[i] = `q[${i}][i] = ${expressions[i].toCode(regRefBuilder)}`; | ||
| validators[i] = `if (q[${i}][i] !== 0n) throw new Error('Constraint ' + ${i} + ' didn\\'t evaluate to 0 at step: ' + (i/skip));`; | ||
| } | ||
| const scriptCode = script.toCode(regRefBuilder); | ||
| for (let i = 0; i < constraintCount; i++) { | ||
| assignments[i] = `$q[${i}][$i] = ${script.outputVariableName}[${i}]`; | ||
| validators[i] = `if ($q[${i}][$i] !== 0n) throw new Error('Constraint ' + ${i} + ' didn\\'t evaluate to 0 at step: ' + ($i/$skip));`; | ||
| } | ||
| catch (error) { | ||
| throw new Error(`Failed to build transition constraint ${i}: ${error.message}`); | ||
| } | ||
| const cBody = ` if (i < nfSteps && i % skip === 0) {\n ${validators.join(';\n')}\n }`; | ||
| const lBody = ` ${assignments.join(';\n')};\n${cBody}`; | ||
| const fBody = `const nfSteps = steps - skip;\nfor (let i = 0; i < steps; i++) {\n${lBody}\n}`; | ||
| return new Function('q', 'r', 'k', 'steps', 'skip', 'field', fBody); | ||
| const cBody = `if ($i < $nfSteps && $i % $skip === 0) {\n${validators.join(';\n')}\n}`; | ||
| const lBody = `${scriptCode}\n${assignments.join(';\n')};\n${cBody}`; | ||
| const fBody = `const $nfSteps = $steps - $skip;\nfor (let $i = 0; $i < $steps; $i++) {\n${lBody}\n}`; | ||
| return new Function('$q', '$r', '$k', '$steps', '$skip', '$field', fBody); | ||
| } | ||
| function buildConstraintEvaluator(expressions) { | ||
| const constraintCount = expressions.length; | ||
| function buildConstraintEvaluator(script) { | ||
| const regRefBuilder = function (name, index) { | ||
| return `${name}[${index}]`; | ||
| }; | ||
| const assignments = new Array(constraintCount); | ||
| for (let i = 0; i < constraintCount; i++) { | ||
| assignments[i] = `q[${i}] = ${expressions[i].toCode(regRefBuilder)};`; | ||
| } | ||
| const body = `const q = new Array(${constraintCount});\n${assignments.join('\n')}\nreturn q;`; | ||
| return new Function('r', 'n', 'k', 'field', body); | ||
| const scriptCode = script.toCode(regRefBuilder); | ||
| const body = `${scriptCode}\nreturn ${script.outputVariableName};`; | ||
| return new Function('$r', '$n', '$k', '$field', body); | ||
| } | ||
| //# sourceMappingURL=config.js.map |
@@ -261,10 +261,24 @@ "use strict"; | ||
| }; | ||
| if (!merkle_1.MerkleTree.verifyBatch(eRoot, augmentedPositions, eProof, this.hashAlgorithm)) { | ||
| throw new StarkError_1.StarkError(`Verification of evaluation Merkle proof failed`); | ||
| try { | ||
| if (!merkle_1.MerkleTree.verifyBatch(eRoot, augmentedPositions, eProof, this.hashAlgorithm)) { | ||
| throw new StarkError_1.StarkError(`Verification of evaluation Merkle proof failed`); | ||
| } | ||
| } | ||
| catch (error) { | ||
| if (error instanceof StarkError_1.StarkError === false) { | ||
| throw new StarkError_1.StarkError(`Verification of evaluation Merkle proof failed`, error); | ||
| } | ||
| } | ||
| this.logger.log(label, `Verified evaluation merkle proof`); | ||
| // 5 ----- verify linear combination proof | ||
| if (!merkle_1.MerkleTree.verifyBatch(proof.degree.root, positions, proof.degree.lcProof, this.hashAlgorithm)) { | ||
| throw new StarkError_1.StarkError(`Verification of linear combination Merkle proof failed`); | ||
| try { | ||
| if (!merkle_1.MerkleTree.verifyBatch(proof.degree.root, positions, proof.degree.lcProof, this.hashAlgorithm)) { | ||
| throw new StarkError_1.StarkError(`Verification of linear combination Merkle proof failed`); | ||
| } | ||
| } | ||
| catch (error) { | ||
| if (error instanceof StarkError_1.StarkError === false) { | ||
| throw new StarkError_1.StarkError(`Verification of linear combination Merkle proof failed`, error); | ||
| } | ||
| } | ||
| const lEvaluations = new Map(); | ||
@@ -271,0 +285,0 @@ const lEvaluationValues = utils_1.buffersToBigInts(proof.degree.lcProof.values); |
@@ -6,2 +6,3 @@ "use strict"; | ||
| const crypto = require("crypto"); | ||
| const inliners = require("./inliners"); | ||
| // RE-EXPORTS | ||
@@ -20,2 +21,3 @@ // ================================================================================================ | ||
| exports.Logger = Logger_1.Logger; | ||
| exports.inline = inliners; | ||
| // PUBLIC FUNCTIONS | ||
@@ -22,0 +24,0 @@ // ================================================================================================ |
| { | ||
| "name": "@guildofweavers/genstark", | ||
| "version": "0.2.0", | ||
| "version": "0.3.0", | ||
| "description": "zk-STARK generation library", | ||
@@ -26,9 +26,9 @@ "main": "index.js", | ||
| "@types/node": "12.0.x", | ||
| "del": "4.0.x", | ||
| "del": "4.1.x", | ||
| "gulp": "4.0.x" | ||
| }, | ||
| "dependencies": { | ||
| "@guildofweavers/galois": "0.1.x", | ||
| "@guildofweavers/galois": "0.2.x", | ||
| "@guildofweavers/merkle": "0.1.x" | ||
| } | ||
| } |
168
README.md
@@ -24,5 +24,5 @@ # genSTARK | ||
| field : new PrimeField(2n**32n - 3n * 2n**25n + 1n), | ||
| tExpressions : { 'n0': 'r0 + 2' }, // define transition function | ||
| tConstraints : ['n0 - (r0 + 2)'], // define transition constraints | ||
| tConstraintDegree : 1 // degree of our constraint is 1 | ||
| tFunction : 'out: $r0 + 2;', // define transition function | ||
| tConstraints : 'out: $n0 - ($r0 + 2);', // define transition constraints | ||
| tConstraintDegree : 1 // degree of our constraint is 1 | ||
| }); | ||
@@ -43,5 +43,6 @@ | ||
| There are a few more sophisticated examples in this repository: | ||
| * [Demo STARK](/examples/demo.ts) - demonstration of how to use readonly registers. | ||
| * [Fibonacci STARK](/examples/fibonacci.ts) - proofs of computation for [Fibonacci numbers](https://en.wikipedia.org/wiki/Fibonacci_number). | ||
| * [MiMC STARK](/examples/mimc.ts) - basically the same as Vitalik Buterin's [MiMC tutorial](https://vitalik.ca/general/2018/07/21/starks_part_3.html). | ||
| * [Fibonacci STARK](/examples/fibonacci.ts) - proofs of computation for [Fibonacci numbers](https://en.wikipedia.org/wiki/Fibonacci_number). | ||
| * [Demo STARK](/examples/demo.ts) - demonstration of how to use readonly registers. | ||
| * [Rescue STARK](/examples/rescue) - proof of knowledge of hash preimage of [Rescue](https://eprint.iacr.org/2019/426.pdf) hash function. | ||
@@ -66,3 +67,3 @@ When you run the examples, you should get a nice log documenting each step. Here is an example output of running MiMC STARK for 2<sup>13</sup> steps: | ||
| -------------------- | ||
| Proof serialized in 3 ms; size: 229.25 KB | ||
| Proof serialized in 3 ms; size: 220.04 KB | ||
| -------------------- | ||
@@ -99,4 +100,4 @@ Proof parsed in 8 ms | ||
| | 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). | | ||
| | 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. | | ||
| | tFunction | An arithmetic script defining state [transition function](#Transition-function) for the computation. | | ||
| | tConstraints | An arithmetic script defining [transition constraint](#Transition-constraints) for the computation. | | ||
| | tConstraintDegree | The highest algebraic degree of the provided transition constraints. | | ||
@@ -120,5 +121,4 @@ | 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. | | ||
| | steps | Number of steps in the computation. Number of steps must be a power of 2. | | ||
| | 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. | | ||
| | inputs | An array of `BigInt`'s containing initial values for all mutable registers. The length of the array must be the same as the width of the vector returned by the [transition function](#Transition-function) script. | | ||
| Once you've generated a proof, you can verify it using `Stark.verify()` method like so: | ||
@@ -144,32 +144,22 @@ | ||
| ## Transition function | ||
| 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 | ||
| { | ||
| 'n0': 'r0 + k0 + 1' | ||
| } | ||
| A core component of STARK's definition is the state transition function. You can define a state transition function by providing an [arithmetic script](#Arithmetic-script) which evaluates to the next state of the computation. For example: | ||
| ``` | ||
| The above example defines a transition expression for a single register. Here is how to interpret it: | ||
| out: $r0 + $k0 + 1; | ||
| ``` | ||
| This script says: the next value of mutable register `$r0` is equal to the current value of the register, plus the current value of readonly register `$k0`, plus 1. | ||
| * `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. | ||
| If your computation involves more than 1 mutable register, your script should return a vector with values for the next state of all registers. Here is an example: | ||
| ``` | ||
| a0: $r0 + $r1; | ||
| a1: a0 + $r1; | ||
| out: [a0, a1]; | ||
| ``` | ||
| The above example describes a state transition function that operates over 2 registers: | ||
| 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. | ||
| * The next value of register 0 is set to the sum of the current values of both registers; | ||
| * The next value of register 1 is set to the same sum plus current value of register 1 again. | ||
| 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. | ||
| (this is actually a somewhat convoluted way to describe a transition function for a Fibonacci sequence). | ||
| One thing to note, you cannot reference future register states within a transition expression. So, something like this would not be valid: | ||
| ```TypeScript | ||
| { | ||
| 'n0': 'r0 + 1', | ||
| 'n1': 'n0 * 2' | ||
| } | ||
| ``` | ||
| But you can easily redefine this as a valid expression like so: | ||
| ```TypeScript | ||
| { | ||
| 'n0': 'r0 + 1', | ||
| 'n1': '(r0 + 1) * 2' | ||
| } | ||
| ``` | ||
| In general, the length of the vector in the `out` statement defines the width of the state (i.e. number of mutable registers). | ||
@@ -179,12 +169,106 @@ ## Transition constraints | ||
| Similarly to transition function, a transition constraint is defined using algebraic expressions like so: | ||
| ```TypeScript | ||
| [ | ||
| `n0 - (r0 + k0 + 1)` | ||
| ] | ||
| Similarly to transition functions, transition constraints are defined by an [arithmetic script](#Arithmetic-script). However, unlike scripts for transition functions, scripts for transition constraints can reference future states of mutable registers. For example: | ||
| ``` | ||
| However, unlike transition function, transition constraints can reference future states of mutable registers. | ||
| out: $n0 - ($r0 + $k0 + 1); | ||
| ``` | ||
| where `$n0` contains value of register `$r0` at the next step of computation. | ||
| If you are working with more than one constraint, your transition script should return a vector with evaluations for all of your constraints. For example: | ||
| ``` | ||
| a0: $r0 + $r1; | ||
| out: [$n0 - a0, $n1 - ($r1 + a0)]; | ||
| ``` | ||
| (these are constraints matching the Fibonacci transition function described previously). | ||
| **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. | ||
| ## Arithmetic script | ||
| If your transition functions and constraints are fairly complex, it will get extremely tedious (and error prone) to write them all out individually. But fear not, arithmetic script is here to help. | ||
| An arithmetic script is nothing more than a series of arithmetic statements (separated by semicolons) which evaluate to a number or to a vector of numbers. Here is an example: | ||
| ``` | ||
| a0: $r0 + $r1; | ||
| a1: $k0 * a0; | ||
| out: [a0, a1]; | ||
| ``` | ||
| Here is what this means: | ||
| * Define variable `a0` to be the sum of values from *mutable* registers `$r0` and `$r1`. | ||
| * Define variable `a1` to be the product of value from *readonly* register `$k0` and variable `a0`. | ||
| * Set the return value of the script to a vector of two elements with values of `a0` and `a1` being first and second elements respectively. | ||
| Every statement of an arithmetic script is an *assignment* statement. It assigns a value of an expression (the right side) to a variable (left side). Every script must terminate with an `out` statement which defines the return value of the script. | ||
| Within the script you can reference registers, constants, variables, and perform arithmetic operations with them. All of this is described below. | ||
| ### Registers | ||
| A computation's execution trace consists of a series of state transitions. A state of a computation at a given step is held in an array of registers. There are two types of registers: | ||
| * **mutable** registers - values in these registers are defined by the state [transition function](#Transition-function). Currently, you can have up to 64 mutable registers. | ||
| * **readonly** registers - values in these registers are defined by the [constant definitions](#Constants). Currently, you can have up to 64 readonly registers. | ||
| To reference a given register you need to specify the name of the register bank and the index of the register within that bank. Names of all register banks start with `$` - so, register references can look like this: `$r1`, `$k23`, `$n11` etc. Currently, there are 3 register banks: | ||
| * **$r** bank holds values of *mutable* registers for the current step of the computation. | ||
| * **$n** bank holds values of *mutable* registers for the next step of the computation. This bank can be referenced only in transition constraints script (not in the transition function script). | ||
| * **$k** bank holds values of *readonly* registers for the current step of the computation. | ||
| ### Variables | ||
| To simplify your scripts you can aggregate common computations into variables. Once a variable is defined, it can be used in all subsequent statements. You can also change the value of a variable by re-assigning to it. For example, something like this is perfectly valid: | ||
| ``` | ||
| a0: $r0 + 1; | ||
| a0: a0 + $r1; | ||
| out: a0; | ||
| ``` | ||
| Variable can be of 3 different types: ***scalars***, ***vectors***, and ***matrixes***. | ||
| #### Scalars | ||
| A variable that holds a simple numerical value is a scalar. Implicitly, all registers hold scalar values. All constant literals are also scalars. A name of scalar variable can include lower-case letters, numbers, and underscores (and must start with a letter). Here are a few examples: | ||
| ``` | ||
| a0: 1; | ||
| foo: $r0; | ||
| foo_bar: $r0 + 1; | ||
| ``` | ||
| #### Vectors | ||
| Two or more scalars can be aggregated into a vector (a vector is just a 1-dimensional array). You can define a vector by putting a comma-separated list of scalars between square brackets. A name of a vector variable can include upper-case letters, numbers, and underscores (and must start with a letter). Here are a few examples: | ||
| ``` | ||
| V0: [1, 2]; | ||
| FOO: [$r0, $r1]; | ||
| FOO_BAR: [$r0, $r1 + 1, $k0]; | ||
| ``` | ||
| #### Matrixes | ||
| A matrix is a 2-dimensional array of scalars with at least 1 row and 2 columns. Similarly to vectors, matrix variable names can include upper-case letters, numbers, and underscores. You can define a matrix by listing its elements in a row-major form. Here are a few examples: | ||
| ``` | ||
| M0: [[1, 2], [1, 2]]; | ||
| FOO: [[$k0, $r0, 1], [$r1 + $r2, 42, $r3 * 8]]; | ||
| ``` | ||
| ### Operations | ||
| To do something useful with registers, variables etc. you can apply arithmetic operations to them. These operations are `+`, `-`, `*`, `/`, `^`. | ||
| When you work with scalar values, these operations behave as you've been taught in the elementary school (though, the math takes place in a finite field). But you can also apply these operations to vectors and matrixes. In such cases, these are treated as **element-wise** operations. Here are a few examples: | ||
| ``` | ||
| V0: [1, 2]; | ||
| V1: [3, 4]; | ||
| V2: V0 + V1; // result is [4, 6] | ||
| v2: V1^2; // result is [9, 16] | ||
| ``` | ||
| You can also replace the second operand with a scalar. Here is how it'll work: | ||
| ``` | ||
| V0: [1, 2]; | ||
| V1: V0 * 2; // result is [2, 4] | ||
| ``` | ||
| One important thing to note: if both operands are vectors, the operations make sense only if vectors have the same dimensions (i.e. you can't do element-wise addition between vectors of different lengths). | ||
| Even though the examples above focus on vectors, you can apply the same operations to matrixes (of same dimensions), and they'll work in the same way. | ||
| There is one additional operation we can apply to vectors and matrixes (but not to scalars): `#`. The meaning of this operation is as follows: | ||
| * **matrix # matrix** - performs a standard [matrix multiplication](https://en.wikipedia.org/wiki/Matrix_multiplication) of two matrixes. If the input matrixes have dimensions [*n*,*p*] and [*p*,*m*], the output matrix will have dimensions [*n*,*m*]. | ||
| * **matrix # vector** - also performs matrix multiplication, but the output is a vector. If the input matrix dimensions are [*n*,*m*], and the length of the input vector is *m*, the output vector will have length *n*. | ||
| * **vector # vector** - performs a [linear combination](https://en.wikipedia.org/wiki/Linear_combination) of two vectors. Vectors must have the same length, and the output is a scalar. | ||
| ## Assertions | ||
@@ -202,3 +286,3 @@ 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: | ||
| ## Constants | ||
| 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. | ||
| 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 scripts by using the `$k` prefix. For example, `$k0`, `$k1`, `$k2` etc. | ||
@@ -205,0 +289,0 @@ You can defined readonly registers by providing constant definitions to `Stark` constructor. Constant definitions have the following form: |
New alerts
Uses eval
Supply chain riskPackage uses dynamic code execution (e.g., eval()), which is a dangerous practice. This can prevent the code from running in certain environments and increases the risk that the code may contain exploits or malicious behavior.
Found 1 instance in 1 package
Fixed alerts
Uses eval
Supply chain riskPackage uses dynamic code execution (e.g., eval()), which is a dangerous practice. This can prevent the code from running in certain environments and increases the risk that the code may contain exploits or malicious behavior.
Found 1 instance in 1 package
Improved metrics
- Total package byte prevSize
- increased by48.61%
166250
- Number of package files
- increased by26.92%
33
- Lines of code
- increased by49.83%
3148
- Number of lines in readme file
- increased by34.57%
327
Dependency changes
+ Added@guildofweavers/galois@0.2.0(transitive)
- Removed@guildofweavers/galois@0.1.2(transitive)
Updated@guildofweavers/galois@0.2.x