Open 0xvon opened 11 months ago
Thanks @0xvon for this analysis. The results make sense. And your opinion (in section 6) is also correct.
Regarding tables 5-1 and 5-2
where we can improve the implementation
I don't have suggestions (especially for BBS+) but a fresh pair of eyes might help.
where we can improve the benchmark (to measure more other metrics)
We don't benchmark the case where RandomizedPairingChecker
is used, i.e. this function. This is going to be efficient (trading off a little bit of security) when proof of knowledge of multiple signatures is done. See this test for an example. Also, we don't benchmark threshold signatures either using PS or BBS+ except in some tests where we print timing info.
There is another aspect of BBS+ that makes it favorable compared to PS when using it in a single issuer setting, the key size. BBS+ has constant (in number of signed messages) size secret and public key making it better for issuers with storage-constrained devices like hardware wallets. With BBS+, only the signature params depend on the number of messages and these can be generated publicly. With PS, the key sizes depend on the number of messages making the signer guess a reasonable upper bound on the number of messages while generating keys. But PS signatures lead to very simple threshold signatures (Coconut). Simple because the signers don't need to communicate while signing. The user creates a signature request and broadcasts to the signers and the user will aggregate the signers' responses as he gets them until he has a threshold. With BBS+, the signers run a multi-round protocol among themselves.
When you find some time, can you please run the above analysis of BBS signature (sig, proof) and share?
@lovesh Thanks for your reply!
For rows GenSig and VerSig, are $1 and $2 two different runs?
I saw these two parts as an output of benches, and seems just repeats for the same message length.
And thank you so much for giving great insights. I'll also try to analyze threshold sigs for BBS+/PS this and next week!
Thank you @0xvon .
Hi @lovesh , thank you for reviewing my previous PR.
1. Abstract
In this issue, let me report the benchmark result for BBS+ and PS signature. After this, I'd like to discuss:
2. Machine Spec (Local)
3. Benchmark Steps
4. Metrics
As the benchmark, I plotted these 4 metrics with changing the number of messages(attributes) for the statement.
5. Benchmark Results
I'll show 2 table and 4 graphs to compare the performance. the first row's label means num of messages(attributes) the unit is ms
Table 5-1: Metrics Result for BBS+
Table 5-2: Metrics Result for PS
And these graphs reflects the table.
Graph 5-1: Performance for GenSig/VerSig
Graph 5-2: Performance for GenProof/VerProof
6. Discussion
The result tells them:
I'll also provide a theoretical computation cost for each algorithm. L: message length, d: open length, d’: hidden length, R: generate random, E: exponation, P: pairing (XX) means time for message which has 30 attributes
Table 6-1. Computation Cost Theory for BBS+/PS
In my opinion: