The UpgradeableOwners validator checks that there is at least threshold many signatures from the list of owners supplied with the transaction. The check is performed with:
PP.length (PP.filter (`PP.elem` txInfoSignatories info) (owners datum)) >= minSigs datum
iterating over both txInfoSignatories and owners. That means that for the check to succeed a threshold * threshold PubkeyHashes need to be compared - that is the check has a quadratic complexity.
This may or may not be a problem depending on the planned amounts of owners and thresholds to be used in the protocol in practice. For small numbers this implementation will perform comparably fast to a linear implementation - and has the advantage of being easy to verify and reason about.
Recommendation
The practical usecase needs to be considered to choose between the present or optimized implementation.
If the performance consideration is important, then the following improvement is possible. Namely, the validator should additionally enforce an ordering on the list of owners held in the datum. This means that in the updated owners list a new address gets inserted into an appropriate place in the list and this is checked by the validator. The check if a threshold is met iterates simultaneously over the signatories and owners list. As the lists are ordered, we can look at elements from both lists in order - counting how many elements appear in both lists.
Description
The
UpgradeableOwners
validator checks that there is at least threshold many signatures from the list of owners supplied with the transaction. The check is performed with:iterating over both
txInfoSignatories
andowners
. That means that for the check to succeed athreshold * threshold
PubkeyHashes need to be compared - that is the check has a quadratic complexity.This may or may not be a problem depending on the planned amounts of owners and thresholds to be used in the protocol in practice. For small numbers this implementation will perform comparably fast to a linear implementation - and has the advantage of being easy to verify and reason about.
Recommendation
The practical usecase needs to be considered to choose between the present or optimized implementation.
If the performance consideration is important, then the following improvement is possible. Namely, the validator should additionally enforce an ordering on the list of owners held in the datum. This means that in the updated owners list a new address gets inserted into an appropriate place in the list and this is checked by the validator. The check if a threshold is met iterates simultaneously over the signatories and owners list. As the lists are ordered, we can look at elements from both lists in order - counting how many elements appear in both lists.