How to generate the extrinsic execution proof

[liuchengxu]

Basically, substrate already supports the block execution proof, which is being used to validate the state transition of parachain block in polkadot.

// Signal to record the proof before initializing the block
if record_proof.yes() {
    api.record_proof();
}

// Block execution

// Extract the proof after finalizing the block
let proof = self.api.extract_proof();

What we want is the more fine-grained extrinsic execution proof in subspace, we use a custom executive (related: #10711) for collecting the storage root after initializing block and applying each extrinsic. If any executor, who is responsible for processing the transactions in subspace, kind of the collator in parachain, detects an invalid state transition of an extrinsic based on the collected intermediate storage roots, then the executor will generate a proof for this invalid extrinsic state transaction, which is the extrinsic execution proof.

My initial idea is that perhaps it might work if we refer to the pattern of the block execution proof, which means to generate the extrinsic proof by using api.record_proof() before applying the extrinsic and api.extract_proof() after applying the extrinsic, for api.record_proof() will reset the inner recorder to the default that is sort of a reset.

substrate/primitives/api/proc-macro/src/impl_runtime_apis.rs

Lines 274 to 276 in 4cd2cc9

	fn record_proof(&mut self) {
	self.recorder = Some(Default::default());
	}

for xt in extrinsics {
    api.record_proof();
    apply_extrinsic();
    let extrinsic_execution_proof = api.extract_proof();
}

This approach partially works until I found that if there are two same kind of extrinsics in a block, the generated proof will be just empty and finally I think it's probably caused by the overlay when retrieving the storage from the state:

substrate/primitives/state-machine/src/ext.rs

Lines 185 to 189 in a2ae8a5

	let result = self
	.overlay
	.storage(key)
	.map(|x| x.map(|x| x.to_vec()))
	.unwrap_or_else(|| self.backend.storage(key).expect(EXT_NOT_ALLOWED_TO_FAIL));

The reason is that the underlying ProofRecorder only exists in the backend not in the overlay, if a storage item already exists in the overlay, then it won't be recorded during the execution of next round, thus the storage proof for the extrinsic execution can't be constructed as expected.

In order to support the extrinsic execution proof, we need to also embed a proof recorder in the overlay, something like that. I'm not sure if that's possible and how many efforts are required in substrate. Collect me if I'm wrong, any inputs are appreciated!

[bkchr]

This approach partially works until I found that if there are two same kind of extrinsics in a block

This should basically fails in the moment you have multiple extrinsics reading and then writing the same storage entry, because the value is then found in the overlay. As you already have found out, accessing the overlay isn't found in the proof, because it doesn't need to.

For your use case, you would require to commit all the intermediate state into a trie and then generate the proof based on this.

[liuchengxu]

With some hacking into substrate, I added the extrinsic execution proof in our custom block builder , but had trouble to verify this approach does work. The idea is to abuse the way of api.record_proof() and api.extract_proof() mentioned in the first comment, which should be able to generate the execution proof for the first extrinsic, and then compare it with one created by execution_proof in the test https://github.com/subspace/subspace/blob/811a83b72f/cumulus/client/cirrus-executor/src/processor.rs#L294, only to find these two proof mismatches, a few of storage keys have different values and I can't tell the meaning of these mismatched storage keys(I can only identify the storage key for :extrinsic_index) by inspecting OverlayedChanges. Can be really helpful if you could shed some light on what can be related and if there is anything logically wrong here. Thank you! @bkchr

[bkchr]

@liuchengxu I tried to check out your code, but you are using some patches to some unknown substrate repo etc. Could you make your code compile-able for me?

[liuchengxu]

@bkchr Sure! I just pushed a commit subspace/subspace@737ebaf to make it compile-able. The forked substrate is https://github.com/subspace/substrate/tree/proof-generation, which is mainly for exposing the overlay in ApiExt and a lot of debugging prints :P

$ cd /tmp
$ git clone https://github.com/subspace/subspace --branch intermediate-storage-proof
$ cd subspace
$ (cd cumulus/client/cirrus-executor/ && cargo test proof -- --nocapture)

[liuchengxu]

only to find these two proof mismatches, a few of storage keys have different values and I can't tell the meaning of these mismatched storage keys(I can only identify the storage key for :extrinsic_index) by inspecting OverlayedChanges

@bkchr I have figured out this problem. First, the substrate-test-runtime test environment has some deviations to the regular runtime, so different OverlayedChanges occurred. After switching to a more regular runtime, OverlayedChanges produced using these two approaches are exactly the same, but they still produced a different storage proof and finally it turned out it's the inner records using HashMap that is the culprit because HashMap does not maintain a deterministic order for the items. Once I replace the HashMap using BTreeMap, I have two identical storage proofs generated using two methods.

substrate/primitives/state-machine/src/proving_backend.rs

Line 118 in 4cd2cc9

records: HashMap<Hash, Option<DBValue>>,

So, my proposal here is:

1. Given that no obvious performance cost IMO, replace HashMap with BTreeMap for the inner records in the favor of determinism.
2. Extend prove_execution with an optional OverlayedChanges so that we can generate an execution proof for any execution at any stage.

   substrate/client/service/src/client/call_executor.rs

   Lines 293 to 298 in f449abc

   	fn prove_execution(
   	&self,
   	at: &BlockId<Block>,
   	method: &str,
   	call_data: &[u8],
   	) -> sp_blockchain::Result<(Vec<u8>, StorageProof)> {

I'll send a PR(perhaps two PRs) later if no objections. @bkchr

[bkchr]

Good that you found it :)

And sorry for me not having answered.

[nazar-pc]

Briefly the idea is that in Subspace we have optimistic execution and fraud proofs. To make fraud proofs efficient for resource-constrained farmers (consensus nodes, they don't execute transactions), fraud proof doesn't cover the whole block, instead it only needs to cover the first transaction which is executed incorrectly in the block.

For this to work we need to collect execution trace (effective state roots after every transaction), then in fraud proof we can provide inputs to a particular transaction and correct state root and farmers can just run that one transaction to verify a fraud proof.

When compared to Polkadot, the biggest differences are:

• instead of executing the whole block (and including inputs for all transactions) only one transaction is executed
• instead of doing this all the time pessimistically farmers only do execution when fraudulent execution is detected by executors (separate node role on the network dedicated to just transaction execution)

[burdges]

Can you explain what the dispute covers? It's some storage even like a node serving the wrong data? I'd think bad nodes would simply not serve the data when requested.

---

We knew about partial block fraud proofs when we designed substrate and polkadot, well the fraud proofs paper gave us the erasure coding idea.

We decided slashing failed disputes, and punishing both sides on indeterminate disputes, worked out much simpler than partial block fraud proofs. We later noticed partial block fraud proofs break too many optimizations, including cryptographic ones like pre-batching Schnorr or Groth16, SnarkPack, etc.

It'll work out differently if you want end users verifying everything of course, like LazyLedger / Celestia or the fraud proofs paper. We also believe this whole approach fails though, due to a tragedy of the commons, maybe details could alter this conclusion, but overall sounds tricky.

I do advise deeper consideration over whether partial block fraud proofs really do what you think they do.

All this said..

I do believe greater room for optimism exists in when doing storage work, so yeah maybe another approach makes sense here. I'd likely focus upon erasure coding but maybe that brings other annoyances. Also state channels, not sure.

We've only really have one sort of storage and proof in substrate, which fits poorly with many important situations. As a prime example, any parachain doing zk UTXOs must implement this all themselves. It's kinda par for the course that if you need to so something interesting then you may require stranger validation code somehow. We should keep teams who run into this sort of things talking together and with us, maybe some shared abstractions emerge, but who knows..

[nazar-pc]

Dispute covers divergence in what is by definition a deterministic execution of the blocks by executors (network role responsible for transaction processing), while blocks themselves are produced by farmers (Proof-of-Archival-Storage consensus nodes).

The reason we can't just do slashing is because farmers (consensus nodes) that need to run computations will be overloaded long before they can do slashing, so fraud proofs need to be as efficient as possible. Farmers are by definition much weaker nodes in terms of processing power, this allows for more decentralized participation.

If you have time (and I don't expect that you do) it might be beneficial to take a look at our whitepaper so that terminology and overall construction makes more sense: https://subspace.network/blog/subspace-network-whitepaper
We do indeed have some unusual things comparing to most Substrate-based chains. We are fine writing custom logic and contributing back to Substrate, forking half of Substrate and modifying a bunch of things downstream is not a very efficient way in terms of maintenance.