[Cryptography] Aggregate signatures

[Jae Kwon]

>
> I'm going to think about contracts in the future. Right now I'm working
> on a fee distribution protocol that, instead of mining, depends on the
> agreement of all potential fee receivers. Maybe a million peers was a
> bit much, but since the cryptocurrency in question removes incentives
> for pool mining, as well as proof of work, I anticipate even cellphone
> users will be able to 'mine' currency, so I'm aiming high. I've been
> having several problems with this protocol, one of which is bandwidth
> usage, hence my interest in aggregate signatures.


Interesting... How do you remove the incentive for proof-of-work without
solving the byzantine generals problem?

If the message being signed is the same, that's technically called a
"multisignature" scheme in literature, which is a type of "aggregate
signature" scheme.  For a noninteractive BLS multisignature scheme, both
signing, aggregation, and verification is fast, but for a noninteractive
BLS general-aggregate-signature scheme, verification requires N pairing
operations, where each pairing takes around 10+ms. [1]

I'm working on a non-proof-of-work consensus algorithm called Tendermint.
[2]

I've considered an aggregate signature scheme for Tendermint.  While it
would be useful for compressing signatures from validators (and so mobile
clients would benefit somewhat), I still need the individual signatures
from validators in order to punish bad validators when they go about
signing things that they shouldn't be signing.  So for now I've decided to
go with Ed25519 [3,4] which can easily batch verify 50,000 signatures in a
matter of seconds.  Mobile devices (where bandwidth is expensive) can check
for consensus probabilistically by requesting a small number of signatures
from a random selection of validators, with the help of merkle trees.
 Mobile devices shouldn't be "mining" on Tendermint, though.

[1] https://eprint.iacr.org/2002/118.pdf
[2] http://tendermint.com
[3] https://github.com/floodyberry/ed25519-donna
[4] https://github.com/tendermint/go-ed25519

p.s. on [1], take special heed of "*we require it to prove knowledge of
secret keys during the public key registration*".

Regards,
Jae
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140609/b1a3987c/attachment.html>