When Schnorr signatures are part of Bitcoin will it be possible validate each block with only one signature validation?A couple of questions on Schnorr sigWhat would UTXO consolidation look like in the public ledger with Schnorr signatures?Did the introduction of VerifyScript cause a backwards incompatible change to consensus?Are sipa's standardized schnorr signatures incompatible with blind signatures?

Why restrict private health insurance?

Virginia employer terminated employee and wants signing bonus returned

Finitely many repeated replacements

What is this diamond of every day?

NASA's RS-25 Engines

The meaning of ‘otherwise’

Gaining more land

Can the alpha, lambda values of a glmnet object output determine whether ridge or Lasso?

Source permutation

Is it possible to find 2014 distinct positive integers whose sum is divisible by each of them?

How does Ehrenfest's theorem apply to the quantum harmonic oscillator?

What is the generally accepted pronunciation of “topoi”?

Does a difference of tense count as a difference of meaning in a minimal pair?

Why do phishing e-mails use faked e-mail addresses instead of the real one?

Was it really inappropriate to write a pull request for the company I interviewed with?

For which categories of spectra is there an explicit description of the fibrant objects via lifting properties?

Street obstacles in New Zealand

Power Strip for Europe

How do we create new idioms and use them in a novel?

What are you allowed to do while using the Warlock's Eldritch Master feature?

Do I really need to have a scientific explanation for my premise?

PTIJ: Why does only a Shor Tam ask at the Seder, and not a Shor Mu'ad?

How to design an organic heat-shield?

What materials can be used to make a humanoid skin warm?



When Schnorr signatures are part of Bitcoin will it be possible validate each block with only one signature validation?


A couple of questions on Schnorr sigWhat would UTXO consolidation look like in the public ledger with Schnorr signatures?Did the introduction of VerifyScript cause a backwards incompatible change to consensus?Are sipa's standardized schnorr signatures incompatible with blind signatures?













2















In a recent talk Pieter Wuille talked about speed up verification when using Schnorr signatures and various algorithms for verifying multiple signatures.



Would it really be possible to verify one single block by aggregating the keys and signatures of all transactions? (In theory even more transactions over several blocks)



I assume this does imply that the old ECDSA scheme would not be used anymore. If we were backwards compatible we could probably only do this for transactions that used Schorr signatures where as the other ones would have to be verified one by one.



(Leaving aside politics of drastic protocol changes) Couldn't we even save more space if we adopt the block header to include one aggregate Schnorre signature for the block and leave out all the schnorr signatures of the single transactions within that block?



Did I miss anything? The talk did not give many details but just mentioned the idea.










share|improve this question


























    2















    In a recent talk Pieter Wuille talked about speed up verification when using Schnorr signatures and various algorithms for verifying multiple signatures.



    Would it really be possible to verify one single block by aggregating the keys and signatures of all transactions? (In theory even more transactions over several blocks)



    I assume this does imply that the old ECDSA scheme would not be used anymore. If we were backwards compatible we could probably only do this for transactions that used Schorr signatures where as the other ones would have to be verified one by one.



    (Leaving aside politics of drastic protocol changes) Couldn't we even save more space if we adopt the block header to include one aggregate Schnorre signature for the block and leave out all the schnorr signatures of the single transactions within that block?



    Did I miss anything? The talk did not give many details but just mentioned the idea.










    share|improve this question
























      2












      2








      2








      In a recent talk Pieter Wuille talked about speed up verification when using Schnorr signatures and various algorithms for verifying multiple signatures.



      Would it really be possible to verify one single block by aggregating the keys and signatures of all transactions? (In theory even more transactions over several blocks)



      I assume this does imply that the old ECDSA scheme would not be used anymore. If we were backwards compatible we could probably only do this for transactions that used Schorr signatures where as the other ones would have to be verified one by one.



      (Leaving aside politics of drastic protocol changes) Couldn't we even save more space if we adopt the block header to include one aggregate Schnorre signature for the block and leave out all the schnorr signatures of the single transactions within that block?



      Did I miss anything? The talk did not give many details but just mentioned the idea.










      share|improve this question














      In a recent talk Pieter Wuille talked about speed up verification when using Schnorr signatures and various algorithms for verifying multiple signatures.



      Would it really be possible to verify one single block by aggregating the keys and signatures of all transactions? (In theory even more transactions over several blocks)



      I assume this does imply that the old ECDSA scheme would not be used anymore. If we were backwards compatible we could probably only do this for transactions that used Schorr signatures where as the other ones would have to be verified one by one.



      (Leaving aside politics of drastic protocol changes) Couldn't we even save more space if we adopt the block header to include one aggregate Schnorre signature for the block and leave out all the schnorr signatures of the single transactions within that block?



      Did I miss anything? The talk did not give many details but just mentioned the idea.







      validation block-validity schnorr-signatures






      share|improve this question













      share|improve this question











      share|improve this question




      share|improve this question










      asked 3 hours ago









      Rene PickhardtRene Pickhardt

      1,997115




      1,997115




















          1 Answer
          1






          active

          oldest

          votes


















          2














          Yes, one validation per block, but not one signature per block.



          To clear up confusion, there are 3 distinct technologies involved here:



          • (1) non-interactive aggregation is the ability for a third party (who does not hold any private keys) to combine multiple signatures, each with their own message and public key, into a single signature that can be verified by someone knows all messages and public keys.

          • (2) interactive aggregation is the same, but when the signers need to be aware of the aggregation, and communicate with each other to jointly produce a single signature.

          • (3) batch validation is the ability for a verifier to verify whether multiple (pubkey,message,signature) tuples are all valid or not, faster than verifying the individual signatures. If one or more of the tuples are invalid the verifier will not learn which ones, in this case.

          Schnorr signatures (and any other known discrete logarithm based signature schemes) support (2) and (3), but not (1).



          The lack of (1) means there cannot be a single signature for an entire block (*), as the miner who constructs the block is a third party who isn't participating in signature creation.



          Due to (2), the best we can hope for (as long as we're restricted to DL-based signatures), is one signature per transaction. Even that requires cross-input aggregation, which has complexities beyond just the implementation of on-chain Schnorr signatures (see this post for example).



          However, because of (3) it is correct that there can be a single validation per block, however not a single signature per block. The speedup that is possible through batch validation does become nontrivial, in fact. Each of the 4 lines is an optimization technique that is currently implemented in libsecp256k1, which will pick the best one based on the size of the problem and the memory constraints.



          Batch validation speedup



          (*) There exists a form of non-interactive "half aggregation" for DL based signatures, where N signatures can be non-interactively combined into a single signature of size (1+N)/2 original signatures. This could be used for blocks, though the gains aren't that great, and there are complexities around block-wide aggregation that make it less interesting.






          share|improve this answer

























          • I guess I have to read up the details again but wasn't the idea of the plain public key model and the construction of musig exactly that non interactive aggregation would become possible? Or should I have asked for musig signatures? I thought musig is just the exact scheme that is currently aimed to be used when people talk about schnorr. Do not mark as correct yet as I still have open questions (which are probably my fault)

            – Rene Pickhardt
            1 hour ago











          • MuSig allows non-interactive setup - signing is still interactive.

            – Pieter Wuille
            1 hour ago











          • And MuSig is just one of the things wallet can choose to use when Schnorr validation on chain exist (because the signatures that come out of MuSig signing are compatible with a Schnorr verifier). There are (interactive setup) constructions that let you build k-of-n with a single key for example, or even arbitrary and/or-combinations of participants.

            – Pieter Wuille
            1 hour ago











          Your Answer








          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "308"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader:
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          ,
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













          draft saved

          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fbitcoin.stackexchange.com%2fquestions%2f85213%2fwhen-schnorr-signatures-are-part-of-bitcoin-will-it-be-possible-validate-each-bl%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown

























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          2














          Yes, one validation per block, but not one signature per block.



          To clear up confusion, there are 3 distinct technologies involved here:



          • (1) non-interactive aggregation is the ability for a third party (who does not hold any private keys) to combine multiple signatures, each with their own message and public key, into a single signature that can be verified by someone knows all messages and public keys.

          • (2) interactive aggregation is the same, but when the signers need to be aware of the aggregation, and communicate with each other to jointly produce a single signature.

          • (3) batch validation is the ability for a verifier to verify whether multiple (pubkey,message,signature) tuples are all valid or not, faster than verifying the individual signatures. If one or more of the tuples are invalid the verifier will not learn which ones, in this case.

          Schnorr signatures (and any other known discrete logarithm based signature schemes) support (2) and (3), but not (1).



          The lack of (1) means there cannot be a single signature for an entire block (*), as the miner who constructs the block is a third party who isn't participating in signature creation.



          Due to (2), the best we can hope for (as long as we're restricted to DL-based signatures), is one signature per transaction. Even that requires cross-input aggregation, which has complexities beyond just the implementation of on-chain Schnorr signatures (see this post for example).



          However, because of (3) it is correct that there can be a single validation per block, however not a single signature per block. The speedup that is possible through batch validation does become nontrivial, in fact. Each of the 4 lines is an optimization technique that is currently implemented in libsecp256k1, which will pick the best one based on the size of the problem and the memory constraints.



          Batch validation speedup



          (*) There exists a form of non-interactive "half aggregation" for DL based signatures, where N signatures can be non-interactively combined into a single signature of size (1+N)/2 original signatures. This could be used for blocks, though the gains aren't that great, and there are complexities around block-wide aggregation that make it less interesting.






          share|improve this answer

























          • I guess I have to read up the details again but wasn't the idea of the plain public key model and the construction of musig exactly that non interactive aggregation would become possible? Or should I have asked for musig signatures? I thought musig is just the exact scheme that is currently aimed to be used when people talk about schnorr. Do not mark as correct yet as I still have open questions (which are probably my fault)

            – Rene Pickhardt
            1 hour ago











          • MuSig allows non-interactive setup - signing is still interactive.

            – Pieter Wuille
            1 hour ago











          • And MuSig is just one of the things wallet can choose to use when Schnorr validation on chain exist (because the signatures that come out of MuSig signing are compatible with a Schnorr verifier). There are (interactive setup) constructions that let you build k-of-n with a single key for example, or even arbitrary and/or-combinations of participants.

            – Pieter Wuille
            1 hour ago
















          2














          Yes, one validation per block, but not one signature per block.



          To clear up confusion, there are 3 distinct technologies involved here:



          • (1) non-interactive aggregation is the ability for a third party (who does not hold any private keys) to combine multiple signatures, each with their own message and public key, into a single signature that can be verified by someone knows all messages and public keys.

          • (2) interactive aggregation is the same, but when the signers need to be aware of the aggregation, and communicate with each other to jointly produce a single signature.

          • (3) batch validation is the ability for a verifier to verify whether multiple (pubkey,message,signature) tuples are all valid or not, faster than verifying the individual signatures. If one or more of the tuples are invalid the verifier will not learn which ones, in this case.

          Schnorr signatures (and any other known discrete logarithm based signature schemes) support (2) and (3), but not (1).



          The lack of (1) means there cannot be a single signature for an entire block (*), as the miner who constructs the block is a third party who isn't participating in signature creation.



          Due to (2), the best we can hope for (as long as we're restricted to DL-based signatures), is one signature per transaction. Even that requires cross-input aggregation, which has complexities beyond just the implementation of on-chain Schnorr signatures (see this post for example).



          However, because of (3) it is correct that there can be a single validation per block, however not a single signature per block. The speedup that is possible through batch validation does become nontrivial, in fact. Each of the 4 lines is an optimization technique that is currently implemented in libsecp256k1, which will pick the best one based on the size of the problem and the memory constraints.



          Batch validation speedup



          (*) There exists a form of non-interactive "half aggregation" for DL based signatures, where N signatures can be non-interactively combined into a single signature of size (1+N)/2 original signatures. This could be used for blocks, though the gains aren't that great, and there are complexities around block-wide aggregation that make it less interesting.






          share|improve this answer

























          • I guess I have to read up the details again but wasn't the idea of the plain public key model and the construction of musig exactly that non interactive aggregation would become possible? Or should I have asked for musig signatures? I thought musig is just the exact scheme that is currently aimed to be used when people talk about schnorr. Do not mark as correct yet as I still have open questions (which are probably my fault)

            – Rene Pickhardt
            1 hour ago











          • MuSig allows non-interactive setup - signing is still interactive.

            – Pieter Wuille
            1 hour ago











          • And MuSig is just one of the things wallet can choose to use when Schnorr validation on chain exist (because the signatures that come out of MuSig signing are compatible with a Schnorr verifier). There are (interactive setup) constructions that let you build k-of-n with a single key for example, or even arbitrary and/or-combinations of participants.

            – Pieter Wuille
            1 hour ago














          2












          2








          2







          Yes, one validation per block, but not one signature per block.



          To clear up confusion, there are 3 distinct technologies involved here:



          • (1) non-interactive aggregation is the ability for a third party (who does not hold any private keys) to combine multiple signatures, each with their own message and public key, into a single signature that can be verified by someone knows all messages and public keys.

          • (2) interactive aggregation is the same, but when the signers need to be aware of the aggregation, and communicate with each other to jointly produce a single signature.

          • (3) batch validation is the ability for a verifier to verify whether multiple (pubkey,message,signature) tuples are all valid or not, faster than verifying the individual signatures. If one or more of the tuples are invalid the verifier will not learn which ones, in this case.

          Schnorr signatures (and any other known discrete logarithm based signature schemes) support (2) and (3), but not (1).



          The lack of (1) means there cannot be a single signature for an entire block (*), as the miner who constructs the block is a third party who isn't participating in signature creation.



          Due to (2), the best we can hope for (as long as we're restricted to DL-based signatures), is one signature per transaction. Even that requires cross-input aggregation, which has complexities beyond just the implementation of on-chain Schnorr signatures (see this post for example).



          However, because of (3) it is correct that there can be a single validation per block, however not a single signature per block. The speedup that is possible through batch validation does become nontrivial, in fact. Each of the 4 lines is an optimization technique that is currently implemented in libsecp256k1, which will pick the best one based on the size of the problem and the memory constraints.



          Batch validation speedup



          (*) There exists a form of non-interactive "half aggregation" for DL based signatures, where N signatures can be non-interactively combined into a single signature of size (1+N)/2 original signatures. This could be used for blocks, though the gains aren't that great, and there are complexities around block-wide aggregation that make it less interesting.






          share|improve this answer















          Yes, one validation per block, but not one signature per block.



          To clear up confusion, there are 3 distinct technologies involved here:



          • (1) non-interactive aggregation is the ability for a third party (who does not hold any private keys) to combine multiple signatures, each with their own message and public key, into a single signature that can be verified by someone knows all messages and public keys.

          • (2) interactive aggregation is the same, but when the signers need to be aware of the aggregation, and communicate with each other to jointly produce a single signature.

          • (3) batch validation is the ability for a verifier to verify whether multiple (pubkey,message,signature) tuples are all valid or not, faster than verifying the individual signatures. If one or more of the tuples are invalid the verifier will not learn which ones, in this case.

          Schnorr signatures (and any other known discrete logarithm based signature schemes) support (2) and (3), but not (1).



          The lack of (1) means there cannot be a single signature for an entire block (*), as the miner who constructs the block is a third party who isn't participating in signature creation.



          Due to (2), the best we can hope for (as long as we're restricted to DL-based signatures), is one signature per transaction. Even that requires cross-input aggregation, which has complexities beyond just the implementation of on-chain Schnorr signatures (see this post for example).



          However, because of (3) it is correct that there can be a single validation per block, however not a single signature per block. The speedup that is possible through batch validation does become nontrivial, in fact. Each of the 4 lines is an optimization technique that is currently implemented in libsecp256k1, which will pick the best one based on the size of the problem and the memory constraints.



          Batch validation speedup



          (*) There exists a form of non-interactive "half aggregation" for DL based signatures, where N signatures can be non-interactively combined into a single signature of size (1+N)/2 original signatures. This could be used for blocks, though the gains aren't that great, and there are complexities around block-wide aggregation that make it less interesting.







          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited 1 hour ago

























          answered 2 hours ago









          Pieter WuillePieter Wuille

          47.2k399158




          47.2k399158












          • I guess I have to read up the details again but wasn't the idea of the plain public key model and the construction of musig exactly that non interactive aggregation would become possible? Or should I have asked for musig signatures? I thought musig is just the exact scheme that is currently aimed to be used when people talk about schnorr. Do not mark as correct yet as I still have open questions (which are probably my fault)

            – Rene Pickhardt
            1 hour ago











          • MuSig allows non-interactive setup - signing is still interactive.

            – Pieter Wuille
            1 hour ago











          • And MuSig is just one of the things wallet can choose to use when Schnorr validation on chain exist (because the signatures that come out of MuSig signing are compatible with a Schnorr verifier). There are (interactive setup) constructions that let you build k-of-n with a single key for example, or even arbitrary and/or-combinations of participants.

            – Pieter Wuille
            1 hour ago


















          • I guess I have to read up the details again but wasn't the idea of the plain public key model and the construction of musig exactly that non interactive aggregation would become possible? Or should I have asked for musig signatures? I thought musig is just the exact scheme that is currently aimed to be used when people talk about schnorr. Do not mark as correct yet as I still have open questions (which are probably my fault)

            – Rene Pickhardt
            1 hour ago











          • MuSig allows non-interactive setup - signing is still interactive.

            – Pieter Wuille
            1 hour ago











          • And MuSig is just one of the things wallet can choose to use when Schnorr validation on chain exist (because the signatures that come out of MuSig signing are compatible with a Schnorr verifier). There are (interactive setup) constructions that let you build k-of-n with a single key for example, or even arbitrary and/or-combinations of participants.

            – Pieter Wuille
            1 hour ago

















          I guess I have to read up the details again but wasn't the idea of the plain public key model and the construction of musig exactly that non interactive aggregation would become possible? Or should I have asked for musig signatures? I thought musig is just the exact scheme that is currently aimed to be used when people talk about schnorr. Do not mark as correct yet as I still have open questions (which are probably my fault)

          – Rene Pickhardt
          1 hour ago





          I guess I have to read up the details again but wasn't the idea of the plain public key model and the construction of musig exactly that non interactive aggregation would become possible? Or should I have asked for musig signatures? I thought musig is just the exact scheme that is currently aimed to be used when people talk about schnorr. Do not mark as correct yet as I still have open questions (which are probably my fault)

          – Rene Pickhardt
          1 hour ago













          MuSig allows non-interactive setup - signing is still interactive.

          – Pieter Wuille
          1 hour ago





          MuSig allows non-interactive setup - signing is still interactive.

          – Pieter Wuille
          1 hour ago













          And MuSig is just one of the things wallet can choose to use when Schnorr validation on chain exist (because the signatures that come out of MuSig signing are compatible with a Schnorr verifier). There are (interactive setup) constructions that let you build k-of-n with a single key for example, or even arbitrary and/or-combinations of participants.

          – Pieter Wuille
          1 hour ago






          And MuSig is just one of the things wallet can choose to use when Schnorr validation on chain exist (because the signatures that come out of MuSig signing are compatible with a Schnorr verifier). There are (interactive setup) constructions that let you build k-of-n with a single key for example, or even arbitrary and/or-combinations of participants.

          – Pieter Wuille
          1 hour ago


















          draft saved

          draft discarded
















































          Thanks for contributing an answer to Bitcoin Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid


          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.

          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fbitcoin.stackexchange.com%2fquestions%2f85213%2fwhen-schnorr-signatures-are-part-of-bitcoin-will-it-be-possible-validate-each-bl%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          -block-validity, schnorr-signatures, validation

          Popular posts from this blog

          Frič See also Navigation menuinternal link

          Identify plant with long narrow paired leaves and reddish stems Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?What is this plant with long sharp leaves? Is it a weed?What is this 3ft high, stalky plant, with mid sized narrow leaves?What is this young shrub with opposite ovate, crenate leaves and reddish stems?What is this plant with large broad serrated leaves?Identify this upright branching weed with long leaves and reddish stemsPlease help me identify this bulbous plant with long, broad leaves and white flowersWhat is this small annual with narrow gray/green leaves and rust colored daisy-type flowers?What is this chilli plant?Does anyone know what type of chilli plant this is?Help identify this plant

          fontconfig warning: “/etc/fonts/fonts.conf”, line 100: unknown “element blank” The 2019 Stack Overflow Developer Survey Results Are In“tar: unrecognized option --warning” during 'apt-get install'How to fix Fontconfig errorHow do I figure out which font file is chosen for a system generic font alias?Why are some apt-get-installed fonts being ignored by fc-list, xfontsel, etc?Reload settings in /etc/fonts/conf.dTaking 30 seconds longer to boot after upgrade from jessie to stretchHow to match multiple font names with a single <match> element?Adding a custom font to fontconfigRemoving fonts from fontconfig <match> resultsBroken fonts after upgrading Firefox ESR to latest Firefox