search

autonomys / subspace

Subspace Network reference implementation
https://subspace.network
371 stars 242 forks source link

Usage of Execution trace root #2154

Open vedhavyas opened 10 months ago

vedhavyas commented 10 months ago

It turns out we dont need the execution root trace for any of the fraud proof verification since we already have required execution traces on consensus chain to verify the state transition fraud proof.

Thinking on this more, I dont think we strictly need those execution traces and if there are n extrinsics, we will end up n+1 32 byte hashes in every ER there by every Bundle. Instead, we can keep the execution trace root and remove the execution traces. When we need those intermediate trace roots, we can provide proof of inclusion.

With this, ER would size would be reduced and so is bundle size. Ofcourse there is new proof added to the Fraud proof but this is totally okay since Fraud proofs should not happen as often as Bundle submission.

Thoughts @NingLin-P ?

NingLin-P commented 10 months ago

Make sense to me, constant size ER is great! Do notice we still need to keep track of the execution trace in the aux storage so that the honest operator can find the exact mismatch of the bad ER's execution trace.

vedhavyas commented 10 months ago

Yeah that is fine. Its not unbounded and its required.

I have also noticed that inboxed_bundles could take the same approach. Then the ER is truly constant sized irrespective of number of bundles.

cc: @dariolina

nazar-pc commented 10 months ago

I recall we considered this and it caused issues when trying to prove invalid execution, but the design has changed quite a bit, so I'm not sure if it is still applicable.

NingLin-P commented 10 months ago

There are some checks of inboxed_bundles (i.e. the bundle_extrinsic_root) performed at the consensus chain, if we replace inboxed_bundles with a merkle root then we will need another fraud proof. And this also complicated other invalid bundle fraud proofs since they can't use the inboxed_bundles field directly during their verification.

The size of inboxed_bundles is bounded by the weight/size limit of the consensus chain and the bundle_slot_probability, so a merkle root doesn't reduce much size IMO.

dariolina commented 5 months ago

There was another suggestion to remove bundle_extrinsic_root and bundle_digest see(https://subspacenetwork.slack.com/archives/C04MKMFNE48/p1698329757770009)

NingLin-P commented 5 months ago

I recall we considered this and it caused issues when trying to prove invalid execution

Thinking on this more, there is indeed an issue about removing the execution trace and only keeping the execution trace root in the ER, namely the honest operator only knows the trace root is mismatched but it can't find the exact mismatched point of the trace since the bad ER's full execution trace is not revealed.