Multiparty attestation - Githubissues

Current structure assume that there is only one testator. Does it make sens to allow for multiparty attestation?

I could imagine that multiple parties would like to attest to one specific datum in a way that they are bound together (that they are doing that together, e.g. commitment to contract). So instead of using sources as a linking mechanism (each would need to link to all and we have chicken and egg problem).

Example:

{
i: [did:1234/attestation/1, did:abcd/attestation/1]
...
}

A threshold multisig is a form of multi-party. The problem with other forms of multi-party is that it is not an single issuer and that gets complicated really quickly. We are not restating to contracts. We are issuing data. So if multiple parties want to issue identical data its just mutiple containers == VCs.

If one wants to have multiparty for security then its multi-sig.

We can always define a different type of container for non-single issuers. But that will be much more complex. I want to avoid too much complexity to start with. This is the bane of the VC world, over generalizing specs.

Sent from my iPad

On Jun 15, 2021, at 12:49, Robert Mitwicki @.***> wrote:

Current structure assume that there is only one testator. Does it make sens to allow for multiparty attestation?

I could imagine that multiple parties would like to attest to one specific datum in a way that they are bound together (that they are doing that together, e.g. commitment to contract). So instead of using sources as a linking mechanism (each would need to link to all and we have chicken and egg problem).

Example:

{ i: [did:1234/attestation/1, did:abcd/attestation/1] ... } — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or unsubscribe.

But how do you represent multiple containers (VCs) in an ideal, self-contained, VC provenance chain of delegation as described here ? For example, using an abbreviated version of the Edge co use-case in the paper: Delegation to the director of procurement requires 2 managing directors: This results in a (rough) graph like this:

         <managing director> --------\   
                                     <director of procurement>
         <managing director> --------/

The credential issued to the director of procurement should contain the credentials of the 2 managing directors, providing provenance as you go up the chain to the root. But, who is the issuer of the credential to the director of procurement? A VC can currently have only 1 issuer.

there are two ways to split this baby. One is to use single key issuer credentials and then layer on business logic for workflows with multiple single issuer credentials. The other is to just leverage thresholded multisig in KERI. With the later approach only one credential is issued and the multi-party is just hidden behind the multi-sig. Recall that in an earlier discussion (or maybe your were not on that discussion) we can use a group of KERI identifiers and KERI's async signature collection mechanism to easily support multi-party signatures.

Group Formation

Each member of the group creates an identifier with one or more signatures (to keep it simple we just use one for now). The set of identifiers now forms a group. The group members agree out of band that they will use the key sequences for each of these identifiers to form a multi-party issuance policy for a new group identifier. The group identifier is just a standard KERI identifier that is self-addressing and is derived from a thresholded kt for the set of keys that are the same set of keys from each of the individual identifiers. So one issuer identifier but controlled by the multi-party set of identifiers via their corresponding keys. The threshold may be a weighted multi-sig threshold as per standard KERI.

The group may be private or public. In the case of public VCs one may choose to include the set of group identifiers in the VC or in a group source document that establishes the group set. Because each member of the group has its own unique identifier with its own unique KEL. One can individually communicate to the members of the group and address them individually. The keys are dual use. The same set of public keys, one for each individual identifier are the same set of keys for the multiple-sig group identifier. Say there are N members of the group. There will be N+1 KELs, one single key KEL for each individual and one group must-sig KEL but only N keys.

Inception

Any one of the members of the set may propose the inception event for the new "group" identifier and sign it with their key. The inception event is not valid until a threshold as defined in the inception event of signatures is attached. The proposer just distributes their signed inception to each of the other members of the group for them to attach their signature and redistribute. Eventually each member of the group will have a fully signed inception event and a copy of the KEL for that group identifier as well as a copy of the N keys for each individual identifier.

Group XoR Next Digest Formation

This works because the next key digest is the xor of all the next public key digests plus the xor of the threshold. Because each of the individual member identifiers is using only one key, The threshold is known and my be removed from the that single member next digest to leave the digest of the next public key. Given that now the next key digest is known for each key in the group set the group must also agree out of band what the group kt should be so that all know it. Give a the group kt any member of the group can compose the group current keys set and the group next key digest once they know the KELs of each of the group member single key identifiers. This XoR property was why we changed the algorithm for computing the next digest from a digest of the concatenation of next public keys to an XoR of the digests so that we could use this protocol for generating group key agreement for multi-party issuance. If we let X represent XoR then A X B X A = B so if A is the threshold digest then we can extract the public key digest by XoRing the threshold digest.

Rotation

To rotate the group key state , the group decides out of band to rotate. Any one of the group at any time can propose a rotation. A threshold number of the group must then individually rotate their single key identifiers to produce a new current key and a new next key for each member. Once that is done then any member of that threshold group may propose a group key rotation event by extracting and XoRing the next key digests from those individual KELs and then signing it with their key and then disseminating it to the other members just like they did with the inception.

Interaction

Interaction events do not require a rotation but the process is similar any member can propose an interaction event by creating it and signing it and disseminating it. It won't be valid until the threshold signs it. Indeed multiple members could simultaneously propose conflicting interaction events and the first one to meet the threshold wins the rest will be discarded.

VC Issuance

Any one of the group can issue a credential against that group identifier by creating an interaction (or rotation) event with an anchor seal of that VC and then publishing it to the other members of the group. but that credential will not validate until a threshold number of the group also sign. The escrow mechanism of KERI means that each member of the group will keep in escrow a partially signed event that includes the Seal or anchor for that issued credential. Likewise the TEL will put that VC issuance event in escrow until a threshold number of members of the group have signed. Using this approach there is no need to have additional business logic for multi-party issuance or issue a VC per party. Just issue one VC that is signed by the group as a multi-sig. This is one of the prime use cases for weighted multi-sig, to enabled complex multi-party threshold logic for such an example.

Witness Considerations

Witnesses are oblivious to how a given multi-sig identifier is composed as they just see themselves as witnesses in the witness list for any given set of events and their logic for receipting does not change.

Multi-sig of Multi-sigs

Now to complicate things, given we have weighted multisig we can leverage the fact that XoR is associative. So some or all the members of the group could use multi-sig for their individual identifiers. The group identifier is then composed from multiple sets of multisig identifiers but the KERI protocol works the same under the hood. So very complex multi-party logic is enabled without changing anything in the existing KERI protocol. The same logic can be applied to delegated identifiers etc.

Summary

So in general KERI solves the multi-party issuance problem simply using its build in properties of: async, escrow, weighted multi-sig, and XoR next key digest commitments. The only additional thing required is the out-of-band agreement to form the multi-party multi-sig group. But this does not require any unique crypto and any secure protocol for this out-of-band agreement. It just requires that the group members recognize that the individual group member single key identifier KELs as belonging to that group. Its a UX issue.

To restate the only new thing required is some out-of-band group agreement to form a group identifier from a set of identifiers, one identifier in the set for each member of the group. Any verifier of a VC issued by the group identifier is verified as a standard multi-sig.

As this exposition hopefully illustrates, KERI multi-sig first approach solves in a natural way, a host of what would be for other identity systems, very complex use cases.

@SmithSamuelM thanks for the response, this is all very interesting. But when you say

Using this approach there is no need to have additional business logic for multi-party issuance or issue a VC per party.

How would this approach deal with more complex logic, say for example:

Granting "purchaser" requires any of 2 "managers" or 1 "director"? I ask this because most of my focus lately relates to the work on chained credentials from Danial Hardman.

These are the kind of realistic rules I see in real-world delegation schemes. Would that require at least 2 groups in a KERI environment? And I assume validating the provenance of all this requires walking different KELs in a potentially large hierarchical setting?

@davebryson Weighted multisig. The two managers each have half the weight of the 1 director. So the threshold is met if two managers sign or one director signs. Weighted multisig thresholds are an ordered list of weights. So fo the order is M1, M2, S1 the weighted threshold would be [1/2/1/2,1] Any combination of signatures that adds to >=1 meets the threshold.

KERI are supports Ored clauses of weights. like [[1/2,1/2,1], [1/3, 1/3,1/3, 1/2, 1/2]] so one can have different sub groups in a one level hierarchy. We did not see any reason to support more that one level of hierarchy as the vast majority of use cases are supported by one level and multiple levels is way more complicated.

Signatures may be used as authorizations (endorsements) without needing a VC. Its reinventing the wheel to use VCs in lieu of multi-sig when multi-sig will do. But @mitfik we could precisely model your example by stating that each source VC for each mangaing director is required to be signed by the managing director. And then form a multi-sig group from the managing director keys with a multi-sig threshold. The resultant group identifier then issues the director VC with a multi-sig. Each managing director would then sign two VCs, their own manage VC with a single signature and the the director VC as a a member of the multi-sig group. The VCs source tree serves to publicize the business model behind the formation of the multi-sig group.

We could do it another way using delegated identifiers. There are several ways to skin this cat using standard KERI.

@SmithSamuelM

Signatures may be used as authorizations (endorsements) without needing a VC

But wouldn't a VC be needed to at least specify what the endorsement is for?

the VC being signed may provide that information. There is no reason to have a tree of VCs in that case.

@SmithSamuelM Thanks. I see you have some potential examples related to this discussion here https://github.com/decentralized-identity/keripy/blob/master/tests/core/test_delegating.py.
I need to dig into this more.

So is it fair to say that the direction of this group is with KERI versus some of the earlier work such as chained credentials here: https://github.com/hyperledger/aries-rfcs/tree/master/concepts/0104-chained-credentials

Any document or contract may include in it its list of signers and the roles the play. If the signers need to be authorized themselves then they may have VCs that authorize them as signers of yet another VC But we are not talking about that use case we are talking about the use case of how to have a multiple issuer VC and I am saying that we just use multi-sig with a group identifier. This means that in all cases all VCs need only have single issuer IDs. But some of those single issuer identifiers may be composed from a group of other identifiers via their keys. To restate there is no need to layer on the complexity of having multiple issuers of a given VC. We just leverage multi-sig.

We need KELs for rotation. I have been assuming we need rotatable multi-issuer identifier keys. Otherwise we can simplify the logic to use non-transferable (non-rotatable identifiers) that need no KEL.

To clarify in any chain or (tree) of trust there will be root entities that are self-authorizing due to their reputation. they form a root-of-trust. GLEIF for example or a government. There will be other entities that have insufficient reputation to be roots-of-trust. They may therefore require an authorizing VC from a root-of-trust or multiple roots-of-trust to imbue them with enough trust that they in turn may issue a VC. In the former case were a multi-sig group is formed from multiple roots-of-trust there would be no "tree" of VCs as the roots-of-trust are self-authorizing by definition. But for derived (imbued) trust entities their may be a chain or VCs that goes back to the roots. One has to analyze the ecosystem and understand the role that roots-of-trust (also called a trust anchors) play in the web-of-trust KERI makes practical the long outdated and largely abandoned concept of a web-of-trust. It solves the problem that the original web of trust punted and that was key rotation as well as not having self-certifying self addressing identifiers for crypto graphic roots-of-trust to bootstrap the whole thing.

This concept of roots-of-trust is fractal in nature. One can have a corporation that has well known identifiers for its founders that are self-authorizing and every other employee is imbued with authority via VCs issued by those founders but the founders themselves have no authorizing VCs. Or they self-issue but that is just book keeping, self issuance provides no additional trust. A root of trust is trusted because of its reputation or role it plays. It has authority assumed as endowed to it independent of VCs. Any one can form a root-of-trust with KERI. But if the entity forming that root is not sufficiently trustworthy it will be a weak root and not very useful. One can build trust over time by consistent good behavior that occurred either pre-root formation or post root formation. The latter is verifiable cryptographically so it allows any entity to prove or provenance their bootstrap of their reputation through a verifiable log of good behavior. The best kind of proof-of-work.

We are generalizing provenance of authentic data. Chained authorization is a special case of authentic data provenance. What you are seeing is that KERI’s design obviates the need for layered on protocols for many use cases. So one either adopts KERI or copies KERI but calls it something else or one does back flips. For some they may have to do back flips. The reason KERI made multi-sig a first class citizen is because it is a best practice for security. Given you have multi-sig then other use cases just fall out naturally. In general most VC DID methods do not support multi-sig in any way so they have to do back flips. I strongly suggest that this is the wrong approach. They need to go back to their did method and add thresholded multi-sig as a first class citizen. then they can model the KERI logic with out exactly using KERI. The same applies to key rotation. Most do not support key rotation in any secure way. KERI does using pre-rotation and now others have started copying that concept without necessarily calling is KERI-like pre-rotation. Too much of the VC community is to bolt on mechanism that defeat the “verifiability” security basis that VCs were meant to provide. AKA JSON-LD with mutable schema, DID methods that rotate keys badly. Etc Etc. So once you use best practices the list of options narrows considerably and you either look like KERI in large part or you are not secure. KERI is simple best practices key management for portable identifiers. Once you tackle portability, your choices go down to one mechanism, that is a VDS (verifiable data structure) which will look suspiciously like a KEL. Once you realize that, then KERI becomes a no-brainer. If on the other hand you do not care at all about portability then you can use a shared distributed ledger as your primary root-of-trust instead of a VDS (KEL). But then you have locked your identifiers to that ledger, but it you support key rotation and multi-sig you can be secure just not portable. Its the combination of portability and security that drives the design of KERI.

KERI are supports Ored clauses of weights. like [[1/2,1/2,1], [1/3, 1/3,1/3, 1/2, 1/2]] so one can have different sub groups in a one level hierarchy. We did not see any reason to support more that one level of hierarchy as the vast majority of use cases are supported by one level and multiple levels is way more complicated.

@SmithSamuelM -- It's not often true that [Manger + Manager == Director] or [Child + Child == Parent] or [Citizen + Citizen ... == Government]. Multisig without context is ok for consensus based algorithms with a single scope of work, but when it comes to applying multisig to reality, weighted algorithms work laterally (peer to peer), but not vertically (when spanning levels of authority). What is needed to solve the vertical problem may not be easily represented in a decision tree of any depth or complexity. I am concerned that when applied, the required context of the signatures will have to be solved by business logic -- and that once that happens, portability will be lost. Maybe that's ok.

@chbuchanan I think that delegated identifiers may adequately solve most vertical problems you describe. So the delegator can be a multisig that then cooperatively authorizes a delegated identifier that itself is multisig. That delegated identifier then may further delegate identifiers to form a tree of delegation each node in the tree may have weighted multi-sig but the hierarchical organization is modeled by the tree of delegated identifiers. The multi-sig group at a delegated leaf, only gets an identifier if all the branches have delegated down to that leaf. This is not that same as having a single decision tree where all nodes may contribute to the tree of signers for each issuance but delegation trees do represent the major use case for vertically (hierarchical organizations) where decisions happen at divisional or group layers that have delegated responsibility. This is how most distributed organizations function. The CEO does not participate in issuing invoices but does participate in delegating the authority to issue invoices. The CEO may revoke that delegation but does not ever sign an invoice although theoretically the CEO could sign an invoice. That a CEO may actually be able to sign an invoice is a corner case we do not need to support as the CEO can just create a new delegation to itself to participate in a group that may sign invoices without making the CEO part of every invoice signing group.

That said weighted multi-sig with multiple clauses can model quite complex decision trees without delegation. For example, we had a practical requirement in an ecosystem governance framework for a 10 signer multi-sig consisting of 5 employee signers and 5 contracted Escrow agents. Any 3 of 5 of employees may sign or 1 employee and 4 Escrow agents or some other combination of Employees and Escrow agents. The requirement is that no combination of only Escrow agents is valid, i.e. at least 1 employee MUST sign but we only want to have at most one designated survivor employee because we don't want to have a case where a single bomb can kill all the employee signer and that means the designated surviver may never ever be in the same building with the other employee signers. This is achieved with a single weighted clause. [1/3,/1/3,1/3,1/3,1/3,1/6,1/6,1/6,1/6,1/6] where the employees each have a weight of 1/3 and the escrow agents each have a weight of 1/6.

With KERI more complex logic can be expressed with multiple clauses And'ed together and each Weighted clause acting as a weighted ORs (WOR) of the keys making the threshold. A weighted OR clause threshold is satisfied when some combination of the weights in that clause sums to >= 1. With that you have a very rich rule expression set as follows:

IF (x WOR Y WOR Z wor ...) AND (a wor b wor ...) AND (m WOR n WOR ....) AND .... THEN issue

The limitation is each variable representing a key may only appear once in the rule. The rule threshold is only met if every AND ed clause meets its threshold. So each AND acts a layer in a multi-sig hierarchy. For example

[[1,1],[1/2,1/2,1/2]] means that any one of the first group AND any two of the second group must sign to meet the threshold. So any one of two directors AND any two of three managers must sign to be approved.

For example a proposal submission rule I had to comply with as an academic was The PI MUSt sign, The department MUST sign which could be the Chairman or Assistant Chairman. The College Must sign which could be any one of the Dean and three associate Deans. The division of sponsored research must sign which could be the Director or assistant director and the Presidents office must sign which could be the president or the VP. The resulting weighted threshold is as follows: [[1],[1,1],[1,1,1,1],[1,1],[1,1]]

In my survey of real world applications ANDed signing tree logic appeared be much more common that layered WOR tree logic. Nonetheless, letting an authority have multiple keys in an ANDED WOR rule allows us to approximate many layered thresholded WOR trees. I find layered WOR trees to be poor attempts a modeling an ANDed WOR rule not the other way around.

Indeed WOR layered trees may have corner conditions that are undesirable where some coalition of signers may subvert the true intent of the signing tree logic by virtue of not having rigid AND logic but just normalized weighted summation logic..

If we relaxed that constraint that each key may appear only once then more complex combinatorial expressions would be possible but that would mean using something more complex than a list or list of lists. And weight position would no longer correspond to a given key in a key list. But we can achieve the same end by letting any entity or role player have more than one key in the key list so effectively their authority participates in multiple clauses. This elegantly allows us be performance optimal and simple but support odd corner cases.

A single weighted OR can be used to approximate hierarchical weighted ORs by flattening the weights in the hierarchy. So for example if I have two sub groups each with [1/2, 1/2, 1/2] that are then combined at the next layer up with a weighted OR of [1,1/2] then that may be approximated by a single layer WOR with the first group having weights of 1/2 and the second group having weights of 1/4. The difference is that in a layered system you could renormalize at each layer which is not exactly the same at collapsing the layers by multiplying the unnormalized weights. When I looked at the example that BitShares uses (see https://how.bitshares.works/en/master/user_guide/accounts/bts_multi-sign.html) which did a multi-layer weighted OR that is renormalized at each layer I realized that I could better represent real world use cases with ANDed clauses which they cannot represent. I.e. ANDed WOR logic in my opinion is a more realistic more needed use case than renormalized layered WOR logic. It seemed that their example was unrealistic. ANDing across hierarchy seemed to me to be more realistic. It was a design tradeoff.

Moreover, with delegation trees we may model logic that allows the same key to appear multiple times in the logic tree or to model renormalization. For example a given multi-sig group may delegate to an identifier who multisig group includes some of the keys from the delegating multisig group. The two groups may then form a layered AND/OR expression where the same key appears more than once. Although as I stated above the same entity can control multiple keys so its authority may appear multiple times but with a different key. With delegation, I believe, we may model arbitrarily complex real world signing hierarchies that better match real world corporate distributed authority delegation trees without over complicating the core multi-sig logic. One mistake we want to avoid is creeping elegance by over designing what needs to be performant thereby making it so non-performant that it is no longer utile for the majority case.

We have yet to see any real world use cases that justify such additional complexity which comes at a cost in performance and security risk costs. Its easy to hypothesize complex use cases but our experience, real world use cases are never that complex because they become too complex for the humans that will be involved. Thus human involvement practically constrains the system. This shows up as delegation which is why we support delegation not complex signing tree logic. Hypothetical complexity is an anti-pattern for security system design. I like to avoid it. Whereas the simple weighted multi-sig that KERI uses is almost always required for any enterprise application. Consequently we want to support it natively and conveniently. And simple cooperative delegation trees enable horizontal scalability which we want to enable. These design choices follow the KERI design aesthetic of minimally sufficient means.

However all that said if there arises a strong use case for layered renormalized weighted OR logic we could support it in KERI with a configuration trait that uses a different combination logic on a list of lists expression for the weighted threshold

So instead of [[1/2,1/2,/1/2], [1,1]] as ANDed WOR clauses we could have something like [ 2/3, 1/3, 1/3, [1/2,1/2,1/2], [1,1], [1/2,1/2,1/2]] to model a weighted OR Tree. This would require code and adding a configuration trait that would indicate using different serialization code and threshold computation code for the multi-sig of that identifier.

Here is the python snippet for the weighted threshold satisfaction


try:
            if not indices:  #  empty indices
                return False

            # remove duplicates with set, sort low to high
            indices = sorted(set(indices))
            sats = [False] * self.size  # default all satifactions to False
            for idx in indices:
                sats[idx] = True  # set verified signature index to True

            wio = 0  # weight index offset
            for clause in self.thold:
                cw = 0  # init clause weight
                for w in clause:
                    if sats[wio]:  # verified signature so weight applies
                        cw += w
                    wio += 1
                if cw < 1:  # each clause must sum to at least 1
                    return False

            return True  # all clauses including final one cw >= 1

        except Exception as ex:
            return False

        return False

This has been a long discussion but one more clarification is worth making. The original question was do we want to support an new protocol in the ACDC spec that provides support for a new type of ACDC that has multi-party issuers. This means at the very least multiple entries in an issuer array instead an issuer field. The short answer IMHO is no. We instead can have single issuers, but those single issuer identifiers represent a multi-party authorization via a multi-signature scheme like KERI provides.

This does not obviate or preclude multi-VC authorization mechanisms. A Multi-VC mechanism is where a verifier requires some threshold of of set of single issuer VCs be met before authorizing some activity. The difference here is that the existing ACDC spec supports any multi-VC authorization mechanisms without change. So its not a constraint on the ACDC spec. All of the discussions about support for hierarchical discission making infrastructure above, could be just as well be supported by a multi-VC policy where each VC has a single issuer (multi-sig or not). But this functionality would then reside at a layer above ACDC. So it would be up to the eco-system to decide where to place the hierarchical multi-threshold authorization logic. Either in the ACDC layer, in a Multi-VC layer above the ACDC layer or split between the two. I suggest that most complex work flows should reside in a layer above the ACDC layer and that there is no need to add a new type of VC that is a multi-party issuer VC. Multi-VC logic with single issuer VCs can handle that, or in many cases multi-sig can handle that, or some of both depending on the actual decision making workflow. We can always layer on additional threshold structures which better fits the many thin layer stack architecture of the HourGlass theorem that informs KERI. A multi-party VC is thickening the ACDC layer whereas a multi-VC layer leaves the ACDC layer thinner.

trustoverip / TSS0033-technology-stack-acdc

Multiparty attestation #7