Ordered Accumulation

[gavofyork]

Allowing ImportSpecs to use a WorkPackageHash rather than a SegmentRoot means that exports can be referenced prior to calculating their content. This is helpful when building Work Packages prior to some dependent Work Package has been guaranteed (from the perspective of the builder, at least).

While a guarantor might have an idea of the SegmentRoot for a given, recent and unreported, WorkPackageHash, it cannot prove it. Nor can auditors be expected to come to the same answer, since they may be unsynced or synced to a different fork. The only option is to check on-chain any correspondence which the guarantor asserts.

If the correct content is known, then could be done by the service's own code in Accumulate, which could track the content canonically. The drawback to this is that (essentially) the same logic and storage would need to be designed for each service which wanted to do this. Furthermore, some clever means of authorization would need to happen to allow the guarantor to substitute into the WorkPackage a SegmentRoot where it finds a WorkPackageHash without breaking the authorization (which may depend on a hash of the package). Finally there is little protection against errant or lazy guarantors from inserting arbitrary SegmentRoot values, and such guarantors would be rewarded for such behaviour through additional WorkReports they can guarantee, which would be perfectly auditable, but fail within Accumulation without any recourse.

Instead, it may be better to allow this conversion to happen in-protocol rather than in-service, thus avoiding the problem of rewarding a guarantor for an unaccumulatable WorkReport through an incorrect WorkPackageHash/SegmentRoot substitution.

To do so it mostly relatively straight-forward: instead of happening directly in the WorkPackage, any correspondences (pairs of WorkPackageHash and SegmentRoot) would be placed in a new field in the WorkReport. These would be used to dynamically substitute during audit, but not be audited themselves. They would be checked on-chain prior to Accumulate, and accumulation would not proceed unless all such correspondences are from WorkReports which are already accumulated.

56 specifies an earlier iteration of this idea. Unfortunately it has a big flaw: if a WorkReport specifies an invalid SegmentRoot, and is relied upon for a WorkPackageHash/SegmentRoot substitution (SRsub) in some WorkPackage importing one of its exports, then nothing at present prevents the latter WorkReport being accumulated prior to the former. This implies that while the former will succumb to the auditing process, with the chain reverted to immediately prior to its accumulation and the WorkReport itself eliminated, the latter would quite possibly stay accumulated.

This is because we do not provide for any strong order of accumulation: while we can and do order reporting and thus the beginning of the availability process, we cannot know or force the time when availability would conclude (it may never) and thus have to be prepared to accumulate out of order.

By providing Ordered Accumulation, we can both provide secure WorkPackageHash/SegmentRoot substitution and avoid the need for service code to deal with out-of-order (or orphaned) accumulation of work-results.

Overview of Changes

Off-chain

• ImportSpecs in WorkPackages should include a discriminator (encoded with the MSB of the index to avoid any bandwidth/storage overhead) indicating that the hash is a WorkPackageHash rather than a SegmentRoot.
• Guarantors, on seeing the bit set, should check to see if they have already seen the WorkPackage and its corresponding WorkReport (and SegmentRoot). If not, the WP's imports are to be considered unavailable and the guarantor should ignore it until it is seen.
• For all such WPHs, we thus assume guarantors have built a sequence of pairs of WPHs and SRs ordered by WPH.
• There should be an extra field Segment Root Lookup in the WorkReport which is defined as this sequence.
• Auditors need not have seen any of the WPHs in ImportSpecs, but will:
  1. Check all such WPHs from the WorkPackage's ImportSpecs are contained in the WorkReport's Segment Root Lookup.
  2. Check that there are no unused entries in the Segment Root Lookup.
  3. Check that the size of Segment Root Lookup is no greater than 8.
  4. Check that the order of the Segment Root Lookup is correct.
  5. Utilize the corresponding SegmentRoot in the Segment Root Lookup should they find an ImportSpec using a WPH.

On-chain

Two additional state items:

• Accumulated: [[(WorkPackageHash, SegmentRoot)]]_EpochPhase
• Queue: [WorkReport, [WorkPackageHash]]_:MaxQueue

Let $m = \tau \bmod \mathsf{E}\ ,\quad m' = \tau' \bmod \mathsf{E}$.

For all epoch phases $p: m < p \le m' \text{ modulo } \mathsf{E}$, clear Accumulated of that index.

MaxQueue = 1024. If the Queue is full, then placing an item on it results in the dropping of the first item.

Whenever a WorkReport is scheduled for accumulation, the implied WPH/SR pairing is inserted into Accumulated under the posterior epoch phase $m'$.

A WPH prerequisite is considered fulfilled when it appears in Accumulated. An SR substitution is considered fulfilled when the pair appears in Accumulated. Together they represent the WorkReport's dependencies. An SR substitution whose WPH appears in Accumulated, with a mismatched SR, is considered unaccumulatable and is dropped immediately with the guarantors not rewarded for introducing the WorkReport.

Queue is kept up to date as representing only the not-yet-fulfilled dependencies. Any items in Queue determined as unaccumulatable are dropped. Any WorkReports whose dependencies are completely fulfilled remain in Queue but map to an empty sequence.

We define the dependencies of a WorkReport as the prerequisite WPH (if one exists) together with any WPHs mentioned in the WR's SRL. This may total at most 9 items (1 for the prerequisite and 8 for the SRL).

In a block, for all WorkReports which have just become available and have all dependencies fulfilled (either already in Accumulated or within those just made available), schedule for accumulation. (In this way these take priority over those WorkReports with unfulfilled dependencies or sitting in Queue from previous blocks). This nonetheless implies updating the Accumulated and Queue state items.

Any which are not scheduled for accumulation at this point are placed in Queue under the posterior epoch phase.

Point X:

Repeat The Following while:

• there is gas remaining (the total per-block accumulation gas minus gas used for accumulation so far minus accumulation gas per WR multiplied by the number of WorkReports scheduled for accumulation this iteration is at least accumulation gas per WR); and
• there is at least one WorkReport in Queue which maps to an empty sequence. The Following:
• pick the earliest, lowest WPH WorkReport from Queue which maps to an empty sequence and schedule for Accumulation.

Execute accumulation (not including OnTransfer).

Go to Point X until no further accumulation happens.

Execute all implied OnTransfers.

[AlistairStewart]

This looks like it should work.

So everything in accumulated that hasn't been accumulated is scheduled to accumulate this block and therefore it is not too misleading a name? We are guaranteed to run accumulate on a dependency before the WP itself though a dependency failing accumulation can unavidably cause a sequence of accumulation failures. It seems like it is also reasonable to assume that a WP with a correct WR on which accumlate is run but fails would also fail if it was guatanteed later.

There is still the question of what the builder knows so that this is useful. It's not if they know the WR for the WP depedency. So maybe they have information from some other builder who knows the dependency WP but not the result of its execution, possibly because that builder doesn't have that WPs depencies yet. Which sounds reasonable so this may indeed be useful. It seems like they (the first bulder) would also need a proof, possibly some light client proof from the dependency WPH that the data they are asking for is what they need.