Delegated CAS / Zero knowledge CAS

[AaronDGoldman]

Delegated CAS

@mohsin
also see Proposal for CAS Scaling - #6 by AaronDGoldman

API endpoint

POST: https://ceramic-node/cas?event=${cid}

In the future, we can consider adding a GET version that returns the anchor status of a particular CID without queueing a new anchor request:

• 404 not found for a CID for which anchoring was not requested
• 200 with the anchor response described below.

Responses

When an anchor request for an event is queued:

Content-Type: application/json
Status: 202

{
  "event": ${cid},
  "status": "pending"
}

When an anchor request has been anchored:

Content-Type: application/vnd.ipld.car

CAR file containing:
  Detached Time Event
  Proof block
  Merkle tree nodes along the path

A Detached Time Event contains enough information for a requesting node to construct the full Time Event. It does not include the id field, and its CID is the root CID of the CAR file in the response.

prev below is the CID of the event for which anchoring was requested.

{
  "path": "0/0/0/0/0/0/0/0/0/0",
  "prev": {
    "/": "bagcqceraplay4erv6l32qrki522uhiz7rf46xccwniw7ypmvs3cvu2b3oulq"
  },
  "proof": {
    "/": "bafyreidgj7twe64g6ofhjt53zw3qfv375e4fgpsuak3m5btxo4dy24dn6u"
  }
}

Proof block:

{
  "chainId": "eip155:1",
  "root": {
    "/": "bafyreicbwzaiyg2l4uaw6zjds3xupqeyfq3nlb36xodusgn24ou3qvgy4e"
  },
  "txHash": {
    "/": "bagjqcgzax554ofnatxvdc54gnlcpykkkzgaa5yvutye4kx2wa6cxtp536fma"
  },
  "txType": "f(bytes32)"
}

Sample Merkle tree node:

[
  {"/": "bafyreia6jc7kwhb755nsta4esi3bcvn5lsoghcmyxtgc3iagexnvve2zz4"}, 
  {"/": "bafyreiandp4yj4rjzxnyk37kbsfg7vohc3ppuojgwj5r77edbcrjxzaanq"}
]

Anchor Request Store

CREATE TABLE request (
    prev CID,  -- CID of the event for which an anchor has been requested
    path text, -- path of the CID through the Merkle tree
    proof CID  -- CID of the anchor proof block
    PRIMARY KEY(prev)
)

Anchoring Workflow

New Request

• When a new anchor request comes in, create a row in the request table with the event CID as prev.
• Respond with status: pending.

Batching for Anchor

At some configurable anchoring period:

• Walk the request table for requests that do not contain a path and proof.
  • Keep track of the maximum and minimum row IDs, and iterating in CID order.
  • Construct a Merkle tree using the CIDs:
    • Calculate but do not durably store the intermediate Merkle tree nodes.
    • Calculate the root CID.
• Construct and sign the Ethereum transaction containing the root hash.
• Submit the transaction to Ethereum.
• Wait/poll with configurable delay/retries until the transaction is in a block and the block is final.
  • If the transaction fails, wait for the next iteration of batching.
• Once the block is finalized:
  • Store the proof block pointing to the now finalized transaction.
  • Walk the request table in CID order from the min row ID to max row ID from earlier.
    • Calculate and store the intermediate Merkle tree nodes.
    • Calculate and store path and proof in the request table for each event.
• If at any point, this process errors out or crashes, you can safely restart from the beginning.

Once proof and path have been written for an event, it is now considered anchored.

Polling Response

When a polling request for an event CID arrives:

• If path and proof are NULL, respond with status: pending.
• If path and proof are present, response with a CAR file containing the Detached Time Event ((root)), proof block, and Merkle tree nodes along the path.

Client Responsibilities

Once a requestor receives the Detached Time Event, they can use their knowledge of the Data Event to add the id field and generate a full Time Event. It is the client’s responsibility to then durably store this Time Event and distribute it around the network.

Even if CAS has a catastrophic failure, the Time Events will still be available to the network. If no node retrieved the Detached Time Event and constructed the Time Event before CAS’s catastrophic failure, their subsequent polling will queue the event for anchoring again. A full Time Event will be constructed after the subsequent anchor.

Subtree Anchoring

If the CID that the client is requesting to be anchored is the root of a sub-tree instead of a single event, then it is the client’s responsibility to keep track of the requests in their local Merkle tree, and generate Detached Time Events for each of them.

Benefits

Scaling

The amount of work that CAS needs to do with scale with the number of Ceramic nodes and not the number of Ceramic events, like it does today.

Privacy

Should a client include in their sub-tree an event with 256 bits of randomness, then this becomes zero-knowledge anchoring.

Risks

Possible duplicate anchoring

While a duplicate anchor is not a problem per se, it is a change from existing behavior where CAS attempts to prevent multiple anchors for the same event.

[mohsin]

With the way the request table is laid out, the Detached Time Event will need to be re-constructed for every response for an anchored CID.

The request table can be simplified further by having just two fields: event for the event CID, and a NULLABLE timeEvent field for the CID of the Detached Time Event. Once available, the Detached Time Event block would be stored in the block store.

CREATE TABLE request (
    event CID,     -- CID of the event for which an anchor has been requested
    timeEvent CID  -- CID of the Detached Time Event
    PRIMARY KEY(event)
)

[spencer]

I think the big complexities here are going to be around how the new HTTP endpoint and behavior will interact with the existing API and behavior. For example, this forum post says the CAS will use a request table in the SQL database, but the existing CAS already has a request table with a different schema that stores a different type of request that needs different logic to handle. We need to figure out how the CAS should behave when it has a mixture of old-style, one-per-write requests, and new-style, one-per-node requests, at the same time.

[AaronDGoldman]

It would need to be a new Api and probably its own table.

If a node asks for the status of an anchor for a single event we should respond with a time event.

Time Event

{
  "id": {
    "/": "bagcqceraplay4erv6l32qrki522uhiz7rf46xccwniw7ypmvs3cvu2b3oulq"
  },
  "path": "0/0/0/0/0/0/0/0/0/0",
  "prev": {
    "/": "bagcqceraplay4erv6l32qrki522uhiz7rf46xccwniw7ypmvs3cvu2b3oulq"
  },
  "proof": {
    "/": "bafyreidgj7twe64g6ofhjt53zw3qfv375e4fgpsuak3m5btxo4dy24dn6u"
  }
}

If a node asks for the status of an anchor for a localy generated tree we should respond with a detached time event.

Detached Time Event

{
  "path": "0/0/0/0/0/0/0/0/0/0",
  "prev": {
    "/": "bagcqceraplay4erv6l32qrki522uhiz7rf46xccwniw7ypmvs3cvu2b3oulq"
  },
  "proof": {
    "/": "bafyreidgj7twe64g6ofhjt53zw3qfv375e4fgpsuak3m5btxo4dy24dn6u"
  }
}

We leave off the id field to make a Detached Time Event. Since the tree may contain events from many streams. The node must keep its own local tree which can be combined with the detached time event to make the full time events for each anchored data event. I don’t think any of the old APIs or DM tables need to change just adding a new one for the tree roots. The tree building logic would change as the tree would include some hashes from the existing tables and some from the tree roots request table.