Adding Support for Logical Connectives (Operators) on Edges

[SmithSamuelM]

The Simple Grant Language, https://github.com/evernym/sgl is a Domain Specific Language for granting privileges (authorizations) conveyed by verifiable credentials. It includes logical operations such as AND OR etc connectives.

ACDC supports property graphs (PG) which include edges with properties. A common use case for a property graph is to aggregate edges. For example, weighted edges can be used with many decision making algorithms such as multi-attribute decision making where the aggregation of a set of weighted values is used to calculate the final decision.

In general, we can define aggregation operations over a set of edges for general decision making logic on the set of edges. A tree of such aggregations then becomes a hierarchical decision tree. With such trees we can reproduce much of the logic of a DSL like SGL (simple grant language).

One of the early use cases is to address the logic for validating an ACDC with more than one edge. Does the ACDC only validate if both edges, validate ("AND" logic aggregate) , or does the ACDC validate if either edge validates ("OR" logic aggregate).

I suggest that the default, is "AND" logic aggregate which is the safest. But then how to specifiy some aggregate that is not the default.

For these we need to specify the syntax for weighting edges with some common aggregation operators such as AND, OR and maybe even logical negation, NOT. as in a credential is valid only if a chained credential is NOT valid.

This issue is a place holder for suggestions for the syntax of aggregation within the edge section of an ACDC.

[pfeairheller]

Trying to work out how this would look using the vLEI OOR credential as an example (leaving out the rules section for brevity). As described here, the default of AND makes that case pretty straight forward and solves the "chain of trust" issue with the current schema. So we would add the QVI credential as a direct descendant of the OOR as follows:

{
  "v": "ACDC10JSON00011c_",
  "d": "E1qH1E2zo7rnW1Pwm3NuYOXZ1SsVH3yeV2Iifj2wtCgA",
  "i": "did:keri:EZBfSGG5k1CZYk1QH3GXFPtEwLHf0H06zuDUEJRyar1E",
  "ri": "did:keri:EymRy7xMwsxUelUauaXtMxTfPAMPAI6FkekwlOjkggt",
  "s": "EDg-Ji3kmi_G97Jctxeajpmp1-A8gSpeyElm-XCzTxiE",
  "a": {
    "d": "ErmVM5JGLewHJrSqIuhwWktoIlfffh7sHIGAQvtcFSU",
    "i": "did:keri:E70sYPRHygB9aOzgg_xEbI5RCVyRRCAXWG9uHyRNrqYE",
    "dt": "2021-06-09T17:35:54.169967+00:00",
    "LEI": "254900YH3ZCDPE1E5306",
    "personLegalName": "John Smith",
    "officialRole": "Chief Executive Officer"
  },
  "e": {
    "d": "EBDmgKOAEwnMGsofWg2m0l63J1awfJafqJyCzTnVkdSw",
    "legalEntityvLEICredential": {
      "n": "Et2DOOu4ivLsjpv89vgv6auPntSLx4CvOhGUxMhxPS24"
    },
    "qualifiedvLEIIssuervLEICredential": {
      "n": "Et2DOOu4ivLsjpv89vgv6auPntSLx4CvOhGUxMhxPS24"
    }
  }
}

Using the default logic of AND between sibling nodes, this would work. To change that to an "OR" we could group the siblings under an "or" label as follows:

{
  "v": "ACDC10JSON00011c_",
  "d": "E1qH1E2zo7rnW1Pwm3NuYOXZ1SsVH3yeV2Iifj2wtCgA",
  "i": "did:keri:EZBfSGG5k1CZYk1QH3GXFPtEwLHf0H06zuDUEJRyar1E",
  "ri": "did:keri:EymRy7xMwsxUelUauaXtMxTfPAMPAI6FkekwlOjkggt",
  "s": "EDg-Ji3kmi_G97Jctxeajpmp1-A8gSpeyElm-XCzTxiE",
  "a": {
    "d": "ErmVM5JGLewHJrSqIuhwWktoIlfffh7sHIGAQvtcFSU",
    "i": "did:keri:E70sYPRHygB9aOzgg_xEbI5RCVyRRCAXWG9uHyRNrqYE",
    "dt": "2021-06-09T17:35:54.169967+00:00",
    "LEI": "254900YH3ZCDPE1E5306",
    "personLegalName": "John Smith",
    "officialRole": "Chief Executive Officer"
  },
  "e": {
    "d": "EBDmgKOAEwnMGsofWg2m0l63J1awfJafqJyCzTnVkdSw",
    "or": {
      "legalEntityvLEICredential": {
        "n": "Et2DOOu4ivLsjpv89vgv6auPntSLx4CvOhGUxMhxPS24"
      },
      "qualifiedvLEIIssuervLEICredential": {
        "n": "Et2DOOu4ivLsjpv89vgv6auPntSLx4CvOhGUxMhxPS24"
      }
    }
  }
}

Again, this seems pretty straightforward to understand and implement.

"NOT" is a little trickier, but we could collect single siblings under a "not" label to negate it against any siblings of the "not" label. For example:

{
  "v": "ACDC10JSON00011c_",
  "d": "E1qH1E2zo7rnW1Pwm3NuYOXZ1SsVH3yeV2Iifj2wtCgA",
  "i": "did:keri:EZBfSGG5k1CZYk1QH3GXFPtEwLHf0H06zuDUEJRyar1E",
  "ri": "did:keri:EymRy7xMwsxUelUauaXtMxTfPAMPAI6FkekwlOjkggt",
  "s": "EDg-Ji3kmi_G97Jctxeajpmp1-A8gSpeyElm-XCzTxiE",
  "a": {
    "d": "ErmVM5JGLewHJrSqIuhwWktoIlfffh7sHIGAQvtcFSU",
    "i": "did:keri:E70sYPRHygB9aOzgg_xEbI5RCVyRRCAXWG9uHyRNrqYE",
    "dt": "2021-06-09T17:35:54.169967+00:00",
    "LEI": "254900YH3ZCDPE1E5306",
    "personLegalName": "John Smith",
    "officialRole": "Chief Executive Officer"
  },
  "e": {
    "d": "EBDmgKOAEwnMGsofWg2m0l63J1awfJafqJyCzTnVkdSw",
    "not": {
      "legalEntityvLEICredential": {
        "n": "Et2DOOu4ivLsjpv89vgv6auPntSLx4CvOhGUxMhxPS24"
      }
    },
    "qualifiedvLEIIssuervLEICredential": {
      "n": "Et2DOOu4ivLsjpv89vgv6auPntSLx4CvOhGUxMhxPS24"
    }
  }
}

From this basic approach I believe we could achieve any level of complexity with simple nesting. Is this the approach you are thinking of?

[SmithSamuelM]

I like how compact the representation is as a result of overloading labels as operators. My concern is that operators become reserved tokens inside the edge label space. The number of potential operators could be large. (implication, sum, avg, etc). The literature on automated reasoning, multi-constraint, multi-objective etc includes dozens of aggregation operators. Othewise we could always nest so the default is not possible and must be and. Then there are two namespaces. One for operators at the top level and then the next level down are edge labels. Then we would have alternating layers of operator labels and edge labels for trees of branched operators aggregations.

Alternative If we just reserve one label, such as, 'o' for operator then its value is unconstrained and does not materially collide with the label space for edges. We would have then only d and o as reserved labels in the edge label space. To nest then we have a group g, label and then inside the group block is an o field and then edges. This saves us from having to nest two layers (one for operator and one for edge). Anyway haven't dug into alternatives. This removes half the layers since there are not two layers for each aggregate but only one. But don't have an opinion yet. But maybe two layers one for operators and one for edges is logically cleaner eve if more verbose.

[SmithSamuelM]

Proposed Operators

After some thought and reviewing your suggestions. Here is a modified proposal. First some definitions then some examples

Definitions

Label Types

There are three types of labels:

• Reserved Field Labels (Metadata). d for SAID of block o for operator n for Node SAID (another ACDC) w for weight

• Edge Field Map Labels (Single Edges) any value except reserved values above

• Edge-Group Field Map Labels (Aggregates of Edges) any value except reserved values above

Block Types

There are two types of field-maps or blocks that may appears as values of fields within an edge section, e, field either at the top level or nested:

• Edge-Group. An edge-group MUST NOT have a node, n, metadata field. Its non-metadata field values may include other (sub) edge-group blocks, edge blocks or other properties.

• Edge. An edge MUST have a node, n, metadata field. Its non-metadata field values MUST NOT include edge-group blocks or other edge blocks but may include other types of properties. From a graph perspective, edge blocks terminate at their node, n, field and are not themselves nestable. An edge block is a leaf with respect to any nested edge-group blocks in which the edge appears. It is therefore also a leaf with respect to its enclosing top-level edge section, e, field. The ACDC node that an edge points to may have its own edge-groups or edges in that node's own top-level edge section.

The top-level edge section, e, field value is always an edge-group block.

With respect to the granularity of a property graph consisting of ACDCs as nodes, nested edge-groups within a given top-level edge field, e, field of a given ACDC constitute a sub-graph whose nodes are edge-groups not ACDCs. One of the attractive features of property graphs (PGs) is their support for different edge and node types which enables nested sub-graphs such as is being employed here to support the expression of complex logical or aggregative operations on groups of edges (as subnodes) within the top-level edge section, e, field of an ACDC (as supernode).

Operator, o, Field

The meaning of the operator, o, metadata field label depends on which type of block it appears in.

• When appearing in an edge-group block then the operator, o, field value is an aggregating (m-ary) operator, such as, OR, AND, AVG, NAND, NOR etc. Its operator applies to all the edges or edge-groups that appear in that edge-group block.

• When appearing in an edge block then the operator, o, field value is a unary operator like NOT. When more than one unary operator applies to a given edge then the value of the operator, o, field is a list of those unary operators.

Weight, w, field.

Many aggregating operators used for automated reasoning such as weighted average, WAVG, or ranking aggregation, depends on each edge having a weight. To simplify the semantics for such operators, the weight, w, field is the reserved field label for weighting. Other fields could provide other types of weights but having a default simplifies the default definitions of those weighted operators.

Special Unary Operators

Two special unary operators are defined for ACDCs. These are:

Issuer-To-Issuee, I2I, constraint operator and Not-Issuer-To-Issuee, NI2I, constraint operator

Many ACDC chains use targeted ACDCs (i.e. have Issuees). A chain of Issuer-To-Issuee targeted ACDCs in which each Issuee becomes the Issuer of the next ACDC in the chain can be used to provide a chain-of-authority. A common use case of a chain-of-authority is a delegation chain for authorization.

The I2I unary operator when present means that that the Issuee of the node that the edge points to MUST be the Issuer of the current ACDC in which the edge resides. This also means therefore that the ACDC node pointed to by the edge must also be a targeted ACDC.

The NI2I unary operator when present removes or nullifies any requirement expressed by the dual I2I operator descibed above. In other words any requirement that the Issuee of the node the edge points to MUST be the Issuer of the current ACDC in which the edge resides is not applicable. To clarify, when operative (present), the NI2I operator means that a targeted ACDC as node of the associated edge may still be valid even when the Issuee of that node's ACDC is not the Issuer of the ACDC in which the edge appears. Furthermore, the ACDC node pointed to by the edge may or may not be a targeted ACDC.

If both the I2I and NI2I operators appear in an operator, o, field list then the last one appearing in the list is the operative one.

Defaults for missing operators

When the operator, o, field is missing in an edge-group block. The default value for the operator, o, field is AND.

When the operator, o, field is missing or empty in an edge block, or is present but does not include either the I2I or NI2I operators Then:

If the node pointed to by the edge is a targeted ACDC i.e. has an Issuee, by default it is assumed that the I2I operator is appended to the operator, o, field's effective list value.

If the node pointed to by the edge-block is a non-targeted ACDC i.e. does not have an Issuee, by default, it is assumed that the NI2I operator is appended to the operator, o, field's effective list value.

Examples

Defaults

{
  "e": 
  {
    "d": "EerzwLIr9Bf7V_NHwY1lkFrn9y2PgveY4-9XgOcLx,UdY",
    "boss":
    {
      "n": "EIl3MORH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZA",
      "power": "high"
    }
   "baby":
    {
      "n": "EORH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZAIl3A",
      "power": "low"
    }
  }
}

Explicit AND

{
  "e": 
  {
    "d": "EerzwLIr9Bf7V_NHwY1lkFrn9y2PgveY4-9XgOcLx,UdY",
    "o": "AND",
    "boss":
    {
      "n": "EIl3MORH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZA",
      "power": "high"
    }
   "baby":
    {
      "n": "EORH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZAIl3A",
      "o": "NOT",
      "power": "low"
    }
  }
}

Unary I2I

{
  "e": 
  {
    "d": "EerzwLIr9Bf7V_NHwY1lkFrn9y2PgveY4-9XgOcLx,UdY",
    "o": "AND",
    "boss":
    {
      "n": "EIl3MORH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZA",
       "power": "high"
    }
    "baby":
    {
      "n": "EORH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZAIl3A",
      "o": "I2I",
      "power": "low"
    }
  }
}

Unary NI2I

{
  "e": 
  {
    "d": "EerzwLIr9Bf7V_NHwY1lkFrn9y2PgveY4-9XgOcLx,UdY",
    "o": "OR",
    "boss":
    {
      "n": "EIl3MORH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZA",
      "o": "NI2I",
      "power": "high"
    }
    "baby":
    {
      "n": "EORH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZAIl3A",
      "o": "I2I",
      "power": "low"
    }
  }
}

Nested Edge-Group

{
  "e": 
  {
    "d": "EerzwLIr9Bf7V_NHwY1lkFrn9y2PgveY4-9XgOcLx,UdY",
    "o": "AND",
    "boss":
    {
      "n": "EIl3MORH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZA",
      "o": ["NI2I", "NOT"],
      "power": "high"
    }
    "baby":
    {
      "n": "EORH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZAIl3A",
      "o": "I2I",
      "power": "low"
    }
    "food":
    {
      "o": "OR",
      "power": "med",
      "plum":
      {
        "n": "EQIYPvAu6DZAIl3AORH3dCdoFOLe71iheqcywJcnjtJt",
        "o": "NI2I"
      }
      "pear":
      {
        "n": "EJtQIYPvAu6DZAIl3AORH3dCdoFOLe71iheqcywJcnjt",
        "o": "NI2I"
      }
    }
  }
}

vLEI ECR issued by QVI example

We discussed that when the ECR is issued by the QVI it is not chained, Issuer-to-Issuee, via the LE credential. More accurate chaining would be to use the AND operator to include both the LE and QVI credentials as edges in the ECR and also to apply the unary NI2I to the LE credential instead of only chaining the ECR to the LE and not chaining to ECR to the QVI at all.

In the following example: The top-level edge-block uses the default of AND and the qvi edge uses the default of I2I because it points to a targeted ACDC. The le edge, on the other hand, points to a targeted ACDC but we want to accept it even though its targeted Issuee is not the Issuer of the current credential. Therefore it must explicitly provide the unary operator, NI2I in its operator, o, field.

{
  "e": 
  {
    "d": "EerzwLIr9Bf7V_NHwY1lkFrn9y2PgveY4-9XgOcLx,UdY",
    "qvi":
    {
      "n": "EIl3MORH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZA"
    }
    "le":
    {
      "n": "EORH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZAIl3A",
      "o": "NI2I",
    }
  }
}

Commentary

This provides a simple but highly expressive syntax for applying (m-ary) aggregating operators to nestable groups of edges and unary operators to edges individually within those groups. This is a general approach with high expressive power. It satisfies many business logic requirements similar to that of SGL.

Certainly, an even more expressive syntax could be developed. The proposed syntax, however, is simple, compact, has intelligent defaults, and is sufficiently general in scope to satisfy all the currently contemplated use cases.

The intelligent defaults for the operator, o, field, including the default application of the I2I or NI2I unary operator, means that in most current use cases the operator, o, field does not even need to be present.

[SmithSamuelM]

Accidently closed