sui
sui copied to clipboard
MystenLabs
Change CertifiedTransaction to use bitmap instead of AuthorityNames
This is an idea to save some space in the CertifiedTransaction, which contains this field:
pub signatures: Vec<(AuthorityName, AuthoritySignature)>,
While the signatures vary, the AuthorityNames are repeated many times for all certified TX's in an epoch. This is because the set of authorities for a given epoch are fixed.
So instead, we can store the following:
pub struct AuthoritySignatures {
authority_bitmap: Vec<u8>,
signatures: Vec<AuthoritySignature>,
The authority_bitmap would be a bitmap which has n bits where n = number of authorities in the epoch committee. One bit is assigned for each possible authority. The bitmap would have a 1 for each authority which has a signature included.
The signatures would be in order of the appearance of authorities in the bitmap which has set bits.
The space saved would be almost 32 bytes per authority.
//cc @gdanezis
For this to work we have to maintain an ordered map/list (queryable by index) of authorities per epoch and atm we use a BTreeMap and HashMap. Well, we can still do the ugly btreemap.iter().nth() and reuse the current voting_rights map to query by index. Anyway, this functionality requires some refactoring.
We could also explore delegating sig verification to this ordered data structure (thus, under committee ONLY) that will carry the ID -> pubKey mapping. It is actually safer to only allow authority sig verification via the committee structure, to avoid surprise bugs.
Note, if we use u8 IDs, we should assume that the max num of authorities is 256. Do we want to enforce that limit in our application or explore a more efficient encoding?
@kchalkias regarding encoding, a bitmap uses only 1 bit per authority and does not have an upper bound limit like a fixed size u8. Let's say for up to 256 authorities, where you would expect (2f+1) or say 193 authorities.
u8 encoding (with max 256 limit) - 193 bytes dumb bitmap - 32 bytes
There are two options, right? a) we include a u8 per authority signature, where this counter is a mapping between PubKey -> ID u8 b) a generic bitmap for the aggregated validators, so 32 bytes will be able to accommodate up to 256 validators.
benefits of (a) and (b), assuming a maximum of 256 authorities.
- If there are less than 32 validator signatures, than (a) requires less bytes.
- For more than 32 signatures, (b) is more succinct.
Then, because we expect 2f+1 sigs, we'll pick option (b) and we'll know that the bitmap size is highly dependent on the number of max validators. Also signatures should be ordered by validator ID sequence (while option (a) does not require ordering).
We'll use option (b) and update the model when accountable BLS is available.
