Performance measurements

[dbosk]

We want to measure how much computations and storage the protocol requires in different stages. We are mostly interested in efficiency (or lack thereof) during the protest, when all parts rely on battery. We need to evaluate

• [ ] how expensive is the distance bounding proof of knowledge during witnessing (DBPK in Fig 5) for a witness?
• [ ] how expensive are the needed PRF computations for the witness?

Assume that a witness must run the protocol 1000 times.

Communication: how expensive is the communication in terms of energy (battery consumption)?

• [ ] keeping the Bluetooth/wifi on and scanning?
• [ ] sending all the needed messages?

Storage:

• [ ] what's the size of each proof share?

We should have a table of costs. Some entries can come from our performance measurements and some can come from the literature.

[dbosk]

We need an implementation of the anonymous credentials, see #54. We are interested in how expensive they are to compute, the PRFs and the NIZK proofs. Some values can be precomputed, but specifically the computations for the witnesses (PRFs) must be done over and over during the protest. The NIZK proofs can be computed afterwards, but we want to know the order of magnitude of the time it will take to generate the NIZK proofs. We also want to know their size for storage. In summary:

• computational resources to compute many PRFs (for the witnesses), time and energy consumption.
• computational resources to compute (many) NIZK proofs, time mostly.
• storage size of the proof shares and their NIZK proofs.

We need an implementation of (parts of) the distance-bounding protocol, see #55. The setup and verification phases of the distance-bounding must be run over and over during the protest, we want to know how expensive is that; will it drain the smartphone battery too quickly? In summary:

• computational resources to compute setup phase, time and energy consumption.
• computational resources to compute verification phase, time and energy consumption.

Finally, we would like to estimate the time for verifying a protest, mostly time consumption is interesting here. (Once #54 and #50 are done, this should be possible to measure.)

It would be a plus to also have an implementation of an adapted blockchain, see #50. Then we can include measurements of time to submit and download. The download is particularly interesting as part of the verification timing.

[dbosk]

We can skip the evaluation of the other parts for now. It's most important to know for the times we run on battery.

[dbosk]

How to evaluate the battery usage? Run on a laptop and map to a smartphone by some other performance measurements that's been done on both laptop and smartphone.

[dbosk]

Energy consumption for communication, e.g. having Bluetooth on, sending lots of messages etc. Bandwidth?

[dbosk]

Table of all costs, some values come from Henri's measurements, some must be estimated otherwise (e.g. other papers).

[dbosk]

Maybe QPython or QPython3 can be used to run our implementation in Charm on an Android device?

[dbosk]

We have two cases to test performance: trusted Jane (few witnesses, witnesses for redundancy) and collusion threshold (many witnesses, must reach threshold).

[dbosk]

For now, just compare to Idemix. We'll be 10 times slower than Idemix.

[dbosk]

Review this issue @sbuc, @seb.