When Bob asks Ursula to do a re-encryption for him, there are two ways of misehavior possible:

• Ursula simply doesn't re-encrypt;
• Ursula produces garbage in response to re-encryption request.

It's not clear if we can do the latter on-chain, but we need some sort of agreement between nodes if we want to prove the former.

Here are 2 ways possible to solve this.

1. Challenge protocol w/o any side-chain

Let's introduce a "generalized ping". Instead of a real ping, it's a challenge with a response respected from Ursula.
If no response comes, the ping was "unresponded".

In brief, we have nodes ursulas[0..N-1], and many nodes ping one node.
The idea is that the target Ursula cannot distinguish if she's being challenged, or it is a legitimate request which she has to do.
Also she cannot see if any two pings come from the same node or not.

With these assumptions, here's the protocol:

It would be too expensive (in terms of gas) for every Ursula to produce evidence about every other Ursula, so we have to definie which Ursula votes on which.
So, we randomly select who votes on who in the following fashion.
We don't necessarily want other Ursulas to know who "pings" them.
At the beginning of the period, hash of the block when the period is started on Ethereum blockchain is h.
Then we have::

r = hash(sign(eth_pubkey, h))
ursulas_to_challenge = [
    closest_hamming_distance(ursulas, hash(r + i))
    for i in range(N_to_challenge)]

Importantly, a smart contract can test whether the pseudorandom number r indeed belongs to this Ursula by using precompiled ecrecover method.

So, now each Ursula has N_to_challenge Ursulas to ping during this period.
They have to ping them multiple times (let say, 100) during the current period randomly, while keeping these requests anonymous (so they shouldn't have same IP
addresses).
After having done that, each Ursula has statistics of how much time the challened Ursula was up.
After that, Ursulas vote (using hash-and-reveal protocol) on which Ursula was up for how much time.

If measurement by one of challenging Ursulas is different from the other swarm significantly enough (so that it's not a statistical artifact), this Ursula gets
slashed. So all Ursulas are incentivized to honestly measure uptime of each Ursula with a precision within the specified margins.

In our case, generalized ping is producing a random capsule to re-encrypt and ask to re-encrypt it. It doesn't have to be a decryptable capsule produced by
Alice: Ursula can "re-encrypt" and produce a proof about any capsule.

The problem of this method is that it heavily relies on anonimity of "pings". If that assumption breaks down, a mean Ursula can re-encrypt for one challenging
Ursula and not re-encrypt for the other, causing a disagreement in the network about who is up, essentially breaking the consensus mechanism.

2. Sidechain

More detailed design of sidechain happens here

The main idea is to introduce a sidechain where Bob can log re-encryption requests.
Normally, Bob can just ask Ursula to re-encrypt.
But if Ursula doesn't respond, Bob can publish his request to the side-chain.
When the request is on side-chain, Ursula is forced to re-encrypt, or she will lose some collateral deposit.

We don't care if the re-encryption request is repeated in another block of a side-chain ("double spend").
So, the sidechain doesn't have a typical robust consensus mechanism requiring expensive proof of work or complex proof of stake.

So, the protocol can work as follows:

• Bob (and only Bob) can submit the capsule he's re-encrypting (while proving by signature that he has a right to re-encrypt it).
• One Ursula is selected randomly, based on Ethereum block hash, every dt.
• This Ursula should take all the requests of Bobs (and responses by Ursulas) from current mempool, form a block and submit, linking it to the previous block.
• Once the request by Bob is in the block, target Ursula has to respond in certain number of blocks.
• If the current random Ursula doesn't include some request from the mempool, the next one will.
• Bob should not be able to do a DOS attack on the network, thus he can be throttled by requiring a client-side PoW (with increasing difficulty if the requests
  are often).
• Once Ursula publishes a (signed) response, any Ursula who's currently forming a block can verify it and include in the block.
• An Ursula should continue the chain from the last correct blocks. Blocks which include incorrect requests, or requests which were already recently included,
  or made by Ursulas who shouldn've been recently producing any blocks, are considered orphan.
• If an Ursula currently on hook somehow produces two different but valid blocks, every other Ursula should use the block which she saw first.
• The longest chain is accepted.
• Every period, Ursulas know exact state of the blockchain, thus they should know exactly which Ursula has to be punished (if) and by how much. Since they know
  the same state, they should know exact same information to vote for which Ursula should be slashed and by how much, so they can vote for it using
  commit/reveal protocol.

The advantage of this protocol is that no anonimity of all the connections is required.

The disadvantage is that Bob now has to be non-anonymous b/c he has to be signing his requests, in order to prevent DOS attacks on him.