### 3 releases

✓ Uses Rust 2018 edition

0.1.2 | Oct 7, 2019 |
---|---|

0.1.1 | Oct 7, 2019 |

0.1.0 | Oct 7, 2019 |

#**103** in Algorithms

**Apache-2.0**

645KB

7K
SLoC

# OpenZKP Stark

Implementation of STARK zero-knowledge-proofs.

## Example

`use` `zkp_stark``::``{``*``,` `primefield``::``*``}``;`
`struct` `FibonacciClaim` `{`
`index``:` `usize`,
`value``:` FieldElement,
`}`
`impl` `Verifiable ``for`` ``FibonacciClaim` `{`
`fn` `constraints``(``&``self``)`` ``->` Constraints `{`
`use` `RationalExpression``::``*``;`
`//` Seed
`let` `mut` seed `=` `self``.`index`.``to_be_bytes``(``)``.``to_vec``(``)``;`
seed`.``extend_from_slice``(``&``self``.`value`.``as_montgomery``(``)``.``to_bytes_be``(``)``)``;`
`//` Constraint repetitions
`let` trace_length `=` `self``.`index`.``next_power_of_two``(``)``;`
`let` g `=` Constant`(``FieldElement``::`root`(`trace_length`)``.``unwrap``(``)``)``;`
`let` `on_row` `=` `|``index``|` `(`X `-` g`.``pow``(`index`)``)``.``inv``(``)``;`
`let` `every_row` `=` `|``|` `(`X `-` g`.``pow``(`trace_length `-` `1``)``)` `/` `(`X`.``pow``(`trace_length`)` `-` `1.``into``(``)``)``;`
`let` `mut` c `=` `Constraints``::`from_expressions`(``(`trace_length`,` `2``)``,` seed`,` `vec!``[`
`(`Trace`(``0``,` `1``)` `-` Trace`(``1``,` `0``)``)` `*` `every_row``(``)``,`
`(`Trace`(``1``,` `1``)` `-` Trace`(``0``,` `0``)` `-` Trace`(``1``,` `0``)``)` `*` `every_row``(``)``,`
`(`Trace`(``0``,` `0``)` `-` `1.``into``(``)``)` `*` `on_row``(``0``)``,`
`(`Trace`(``0``,` `0``)` `-` `(``&``self``.`value`)``.``into``(``)``)` `*` `on_row``(``self``.`index`)``,`
`]``)`
`.``unwrap``(``)`
`}`
`}`
`impl` `Provable``<``&`FieldElement`>` `for`` ``FibonacciClaim` `{`
`fn` `trace``(``&``self`, `witness``:` `&`FieldElement`)`` ``->` TraceTable `{`
`let` trace_length `=` `self``.`index`.``next_power_of_two``(``)``;`
`let` `mut` trace `=` `TraceTable``::`new`(`trace_length`,` `2``)``;`
trace`[``(``0``,` `0``)``]` `=` `1.``into``(``)``;`
trace`[``(``0``,` `1``)``]` `=` witness`.``clone``(``)``;`
`for` i `in` `0``..``(`trace_length `-` `1``)` `{`
trace`[``(`i `+` `1``,` `0``)``]` `=` trace`[``(`i`,` `1``)``]``.``clone``(``)``;`
trace`[``(`i `+` `1``,` `1``)``]` `=` `&`trace`[``(`i`,` `0``)``]` `+` `&`trace`[``(`i`,` `1``)``]``;`
`}`
trace
`}`
`}`
`pub` `fn` `main``(``)`` ``{`
`let` claim `=` FibonacciClaim `{`
index`:` `5000``,`
value`:` `FieldElement``::`from_hex_str`(``"`069673d708ad3174714a2c27ffdb56f9b3bfb38c1ea062e070c3ace63e9e26eb`"``)``,`
`}``;`
`let` secret `=` `FieldElement``::`from`(``42``)``;`
`let` proof `=` claim`.``prove``(``&`secret`)``.``unwrap``(``)``;`
claim`.``verify``(``&`proof`)``.``unwrap``(``)``;`
`}`

## Features and Limitations

### Features

**A simple interface.** The public interface is simple and is considered semver-stable. Future versions are expected to add functionality without breaking this interface.

**Succinct proofs.** For a given security parameter, the proof size is close to minimal. Significant improvements here would require innovations in the way constraint systems are designed or in the underlying cryptography.

**Decent performance.** All steps of the proof are using asymptotically optimal algorithms and all of the major steps are multi-threaded. There are no hard memory requirements. We can expect a good amount of performance improvements by fine-tuning, but we don't expect orders of magnitude improvements.

**Webassembly support.** The verifier can be used in a WebAssembly environment without the Rust

lib. The prover will work too, but has not been a priority.`std`

### Limitations

**No high-level language.** Constraints are specified using their algebraic expressions. This requires complicated and careful design from the library user and is easy to do wrong, leading to insecure systems. A high level language would help make development simpler and safer and facilitate re-use of components.

**No comprehensive security audit.** While development is done with the best security practices in mind, it is still very early stage and has not had the amount of expert peer review required for a production grade system.

**No perfect zero-knowledge.** The current implementation provides succinct proofs but not perfect zero knowledge. While non-trivial, it is theoretically possible to learn something about the secret. Achieving perfect zero-knowledge is possible and can be implemented.

**No side-channel resistance.** The implementation favours performance over side-channel resistance. While this is common in zero-knowledge proof system, you should be aware that his might leak intermediate computations. Side-channel resistance can be implemented.

**Hard-coded field and hash.** The current implementation uses a particular prime field and a particular hash function. These are optimized for verification in the Ethereum Virtual Machine. This can be generalized to other primitives optimized for other use cases.

#### Dependencies

~1–2.6MB

~54K SLoC