Implementation Feedback

[bellebaum]

We have implemented the current spec in C: https://github.com/Fraunhofer-AISEC/libbbs

Our implementation tries to simplify certain constructions. For instance, it avoids to create long arrays and can generally be adapted to provide an incremental API (which is useful if 2^64 messages, or even 2^16, shall be supported in any application). While the README lists the current performance characteristics for the main interface, we might eventually provide optimized interfaces for e.g. signers.

Some random feedback from working with the current draft:

1. The draft layout makes it quite hard to implement the spec in a straight forward way, because what ends up being only a few lines of code is separated into a lot of subroutines, each with (sometimes redundant) deserialization and validation steps. My guess that this was done in preparation for extensions (e.g. blind BBS signatures), but it does slow down development and makes it more likely to overlook crucial validation steps (this happened to me). Where validation steps in subroutines are not meaningful to a standalone implementation, it seems more straightforward to document the assumptions enforced by the validation, and perform necessary validation in the calling functions, e.g. in extensions.
2. This modularity sometimes creates additional work. For instance, during our simplifications I decided to simply not implement the special rules for serializing/deserializing the identity element (instead returning an error). This simplified the code not just in the deserialization, but also made several validation steps obsolete. Unless there are good reasons against it, I would recommend considering this for the draft as well.
3. The deterministic generation of random scalars for the test vectors was a pain, as expected. I ended up implementing a callback for these values, which is a hash-to-scalar-powered PRF from a random 32-byte salt during normal signing, and replaced by the mockup in the draft for the tests. If anything, the random function gives slightly less power to an adversary influencing the OS randomness.

As a concrete example of possible "simplifications", consider the following procedure for Sign:

1. (msg_1, ..., msg_L) = messages_to_scalars(messages, api_id)
2. (Q_1, H_1, ..., H_L) = create_generators(length(messages)+1, api_id)

3. domain = calculate_domain(PK, (Q_1,H_1, ..., H_L), header, api_id)
4. e = hash_to_scalar(serialize((SK, msg_1, ..., msg_L, domain)),
                                                     hash_to_scalar_dst)

5. B = P1 + Q_1 * domain + H_1 * msg_1 + ... + H_L * msg_L
6. A = B * (1 / (SK + e))

7. return serialize((A, e))

This is seven steps instead of ten, not counting the superfluous length checks in CoreSign (thus also rendering the INVALID check redundant). Furthermore, the text about a possible identity A becomes superfluous if serialization of A returns INVALID for the identity, so for an implementer, not much additional text is needed. For good measure, I also removed the signature_to_octets wrapper on serialize. The same would theoretically be possible for calculate_domain. Extensions to the signature scheme can always just restate the missing 3-4 lines of the signing procedure above.
Even greater improvements in readability and conciseness are achievable with other methods, especially ProofGen.

I believe the fastest implementation would have been possible having a draft with code structured roughly as follows:

1. serialization/deserialization operations for curve points, scalars etc. (opt. excluding the identity element)
2. message scalars (hashed and random) and generators
3. (optional) domain calculation
4. KeyGen, Sign, Verify, ProofGen, ProofVerify, with everything inlined as much as possible

Thanks for reading :)