candidate Fuzzer Protocol feature: GetWorkReportDerivation

[sourabhniyogi]

As a feature of the JAM v1 fuzzer protocol, there is a RefineBundle mapping to WorkReport feature that enables JAM implementations to conform on refining/assuring processes. The fuzzer target should:

1. Verify the bundle and execute refine, which results in segments which are erasure coded into segment_chunks
2. Build the Availability Specifier
   • Part 1: Compute bClubs and bundle_chunks the erasure coding of the JAM codec bundle
   • Part 2: Compute sClubs
   • Part 3: Compute u Erasure Root
   • Part 4: Compute e Exports Root
3. Generate a work report, which includes the Availability Specifier.

However, at present, if implementations disagree on their WorkReport, it is difficult for two implementations to know where they differ in this multi-step process. So we propose to add a GetWorkReportDerivation feature [analogous to GetState (providing full key-value pairs)] with all the key components necessary to compute the Availability Spec contained within the work report:

• the exported segments
• the BClubs hashes
• the SClubs hashes
• the erasure coded BundleChunks
• the erasure coded SegmentChunks

We request feedback on whether this is too little or too much to debug discrepancies.

It is natural to have a few teams do a proof-of-concept of this new fuzzer feature before we add it to the v1 spec.

Availability Specifier Guide

Below is a step-by-step guide on Availability Specifier construction.

For simplicity we will assume:

• 10-byte work package bundle b 0x1421199addac7c87873a -- this is intended to be a short version of a "real" JAM codec version of a bundle
• N 4104-byte distinct segments formed by a hash chain:
  • hash("") = 0e5751c026e543b2e8ab2eb06099daa1d1e5df47778f7787faab45cdf12fe3a8
  • hash(hash("")) = 7c09f7c4d76ace86e1a7e1c7dc0a0c7edcaa8b284949320081131976a87760c3
  • ...

with 3 EXPORT segments: (which can of course be imported segments and FETCHed)

segment 0: 0e5751c026e543b2e8ab2eb06099daa1d1e5df47778f7787faab45cdf12fe3a87c09f7c4... (4104 bytes)
segment 1: 3e34a14d4b4f0ce28228429970f96404dde7c29005f1f18c6646144a897d45e78d621845... (4104 bytes)
segment 2: aa89f2c6cbfa194e38e1222c3e9a7ca8ce7212ca968f23cf70ea9802ea98c1f5680eb049... (4104 bytes)

The endpoint will be the package_spec of a work_report

{
  "hash": "0x29dd530e106750dd9b7d8a92875b47577f025d3ca5ad7070f82a92a2a947b40f",
  "length": 10,
  "erasure_root": "0xc5ea57494802ff617a5e01abf6a8bec9b5f1e46e9ef9ba5033370c808d897807",
  "exports_root": "0x8f14f9fdf5f8b1315d983d67048fbb059c67d914522ea349e987bba2c5d837c9",
  "exports_count": 3
}

A full step-by-step derivation of a package_spec with supporting pictures may help to achieve alignment and is shown below. See if you can find a mistake!

Part 1. Compute b-club

Step 1. Pad b to a multiple of W_E (4).

This will be 12 bytes.

Step 2. Compute the erasure coding of the above

Step 3. Compute hash of each of the shards

This will form 6 hashes.

Output:

Padded 10 bytes to 12 bytes (multiple of 4 bytes) => 1421ddac873a199a7c870000

buildBClub hash 0: 0x41cb1628497c88e0004b0fffc88e80ed5eb71348df7082220e86bd9b2bcde162 Shard: 1421ddac873a (6 bytes)
buildBClub hash 1: 0xacb9cdcaa760268a2205d6a82d74219da6ee413f95dd5b1fd9fdb339b4e7741f Shard: 199a7c870000 (6 bytes)
buildBClub hash 2: 0xe1a0b3e80b8705a4bf0e20555e7f3511b2b99b023199db917270062859573a8f Shard: c75ae79a6a22 (6 bytes)
buildBClub hash 3: 0x929bc730d37c379dec6fd0ba37f86910935f1babae0fca1b92dc710417972bcd Shard: cae146b1ed18 (6 bytes)
buildBClub hash 4: 0xf9738461a5c23be1fe448a11f7d20024c2f1108a0508ec2b2d6642efaa909afc Shard: edadf41bf3c3 (6 bytes)
buildBClub hash 5: 0x9b5da282f5066e605b9408aeda9775d9c6119c77b1f816f91bde824abbf2f992 Shard: e016553074f9 (6 bytes)

You can see this part in bClubs

Part 2: Compute s-club

Step 1. Generate page proofs for the N Exported segments

Note: As N increases to 65, 129, ... an additional page proof appears.

Step 2. Compute the EC encoding of the above

Step 3. Compute the WBT of the above

Output:

buildsClub hash 0: 0x5694b94dbdc251985cebf51da2ffd483556c024f5e6e7c251b1d6f0facaf1bae nchunks: 4 (2052 bytes/chunk)
buildsClub hash 1: 0xbc6df7e3aa9623d58d786b7beab9693389c838e0bf83a4292aa452244e11eb2e nchunks: 4 (2052 bytes/chunk)
buildsClub hash 2: 0x5edd986939163ca6b36b86513b73c41bcbf91cc1613831745b24b6d1ae421086 nchunks: 4 (2052 bytes/chunk)
buildsClub hash 3: 0x2b29127b8d2e86e43c46aad75bc7ccdc75a158ce8fc2d47c2581e58128257bb3 nchunks: 4 (2052 bytes/chunk)
buildsClub hash 4: 0xd0fd5b4d07cba6bcd1982842f729efb8215c9df61559402f6cabf4422155c0be nchunks: 4 (2052 bytes/chunk)
buildsClub hash 5: 0x66635b15bee67f77b74f67aee68d8e1255b712443fab89eb03451104f73af2c7 nchunks: 4 (2052 bytes/chunk)

You can see this part in sClubs

Part 3. Compute u Erasure Root

Zip Part 1 (Step 3) + Part 2 (Step 3) together:

Make a WBT out of the leaves above:

like so:

Output:

bclub-sclub pair 0 = 41cb1628497c88e0004b0fffc88e80ed5eb71348df7082220e86bd9b2bcde1625694b94dbdc251985cebf51da2ffd483556c024f5e6e7c251b1d6f0facaf1bae
bclub-sclub pair 1 = acb9cdcaa760268a2205d6a82d74219da6ee413f95dd5b1fd9fdb339b4e7741fbc6df7e3aa9623d58d786b7beab9693389c838e0bf83a4292aa452244e11eb2e
bclub-sclub pair 2 = e1a0b3e80b8705a4bf0e20555e7f3511b2b99b023199db917270062859573a8f5edd986939163ca6b36b86513b73c41bcbf91cc1613831745b24b6d1ae421086
bclub-sclub pair 3 = 929bc730d37c379dec6fd0ba37f86910935f1babae0fca1b92dc710417972bcd2b29127b8d2e86e43c46aad75bc7ccdc75a158ce8fc2d47c2581e58128257bb3
bclub-sclub pair 4 = f9738461a5c23be1fe448a11f7d20024c2f1108a0508ec2b2d6642efaa909afcd0fd5b4d07cba6bcd1982842f729efb8215c9df61559402f6cabf4422155c0be
bclub-sclub pair 5 = 9b5da282f5066e605b9408aeda9775d9c6119c77b1f816f91bde824abbf2f99266635b15bee67f77b74f67aee68d8e1255b712443fab89eb03451104f73af2c7

This maps into the erasure_root

Part 4: Compute e Exports Root

Using the same 3 segments, use CDT to compute the exports root:

M(s) - CDT of exportedSegment
[Branch Root]: 0x8f14f9fdf5f8b1315d983d67048fbb059c67d914522ea349e987bba2c5d837c9
  [Branch Left]: 0x6d7f4852584798717ca1d53ec9cc1a5eb448670cca59d8f077a8811ad94178ea
    [Leaf Left]: 0xd52599e030b6437824ada5a12ee5028c2ee40c7b911ab545ee1bb923f7e61bde
    [Leaf Right]: 0x1f7d61d4573135f534e2ad31a8d4e6186efdcea59d67fc33d30399ffe60c4503
  [Branch Right]: 0x17f69698120396ac53ef94016028054b571beead9766d1dc7ac44d0fd30f4aac
    [Leaf Left]: 0x0e987f71556195dd61e5f8469d217e244eb6a9ff2c596c111427e00970a3e0ee
    [Leaf Right]: 0x0000000000000000000000000000000000000000000000000000000000000000

This maps into the exports_root of the Availability Spec.

Putting it together in the fuzzer

We will update this a sample test case shortly.

[danicuki]

@sourabhniyogi
Is this doc updated to the latest GP version (0.7.2)?

If so, I can start testing against this

[danicuki]

Shouldn't your hash chain implementation take mid-hash binaries? 4014 is not divisible by 32. So the second hash should start in the middle of the 129th hash, not on the 130th hash as it appears to be

[danicuki]

Part 1, step 2 for us returns (erasure coding using the same algorithm that matches test vectors):

["0x1421199addac", "0x7c87873a0000", "0x23f7c744f077", "0x4b5159e42ddb", "0x1eeea558756f", "0x76483bf8a8c3"]