Author Topic: Threshold Schnorr signature to approve previous block by >80% of delegates  (Read 1918 times)

0 Members and 1 Guest are viewing this topic.

Offline pc

  • Hero Member
  • *****
  • Posts: 1530
    • View Profile
    • Bitcoin - Perspektive oder Risiko?
  • BitShares: cyrano
A simpler method to avoid bloat would be to introduce a special "ephemeral" transaction type that is broadcast through the network but normally not included in blocks.

Delegates could sign every 10th block or so using such an ephemeral transaction, and clients would see these signatures and could use them to check for a majority. Only in the case where a delegate later signs a block in a different fork could the ephemeral transaction be used to prove that delegate's misbehaviour. (Special handling might be necessary for forks arising from client bugs.)

The delegate's ephemeral transactions can be discarded as soon as he signs a regular block in the same fork.
Bitcoin - Perspektive oder Risiko? ISBN 978-3-8442-6568-2 http://bitcoin.quisquis.de

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
I admit this is not a fully fleshed out idea/proposal. But I wanted to see if I can get some feedback on it from devs.

A while ago on this GitHub thread, I said the following:
Quote
Finally, I was thinking about an idea to possibly reduce this 8 minute delay. Even though all the delegates should typically validate a given block N submitted at time T in less than 10 seconds after the block was submitted, the delegate signing block N + M has to wait until time T + M*(10 seconds) to provide the signature the adds their approval to all transactions in the blocks that came before it. This is what leads to the minimum 8 minute delay for getting more than 50% of delegates to approve of a transaction before the receiver can feel confident it does not exist on a minority fork. What if an active delegate was allowed to optionally submit a signature approving of a recent block before their designated time slot, sort of like they are allowed to optionally provide price feeds. They wouldn't be producing these blocks, the delegate producing the block could simply include their signatures into the block (only a maximum of 100 such signatures could ever be included per block since the block producer would only include at most one signature from each active delegate other than itself, which would be the signature by the delegate for the most recent block that delegate has signed that wasn't already included in a previous block in the chain). If all delegates submit a signature of the most recent block that they validated to the network (or at least to the private active delegate network), the user's clients could know a transaction is part of the majority-consensus chain only 10-30 seconds after the transaction was submitted.

The goal is to not have to wait for 17 minutes to get a "checkpoint" by most of the delegates but to ideally get these checkpoints every 10 seconds. Each of the delegates already knows whether the previous block is valid or not. But they cannot add their signature to it which shows their approval of the block until it is time to make their designated block which can be up to 16 minutes later! So why not allow the delegates to publicly contribute this information as soon as possible?

Well one objection raised by theoretical is that "we don't want to bloat every block with a bunch of extra delegate sigs." While, I don't think 100 extra sigs per block is that big of a deal in the larger scheme of things, it is a valid point.

So this is my new idea.

A (t, n) threshold signature scheme allows n participants to work together to generate a common shared random secret x (which acts as the private key to a public key Y that is known to all parties) in which none of the participants know the value of x but each of them have their own secret shares that allow them to create signatures using x, and specifically allows any t of the n participants to work together using their secret shares to generate a signature of any arbitrary message that can be verified to be signed by the private key x (without ever exposing x). Because of certain limitations on the value of t (t <= (n+1)/2) when this scheme is used with ECDSA, it is useful to implement this threshold signature scheme with Schnorr signatures instead if that choice is available.

So, I think the delegates should work together to generate a threshold digital signature for Schnorr signatures of the hash of the previous block and submit that in every block. This is just one extra signature added to every block. All of this communication happens out-of-band (not over the blockchain or even the main p2p network, but on the private delegate network). Since there are only 101 delegates and there is only one message (the previous block hash) to sign every 10 seconds, I imagine this adds barely any computational overhead. Because of the nature of threshold signatures not all of the delegates would need to cooperate for signature generation to be successful. I can imagine a 81-of-101 signature scheme working well. This can be comparable to how Ripple requires consensus by 80% of its rippled nodes in the UNL in order to close a ledger. And in the worse case scenario if a threshold could not be achieve by the time the block would need to be produced, it just means that the checkpoint is delayed a little bit.

I also want to be clear that each block still has a specific delegate that is responsible for generating it and signing off on it. Nothing changes there. There is clear responsibility for tardy or inactive delegates. It is just that the signature generated by participation of at least 80% of the active delegates can be added by the block producing delegate in order to give users instant (every 10 seconds) checkpoints instead of the current system of checkpoints every 17 minutes.

There is another benefit here as well. In the process of generating the threshold signature every block, the delegates end up computing a random number V (which needs to be included as part of the signature for signature verification) that incorporates the entropy of each of the participants. This random number can be used as a source of entropy for the blockchain that updates every 10 seconds. Currently, if you want a stream entropy that has the decentralization of nearly 101 delegates behind it, one must wait for a new random number every 16 minutes. Having this much faster stream of entropy improves the usability of certain blockchain applications, in particular games.

One other thing to mention about this proposal is that the public key Y representing the 101 delegates needs to be known to the public so that they can actually verify the signatures. In particular, they need to know that the public key claimed to be the one generated by the 101 delegates for this purpose really is that one. Every delegate that produces a block would only add their block to a chain claiming that the latest shared public key is Y if it actually was. This means that one needs to wait for a round (16 minutes) to finish before they know they can trust the claimed public key as of the end of the previous round. Every time delegates get removed from the top 101 ranks and new ones replace them, the new set of active delegates need to run through the key generation protocol again and generate a new public key Y. That Y is then committed to the block chain and once enough of the delegates confirm it by adding blocks on top of the block with that update to Y, the threshold signatures can switch to using signatures that are verified by that new Y. Since delegate turnover should be relatively slow, the delegates that weren't recently hired should still be more than 80% of the 101 active delegates and therefore still should be able to produce signatures correspond to the old Y until they are ready to switch over to signatures corresponding to the new Y. So threshold signatures can be submitted every 10 blocks with the same level as security even as the delegates in the top 101 ranks change.

I also have a proposal that we should implement Schnorr signatures more generally throughout the blockchain as an alternative to ECDSA, and in particular for the issuers/managers of UIAs which makes the integration of side chain DACs easier, but I will leave that one alone for now.