Verifiable Batch Queries

​

Abstract

​

Commitment Properties

• Hiding - The commitment does not reveal any information about the operation. The hashes in the commitment section don’t reveal inputs or outputs, while the proof section reveals only the identity of the node that performed the computation.
• Binding - It is impossible to change any inputs or outputs of the operation without invalidating the commitment.
• Succinct - The commitment is small enough to be stored cheaply (e.g. on a blockchain), and disputing the result does not require storing and transferring the resulting data.
• Deterministic - The same query results in the same commitment, as long as the query itself is deterministic.
• Reproducible - Given the same inputs a third party can repeat the query, arrive at the same results, and validate them against the original commitment.
• Non-repudiable - A node cannot deny performing the operation, as the commitment is signed with the key tied to the node’s identity.
• Composable - Computation split into several steps, possibly executed by nodes belonging to different parties (e.g. when joining datasets of different owners), produces commitments that compose into one final commitment. In case of a dispute the responsibility can be assigned to the specific party, not only to the party that aggregated the final result.
• Multi-protocol - The commitment structure can be reused across different protocols without significant alterations.

​

Response Structure

{
  "input": {
    "query": "select * from foo",
    "queryDialect": "SqlDataFusion",
    "dataFormat": "JsonAoS",
    "schemaFormat": "ArrowJson",
    "datasets": [{
      "id": "did:odf:fed0..ee02",
      "alias": "foo",
      "blockHash": "f162..3e0b"
    }]
  },
  "output": {
    "data": [
      {"foo": 1, "bar": "A"},
      {"foo": 2, "bar": "B"}
    ],
    "dataFormat": "JsonAoS",
    "schema": {"fields": [...]},
    "schemaFormat": "ArrowJson"
  },
  "subQueries": [{
    "input": {...},
    "subQueries": [...],
    "commitment": {...},
    "proof": {...}
  }],
  "commitment": {
    "inputHash": "f162..3e0b",
    "outputHash": "f162..baaf",
    "subQueriesHash": "f162..8dae"
  },
  "proof": {
    "type": "Ed25519Signature2020",
    "verificationMethod": "did:key:fed0..3e41",
    "proofValue": "u3MvG...ouQk"
  }
}

​

Input

• The query and its dialect
• All parameters that affect the output, including the requested data and schema formats
• The list of queried datasets, each with:
  • id - the unique identifier of the dataset
  • alias - the name under which the dataset was referred to in the query
  • blockHash - hash of the block that represents the exact state of the dataset the query was executed against

​

Output

​

Sub-queries

​

Commitment

• inputHash - multihash(canonicalize(input))
• outputHash - multihash(canonicalize(output))
• subQueriesHash - multihash(canonicalize(subQueries))

​

Proof

• type - signature scheme (e.g. Ed25519Signature2020)
• verificationMethod - DID of the node, from which the public key used to verify the signature can be derived
• proofValue - multibase(sign(canonicalize(commitment)))

​

JSON Hashing

​

Response Validation

1. Verify that the proof.verificationMethod DID belongs to the node the data was requested from
2. Verify commitment.outputHash by recomputing the hash
3. Verify commitment.inputHash by recomputing the hash
4. Verify commitment.subQueriesHash by recomputing the hash
5. Verify the signature in proof.proofValue using:
   • Message: canonicalize(commitment)
   • Public key: key_from_did(proof.verificationMethod)
6. Repeat steps 3-5 recursively for every entry in subQueries

​

Storing Commitments

• input
• subQueries
• commitment
• proof

• input - provides reproducibility
• commitment - seals the response against tampering
• proof - adds non-repudiation via signature
• subQueries - provide the above for multi-party computations

​

Dispute Resolution

1. Consumer submits a claim to the verifier, providing the input, subQueries, commitment, and proof sections
2. Verifier obtains the datasets listed in input.datasets at the specified block hashes
3. Verifier validates the claim according to the Response Validation rules
   • If any check fails, the claim is rejected as invalid
4. Verifier checks that all nodes that signed the subQueries are known (registered) nodes
   • If an unknown node is found, the claim is accepted and the blame is assigned to the root node for using a bogus node to compute part of the response
5. Verifier generates the logical query plan and checks that it is identical or equivalent to the plan composed from the subQueries
   • If the plan does not correspond to the original query, the claim is accepted and the blame is assigned to the root node for providing a malicious query plan
6. In a bottom-up fashion, verifier repeats all computation steps using their input sections and compares hashes of the outputs to the corresponding commitment.outputHash values
   • If a hash doesn’t match, the claim is accepted and the blame is assigned to the node that signed the corresponding commitment for providing malicious output data

​

Use in Other Protocols