Re: [bitcoin-dev] Trustless Address Server – Outsourcing handing out addresses to prevent address reuse

2022-10-18 Thread Andrew Poelstra via bitcoin-dev
On Mon, Oct 17, 2022 at 07:07:07PM -0500, Bryan Bishop via bitcoin-dev wrote:
> 
> Isn't this the same problem but now for copy-pasting pubkeys instead of an
> address?
>

No, as I understand the proposal, the "public key" held by the wallet is simply
a signing key used to authenticate addresses, and never leaves the wallet. Yes,
if the wallet's own memory is compromised, it can be tricked into accepting bad
addresses, but this is much much harder than compromising data on the clipboard,
which basically any application can do without any "real" exploits or special
permissions.

As an extreme, this proposal could be run on a hardware wallet which had some
out-of-band way to obtain and authenticate public keys (similar to Signal QR
codes).

-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Wallet policies for descriptor wallets

2022-09-29 Thread Andrew Poelstra via bitcoin-dev

I'm really happy to see this discussion. I don't have any comments on the spec
because I think I'd have to be more in-the-weeds trying to implement a hww to
understand how well it works for realistic use cases. But a strong concept-ACk
from me and thanks to Salvatore for exploring this!

On Mon, May 09, 2022 at 11:36:47AM +, darosior via bitcoin-dev wrote:
> 
> Unrelated question, since you mentioned `musig2` descriptors in this context. 
> I thought Musig2 wasn't really
> feasible for hardware signing devices, especially stateless ones. Do you 
> think/know whether it is actually
> possible for a HW to take part in a Musig2?
>

As Salvatore mentioned in his reply, there are a couple ways that hwws can deal
with musig2 -- specifically, having state (and I believe you can get away with
as little state as a single monotonic counter) or having a RNG which is reliable
enough that it at least won't repeat values.

Because these aren't blockers for all hwws, even if they are blockers for some,
I'd really like to see musig2 support in these protocols, or at least for musig2
to be considered in their design.
 

-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Why OpenTimestamps does not "linearize" its transactions

2022-06-14 Thread Andrew Poelstra via bitcoin-dev
On Tue, Jun 14, 2022 at 01:15:08PM -0400, Undiscussed Horrific Abuse, One 
Victim of Many via bitcoin-dev wrote:
> I'm replying to Peter, skipping the other emails.
> 
> I perceive all these emails as disruptive trolling, ignoring the
> importance of real timestamping, while handwaving about things that
> are roughly false and harmful.
> 
> Since the start of cryptocurrency, Bitcoin has been used to write
> timestamps that stay intact despite malicious action to arbitrary
> systems and records, showing the earliest on-chain publication of
> data. It seems misleading that OTS does not do that, when it is such a
> prominent system.
>

Please be cautious with tone and when assuming bad faith. I don't believe
that Peter is trolling. Also, as politely as I can, when something like
OTS whose model is dead-simple, well-documented, and has been running for
years providing significant value to many people, comes under attack for
being underspecified or failing to do what it says ... this is a
surprising claim, to say the least.


After talking to a few people offline, all of whom are baffled at this
entire conversation, I think the issue might come down to the way that
people interpret "timestamping".

If you believe that "timestamping" means providing a verifiable ordering
to events, then of course OTS does not accomplish this, nor has it ever
claimed to. If you think that "timestamping" means proving that some
data existed at a particular time, then this is exactly what OTS does.

Personally -- and I suspect this is true of Peter as well -- I have always
read the word as having the latter meaning, and it never occurred to me
until now that others might have a different interpretation.


I apologize for contributing to a thread that is getting a bit out of hand,
but I hope this can help the different parties see where the confusion is.




-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Is there a tool like Ethereum EVM at present for Bitcoin script?

2021-08-24 Thread Andrew Poelstra via bitcoin-dev

Simplicity does not compile to Bitcoin Script, and Sapio assumes extensions
to Bitcoin Script that are not currently part of the consensus code.


On Tue, Aug 24, 2021 at 03:36:29PM +0800, Gijs van Dam via bitcoin-dev wrote:
> Hi,
> 
> 
> Bitcoin does not have a virtual machine. But you do have [Miniscript][1],
> [Min.sc][2], [Simplicity][3] and [Sapio][4]. These are all higher level
> languages that compile to Bitcoin Script. Sapio is "just" Rust, so that
> might fit your setting best.
> 
> By the way, this question also has an answer on [Bitcoin Stackexchange][5]
> which is a great resource for questions like this.
> 
> [1]: http://bitcoin.sipa.be/miniscript/
> [2]: https://min.sc/
> [3]: https://github.com/ElementsProject/simplicity
> [4]: https://learn.sapio-lang.org/
> [5]:
> https://bitcoin.stackexchange.com/questions/108261/is-there-a-tool-like-ethereum-evm-at-present-for-bitcoin-script
> 
> On Tue, Aug 24, 2021 at 2:55 PM Null Null via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> > Hi all,
> >
> > Is there a tool like Ethereum EVM at present? Users can write bitcoin
> > scripts in a syntax just like python(or like other programming language);
> > through this tool, they can be translated into bitcoin original scripts; it
> > sounds like a new programming language has been invented.
> >
> > In my opinion, Bitcoin script programming is based on reverse Polish
> > expression; this is not friendly to programmers;
> >
> > In fact, Bitcoin's opcode expression ability is very rich, and it may be
> > unfriendly, which has affected the promotion of Bitcoin in the technical
> > community.
> >
> > Hope for hearing some voice about this.
> >
> > Best wish.
> >
> > ___
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >

> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] BIP - limiting OP_RETURN / HF

2021-04-16 Thread Andrew Poelstra via bitcoin-dev
On Fri, Apr 16, 2021 at 03:34:33PM +, Christopher Gilliard via bitcoin-dev 
wrote:
> This sounds like a good justification to remove the legacy multi-signature
> capabilities as well.
>

Doing so would confiscate coins, and also it is impossible to remove
legacy multisignatures in general without gutting almost all of Script.
 
> >> Thus, given that it is otherwise impossible to stop people from putting
> arbitrary data values into their transactions, then we rather encourage
> people who are going to encode their arbitrary data in transaction to use
> the OP_RETURN outputs in order to avoid UTXO bloat.
> 
> You can't make it completely impossible to do that, but you can make it
> harder and at the same time you can provide a solution for doing what they
> want to do.
>

I don't think you can even make it harder in a meaningful sense. There is
too much flexibility in transaction data.
 
-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Update on "Speedy" Trial: The circus rolls on

2021-04-08 Thread Andrew Poelstra via bitcoin-dev
On Thu, Apr 08, 2021 at 12:40:42PM +0100, Michael Folkson via bitcoin-dev wrote:
> 
> All of this makes me extremely uncomfortable and I dread to think what
> individuals and businesses all over the world who have plans to
> utilize and build on Taproot are making of all of this. As an
> individual I would like to distance myself from this circus. I will
> try to keep the mailing list informed though of further developments
> re Speedy Trial in Core or progress on an alternative client.
>

Thank you for your updates.


For what it's worth, as somebody who wants to use Taproot I don't care *at
all* about activation parameters, and I especially don't care about block
height vs MTP.

If a coin toss is what it takes for people to move past this that's fine
by me.


 
-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Provisions (was: PSA: Taproot loss of quantum protections)

2021-03-16 Thread Andrew Poelstra via bitcoin-dev
On Tue, Mar 16, 2021 at 03:10:21PM +0100, Andrea via bitcoin-dev wrote:
> 
> Hi! Sorry for the OT, could you provide some references to ring signatures
> over/for/via taproot (I mean the schema or something like that)? And what is
> "Provisions" (the capital letter makes me think it's a product/technology)?
> I'm a rookie following this mailing since just a few months...
>

Thanks for posting such a positive message in an otherwise tense thread :)

Provisions is a scheme for providing proof of ownership of funds, developed
by Dagher et al in 2015 at https://eprint.iacr.org/2015/1008 . The way it
works is to collect all of the Bitcoin outputs which have exposed/known
public keys then associate to these keys a Pedersen commitment which commits
to the outputs' amounts in a homomorphic way.

Homomorphic means that even though the commitments hide what the original
amounts are, anyone can add them together (in some sense) to get a new
commitment to the sum of the original amounts.

So Provisions is essentially a zero-knowledge proof of the following statement

1. I have a commitment to >100BTC (or whatever)...
2. ...which is a sum of commitments of actual UTXO values...
3. ...where these UTXOs come from the set of known-public-key UTXOs...
4. ...and I am able to sign with the public keys associated to them.

which proves ownership of some amount of BTC, without revealing which specific
UTXOs were involved. This zero-knowledge proof can be done fairly efficiently
by exploiting the structure of EC public keys and Pedersen commitments.


Unfortunately, most unspent Bitcoin outputs do not have known public keys,
which means that you can only do a Provisions proof using a small anonymity
set. However, all Taproot outputs, by virtue of having exposed public keys
(which is the point under contention in this thread), will be in the set of
exposed-public-key UTXOs, allowing people to do Provisions proofs where
their anonymity set consists of a large proportion of active coins.


BTW, even without Provisions, there are some similar and simpler things you
can do with Taproot keys along these lines. See for example
https://twitter.com/n1ckler/status/1334240709814136833



-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

2021-03-16 Thread Andrew Poelstra via bitcoin-dev
On Tue, Mar 16, 2021 at 03:44:25AM +, Luke Dashjr wrote:
> (To reiterate: I do not intend any of this as a NACK of Taproot.)
>

Thanks, although it's still somewhat frustrating to be rehashing this
discussion again after so many years.
 
> On Monday 15 March 2021 23:12:18 Andrew Poelstra wrote:
> > "No gain" except to save significant CPU time and bandwidth?
> 
> The CPU time is localised to involved nodes, and (correct me if I'm wrong) 
> trivial in comparison to what is required to run a full node in the first 
> place. I'm not sure how it looks with bandwidth.
>

I really can't parse what "localized to involved nodes" means. All Bitcoin
nodes will be affected. Right now for nodes with sufficient bandwidth, signature
validation is the slowest part of validating transactions, which is why it
is disabled for the bulk of the chain during IBD. Taproot, by virtue of
enabling batch verification, would give a 2-3x speedup when validating the
same number of signatures.
 
> > Having exposed keys also lets you do ring signatures over outputs, creating
> > the ability to do private proof of funds via Provisions.
> 
> But you can also do comparable proofs behind a hash with Bulletproofs, right?
>

Yes, if you are willing to accept independent >10x slowdowns on proving,
verification and code review.
 
> > > Despite this, I still don't think it's a reason to NACK Taproot: it
> > > should be fairly trivial to add a hash on top in an additional softfork
> > > and fix this.
> >
> > This would make Bitcoin strictly worse.
> 
> How so? People could just not use it if they don't care, right?
> The alternative (if people care enough) is that those concerned about quantum 
> risk would be forced to forego the benefits of Taproot and stick to p2pkh or 
> such, which seems like an artificial punishment.
>

People who do use it will reduce their privacy set, reduce the privacy set of
people who aren't using it, create confusion and delays for people implementing
Taproot, and slow down Bitcoin nodes who would have to validate the extra
material.
 
> > > In addition to the points made by Mark, I also want to add two more, in
> > > response to Pieter's "you can't claim much security if 37% of the supply
> > > is at risk" argument. This argument is based in part on the fact that
> > > many people reuse Bitcoin invoice addresses.
> >
> > 37% is a dramatic understatement. Every address which is derived using
> > BIP32 should be assumed compromised to a QC attacker because xpubs are not
> > treated like secret key material and are trivial to e.g. extract from
> > hardware wallets or PSBTs. I expect the real number is close to 100%.
> 
> xpubs should be treated like secret key material IMO.
> 

Your opinion is noted. This is not how xpubs are, in reality, treated. And
it would make them significantly less useful if you could no longer share
descriptors with people you would like to do multiparty transactions with.

> A quantum attacker would need to compromise your PC to attack a hardware 
> wallet, right?
> 

No, I expect you could get xpubs out of hardware wallets using any of the
web endpoints provided by hardware wallet vendors, or by asking it to update
a PSBT with any of its scriptpubkeys.

> > In any case, Taproot keys, when used according to the recommendation in
> > BIP-0341, are already hashes of their internal keys, so (a) Taproot outputs
> > actually have better quantum resistance than legacy outputs; and (b) adding
> > another hash would be strictly redundant.
> 
> It not only stops the attacker from obtaining the original key, but also 
> prevents creating a new private key that can spend the output?
> 

I don't know what you mean by this. If the original key is usable, i.e. a QC
has appeared overnight, then Bitcoin is screwed. (For that matter, the same is
true if there is an overnight break in SHA2, or ECDSA, or any other major
component of Bitcoin. Fortunately this is not how cryptographic breaks have
historically appeared.) There is no new private key that could be created.

If there is a QC where we have some warning, then we need to disable all EC
operations in Script, including keypath spends of Taproot outputs, and this
would be true with or without the redundant extra hash.

Taproot, with or without the redundant hash, has a few distinct benefits over
legacy outputs in this scenario:

  * Taproot keys are hashes of semi-secret data (at least as secret as xpubs)
in a well-defined and simple way, by virtue of committing to an internal
key and some script (usually unspendable)
  * By adding secret data to the script, users can provide extra data to prove
in a QC-hard way, even if their internal key is compromised
  * Taproot keys can be chosen to be provably unspendable except by a DL break,
as David Harding points out, by using a NUMS point as an internal key.

None of these factors are improved by adding an extra hash.

-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra 

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

2021-03-15 Thread Andrew Poelstra via bitcoin-dev
On Mon, Mar 15, 2021 at 09:48:15PM +, Luke Dashjr via bitcoin-dev wrote:
> Also, what I didn't know myself until today, is that we do not actually gain 
> anything from this: the features proposed to make use of the raw keys being 
> public prior to spending can be implemented with hashed keys as well.
> It would use significantly more CPU time and bandwidth (between private 
> parties, not on-chain), but there should be no shortage of that for anyone 
> running a full node (indeed, CPU time is freed up by Taproot!); at worst, it 
> would create an incentive for more people to use their own full node, which 
> is a good thing!
> 

"No gain" except to save significant CPU time and bandwidth? As Matt points
out there is also a storage hit (unless you want to _really_ waste CPU time
by using pubkey recovery, eliminating any hope of batch validation while
introducing a new dependency on an algorithm with a very unclear patent
story).

Having exposed keys also lets you do ring signatures over outputs, creating the
ability to do private proof of funds via Provisions.

> Despite this, I still don't think it's a reason to NACK Taproot: it should be 
> fairly trivial to add a hash on top in an additional softfork and fix this.
> 

This would make Bitcoin strictly worse.

> In addition to the points made by Mark, I also want to add two more, in 
> response to Pieter's "you can't claim much security if 37% of the supply is 
> at risk" argument. This argument is based in part on the fact that many 
> people reuse Bitcoin invoice addresses.
> 

37% is a dramatic understatement. Every address which is derived using BIP32
should be assumed compromised to a QC attacker because xpubs are not treated
like secret key material and are trivial to e.g. extract from hardware wallets
or PSBTs. I expect the real number is close to 100%.


In any case, Taproot keys, when used according to the recommendation in
BIP-0341, are already hashes of their internal keys, so (a) Taproot outputs
actually have better quantum resistance than legacy outputs; and (b) adding
another hash would be strictly redundant.

-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] BIP-0322 (generic signmessage) improvements

2020-12-23 Thread Andrew Poelstra via bitcoin-dev
On Tue, Dec 22, 2020 at 12:22:37AM +, Pieter Wuille via bitcoin-dev wrote:
> 
> Re-reading your proposed text, I'm wondering if the "consensus-only 
> validation" extension is intended to replace the 
> inconclusive-due-to-consensus-and-standardness-differ state. If so, I don't 
> think it does, and regardless it doesn't seem very useful.
> 
> What I'm suggestion could be specified this way:
> * If validator understands the script:
>   * If signature is consensus valid (as far as the validator knows):
> * If signature is not known to trigger standardness rules intended for 
> future extension (well-defined set of rules listed in BIP, and revisable): 
> return valid
> * Otherwise: return inconclusive
>   * Otherwise: return invalid
> * Otherwise: return inconclusive
> 
> Or in other words: every signature has a well-defined result (valid, invalid, 
> inconclusive) + validators may choose to report inconclusive for anything 
> they don't understand.
> 
> This has the property that as long as new consensus rules only change things 
> that were covered under for-future-extension standardness rules, no two 
> validators will ever claim valid and invalid for the same signature. Only 
> valid+inconclusive or invalid+inconclusive.
>

I've updated my PR at https://github.com/bitcoin/bips/pull/1048

Differences:

1. I compacted all the validation states into three: valid at time/age T/S, 
invalid,
   and inconclusive.

2. "Inconclusive" means either an "upgradeable rule" failed, e.g. use of a NOP 
or a
   bad network version, or the validator just didn't understand the scripts.

3. I removed the "Extensions" sections now everything is in the main protocol.

4. I removed the "to_sign" transaction from the wire serialization, since after 
all
   this, it can always be inferred from the message and address. (This does 
mean,
   however, that there is no way to sign for scriptPubKeys that don't have 
addresses,
   e.g. bare public keys or multisigs. I don't think it's worth complicated the
   protocol for such obscure things.)

-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] New PSBT version proposal

2020-12-23 Thread Andrew Poelstra via bitcoin-dev
On Wed, Dec 23, 2020 at 12:30:20AM -0300, fiatjaf via bitcoin-dev wrote:
> Hi Andrew.
> 
> I'm just a lurker here and I have not much experience with PSBTs, but still 
> let me pose this very obvious question and concern: isn't this change going 
> to create a compatibility nightmare, with some software supporting version 1, 
> others supporting version 2, and the ones that care enough about UX and are 
> still maintained being forced to support both versions -- and for no very 
> important reason except some improvements in the way data is structured?
>

Yes, software will have to support both versions for a long time (likely
forever, at least in the case of Core). But I think this is okay, for a
couple of reasons:

1. it is very easy to convert from the old to new format, and from new to
   old (unless the new one uses features unsupported by the old). Indeed,
   the conversion logic is essentially the same as the logic that the
   Extractor role uses, so there isn't even that much redundant code.

2. There actually isn't a lot of software using PSBT out there, and most
   of that that does use PSBT is under rapid development. The obvious
   exception to this deployed hardware wallets, but as far as "software
   developers supporting old things for the sake of old hardware wallets"
   I think this transition is an order of magnitude simpler to handle
   than many of the ad-hoc protocol changes that individual vendors have
   done. In other words this is a "fact of life", and not even one of
   the grosser ones.

3. PSBT is pretty-much a dumb pure data format, and the diff between the
   new format and the old is pretty small.

> Ultimately I don't think it should matter if some data is structured in 
> not-the-best-possible way, as long as it is clear enough for the computer and 
> for the libraries already written to deal with it. Backwards-compatibility 
> and general interoperability is worth much more than anything else in these 
> cases.
>

The reasons for switching to PSBT 2 are actually more than just structuring
the data in a cleaner way. I agree that if the point of this upgrade were
just elegance, it would not be worth the compatibility loss. But there are
practical limitations that this proposal eliminates:

1. PSBT provides no way to modify the set of inputs or outputs after the
   Creator role is done.

2. Because of this, it forces certain things (e.g. locktimes and sequence
   numbers) to be chosen by the Creator, who may not have all the relevant
   information, and who certainly might not have it before any Updaters
   have done their part.

as well, of course, as elegance reasons:

3. Parsers of the existing PSBT need to understand the Bitcoin transaction
   format just to learn e.g. how many inputs and outputs there are. It is
   impossible to parse a PSBT without also parsing (almost) the whole
   transaction.

4. Similarly to cross-check fields like 'non_witness_utxo' which are
   committed to in the transaction, you have to parse the whole transaction
   just to make sure that the purely-redundant data is correctly redundant.

5. If you put a 0-input transaction into a PSBT (which would be pointless
   because there's no way to add inputs, but it's not forbidden so your
   software still has to deal with this somehow..), you need a different
   transaction parser than the normal one, because there is an ambiguity
   related to segwit that PSBT resolves differently.

It's also worth considering that PSBT is a young protocol, and future
extensions will be easier starting from PSBT 2 than starting from the
original version.

 
> Also let me leave this article here, which I find very important (even if for 
> some reason it ends up not being relevant to this specific case): 
> http://scripting.com/2017/05/09/rulesForStandardsmakers.html
> 

-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] BIP-0322 (generic signmessage) improvements

2020-12-21 Thread Andrew Poelstra via bitcoin-dev
On Tue, Dec 22, 2020 at 12:22:37AM +, Pieter Wuille via bitcoin-dev wrote:
> 
> Re-reading your proposed text, I'm wondering if the "consensus-only 
> validation" extension is intended to replace the 
> inconclusive-due-to-consensus-and-standardness-differ state. If so, I don't 
> think it does, and regardless it doesn't seem very useful.
> 
> What I'm suggestion could be specified this way:
> * If validator understands the script:
>   * If signature is consensus valid (as far as the validator knows):
> * If signature is not known to trigger standardness rules intended for 
> future extension (well-defined set of rules listed in BIP, and revisable): 
> return valid
> * Otherwise: return inconclusive
>   * Otherwise: return invalid
> * Otherwise: return inconclusive
> 
> Or in other words: every signature has a well-defined result (valid, invalid, 
> inconclusive) + validators may choose to report inconclusive for anything 
> they don't understand.
> 
> This has the property that as long as new consensus rules only change things 
> that were covered under for-future-extension standardness rules, no two 
> validators will ever claim valid and invalid for the same signature. Only 
> valid+inconclusive or invalid+inconclusive.
>

I like it!

My thinking regarding standardness vs consensus rules was essentially that
I wanted to enforce the included standardness rules for anti-malleability
reasons, i.e. the hope that for "normal scripts" we would get strong signatures,
which may be important for anti-DoS reasons. (What I mean by this is that
if you can easily create mutations of signatures, it may confuse software
in similar ways to the Gox-era malleability attacks on wallet software of
the time.) But conversely, it is hard to enforce these rules as an
implementor, because libbitcoinconsensus does not expose them. So allowing
both forms of validation, to me, was an attempt to encourage adoption
rather than anything principled.

I didn't even consider the idea that validators should be able to signal "this
signature appears to use future consensus rules", although I should have been
clued in by your "upgradeable rules" language that this was your goal. Now that
you say this, it's obvious that this is desireable, and also obvious that using
the "inconclusive" state is an elegant way to achieve this.

I also agree that "confirming validators should never disagree on valid vs
invalid" is a good design goal and we should make that explicit.


I'll add a commit to my PR at https://github.com/bitcoin/bips/pull/1048 which
adds these thoughts.

-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[bitcoin-dev] BIP-0322 (generic signmessage) improvements

2020-12-18 Thread Andrew Poelstra via bitcoin-dev
I have gone over BIP-0322 and substantially rewritten the text.
Everything I did is (I think) simply clarifying the existing
protocol, which felt like it was written by committee and wasn't
easy to follow, EXCEPT:

1. I rewrote the motivation section, which I believe originally
   was a paraphrase of Luke-jr's general objections to having any
   signmessage functionality. I hope Luke in particular can take
   a look at what I wrote under "Motivation" and see if it
   captures his concerns.

2. I merged the "consensus" and "upgradeable" rules to simply be
   one set of rules, consisting of consensus checks plus additional
   restrictions, all of which must be included. The new "Extensions"
   section allows validators to output the state "consensus-valid"
   if they really don't want to check the additional restrictions.

3. The "inconclusive" state, which was originally used for what I've
   called "consensus-valid", now indicates that a validator does not
   understand the script that it is checking (also described in the
   new "Extensions" section). The goal is that implementors are able
   to be meaningfully BIP-0322 while only supporting a subset of
   Script, e.g. the templates that their own software supports, or
   Miniscript, or the non-raw non-address set of output descriptors,
   or whatever.

   We have seen opposition to supporting BIP-322, e.g. [1] because
   of the requirement that you either have a full script interpreter
   (plus an open-ended list of Core's standardness flags, which is
   not even available through libbitcoinconsensus) or nothing. On
   the other hand, the vast majority of outputs are single-key p2pkh,
   p2pkwh or p2sh-wpkh.

The new text is here (and for posterity I will also include it
inline below, though unless Github deletes it it will be easier
to read in rendered form):

https://github.com/apoelstra/bips/blob/2020-12--bip322-overhaul/bip-0322.mediawiki

I'll also PR this to the BIPs repo in the next day or two, and
comments on Github are then welcome.


[1] https://bitcointalk.org/index.php?topic=5261605.0



* * * * * Full text of the above link * * * * *


  BIP: 322
  Layer: Applications
  Title: Generic Signed Message Format
  Author: Karl-Johan Alm 
  Comments-Summary: No comments yet.
  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0322
  Status: Draft
  Type: Standards Track
  Created: 2018-09-10
  License: CC0-1.0


== Abstract ==

A standard for interoperable signed messages based on the Bitcoin Script 
format, either for proving fund availability, or committing to a message as the 
intended recipient of funds sent to the invoice address.

== Motivation ==

The current message signing standard only works for P2PKH (1...) invoice 
addresses. We propose to extend and generalize the standard by using a Bitcoin 
Script based approach. This ensures that any coins, no matter what script they 
are controlled by, can in-principle be signed for. For easy interoperability 
with existing signing hardware, we also define a signature message format which 
resembles a Bitcoin transaction (except that it contains an invalid input, so 
it cannot be spent on any real network).

Additionally, the current message signature format uses ECDSA signatures which 
do not commit to the public key, meaning that they do not actually prove 
knowledge of any secret keys. (Indeed, valid signatures can be tweaked by 3rd 
parties to become valid signatures on certain related keys.)

Ultimately no message signing protocol can actually prove control of funds, 
both because a signature is obsolete as soon as it is created, and because the 
possessor of a secret key may be willing to sign messages on others' behalf 
even if it would not sign actual transactions. No signmessage protocol can fix 
these limitations.

== Types of Signatures ==

This BIP specifies three formats for signing messages: ''legacy'', ''simple'' 
and ''full''. Additionally, a variant of the ''full'' format can be used to 
demonstrate control over a set of UTXOs.

=== Legacy ===

New proofs should use the new format for all invoice address formats, including 
P2PKH.

The legacy format MAY be used, but must be restricted to the legacy P2PKH 
invoice address format.

=== Simple ===

A ''simple'' signature consists of a witness stack, consensus encoded as a 
vector of vectors of bytes, and base64-encoded. Validators should construct 
to_spend and to_sign as defined below, with default 
values for all fields except that

* message_hash is a BIP340-tagged hash of the message, as 
specified below
* message_challenge in to_spend is set to the 
scriptPubKey being signed with
* message_signature in to_sign is set to the provided 
simple signature.

and then proceed as they would for a full signature.

=== Full ===

Full signatures follow an analogous specification to the BIP-325 challenges and 
solutions used by Signet.

Let there be two virtual transactions to_spend and to_sign.

The "to_spend" transaction is:

Re: [bitcoin-dev] New PSBT version proposal

2020-12-16 Thread Andrew Poelstra via bitcoin-dev
On Wed, Dec 09, 2020 at 10:25:37PM +, Andrew Chow via bitcoin-dev wrote:
> Hi All,
> 
> I would like to propose a new PSBT version that addresses a few 
> deficiencies in the current PSBT v0. As this will be backwards 
> incompatible, a new PSBT version will be used, v1.
> 
> The primary change is to truly have all input and output data for each 
> in their respective maps. Instead of having to parse an unsigned 
> transaction and lookup some data from there, and other data from the 
> correct map, all of the data for an input will be contained in its map. 
> Doing so also disallows PSBT_GLOBAL_UNSIGNED_TX in this new version. 
> Thus I propose that the following fields be added:
> 
> Global:
> * PSBT_GLOBAL_TX_VERSION = 0x02
>  ?? * Key: empty
>  ?? * Value: 32-bit little endian unsigned integer for the transaction 
> version number. Must be provided in PSBT v1 and omitted in v0.

All of these changes sound great. It would definitely make working with
PSBTs easier if all data was accessible in the same format, rather than
being split between the global unsigned tx and the main body.

One minor quibble is the version numbering -- you mention "v1" in this
post but set GLOBAL_TX_VERSION to 2. I think we should consistently use
2 everywhere; probably nobody thinks of the existing PSBT as "version 0".

-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

2019-10-09 Thread Andrew Poelstra via bitcoin-dev
On Thu, Oct 03, 2019 at 11:05:52AM -0400, Ethan Heilman wrote:
> To avoid derailing the NO_INPUT conversation, I have changed the
> subject to OP_CAT.
> 
> Responding to:
> """
> * `SIGHASH` flags attached to signatures are a misdesign, sadly
> retained from the original BitCoin 0.1.0 Alpha for Windows design, on
> par with:
> [..]
> * `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> [..]
> """
> 
> OP_CAT is an extremely valuable op code. I understand why it was
> removed as the situation at the time with scripts was dire. However
> most of the protocols I've wanted to build on Bitcoin run into the
> limitation that stack values can not be concatenated. For instance
> TumbleBit would have far smaller transaction sizes if OP_CAT was
> supported in Bitcoin. If it happens to me as a researcher it is
> probably holding other people back as well. If I could wave a magic
> wand and turn on one of the disabled op codes it would be OP_CAT.  Of
> course with the change that size of each concatenated value must be 64
> Bytes or less.
>

Just throwing my two cents in here - as others have noted, OP_CAT
lets you create Merkle trees (allowing e.g. log-sized accountable
threshold sigs, at least in a post-Schnorr future).

It also allows manipulating signatures - e.g. forcing the revelation
of discrete logs by requiring the user use the (1/2) point as a nonce
(this starts with 11 zero bytes, which no other computationally
accessible point does), or by requiring two sigs with the same nonce.

It also lets you do proof-of-work-like computations on hashes or
curvepoints; or enforce that EC points come from a hash and have
no known discrete log. You can also switch on hashes, something
currently impossible because of the 4-byte limitation on numeric
opcodes. I don't have specific application of these in mind but
definitely have cut off many lines of inquiry because they were
impossible.

You could build a crappy Lamport signature, though the key would
be so big that you'd never do this pre-MAST :P.


-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Timelocks and Lightning on MimbleWimble

2019-09-20 Thread Andrew Poelstra via bitcoin-dev
On Fri, Sep 20, 2019 at 04:54:34AM +1000, Lloyd Fournier via bitcoin-dev wrote:
> Hi ZmnSCPxj,
> 
> I can give some context on the exchange during the talk. I was the "Q" and
> Andrew Polestra was the "A".
> 
> I followed up with Andrew after and he indeed knew about the pre-signed
> nlocktime transaction double spend technique (actually, I thought he was
> the one who originally came up with that idea for scriptless atomic swaps).
> He clarified saying that you can do that with locktime (absolute time
> locks) but not with sequence numbers (relative time locks). i.e. to enforce
> sequence numbers you need to use OP_CHECKSEQUENCEVERIFY. He said that it
> would make sense to change that so it's enforced regardless of script.
> 
> However, I talked to Antoine Riard later who was adamant that sequence
> numbers already worked as expected. He pointed to the fact that BIP68
> already describes it as an independent constraint [1]
> 
> So if things do work as described in BIP68 then we should be able to do
> lightning on Bitcoin without any script once we have Schnorr. I'm keen to
> actually figure out all the details of how to do this. It works in my head
> but I think I should write it down somewhere to make sure it works.
> 
>  [1] https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki
> 
> LL
>

Yep, during the recorded exchange I was confused about the content of
the BIP. Later I described the exchange to Dan Robinson, who showed me
the actual text :).

Sorry for the confusion - Lloyd was totally right and you can do
relative locktimes this way in Taproot without needing to expose a
script.


Having said this, there is the important caveat that your "emergency
backout" keys are online to produce a pre-signed transaction, and
that a suitable destination is known beforehand. This makes sense for
Lightning or most atomic swap protocols where the money simply returns
to the original owner, but not e.g. for Liquid, where the emergency
keys have never been brought online (and anyway the contents of any
transaction they might sign depends on facts and circumstances that
aren't known ahead of time).


-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[bitcoin-dev] BIP174 / PSBT extensions

2019-03-07 Thread Andrew Poelstra via bitcoin-dev
Hi all,


I'd like to start initial discussion about an extension to BIP174 [1] to add
some fields that I've found myself wanting when using PSBT in practice. For
now I'll just list the things that I'd like to see, and if we can come up
with a stable list then I'll try to write up a more formal draft.

Basically I'd just like to add some more fixed data fields.

1. Add an field to PSBT_GLOBAL_UNSIGNED_TX to the global table which contains
   just a txid of the unsigned transaction, for bandwidth savings in case
   signers have already seen the tx or can construct it themselves.

   This field would be fixed 32 bytes.

   (This would actually be a breaking change since the current PSBT rules 
require
   PSBT_GLOBAL_UNSIGNED_TX to always be present. Maybe this is a no-go for that
   reason alone.)

2. Add a version field to the global table.

3. Add fields to the per-input tables for
   (a) confirmed depth of the referenced txout; this is useful for finalizers
   trying to create optimized witnesses, for e.g. cases when CSV timeouts
   expire and some signatures become unnecessary.

   This field must be a varint.

   (b) a map from SHA2 hashes to their 32-byte preimages; this field must be
   fixed 32 bytes. This, plus the CSV thing, would allow writing finalizers
   that work with all of Miniscript [2].

   (c) a map from public keys to 32-byte "tweaks" that are used in the 
pay-to-contract
   construction. Selfishly I'd like this to be a variable-length bytestring
   with the semantics that (a) the first 33 bytes represent an untweaked
   pubkey; (b) the HMAC-SHA256 of the whole thing, when multiplied by G and
   added to the untweaked pubkey, result in the target key. This matches the
   algorithm in [3] which is deployed in Blockstream's Liquid, but I'd be
   happy with a more efficient scheme which e.g. used SHA256 rather than
   HMAC-SHA256.

   (d) maps from public keys to partial nonce commitments, partial nonces, and
   partial signatures, for MuSig [4] support.

   (e) a map from signatures (or signature nonces?) to sign-to-contract tweaks.
   Same semantics as (c) above.

   The last two suggestions are probably premature and need further development
   and standardization of the related protocols. But I'm throwing them in to see
   if other people have strong feelings about this.

4. Add fields to the per-output tables for pay-to-contract, like in (c) above.

5. Add a field (or rather, family of fields) to every table which is 
"proprietary
   use" and guaranteed not to be defined by any future PSBT extension. 
Specifically
   every field with key-type 0xFF could be considered "proprietary".

5a. The special field in the global table whose key is only 0xFF should be a
"proprietary version field" with unspecified semantics but an understanding
that specific users might stick a GUID or something in there as a way to
recognize their own PSBTs.

[1] https://github.com/bitcoin/bips/blob/master/bip-0174.mediawiki#Encoding
[2] http://bitcoin.sipa.be/miniscript/miniscript.html
[3] 
https://github.com/ElementsProject/elements/blob/elements-0.14.1/src/validation.cpp
[4] https://eprint.iacr.org/2018/068


-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"There are some mornings when the sky looks like a road
 There are some dragons who were built to have and hold
 And some machines are dropped from great heights lovingly
 And some great bellies ache with many bumblebees
 And they sting so terribly"
   --Joanna Newsom

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Schnorr signatures BIP

2018-09-14 Thread Andrew Poelstra via bitcoin-dev
On Tue, Sep 11, 2018 at 01:37:59PM -0400, Erik Aronesty via bitcoin-dev wrote:
> - Musig, by being M of M, is inherently prone to loss.
>

It has always been possible to create M-of-N threshold MuSig signatures for any
M, N with 0 < M ≤ N. This is (a) obvious, (b) in our paper, (c) implemented at

https://github.com/apoelstra/secp256k1/blob/2018-04-taproot/src/modules/musig/main_impl.h
 

-- 
Andrew Poelstra
Research Director, Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"Make it stop, my love; we were wrong to try
 Never saw what we could unravel in traveling light
 Nor how the trip debrides like a stack of slides
 All we saw was that time is taller than space is wide"
   --Joanna Newsom



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Schnorr signatures BIP

2018-09-05 Thread Andrew Poelstra via bitcoin-dev
On Wed, Sep 05, 2018 at 08:26:14AM -0400, Erik Aronesty wrote:
> Why would you call it FUD?   All the weird hemming and hawing about it is
> really strange to me.  The more I look into it and speak to professors
> about i, the more it seems "so trivial nobody really talks about it".
> 
> 1. Generate an M of N shared public key (done in advance of signing 
> this gets you the bitcoin address)
> 2. Generate signature fragments (this can be done offline, with no
> communication between participants)
> 
> Detailed explanation with code snippets:
> 
> https://medium.com/@simulx/an-m-of-n-bitcoin-multisig-scheme-e7860ab34e7f
>

The hemming and hawing is because you've been repeatedly told that your
scheme doesn't work, and to please implement it in some computer algebra
system so that you can see that (or so we can see where your mistake is),
and you instead continue to post incomplete/incoherent copies of the same
thing across multiple mediums - Reddit, this list, Bitcointalk, Medium,
etc ad nauseum.

It's distracting and offensive to people who have spent a lot of time and
energy thinking about this stuff, and more importantly it causes confusion
in the public eye. Phrasings like "weird hemming and hawing" suggest that
we don't know/don't care about some insight you have, which is not true.
This is why your posts are FUD.

For example, in your linked post I looked at every single instance of the
character 'k' and *not one of them* defined the value 'k' from which 'R'
is derived in the signing procedure.


Of course there is no possible value, individual signers cannot learn 'R'
at signing time without interaction, and your whole scheme is broken. Given
the number of times you've been told this, I find it hard to believe that
this was an honest mistake.



Andrew



-- 
Andrew Poelstra
Research Director, Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"Make it stop, my love; we were wrong to try
 Never saw what we could unravel in traveling light
 Nor how the trip debrides like a stack of slides
 All we saw was that time is taller than space is wide"
   --Joanna Newsom



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Schnorr signatures BIP

2018-09-03 Thread Andrew Poelstra via bitcoin-dev
On Wed, Aug 29, 2018 at 08:09:36AM -0400, Erik Aronesty wrote:
> Note:
> 
> This spec cannot be used directly with a shamir scheme to produce
> single-round threshold multisigs, because shares of point R would need to
> be broadcast to share participants in order to produce valid single
> signatures.
> 
> (R, s) schemes can still be used "online", if share participants publish
> the R(share) but, not sure if it matter much, this choice eliminates
> offline multiparty signing in exchange for batch validation.
>

Please stop with this FUD. No tradeoff was made. There are no non-interactive
Schnorr signatures.


Andrew
 

-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
   --Joanna Newsom



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Schnorr signatures BIP

2018-08-12 Thread Andrew Poelstra via bitcoin-dev

I think it's just an oversight. We should specify that we use the standard
encoding from section 2.3 of http://www.secg.org/sec1-v2.pdf except that
we allow only compressed public keys.

Andrew


On Mon, Aug 06, 2018 at 11:12:48PM +0200, Tim Ruffing via bitcoin-dev wrote:
> Is it intentional that the encoding of public (and private) keys is
> unspecified? I'd consider at least the encoding of the public key to be
> part of the signature scheme, so ideally it should be specified already
> in this BIP. On the other hand, there may be good arguments against it,
> but I'm not aware of any.
> 
> This issue leads to a discrepancy between the specification and the
> test vectors because the data fields of test vectors "are given as byte
> arrays", including public and secret key. As a consequence, even the
> Python reference implementation in the BIP draft doesn't work on test
> vectors (in a strict sense).
> 
> Best,
> Tim
> 
> 
> On Fri, 2018-07-06 at 11:08 -0700, Pieter Wuille via bitcoin-dev wrote:
> > Hello everyone,
> > 
> > Here is a proposed BIP for 64-byte elliptic curve Schnorr signatures,
> > over the same curve as is currently used in ECDSA:
> > https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
> > 
> > It is simply a draft specification of the signature scheme itself. It
> > does not concern consensus rules, aggregation, or any other
> > integration into Bitcoin - those things are left for other proposals,
> > which can refer to this scheme if desirable. Standardizing the
> > signature scheme is a first step towards that, and as it may be
> > useful
> > in other contexts to have a common Schnorr scheme available, it is
> > its
> > own informational BIP.
> > 
> > If accepted, we'll work on more production-ready reference
> > implementations and tests.
> > 
> > This is joint work with several people listed in the document.
> > 
> > Cheers,
> > 
> 
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
> 

-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
   --Joanna Newsom



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Should Graftroot be optional?

2018-05-24 Thread Andrew Poelstra via bitcoin-dev
On Thu, May 24, 2018 at 11:44:16AM +0200, Natanael via bitcoin-dev wrote:
> 
> As stated above by Wuille this seems to not be a concern for typical P2SH
> uses, but my argument here is simply that in many cases, not all
> stakeholders in a transaction will hold one of the private keys required to
> sign. And such stakeholders would want a guarantee that the original script
> is followed as promised.
>

In this case, even mandatory graftroot would not allow the signing stakeholders
to take the coins. The reason is that if there are _any_ non-signing script
conditions that must be followed, then to use Taproot the top-level public key
needs to be unusable, e.g. by being a NUMS point. In that case the public key
would also be unusable for Graftroot.

Another way to see this is -- in any context where Graftroot seems dangerous,
there needs to be a reason why the ability to just create transactions is not
dangerous. In your example it seems that the signing parties can just take
the coins with or without Graftroot, so the problem is not in Graftroot but
in the way that the example is set up.
 
> I'm not concerned by the ability to move funds to an address with the new
> rules that you'd otherwise graftroot in, only that you can provide a
> transparent guarantee that you ALSO follow the original script as promised.
> What happens *after* you have followed the original script is unrelated,
> IMHO.
>

To do this in Taproot you need to disable the top-level key, which will also
disable Graftroot. 

-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
   --Joanna Newsom



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Should Graftroot be optional?

2018-05-23 Thread Andrew Poelstra via bitcoin-dev
On Wed, May 23, 2018 at 01:50:13PM +, Andrew Poelstra via bitcoin-dev wrote:
> 
> Graftroot also break blind signature schemes. Consider a protocol such as [1]
> where some party has a bunch of UTXOs all controlled (in part) by the same
> key X. This party produces blind signatures on receipt of new funds, and can
> only verify the number of signatures he produces, not anything about what he
> is signing.
> 
> BTW, the same concern holds for SIGHASH_NOINPUT, which I'd also like to be
> disable-able. Maybe we should extend one of ZmnSCPxj's suggestions to include
> a free "flags" byte or two in the witness?
> 
> (I also had the same concern about signature aggregation. It seems like it's
> pretty hard to preserve the "one signature = at most one input" invariant of
> Bitcoin, but I think it's important that it is preserved, at least for
> outputs that need it.)
> 
> Or maybe, since it appears it will require a space hit to support optional
> graftroot anyway, we should simply not include it in a proposal for Taproot,
> since there would be no opportunity cost (in blockchain efficiency) to doing
> it later.
> 
> [1] https://github.com/apoelstra/scriptless-scripts/pull/1 
>

On further thought, I rescind this concern (ditto for SIGHASH_NOINPUT) (but
not for aggregate sigs, they still interact badly with blind signatures).

As long as graftroot (and NOINPUT) sigs commit to the public key, it is
possible for a server to have unique keys for every output, even while
retaining the same private key, and thereby ensure that "one sig can spend
only one output" holds. To do this, suppose the server has a BIP32 xpubkey
(xG, cc). A blind signer using the private key x can be made to sign not
only for xG, but also for any publicly-derived child keys of (xG, cc).

Here is a simple scheme that does this:

  1. Signer provides a nonce R = kG

  2. Challenger computes bip32 tweak h, chooses blinders alpha and beta,
 and computes:
 R' = R + alpha*G + beta*P
 e  = H(P + hG || R' || tx)
 e' = e + beta
 and sends e' to the signer.

  3. Signer replies with s = k + xe' (= k + beta*x + (x + h)e - he)

  4. Challenger unblinds this as s' = s + alpha + he

(This blind signature scheme is vulnerable to Wagner's attack, though see
Schnorr 2004 [1] for mitigations that are perfectly compatible with this
modified BIP32ish scheme.)

I'm unsure whether key-prefixing is _actually_ necessary for this, but it
makes the security argument much clearer since the messagehash contains
some data which can be made unique per-utxo and is committed in the chain.


Andrew


[1] 
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=8ECEF929559865FD68D1D873555D18FE?doi=10.1.1.68.9836=rep1=pdf


-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
   --Joanna Newsom



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Should Graftroot be optional?

2018-05-23 Thread Andrew Poelstra via bitcoin-dev
On Tue, May 22, 2018 at 11:17:42AM -0700, Pieter Wuille via bitcoin-dev wrote:
> 
> Given the recent discussions about Taproot [1] and Graftroot [2], I
> was wondering if a practical deployment needs a way to explicitly
> enable or disable the Graftroot spending path. I have no strong
> reasons why this would be necessary, but I'd like to hear other
> people's thoughts.
>

Graftroot also break blind signature schemes. Consider a protocol such as [1]
where some party has a bunch of UTXOs all controlled (in part) by the same
key X. This party produces blind signatures on receipt of new funds, and can
only verify the number of signatures he produces, not anything about what he
is signing.

BTW, the same concern holds for SIGHASH_NOINPUT, which I'd also like to be
disable-able. Maybe we should extend one of ZmnSCPxj's suggestions to include
a free "flags" byte or two in the witness?

(I also had the same concern about signature aggregation. It seems like it's
pretty hard to preserve the "one signature = at most one input" invariant of
Bitcoin, but I think it's important that it is preserved, at least for
outputs that need it.)

Or maybe, since it appears it will require a space hit to support optional
graftroot anyway, we should simply not include it in a proposal for Taproot,
since there would be no opportunity cost (in blockchain efficiency) to doing
it later.

[1] https://github.com/apoelstra/scriptless-scripts/pull/1 

-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
   --Joanna Newsom



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Soft-forks and schnorr signature aggregation

2018-03-21 Thread Andrew Poelstra via bitcoin-dev
On Wed, Mar 21, 2018 at 02:06:18PM +1000, Anthony Towns via bitcoin-dev wrote:
> 
> That leads me to think that interactive signature aggregation is going to
> take a lot of time and work, and it would make sense to do a v1-upgrade
> that's "just" Schnorr (and taproot and MAST and re-enabling opcodes and
> ...) in the meantime. YMMV.
>

Unfortunately I agree. Another complication with aggregate signatures is
that they complicate blind signature protocols such as [1]. In particular
they break the assumption "one signature can spend at most one UTXO"
meaning that a blind signer cannot tell how many coins they're authorizing
with a given signature, even if they've ensured that the key they're using
only controls UTXOs of a fixed value.

This seems solvable with creative use of ZKPs, but the fact that it's even
a problem caught me off guard, and makes me think that signature aggregation
is much harder to think about than e.g. Taproot which does not change
signature semantics at all.


Andrew



[1] 
https://github.com/jonasnick/scriptless-scripts/blob/blind-swaps/md/partially-blind-swap.md



-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
   --Joanna Newsom



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

2018-01-23 Thread Andrew Poelstra via bitcoin-dev
On Tue, Jan 23, 2018 at 10:45:06PM +, Gregory Maxwell via bitcoin-dev wrote:
> On Tue, Jan 23, 2018 at 10:22 PM, Anthony Towns  wrote:
> > Hmm, at least people can choose not to reuse addresses currently --
> > if everyone were using taproot and that didn't involve hashing the key,
> 
> Can you show me a model of quantum computation that is conjectured to
> be able to solve the discrete log problem but which would take longer
> than fractions of a second to do so? Quantum computation has to occur
> within the coherence lifetime of the system.
> 
> > way for individuals to hedge against quantum attacks in case they're ever 
> > feasible, at least that I can see (well, without moving their funds out of 
> > bitcoin anyway)?
> 
> By using scriptpubkeys with actual security against quantum computers
> instead of snake-oil.
> 
> > (It seems like using the point at infinity wouldn't work because
> 
> Indeed, that doesn't work.
> 
> > that when quantum attacks start approaching feasibility. If funds are
> > being held in reused addresses over the long term, that would be more
> 
> They are. But I don't believe that is relevant; the attacker would
> simply steal the coins on spend.


Then the system would need to be hardforked to allow spending through a
quantum-resistant ZKP of knowledge of the hashed public key. I expect
that in a post-quantum world there will be demand for such a fork,
especially if we came into such a world through surprise evidence of
a discrete log break.

-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
   --Joanna Newsom



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Updates on Confidential Transactions efficiency

2017-12-04 Thread Andrew Poelstra via bitcoin-dev
To follow up on the remarkable work Greg announced from Benedikt Bünz (Stanford)
and Jonathan Bootle (UCL) on Bulletproofs: https://eprint.iacr.org/2017/1066

Summary
=

Over the last couple weeks, along with Jonas Nick, Pieter Wuille, Greg Maxwell
and Peter Dettmann, I've implemented the single-output version of Bulletproofs
at https://github.com/ElementsProject/secp256k1-zkp/pull/16 and have some
performance numbers.

All of these benchmarks were performed on one core of an Intel i7-6820MQ
throttled to 2.00Ghz, and reflect verification of a single 64-bit rangeproof.


Old Rangeproof14.592 ms
 with endo10.304 ms
Bulletproof4.208 ms
 with endo 4.031 ms
ECDSA verify   0.117 ms
 with endo 0.084 ms


Here "with endo" refers to use of the GLV endomorphism supported by the curve
secp256k1, which libsecp256k1 (and therefore Bitcoin) supports but does not
enable by default, out of an abundance of caution regarding potential patents.

As we can see, without the endomorphism this reflects a 3.47x speedup over
the verification speed of the old rangeproofs. Because Bulletproof verification
scales with O(N/log(N)) while the old rangeproof scales with O(N), we can
extrapolate forward to say that a 2-output aggregate would verify with 4.10x
the speed of the old rangeproofs.

By the way, even without aggregation, we can verify two rangeproofs nearly 15%
faster than verifying one twice (so a 3.95x speedup) because the nature of the
verification equation makes it amenable to batch verification. This number
improves with the more proofs that you're verifying simultaneously (assuming
you have enough RAM), such that for example you can batch-verify 1
bulletproofs 9.9 times as fast as you could verify 1 of the old proofs.


While this is a remarkable speedup which greatly improves the feasibility of
CT for Bitcoin (though still not to the point where I'd expect a serious
proposal to get anywhere, IMHO), the concerns highlighted by Greg regarding
unconditional versus computational soundness remain. I won't expand on that
more than it has already been discussed in this thread, I just want to tamp
down any irrational exhuberance about these result.


People who only care about numbers can stop reading here. What follows is a
discussion about how this speedup is possible and why we weren't initially
sure that we'd get any speedup at all.


Details
=

Section 6 of the linked preprint discusses performance vs our old rangeproofs. 
As
Greg mentioned, it is possible to fit two 64-bit bulletproofs into 738 bytes,
with logarithmic scaling. (So one proof would take 674 bytes, but eight proofs
only 866 bytes.)

However, this section does not give performance numbers, because at the time
the preprint was written, there was no optimized implementation on which to
benchmark. It was known that verification time would be roughly linear in the
size of the proof: 141 scalar-multiplies for a 64-bit proof, 270 for an
aggregate of two proofs, and so on [*]. Our old rangeproofs required only 128
multiplies for a 64-bit proof, then 256 for two, and so on. So naively we were
concerned that the new Bulletproofs, despite being fantastically smaller than
the original rangeproofs, might wind up taking a bit longer to verify.

For reference, an ordinary ECDSA signature verification involves 2 multiplies.
So roughly speaking, the naive expectation was that a N-bit rangeproof would
require N-many signature verifications' worth of CPU time, even with this new
research. Worse, we initially expected bulletproofs to require 1.5x this much,
which we avoided with a trick that I'll describe at the end of this mail.

As you can see in the above numbers, the old rangeproofs actually perform worse
than this expectation, while the new Bulletproofs perform significantly 
**better**.
These are for the same reason: when performing a series of scalar 
multiplications
of the form

  a*G + b*H + c*I + ...

where G, H, I are curvepoints and a, b, c are scalars, it is possible to compute
this sum much more quickly than simply computing a*G, b*H, c*I separately and
then adding the results. Signature validation takes advantage of this speedup,
using a technique called Strauss' algorithm, to compute the sum of two 
multiplies
much faster than twice the multiple-speed. Similarly, as we have learned, the
141 scalar-multiplies in a single-output Bulletproof can also be done in a 
single
sum. To contrast, the old rangeproofs required we do each multiplication 
separately,
as the result of one would be hashed to determine the multiplier for the next.

libsecp256k1 has supported Strauss' algorithm for two points since its inception
in 2013, since this was needed for ECDSA verification. Extending it to many 
points
was a nontrivial task which Pieter, Greg and Jonas Nick took on this year as 
part
of our aggregate signatures project. Of the algorithms that we tested, we found
that Strauss was fastest up to about 100 points, 

Re: [bitcoin-dev] hypothetical: Could soft-forks be prevented?

2017-09-15 Thread Andrew Poelstra via bitcoin-dev
On Fri, Sep 15, 2017 at 10:40:12PM +0200, Simone Bronzini via bitcoin-dev wrote:
> Since a soft-fork is a restriction of the consensus rules, I think the
> only way to have an un-soft-forkable cryptocurrency is creating a
> cryptocurrency where no transaction is valid.
> 

Even this can be soft-forked to add an extension block that contains 
transactions :)

Ultimately I think the best you can do in this direction is to design for
maximal fungibility and/or transaction structures that minimize interaction
with the blockchain. This minimizes the surface for transaction censorship,
which is somewhat in the spirit of your goal.

-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
   --Joanna Newsom



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Per-block non-interactive Schnorr signature aggregation

2017-05-10 Thread Andrew Poelstra via bitcoin-dev
On Tue, May 09, 2017 at 09:59:06PM -0400, Russell O'Connor via bitcoin-dev 
wrote:
> I'm a bit amateur at this sort of thing, but let me try to argue that this
> proposal is in fact horribly broken ;)
> 
> Suppose Alice has some UTXO with some money Bob wants to steal.  Grant me
> that the public key P0 protecting Alice's UTXO is public (say because the
> public key has been reused elsewhere).
> 
> Bob going to spend Alice's UTXO by generating random values s0, k0 and R0
> := k0*G and thus creating a random signature for it, [R0, s0].  Now clearly
> this signature isn't going to be valid by itself because it is just random.
> Bob's goal will be to make a transaction with other inputs such that, while
> the individual signatures are not valid, the aggregated signature will be
> valid.
>

If you seed the randomization with every R value (which would come for free
if you used, say, the witness root) then Wagner's attack no longer applies.

The idea is that no aggregation occurs until a miner produces a block. You
have a bunch of independent Schnorr sigs (s_i, R_i). Then the _miner_ multiples
each s_i by H(witness root || index) or whatever, sums up the s_i's, and commits
the sum somewhere where it doesn't affect the root.

Verifiers then multiply each R_i by the same multiplying factors and are able
to do a batch verification of them.


Verifiers who have seen a signature before and cached it as valid can save
themselves a bit of time by subtracting H(witness root || index)*s_i from
the summed s-value and then skipping R_i in the above step. These are scalar
operations and are extremely cheap.

They can recognize the signature given only the transaction it signs and R_i,
which uniquely determine a valid signature.


I believe this is what Tadge was referring to when he mentioned a talk of mine.
It's roughly what I've had in mind whenever I talk about non-interactive Schnorr
aggregation.



Cheers
Andrew


-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
   --Joanna Newsom



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Small Nodes: A Better Alternative to Pruned Nodes

2017-04-20 Thread Andrew Poelstra via bitcoin-dev
On Thu, Apr 20, 2017 at 11:46:33AM +0200, Tom Zander via bitcoin-dev wrote:
> On Wednesday, 19 April 2017 19:30:30 CEST David Vorick via bitcoin-dev 
> wrote:
> > > I suggested something similar which is a much simpler version;
> > > https://zander.github.io/scaling/Pruning/
> 
> > Your proposal has a significant disadvantage: If every peer is dropping
> > 75% of all blocks randomly, then you need to connect to a large number of
> > peers to download the whole blockchain.
> ...
> > If you are downloading 450,000 blocks, you will need to
> > connect to an expected 46 peers to download the whole blockchain.
> 
> I don’t really see the problem here, even if your math is a off. (Statistics 
> is difficult, I know). Connecting to many nodes to download faster is really 
> not an issue and already happens.
>

I think the expected number of peers is actually ~47.75, which is pretty
close to David's estimate, which was wrong in a way that was actually
more favorable to the "everyone stores random blocks" scheme than the
truth.

Even assuming no archival nodes, and all nodes storing only one random
index between 5 and 255 inclusive, the chance of five arbitrary nodes
giving unique indices by chance is about 98.4%. To get the same probability
from a scheme where each peer has only 25% of the blocks, you need to
connect to 59.59 nodes.

This is over a ten-times increase in the number of nodes required to
download the entire chain, and requires participating nodes to use 25%
more space than David's proposal.

> > Your proposal is also a lot less able to handle active adversaries: if
> > nodes are randomly dropping blocks, the probability that one block in
> > particular is dropped by everyone goes up significantly. 
> 
> You make the assumption that this new mode of pruning will be used by 100% 
> of the network, this is not how distributed systems work.
>

Storing random but complete blocks requires the assumption this is _not_ the
case; David's does not make any assumptions. So on top of the performance
considerations there is this potential DoS vector.
 

-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
   --Joanna Newsom



signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev