Delegated re-encryption requests to allow for better availability checking

[isaacagudo]

Current mechanism for checking Ursulas availability is only based on checking that they are online but not on whether they are effectively following the protocol, i.e. providing the re-encryption service under the terms of the policies deployed in the network.

There should be some mechanism in place to assure nodes are indeed following the protocol. Ideally, the mechanisms should be decentralized, where peers agree on the performance of other peers. I like the idea of setting up a reputation system, but I am not sure whether reputation should be measured from outside clients: Alices and Bobs; or from other peers: i.e. other Ursulas, or even both of them. Anyway, it is not straight forward to implement a fair decentralized reputation system.

In my opinion Ursulas should play an active role on testing other Ursulas performance. Apart from being required to respond to Alice and Bob requests, they should also be in charge of challenging other Ursulas. That will increase Ursulas workload but will also provide a decentralized mechanism to evaluate Ursulas’ performance.

Whereas posing as an Alice is fairly simple, Ursulas will only need some allowance to create random policies, it is not clear how an Ursula can act as Bob in order to ask for re-encryptions. To begin with, the challenging Ursula should know where the re-encryption key fragments are, but I think this information in currently only known by Alice and the actual Bob. In order to avoid that limitation, we could make this information public, but that might produce some collateral effects.

My proposal is based on allowing for delegated requests between Ursulas. In this case Bobs won’t be in charge of contacting the right Ursulas, i.e. the ones with their fragments, they will instead contact any Ursula in the network based on parameters such closeness, latency or maybe lower fees. This Ursula will act as a gateway for Bob and will be in charge of finding the right Ursulas and collecting the cFrags to finally pass them to Bob. In this way, Ursulas would have to answers other Ursulas requests regularly without knowing whether it is an availability challenge or a real request originating from the actual Bob. This will allow Bob and Alice to run off chain, they don´t need to learn anything from the Nucypher Network if they use a gateway Urusla.

Ursulas would be able to assess whether:

• An Ursula is denying re-encryption for expired policies
• An Ursula is providing re-encryption for active policies
• An Ursula is not responding if it doesn’t hold the corresponding kFrag.

Under some circumstances, the gateway Ursula could even combine cFrags and pass the capsule directly to Bob. If we try to implement that, when reconstructing the capsule, the gateway Ursula could check if there was a problem with any of the shares in order to identify a misbehaving Ursula, i.e. an Ursula that is providing faulty re-encryption for active policies. This is something that will need some changes in the protocol and may have some implications in the security model.

All this information could be reported to the network or stored on-chain in order to have some metrics on individual Ursulas performance. Of course, there is also the problem of falsely reporting a bad Ursula. In order to mitigate that, there should be some kind of consensus by a group of Ursulas before reporting bad behavior.

If we opt for this challenging mechanism, it is important that challengers and the targets are selected randomly using some fair and secure mechanism. An interesting approach would be to use the random beacons to select the sample (https://www.cloudflare.com/leagueofentropy/ or https://csrc.nist.gov/projects/interoperable-randomness-beacons). That would assure that all Ursulas contribute to the resilience of the network equally and that we got enough "opinions" on every Ursula in order to reach an agreement. Assuming M as a security level, for every period each target Ursula should be challenged by M randomly selected challenging Ursulas. As M grows, we get more confidence on the reports but we also get a greater load on the Nucypher network …

All these ideas will have a significant impact the network architecture, even in the token economy that might not be worth the effort. I understand it would be difficult to implement them, but I hope this issue serves as a basis for good discussions on how to improve the mechanisms to check Ursula availability and improve the nucypher network in general.

[GhadaAlmashaqbeh]

Thanks Isaac!

The idea is interesting, and as you said, it could be complex to be implemented and definitely will change the architecture of the NuCypher network.

I have few comments/questions:

• This sounds like creating a backbone network of Ursulas. There are gateways or the edges of the network that communicate with Bob, and internal or non-gateway Ursulas. So I assume that both types of Ursulas will provide the re-encryption service, i.e., will be contacted by Alice to create policies, right? Also, how do you picture routing Bob requests? is it one hop from Bob to a gateway Ursula and then one hop from the gateway to the destination Ursulas that hold kFrags? or there will be multihop routes (via other intermediary Ursulas) from the gateway to the Ursulas that carry the policy? If it is the former, then each gateway Ursula needs to have a global view of the network (like who carries which policy), and if it is the latter then we need to implement a multihop routing protocol.

• Randomly selecting the challenger and target Ursulas need to be done in a private (and provable) way. Otherwise, if we rely on a public randomness source (whether it is a direct use of the NIST/etc. beacon or by using a random extractor evaluated over a public input like the block hashes, for example), then a target Ursula will know that it has been selected and act honestly until the end of the challenge period then go back to its lazy/malicious acting afterwards.

• This approach is more like analyzing network logs to detect misbehaving entities, and it also requires ensuring the consistency of the logs among different Ursulas. So having consensus among Ursulas requires exchanging these logs and agreeing on a common status (much like running a fault tolerant byzantine agreement or something similar). I am not sure how efficient or scalable such a solution can be. Usually such logs are sent to a verifier in the network that performs this analysis, but in a fully distributed and trustless setup this could be challenging. Also, I am afraid that it may motivate collusion, where Ursulas may collude to fabricate valid looking logs. Any thoughts on this?

[isaacagudo]

If it is the former, then each gateway Ursula needs to have a global view of the network (like who carries which policy), and if it is the latter then we need to implement a multihop routing protocol.

I think both approaches have advantages and disadvantages, but I would innitially target a direct connection between edge Ursulas and inner Ursulas. Moreover, those roles don't need to be static, Ursulas could take turns and the shape of the network could change every period so that all nodes in the networks contributed equally. That comes from @cygnusv and I think might be worth considering.

Randomly selecting the challenger and target Ursulas need to be done in a private

Yes, you are completely right. We could take a look at the Distrubuted Key Generation mechanism used by the league of entropy to see if we could adapt it to this scenario. The publicly selected challenger Ursulas would need to engage in a fair protocol to randomly select the target Ursulas.

I am not sure how efficient or scalable such a solution can be. Usually such logs are sent to a verifier in the network that performs this analysis, but in a fully distributed and trustless setup this could be challenging. Also, I am afraid that it may motivate collusion, where Ursulas may collude to fabricate valid looking logs. Any thoughts on this?

That is the most challenging part as in any reputation system. We could opt for implementing mechanisms that disincentivize nodes producing fake information. We could also rely on another Decentralized network for monitoring, channeling all requests and responses between Ursulas through this network so that everything is logged and variable without the need of centralized monitor.

[GhadaAlmashaqbeh]

so that everything is logged and variable without the need of centralized monitor.

Yup, I was not advocating for a a centralized approach. I just wanted to highlight the fact that having a decentralized monitoring approach (to avoid driving the NuCypher network toward centralization) will be a challenging issue as well.

[GhadaAlmashaqbeh]

Another question that crossed my mind now.

If we are saying that gateway Ursulas that will challenge other Ursulas will be selected at random, this means that each gateway Ursula must have a policy (or set of policies) that involve all other Ursulas in the network so she can issue challenge requests, right?

Also, who will pay for these policies? the gateway Ursulas? this means that they should be refunded for that, and possibly, get rewarded for performing the routing and challenging tasks (and agreeing on the report status later on as well), what do you think?

[isaacagudo]

If we are saying that gateway Ursulas that will challenge other Ursulas will be selected at random, this means that each gateway Ursula must have a policy (or set of policies) that involve all other Ursulas in the network so she can issue challenge requests, right?

Well, that's not quite right. Gateways will be impersonating legit Bobs in the system, in some sense hijacking existing policies. However, there is no harm to actual Bobs as the fragments are only useful to Bob, who has the corresponding private key. The challenges for this gateways are, on the one hand to know which policies are hold by which Ursulas and on the other hand to recognize whether the fragments are correct or just random data.

Also, who will pay for these policies? the gateway Ursulas? this means that they should be refunded for that, and possibly, get rewarded for performing the routing and challenging tasks (and agreeing on the report status later on as well), what do you think?

In case we want Gateway ursulas to also impersonate Alicies, they would need to create fake policies, so we need to face this problem anyway. In my opinion the challenging ursulas should receive a higher reward that should at least cover the cost of the fake policies issued.

[GhadaAlmashaqbeh]

One interesting thought here related to the above questions and the challenge mechanism in general:

We can have a side chain with the gateway Ursulas as the miners who maintain this chain (add blocks to it, verify records, agree on its status, etc.). During every period, i.e., block generation time, gateway Ursulas will broadcast their findings regarding responsive/irresponsive Ursulas that they challenged.

These finding are published in a block after being verified and validated (like running some consistency checks to make sure that gateway Ursulas are not lying and that they were indeed selected to do the challenge task, etc., still we need to specific what exactly that means).

Then, using a Byzantine agreement-like consensus protocol, a set of gateway Ursulas are elected at random to add a new block to the side chain. Their task is to form a block, validate it, and agree on adding it to the side chain.

The NuCypher main network relies on the information on the side chain to punish misbehaving Ursulas accordingly (by slashing part of their deposit).

Again, we still need to figure out tons of details here, but this is kind of high level structure of the idea.

[GhadaAlmashaqbeh]

Well, that's not quite right. Gateways will be impersonating legit Bobs in the system, in some sense hijacking existing policies.

Right, we do not require Bob to sign the requests or Ursula to check that indeed Bob is the one who issued the request, at least until now. Yeah, this works under the current network model.

[isaacagudo]

The challenging Ursulas can be seen as the validators of a side chain where verified work is registered. We could opt for having two separate roles in the NuCypher network, workers and validators or have all nodes alternate roles when selected as validators. The side chain will also provide some transparency on the performance of the nodes in the network. There are many advantages of maintaining this side chain but there is also an overhead that we might need to consider, also depending on what and how many consistency checks will validators run. Random sampling will make validation faster but we need to find a compromise in the number of validators selected for each period. Also, we need to ensure that all ursulas have some minimum number of policies even if they are fake ... As you said, tons of details are still to figure out.

[cygnusv]

My 2 cents:

• Whatever approach we follow, it should have 2 subprotocols: an optimistic and a pessimistic. In the optimistic (which is what we already do), Bob directly requests target Ursulas assuming they are going to respond; if they respond then all good, no need to make this more complex. Then, we have to think in ideas for the pessimistic subprotocol when some Ursula doesn't respond.
• We already have some structure to handle requests from Bob to Ursulas through other entities. We have the WorkOrder abstraction, which is constructed by Bob and delivered to the target Ursula. Currently, it's delivered by Bob himself, but nothing prevents from being routed through a sequence of intermediaries (1 ursula, N ursulas, or potentially even other types of entities).
• I personally believe that we don't need to do periodic challenges. I don't mind if an Ursula that is not being targeted (for whatever reason: it can be that the policy is not used, or simply, she's being "lucky") is not punished. What I want to solve is the problem of Bobs that are trying to contact an Ursula and she's not responding. In other words, Bobs real requests are the challenge.
• A simple idea for a pessimistic subprotocol: When Bob hits an unresponsive Ursula, he contacts a current gateway Ursula (which is a role that should rotate probabilistically among all Ursulas, and it's mandatory, like jury duty). Gateway Ursula routes the request to the Ursula that Bob wants to contact. Now Bob has an impartial witness about the outcome of this request. Now the problem is deciding what to do with this information. It may be necessary to do some committee signing, or consensus protocol, etc. I have no idea at this point.

[GhadaAlmashaqbeh]

Three issues with this approach:

• So the approach is that Bob will work as usual and contact a working Ursula first, if no answer he will contact a gateway Ursula and say “hey, contact this working Ursula for me, she is not responding to my request”. But in this case, when this working Ursula sees the same request again, it will reply (assuming it is up) since it knows that this is a challenge. My point is that a malicious working Ursula may respond only to challenges, to avoid slashing, rather than all Bob requests.

Based on our discussions on Discord, this is not a practical threat. To perform this attack, a working Ursula is online either way, and she is just trying to proceed with the pessimistic part of the protocol, which is more dangerous for her. So for a rational Ursula such an attack is not appealing.

• How about a malicious Bob that may perform a DDoS attack against a working Ursula by issuing false complaints to a gateway Ursula?

This can be handled by requiring Bob to do some PoW in order to accept his complaint.

• How about other attackers who may impersonate Bob and issue complaints to gateway Ursulas? Recall that requests from Bob are not signed, so anyone can issue requests on his behalf.

Impersonation can be solved by requiring Bob to sign his requests, or at least sign the complaints for now. There could be other solutions to this problem as well.