changed a year ago
Published Linked with GitHub

Mithril Decentralised Network

Abstract

We propose to integrate Mithril Signer and Aggregator nodes in a non-intrusive way side by side Cardano node in order to be able to use the Cardano network layer for Mithril inter-node communications.

In this way, we can significantly reduce the cost and effort required to build a decentralised network for Mithril by using Cardano's established infrastucture, with negligible to no impact on the performance and no impact on the security of the Cardano network.

Motivation

Mithril is a protocol based on Stake-based Threshold Multisignatures scheme which efficiently produces certificates which can be used in a trustless way. There are several usecases envisaged for the Cardano ecosystem such as fast bootstrapping of full nodes, enabling secure light wallets, and decentralised voting.

There are several key components and requirements that need to be in place:

  • a decentralised network of communicating nodes, consisting of Signers and Aggregators, refered to as Mithril network.
  • independent and direct access by individual Mithril nodes to chain data
  • almost all of Cardano's active stake is represented by Mithril network

Such a network, if built from the ground up, would require significant efforts and investment. Furthermore, the majority of SPO's, as the representatives of Cardano's active stake, will have to adopt and operate Mithril nodes alongside their Cardano node. This is not guaranteed without a sustainable incentive scheme in place due to the additional maintenance and operational costs. Mithril is a lightweight protocol with respect to both computation and network communication overhead and has less strict network guarantees requirements than Cardano consensus. Thus a natural solution is to use the Cardano network layer to significantly facilitate the development of Mithril protocol without a significant impact on the Cardano network or high maintenance efforts for the SPOs. The proposed solution is described in detail below.

Specification

Overview

This specification proposes to create 4 new mini-protocols in the Cardano network layer:

Mithril Signer Registration Protocol

This protocol is run in the node-2-node stack.

This is the protocol driving the diffusion of signers registration across the network. The purpose of this protocol is to ensure timely diffusion of each signer's registration for the next epoch.

How do we avoid last minute registrations from malicious players? Even if we have a time window for registering, we still need to allow for some marging so that messages reach the full network. But what stops adversaries from sending a registration request off-limits of the time-window? This is important, because if honest nodes have registrations with different users, their signatures will not be compatible for aggregation.

There's a need to limit the time range during which we allow for registration to be sent and to be received, as we want to avoid last minute flooding of registrations that would create discrepancy between signers that would prevent them from signing.

In order to achieve consensus on the signer registrations, a solution could be having the SPOs create a transaction on the main chain to register their Mithril verification keys (once every epoch or k epochs if a KES like mechanism is possible).

Protocol Summary

  • For each epoch, the protocol handler at each node maintains an ordered map of pool ids and Mithril signer registration requests.
  • A node can ask its neighbours to give registration requests for a range of pool ids they have registration for a given epoch:
    ​​haveSignersFor?(range = [0, 100])
    
  • Neighbour answers with the list it has available:
    ​​hasSigners!( list = [id_x, id_y, ..., id_z])
    
  • Node can ask for signers' registrations within list of pool ids it has not synchronized yet, which put the node in streaming mode:
    ​​-> giveMeSigners(list = [id_x, id_y])
    ​​<- signer(signer = id_x, registration = "0xcafe")
    ​​<- signer(signer = id_y, registration = "0xcafe") 
    ​​...
    ​​<- noMoreSigners
    
  • A node can also be engaged simultaneously with another neighbour into a symmetric signer registration diffusion process.

We expect this protocol to guarantee that if a node has emitted a signer registration for a given epoch, it will reach all signers before the end of the epoch. Or in other words, the set of registered signers must be identical for each signer node.

The pull system should ensure convergence of state for all involved nodes within the timespan of an epoch.

Protocol Logic

There is a delicate topic regarding the collection of signers' registration:

  • The signers' table to be consistent among enough nodes
  • The Cardano network should provide this consistency given the guarantee that it will broadcast a message to all the nodes within a delay.
  • The system must be able to reach consensus even if adversaries are participating (and misbehaving)

There is a need to define openWindow and closeWindow, which corresponds to the time we allow for registration (or when we decide to stop accepting registrations). These values could be tied to epoch numbers, or the security parameter k.

This problem is not trivial, and by no means resolved. We should check with the rest of the team (consensus/ledger/network) whether it makes sense to treat registration requests in a similar way as blocks are treated (e.g. registration pool waiting to be included in a 'RegistrationBlock'). If we treat them as such, then the 'k' parameter is again relevant for agreeing on 'when' a fork can no longer happen.

Protocol Description

Agency
Client has Agency StIdle, StSyncing
Server has Agency StFindSigners, StStreamingSigners
digraph signer_protocol {
  { 
     Start [ shape = plain ];
     StDone [ style = "black"];
     StSyncing, StIdle [ color = "green" ]; 
     StFindSigners, StStreamingSigners [ color = "blue" ];
   };
   
   Start -> StIdle;
   StIdle -> StSyncing [ label = "MsgOpenWindow"]; 
   StSyncing -> StFindSigners [ label = "MsgRequestRange" ];
   StFindSigners -> StSyncing [ label = "MsgIndexesList" ];
   StSyncing -> StStreamingSigners [ label = "MsgGetSignersAtIndexes" ];
   StStreamingSigners -> StStreamingSigners [ label = "MsgSigner" ];
   StStreamingSigners -> StSyncing [ label = "MsgNoMoreSigners" ]; 
   StSyncing -> StIdle [ label = "MsgCloseWindow" ];
   StIdle -> StDone [ label = "MsgClientDone" ];
}

State Machine

Protocol messages:

  • MsgOpenWindow: The signer registration synchronization window is open.
  • MsgCloseWindow: The signer registration synchronization window is closed.
  • MsgRequestRange(range): The client requests a range of registration requests.
  • MsgIndexesList(list): The server returns the list of indexes of signers he can provide to the client.
  • MsgGetSignersAtIndexes(list): The client asks for a list of registrations to the server given a list of signers indexes.
  • MsgSigner(signer_registration): The server streams a single signer registration.
  • MsgNoMoreSigners: The server ends streaming the signers' list.
  • MsgClientDone: The client terminates the protocol.

Transition table:

From state Message Parameters To State
StIdle MsgOpenWindow StSyncing
StSyncing MsgRequestRange range StFindSigners
StFindSigners MsgIndexList list StSyncing
StSyncing MsgGetSignersAtIndexes list StStreamingSigners
StStreamingSigners MsgSigner signer_registration StStreamingSigners
StStreamingSigners MsgNoMoreSigners StSyncing
StSyncing MsgCloseWindow StIdle
StIdle MsgClientDone StDone

Data Description / CDDL encoding specification

1
2 signerRegistrationMessage
3 = msgOpenWindow
4 / msgCloseWindow
5 / msgRequestRange
6 / msgIndexesList
7 / msgGetSignersAtIndexes
8 / msgSigner
9 / msgNoMoreSigners
10 / msgClientDone
11
12 msgOpenWindow = [ 0 ]
13 msgCloseWindow = [ 1 ]
14 msgRequestRange = [ 2, point , point ]
15 msgIndexesList = [ 3,  * point]
16 msgGetSignersAtIndexes = [ 4 , * point ]
17 msgSigner = [ 5,  signer_registration ]
18 msgNoMoreSigners = [ 6 ]
19 msgClientDone = [ 7 ]
20 
21 signer_registration =
22   [ registration_header
23   , party_index: word16
24   , party_id : bech32
25   , verification_key   : base64
26   , verification_key_signature   : base64
27   , operational_certificate : base64
28  ]

Mithril Signature Protocol

This protocol is run in the node-2-node stack.

This is the protocol driving the diffusion of signers signatures across the network. The purpose of this protocol is to ensure timely diffusion of each signer's signature for the current signing round.

A signing round is an event that is defined as:

  • Occurring at least once per epoch.
  • Computed deterministically by all the signer nodes by querying the Cardano state/chain.

Protocol Summary

  • For each signing round, the protocol handler at each node maintains an ordered map of pool ids and Mithril signer signatures requests.
  • A node can ask its neighbours to give signatures requests for a range of pool ids they have registration for a given epoch:
    ​​haveSignaturesFor?(range = [0, 100])
    
  • Neighbour answers with the list it has available:
    ​​hasSignatures!( list = [id_x, id_y, ..., id_z])
    
  • Node can ask for signers' signatures within list of pool ids it has not synchronized yet, which put the node in streaming mode:
    ​​-> giveMeSignatures(list = [id_x, id_y])
    ​​<- signature(signer = id_x, signature = "0xcafe")
    ​​<- signature(signer = id_y, signature = "0xcafe")
    ​​...
    ​​<- noMoreSignatures
    
  • A node can also be engaged simultaneously with another neighbour into a symmetric signer signature diffusion process.

Protocol Description

Agency
Client has Agency StIdle
Server has Agency StFindSignatures, StStreamingSignatures
digraph signature_protocol {
  { 
     Start [ shape = plain ];
     StDone [ style = "black"];
     StIdle [ color = "green" ]; 
     StFindSignatures, StStreamingSignatures [ color = "blue" ];
   };
   
   Start -> StIdle;
   StIdle -> StFindSignatures [ label = "MsgRequestRange" ];
   StFindSignatures -> StIdle [ label = "MsgIndexesList" ];
   StIdle -> StStreamingSignatures [ label = "MsgGetSignaturesAtIndexes" ];
   StStreamingSignatures -> StStreamingSignatures [ label = "MsgSignature" ];
   StStreamingSignatures -> StIdle [ label = "MsgNoMoreSignatures" ]; 
   StIdle -> StDone [ label = "MsgClientDone" ];
}

State Machine

Protocol messages:

  • MsgRequestRange(range): The client requests a range of signatures requests.
  • MsgIndexesList(list): The server returns the list of indexes of signers for which he can provide signatures to the client.
  • MsgGetSignaturesAtIndexes(list): The client asks for a list of signatures to the server given a list of signers indexes.
  • MsgSignature(signer_signature): The server streams a single signature.
  • MsgNoMoreSignatures: The server ends streaming the signatures' list.
  • MsgClientDone: The client terminates the protocol.

Transition table:

From state Message Parameters To State
StIdle MsgRequestRange range StFindSignatures
StFindSignatures MsgIndexList list StIdle
StIdle MsgGetSignaturesAtIndexes list StStreamingSignatures
StStreamingSignatures MsgSignature signer_signature StStreamingSignatures
StStreamingSignatures MsgNoMoreSignatures StIdle
StIdle MsgClientDone StDone

Data Description / CDDL encoding specification

1
2 signerSignatureMessage
3 = msgRequestRange
4 / msgIndexesList
5 / msgGetSignaturesAtIndexes
6 / msgSignature
7 / msgNoMoreSignatures
8 / msgClientDone
9
10 msgRequestRange = [ 0, point , point ]
11 msgIndexesList = [ 1,  * point]
12 msgGetSignaturesAtIndexes = [ 2 , * point ]
13 msgSignature = [ 3,  signer_signature ]
14 msgNoMoreSignatures = [ 4 ]
15 msgClientDone = [ 5 ]
16 
17 signer_signature =
18   [ signature_header
19   , party_index: word16
20   , single_signature   : base64
21   , won_lotteries   : * point
22  ]

Mithril Local Submission Protocol

This protocol is run in the node-2-client stack.

This is the protocol used by signers to broadcast their registration and signatures. Note that this protocol allows a signer to send both their registration for a given epoch and their signature for a given signing round.

Summary

  • Client (Mithril signer) gets a trigger to register for a new epoch.
  • Client sends signer registration request to Cardano node through local connection.
  • Server checks that registration request is valid and adds it to its internal map of registered signers.
  • Process is exactly the same for signatures but happens more often (once per signing round instead of once per epoch)

Protocol Description

Agency
Client has Agency StIdle, StDone
Server has Agency StRegistering, StSigning
digraph mithril_local_submission {
   { 
     Start [  shape = plain, style = invis  ];
     StStop [style = "black" ]
     StIdle, StDone [ color = "green" ]; 
     StRegistering, StSigning [ color = "blue" ];
   };
   
   Start -> StIdle;
   StIdle -> StRegistering [ label = "MsgSubmitRegistration" ];
   StRegistering -> StDone [ label = "MsgRegistrationSuccessful" ];
   StRegistering-> StDone  [ label = "MsgRegistrationError" ];
   StIdle -> StSigning [ label = "MsgSubmitSignature" ];
   StSigning -> StDone [ label = "MsgSignatureSuccessful" ];
   StSigning -> StDone  [ label = "MsgSignatureError" ];
   StDone -> StStop  [ label = "MsgClientDone" ];
}

State Machine

Protocol messages:

  • MsgSubmitRegistration(signer_registration): The client submits a signer registration.
  • MsgRegistrationSuccessful: The server returns success for the signer registration.
  • MsgRegistrationError(error): The server returns error for the signer registration.
  • MsgSubmitSignature(signer_signature): The client submits a signer signature.
  • MsgSignatureSuccessful: The server returns success for the signer signature.
  • MsgSignatureError(error): The server returns error for the signer signature.
  • MsgClientDone: The client terminates the protocol.

Transition table:

From state Message Parameters To State
StIdle MsgSubmitRegistration signer_registration StRegistering
StRegistering MsgRegistrationSuccessful StDone
StRegistering MsgRegistrationError error StDone
StIdle MsgSubmitSignature signer_signature StSigning
StSigning MsgSignatureSuccessful StDone
StSigning MsgSignatureError error StDone
StIdle MsgClientDone StDone

Data Description / CDDL encoding specification

1
2 localSubmissionMessage
3 = msgSubmitRegistration
4 / msgRegistrationSuccessful
5 / msgRegistrationError
5 / msgSubmitSignature
6 / msgSignatureSuccessful
7 / msgSignatureError
8 / msgClientDone
9
10 msgSubmitRegistration = [ 0, signer_registration ]
11 msgRegistrationSuccessful = [ 1 ]
12 msgRegistrationError = [ 2 , error ]
13 msgSubmitSignature = [ 3,  signer_signature ]
14 msgSignatureSuccessful = [ 4 ]
15 msgSignatureError = [ 5 , error ]
16 msgClientDone = [ 6 ]
17
18 signer_registration =
19   [ registration_header
20   , party_index: word16
21   , party_id : bech32
22   , verification_key   : base64
23   , verification_key_signature   : base64
24   , operational_certificate : base64
25  ]
26
27 signer_signature =
28   [ signature_header
29   , party_index: word16
30   , single_signature   : base64
31   , won_lotteries   : * point
32  ]
33
34 error = 
35   [ error_message : tstr]
33 

Mithril Local Notification Protocol

This protocol is run in the node-2-client stack.

This is the protocol used by signers and aggregators to be notified of registration and signatures of signers.

Summary

  • Client requests next signature for current signing round from server.
  • Server sends the next available signature from the currently available signature map (\(\implies\) server maintains a tally of sent signatures).
  • Server sends MsgNoSignature if there aren't more signatures.
  • Process is exactly the same for registrations.

Protocol Description

Agency
Client has Agency StIdle, StStop
Server has Agency StHasSignature, StWaitSignature, StHasRegistration, StWaitRegistration
digraph mithril_local_notification {
   { 
     Start [  shape = plain, style = invis  ];
     StStop [style = "black" ]
     StIdle [ color = "green" ];
     StHasSignature, StWaitSignature  [ color = "blue" ];
     StHasRegistration, StWaitRegistration  [ color = "blue" ];
   };
   
   StStart -> StIdle;
   
   StIdle -> StHasRegistration [ label = "MsgNextRegistration" ];
   StHasRegistration -> StIdle [ label = "MsgGotRegistration" ];
   StHasRegistration -> StWaitRegistration [ label = "MsgNoRegistration" ];
   StWaitRegistration -> StIdle [ label = "MsgGotRegistration" ];
   StWaitRegistration -> StIdle [ label = "MsgTimeout" ];
   
   StIdle -> StHasSignature [ label = "MsgNextSignature" ];
   StHasSignature -> StIdle [ label = "MsgGotSignature" ];
   StHasSignature -> StWaitSignature [ label = "MsgNoSignature" ];
   StWaitSignature -> StIdle [ label = "MsgGotSignature" ];
   StWaitSignature -> StIdle [ label = "MsgTimeout" ];
   
   StIdle -> StStop [ label = "MsgClientDone" ];
}

The following state machine does not represent the full semantics of the Mithril protocol, which requires to collect registrations for an epoch before collecting signatures for the next epoch.

State Machine

Protocol messages:

  • MsgNextRegistration(signer_registration): The server returns the next signer registration.
  • MsgGotRegistration: The server has no more signer registration to return.
  • MsgNoRegistration: The server has no more signer registration to return.
  • MsgNextSignature: The client asks for the next signer signature.
  • MsgGotSignature(signer_signature): The server returns the next signer signature.
  • MsgNoSignature: The server has no more signer signature to return.
  • MsgTimeout: The server did not answer and times out.

Transition table:

From state Message Parameters To State
StIdle MsgNextRegistration StHasRegistration
StHasRegistration MsgGotRegistration signer_registration StIdle
StHasRegistration MsgNoRegistration StWaitRegistration
StWaitRegistration MsgGotRegistration signer_registration StIdle
StWaitRegistration MsgTimeout StIdle
StIdle MsgNextSignature StHasSignature
StHasSignature MsgGotSignature signer_signature StIdle
StHasSignature MsgNoSignature StWaitSignature
StWaitSignature MsgGotSignature signer_signature StIdle
StWaitSignature MsgTimeout StIdle
StIdle MsgClientDone StStop

Data Description / CDDL encoding specification

1
2 localNotificationMessage
3 = msgNextRegistration
4 / msgGotRegistration
5 / msgNoRegistration
5 / msgNextSignature
6 / msgGotSignature
7 / msgNoSignature
8 / msgTimeout
8 / msgClientDone
9
10 msgNextRegistration = [ 0 ]
11 msgGotRegistration = [ 1 ]
12 msgRegistrationError = [ 2 , signer_registration ]
13 msgNoRegistration = [ 3 ]
14 msgNextSignature = [ 4 ]
15 msgGotSignature = [ 5 , signer_signature ]
16 msgNoSignature = [ 6 ]
17 msgTimeout = [ 7 ]
18 msgClientDone = [ 8 ]
19
20 signer_registration =
21   [ registration_header
22   , party_index: word16
23   , party_id : bech32
24   , verification_key   : base64
25   , verification_key_signature   : base64
26   , operational_certificate : base64
27  ]
28
29 signer_signature =
30   [ signature_header
31   , party_index: word16
32   , single_signature   : base64
33   , won_lotteries   : * point
34  ]
35 

Rationale

Why are we proposing this CIP?

  • Mithril requires strong network foundations to support interactions between its various nodes:

    • Mithril needs to exist in a decentralized context where the aggregation of the multi-signatures can be done by any aggregator node (which is not necessarily a signer node i.e. run by a SPO).
    • Mithril needs participation of all or nearly all of the Cardano network SPOs to provide maximal security to the multi-signatures embedded in the certificates.
    • Creating a separate network would entail significant costs and efforts (there are more than 3,000 SPOs which would need to be connected with resilient and secure network, and much more passive nodes).
    • The Cardano network is very efficient for diffusion (e.g. broadcasting) which is precisely what is needed for Mithril.
    • Mithril signer node needs to run on the same machine as the Cardano block producing node (to access the registration keys - KES and OpCert). Given that they have to run on the same machine, it makes sense to use the same network layer, which will also facilitate a high level of participation.
  • Why it would be great for Cardano to support Mithril within its network?

    • Mithril is a key part to make the Cardano Ecosystem scalable.
    • Future instances of the Cardano protocol could leverage Mithril signatures (e.g. Ouroboros Leios).
    • There are known benefits for clients (wallets, exchanges, dapps) in being able to synchronise with the full chain state faster than what is currently possible using standard process (e.g. restoring a Daedalus wallet on mainnet is 15-20x faster with Mithril).
    • Mithril could also be valuable for governance purposes of the Cardano Ecosystem.
  • What would be the overhead of operating a Mithril node on the Cardano network?

    • The overhead to the network is very low as there are few messages that need to be exchanged only few times a day (less than 10 signing rounds a day).
    • There will be as many registration requests as there are SPOs (around 3,500) per epoch (each less than 10KB): this means at most ~35MB / epoch / Cardano node.
    • There will be as many signatures as there are 'registered' SPOs (around 3,500) per signing round (each less than 1KB): this means at most ~3.5MB / signing round / Cardano node or ~175MB / epoch / Cardano node.
    • The CPU overhead of a signer is very low as the most intensive part of the process takes a few seconds once for every signing round (less than 10 signing rounds a day).

Path to Active

Acceptance Criteria

  1. A Cardano node implementing the previously described mini-protocols is released for production.
  2. A Mithril Signer node communicating with the Cardano node through mini-protocols is released.
  3. A mithril Aggregator producing multi-signatures embedded into certificates using the mini-protocols is released.

Implementation Plan

  • "Formal" specification of the protocols along with vectors/conformance checker for protocol's structure and state machine logic.
  • Validate protocol behaviour with all relevant parties (Network and Node teams).
  • Validate performance profile and impact on Cardano network.
  • Implement Cardano networking mini-protocols in the Cardano node.
  • Implement Cardano local mini-protocols in Mithril Signer and Aggregator nodes.

A hard-fork of the Cardano chain is not required during this implementation plan.

Further Reading

Copyright

This CIP is licensed under Apache-2.0

Select a repo