toposware / certificate-stark Goto Github PK

View Code? Open in Web Editor NEW

3.0 3.0 1.0 227 KB

An example of state-transition AIR program backed by the winterfell library.

License: Apache License 2.0

Rust 100.00%

rust cryptography zkp stark state-transition

certificate-stark's Introduction

certificate-stark

The Topos state-transition AIR program backed by the winterfell library.

This crate can be made no_std compliant, by relying on the alloc crate instead.

WARNING: This is an ongoing, prototype implementation subject to changes. In particular, it has not been audited and may contain bugs and security flaws. This implementation is NOT ready for production use.

Features

concurrent: Enables multi-threading during proof generation. It implies the std feature.
std (on by default): Enables the use of the Rust standard library

Description

The Topos state-transition AIR program ensures a global consistency of the Topos ecosystem by means of zk-STARKs. It verifies the consistency of transactions provided as private witness, through a set of hardcoded rules validating or rejecting them.

It internally relies on the winterfell library.

License

Licensed under either of

Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

certificate-stark's People

Contributors

Stargazers

Watchers

Forkers

mfaulk

certificate-stark's Issues

Use several Fp elements of hash digest for Schnorr scalar multiplication

The PR #10 introduces the new field-extension based curve Cheetah as underlying curve for our state-transition AIR program.
Unlike the previously used curve, each register is storing a u64 value representing an Fp element. Hence, we need to use more than one register of hash output during Schnorr signature verification AIR program to perform the scalar multiplication with the public key.

The above PR only takes the first element of the hash digest to recompute the scalar mult, similarly to the previous curve over a field of size 252 bits. There are ways to deal with this properly, but it may be impacted by the way we want to rearrange the trace / perform the Schnorr aggregation / implement the in-circuit RAPs. This Issue is to keep track of it.

Random constraint degrees mismatch in AIR program

Happens sparsely. Requires to be ran in debug as the constraint degree check is not enforced in release mode.

running 4 tests
test merkle::update::tests::transaction_test_basic_proof_verification_fail ... ok
test merkle::update::tests::transaction_test_basic_proof_verification ... ok
test tests::transaction_test_basic_proof_verification has been running for over 60 seconds
test tests::transaction_test_basic_proof_verification_fail has been running for over 60 seconds
test tests::transaction_test_basic_proof_verification ... FAILED
test tests::transaction_test_basic_proof_verification_fail ... ok

failures:

---- tests::transaction_test_basic_proof_verification stdout ----
thread 'tests::transaction_test_basic_proof_verification' panicked at 'transition constraint degrees didn't match
expected: [14327, 12280, 12280, 8187, 14327, 14327, 14327, 8187, 8187, 8187, 8187, 8187, 8187, 8187, 8187, 8187, 8187, 8187, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093]
actual:   [14327, 12280, 12280, 8187, 10234, 10234, 10234, 8187, 8187, 8187, 8187, 8187, 8187, 8187, 8187, 8187, 8187, 8187, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093, 4093]', /home/travis/.cargo/git/checkouts/winterfell-0d41aad92a6cccd9/b97463e/prover/src/constraints/evaluation_table.rs:213:13
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    tests::transaction_test_basic_proof_verification

test result: FAILED. 3 passed; 1 failed; 0 ignored; 0 measured; 8 filtered out; finished in 214.53s

error: test failed, to rerun pass '--lib'

Implement in-circuit Schnorr signature verification aggregation

See detailed explanations here.

The usefulness of this optimization may be impacted by issues related to #6 and #7, depending on how these extra features are dealt with (i.e. if they increase the execution trace length).

In particular, the new Rescue hash instantiation with the Cheetah curve allows us to reduce the total current Merkle execution trace's length to less than 256 rows (currently 512), which combined with a reduction in half of Schnorr's length (currently 512) would lead to a total execution trace length also reduced by half.

Dependency problem with cheetah

certificate-stark$ cargo build
    Updating crates.io index
    Updating git repository `https://github.com/ToposWare/winterfell.git`
error: failed to get `winterfell` as a dependency of package `certificate-stark v0.1.0 (/home/alonso/Toposware/certificate-stark)`

Caused by:
  failed to load source for dependency `winterfell`

Caused by:
  Unable to update https://github.com/ToposWare/winterfell.git?branch=cheetah

Caused by:
  failed to find branch `cheetah`

Caused by:
  cannot locate remote-tracking branch 'origin/cheetah'; class=Reference (4); code=NotFound (-3)

maybe because is looking for the branch cheetah on winterfell?

Random wrong accumulated value for sigma

This one is not related to the AIR program itself but to the trace builder. Needs to be ran in debug mode as well or will be ignored (or turn the debug_assert_eq! to assert_eq!)

running 4 tests
test tests::transaction_test_basic_proof_verification_fail ... FAILED
test merkle::update::tests::transaction_test_basic_proof_verification_fail ... ok
test merkle::update::tests::transaction_test_basic_proof_verification ... ok
test tests::transaction_test_basic_proof_verification has been running for over 60 seconds
test tests::transaction_test_basic_proof_verification ... ok

failures:

---- tests::transaction_test_basic_proof_verification_fail stdout ----
thread 'tests::transaction_test_basic_proof_verification_fail' panicked at 'assertion failed: `(left == right)`
  left: `0x0000000000000000000000000000000000000000000000002f4eb07f6874f52d`,
 right: `0x0000000000000000000000000000000000000000000000012f4eb07f6874f52d`: expected accumulated value for sigma of 0x0000000000000000000000000000000000000000000000012f4eb07f6874f52d, found 0x0000000000000000000000000000000000000000000000002f4eb07f6874f52d', src/trace.rs:213:13
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    tests::transaction_test_basic_proof_verification_fail

test result: FAILED. 3 passed; 1 failed; 0 ignored; 0 measured; 8 filtered out; finished in 208.35s

error: test failed, to rerun pass '--lib'

Support insertion of new accounts in the state

We currently deal with transactions between existing accounts, but a transaction may send funds to a previously unregistered address of the subnet, which would need to be replacing the next "dummy" leaf.

It seems relatively easy to add constraints enforcing that the leaf corresponding to the receiver position matches either the receiver address (i.e. existing account) or a known "dummy" leaf value (i.e new account).
Note that this doesn't prevent the STARK producer to fill a new leaf entry with an already existing account (i.e. no easy non-membership proof within a regular Merkle tree). It doesn't seem to be a real issue in our usecase though.

Fee handling

Transaction fees are currently unsupported (or assuming no fees in Topos transactions) for the state-transition AIR program.

The easiest approaches seem to be either

burn the fee (but may make total supply control tricky)
send the fees to a dedicated account. Could be the first one in the Merkle tree, with a dedicated unreachable address. This implies adding the correct update of this account.

Approach two seems to be the preferred one.

Non-hashed Merkle tree leaves

Currently, the Merkle tree implementation stores leaves as hashes, while we may want to keep track of the non-hashed values for easier update with new transactions.

May require either an update on the winterfell side directly or some pairing between a tree as it currently is and a slice viewing all non-hashed account values.

May be nice to have an idea of how things are being dealt with inside Substrate.

XC transactions handling

The State transition AIR program currently only supports internal transactions with both accounts on the chain.
Being able to handle XC transactions as well (both incoming and outgoing ones) requires:

funds management (for supply control) - could be locked in a specific account for this purpose (see #6 issue for related idea)
transactions being public for receiver handling (currently all transactions are private and known only to the sidechain; private XC txes are not being in the pipeline for now)

Having two separate STARK proofs (1 for internal transactions, 1 for XC ones) seems the easiest solution, at the cost of heavier Cert generation / slower interoperability. It may also require for the Sidechain to wait for XC tx inclusion until the end of a regular tx batch in case that would affect the SC state.

Use full-depth tree

We're currently using two different Tree depth constants for unit tests and general use mode, i.e. 4 or 16.

The actual expected state of a subnet would be rather 2^32, which would require to generate an empty tree directly through hardcoded nodes at each layer, to prevent tree creation time to blow-up. It would be also helpful to test performances in real conditions.

This would be directly implemented in https://github.com/Toposware/winterfell/tree/main/crypto/src/merkle/mod.rs with the other helper methods.

Use actual implementation of Rescue and Schnorr in the STF

The current AIR program re-implements the Rescue hash instantiation being used and the custom Schnorr signature, while external crates are ready to be used.
For consistency, ease of use and prevent breaking changes, it would be better to use the actual implementations directly