search

w3f / schnorrkel

Schnorr VRFs and signatures on the Ristretto group
BSD 3-Clause "New" or "Revised" License
315 stars 94 forks source link

Explore two-round mBCJ multi-signature scheme #15

Closed burdges closed 4 years ago

burdges commented 5 years ago

We should explore the two round mBCJ signature scheme from pages 21 and 21 of https://eprint.iacr.org/2018/417.pdf using session type in the vein of the musig implementation in multi.rs

It requires a different verification from a schnorr signature, and comes with proofs-of-possession and a strange hierarchical relationship among the signers, but it does a two-round trip multi-signature without pairings.

burdges commented 5 years ago

I looked into mBCJ further. As written, it requires an aggregator check the proof-of-possession, but a malicious aggregator could simply ignore this, maybe permitting rogue public key attacks. I have not checked their security proof but it likely sweeps this under the rug with the key model. At some point @hndnklnc and I should look into a delinearized variant of mBCJ.

burdges commented 5 years ago

I have not found time to look into this more seriously, but mBCJ still looks like our most promising approach. Right now, there is no obvious uses for proof-of-possession in a signature scheme without true 1-RTT aggregation ala BLS, which makes mBCJ itself useless. Yet, several research questions remain:

  1. Explore what a delinearized variant of mBCJ looks like. In this, how close can mBCJ keys be made to Schnorr keys?
  2. Can a 2-RTT proof-of-possession scheme like mBCJ be integrated with GRANDPA? Imagine sending the first messages in the previous GRANDPA round or even using BLS only for prevotes but sending a first message for an mBCJ-like precommit in the prevote.
burdges commented 4 years ago

We concluded mBCJ looks too messy for this, and we're close to a real answer, so closing.