Re: [bitcoin-dev] Compressed Bitcoin Transactions

[Andrew Poelstra via bitcoin-dev]

Thanks Tom.

It looks like you posted a text-scrape of the rendered markdown, which
is hard to read. For posterity here is the full text.

Best
Andrew


=== begin compressed_transactions.md ===

# Compressed Transaction Schema
By (Tom Briar) and (Andrew Poelstra)

## 1. Abstract

With this Transaction Compression Schema we use several methods to compress 
transactions,
including dropping data and recovering it on decompression by grinding until we 
obtain
valid signatures.

The bulk of our size savings come from replacing the prevout of each input by a 
block
height and index. This requires the decompression to have access to the 
blockchain, and
also means that compression is ineffective for transactions that spend 
unconfirmed or
insufficiently confirmed outputs.

Even without compression, Taproot keyspends are very small: as witness data they
include only a single 64/65-byte signature and do not repeat the public key or
any other metadata. By using pubkey recovery, we obtain Taproot-like compression
for legacy and Segwit transactions.

The main applications for this schema are for steganography, satellite/radio 
broadcast, and
other low bandwidth channels with a high CPU availability on decompression. We
assume users have some ability to shape their transactions to improve their
compressibility, and therefore give special treatment to certain transaction 
forms.

This schema is easily reversible except for compressing the Txid/Vout input 
pairs(Method 4).
Compressing the input Txid/Vout is optional, and without it still gleans 50% of 
the
total compression. This allows for the additional use case of P2P communication.

## 2. Methods

The four main methods to achieve a lower transactions size are:

1. packing transaction metadata before the transaction and each of its inputs 
and
outputs to determine the structure of the following data.
2. replacing 32-bit numeric values with either variable-length integers 
(VarInts) or compact-integers (CompactSizes).
3. using compressed signatures and public key recovery upon decompression.
4. replacing the 36-byte txid/vout pair with a blockheight and output index.

Method 4 will cause the compressed transaction to be undecompressable if a block
reorg occurs at or before the block it's included in. Therefore, we'll only 
compress
the Txid if the transaction input is at least one hundred blocks old.


## 3 Schema

### 3.1 Primitives

| Name | Width | Description |
|--|---|-|
| CompactSize  | 1-5 Bytes | For 0-253, encode the value directly in one 
byte. For 254-65535, encode 254 followed by 2 little-endian bytes. For 
65536-(2^32-1), encode 255 followed by 4 little-endian bytes. |
| CompactSize flag | 2 Bits| 1, 2 or 3 indicate literal values. 0 indicates 
that the value will be encoded in a later CompactInt. |
| VarInt   | 1+ Bytes  | 7-bit little-endian encoding, with each 7-bit 
word encoded in a byte. The highest bit of each byte is 1 if more bytes follow, 
and 0 for the last byte. |
| VLP-Bytestream   | 2+ Bytes  | A VarInt Length Prefixed Bytestream. Has a 
VarInt prefixed to determine the length. |

### 3.2 General Schema

| Name   | Width   | Description |
||-|-|
| Transaction Metadata   | 1 Byte| Information on the structure of 
the transaction. See Section 3.3. |
| Version| 0-5 Bytes | An optional CompactSize 
containing the transactions version. |
| Input Count| 0-5 Bytes | An optional CompactSize 
containing the transactions input count. |
| Output Count   | 0-5 Bytes | An optional CompactSize 
containing the transactions output count. |
| LockTime   | 0-5 Bytes | An optional CompactSize 
containing the transaction LockTime if its non zero. |
| Minimum Blockheight| 1-5 Bytes | A VarInt containing the Minimum 
Blockheight of which the transaction locktime and input blockheights are given 
as offsets. |
| Input Metadata+Output Metadata | 1+ Bytes  | A Encoding containing metadata 
on all the inputs and then all the outputs of the transaction. For each input 
see Section 3.4, for each output see Section 3.5. |
| Input Data | 66+ Bytes | See Section 3.6 for each input. |
| Output Data| 3+ Bytes  | See Section 3.7 for each output. 
|

For the four CompactSize listed above we could use a more compact bit encoding 
for these but they are already a fall back for the bit encoding of the 
Transaction Metadata.

### 3.3 Transaction Metadata

| Name | Width  | Description |
|--||-|
| Version  | 2 Bits | A CompactSize flag for the transaction version. |
| Input Count  | 2 Bits | A CompactSize flag for the transaction input count. |
| Output Count | 2 Bits | A CompactSize flag for the transaction output count. |
| LockTime 

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Andrew Poelstra via bitcoin-dev]

On Tue, Oct 24, 2023 at 02:15:49PM +1030, Rusty Russell wrote:
> Andrew Poelstra  writes:
> > I had a similar thought. But my feeling is that replacing the stack
> > interpreter data structure is still too invasive to justify the benefit.
> >
> > Also, one of my favorite things about this BIP is the tiny diff.
> 
> To be fair, this diff is even smaller than the OP_CAT diff :)
>

Oh, look at that :). For some reason I had it in my head that looping
like this would mess up the asymptotics and meaningfully harm
performance. But no, it just involves adding (at most) 1000 numbers.
Which is unlikely to even be measurable.

> Though I had to strongly resist refactoring, that interpreter code
> needs a good shake!  Using a class for the stack is worth doing anyway
> (macros, really??).
>

Hah, agreed, but it still makes my hands sweat to think about refactoring
that file.

-- 
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] Proposed BIP for OP_CAT

[Andrew Poelstra via bitcoin-dev]

On Tue, Oct 24, 2023 at 11:18:24AM +1030, Rusty Russell wrote:
> Andrew Poelstra  writes:
> >> 3. Should we restrict elsewhere instead?  After all, OP_CAT doesn't
> >>change total stack size, which is arguably the real limit?
> >> 
> >
> > Interesting thought. Right now the stack size is limited to 1000
> > elements of 520 bytes each, which theoretically means a limit of 520k.
> > Bitcoin Core doesn't explicitly count the "total stack size" in the
> > sense that you're suggesting; it just enforces these two limits
> > separately.
> 
> BTW, I'm just learning of the 1000 element limit; I couldn't see it on
> scanning BIP-141.
>

This limit is very old and predates segwit. It might predate P2SH.

> > I think trying to add a "total stack size limit" (which would have to
> > live alongside the two existing limits; we can't replace them without
> > a whole new Tapscript version) would add a fair bit of accounting
> > complextiy and wind up touching almost every other opcode...probably
> > not worth the added consensus logic.
> 
> Simplest thing I can come up with:
> 
> - instead of counting simple stack depth, count each stack entry as
>   (1 + /520) entries?  You can still only push 520 bytes, so you
>   can only make these with OP_CAT.
> 
> Looking in interpreter.cpp, `stack` and `altstack` now need to be
> objects to count entries differently (not vectors), but it seems like
> it'd be simple enough, and the logic could be enabled unconditionally
> since it Cannot Be Violated prior to OP_CAT.
>

I had a similar thought. But my feeling is that replacing the stack
interpreter data structure is still too invasive to justify the benefit.

Also, one of my favorite things about this BIP is the tiny diff.

-- 
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] Ordinals BIP PR

[Andrew Poelstra via bitcoin-dev]

On Mon, Oct 23, 2023 at 03:35:30PM +, Peter Todd via bitcoin-dev wrote:
> 
> I have _not_ requested a BIP for OpenTimestamps, even though it is of much
> wider relevance to Bitcoin users than Ordinals by virtue of the fact that much
> of the commonly used software, including Bitcoin Core, is timestamped with 
> OTS.
> I have not, because there is no need to document every single little protocol
> that happens to use Bitcoin with a BIP.
> 
> Frankly we've been using BIPs for too many things. There is no avoiding the 
> act
> that BIP assignment and acceptance is a mark of approval for a protocol. Thus
> we should limit BIP assignment to the minimum possible: _extremely_ widespread
> standards used by the _entire_ Bitcoin community, for the core mission of
> Bitcoin.
>

This would eliminate most wallet-related protocols e.g. BIP69 (sorted
keys), ypubs, zpubs, etc. I don't particularly like any of those but if
they can't be BIPs then they'd need to find another spec repository
where they wouldn't be lost and where updates could be tracked.

The SLIP repo could serve this purpose, and I think e.g. SLIP39 is not a BIP
in part because of perceived friction and exclusivity of the BIPs repo.
But I'm not thrilled with this situation.

In fact, I would prefer that OpenTimestamps were a BIP :).

> It's notable that Lightning is _not_ standardized via the BIP process. I think
> that's a good thing. While it's arguably of wide enough use to warrent BIPs,
> Lightning doesn't need the approval of Core maintainers, and using their
> separate BOLT process makes that clear.
> 

Well, LN is a bit special because it's so big that it can have its own
spec repo which is actively maintained and used.

While it's technically true that BIPs need "approval of Core maintainers" 
to be merged, the text of BIP2 suggests that this approval should be a
functionary role and be pretty-much automatic. And not require the BIP
be relevant or interesting or desireable to Core developers.


-- 
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] Ordinals BIP PR

[Andrew Poelstra via bitcoin-dev]

On Fri, Oct 20, 2023 at 10:38:01PM -0700, Casey Rodarmor via bitcoin-dev wrote:
>
> 
> 
> There has been much misunderstanding of the nature of the BIP process.
> BIPS, in particular informational BIPs, are a form of technical
> documentation, and their acceptance does not indicate that they will be
> included in any implementation, including Bitcoin Core, nor that they they
> have consensus among the community.
> 
> Preexisting BIPs include hard-fork block size increases, hard-fork
> proof-of-work changes, colored coin voting protocols, rejected soft fork
> proposals, encouragement of address reuse, and drivechain.
>
> 
>

I agree and I think it sets a bad precedent to be evaluating BIPs based
on the merits of their implementation (vs their specification) or their
consequences for the network. Actual consensus is much bigger than the
BIPs repo, so this accomplishes little beyond making the BIPs repo itself
hard to interact with.

In the worst case it may cause people to interpret BIP numbers as
indicating that proposals are "blessed" by some particular influential
set of people, which can only cause problems.

-- 
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] Proposed BIP for OP_CAT

[Andrew Poelstra via bitcoin-dev]

On Mon, Oct 23, 2023 at 12:43:10PM +1030, Rusty Russell via bitcoin-dev wrote:
> Ethan Heilman via bitcoin-dev  writes:
> > Hi everyone,
> >
> > We've posted a draft BIP to propose enabling OP_CAT as Tapscript opcode.
> > https://github.com/EthanHeilman/op_cat_draft/blob/main/cat.mediawiki
> 
> This is really nice to see!
> 
> AFAICT you don't define the order of concatenation, except in the
> implementation[1].  I think if A is top of stack, we get BA, not AB?
> 
> 520 feels quite small for script templates (mainly because OP_CAT itself
> makes Script more interesting!).  For example, using OP_TXHASH and
> OP_CAT to enforce that two input amounts are equal to one output amount
> takes about 250 bytes of Script[2] :(
> 
> So I have to ask:
> 
> 1. Do other uses feel like 520 is too limiting?

In my view, 520 feels limiting provided that we lack rolling sha2
opcodes. If we had those, then arguably 65 bytes is enough. Without
them, I'm not sure that any value is "enough". For CHECKSIGFROMSTACK
emulation purposes ideally we'd want the ability to construct a full
transaction on the stack, which in principle would necessitate a 4M
limit.

> 2. Was there a concrete rationale for maintaining 520 bytes?  10k is the 
> current
>script limit, can we get closer to that? :)

But as others have said, 520 bytes is the existing stack element limit
and minimizing changes seems like a good strategy to get consensus. (On
the other hand, it's been a few days without any opposition so maybe we
should be more agressive :)).

> 3. Should we restrict elsewhere instead?  After all, OP_CAT doesn't
>change total stack size, which is arguably the real limit?
> 

Interesting thought. Right now the stack size is limited to 1000
elements of 520 bytes each, which theoretically means a limit of 520k.
Bitcoin Core doesn't explicitly count the "total stack size" in the
sense that you're suggesting; it just enforces these two limits
separately.

I think trying to add a "total stack size limit" (which would have to
live alongside the two existing limits; we can't replace them without
a whole new Tapscript version) would add a fair bit of accounting
complextiy and wind up touching almost every other opcode...probably
not worth the added consensus logic.

> Of course, we can increase this limit in future tapscript versions, too,
> so it's not completely set in stone.
> 

-- 
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] Proposed BIP for OP_CAT

[Andrew Poelstra via bitcoin-dev]

On Sat, Oct 21, 2023 at 01:08:03AM -0400, Ethan Heilman via bitcoin-dev wrote:
> Hi everyone,
> 
> We've posted a draft BIP to propose enabling OP_CAT as Tapscript opcode.
> https://github.com/EthanHeilman/op_cat_draft/blob/main/cat.mediawiki
> 
> OP_CAT was available in early versions of Bitcoin. It was disabled as
> it allowed the construction of a script whose evaluation could create
> stack elements exponential in the size of the script. This is no
> longer an issue in the current age as tapscript enforces a maximum
> stack element size of 520 Bytes.
>

Thanks, Ethan! This is really great, thank you for pushing forward and
writing up the BIP text.

In addition to the usecases listed in the text, I think CAT would open
up a wide range of Bitcoin script research and let us test nontrivial
things, in perhaps inefficient ways, in real life, befoer proposing
dedicated opcodes. When spitballing about ways to do cool stuff with
Bitcoin Script, I'd say about 90% of the time it ends with "we could do
this if only we had CAT". And the remaining 10% usually don't need much
more.

As evidenced by the short text and short implementation code, CAT is
very simple but provides a ton of value. There is a temptation to try
to bundle other opcodes in with this (for example, rolling SHA256
opcodes to allow hashing more than 520 bytes of data) but I think:

* There is no logical end to the list of opcodes we'd like to add, so
  this will invite an interminable amount of bikeshedding.

* No single opcode comes close to the power of CAT (except super
  general-purpose opcodes like OP_ZKP_VERIFY :))

* Most everything is more controversial than we expect. You can find
  Matt's "consensus cleanup" BIP from a couple years ago which did 4
  small things and I think that all 4 got a bunch of pushback.

So I think we should stick with "just CAT" :).

-- 
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] Compressed Bitcoin Transactions

[Andrew Poelstra via bitcoin-dev]

Hi Fabian,

We did consider indexing all txos -- even, amusingly, by using ordinals --
but decided that the extra index requirements for the decompressor (which
otherwise just requires a bit of extra CPU cycles but nothing beyond a
normal Core node).

A while ago we looked into putting the whole UTXOset into a trie so that
we could do prefix lookups. I think we discarded this idea for the same
reason, and because it could lead to surprising behavior for users since
a compressed tx might get invalidated by some UTXO showing up whose
prefix is too close to one of its inputs. Where "prefix" likely means
some special-purpose hash of the prevout that users will never otherwise
encounter.

We were also a bit put off by the data structure complexity since the
UTXO set no longer fits in RAM so it takes nontrivial effort to
implement a new index :) plus it drops our chances of getting code into
Core by a very large factor.

We can swag what the space savings would be: there are 122MM utxos right
now, which is a bit under 2^27. So assuming a uniform distribution of
prefixes we'd need to specify 28 bits to identify a UTXO. To contrast,
to identify a blockheight we need 20 bits and then maybe 12 more bits to
specify a TXO within a block. Plus whatever varint overhead we have.
(I've been working on this project but busy with family stuff and don't
remember exactly where we landed on the varints for this. I think we
agreed that there was room for improvement but didn't want to hold up
posting the rest of the concept because of it.)


The TL;DR is that we probably save a little less than a byte per input,
on average, which is not trivial but probably not worth the decreased
UX and greatly increased implementation complexity.


Best
Andrew



On Fri, Sep 01, 2023 at 10:24:54AM +, Fabian via bitcoin-dev wrote:
> Hi Tom,
> 
> without having gone into the details yet, thanks for the great effort you 
> have put into this research and implementation already!
> 
> > The bulk of our size savings come from replacing the prevout of each input 
> > by a block height and index.
> 
> Have you also considered using just an index from a sorted UTXO set instead? 
> The potential additional space saving might be minor but this would make the 
> scheme compatible with pruning. I had this on my list as a future research 
> topic but didn't get around to it yet.
> 
> Thanks,
> Fabian
> --- Original Message ---
> On Thursday, August 31st, 2023 at 11:30 PM, Tom Briar via bitcoin-dev 
>  wrote:
> 
> > Hey everyone,
> >
> > I've been working on a way to compress bitcoin transactions for 
> > transmission throughsteganography, satellite broadcasting,
> > and other low bandwidth channels with high CPU availability on 
> > decompression.
> >
> > [compressed_transactions.md](https://github.com/TomBriar/bitcoin/blob/2023-05--tx-compression/doc/compressed_transactions.md)
> >
> > In the document I describe a compression schema that's tailored for the 
> > most common transactions single parties are likely to make.
> > In every case it falls back such that no transaction will become malformed 
> > or corrupted.
> > Here's a PR for implementing this schema.
> >
> > [2023 05 tx compression](https://github.com/TomBriar/bitcoin/pull/3)
> > Thanks-
> > Tom.

> ___
> 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



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] Compressed Bitcoin Transactions

[Andrew Poelstra via bitcoin-dev]

On Thu, Aug 31, 2023 at 09:30:16PM +, Tom Briar via bitcoin-dev wrote:
> Hey everyone,
> 
> I've been working on a way to compress bitcoin transactions for transmission 
> throughsteganography, satellite broadcasting,
> and other low bandwidth channels with high CPU availability on decompression.
> 
> [compressed_transactions.md](https://github.com/TomBriar/bitcoin/blob/2023-05--tx-compression/doc/compressed_transactions.md)
> 
> In the document I describe a compression schema that's tailored for the most 
> common transactions single parties are likely to make.
> In every case it falls back such that no transaction will become malformed or 
> corrupted.
> Here's a PR for implementing this schema.
> 
> [2023 05 tx compression](https://github.com/TomBriar/bitcoin/pull/3)

Hey Tom,


Thank you for posting this. Could you put together a chart with some
size numbers so we can get a picture of how strong this compression is?

I understand that because this is targeted at stego/satellite
applications where the user is expected to "shape" their transaction,
that you won't get great numbers if you just look at the historical
chain or try to analyze "average" transactions. But it would be great to
post a chart with uncompressed/compressed sizes for "optimum"
transactions. At the very least, a 2-in-2-out wpkh transaction, and a
2-in-2-out Taproot transaction.

Since the scheme includes explicit support for p2sh-wpkh and p2pkh it
would also be great to see numbers for those, though they're less common
and less interesting.


Cheers
Andrew



-- 
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] segwit naming ambiguity

[Andrew Poelstra via bitcoin-dev]

On Fri, Aug 11, 2023 at 02:45:57PM +1000, Tobin Harding via bitcoin-dev wrote:
> Question for OG bitcoin API designers please.
> 
> If you were to see the following function
> 
> `is_segwit()`
> 
> would you assume it returns `true` or `false` for a p2tr transaction?
> 
> 
> Currently we (rust-bitcoin) are being liberal with the use of `v0` but
> its a pretty ugly. Is there an official, or widely used, name for segwit v0?
>

As others have said, I think `is_segwit` should match all segwit
versions. Pavol also sorta answered your "widely used name" question
though he didn't draw attention to it -- segwit v0 outputs are called
"p2wsh" or "p2wpkh".

But I don't know any term that covers "p2wsh or p2wpkh but not p2tr".
Other than "segwit_v0", which we are currently using, and which I agree
is a bit of a mouthful.


-- 
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] Blinded 2-party Musig2

[Andrew Poelstra via bitcoin-dev]

On Wed, Jul 26, 2023 at 12:09:41AM -0400, Erik Aronesty via bitcoin-dev wrote:
> personally, i think *any* time a public key is transmitted, it should come
> with a "proof of secret key".   it should be baked-in to low level
> protocols so that people don't accidentally create vulns.  alt discussion
> link:  https://gist.github.com/RubenSomsen/be7a4760dd4596d06963d67baf140406
>

POSK is not a panacea. For example, if you were to try to eliminate
rogue key attacks in MuSig by using POSK rather than by rerandomizing
the keys, the last person to contribute a key could add a Taproot
commitment to their key, thereby modifying the final key to have a
Taproot spending path that other participants don't know about. If they
did this, they'd have no problem producing a POSK since Taproot
commitments don't affect knowledge of the secret key.

POSKs are also logistically difficult to produce in many contexts. They
essentially require an interactive challege-response (otherwise somebody
could just copy a POSK from some other source), meaning that all
participants need to be online and have secret key access at key setup
time.

In some contexts maybe it's sufficient to have a static POSK. Aside from
the complexity of determining this, you then need a key serialization
format that includes the POSK. There are standard key formats for all
widely used EC keys but none have a facility for this. If you are trying
to use already-published keys that do not have a POSK attached, you are
out of luck.

If your protocol requires POSKs to be provably published, you also run
into difficulties because they don't make sense to embed on-chain (since
blockchain validators don't care about them, and they're twice as big as
the keys themselves) so you need to establish some other publication
medium.

If you want to support nested multisignatures, you need to jointly
produce POSKs, which requires its own protocol complexity.


The MuSig and MuSig2 papers say essentially the same thing as the above;
it's why we put so much effort into developing a scheme which was
provably secure in the plain public key model, which means that POSKs
are superfluous and you don't need to deal with all these logistical
hurdles.


-- 
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] Seeking concept ACKs for transaction terminology BIP

[Andrew Poelstra via bitcoin-dev]

On Wed, Apr 05, 2023 at 02:54:15PM -0400, Murch via bitcoin-dev wrote:
> Hey everyone,
> 
> Over the years, I have participated in a few conversations about various
> aspects of transactions. Often a chunk of the conversation is spent on
> establishing a shared vocabulary. There are many competing terms—e.g. I can
> think of at least three additional terms that refer to `scriptPubKey`.
> 
> I’ve drafted an informational BIP that proposes terminology for various
> components and aspects of transactions. As some established terms are
> already contradictory, the proposal does not aim for a perfectly consistent
> selection of terms, but rather just to establish a shared vocabulary to
> avoid confusion.
> 
> Draft: https://github.com/Xekyo/bips/pull/1
> 
> Please let me know whether you’d be interested in the creation of such a
> BIP.
>

I would be interested in such a BIP existing.

I will leave to others the hard work of bikeshedding every single term.


Cheers


-- 
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] Codex32

[Andrew Poelstra via bitcoin-dev]

On Wed, Feb 15, 2023 at 09:16:02PM -0500, Russell O'Connor via bitcoin-dev 
wrote:
> I've been asked by Dr. Curr and Professor Snead to forward this message to
> this mailing list, as it may be of general interest to Bitcoin users.
>
> 
>

I have opened a PR to the BIPs repo for this scheme: 
https://github.com/bitcoin/bips/pull/1425

Thanks very much to Pavol Rusnak, David Harding, and Christopher Allen
for their comments on this list. We've updated the draft text to try to
address your concerns. In particular:

  * Added more text to "Motivation" distinguishing the scheme from SLIP-39
  * Added more details to "Rationale"  about error correction capabilities
of the code, and to explain that the code does not defend against
malicious errors
  * Added a note to use uppercase for QR codes
  * Rearranged and clarified the "creating shares" instructions
  * Added text about hand-computation, in particular hand-computation
of share verification, to "Motivation".

If any of you would like to be listed under Acknowledgements, please let
me know here or on the PR.


Cheers
Andrew


-- 
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] Codex32

[Andrew Poelstra via bitcoin-dev]

On Sun, Feb 19, 2023 at 10:13:33AM -1000, David A. Harding wrote:
> On 2023-02-16 03:49, Andrew Poelstra via bitcoin-dev wrote:
> > the draft lists several benefits over SLIP-0039.
> 
> The only benefit over SLIP39 that I see explicitly mentioned in the
> draft BIP is "simple enough for hand computation".  In the FAQ[1] on the
> project's website, I see some additional reasons:
>

Oh, you're right! I think we removed this text in one of our revisions.
I'll see if it makes sense to put it back.

> | This scheme is essentially the same as SLIP39, with the following
> differences:
> |
> | - The checksum is longer, slightly stronger, and designed to be
> |   computable by hand.
> |
> | - Our encoding is more compact, giving us room for a bit of more
> |   metadata, which is also designed to be readable by hand.
> |
> | - Unlike SLIP39, we do not support passphrases or hardening of any
> |   form.
> |
> | - Unlike SLIP39, we have no hardware wallet support. But we hope that
> |   will change!
> 

These are roughly the benefits -- a more compact encoding which is
always a fixed width. We also list "not supporting features such as
passphrases" as a benefit, for users who don't need/want this.

> 
> 
> When I first saw the post about this, it was unclear to me that it was a
> serious project, but I've become increasingly interested as I researched
> it.  I'm not personally that interested in generating entropy from dice
> or encoding shares by hand---it's already imperative that I acquire a
> trustworthy computer and load it with trustworthy software in order to
> use my seed securely, so I might as well have it generate my seeds and my
> recovery codes for me.
>

Yes, we've been a bit coy about how serious this project is, because on
its face it's such a silly thing. But for my part, I've been using it
for real coins for over a year and I consider it to be serious.

> What really did catch my attention, but which was kind of buried in the
> project documentation, is the ability to verify the integrity of each
> share independently without using a computer.  For example, if I store a
> share with some relative who lives thousands of kilometers away, I'll be
> able to take that share out of its tamper-evident bag on my annual
> holiday visit, verify that I can still read it accurately by validating
> its checksum, and put it into a new bag for another year.  For this
> procedure, I don't need to bring copies of any of my other shares,
> allowing them (and my seed) to stay safe.
> 

This is good feedback. I strongly agree that this is the big selling
point for this -- that you can vet shares/seeds which *aren't* being
actively used, without exposing them to the sorts of threats associated
with active use.

We should make this more prominent in the BIP motivation.

> 
> I do have one question after watching an excellent video[2] about the
> motivation for this system.  In the video, one of the threat models
> described is a disarrangement of the words in a metal backup system.
> The implication seems to be that this would be an accidental
> disarrangement, which obviously the Codex32 checksum would catch during
> periodic offline verification.  But what about deliberate modification
> of a recovery code?  For example, Bob doesn't keep his seed loaded on
> any computer; it only exists in Codex32 shares which Bob plans to
> combine together in 20 years when he retires, although he makes regular
> deposits to the pubkeys derived from the seed's master xpub.  Mallory is
> able to obtain access to Bob's shares, allowing her to immediately steal
> his current funds---but also allowing her to replace them with
> similar-looking
> shares with the same metadata and valid checksums so that Bob
> continues making deposits to the wallet.
> 
> I'm curious about whether there's a way to prevent this attack without
> otherwise compromising the properties of the code?  For example, some
> extra data that Bob can carry around (or memorize) for verifying the
> shares haven't changed, but which is not otherwise needed for recovery
> (so there's no problem if it's lost).
>

Unfortunately not, as near as I can tell ... one way to think of this is
that Alice can flip a lot of random tiles then "error correct" it to get
a new valid, but incorrect, seed. So as long as we support error
correction it'll be possible to wreck seeds in this way.

It's actually even worse than this ... as long as there's a clearly
defined "checksum" at the end of a share, Alice will be able to mangele
tiles and then just re-compute the checksum at the end.

So what we really need to prevent this is something like a MAC: where
Bob has a secret value which gets input into the checksum somehow, which
Alice can't create valid chec

Re: [bitcoin-dev] Testing censorship resistance of bitcoin p2p network

[Andrew Poelstra via bitcoin-dev]

On Sat, Feb 18, 2023 at 02:03:15AM +0200, Peter Todd wrote:
> On February 18, 2023 1:35:34 AM GMT+02:00, Andrew Poelstra via bitcoin-dev 
> >You could try statically analyze `` to determine whether the
> >IF branch could ever be taken. For example there is no path through
> >the "inscription script" that would result in all the crap being dropped
> >by the end of the script, violating the CLEANSTACK rule.
> >
> >This sort of filtering, assuming it could be reliably and efficiently
> >done, would at least force inscription scripts to be "plausible", and
> >would greatly increase their space cost by e.g. requiring OP_DROP to be
> >added somewhere hundreds of times.
> 
> "greatly increase their space cost"?
> 
> Tell me, what is the actual % increase to adding OP_DROPs like you propose?
>

By standardness rules (where you can have up to 80-byte pushes), a
little over 1%. By consensus (520-byte pushes) less than 0.2%.

Perhaps "greatly increase" is a stretch :) but if the fee market is
functioning and we're talking about large amounts of data, it's not
trivial either.

-- 
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] Testing censorship resistance of bitcoin p2p network

[Andrew Poelstra via bitcoin-dev]

On Fri, Feb 17, 2023 at 11:35:34PM +, Andrew Poelstra via bitcoin-dev wrote:
> 
> If you ban any of these specific script fragments then spammers will
> just use `IF  ENDIF` and provide the `FALSE` as a zero push.
> And banning *this* would ban legitimate use cases.
>

I realize this is confusingly worded. I mean, they'd provide the `FALSE`
as a separate witness element rather than being part of the witnessScript.




-- 
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] Testing censorship resistance of bitcoin p2p network

[Andrew Poelstra via bitcoin-dev]

On Fri, Feb 17, 2023 at 03:56:31PM +0100, vjudeu via bitcoin-dev wrote:
> > [0]: https://gist.github.com/luke-jr/4c022839584020444915c84bdd825831
> 
> I wonder how far should that rule go: SCRIPT_ERR_DISCOURAGE_UPGRADABLE_NOPS. 
> Because "OP_FALSE OP_IF  OP_ENDIF" is effectively the same as 
> "OP_NOP", and putting NOPs in many places is considered non-standard. The 
> same is true for "OP_TRUE OP_NOTIF  OP_ENDIF", and also there are 
> many variants, where someone could use "OP_FALSE OP_NOT" instead of 
> "OP_TRUE", or check if "2+2==4" by using "OP_2 OP_2 OP_ADD OP_4 OP_EQUAL" 
> (instead of putting "OP_TRUE").
>

If you ban any of these specific script fragments then spammers will
just use `IF  ENDIF` and provide the `FALSE` as a zero push.
And banning *this* would ban legitimate use cases.

You could try statically analyze `` to determine whether the
IF branch could ever be taken. For example there is no path through
the "inscription script" that would result in all the crap being dropped
by the end of the script, violating the CLEANSTACK rule.

This sort of filtering, assuming it could be reliably and efficiently
done, would at least force inscription scripts to be "plausible", and
would greatly increase their space cost by e.g. requiring OP_DROP to be
added somewhere hundreds of times.

-- 
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] Codex32

[Andrew Poelstra via bitcoin-dev]

On Thu, Feb 16, 2023 at 12:50:12PM +0100, Pavol Rusnak via bitcoin-dev wrote:
> Hi!
> 
> The BIP states that its only advantage over SLIP-0039, which has been used
> in production for nearly three years (in at at least 3 SW/HW wallet
> implementations), is that it aims to be simple enough for hand computation.
> However, the BIP also indicates that "details of hand computation are
> outside the scope of this standard, and implementers do not need to be
> concerned with this possibility." Therefore, I am curious about how
> significant this advantage over SLIP-0039 really is. If hand computation is
> not straightforward and there are no other substantial advantages over
> SLIP-0039, I cannot help but feel that this BIP is simply a result of
> not-invented-here syndrome, but please correct me if I am wrong.
>

In my view, the hand computation is actually the main benefit of this
scheme. The process *is* straightforward, but tedious enough (and the
security benefits obscure enough, though they really shouldn't be...
"computers are opaque and untrustworthy" should be a common sentiment)
that it's hard to expect more than a small absolute number of users to
actually do it.

But for the purpose of the *standard*, what is important is that it is
possible to implement and use this within a normal hww workflow. This is
important for hand-computing users who know that their coins will not
die with them (since the 'standard' has fallen into obscurity), and
important for "normal" users who have the option to seamlessly switch
over to hand computation as the BTC price goes up or the world becomes
scarier.

For what it's worth, the draft lists several benefits over SLIP-0039.
I agree that none of them are particularly strong [1], and even together
they probably wouldn't meet the threshold to take the time to write a
standard, but I assure you the motivation was not NIH :).

> Keep in mind that the encoded shares in SLIP-0039 consist of exactly 200 or
> 330 bits, both of which are divisible by 5. This makes it straightforward
> to encode them as Bech32 strings.
> 

This is true! And very convenient for people who may want to simply
"layer on" the codex32 checksum/splitting logic onto their SLIP39 words.
They can use a lookup table to do the conversion, spend years or
whataever doing hand-computation on them, and then use a lookup table
to go back.


[1] One listed reason is that "a SLIP is not a BIP". I have heard people
speculate that this is one reason SLIP-0039 is not nearly as
widespread as BIP-0039, even though it is objectively a far better
standard. I'm unsure whether I believe this, but "there is no other
BIP" does seem like a good reason for BIP-0039's continued
dominance.

At the very least, it means that on BIP-0039 itself we have nothing
that we could say "supercedes" or "is recommended instead of" the
BIP. See https://github.com/bitcoin/bips/pull/1413

So it's something of an aside, but I think it would probably be good
for the ecosystem (though maybe bad for this BIP's prospects :)) if
you would request a BIP number for SLIP-0039.


-- 
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] Unenforceable fee obligations in multiparty protocols with Taproot inputs

[Andrew Poelstra via bitcoin-dev]

On Wed, Feb 08, 2023 at 09:34:57AM +, Michael Folkson wrote:
> Hi Andrew
> 
> > There is a bug in Taproot that allows the same Tapleaf to be repeated 
> > multiple times in the same Taproot, potentially at different Taplevels 
> > incurring different Tapfee rates.
> >> The countermeasure is that you should always know the entire Taptree when 
> >> interacting with someone's Tapspend.
> 
> I wouldn't say it is a "bug" unless there is a remedy for the bug that wasn't 
> (and retrospectively should have been) included in the Taproot design. In 
> retrospect and assuming you could redesign the Taproot consensus rules again 
> today would you prevent spending from a valid P2TR address if a repeated 
> Tapleaf hash was used to prove that a spending path was embedded in a Taproot 
> tree? That's the only thing I can think of to attempt to remedy this "bug" 
> and it would only be a partial protection as proving a spending path exists 
> within a Taproot tree only requires a subset of the Tapleaf hashes.
> 
> I only point this out because there seems to be a push to find "bugs" and 
> "accidental blowups" in the Taproot design currently. No problem with this if 
> there are any, they should definitely be highlighted and discussed if they do 
> exist. The nearest to a possible inferior design decision thus far that I'm 
> aware of is x-only pubkeys in BIP340 [0].
> 

I'm actually not certain what Russell's referring to, but if it's indeed
possible to construct TapTrees where the "same" leafhash appears multiple
times at different heights, that's something unintended and which we
could've fixed by changing the Merkle structure. I don't even think
there would've been an efficiency tradeoff.

So I think it's totally reasonable to call such a thing a "bug".

-- 
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] Unenforceable fee obligations in multiparty protocols with Taproot inputs

[Andrew Poelstra via bitcoin-dev]

Some people highlighted some minor problems with my last email:

On Tue, Feb 07, 2023 at 01:46:22PM +, Andrew Poelstra via bitcoin-dev wrote:
> 
>  
> 
> [1] https://bitcoin.sipa.be/miniscript/
> [2] In Taproot, if you want to prevent signatures migrating to another
> branch or within a branch, you can use the CODESEPARATOR opcode
> which was redisegned in Taproot for exactly this purpose... we
> really did about witness malleation in its design!

In Taproot the tapleaf hash is always covered by the signature (though
not in some ANYONECANPAY proposals) so you can never migrate signatures
between tapbranches.

I had thought this was the case, but then I re-confused myself by
reading BIP 341  which has much of the sighash specified, but not
all of it! The tapleaf hash is added in BIP 342.

> 
> If you want to prevent signatures from moving around *within* a
> branch,
>

And this sentence I just meant to delete :)


-- 
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] Unenforceable fee obligations in multiparty protocols with Taproot inputs

[Andrew Poelstra via bitcoin-dev]

On Tue, Feb 07, 2023 at 04:49:28AM +0200, Yuval Kogman via bitcoin-dev wrote:
> 
> Since Taproot (more generally any kind of MAST) spends have variable size 
> which
> depends on the path being used, the last such input to be signed in a 
> multiparty
> transaction can always use a larger than estimated signature to unfairly 
> extract
> a fee contribution from the other parties to the transaction (keeping the
> absolute fees the same and reducing the feerate for the transaction).
>

Using Miniscript [1] it is possible for all participants to determine
the maximum witness size of the tree, which can bound the size of this
attack. In fact, they can bound the size *given that their own signature
is used*, or subject to other whatever other conditions they would like,
and only sign under those conditions.

Furthermore, under Taproot individual signatures have a maximum size of
65 bytes; an "attacker" can reduce this to 64 by not including a sighash
flag, but he has one byte of play. (Pre-Taproot signatures could take up
to 73 bytes with significant room to reduce this by using crypto tricks
and/or grinding).

Peter Todd also suggests in this thread that the use of uncompressed
keys can cause "surprise" witness inflation, but (a) since segwit
uncompressed keys are also banned, so keys are a fixed 33 bytes (32 in
Taproot), and (b) we expect users of Miniscript to always know all the
keys used in a script that they're signing. Except perhaps in obscure
cases where, say, the "victim" is a somewhat passive countersigner of
a transaction, e.g. BitGo, ... in which case they're not the one putting
up fees or with an interest in the transaction going through.


With Miniscript, the problem is narrower:

* There is some more-expensive branch that could be taken without
  Alice's signature. In which case Alice is only signing at all to
  optimistically reduce the witness size... but she cannot assume
  that she is going to be successful!

  Notably, in this case Alice does not really have any interest in the
  coins, in the sense that they can move entirely without her consent,
  so it's hard to imagine that she has an interest in the transaction's
  speedy confirmation.

* There is some more-expensive branch that could be taken by moving
  Alice's signature. This is the case that you identify in the thread.

While the attack remains in both cases, fortunately Miniscript gives
Alice the tools to (a) determine which, if any, case applies to the
script under question, and (b) determine what the maximum witness size
might be, and just sign assuming that, treating any savings as "bonus".



[1] https://bitcoin.sipa.be/miniscript/
[2] In Taproot, if you want to prevent signatures migrating to another
branch or within a branch, you can use the CODESEPARATOR opcode
which was redisegned in Taproot for exactly this purpose... we
really did about witness malleation in its design!

If you want to prevent signatures from moving around *within* a
branch,

-- 
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] Debate: 64 bytes in OP_RETURN VS taproot OP_FALSE OP_IF OP_PUSH

[Andrew Poelstra via bitcoin-dev]

On Sat, Feb 04, 2023 at 07:11:35PM -0500, Russell O'Connor via bitcoin-dev 
wrote:
> Since bytes in the witness are cheaper than bytes in the script pubkey,
> there is a crossover point in data size where it will simply be cheaper to
> use witness data.  Where that crossover point is depends on the finer
> details of the overhead of the two methods, but you could make some
> reasonable assumptions.  Such a calculation could form the basis of a
> reasonable OP_RETURN proposal.  I don't know if it would be persuasive, but
> it would at least be coherent.
>

I agree with Peter that, given that users have found ways to store arbitrary
amounts of data on-chain if they really want, we might as well just make
OP_RETURN a free-for-all.

-- 
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] Debate: 64 bytes in OP_RETURN VS taproot OP_FALSE OP_IF OP_PUSH

[Andrew Poelstra via bitcoin-dev]

On Tue, Jan 31, 2023 at 09:07:16PM -0500, Peter Todd via bitcoin-dev wrote:
> 
> 
> On January 31, 2023 7:46:32 PM EST, Christopher Allen via bitcoin-dev 
>  wrote:
> >All other things being equal, which is better if you need to place a
> >64-bytes into the Bitcoin blockchain? A traditional OP_RETURN or a spent
> >taproot transaction such as:
> >
> >OP_FALSE
> >OP_IF
> >OP_PUSH my64bytes
> >OP_ENDIF
> 
> What's wrong with OpPush  OpDrop?
>

This is a technical nit, but the reason is that  is limited to 520
bytes (and I believe, 80 bytes by standardness in Taproot), so if you
are pushing a ton of data and need multiple pushes, it's more efficient
to use FALSE IF ... ENDIF since you avoid the repeated DROPs.

-- 
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] Ordinal Inscription Size Limits

[Andrew Poelstra via bitcoin-dev]

On Fri, Jan 27, 2023 at 09:44:10AM -0300, Robert Dickinson via bitcoin-dev 
wrote:
> I'm curious what opinions exist and what actions might be taken by core
> developers regarding storing unlimited amounts of NFT (or other?) content
> as witness data (https://docs.ordinals.com/inscriptions.html). The ordinal
> scheme is elegant and genius IMHO, but when I think about the future disk
> use of all unpruned nodes, I question whether unlimited storage is wise to
> allow for such use cases. Wouldn't it be better to find a way to impose a
> size limit similar to OP_RETURN for such inscriptions?
> 
> I think it would be useful to link a sat to a deed or other legal construct
> for proof of ownership in the real world, so that real property can be
> transferred on the blockchain using ordinals, but storing the property
> itself on the blockchain seems nonsensical to me.

Unfortunately, as near as I can tell there is no sensible way to prevent
people from storing arbitrary data in witnesses without incentivizing
even worse behavior and/or breaking legitimate use cases.

If we ban "useless data" then it would be easy for would-be data storers
to instead embed their data inside "useful" data such as dummy
signatures or public keys. Doing so would incur a ~2x cost to them, but
if 2x is enough to disincentivize storage, then there's no need to have
this discussion because they will will be forced to stop due to fee
market competition anyway. (And if not, it means there is little demand
for Bitcoin blockspace, so what's the problem with paying miners to fill
it with data that validators don't even need to perform real computation
on?).

But if we were to ban "useful" data, for example, saying that a witness
can't have more than 20 signatures in it, then we are into the same
problem we had pre-Taproot: that it is effectively impossible construct
signing policies in a general and composeable way, because any software
that does so will need to account for multiple independent limits. We
deliberately replaced such limits with "you need to pay 50 weight for
each signature" to makes this sort of analysis tractable.

There's a reasonable argument that this sort of data is toxic to the
network, since even though "the market is willing to bear" the price of
scares blockspace, if people were storing NFTs and other crap on the
chain, then the Bitcoin fee market would become entangled with random
pump markets, undermining legitimate use cases and potentially
preventing new technology like LN from gaining a strong foothold. But
from a technical point of view, I don't see any principled way to stop
this.



-- 
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] Trustless Address Server – Outsourcing handing out addresses to prevent address reuse

[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

[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

[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?

[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

[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

[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)

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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?

[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?

[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?

[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

[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

[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

[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?

[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

[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

[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