Benchmarks for BBS+/PS

[grandchildrice]

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:

• if the result makes sense or not (compared to math theory)
• which algorithm is better (for each cases)
• where we can improve the implementation
• where we can improve the benchmark (to measure more other metrics)

2. Machine Spec (Local)

• Macbook Pro 13-inch
• M1 2020
• 16GB Memory
• macOS Ventura 13.5.2
• 512GB Storage

3. Benchmark Steps

git clone git@github.com:docknetwork/crypto.git && cd crypto
cargo bench --bench=bbs_plus_signature
cargo bench --bench=bbs_plus_proof
cargo bench --bench=ps_signature
cargo bench --bench=ps_proof

4. Metrics

As the benchmark, I plotted these 4 metrics with changing the number of messages(attributes) for the statement.

• GenSig Time
• VerSig Time
• GenProof Time
• VerProof Time
• (GenKey Time)
• (SigSize)
• (ProofSize)

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

• $2~ $5 changes the number of revealed messages

Table 5-1: Metrics Result for BBS+

		2	4	8	15	20	30	40	60
BBS+ GenSig[ms]	$1	0.62183	0.64961	0.71722	0.827	0.90691	1.045	1.1586	1.3416
	$2	1.7734	1.8958	2.0983	2.4408	2.6355	2.9816	3.4678	3.9194
	ave.	1.197615	1.272705	1.40776	1.6339	1.771205	2.0133	2.3132	2.6305
BBS+ VerSig[ms]	$1	2.7016	2.6374	2.7036	2.8611	2.9737	3.0657	3.1599	3.3106
	$2	3.2652	3.4031	3.6543	3.8949	4.0533	4.436	4.9669	5.4332
	ave.	2.9834	3.02025	3.17895	3.378	3.5135	3.75085	4.0634	4.3719
BBS+ GenProof[ms]	$1	2.0099	2.1014	2.8049	2.2209	2.7935	2.9676	3.2108	3.5762
	$2	1.96	2.067	2.8871	2.5812	2.735	2.9154	3.2154	3.6223
	$3		2.0406	2.5583	2.5471	2.7057	2.8124	3.046	3.5096
	$4		2.0601	2.3759	2.4619	2.6178	2.6977	2.9467	3.2454
	$5				2.361	2.4378	2.4847	2.6728	2.806
	max.	2.0099	2.1014	2.8871	2.5812	2.7935	2.9676	3.2154	3.6223
BBS+ VerProof[ms]	$1	3.5296	3.6233	3.7149	3.7544	3.8783	3.9414	4.0455	4.27
	$2	3.5781	3.624	3.6392	3.7953	3.8829	3.9481	4.1603	4.3722
	$3		3.6087	3.6367	3.8269	3.8823	4.007	4.2378	4.4628
	$4		3.5764	3.685	3.843	3.8835	4.0056	4.2087	4.593
	$5			3.7057	3.8491	3.8423	3.9704	4.182	4.3449
	max.	3.5781	3.624	3.7149	3.8491	3.8835	4.007	4.2378	4.593

Table 5-2: Metrics Result for PS

		2	4	8	15	20	30	40	60
PS GenSig[ms]	$1	0.51308	0.53232	0.56112	0.5592	0.56739	0.55512	0.57305	0.56861
	$2	0.51673	0.54085	0.5582	0.56925	0.56855	0.5598	0.56941	0.56456
	ave.	0.514905	0.536585	0.55966	0.564225	0.56797	0.55746	0.57123	0.566585
PS VerSig[ms]	$1	7.7095	7.7969	8.3695	9.0656	9.3218	10.162	10.586	12.122
	$2	7.3306	7.9236	7.9625	8.6113	9.0243	9.8657	10.314	11.564
	ave.	7.52005	7.86025	8.166	8.83845	9.17305	10.01385	10.45	11.843
PS GenProof[ms]	$1	5.9315	6.1475	6.6131	7.9361	8.0812	9.3107	10.846	12.102
	$2	5.7042	5.8307	6.5255	7.3908	8.0245	9.1593	10.259	11.957
	$3		5.7572	6.4059	7.225	7.7813	8.7491	9.765	11.255
	$4		5.419	6.2343	6.9428	7.3541	8.1313	8.5433	9.9965
	$5			5.6496	6.0622	6.2131	6.6925	6.622	7.3308
	max.	5.9315	6.1475	6.6131	7.9361	8.0812	9.3107	10.846	12.102
PS VerProof[ms]	$1	7.2431	7.4569	7.8751	8.3666	9.3701	9.656	10.866	12.167
	$2	7.327	7.5439	8.0123	8.4641	9.2729	9.6978	11.127	12.12
	$3	7.4569	7.5204	7.9836	8.5934	8.9852	9.8368	11.128	12.588
	$4		7.6356	8.0263	8.6903	9.0409	9.9549	11	12.433
	$5			7.9485	9.2128	9.0994	10.027	10.877	12.275
	max.	7.4569	7.6356	8.0263	9.2128	9.3701	10.027	11.128	12.588

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:

• PS is better for GenSig, but BBS+ is better for VerSig, GenProof and VerProof.
• GenSig time takes less than 1ms and looks almost constant (on PS).
• VerSig time on PS takes almost twice than on BBS+.
• GenProof time is positive for number of blinding messages (on both BBS+/PS).
• VerProof time is constant for any number of blinding messages (on both BBS+/PS).

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

	GenKey	GenSig	VerSig	GenProof	VerProof
BBS+	(L+1)RG1+1EG1	2RZp+(L+2)EG1(2.01ms)	(L+1)EG1 + 1EG2+2P(3.75ms)	2RZp+(d’+8)EG1+1EG2(2.96ms)	(L+3)EG1+2P(4.01ms)
PS	(L+1)RG1+(L+1)EG2	1RG1+1EG1(0.557ms)	LEG2+2P(10.01ms)	(d’+3)RZp+3EG1+(2d’+2)EG2(9.31ms)	(L+1)EG2+2P(10.03ms)

In my opinion:

• The result matches the theory.
  • PS signature looks less computation than BBS+ one, but PS mainly executes the multiplications on G2, which takes more time than G1.
• PS signature needs much less computation on GenSig, but needs much more computation on GenKey instead.
• BBS+ seems better because we mainly have less computation power in VerSig/GenProof/VerProof, which processes on the holder/verifier's mobile devices.

[lovesh]

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

1. For rows GenSig and VerSig, are $1 and $2 two different runs?
2. VerProof is more expensive than GenProof as verification involves pairings.
3. As you reveal more messages, proving and verification become cheaper as there is less to prove.

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?

[grandchildrice]

@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!

[lovesh]

Thank you @0xvon .