Working backwards to verify witness proofs

[swcurran]

One other aspect of witness validating from the client side.

For the logic to work in the current spec, I need to work backwards not forwards which isn't clear.

If I start at logEntry-1 - it may not have WitnessProofs as they exist only on the latest -N entry because it is the same witness through the entire chain.

But another witness that was only enabled for a singular (or a period of time) will show up partially in the streams which I can only determine in reverse order.

i.e.
N = last entry.
N- = full witness proof
(N-1)- = no proofs as no witness change
(N-2)-entryHash> = one proof as a witness was removed

If I go forward - then I don't know future proof records that only exist for the LAST record they witnessed

[swcurran]

Yes, that is correct -- for the witness processing. There is a document on the did:webvh information site about implementing a resolver that goes over the high level logic. In a nutshell:

• Fully process the DID Log Entry file, tracking where you need witnessed entries -- e.g. each versionId the witness keys for that entry.
• If any witnessed entries need to be verified, retrieve the witness.json file and verify the proofs, the versionIds and the witness keys.
• Loop through the list of tracked entries to verify that there are current or later proofs from the keys needed to meet the threshold to indicate an entry is "witnessed".

Thus, don't do the witness checking as you go, do it as a follow up after completing the Log verification.

Does that make sense?

I'd welcome comments from other implementors!

[stormer78]

suggestion in the spec is to use the process above, from an implementation perspective we are doing it the other way around as it creates a faster validation flow.

(EDITED: the following won't due to possibility of future proofs for unreleased LogEntries)

1. Load the witness proofs, create a state table of witness proofs to version-id mapping (Single pass - O(n))
2. Load the did.jsonl LogEntries (in parallel with the above)
3. For each LogEntry validate LogEntry and check against the witness proof state table (and validate witness proof at that time) (Requires a single pass, previous LogEntries do NOT need to be stored in memory (important for DOS protection)
4. At the conclusion of LogEntry validation (EOF) then validation is 100% complete and no reload of data required

Pass the result back to the client
The currrent suggested method requires:

1. Load the did.jsonl
2. Process LogEntries (one pass)
3. Load the witness proofs and build a state table of some kind (one pass)
4. Go back and reload or cache the LogEntries in memory and validate the proofs (several things you can do here, but at a minimum requires another pass through the LogEntries or caching the LogEntries in memory during validation)
5. At conclusion pass the result back top the client

Again - not a hill to die on, but sharing optimisations similar to other issue may help in larger webvh files.

[stormer78]

Actually it gets a little harder in the current spec.

Due to potential of witness proofs for unpublished LogEntries, you need to know the highest published LogEntry versionId so you know when to cut off the latest valid witness proof.

So flow would need to be:

1. Process the LogEntry file, validating each LogEntry as you proceed.
2. When you reach EOF, record the highest versionId
3. Load the Witness Proof file, read it up until the highest versionId from the LogEntry file. Discard anything above (future proofs)
4. Now go back through and validate each versionId with a proof record against the corresponding LogEntry file (another pass through the full file)

[swcurran]

The need for unpublished LogEntry proofs is painful from a logic perspective -- needing to keep the extras. Those proofs can still be verified, but they have to be ignored as counting towards the threshold. Probably the biggest pain of the two file system. Tradeoff of long-lasting extra data in the Log File vs. logic complexity in achieving thresholds. When discussed at the Work Item meeting, the call was to go with the separate file.