Enable signature verification in background task

[librelois]

Bring back signature batch verification but with the new name background verification.

Indeed, batch verification - in the cryptographic sense - is a different feature, and only exists for certain types of signatures.

Batch verification is currently only implemented for signatures of type sr25519. For the other types of signatures (ed25519 and ecdsa), each signature is verified alone but in a background task.

Some questions about the design:

1. How to expose this functionality to the user? For the moment I have chosen a compilation feature at the frame-executive level because it is the simplest.
2. Should we disable batch verification for sr25519 signatures, in order to separate this in a different future functionality?
3. Should we replace all the batch occurrences by background ?

---

Added an optimization suggested by @crystalin: in case the first extrinsics are particularly long to run, the background tasks that check the signatures will do nothing for a while, which is suboptimal. It is more optimal to spawn all the signatures to be checked in the background before starting to run the extrinsics.

---

Closes #6618

[librelois]

@bkchr Can someone from parity give me feedback on this PR please? We still want to integrate signature verification as a background task :)

[crystalin]

@bkchr can we get a review/feedback on this please ?

[librelois]

The SignatureBatching should then be renamed.

@bkchr what new name do you suggest ?

[bkchr]

The SignatureBatching should then be renamed.

@bkchr what new name do you suggest ?

IDK. Maybe BackgroundVerifyContext?

[librelois]

@bkchr This PR is ready for a final review :)

@kianenigma I ran try-runtime follow-chain on a polkadot fork that include this PR, and it seems to work well:

2022-07-01 21:46:58 proof size: 1.28 MB (1306.921875 KB) (1338288 bytes)    
2022-07-01 21:46:58 compact proof size: 1.27 MB (1298.25 KB) (1329408 bytes)    
2022-07-01 21:46:58 zstd-compressed compact proof 1.24 MB (1269.294921875 KB) (1299758 bytes)    
2022-07-01 21:47:01 executed block 10980530, consumed weight 494804135000, new storage root 0x3204c6241d7f23366ea0038224a13719c72a7665d5c860011a89b468e1182535    
2022-07-01 21:47:02 Connection established to target: Target { sockaddrs: [], host: "rpc.polkadot.io", host_header: "rpc.polkadot.io:443", _mode: Tls, path_and_query: "/" }
2022-07-01 21:47:04 proof: 000000000000000001000000000000002ab434ab6d0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000008083150fec09000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000a000005000000a00000000c8000000c800000a0000000a00000040380000580200000000500000c8000000e87648170000000a0000000000000000e8764817000000000000000000000000e87648170000000000000000000000e8030000009001000a00000000000000009001004038000000000000000000000a0000000a0000000a00000001000000010500000001c8000000060000005802000002000000580200000200000059000000000000001e0000002800000000c817a804000000000200000014000000210316b94e2d5d12d60c7314cca383bf185ddda83f413da740a121601e3277d3083efc6f8380646bfa19f4dc7c1ed6ebfb0a93f5781793aef9224a05e805426d151c688140b645221a0239782a1f27f7dfa3b2967ba30b52bcd2c922d993cff3d27d29a843ce5a67c2d285cc5f302db173ee4563e7af383dfc6b9a8fa64e148efd12a4d9ad920e6d008377f35404c242a24b968467...adfef6ce96a5a3de045b22052e7c70b2e180d2cba07dcb6449eb812a2fc75b4a8d3eb8675c7273dcd8b8f05df2f420845059805d475dddb3969e9f2bfd954ab771d87002ea94bc3cd7a232a1744c3066b46cac80d806c7fb1a06cb0d73d6732065d15af6ea8b3b0cf41133bb5b34276ad205506a80e9d25d80c402efb91ac2d2c80d406a81a96efe7fe6a6e993ca101351f85b49c7808c9e93c5847eec423de273b85d7bc726723f3fb9aef242e4544b9d8b300da2be8069d8343e0894b98b8b7467c47dcf5e72d2abfc9641252af36f0724a75c7f381280ada7b6395698ae8fbafc7576290a7a9ce43255806f47dcc9be8b990db61b1dc280108026e8f7ad83f19f4689e1b740772112789be37426c72e43e0b8b591cf207a80d970d61eaa2191348742223f5d05bfecfb259d065770491d92b152709fa21eb2801273be3be60c1dc417fb3dc9a048a98a06b49e481b067da5205a4feb6d3335c1809fb5dfefe43d23d68560403bb51ea7b20abe2c222e51114eb4852fa2238be088801c7fd802a90ce29b0676fd0954c93fd5eb06851c1eae683a5b76812714c4c44f80e53713847d04fb94c10a1f1b90c7c7f35bf1cea35c24c6f100450fceb1521dfd80984920fd1f8909cc7008d821cc40c77d9c77b5909586dbc046371a07de5c615a80524ac30f09db01bd68144b569588b4be2886e845049c5f472e2eefec886f9d6c / 329 nodes    
2022-07-01 21:47:04 proof size: 1.29 MB (1321.93359375 KB) (1353660 bytes)    
2022-07-01 21:47:04 compact proof size: 1.28 MB (1312.0439453125 KB) (1343533 bytes)    
2022-07-01 21:47:04 zstd-compressed compact proof 1.25 MB (1280.39453125 KB) (1311124 bytes)    
2022-07-01 21:47:07 executed block 10980531, consumed weight 479809388000, new storage root 0xe93030646c31dc4d95f0a96fa146c9fcee83ac0989b7f437de7710f612a3cda6    
2022-07-01 21:47:08 Connection established to target: Target { sockaddrs: [], host: "rpc.polkadot.io", host_header: "rpc.polkadot.io:443", _mode: Tls, path_and_query: "/" }
2022-07-01 21:47:10 proof: 0000a000005000000a00000000c8000000c800000a0000000a00000040380000580200000000500000c8000000e87648170000000a0000000000000000e8764817000000000000000000000000e87648170000000000000000000000e8030000009001000a00000000000000009001004038000000000000000000000a0000000a0000000a00000001000000010500000001c8000000060000005802000002000000580200000200000059000000000000001e0000002800000000c817a804000000000200000014000000210316b94e2d5d12d60c7314cca383bf185ddda83f413da740a121601e3277d3083efc6f8380646bfa19f4dc7c1ed6ebfb0a93f5781793aef9224a05e805426d151c688140b645221a0239782a1f27f7dfa3b2967ba30b52bcd2c922d993cff3d27d29a843ce5a67c2d285cc5f302db173ee4563e7af383dfc6b9a8fa64e148efd12a4d9ad920e6d008377f35404c242a24b968467891ceb87dcf5e8c12943b02e5e730800477a5fb0302fa9ff4b5623662a27719a304dedb3e12eb004f48ecf6b29996a48be9e514c627122d28cbc8128389b88b230a85228a2fd091cc5d8292b394a8de2c6b6c1690a27aaa4cb64e0168bced54ab568958965187646f06442be6d2c2a55b5b05723585c7421428d9ef451313e33e13803424b0f8cabd383d0df37c22eff63f91830d4f1b882bad30ab87660afb9...adfef6ce96a5a3de045b22052e7c70b2e180d2cba07dcb6449eb812a2fc75b4a8d3eb8675c7273dcd8b8f05df2f420845059805d475dddb3969e9f2bfd954ab771d87002ea94bc3cd7a232a1744c3066b46cac80d806c7fb1a06cb0d73d6732065d15af6ea8b3b0cf41133bb5b34276ad205506a80e9d25d80c402efb91ac2d2c80d406a81a96efe7fe6a6e993ca101351f85b49c7808c9e93c5847eec423de273b85d7bc726723f3fb9aef242e4544b9d8b300da2be8069d8343e0894b98b8b7467c47dcf5e72d2abfc9641252af36f0724a75c7f381280ada7b6395698ae8fbafc7576290a7a9ce43255806f47dcc9be8b990db61b1dc280108026e8f7ad83f19f4689e1b740772112789be37426c72e43e0b8b591cf207a80efee9720e0b131870c39edb648ed4cf8e511d46554b89c02c3cbabe12bb3e297801273be3be60c1dc417fb3dc9a048a98a06b49e481b067da5205a4feb6d3335c1809fb5dfefe43d23d68560403bb51ea7b20abe2c222e51114eb4852fa2238be088801c7fd802a90ce29b0676fd0954c93fd5eb06851c1eae683a5b76812714c4c44f80e53713847d04fb94c10a1f1b90c7c7f35bf1cea35c24c6f100450fceb1521dfd80984920fd1f8909cc7008d821cc40c77d9c77b5909586dbc046371a07de5c615a80524ac30f09db01bd68144b569588b4be2886e845049c5f472e2eefec886f9d6c / 292 nodes    
2022-07-01 21:47:10 proof size: 1.27 MB (1305.38671875 KB) (1336716 bytes)    
2022-07-01 21:47:10 compact proof size: 1.27 MB (1296.5556640625 KB) (1327673 bytes)    
2022-07-01 21:47:10 zstd-compressed compact proof 1.24 MB (1267.6357421875 KB) (1298059 bytes)    
2022-07-01 21:47:13 executed block 10980532, consumed weight 495664703000, new storage root 0x12ceaff4fe49da9ffea12b48cc244d00fec6a7adf496a8393033d398cd606022    
2022-07-01 21:47:13 Connection established to target: Target { sockaddrs: [], host: "rpc.polkadot.io", host_header: "rpc.polkadot.io:443", _mode: Tls, path_and_query: "/" }

[librelois]

@bkchr This PR is ready and the CI is green, can you do a final review ?

[ggwpez]

It stops working for larger blocks, when i try the benchmark extrinsic command with a Signature verification failed…

With 100 extrinsics per block it works fine:

# On branch PureStake:elois-background-sig-verif
cargo r --release --bin substrate --features background-signature-verification -- benchmark extrinsic --pallet system --extrinsic remark --dev --max-ext-per-block 100

Running 10 warmups...    
Executing block 100 times    
Building block, this takes some time...    
Extrinsics per block: 100    
Running 10 warmups...    
Executing block 100 times    
Executing a system::remark extrinsic takes[ns]:
Total: 5699353
Min: 55747, Max: 58498
Average: 56993, Median: 56988, Stddev: 402.85
Percentiles 99th, 95th, 75th: 57993, 57578, 57250

But with 1000 it panics:

cargo r --release --bin substrate --features background-signature-verification -- benchmark extrinsic --pallet system --extrinsic remark --dev --max-ext-per-block 1000

Running 10 warmups...    
Executing block 100 times    
Building block, this takes some time...    
Extrinsics per block: 1000    
Running 10 warmups...    
Haven't received async result from verification task. Returning false.    

====================

Version: 3.0.0-dev-38a5d822dd7

   0: sp_panic_handler::set::{{closure}}
   1: std::panicking::rust_panic_with_hook
             at /rustc/4b91a6ea7258a947e59c6522cd5898e7c0a6a88f/library/std/src/panicking.rs:702:17
   2: std::panicking::begin_panic_handler::{{closure}}
             at /rustc/4b91a6ea7258a947e59c6522cd5898e7c0a6a88f/library/std/src/panicking.rs:586:13
   3: std::sys_common::backtrace::__rust_end_short_backtrace
             at /rustc/4b91a6ea7258a947e59c6522cd5898e7c0a6a88f/library/std/src/sys_common/backtrace.rs:138:18
   4: rust_begin_unwind
             at /rustc/4b91a6ea7258a947e59c6522cd5898e7c0a6a88f/library/std/src/panicking.rs:584:5
   5: core::panicking::panic_fmt
             at /rustc/4b91a6ea7258a947e59c6522cd5898e7c0a6a88f/library/core/src/panicking.rs:142:14
   6: tracing::span::Span::in_scope
   7: frame_executive::Executive<System,Block,Context,UnsignedValidator,AllPalletsWithSystem,COnRuntimeUpgrade>::execute_block
   8: kitchensink_runtime::api::dispatch
   9: <node_executor::ExecutorDispatch as sc_executor::native_executor::NativeExecutionDispatch>::dispatch
  10: std::thread::local::LocalKey<T>::with
  11: sc_executor::native_executor::WasmExecutor<H>::with_instance::{{closure}}
  12: sc_executor::wasm_runtime::RuntimeCache::with_instance
  13: sp_state_machine::execution::StateMachine<B,H,Exec>::execute_aux
  14: sp_state_machine::execution::StateMachine<B,H,Exec>::execute_using_consensus_failure_handler
  15: <sc_service::client::call_executor::LocalCallExecutor<Block,B,E> as sc_client_api::call_executor::CallExecutor<Block>>::contextual_call
  16: <sc_service::client::client::Client<B,E,Block,RA> as sp_api::CallApiAt<Block>>::call_api_at
  17: <kitchensink_runtime::RuntimeApiImpl<__SR_API_BLOCK__,RuntimeApiImplCall> as sp_api::Core<__SR_API_BLOCK__>>::__runtime_api_internal_call_api_at
  18: sp_api::Core::execute_block
  19: frame_benchmarking_cli::extrinsic::bench::Benchmark<Block,BA,C>::measure_block
  20: frame_benchmarking_cli::extrinsic::bench::Benchmark<Block,BA,C>::bench_extrinsic
  21: sc_cli::runner::Runner<C>::sync_run
  22: node_cli::command::run
  23: substrate::main
  24: std::sys_common::backtrace::__rust_begin_short_backtrace
  25: std::rt::lang_start::{{closure}}
  26: core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &F>::call_once
             at /rustc/4b91a6ea7258a947e59c6522cd5898e7c0a6a88f/library/core/src/ops/function.rs:280:13
      std::panicking::try::do_call
             at /rustc/4b91a6ea7258a947e59c6522cd5898e7c0a6a88f/library/std/src/panicking.rs:492:40
      std::panicking::try
             at /rustc/4b91a6ea7258a947e59c6522cd5898e7c0a6a88f/library/std/src/panicking.rs:456:19
      std::panic::catch_unwind
             at /rustc/4b91a6ea7258a947e59c6522cd5898e7c0a6a88f/library/std/src/panic.rs:137:14
      std::rt::lang_start_internal::{{closure}}
             at /rustc/4b91a6ea7258a947e59c6522cd5898e7c0a6a88f/library/std/src/rt.rs:128:48
      std::panicking::try::do_call
             at /rustc/4b91a6ea7258a947e59c6522cd5898e7c0a6a88f/library/std/src/panicking.rs:492:40
      std::panicking::try
             at /rustc/4b91a6ea7258a947e59c6522cd5898e7c0a6a88f/library/std/src/panicking.rs:456:19
      std::panic::catch_unwind
             at /rustc/4b91a6ea7258a947e59c6522cd5898e7c0a6a88f/library/std/src/panic.rs:137:14
      std::rt::lang_start_internal
             at /rustc/4b91a6ea7258a947e59c6522cd5898e7c0a6a88f/library/std/src/rt.rs:128:20
  27: main
  28: __libc_start_call_main
             at ./csu/../sysdeps/nptl/libc_start_call_main.h:58:16
  29: __libc_start_main_impl
             at ./csu/../csu/libc-start.c:392:3
  30: _start


Thread 'main' panicked at 'Signature verification failed.', /home/vados/work/substrate/frame/executive/src/lib.rs:413

This is a bug. Please report it at:

	https://github.com/paritytech/substrate/issues/new

2022-08-30 12:27:36 Evicting failed runtime instance error=Runtime panicked: Signature verification failed.
Error: Client(RuntimeApiError(Application(Execution(RuntimePanicked("Signature verification failed.")))))

It warns "Haven't received async result from verification task. Returning false.". I changed it to print the actual error which is just: RecvError.

[bkchr]

@ggwpez will be solved by this: https://github.com/paritytech/substrate/pull/12147

[librelois]

Thank you @ggwpez for your tests :)

I ran the same commands as you and I got the same error. The error occurs exactly when the number of extrinsic reaches 128 (it works with 127), I think it's related to this line: https://github.com/PureStake/substrate/blob/elois-background-sig-verif/primitives/io/src/batch_verifier.rs#L125

I admit I haven't understood everything yet, this is a part of the code I haven't written and haven't touched yet. hope that paritytech/substrate#12147 will indeed solve the problem.

[Polkadot-Forum]

This pull request has been mentioned on Polkadot Forum. There might be relevant details there:

https://forum.polkadot.network/t/background-signature-verification/132/1

[stale[bot]]

Hey, is anyone still working on this? Due to the inactivity this issue has been automatically marked as stale. It will be closed if no further activity occurs. Thank you for your contributions.