Using zkp::verify() from Move with invalid proof is 1000 times slower

[simsekgokhan]

Problem Description

Calling zkp::verify() from Move with invalid proof is 1000 times slower than calling from Rust. (And with valid proof 6 times slower.)

After initial short investigation, the line where the long wait happens is here: https://github.com/simsekgokhan/ethSTARK/blob/bdccf92425cabe9de435f730f85a0313b93a4ddd/src/starkware/stark/stark.cc#L391

  const CompositionOracleVerifier oods_composition_oracle =
      OutOfDomainSamplingVerify(std::move(composition_oracle));

Details

1. Using zkp::verify() from Move

Branch: https://github.com/OLSF/libra/tree/zkp
cd language/move-lang/functional-tests/
cargo t zkp

a. Invalid proof: (Problematic case)

language/move-lang/functional-tests/tests/0L/zkp/zkp_verify_invalid_proof_hex.move

----------- unsafe C++ call   -----------

// <==== Long wait here

E0209 17:58:24.340343 321167 proof_system.cc:14] 
  /home/gsimsek/ethSTARK/src/starkware/stark/oods.cc:153: 
  Out of domain sampling verification failed.
-------
--- time_elapsed (msec): 35947
-------
E0209 17:58:24.342315 321167 rescue_verifier.cc:50] Invalid proof.
----------- end of unsafe C++ -----------
test functional_testsuite::0L/zkp/-zkp_verify_invalid_proof_hex.move ... ok

b. Valid proof (Ok - but still 6 times slower than Rust):

language/move-lang/functional-tests/tests/0L/zkp/zkp_verify_valid_proof_hex.move

----------- unsafe C++ call   -----------
-------
--- time_elapsed (msec): 6
-------
I0209 22:49:08.584766 377465 rescue_verifier.cc:48] Proof verified successfully.

----------- end of unsafe C++ -----------

test functional_testsuite::0L/zkp/zkp_verify_valid_proof.move ... ok

2. Using zkp::verify() from Rust - All good here

Using zkp::verify() from miner/main.rs

/// Boot MinerApp
fn main() {
    // abscissa_core::boot(&APPLICATION);
    let public_input: &str = 
        // invalid
        r#" {"chain_length":3,"output":["0xab0a16d9f9cedae","0x244b64cb5a39a2b","0x1f6c22cd3cfdde49","0x4bf27b6fae084cb"]} "#;
        // valid
        // r#" {"chain_length":3,"output":["0xdb0a16d9f9cedae","0x244b64cb5a39a2b","0x1f6c22cd3cfdde49","0x4bf27b6fae084cb"]} "#;

    rescue_verify(
        example_proof::PROOF_HEX, 
        public_input,
        example_proof::PARAMETERS, 
        ""        
    );

a. Invalid proof:

----------- unsafe C++ call   -----------
E0210 10:10:49.439395 392816 proof_system.cc:14]
  /home/gsimsek/ethSTARK/src/starkware/stark/oods.cc:153: 
  Out of domain sampling verification failed.

-------
--- time_elapsed (msec): 30
-------
E0210 10:10:49.439499 392816 rescue_verifier.cc:50] Invalid proof.

----------- end of unsafe C++ -----------

b. Valid proof:

----------- unsafe C++ call   -----------
-------
--- time_elapsed (msec): 1
-------
  I0209 17:51:24.506377 317142 rescue_verifier.cc:48] 
  Proof verified successfully.
----------- end of unsafe C++ -----------

Next Actions

• Continue investigating ethSTARK repo to find exact long waiting function/line
• Find out what is being done differently in program execution model when verify() is called from Move (e.g. heavy thread usage?, green-threading?)

[0o-de-lally]

paging @zmanian and @tarcieri

[simsekgokhan]

Update:

• Seems that the problem is fixed by not using ASSERT_RELEASE(..) macro in oods.cc in ethSTARK code. https://github.com/simsekgokhan/ethSTARK/commit/a9bd62f5640072490b75c3b0a04c1a38521e8b6c#diff-26eb06651941ec7cfbe57050732a0ae7f1e0ffbeb23ab86a63a33fb6094b5f7bL151
• This temporary fix also seems to make Rust verify call with invalid proof 30 times faster.
• The fix: https://github.com/simsekgokhan/ethSTARK/commit/a9bd62f5640072490b75c3b0a04c1a38521e8b6c#diff-d1f0b1c8afef2bc46fcdb007598290b24bcf45e7be2ec4e51a6e6617e768b535

Root Cause:

Invalid proof triggers ThrowStarkwareException() function (by ASSERT_RELEASE(..) macro) which causes the long wait probably due to some things go very wrong inside that function - might be investigated more if needed. https://github.com/simsekgokhan/ethSTARK/blob/master/src/starkware/error_handling/error_handling.cc#L26

Latest Results:

1. Using zkp::verify() from Move

a. Invalid proof: (Previously 1000 times slower than Rust - now almost the same)

----------- unsafe C++ call   -----------

WARNING: Logging before InitGoogleLogging() is written to STDERR
E0225 20:07:09.778414 218725 verifier_main_helper.cc:65] --- oods.cc: Out of domain sampling verification failed.
-------
--- time_elapsed: 1 msec 
-------
E0225 20:07:09.778749 218725 rescue_verifier.cc:48] Invalid proof.

----------- end of unsafe C++ -----------

test functional_testsuite::0L/zkp/zkp_verify_invalid_proof_hex.move ... ok

b. Valid proof: (Previously 6 times slower than Rust - now 2-3 times slower)

----------- unsafe C++ call   -----------

-------
--- time_elapsed: 3 msec 
-------
WARNING: Logging before InitGoogleLogging() is written to STDERR
I0225 20:09:25.202208 220013 rescue_verifier.cc:46] Proof verified successfully.

----------- end of unsafe C++ -----------

test functional_testsuite::0L/zkp/zkp_verify_valid_proof.move ... ok

2. Using zkp::verify() from Rust

a. Invalid proof: (30 times faster than before)

----------- unsafe C++ call   -----------

WARNING: Logging before InitGoogleLogging() is written to STDERR
E0225 20:05:29.171983 216599 verifier_main_helper.cc:65] --- oods.cc: Out of domain sampling verification failed.
-------
--- time_elapsed: 1 msec 
-------
E0225 20:05:29.172487 216599 rescue_verifier.cc:48] Invalid proof.

----------- end of unsafe C++ -----------

b. Valid proof:

----------- unsafe C++ call   -----------

-------
--- time_elapsed: 2 msec 
-------
WARNING: Logging before InitGoogleLogging() is written to STDERR
I0225 20:13:19.480569 220229 rescue_verifier.cc:46] Proof verified successfully.

----------- end of unsafe C++ -----------

Next Actions:

• This fix is temporary a one. Different type of invalid proof cases might trigger this problem again. The general solution might involve changing ASSERT_RELEASE(..) macro or ThrowStarkwareException(). But this more generic fix might be done in the future. New issue: https://github.com/OLSF/libra/issues/372
• To be closed after final testing

[0o-de-lally]

closed with f4c3f42