Ratcheting Re-Encryption State Channel

gistfile1.txt

=== Ratcheting Re-Encryption State Channel ===


Some definitions:
    C   -> The WorkOrder as a Hash Chain (a chain of signatures).
    C_r -> The Chain root of the WorkOrder, the signature of the last performed re-encryption.
    C_i -> The signature of the i'th re-encryption request.
    R_i -> The number of re-encryptions an Ursula node has performed for a Bob (the re-encryption index).
    R_f -> The final re-encryption request from Bob.
    R   -> The current re-encryption request.
    H() -> A cryptographic hash function.
    P   -> A unique Policy ID.
    U_k -> Ursula's pubkey.
    B_k -> Bob's pubkey.


Overview:

A WorkOrder becomes a Hash Chain where each link at index i is a signed hash of the i'th re-encryption request from Bob
A re-encryption request for NuCypher can vary, but in this specific protocol it must be a signature of H(P || U_k || B_k || R_i) as R.
Ursula appends R to the Chain C where it becomes C_r.
When a WorkOrder is finalized, the proof that work was performed is given as the Chain root (C_r, P, U_k, B_k, R_i).
When the proof is submitted, we form R_f' by H(P || U_k || B_k || R_i).
We can then verify the proof by performing a signature verification SigVerify(C_r, R_f', B_k).
If the signature is verified, then Ursula gets paid for R_i re-encryptions.
Otherwise, a fault has occurred and Ursula can potentially get slashed for submitting an invalid proof.

It's not necessary to include the current C_r in the re-encryption request R in an interactive setting because Bob would never sign R_i+1 when Ursula can't prove Bob signed a given R_i beforehand.
Calling a WorkOrder a "Hash Chain" is understandably false in our use, thus it may be more apt to call it a linked list of signatures.
We call it a Hash Chain in this description to keep the visualization simple.


C_1 -> C_2 -> ... -> C_r


Protocol Described:

When Ursula receives a KFrag, she learns P and B_k and sets R_i = 0.
Bob will initiate a request for re-encryption that will be performed in two rounds:

Re-Encryption Protocol:
Round One:
    U <- (Policy_ID, Capsule, etc)
    B <- (U_k, R_i, (C_r if R_i > 0))

Round Two:
    B:  If C_r for R_i is valid or R_i == 0, then:
            R = Sign( H(P || U_k || B_k || R_i+1) )
        Else If C_r is invalid:
            Blockchain <- FaultProof(C_r, U_k, B_k)
    U <- R
    U:  If R for R_i+1 is valid, then:
            R_i += 1
            C += R, C_r = R
            CFrag = ReEncrypt(KFrag, Capsule)
        Else If R is invalid:
            Exit
    B <- CFrag


Optionally, Bob can reduce this to one round by holding the R_i state per Ursula:
Round One:
    B:  R = Sign( H(P || U_k || B_k || R_i+1) )
    U <- (Policy_ID, Capsule, R)
    U:  If R for R_i+1 is valid, then:
            R_i += 1
            C += R, C_r = R
            CFrag = ReEncrypt(KFrag, Capsule)
        Else If R is invalid:
            Exit
    B <- CFrag

The above protocol requires a strong assumption that Ursula returns the CFrag after receiving R in Round Two.
If this assumption is false, then it results in a Denial-of-Service attack against Bob and an attack against Alice's deposit.
However, this assumption can be significantly mitigated in a seperate challenge round that we discuss later.


Ursula can also receive on-chain payment by finalizing her WorkOrder in one round:

Payment Protocol:
Round One:
    C <- (C_r, P, U_k, B_k, R_i)
    C:  R_f' = H(P || U_k || B_k || R_i)
        If R_f' for C_r is valid, then:
            reward = R_i * fee
    U <- Pay(reward)


Improving Security:

Our protocol requires a strong assumption that Ursula will transmit the CFrag to Bob.
This is a difficult problem as there exists no fair-exchange protocol for two parties.
There are two protocol additions that can significantly aid in mitigating this assumption.
The first method is simple and requires that Alice increase only the number of n nodes available for re-encryption.
This reduces the chance that a critical mass of Ursulas would be offline when needed for re-encryption.

Our second addition is a three round challenge protocol that's more complex in that it requires blockchain communication, which is not ideal for Bob.
When Bob detects an Ursula node is offline, he can submit an on-chain challenge to her which requires her to respond on-chain with the appropriate CFrag.


Bob's Challenge Protocol:
Round One:
    B:  Request = ReEncryption_Request(Policy_ID, Capsule, etc)
    C <- ReEncryption_Request(Policy_ID, capsule, etc)

Round Two:
    U:  CFrag = ReEncrypt(Capsule_from_chain, KFrag)
    C <- CFrag
    C:  If CFrag is not valid or transaction_time not within challenge_time:
            Slash(Ursula)
        Else If On_Chain_Cfrags < m:
            Store_CFrag(CFrag)
        Else:
            Revoke_Policy(Policy_ID)

Round Three:
    B <- CFrag


It doesn't seem immediately obvious why there are three rounds instead of two, but this is due to the asynchronous communication between Bob, Ursula, and the blockchain.
It cannot be expected that Bob will use this CFrag because it requires that he get it off-chain, furthermore, by the time Ursula responds, he may not need it anymore.
The challenge protocol is not meant for downtime recovery, it's meant for punishment.
When a challenge is submitted, Ursula has a small period of time where she can respond.
If she doesn't respond with the appropriate CFrag in time, she will be slashed for being down.

It should also be noted that when m-1 CFrags are produced on the chain, the policy should be revoked to prevent a critical mass of CFrags appearing on chain and thereby delivering Bob persistent access.
However, to avoid a critical mass, Bob can create a "fake capsule" and submit that in lieu of the actual capsule on-chain.
This challenge does not fully close the gap yet because it opens the possibility of Bob always wanting on-chain re-encryption.
This can be mitigated by requiring a few random Ursulas to sign Bob's challenge request and sign an attestation that they also believe the target node to be offline.
Essentially, this will force cooperation between Bob and Ursula by requiring that several Ursulas attempt communication with the allegedly down node before going on-chain.


Alice's Challenge Protocol:

Thus far we have only discussed Bob <-> Ursula communications leaving us with the question of communications between Alice <-> Ursula.
Alice's challenges are far more complex than Bob's due to the secrecy requirement of the KFrag.

To keep this document simple, we will briefly describe the protocol without elaboration:
In essence, Alice submits an encryption (to preserve secrecy), a signature of the KFrag, and a ZK Proof-of-Knowledge of a shared secret used to encrypt the KFrag.
Ursula, in response, only needs to validate that the decryption of the KFrag is a valid KFrag.
If all is well, then she only needs to reply with an "OKAY" on-chain.
If the KFrag is invalid, she can generate a proof that the decryption of the KFrag with the provided shared secret is invalid thus asserting her innocence.

There are other problems that lie with complications in how Alice's sample for a policy is affected by having one of the sampled nodes offline, especially if they prove their uptime.
We can mitigate these issues with already existing functionalities in NuCypher, but we leave this protocol and the solutions for the surrounding problems for another document.


Open Problems:

While these challenges disincentivize misbehavior, they unfortunately don't incentivize good behavior.
The possibility of incentivizing good behavior and a healthy network is largely an open problem for us, but the immediately obvious solution may be a reputation-based system.
We can construct a simple reputation system based on policies accepted and policies denied by Ursula (whether they were actively or passively denied or not).
This is very similar to how taxi apps like Uber score their drivers for cancelling trips.
If an Ursula's score gets too low, she may be slashed for having a low score and Ursulas with consistently high scores may be rewarded or otherwise incentivized to maintain the score.

There are also problems that exist with who pays for Bob's challenges since we cannot assume Bob has enough funding to afford challenges.
We cannot assume that Bob will act rationally and get funding, either.
This gap can be closed by having another actor submit the challenge on behalf of Bob.
There is a possibility of using an Ursula to do this due to their shared interest in slashing a negligent Ursula.
However, the game theory for this seems far more tricky than is immediately apparent.
We leave solutions for these problems for later work.


Conclusion:

We've presented an efficient solution for payment per re-encryption via WorkOrder and a simplistic state channel.
The WorkOrder model is a very flexible method for receiving payment for re-encryptions that aligns economic incentives to the work performed without the weak guarantees of the confirmActivity model.
Without confirmActivity, we are left to cover two major assumptions in securty, but this is easily satisified via on-chain challenges.
With all the components described, we are left with a relatively flexible system that has a lot of room for upgrades, but mainnet worthy product.

Thanks to David and Sergey for helping me talk through a lot of these points.