Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement Schnorr-based signature of the block #365

Open
Geod24 opened this issue Sep 30, 2019 · 12 comments
Open

Implement Schnorr-based signature of the block #365

Geod24 opened this issue Sep 30, 2019 · 12 comments

Comments

@Geod24
Copy link
Member

@Geod24 Geod24 commented Sep 30, 2019

As a node operator, I need blocks that has been accepted by the consensus protocol to be signed in a compact way. In the best case scenario, the signature should use O(1) space & time.

The first step is to come up with a definition of the data structure used, as well as the signature collection window. For example, can a signature be added to the block after another block has been appended to the chain ?

Also, the Schnorr signature algorithm currently depends on:

  • R (random number)
  • S (public key)
  • Hash(R || S || message)

In this case, message could simply be the hash of the block. There is currently no evidence that S being part of the Hash is more secure, so it could be removed. However
this scheme, having R as part of the Hash, does not allow arbitrarily adding signatures.

Possibly depends on #304

Drey's edit:

20191105_154142
20191105_154134
20191105_161651

@AndrejMitrovic

This comment has been minimized.

Copy link
Member

@AndrejMitrovic AndrejMitrovic commented Nov 1, 2019

For example, can a signature be added to the block after another block has been appended to the chain ?

I don't think so, otherwise the chain is not immutable?

@AndrejMitrovic

This comment has been minimized.

Copy link
Member

@AndrejMitrovic AndrejMitrovic commented Nov 3, 2019

However this scheme, having R as part of the Hash, does not allow arbitrarily adding signatures.

What did you mean by this, "arbitrarily"?

@AndrejMitrovic

This comment has been minimized.

Copy link
Member

@AndrejMitrovic AndrejMitrovic commented Nov 4, 2019

Ok, so I'm thinking we could have something like this in the block:

Bitfield bitfield;
Signature sig;

The bitfield would be a compact representation specifying which validators signed, and which did not. If for example there are 6 validators in total, and the bits at index #0, #2, #4 are 1, it means validators #0, #2, #4 signed the block, and validators #1, #3, and #5 did not.

Then, it should be simple to verify a block. Prototyping:

Point sum_keys = 
    bitfield  // range over bits
        .map!(idx => this.validator_keys[idx])  // get the keys
        .reduce!((a, b) => a + b));  // sum them via schnorr

if (verify(sum_keys, block.signature, block.hash))
{
   // ...
}

Is there any drawback to this approach?

@Geod24

This comment has been minimized.

Copy link
Member Author

@Geod24 Geod24 commented Nov 4, 2019

What did you mean by this, "arbitrarily"?

They don't need another round of communication to exchange their R.

Is there any drawback to this approach?

I can't see any ATM.

@AndrejMitrovic

This comment has been minimized.

Copy link
Member

@AndrejMitrovic AndrejMitrovic commented Nov 8, 2019

For example, can a signature be added to the block after another block has been appended to the chain ?

Is this about validators which didn't sign in due time after the block was published? So it gives them time to "catch up" and sign the blocks they didn't sign while they were offline?

@Geod24

This comment has been minimized.

Copy link
Member Author

@Geod24 Geod24 commented Nov 8, 2019

Yes

@TrustHenry

This comment has been minimized.

Copy link
Member

@TrustHenry TrustHenry commented Nov 8, 2019

Is this about validators which didn't sign in due time after the block was published? So it gives them time to "catch up" and sign the blocks they didn't sign while they were offline?

Is it a block that is not connected to the chain yet or an undetermined block?

@Geod24

This comment has been minimized.

Copy link
Member Author

@Geod24 Geod24 commented Nov 8, 2019

It's about the HEAD of the chain (and potentially, X blocks under HEAD): If a validator goes offline for, let's say 3 blocks, and come back, can they "catch up" on validation (add their signatures) or do they have to start validating from the current HEAD and forget about the 3 blocks they missed ?

@TrustHenry

This comment has been minimized.

Copy link
Member

@TrustHenry TrustHenry commented Nov 8, 2019

If a validator goes offline for, let's say 3 blocks, and come back, can they "catch up" on validation

If they come back, they found the wrong block while proceeding with the "catch up" verification. Can they replace the block?

@Geod24

This comment has been minimized.

Copy link
Member Author

@Geod24 Geod24 commented Nov 8, 2019

It depends on what you mean by "wrong block"

@AndrejMitrovic

This comment has been minimized.

Copy link
Member

@AndrejMitrovic AndrejMitrovic commented Nov 8, 2019

I have a somewhat convoluted unittest example (which I'll clean up when I have the time), but I think I am maybe/almost on track:

unittest
{
    Hash msg_1 = "Block #1".hashFull();

    // secret
    Scalar n1_r1;
    Scalar n2_r1;

    // keys
    Pair kp1 = Pair.random();
    Pair kp2 = Pair.random();

    // random points
    Pair N1_R = Pair.random();
    Pair N2_R = Pair.random();

    // these are derived from the previous block sig or previous enrollment
    Point N1_R1;
    Point N2_R1;

    // node #1
    {
        Hash[] n1_preimages;
        n1_preimages ~= N1_R.v.hashFull();
        n1_preimages ~= N1_R.v.hashFull().hashFull();

        Scalar r0 = N1_R.v;
        Scalar n1X0 = Scalar(n1_preimages[$ - 1]);
        n1_r1 = r0 + n1X0;
        N1_R1 = N1_R.V + n1X0.toPoint();
    }

    // node #2
    {
        Hash[] n2_preimages;
        n2_preimages ~= N2_R.v.hashFull();
        n2_preimages ~= N2_R.v.hashFull().hashFull();

        Scalar r0 = N2_R.v;
        Scalar n2X0 = Scalar(n2_preimages[$ - 1]);
        n2_r1 = r0 + n2X0;
        N2_R1 = N2_R.V + n2X0.toPoint();
    }

    auto R = N1_R1 + N2_R1;

    // all validator public keys
    Point PubKeys = kp1.V + kp2.V;

    // both sign on R and their own r points
    Signature N1_SIG1 = sign(kp1.v, PubKeys, R, n1_r1, msg_1);
    Signature N2_SIG1 = sign(kp2.v, PubKeys, R, n2_r1, msg_1);

    // multisig for block #1
    Signature multisig_1 = Signature(R, N1_SIG1.s + N2_SIG1.s);

    assert(verify(PubKeys, multisig_1, msg_1));
}
@AndrejMitrovic

This comment has been minimized.

Copy link
Member

@AndrejMitrovic AndrejMitrovic commented Nov 14, 2019

For example, can a signature be added to the block after another block has been appended to the chain ?
However
this scheme, having R as part of the Hash, does not allow arbitrarily adding signatures.

I'm working on a scheme where signatures can be arbitrarily added at a later point. Also, R being part of the hash can be OK, as long as validator nodes publish their preimages. Essentially, a node operator may send out multiple preimages (say next 10 blocks), go offline, and later when it comes back online it signs those blocks.

It's a pretty neat scheme, and I'm working on a PoC right now. I'm about 95% there with a working prototype.

@bpalaggi bpalaggi moved this from To do to In progress (Max 4) in Sprint #8 (2019-10-29 to 2019-11-12) Nov 20, 2019
@bpalaggi bpalaggi moved this from In progress (Max 4) to Review/Testing (Max 2) in Sprint #8 (2019-10-29 to 2019-11-12) Nov 22, 2019
@bpalaggi bpalaggi moved this from Review/Testing (Max 2) to Blocked (Max 1) in Sprint #8 (2019-10-29 to 2019-11-12) Dec 3, 2019
@bpalaggi bpalaggi added this to To do in Sprint #9 (2020-01-07 to 2020-01-20) via automation Jan 7, 2020
@bpalaggi bpalaggi removed this from Blocked (Max 1) in Sprint #8 (2019-10-29 to 2019-11-12) Jan 7, 2020
@Geod24 Geod24 moved this from To do to Review/Testing (Max 2) in Sprint #9 (2020-01-07 to 2020-01-20) Jan 7, 2020
@bpalaggi bpalaggi moved this from Review/Testing (Max 2) to In progress (Max 5) in Sprint #9 (2020-01-07 to 2020-01-20) Jan 21, 2020
@bpalaggi bpalaggi added this to To do in Sprint #10 (2020-01-21 to 2020-02-10) via automation Jan 21, 2020
@bpalaggi bpalaggi removed this from In progress (Max 5) in Sprint #9 (2020-01-07 to 2020-01-20) Jan 21, 2020
@AndrejMitrovic AndrejMitrovic moved this from To do to In progress (Max 5) in Sprint #10 (2020-01-21 to 2020-02-10) Jan 22, 2020
@bpalaggi bpalaggi removed this from In progress (Max 5) in Sprint #10 (2020-01-21 to 2020-02-10) Feb 11, 2020
@bpalaggi bpalaggi added this to To do in Sprint #11 (2020-02-11 to 2020-02-24) via automation Feb 11, 2020
@bpalaggi bpalaggi moved this from To do to In progress (Max 5) in Sprint #11 (2020-02-11 to 2020-02-24) Feb 11, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants
You can’t perform that action at this time.