nucypher sidechain

Derek Pierre edited this page Oct 29, 2018 · 9 revisions

NuCypher sidechain design

Intro

When Bob asks Ursula to re-encrypt, he can go two ways. He can go totally off-chain, and then he's on mercy of Ursulas being honest.

But Bob can also choose his request to be enforced. For that, he can log his request on side-chain, and now, if Ursula doesn't re-encrypt that in a certain timeframe, she gets slashed.

Threat model. What we want to avoid

  • Ursulas systematically not submitting blocks to the side-chain. We want the majority of Ursulas to do that.
  • Ursulas submitting wrong blocks to side-chain.
  • Ethereum miners forming blocks in such a way that they are selected more often as block submitters on the sidechain.
  • Submitting blocks with valid but old re-encryptions onto the side-chain with the intent to create a spam attack.
  • Bob submitting too many re-encryptions to overload validators of the side-chain or a specific Ursula.
  • Causing wrong Ursulas to be penalized when exiting side-chain.
  • Not being penalized while submitting wrong blocks (due to too high fees for others to submit proofs?).

Sidechain

Ursula re-encrypting correctly, Ursula misbehaving and Ursula having a re-encryption pending are the three things which we want to report to blockchain. These merged in three different Merkle trees. Let's call them tree_req, tree_good and tree_bad.

In tree_req, there are request for Ursulas in format: (capsule, verification_keys, policy_proof[u], sig_b), where policy_proof[u] proves that Ursula u indeed should process for this policy, and sig_b is a signature by Bob (in order to apply per-Bob limits). In tree_good and tree_bad, there are responses by Ursulas in form (cfrag, sig_u). Absence of Ursula's signature isn't recorded and considered as "no response".

We have a sidechain with relatively rare blocks (every s Ethereum blocks) which commit Merkle roots to Etherereum blockchain. Also, every day or so (defined by timestamp), we determine which Ursula should be slashed and which not, and continue.

Ethereum blockchain                 Sidechain

       |                                |
      [ ]                           +---+---+
       |                            |       |
      [ ]                           |   i   |
       |                            |       |
      [ ]                           +---+---+
       |          Ursula[i]             |
       |     (root_good, root_bad)      |
      [ ] <-----------------------------+
       |                                |
      [ ]                           +---+---+
       |                            |       |
      [ ]                           |  i+1  |
       |                            |       |
      [ ]                           +---+---+
       |          Ursula[i+1]           |
       |      (root_good, root_bad)     |
      [ ] <-----------------------------+
       |                                |
      [ ]                           +---+---+
       |                            |       |
      [ ]                           |  i+2  |
       |                            |       |
      [ ]                           +---+---+
       |          Ursula[i+2]           |
       |      (root_good, root_bad)     |
      [ ] <-----------------------------+
       |                                |

Each sidechain block i should be committed into an Ethereum block with number e such as:

(e >= genesis + i * s) and (e < genesis + i * s + s).

There is a list of active Ursulas ursulas such as all Ursulas can be enumerated as ursulas[u]. Each Ursula ursulas[i] should be selected pseudo-randomly, but proportional to the amount of stake she has. We discuss it separately at the end of the issue.

Sidechain blocks are replicated by all Ursulas, only Merkle roots are stored on Ethereum blockchain. Each Ursula can check validity of every block. The block is valid if:

  • Every entry in tree_good is correct and didn't exist previously (maybe the latter isn't required?).
  • Every entry in tree_bad has an incorrect cfrag.
  • Every entry in tree_req has a correct re-encryption request. So, each Ursula can validate any block and form her own copy of the sidechain, and all honest Ursulas should have the same sidechain.

It is possible that a malicious Ursula commits a Merkle root of an invalid block onto Ethereum blockchain. In this case, an on-chain smart contract should be able to keep track of all sidechain forks. Honest Ursulas will build only on top of the valid sidechain. Also the Ethereum smart contract should drop shortest sidechains after some threshold number of block confirmations. It is important to notice that waiting for sidechain block confirmations happens on main Ethereum blockchain.

Pseudocode for selecting the fork based on number of confirmations in the smart contract could look like:

n_confirmations = 10
s = ...  # ETH blocks in sidechain block
sidechain_blocks = {}  # n -> (root, prev_n)
confirmation_pool_h = [None] * n_confirmations
confirmation_pool_n = [None] * n_confirmations
chain_sizes = [None] * n_confirmations
pool_cursor = 0

def current_sidechain_block():
    return (self.blockNumber - genesis) // s

def add_block(prev_hash, root_hash):
    current_block = current_sidechain_block()
    check_ursula_permissions()
    assert current_block not in sidechain_blocks

    assert prev_hash in confirmation_pool_h
    pool_cursor += 1
    confirmation_pool_h[pool_cursor] = root_hash
    confirmation_pool_n[pool_cursor] = current_block
    chain_size = chain_sizes[confirmation_pool_h.index(prev_hash)] + 1
    prev_n = chain_sizes[confirmation_pool_h.index(prev_hash)]
    chain_sizes[current_cursor] = chain_size
    sidechain_blocks[current_block] = (root_hash, prev_n)

def get_sidechain_head():
    return confirmation_pool[pool_cursor]

def get_last_confirmed():
    # Simply choose the longest chain from the pool
    # and iterate n_confirmations to the past
    i = argmax(chain_sizes)
    n = confirmation_pool_n[i]
    for j in range(n_confirmations):
        root_hash, n = sidechain_blocks[n]
    return root_hash

Merging to Ethereum blockchain

It is common to have participants "exiting" sidechains. In our case, "exit" means giving an Ethereum smart contract information about who gets slashed and who doesn't, depending on the misbehavior reported.

The basic idea is the following. Periodically (every period which is equal to 1 day), nodes self-report about how they behaved and get slashed accordingly (eventually). However, if they report incorrectly, anyone can submit a Merkle proof (which can be checked on-chain), and they'll be penalized (very hard) for lying, while the whistleblower (William?) gets a significant bounty. The whistleblower can report at any time until the next period ended. The proof has to belong to the previous period though.

There could be a proof that a bad response took place (proof of inclusion in tree_bad over the last period). This is a "final" proof.

There could be a proof that a request was not responded to for too long by having a proof of inclusion into a sufficiently old (but in-period) tree_req. This proof can potentially be wrong, and anyone can disprove it by showing that the correct response is posted in tree_good.

Committing a sidechain block should be rewarded so that Ursulas are incentivized to do it. Alternatively, they could be penalized for non-submission.

Pseudorandom selection of Ursulas

First of all, we don't care as much about the unpredictability of Ursula selection as we care that random selection of Ursula should be unaffected by anyone (including Ethereum miners). Simply, every sidechain block we can execute on Ethereum blockchain:

random_ursula = uint(hash(random_ursula))

(note tht this is a biased way to generate random numbers, the proper one is mentioned later).

where we have hash is <some_256_bit_hash> at sidechain's block 0. If for some reason (?) we want random_ursula to be unpredictable, we can throw an ID of each new Ursula joining the network into the hash.

The sidechain block i has to be produced only by one specific Ursula. It would be very simple to select between Ursulas with equal probability:

def check_ursula_permissions():
    assert ursulas[u] == msg.sender
    assert u == random_ursula % len(ursulas)

If this Ursula misses her spot to commit the Merkle root, she cannot do it anymore.

However, we need to select Ursulas with probability proportional to their stake. We can do it in the following way. Every period, Ursulas do in confirm_activity:

stake_cumsum = {uint16 -> uint256}  # ursula_number -> cumulative stake
total_stake = uint256
ursulas_number: uint16 = 0

def confirm_activity(...):
    ...
    # Ursula number is iterated from 0 to number of ursulas
    if first_ursula():  # First Ursula to be confirmed in this period
        total_stake = 0
        ursulas_number = 0
        stake_cumsum[0] = 0
    stake_cumsum[ursulas_number] = total_stake
    stake_cumsum[ursulas_number + 1] = 0  # in case it was the last Ursula
    total_stake += stakes[u]

Keys of mapping stake_cumsum have a form 0, 1, 2, ..., N, 0.

Selection of random Ursula (in the next period!) would be done through binary search.

def check_ursula_permissions():
    assert ursulas[u] == msg.sender
    stake_pos = random_ursula % total_stake
    u_ = binary_search(stake_cumsum, stake_pos)  # done in log2(total_stake) time
    assert u == u_

Also, the PRNG should be made unbiased, for example in the following manner:

while True:
    random_ursula = uint(hash(random_ursula))
    if random_ursula < max_uint // total_stake * total_stake:
        break
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.