Reduce gas costs associated with publishing storage deals

[anorth]

This is a discussion and tracking issue for improvements to deal-related gas costs. The background is filecoin-project/FIPs#535

Changes:

• Market actor batch datacap token transfers #722 (closes Market actor should batch datacap token transfers #662)
• Avoid redundant read/write of allocation/claims HAMT root when unchanged #1030
• Optimise the datacap actor's allowance data into the same HAMT as balances #1101
• Defer loading and decoding the parameters block until it's actually used #1066
• Market: avoid loading deals twice during VerifyDealsForActivation #1103
• Market: avoid loading deal proposals twice during activation #1102

[anorth]

One of the challenges here has been lack of tooling (re: filecoin-project/ref-fvm#1080). Without tooling we don't understand where the costs are coming from. I have been working on FVM instrumentation and analysis tooling in https://github.com/anorth/fvm-workbench. While not yet ready for general use yet (depends on some unreleased changes to FVM and actors), I do have some early results.

One small part of deal publishing is the datacap transfer (including receiver hook call). I have instrumented a VM test just of this function. In the very basic case of an initially empty state (no existing allocations), here's a breakdown of gas usage:

Span[Root, self: {sum=70,200, OnChainReturnValue=70,200, none=0}, total: {sum=9,556,695, OnBlockLink=3,917,825, OnBlockOpenBase=2,305,489, wasm_exec=1,983,364, OnSyscall=1,120,000, OnHashing=94,065, OnChainReturnValue=70,200, OnMethodInvocation=47,712, OnBlockOpenPerByte=9,839, OnBlockCreate=7,634, OnBlockRead=568, OnBlockStat=0, none=0}]
Span[1-Call(103->f07::15), self: {sum=5,987,911, OnBlockLink=2,101,256, OnBlockOpenBase=1,627,404, wasm_exec=1,538,736, OnSyscall=686,000, OnMethodInvocation=23,856, OnBlockOpenPerByte=6,027, OnBlockCreate=4,295, OnBlockRead=337, OnBlockStat=0}, total: {sum=9,486,495, OnBlockLink=3,917,825, OnBlockOpenBase=2,305,489, wasm_exec=1,983,364, OnSyscall=1,120,000, OnHashing=94,065, OnMethodInvocation=47,712, OnBlockOpenPerByte=9,839, OnBlockCreate=7,634, OnBlockRead=568, OnBlockStat=0}]
Span[2-Span(TokenLib-TransferFrom), self: {sum=4,173,472, OnBlockLink=2,101,256, wasm_exec=917,472, OnBlockOpenBase=813,702, OnSyscall=336,000, OnBlockCreate=2,688, OnBlockOpenPerByte=2,247, OnBlockRead=107}, total: {sum=4,173,472, OnBlockLink=2,101,256, wasm_exec=917,472, OnBlockOpenBase=813,702, OnSyscall=336,000, OnBlockCreate=2,688, OnBlockOpenPerByte=2,247, OnBlockRead=107}]
Span[3-Span(ReceiverHook), self: {sum=4,622,283, OnBlockLink=1,816,569, OnBlockOpenBase=1,220,553, wasm_exec=855,164, OnSyscall=602,000, OnHashing=94,065, OnMethodInvocation=23,856, OnBlockOpenPerByte=5,387, OnBlockCreate=4,379, OnBlockRead=311, OnBlockStat=0}, total: {sum=4,622,283, OnBlockLink=1,816,569, OnBlockOpenBase=1,220,553, wasm_exec=855,164, OnSyscall=602,000, OnHashing=94,065, OnMethodInvocation=23,856, OnBlockOpenPerByte=5,387, OnBlockCreate=4,379, OnBlockRead=311, OnBlockStat=0}]
Span[4-Call(7->f06::3726118371), self: {sum=3,498,585, OnBlockLink=1,816,569, OnBlockOpenBase=678,085, wasm_exec=444,628, OnSyscall=434,000, OnHashing=94,065, OnMethodInvocation=23,856, OnBlockOpenPerByte=3,812, OnBlockCreate=3,339, OnBlockRead=231, OnBlockStat=0}, total: {sum=3,498,585, OnBlockLink=1,816,569, OnBlockOpenBase=678,085, wasm_exec=444,628, OnSyscall=434,000, OnHashing=94,065, OnMethodInvocation=23,856, OnBlockOpenPerByte=3,812, OnBlockCreate=3,339, OnBlockRead=231, OnBlockStat=0}]

The Root span gives the totals, with breakdown by the label attached to each gas charge: 9.5M gas total, with 3.9M attributed to block link (writing new blocks to store), 2.3M for block open (reading), and <2M WASM execution. The gas charge of block link is dominated by a fixed per-block charge, rather than per-byte increment.

The subsequent spans show smaller areas of the code:

• The first call is client->datacap TransferFrom
• The next span wraps the token library's state updates
• The next span wraps calling the receiver hook
• The last call span is datacap->verifreg receiver hook.

The receiver hook in this case creates the verified registry allocation record, to be later claimed by the provider for QAP.

I'm investigating opportunities to reduce costs here, but we should also investigate the entire PublishStorageDeals flow.

[anorth]

The HAMT implementation redundantly writes the root node to storage when flushed, even if unchanged (filecoin-project/ref-fvm#1443). This happens in the verified registry actor when receiving tokens for a new allocation or claim (but not both at the same time). Fixed in #1030.

[anorth]

I have completed a trace of a simple PublishStorageDeals method. This message carries 5 deals but is against an otherwise empty state.

• unverified deals (total 49M gas)

total: {sum=48,954,737, wasm_exec=14,756,184, OnBlockLink=9,317,025, OnVerifySignature=8,186,460, OnBlockOpenBase=8,137,020, OnSyscall=5,320,000, OnHashing=2,821,950, OnMethodInvocation=333,984, OnBlockOpenPerByte=33,936, OnBlockCreate=33,705, OnChainReturnValue=11,700, OnBlockRead=2,773, none=0, OnBlockStat=0}

• verified deals

total: {sum=103,424,915, OnBlockLink=29,989,883, wasm_exec=29,369,224, OnBlockOpenBase=20,206,933, OnSyscall=11,452,000, OnVerifySignature=8,186,460, OnHashing=3,449,050, OnMethodInvocation=572,544, OnBlockOpenPerByte=94,973, OnBlockCreate=85,817, OnChainReturnValue=11,700, OnBlockRead=6,332, OnBlockStat=0, none=0}

Some notable points:

• The total of ~103M gas for five deals is a lot lower than values observed against mainnet state, from which we might infer that traversing and updating large data structures of deals is a large part of the cost.
• The big items are
  • unverified: reading+writing storage 35%, WASM execution 30%, signature verification 16%, syscalls 10%
  • verified: storage 50%, WASM 28%, syscalls: 11%, signature verification: 8%
• The datacap transfers together total ~30M gas, so we might expect batching (Market actor batch datacap token transfers #722) to be quite effective when the deals have the same client
• 5 calls to MarketNotifyDeal on the account actor account for 2M gas (4% of unverified total), a method which isn't even implemented. Most of this cost is reading/decoding the parameters block which is ignored

There's most investigation to do to find which storage and execution operations are most expensive.

[anorth]

The datacap actor writes multiple blocks when processing a TransferFrom operation. We can probably significantly reduce the gas costs associated with datacap by restructuring that state. See #1101 (a tracking issue for filecoin-project/actors-utils#188)

[anorth]

With #722 merged, I've an updated trace of publishing verified deals.

total: {sum=63,326,639, wasm_exec=20,529,984, OnBlockLink=13,315,744, OnBlockOpenBase=10,578,126, OnVerifySignature=8,186,460, OnSyscall=7,000,000, OnHashing=3,198,210, OnMethodInvocation=405,552, OnBlockCreate=51,818, OnBlockOpenPerByte=45,318, OnChainReturnValue=11,700, OnBlockRead=3,728, OnBlockStat=0, none=0}]

So a total of 103M -> 63M 🎉

[anorth]

This issue is now just a tracking issue for a set of mitigations, each written up separately. I think we can close this now as it's not actionable. FYI @jennijuju

[anorth]

Re-opening this as a venue for discussion about optimisations here, beyond what's captured in the referenced issues.

See also #1276 about balancing the single vs aggregate ProveCommit (which includes deal activation) and #1278.

[anorth]

We optimised much more here, primarily through batching. The changes will land in nv21.