Sortition

[ryardley]

In order to manage sortition of a ciphernode from a ranked list we need to manage the master list within solidity and dispatch change events to our swarm. By emitting the following events it should be possible for the Sortition module to reconstitute the list locally:

event CiphernodeAdded(address node, uint256 newRank, uint256 newListLen);
event CiphernodeRemoved(address node, uint256 oldRank, uint256 newListLen);

Sortition module when initialized will accept a local node ethereum address as part of it's configuration.

It will listen to all events from the contract and manage a list

Sortition module will listen for the following event:

event CommitteeRequested(
    uint256 e3Id,
    address filter,
    uint32[2] threshold,
    uint256 seed
);

It can then calculate a fisher yates shuffle of the list based on the M of N threshold and the random seed as well as the current node list it has a copy of.

It will also in parallel wait for the following event:

event E3Requested(
    uint256 e3Id,
    //...
    bytes params
);

Once it has received both events if the given local node address in part of the selected committee the module will dispatch a LocalNodeSelected event that will be a local event forwarding the relevant CommitteeRequested data which will trigger the Ciphernode actor to generate a keyshare.

Sortition module will also listen for CiphertextOutputPublished and dispatch LocalNodeDecryptionRequested which will forward much of the data

Sortition module needs to ensure it's registry list is up to date.

[ryardley]

I didn't mean to post this from my phone the other day - woops! Here is an updated version with more detail around what I have been thinking.

[ryardley]

• Rename existing events to fall in line with the current evm contract
• Sortition module re-broadcasts Local event which is not gossiped
• Sortition module manages list based on events
• Sortition module determines if local node is within committee size based on FY shuffle and only re-broadcasts in that case.

[auryn-macmillan]

In order to manage sortition of a ciphernode from a ranked list we need to manage the master list within solidity and dispatch change events to our swarm. By emitting the following events it should be possible for the Sortition module to reconstitute the list locally:

event CiphernodeAdded(address node, uint256 newRank, uint256 newListLen);
event CiphernodeRemoved(address node, uint256 oldRank, uint256 newListLen);

Currently, each ciphernode is simply added/removed from a mapping. The contract has no concept of the number of nodes or the order/rank. I think our initial thought here was that this could all be managed deterministically off-chain. However, I see that tracking some of these elements onchain would likely make the off-chain components simpler and more easily verifiable onchain.

I'd suggest that we use an incremental merkle tree, similar to what we just added for inputs.

Each leaf in the tree has an index, which corresponds to the rank you described. And the tree has a size which corresponds to len you described.

We're currently using a Lean incremental merkle tree, which doesn't really give us the ability to remove items from the tree. We can only zero them out in place. But we can explore other IMT implementations to try to find something that will better facilitate removing items.

[ryardley]

The verifiability of a merkle tree is awesome as the client can know it is in sync and we can create zkps to test inclusion. A node can blindly determine it's shuffled order based on it's rank in the original list as well as the list length and a seed. This is assuming every node in the list is valid.

We can have a list with zeroed leaves but will need to also maintain a list of these zeroed ranks as knowing this specific array of zeroed ranks is required to be applied to the algorhythm in order to determine which nodes are invalid. Every node that is calculating it's place would need to store this list of skipped ranks. Should this be a second merkletree?

Skiplist implementation example: https://github.com/ryardley/basic-fisher-yates-sortition/blob/master/src/main.rs

Another option would be that instead of storing a second list you maintain a single list of valid nodes and instead of zeroing out the leaf you swap it with the last inserted leaf (which you must remember to store) and broadcast the changes.

This would mean we can spare the complexity of managing the skipped list.

Whilst less gas efficient in terms of storage the two list idea is useful in that it could be easily applied to nodes that don't return their keyshare by adding them to the skiplist.

[auryn-macmillan]

Another option would be that instead of storing a second list you maintain a single list of valid nodes and instead of zeroing out the leaf you swap it with the last inserted leaf (which you must remember to store) and broadcast the changes.

Yes! I wrote out something similar in my draft response and then deleted it to go and figure out what is the best practice for this with PSE's IMT implementations. This seems like the right approach to me though.

[auryn-macmillan]

@ryardley, #44 implements the following events in ICiphernodeRegistry. Will this work?

    /// @notice This event MUST be emitted when a ciphernode is added to the registry.
    /// @param node Address of the ciphernode.
    /// @param index Index of the ciphernode in the registry.
    /// @param numNodes Number of ciphernodes in the registry.
    /// @param size Size of the registry.
    event CiphernodeAdded(
        address indexed node,
        uint256 index,
        uint256 numNodes,
        uint256 size
    );

    /// @notice This event MUST be emitted when a ciphernode is removed from the registry.
    /// @param node Address of the ciphernode.
    /// @param index Index of the ciphernode in the registry.
    /// @param numNodes Number of ciphernodes in the registry.
    /// @param size Size of the registry.
    event CiphernodeRemoved(
        address indexed node,
        uint256 index,
        uint256 numNodes,
        uint256 size
    );

Worth noting that index refers to the index in a merkle tree. So when an item is removed, that index is simply set to zero, meaning that the index of other nodes does not change.

[ryardley]

So the API we need in the sortition module aught to be something like:

trait Sortition {
  // triggered when a node requests if it is in the list 
  fn contains(&self, seed:u64, address: Address) -> bool;

  // triggered when a CiphernodeAdded event is received from the evm 
  fn add(&self, address: Address, rank: usize);
  
  // triggered when a CiphernodeRemoved event is received from the evm
  fn remove(&self, address: Address, rank: usize);
}

[ryardley]

This is implemented although not tested yet.