Problem
Data volume transmitted in Hare is surprisingly large (at the range of hundreds-of-megabytes, as measured on our test environment with 300 nodes). We would like to understand what is causing this and if there is any chance to improve this situation.
Diagnosis
The root cause of this turns out to be including collections of status messages as part of every:
- safe value proofs
- commit certificate
Solution
Messages included inside a commit certificate and a safe value proof are status messages. Say C is a commit certificate. By design of Hare, all status messages included in C must have been broadcast over gossip before C was created. Moreover, these status messages all belong to the round preceding the round where C was created. Therefore, by our security assumptions, these status messages should have been delivered to all honest nodes before C was delivered.
Similar mechanics occurs in case of safe value proofs.
It feels like replacing all status messages in a commit certificate and a safe value proof with just message hashes, combined with caching of messages in node, could provide a significant reduction in data volume transmitted, while retaining all the properties of Hare.
Calculations
I did a calculation of data volume for an “idealized” Hare protocol.
I assumed the following structures of messages (for the un-optimized protocol):
abstract class Message {
val sender: NodeId
val sig: Signature
val eligibilityProof: Signature
}
class CommitCertificate {
val acceptedSet: CollectionOfMarbles
val iteration: Int
val commitMessages: Array[CommitMsg]
}
class SafeValueProof {
val iteration: Int
val statusMessages: Set[StatusMsg]
val magicMessage: StatusMsg
}
class PreroundMsg extends Message {
val inputSet: CollectionOfMarbles
}
class StatusMsg extends Message {
val iteration: Int
val certifiedIteration: Int
val acceptedSet: CollectionOfMarbles
}
class ProposalMsg extends Message {
val iteration: Int
val safeValueProof: SafeValueProof
}
class CommitMsg extends Message {
val iteration: Int
val commitCandidate: CollectionOfMarbles
}
class NotifyMsg extends Message {
val iteration: Int
val commitCertificate: CommitCertificate
}
In the above, CollectionOfMarbles type is used to represent collections of elements we are attempting to achieve consensus on (and elements are 32-bytes long hashes).
val numberOfNodes: Int = 100000
val maxNumberOfMarblesInACollection: Int = 50
val c: Int = 800 //committee size
val d: Int = 5 //target number of leader candidates to be elected in the proposal round
val nodeId: Int = 32
val marbleId: Int = 32
val msgSignature: Int = 64
val eligibilityProof: Int = 64
val iterationNumber: Int = 4
val messageHash: Int = 32
val senderId: Int = nodeId
val marblesCollectionTotal: Int = maxNumberOfMarblesInACollection * marbleId
val msgMetadata: Int = senderId + iterationNumber + eligibilityProof + msgSignature
class MsgVolumesProfile {
var preRoundMsg: Int = 0
var statusMsg: Int = 0
var svp: Int = 0
var proposalMsg: Int = 0
var commitMsg: Int = 0
var commitCertificate: Int = 0
var notifyMsg: Int = 0
}
fun originalProtocol: MsgVolumesProfile = {
val p = new MsgVolumesProfile
p.preRoundMsg = senderId + marblesCollectionTotal + eligibilityProof + msgSignature
p.statusMsg = msgMetadata + iterationNumber + marblesCollectionTotal
p.svp = iterationNumber + c * p.statusMsg + marblesCollectionTotal
p.proposalMsg = msgMetadata + p.svp
p.commitMsg = msgMetadata + marblesCollectionTotal
p.commitCertificate = marblesCollectionTotal + iterationNumber + c * p.commitMsg
p.notifyMsg = msgMetadata + p.commitCertificate
return p
}
fun optimizedProtocol: MsgVolumesProfile = {
val p = new MsgVolumesProfile
p.preRoundMsg = senderId + marblesCollectionTotal + eligibilityProof + msgSignature
p.statusMsg = msgMetadata + iterationNumber + marblesCollectionTotal
p.svp = iterationNumber + c * messageHash + marblesCollectionTotal
p.proposalMsg = msgMetadata + p.svp
p.commitMsg = msgMetadata + marblesCollectionTotal
p.commitCertificate = marblesCollectionTotal + iterationNumber + c * messageHash
p.notifyMsg = msgMetadata + p.commitCertificate
return p
}
The final results (for given profile: MsgVolumesProfile) are achieved as:
val preRoundTotal: Int = profile.preRoundMsg * c
val statusTotal: Int = profile.statusMsg * c
val proposalTotal: Int = profile.proposalMsg * d
val commitTotal: Int = profile.commitMsg * c
val notifyTotal: Int = profile.notifyMsg * c
val downloadInIterationZero: Int = preRoundTotal + statusTotal + proposalTotal + commitTotal + notifyTotal
val downloadInIterationOne: Int = statusTotal + proposalTotal + commitTotal + notifyTotal
These are the numbers I achieved:
----------------- original protocol [all values in megabytes] -------------------
download in iteration 0: 1088.80
download in iteration 1: 1087.46
commit certificate: 1.3473548889160156
svp: 1.3504066467285156
pre round: 1.34
status round: 1.35
proposal round: 6.75
commit round: 1.35
notify round: 1078.01
----------------- optimized protocol [all values in megabytes] -------------------
download in iteration 0: 25.05
download in iteration 1: 23.71
commit certificate: 0.025943756103515625
svp: 0.025943756103515625
pre round: 1.34
status round: 1.35
proposal round: 0.13
commit round: 1.35
notify round: 20.88