Re: Max. Number of Organizations in a common channel #channel #fabric #hyperledger-fabric #network #administrator-organiization
Just because Fabric does exhaustive search, doesn't mean the problem is really NP hard.toggle quoted messageShow quoted text
If you have an endorsement policy that is satisfied by any k organizations out of n organizations, then determining if a given signature set satisfies it, is far from being NP hard.
Just make a bipartite graph where on the left side you have vertices that represent principals (n organizations) and on the right side you have vertices that represent identities of your endorsements (there have to be more than distinct k identities otherwise you abort instantly).
Now draw an edge between each identity (in an endorsement) on the right, to all principals it satisfies (on the left).
Finally, run a graph matching algorithm to find the maximum matching. Since the graph is bipartite, there is a polynomial time algorithmthat solves this problem.
If the algorithm found a matching of size k, then you have k out of n organizations that are satisfied by distinct k signatures (corresponding to identities) in the endorsements of the transaction. Otherwise, it is impossible to satisfy the endorsement policy with the given endorsements.
Lastly, I also claim that you can greatly simplify the search space by doing clever pruning of the policy tree based on the endorsements you are given: If you have total n principals in the system and an endorsement contains up to m<n signatures/identities, then you can do something as follows:
build the endorsement policy tree, and then starting from the leaves, for each principal in a leaf check if there exists an identity in the endorsement set that satisfies it. If not, just prune that leaf from the tree.
Next, go up to the parent level of the policy tree, and prune inner vertices that cannot be satisfied anymore because they have less sub-trees than the NoutOf threshold.
You will notice that intimidating policies such as "n/2 out of n" now become a simple "n/2 out of n/2" policy which is a single principal combination!
What is the worst type of policy tree you can get which renders the pruning approach less effective? probably... an NoutOf(sqrt(n), n) with each sub-tree also being an NoutOf(sqrt(n), n) totalling in n signatures (all principals, I know, this is an inefficient way of saying "n out of n").
In this case, nothing will be pruned and in case of n=100 we are left with a huge combination space.
Why am I giving this example? Because I believe that the "hardness" of the endorsement policy satisfaction lies in the exponential blowup up of the policy language, and not in the evaluation of whether a signature set satisfies the endorsement policy.
In other words - although the syntax of the endorsement policy allows us to construct expressions that have exponential expansion, any reasonable endorsement policy can probably be efficiently checked for satisfaction by a signature set.
From: "Brett T Logan" <brett.t.logan@...>
Date: 01/17/2021 11:37 PM
Subject: [EXTERNAL] Re: [Hyperledger Fabric] Max. Number of Organizations in a common channel #channel #fabric #hyperledger-fabric #network #administrator-organiization
Sent by: fabric@...
I'll quote Senthil on this one, consider a channel, with a large...
I'll quote Senthil on this one, consider a channel, with a large number of organizations, but only requiring 2 endorsements, the question was, does increasing the number of members decrease the performance:
Yes, it does. Though we need to collect only 2 endorsements out of 50 organizations, the matching of the signature set to the endorsement policy is an NP-hard problem. When the search space increases, the performance would go down.
Please refer to slide 22 here – http://www.bchainledger.com/2020/03/performance-analysis-of-hyperledger.html
----- Original message -----
Sent by: fabric@...
Subject: [EXTERNAL] [Hyperledger Fabric] Max. Number of Organizations in a common channel #channel #fabric #hyperledger-fabric #network #administrator-organiization
Date: Sun, Jan 17, 2021 8:10 AM
Is there an upper limit to how many organizations can be enrolled in the same channel in Hyperledger Fabric?
What are the best practices to keep in mind when designing a network for many stakeholders (fabric organizations) that need to share data with each other?
Thanks, Samyak Jain