[bitcoin-dev] libsecp256k1 v0.3.1 released

[Pieter Wuille via bitcoin-dev]

Hello,

Today we'd like to announce the release of version 0.3.1 of libsecp256k1:

  https://github.com/bitcoin-core/secp256k1/releases/tag/v0.3.1

This is a bugfix release after 0.3.0 (which was not announced on this list). 
For the full release notes of 0.3.0 and 0.3.1 see:

  https://github.com/bitcoin-core/secp256k1/blob/master/CHANGELOG.md

but the impetus for this release is the discovery that Clang 14 and later 
became smart enough to optimize out a specific timing side-channel protection 
mechanism in the code that could leave applications vulnerable to a 
side-channel attack. This has been fixed in 0.3.1.

We strongly recommend any users of the library to upgrade if their code may end 
up being compiled with Clang 14+. Bitcoin Core release binaries are not 
affected.

-- 
Pieter


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

Re: [bitcoin-dev] Refreshed BIP324

[Pieter Wuille via bitcoin-dev]

On Sunday, February 19th, 2023 at 6:56 PM, Anthony Towns  
wrote:

> On Fri, Feb 17, 2023 at 10:13:05PM +0000, Pieter Wuille via bitcoin-dev wrote:
> 
> > > I think it's probably less complex to close some of the doors?
> > > 2) are short ids available/meaningful to send prior to VERACK being
> > > completed?
> > > Ah, I hadn't considered this nuance. If we don't care about them being 
> > > available before VERACK negotiation, then it may be possible to introduce 
> > > a way to negotiate a different short id mapping table without needing a 
> > > mechanism for re-negotiating.
> 
> I think you still need/want two negotiation steps -- once to tell each
> other what tables you know about, once to choose a mutually recognised
> table and specify any additions.

Right, I wasn't talking about how many steps/messages the negotiation takes. I 
just meant that if all negotiation of the mapping table happens just once 
(before VERACK) and that negotiation itself happens without use of short 
commands, then there is no need for re-negotiating short commands after they 
are already in use. Nothing concrete, but I can imagine that that may simplify 
some implementations.

Cheers,

-- 
Pieter

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

Re: [bitcoin-dev] Refreshed BIP324

[Pieter Wuille via bitcoin-dev]

On Friday, February 17th, 2023 at 10:51 AM, Anthony Towns via bitcoin-dev 
 wrote:

> I think it's probably less complex to close some of the doors?
 
> 2) are short ids available/meaningful to send prior to VERACK being
> completed?

Ah, I hadn't considered this nuance. If we don't care about them being 
available before VERACK negotiation, then it may be possible to introduce a way 
to negotiate a different short id mapping table without needing a mechanism for 
*re*-negotiating.

> Here's another approach:
> 
> idea: we use short ids to minimise bandwidth, and don't care about
> bandwidth for long ids
> 
> implementation:
> short id 0 is reserved for long commands. when received, we
> decode the first 12 bytes of the payload and treat them
> exactly the same as a v1 p2p message (trailing 0-bytes, etc)
> (if there's not 12 bytes of payload, it's just treated as an
> invalid command and dropped)
> 
> short ids 1-255 are available for use as aliases of particular
> long commands
> 
> (That's exactly compatible with p2p v1, and also avoids the temptation
> to try to choose short command names rather than descriptive ones -- the
> 0-padding to 12 bytes prevents you from saving any bandwidth that way;
> but that's what we have short ids for anyway)

I like this idea. It avoids the variable-length encoding question and related 
complexity entirely for things where we admittedly don't care about the 
bandwidth impact anyway.

It may also have another (rather weak) advantage, in that it may reduce how 
much information a passive observe may learn about application level features 
(sendheaders, sendaddrv2, ...) from the packet size sent (which would otherwise 
depend on command lengths), even when decoys are not in use, if no short 
commands are included for these messages.

> > - We remove 1 byte allocations for messages that are sent at most once per 
> > connection per direction
> 
> I think this leaves 32 commands that get short ids initially:
> 
> misc: ADDR, ADDRV2, BLOCK, FEEFILTER, GETBLOCKS, GETDATA, GETHEADERS,
> HEADERS, INV, NOTFOUND, PING, PONG, TX
> bip 35/37: FILTERADD, FILTERCLEAR, FILTERLOAD, MEMPOOL, MERKLEBLOCK
> bip 152: BLOCKTXN, CMPCTBLOCK, GETBLOCKTXN
> bip 157: CFCHECKPT, CFHEADERS, CFILTER, GETCFCHCKPT, GETCFHEADERS,
> GETCFILTERS
> bip 330: RECONCILDIFF, REQRECON, REQSKETCHEXT, SENDCMPCT, SKETCH

Sounds right.

> which drops:
> 
> VERSION, VERACK, GETADDR, SENDADDRV2, SENDHEADERS, SENDTXRCNCL,
> WTXIDRELAY

Indeed.

> compared to bip 324 currently.
> 
> I think the things missing from the current list (and not currently in
> use by bitcoin core) are:
> 
> bip 61: REJECT
> bip 331: GETPKGTXNS, PKGTXNS, ANCPKGINFO

Do you feel REJECT should be included?

> > - Optionally, in the implementation we can attempt to move the type id 
> > mapping to the p2p layer away from the transport layer. I suspect this 
> > could also be done after the implementation is merged but might be cleaner 
> > as the mapping is a p2p concern.
>
> I agree that's fine, though I expect that we'll probably want to do it
> not long after bip 331 is ready for merge (or some other p2p improvement
> comes along)...

I do prefer that as well; it feels like the transport layer shouldn't be aware 
of the different command names that exist, but this is very much just an 
implementation issue.

Perhaps a possibility is having the transport layer translate 
short-command-number-N to the 12-byte command "\x00\x00..." + byte(N), and hand 
that to the application layer, which could then do the mapping?

Cheers,

-- 
Pieter

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

Re: [bitcoin-dev] Refreshed BIP324

[Pieter Wuille via bitcoin-dev]

--- Original Message ---
On Friday, November 18th, 2022 at 3:24 AM, Anthony Towns  
wrote:

> > * etc
> > So this gives a uniform space which commands can be assigned from, and 
> > there is no strict need for thinking of the short-binary and 
> > long-alphabetic commands as distinct. In v2, some short ones would be 
> > treated as aliases for old long-alphabetic ones. But new commands could 
> > also just be introduced as short ones only (even in v1).
> 
> Isn't that optimising for the wrong thing? Aren't the goals we want:
> 
> 1) it should be easy to come up with a message identifier without
> accidently conflicting with someone else's proposal
> 
> 2) commonly used messages on the wire should have a short encoding
> in order to save bandwidth
> 
> Depending on how much the p2p protocol ossifies, which messages are
> "commonly used on the wire" might be expected to change; and picking an
> otherwise meaningless value from a set of 102 elements seems likely to
> produce conflicts...

Oh, yes. I meant this as an encoding scheme, not as a (replacement for) the 
negotiation/coordination mechanism. There could still be an initial assignment 
for 1-byte encodings, and/or an explicit mechanism to negotiate other 
assignment, and/or nothing at all for now.

I just thought it would be interesting to have a uniform encoding without 
explicit distinction between "short commands" and "long commands" at that layer.

But maybe none of this is worth it, as it's perhaps more complexity than the 
alternative, and the alternative already has a working implementation and 
written-up specification.

Cheers,

-- 
Pieter

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

[bitcoin-dev] libsecp256k1 version 0.2.0 released

[Pieter Wuille via bitcoin-dev]

Hi,

After not even 10 years of development, we'd like to announce the first tagged 
release of libsecp256k1, version 0.2.0:

    https://github.com/bitcoin-core/secp256k1/releases/tag/v0.2.0

For a long time, libsecp256k1's development only had a master branch, creating 
unclarity about API compatibility and stability. Going forward, we will be 
creating tagged releases when relevant improvements are merged, following a 
semantic versioning scheme. This is not yet a version 1.0.0 as there are some 
important improvements we'd like to make before that point. We do reserve the 
ability to introduce API breaks, but promise clear documentation of such 
changes.

We're skipping version 0.1.0 because this version number was set in our 
autotools build scripts for years, and does not uniquely identify a set of 
source files. We will not be creating binary releases, but will take expected 
ABI compatibility issues into account for release notes and versioning.

The release tag is signed with my PGP key: https://bitcoin.sipa.be/sipa.asc

Grab it while it's hot. We welcome suggestions for the release process going 
forward.

Cheers,

-- 
the libsecp256k1 maintainers

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

Re: [bitcoin-dev] Refreshed BIP324

[Pieter Wuille via bitcoin-dev]

Another idea...

On Thursday, November 10th, 2022 at 4:23 PM, Pieter Wuille via bitcoin-dev 
 wrote:

> On Thursday, November 3rd, 2022 at 1:53 PM, Murch wrote:
> 
> > From what I understand we'll have about 35 message types on the network
> > with the addition of BIP324. 256 possible IDs sounds like plenty room to
> > grow, but perhaps we can be a bit more conservative:
> > 
> > We could use the first bit to signal a 2-byte message ID. That allows us
> > to express 128 IDs with 1 byte, but if we need more, we get a total of
> > 2^15 IDs across 2 bytes.
> 
> Yeah, effectively treating the first 1 or 2 bytes as a simple variable
> length integer is a nice way of increasing the space at low cost.

The above would really result in having two separate variable-length encodings:
* First byte 1-12 to signify length of alphabetic command
* Otherwise first bit to signify length of short command

I think we can just merge the two and have a single variable-length command 
structure that can be used for both: command encodings are 1 to 12 bytes, each 
byte's top bit indicating whether another byte follows (the top bit of byte 11 
has no special meaning).

This means:
* Every alphabetic command of L characters becomes L bytes.
* 102 non-alphabetic 1-byte commands can be assigned.
* 15708 non-alphabetic 2-byte commands can be assigned.
* etc

So this gives a uniform space which commands can be assigned from, and there is 
no strict need for thinking of the short-binary and long-alphabetic commands as 
distinct. In v2, some short ones would be treated as aliases for old 
long-alphabetic ones. But new commands could also just be introduced as short 
ones only (even in v1).

WDYT?

Cheers,

-- 
Pieter




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

Re: [bitcoin-dev] Refreshed BIP324

[Pieter Wuille via bitcoin-dev]

Hi,

Thanks for the comments so far. I think these are all reasonable ideas.
Comments inline below.

On Thursday, November 3rd, 2022 at 1:53 PM, Murch wrote:

> From what I understand we'll have about 35 message types on the network
> with the addition of BIP324. 256 possible IDs sounds like plenty room to
> grow, but perhaps we can be a bit more conservative:
> 
> We could use the first bit to signal a 2-byte message ID. That allows us
> to express 128 IDs with 1 byte, but if we need more, we get a total of
> 2^15 IDs across 2 bytes.

Yeah, effectively treating the first 1 or 2 bytes as a simple variable
length integer is a nice way of increasing the space at low cost.

This also doesn't need to be decided now. The initial approach could just
be avoiding allocating bytes in the 128-255 range until the need for more
space arises. If and when that is the case, the choice could be to:
* Just continue treating the first byte as the command.
* Start treating the first upper bit as a sign that another command byte
  follows.
* Switch to some form of explicit signalling (option 3 is my earlier
  mail).

On Thursday, November 3rd, 2022 at 6:26 PM, Jonas Schnelli wrote:

> There would be an alternative to preserve more 1 byte IDs on the cost
> of a (much) smaller 2 byte ID space: Reserve the short ID 0xFF as an
> indication for a 2 bytes short ID (additional 256 short IDs with 2 bytes).

I don't think this is needed, because we arguably already have that! If the
first byte is 0x01, then 1 more command byte follows in the current BIP324
draft. That mechanism is designed for alphabetic 1-character commands, but
nothing prevents it from also being used for other things (by using a
non-alphabetic byte there).

> Maybe the BIP should state that only frequent sent messages should reserve
> a short ID, though, the BIP itself assigns short IDs to all(?) message
> types (including low frequent messages like SENDHEADERS).
> 
> Maybe exclude message types that expected to be only sent once from
> assigning a short ID?

I think that makes sense. Especially in combination with the idea avoiding
bytes with the upper bit set there is a bit more pressure on the 1-byte
space. Rarely-sent or at-most-once-sent commands don't really provide much
benefit. I'd suggest scrapping from the list:
* Version messages: version, verack
* Negotiation messages: sendaddrv2, sendheaders, sendcmpct, wtxidrelay
* Rarely-sent messages: mempool

I'm not sure to what extent filteradd/filterload/filterclear/merkleblock
are still actually used; perhaps they could be removed too?

On Monday, November 7th, 2022 at 10:20 PM, Anthony Towns wrote:

> I guess I think it would make sense to not start using a novel 1-byte
> message unless you've done something to introduce that message first;
> whether that's via approach (3) ("I'm going to use 0xE9 to mean pkgtxns")
> or via a multibyte feature support message ("I sent sendaddrv3 as a
> 10-byte message, that implies 0xA3 means addrv3 from now on").

That's fair, but I don't think it matters too much for allocation purposes;
protocol designs should still not assign overlapping values, unless the
protocols are known to never be used simultaneously?

Unless... the assignment works like "whenever the sendaddrv3 is sent, the
next available byte in range 48..127 gets allocated for addrv3". That means
no explicit mapping is needed, as long as the total number of messages from
simultaneously-active extensions isn't too large.

> I do still think it'd be better to recommend against reserving a byte for
> one-shot messages, and not do it for existing one-shot messages though.

Agree.

FWIW, if anyone was wondering about how much is actually saved by having
1-byte commands vs 12-byte commands, I've gathered statistics from two nodes
(one with many inbound connections, one only outbound) for two weeks. This is
obviously very dependent on network topology and local implementation choices,
but it may still give an idea:
* Outbound-only node:
  * Around 4.5% of sent bytes are bytes 2-12 of the command.
  * Sent 979.98 MiB in total.
* Outbound and inbound node:
  * Around 1.6% of sent bytes are bytes 2-12 of the command.
  * Sent 124.14 GiB in total.

Cheers,

-- 
Pieter

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

Re: [bitcoin-dev] Refreshed BIP324

[Pieter Wuille via bitcoin-dev]

Hi all,

On Saturday, October 8th, 2022 at 8:59 AM, Dhruv M  wrote:

> We have refreshed the proposal for BIP324, a new bitcoin P2P protocol
> featuring opportunistic encryption, a mild bandwidth reduction, and the
> ability
> to negotiate upgrades before exchanging application messages. We'd like
> to invite community members to review the BIP[1] and the related Bitcoin
> Core
> code[2].

One open question we have regarding BIP324's design is how to deal with the
coordination of assigning the message type IDs.

For context, the current BIP324 draft introduces a notion of 1-byte message
type IDs, which take the place of the 12-byte command strings (in a backward
compatible way; it's still possible to send full strings). This offers a
mild bandwidth reduction (3 bytes per message overall), especially since many
messages on the network are fairly small.

However, it obviously raises the question of how the mapping table between the
1-byte IDs and the commands they represent should be maintained:

1. The most straightforward solution is using the BIP process as-is: let BIP324
   introduce a fixed initial table, and future BIPs which introduce new
   messages can introduce new mapping entries for it. In theory, this is no
   worse than the current coordination difficulty about command strings, but
   in practice the risk of collisions due to competing proposals is of course
   significantly larger with 1-byte IDs vs. 12-byte strings.

2. An alternative approach is not using 1-byte IDs but slightly longer ones;
   for example 3-byte IDs, each consisting of a 2-byte BIP number and a 1-byte
   message index introduced by that BIP, at the cost of a smaller bandwidth
   improvement. This significantly reduces collision risks, but doesn't remove
   the coordination process concerns entirely (e.g. revisions changing what a
   BIP introduces need to be taken into account and probably still mean BIPs
   need to explicitly list which assignments they introduce).

3. Yet another possibility is not having a fixed table at all, and negotiate
   the mapping dynamically. E.g. either side could send a message at
   connection time with an explicit table of entries "when I send byte X, I
   mean command Y".

4. Lastly, the whole feature could just be dropped from BIP324 (sticking with
   command strings), and left for a follow-up (or independent) protocol
   improvement. Since arguably this is purely an application-layer concern and
   not a transport-layer one, it could even be added as an optional feature to
   the (pre-BIP324) protocol today. That would however very likely mean that
   BIP324 if adopted as-is isn't actually an (albeit small) bandwidth
   reduction compared to today, and forego a possibility to fix a fairly
   gratuitous inefficiency in the protocol from day one.

Our idea is to start out with approach (1), with a mapping table effectively
managed by the BIP process directly, but if and when collisions become a
concern (maybe due to many parallel proposals, maybe because the number of
messages just grows too big), switch to approach (3), possibly even
differentially (the sent mappings are just additions/overwrites of the
BIP-defined table mappings, rather than a full mapping).

That said, we're not all that convinced this is the best approach, and feel
this more a community/process question than a technical one, so it would be
good to see more opinions on the topic.

Cheers,

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

Re: [bitcoin-dev] [Opt-in full-RBF] Zero-conf apps in immediate danger

[Pieter Wuille via bitcoin-dev]

On Wednesday, October 12th, 2022 at 1:42 AM, Anthony Towns 
 wrote:

> On Tue, Oct 11, 2022 at 04:18:10PM +0000, Pieter Wuille via bitcoin-dev wrote:
> 
> > On Friday, October 7th, 2022 at 5:37 PM, Dario Sneidermanis via bitcoin-dev 
> > bitcoin-dev@lists.linuxfoundation.org wrote:
> > 
> > > Thanks for the fast answer! It seems I missed the link to the PR, sorry 
> > > for the
> > > confusion. I'm referring to the opt-in flag for full-RBF from #25353
> > > (https://github.com/bitcoin/bitcoin/pull/25353).
> > > It is not clear to me why you believe the merging of this particular pull 
> > > request poses an immediate risk to you.
> 
> 
> Did you see the rest of Dario's reply, bottom-posted after the quoted
> text? Namely:

Oh, my mail client for some reason chose to hide all that. Dario, I'm sorry for 
missing this; I see now that you were certainly aware of what the PR under 
consideration did.

Further comments inline.

> On Fri, Oct 07, 2022 at 06:37:38PM -0300, Dario Sneidermanis via

> > The question then is whether an opt-in flag for full-RBF will have enough
> > adoption to get us from 1 to 2. If it isn't, then #25353 won't meet its
> > objective of allowing nodes participating in multi-party funding protocols
> > to assume that they can rely on full-RBF. If it is, then zero-conf 
> > applications
> > will be at severe risk (per the logic in the initial email).

> 
> 
> That logic seems reasonably sound to me:
> 
> - if adding the option does nothing, then there's no point adding it,
> and no harm in restricting it to test nets only
> 
> - if adding the option does do something, then businesses using zero-conf
> need to react immediately, or will go from approximately zero risk of
> losing funds, to substantial risk
> 
> (I guess having the option today may allow you to manually switch your
> node over to supporting fullrbf in future when the majority of the network
> supports it, without needing to do an additional upgrade in the meantime;
> but that seems like a pretty weak benefit)

I certainly recognize that adding the flag is a likely step towards, over time, 
the full RBF policy becoming more widely adopted on the network. That is 
presumably the reason why people are in favor of having the flag, even default 
off - including me. I believe that policy's adoption is inevitable eventually, 
but the speed at which that is achieved is certainly a function of availability 
and adopted of software which provides the option.

That said, I think it's a bit of a jump to conclude that the only two options 
are that either the existence of the flag either has no effect at all, or poses 
an immediate threat to those relying on its absence. In my view, it is just 
what I said: a step towards getting full RBF on the network, by allowing 
experimentation and socializing the notion that developers believe it is time. 
So I have a hard time imagining how it would change anything *immediately* on 
the network at large (without things like default on and/or preferential 
peering, ...), but I still believe it's an important step.

Cheers,

-- 
Pieter

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

Re: [bitcoin-dev] [Opt-in full-RBF] Zero-conf apps in immediate danger

[Pieter Wuille via bitcoin-dev]

On Friday, October 7th, 2022 at 5:37 PM, Dario Sneidermanis via bitcoin-dev 
 wrote:


> Hello David,
> 
> Thanks for the fast answer! It seems I missed the link to the PR, sorry for 
> the
> confusion. I'm referring to the opt-in flag for full-RBF from #25353
> (https://github.com/bitcoin/bitcoin/pull/25353).

Hello Dario,

It is not clear to me why you believe the merging of this particular pull 
request poses an immediate risk to you.

As explained by others, it's only a configuration option that is default off, 
and the possibility of running rull-RBF policy nodes on the network have been 
trivial for anyone who wanted to for a long time on the network.

I don't want to sound dismissive of your concerns, but at this point I'm not 
convinced you're actually aware of what this PR does and doesn't do.

Cheers,

-- 
Pieter

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

Re: [bitcoin-dev] Zero-knowledge proofs e.g. Schnorr are incompatible with address signing without compromise

[Pieter Wuille via bitcoin-dev]

--- Original Message ---
On Thursday, July 28th, 2022 at 11:51 AM, Ali Sherief  
wrote:

> The way I understood the BIP, was that a user can do batch recovery or 
> single-key recovery. Can you explain how it is possible to recover a public 
> key from a single-key signature, because a few days earlier on the 
> BIP-notatether-messageverify thread I was told (I think it was achow) that 
> Schnorr doesn't allow for public key recovery.

No, BIP340, in its design decisions, had to choice to either support public key 
recovery, or support batch validation. We chose to support batch validation for 
a variety of reason. BIP340 does not in any way support key recovery.

> > > , just like BIP340).
> >
> > How so? Every taproot compatible wallet has a BIP340 implementation.
>
>
> I guess I made an assumption, since almost all of the wallets I have seen did 
> not have a sign message feature, not even for legacy addresses.

I'm not talking about sign message, I'm talking about BIP340 for the purpose of 
transaction signing, as it's the signature scheme used in BIP341/BIP342.

My point being: for any prospective message signing feature, if the wallet 
supports taproot signing, they inevitably already have code to produce BIP340 
signatures. If they don't support taproot signing, then message signing for it 
is irrelevant.

Cheers,

--
Pieter

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

Re: [bitcoin-dev] Zero-knowledge proofs e.g. Schnorr are incompatible with address signing without compromise

[Pieter Wuille via bitcoin-dev]

--- Original Message ---
On Thursday, July 28th, 2022 at 3:27 AM, Ali Sherief via bitcoin-dev 
 wrote:

> Essentially, zero-knowledge proofs such as Schnorr are not compatible with 
> address message signing - the public key cannot be retrieved from the address 
> or the signature, so the address does not actually prove the authenticity of 
> a Schnorr signature. That's why the public key is required as an input in the 
> first place.

Yes, that's an intentional design choice in BIP340, see note 5: 
https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#cite_ref-5-0. 
The choice is either batch verifiability or public key recovery.

I regret ever using public key recovery when introducing the old legacy message 
signing scheme. It should just have used script signatures like BIP322 proposes.

> In order to make it compatible with the address signing mechanism, the 
> zero-knowledge part would have to be sacrificed in my BIP, or else a 
> completely separate message signing format just for Taproot would be required

You can avoid relying on public key recovery, and include the public key + 
BIP340 signature in the encoded signature.

> (which, in my view, is redundant - there is already the draft BIP322 which 
> can verify anything and everything, but nobody is implementing that

I think it would be much better if people would cooperate to get BIP322 to move 
forward than to keep inventing other formats. It's the obvious solution in my 
opinion: not restricted to single-key policies, compatible with every script 
type, and trivially extensible to future schemes.

> , just like BIP340).

How so? Every taproot compatible wallet has a BIP340 implementation.

Cheers,

--
Pieter

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

Re: [bitcoin-dev] A suggestion to periodically destroy (or remove to secondary storage for Archiving reasons) dust, Non-standard UTXOs, and also detected burn

[Pieter Wuille via bitcoin-dev]

> Dear Bitcoin Developers,

> -When I contacted bitInfoCharts to divide the first interval of addresses, 
> they kindly did divided to 3 intervals. From here:
> https://bitinfocharts.com/top-100-richest-bitcoin-addresses.html
> -You can see that there are more than 3.1m addresses holding ≤ 0.01 BTC 
> (1000 Sat) with total value of 14.9BTC; an average of 473 Sat per address.

> -Therefore, a simple solution would be to follow the difficulty adjustment 
> idea and just delete all those

That would be a soft-fork, and arguably could be considered theft. While 
commonly (but non universally) implemented standardness rules may prevent 
spending them currently, there is no requirement that such a rule remain in 
place. Depending on how feerate economics work out in the future, such outputs 
may not even remain uneconomical to spend. Therefore, dropping them entirely 
from the UTXO set is potentially destroying potentially useful funds people own.

> or at least remove them to secondary storage

Commonly adopted Bitcoin full nodes already have two levels of storage 
effectively (disk and in-RAM cache). It may be useful to investigate using 
amount as a heuristic about what to keep and how long. IIRC, not even every 
full node implementation even uses a UTXO model.

> for Archiving with extra cost to get them back, along with non-standard UTXOs 
> and Burned ones (at least for publicly known, published, burn addresses).

Do you mean this as a standardness rule, or a consensus rule?

* As a standardness rule it's feasible, but it makes policy (further) deviate 
from economically rational behavior. There is no reason for miners to require a 
higher price for spending such outputs.
* As a consensus rule, I expect something like this to be very controversial. 
There are currently no rules that demand any minimal fee for anything, and 
given uncertainly over how fee levels could evolve in the future, it's unclear 
what those rules, if any, should be.

Cheers,

--
Pieter

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

Re: [bitcoin-dev] Rebroadcast mechanism in Bitcoin P2P network

[Pieter Wuille via bitcoin-dev]

On Sunday, December 12th, 2021 at 9:23 AM, Aymeric Vitte via bitcoin-dev 
 wrote:

> Using the Tor network to bypass censorship for bitcoin can work but is a very 
> poor solution, the Tor network is very centralized, very small, watched and 
> controlled, with plenty of features that do not apply to other protocols than 
> those made to be used with the Tor Browser, Pieter gave a simple example, 
> that you can solve easily changing the circuits, the problem remains that you 
> really need to be a super expert to escape all the dangers of the Tor 
> network, not even sure it's possible unless you use something else than the 
> Tor project code

FWIW, I wasn't talking about anything related to Tor's protocol or organization 
at all. What I meant is that because creating a hidden service has ~0 cost, it 
is trivial for anyone to spin up an arbitrary number of Bitcoin hidden 
services. Thus, if one runs a node that only connects to hidden services, it is 
fairly easily eclipsable.

It's just one example of a downside of (a particular way of) using Tor. That 
doesn't mean I recommend against using Tor for Bitcoin traffic at all; my point 
was simply that there are trade-offs, and aspects of privacy of the P2P 
protocol that Tor does not address, and thus one shouldn't assume that all 
problems are solved by "just use Tor".

Cheers,

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

Re: [bitcoin-dev] Rebroadcast mechanism in Bitcoin P2P network

[Pieter Wuille via bitcoin-dev]

> It is that the solution to privacy is to use privacy-enhancing network
> communications, such as TOR. I am not against a mechanism to rebroadcast
> transactions more robustly if the mempool of adjoining nodes has
> forgotten about them, but the truth is, all transactions originate from
> some node, and there are methods that allow an individual node to be
> identified as the likely source of a transaction unless privacy-enabled
> networks are utilised. Having a different method to cause rebroadcast
> does not obfuscate the origin.

You're talking about distinct aspects of transaction privacy.

The rebroadcasting approach as it exists on the network, where wallets are 
responsible for their own rebroadcasting, directly reveals to your peers a 
relation between nodes and transactions: whenever any node relays the same 
transaction twice, it almost certainly implies they are the origin.

This is just a node-transaction relation, and not necessarily IP-transaction 
relation. The latter can indeed be avoided by only connecting over Tor, or 
using other privacy networks, but just hiding the relation with IP addresses 
isn't sufficient (and has its own downsides; e.g. Tor-only connectivity is far 
more susceptible to partition/Eclipse/DoS attacks). For example seeing the same 
node (even without knowing its IP) rebroadcast two transaction lets an observe 
infer a relation between those transactions, and that too is a privacy leak.

I believe moving to a model where mempools/nodes themselves are responsible for 
rebroadcasting is a great solution to improving this specific problem, simply 
because if everyone rebroadcasts, the original author doing it too does not 
stand out anymore. It isn't "fixing privacy", it's fixing a specific leak, one 
of many, but this isn't a black and white property.

Cheers,

--
Pieter

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

Re: [bitcoin-dev] Taproot Fields for PSBT

[Pieter Wuille via bitcoin-dev]

On Wednesday, November 24th, 2021 at 7:44 AM, Sjors Provoost via bitcoin-dev 
 wrote:

> Hi Andrew,
>
> I'm confused why PSBT_IN_TAP_BIP32_DERIVATION and 
> PSBT_OUT_TAP_BIP32_DERIVATION
> contain not just the derivation path for the xonlypubkey, but also the 
> tapleaf merkle path.
>
> First I thought it was perhaps necessary in order for a signer to guess which
> script leaves it can sign with its own keys. But you can't really know that 
> without
> actually seeing the script. When a signer looks at a script, it presumably 
> already
> knows the leaf path.

No, that's exactly it. Signers aren't expected to know or understand scripts 
ahead of time. With a field telling them which keys are present in which 
leaves, and how those keys are derived, they can sign without fully 
understanding the script, or needing the ability to parse the relevant script 
at all. The actual script information is there too of course, for those that do 
want to analyze it, or factor that into the decision whether to sign or not.

Cheers,

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

Re: [bitcoin-dev] bitcoinj fork with Taproot support

[Pieter Wuille via bitcoin-dev]

On Wednesday, November 17th, 2021 at 1:07 PM, Andrew Chow via bitcoin-dev 
 wrote:

> Prior to 0.19.0, creating outputs with an unknown witness version was 
> considered non-standard. This was a violation of BIP 173 and was fixed for 
> 0.19.0+ in PR #15846.

That's correct, but I think OP's problem is with getting P2TR _spends_ to 
relay. Those will be rejected by all post-segwit pre-taproot Bitcoin Core 
releases, as far as I know.

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

[bitcoin-dev] BIP341 test vectors for wallet implementations

[Pieter Wuille via bitcoin-dev]

Hi all,

I wanted to bring some attention to a set of test vectors I'm proposing to add 
to BIP341 in https://github.com/bitcoin/bips/pull/1225.

These are focused on wallet implementations, covering Merkle root / tweak / 
scriptPubKey computation from key/scripts, sigmsg/sighash/signature computation 
for key path spending, and control block computation for script path spending.

Given the short time that remains before BIP341's activation, I think this may 
be helpful to people working on implementations, even before it's merged. All 
values in it are automatically generated from an actual scenario tested against 
Bitcoin Core (which involves constructing and mining transactions with 
specified data).

The tests are mostly focused on features that are likely useful/testable in 
implementations right now, and e.g. excludes sighashes that involve annexes for 
that reason. It's also specific to BIP341, and doesn't cover BIP342 script 
semantics. Still, if anyone relies on features that are useful, but aren't 
covered, I'm happy to add more scenarios.

Cheers,

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

Re: [bitcoin-dev] death to the mempool, long live the mempool

[Pieter Wuille via bitcoin-dev]

On Monday, October 25th, 2021 at 10:56 PM, lisa neigut via bitcoin-dev 
 wrote:

> Hi all,
>
> In a recent conversation with @glozow, I had the realization that the mempool 
> is obsolete and should be eliminated.

Hi Lisa,

I see where this idea is coming from, especially as it relates to reducing 
complexities around transaction relays, but I strongly believe this is throwing 
out the baby with the bathwater. Comments inline below.

> In reality however, mempool relay is unnecessary where the majority of 
> hashpower and thus block template creation is concentrated in a 
> semi-restricted set.

The *entire* reason mining and PoW exist, as opposed to having a fixed, 
centralized (set of) actors who decide transaction ordering, is to make the 
"censorship rights" of the network permissionless. It is essential that anyone 
can become a miner if they dislike what existing miners are doing, with income 
close to proportional to their investment. The existing reality isn't perfect, 
but it's fairly close to that. Sure, at any given point in time, a nontrivial 
fraction of mining power is in the hands of a few, but over time, those can, 
and have, changed a lot. Furthermore, if miners were to actually exercise 
censorship, it could quite reasonably incentivize other ecosystem players to 
start mining, perhaps close at cost or even at a small loss.

Your proposal, as far as I can tell, makes it *far* harder to become a miner. 
Ideas to provide a mechanism for miners to publish their "tx submit" 
URL/IP/onion on chain don't help; that's dependent on other miners to not 
censor the publishing. Furthermore, it gives a tremendous centralizing 
incentive: it's just far easier for most wallets to just submit to the largest 
few pools, because the cost/complexity of an additional submission is 
independent of the pool's hashrate, but the benefit is directly proportional to 
it. There would be very little incentive to submit to a sub-1% pool for anyone.

> Removing the mempool would greatly reduce the bandwidth requirement for 
> running a node,

That's not true due to compact blocks (most transactions are relayed exactly 
once to every node, and not repeated in blocks), and with Erlay it will be even 
less the case.

> keep intentionality of transactions private until confirmed/irrevocable,

Except to miners; it's replacing socialized transparency with a few who get to 
see the actual details. Not the same scale obviously, but there is some 
similarity to banks in the existing financial system. Our privacy goals 
shouldn't be relying on a few trusted gatekeepers.

> and naturally resolve all current issues inherent in package relay and rbf 
> rules. It also resolves the recent minimum relay questions, as relay is no 
> longer a concern for unmined transactions.

There are other solutions to this, like weak blocks (miners get to relay 
partial PoW solutuon of say 10% of the difficulty to the network; and nodes 
which receive such a weak block can "forcibly" insert its transaction to their 
mempool, as there is evidence it's actually being worked on, while still being 
DoS resistant because partial PoW is still PoW).

> Provided the number of block template producing actors remains beneath, say 
> 1000, it’d be quite feasible to publish a list of tor endpoints that nodes 
> can independently + directly submit their transactions to. In fact, merely 
> allowing users to select their own list of endpoints to use alternatively to 
> the mempool would be a low effort starting point for the eventual replacement.

In this scenario, there is no incentive for miners to relay to each other. The 
fewer other miners know about a high fee-paying transaction, the better you as 
a miner.

More conceptually: it is a responsibility of the full node network to relay 
blocks between miners quickly, to limit how much advantage well-connected 
miners over less-well-connected ones have. If the network doesn't have the 
transactions being included in those blocks, this is *far* harder (additional 
roundtrips, as nodes can't reconstruct from mempools).

> A direct communication channel between block template construction venues and 
> transaction proposers also provides a venue for direct feedback wrt 
> acceptable feerates at the time, which both makes transaction confirmation 
> timelines less variable as well as provides block producers a mechanism for 
> (independently) enforcing their own minimum security budget. In other words, 
> expressing a minimum acceptable feerate for continued operation.

Yes, it's definitely easier. That doesn't make it right.

Cheers,

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

Re: [bitcoin-dev] bitcoin.org missing bitcoin core version 22.0

[Pieter Wuille via bitcoin-dev]

On Wednesday, October 20th, 2021 at 3:20 PM, Owen Gunden via bitcoin-dev 
 wrote:

> I also notice that, as of 22.0, Wladimir is no longer signing the
> releases, and I have no trust in my gpg network of the people who seem
> to have replaced him.

This is not correct. Here are Wladimir's attestations on the 22.0 release: 
https://github.com/bitcoin-core/guix.sigs/tree/main/22.0/laanwj

There is no separate special release key anymore though. Instead, the build 
attestations (by anyone) can be used as your trust basis.

> Given the level of security at stake here, my eyebrows are raised at
> this combination of items changing (new website + new gpg signers at the
> same time).

There is no new website. The Bitcoin Core project website has been 
https://bitcoincore.org for years. I don't know why https://bitcoin.org hasn't 
updated to list the 22.0 release, though; that's up to them.

Cheers,

--
Pieter

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

Re: [bitcoin-dev] Taproot testnet wallet

[Pieter Wuille via bitcoin-dev]

On Oct 9, 2021, 11:36, Andreas Schildbach via bitcoin-dev < 
bitcoin-dev@lists.linuxfoundation.org> wrote:

> I'm trying to finish off bitcoinj's implementation for sending to

taproot addresses. For this, I'd like to test against a wallet that can

receive to P2TR and spend back.

> I've been trying to get a taproot address from Bitcoin Core 22.0 and

spent many hours, but in vain. Can someone please simply send my a

testnet wallet that has at least one taproot address? (I don't care

about anyone stealing my testnet coins, so don't worry about the

compromised private key.)

Hi Andreas,

You can construct a taproot-capable wallet in Bitcoin Core as follows:

* Have or create a descriptor wallet (createwallet RPC, with descriptors=true).

* Import a taproot descriptor (of the form "tr(KEY)"), as active descriptor 
(with active=true), where KEY can be a tprv.../* or any other supported key 
expression.

* Get a new address with addresstype=bech32m

I've also created one myself for testing: 
tb1p84x2ryuyfevgnlpnxt9f39gm7r68gwtvllxqe5w2n5ru00s9aquslzggwq

If you send testnet coins there email me an address, I'll return them.

Cheers,

--

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

Re: [bitcoin-dev] [Lightning-dev] Removing the Dust Limit

[Pieter Wuille via bitcoin-dev]

Jumping in late to this thread.

I very much agree with how David Harding presents things, with a few comments 
inline.

‐‐‐ Original Message ‐‐‐
On Sunday, August 8th, 2021 at 5:51 PM, David A. Harding via bitcoin-dev 
 wrote:

> > 1.  it's not our business what outputs people want to create
>
> Every additional output added to the UTXO set increases the amount of
> work full nodes need to do to validate new transactions. For miners
> for whom fast validation of new blocks can significantly affect their
> revenue, larger UTXO sets increase their costs and so contributes
> towards centralization of mining.
> Allowing 0-value or 1-sat outputs minimizes the cost for polluting the
> UTXO set during periods of low feerates.
> If your stuff is going to slow down my node and possibly reduce my
> censorship resistance, how is that not my business?

Indeed - UTXO set size is an externality that unfortunately Bitcoin's consensus 
rules fail to account
for. Having a relay policy that avoids at the very least economically 
irrational behavior makes
perfect sense to me.

It's also not obvious how consensus rules could deal with this, as you don't 
want consensus rules
with hardcoded prices/feerates. There are possibilities with designs like 
transactions getting
a size/weight bonus/penalty, but that's both very hardforky, and hard to get 
right without
introducing bad incentives.

> > 2.  dust outputs can be used in various authentication/delegation smart
> > contracts
>
> > 3.  dust sized htlcs in lightning (
> > 
> > https://bitcoin.stackexchange.com/questions/46730/can-you-send-amounts-that-would-typically-be-considered-dust-through-the-light)
> > force channels to operate in a semi-trusted mode
>
> > 4.  thinly divisible colored coin protocols might make use of sats as value
> > markers for transactions.

My personal, and possibly controversial, opinion is that colored coin protocols 
have no business being on the Bitcoin chain, possibly
beyond committing to an occasional batched state update or so. Both because 
there is little benefit for tokens with a trusted
issuer already, and because it competes with using Bitcoin for BTC - the token 
that pays for its security (at least as long as
the subsidy doesn't run out).

Of course, personal opinions are no reason to dictate what people should or can 
use the chain for, but I do think it's reason to
voice hesitancy to worsening the system's scalability properties only to 
benefit what I consider misguided use.

> > 5.  should we ever do confidential transactions we can't prevent it without
> > compromising privacy / allowed transfers
>
> I'm not an expert, but it seems to me that you can do that with range
> proofs. The range proof for >dust doesn't need to become part of the
> block chain, it can be relay only.

Yeah, range proofs have a non-hidden range; the lower bound can be nonzero, 
which could be required as part of a relay policy.

Cheers,

--
Pieter

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

Re: [bitcoin-dev] Test cases for Taproot signature message

[Pieter Wuille via bitcoin-dev]

On Thursday, September 16th, 2021 at 5:36 PM, Giacomo Caironi via bitcoin-dev 
 wrote:

> Hi,
> recently I have worked on a python implementation of bitcoin signature 
> messages, and I have found that there was way better documentation about 
> Segwit signature message than Taproot.
>
> 1) Segwit signature message got its own BIP, completed with test cases 
> regarding only that specific function; Taproot on the other hand has the 
> signature message function defined in BIP 341 and the test vectors in a 
> different BIP (341). This is confusing. Shouldn't we create a different BIP 
> only for Taproot signature message exactly like Segwit?

I'm not entirely sure what you mean; you're saying BIP 341 twice.

Still, you're right overall - there is no separate BIP for the signature 
message function. The reason is that the message function is different for 
BIP341 and BIP342. BIP 341 defines a basic common message function, which is 
then built up for BIP 341 key path spending, and for BIP 342 tapscript 
spending. This common part could have been a separate BIP, but that'd still not 
be a very clean separation. I'm not very inclined to support changing that at 
this point, given the state of deployment the BIPs have, but that doesn't mean 
the documentation/vectors can't be improved in the existing documents.

> 2) The test vectors for Taproot have no documentation and, most importantly, 
> they are not atomic, in the sense that they do not target a specific part of 
> the taproot code but all of it. This may not be a very big problem, but for 
> signature verification it is. Because there are hashes involved, we can't 
> really debug why a signature message doesn't pass validation, either it is 
> valid or it is not. BIP 143 in this case is really good, because it provides 
> hash preimages, so it is possible to debug the function and see where 
> something went wrong. Because of this, writing the Segwit signature hash 
> function took a fraction of the time compared to Taproot.

You're right. The existing tests are really intended for verifying an 
implementation against (and for making sure future code changes don't break 
anything). They have much higher coverage than the segwit tests had. But they 
aren't useful as documentation; the code that generates them 
(https://github.com/bitcoin/bitcoin/blob/v22.0/test/functional/feature_taproot.py#L605L1122)
 is probably better at that even, but still pretty dense.

> If this idea is accepted I will be more than happy to write the test cases 
> for Taproot.

If you're interested in writing test vectors that are more aimed at helping 
debugging issues, by all means, do. You've already brought up the sighash code 
as an example. Another idea, primarily aimed at developers of signing code, is 
test vectors for certain P2TR scriptPubKeys, derived from certain internal keys 
and script trees. I'm happy to help to integrate such in Bitcoin Core and the 
BIP(s).

Thanks!

Cheers,

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

Re: [bitcoin-dev] Human readable checksum (verification code) to avoid errors on BTC public addresses

[Pieter Wuille via bitcoin-dev]

On Thursday, August 19th, 2021 at 1:02 PM, ts via bitcoin-dev 
 wrote:

> > In any case --- the last 5 characters of a bech32 string are already a 
> > human-readable 5-digit code, with fairly good properties, why is it not 
> > usable for this case?

Side note: it's actually the last six characters.

>
> Well, because
>
> a) most people don't know that
>
> b) it is specific to bech32
>
> c) it is not easily readable being the last digits of a long address 
> (although this could be

I think this is a misconception. For the purpose of verifying that you have the 
*right* address (rather than just a valid one), the checksum, or even the 
knowledge that a checksum is present, is completely irrelevant.

In honestly-generated addresses, every character except the prefix (the ~2 
first characters for P2PKH and P2SH, and the ~4 first characters for 
BIP173/BIP350 native segwit addresses) has exactly the same amount of entropy. 
Instead of adding say a 4 character code, just tell people to compare any 4 
characters of their choosing. Or more - I would hope people are already 
comparing (much) more than 4 characters already.

It doesn't matter if the characters being compared are checksum characters or 
data characters. In honestly-generated addresses, both are equally random.

Adding a special 4 character "external" checksum IMO would instead encourage 
people to perhaps just compare those 4 characters instead of the rest (or at 
least, focus mostly on those). That could easily worsen how well comparisons 
are done in practice...

Cheers,

--
Pieter

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

Re: [bitcoin-dev] Using transaction version number in different projects

[Pieter Wuille via bitcoin-dev]

On Sunday, August 29th, 2021 at 5:32 AM, Prayank via bitcoin-dev 
 wrote:

> Wanted to know if others think we should allow more numbers in transaction 
> version by considering such transaction standard. I have shared an example 
> how transaction version can be used to bet on something that involves 2 
> outcomes:
> https://gist.github.com/prayank23/6f54e9a27f057abd1182436e7f88d1ac

I can't say I understand what you're suggesting, or what transaction version 
numbers have to do with it, so take the following with the caveat that I may be 
missing your point.

Generally, my view is that Bitcoin transactions should solely contain the 
information necessary for the world to validate them. Given that, as of now, 
there are no consensus rules (or even generally-adopted relay policies) that 
care about the version number except it being 1 or 2 (due to BIP68), I would 
say that the usage of anything but those 2 possible numbers is both pointless 
and a gratuitous loss of privacy: for numbers with no protocol-defined meaning, 
the usage of an uncommon one reveals something to the world that should be 
privately communicated to the parties involved instead.

Combined with the fact that currently-unused version numbers may well be used 
for future consensus rules like BIP68, which any use you're suggesting may 
interfere with, I say no: versions numbers with no protocol-defined meaning 
should not be standard. They are reserved for future extensions.

Cheers,

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

Re: [bitcoin-dev] Human readable checksum (verification code) to avoid errors on BTC public addresses

[Pieter Wuille via bitcoin-dev]

On Saturday, August 28th, 2021 at 5:17 PM, ts via bitcoin-dev 
 wrote:

> Following up on my original proposal, I would like to get some more feedback 
> of the community
>
> to see if this could be realized at some point. Also, any recommendations as 
> to who to contact
>
> to get things rolling?

I honestly don't understand the point of what you're suggesting.

* If you're concerned about random typos, this is something already 
automatically protected against through the checksum (both base58check or 
bech32/bech32m).

* If you're concerned about accidentally entering the wrong - but honestly 
created - address, comparing any few characters of the address is just as good 
as any other. It doesn't even require the presence of a checksum. Looking at 
the last N characters, or the middle N, or anything except the first few, will 
do, and is just as good as an "external" checksum added at the end. For 
randomly-generated addresses (as honest ones are), each of those has exactly as 
much entropy.

* If you're concerned about maliciously constructed addresses, which are 
designed to look similar in specific places, an attacker can just as easily 
make the external checksum collide (and having one might even worsen this, as 
now the attacker can focus on exactly that, rather than needing to focus on 
every other character).

Things would be different if you'd suggest a checksum in another medium than 
text (e.g. a visual/drawing/colorcoding one). But I don't see any added value 
for an additional text-based checksum when addresses are already text 
themselves. This is even disregarding the difficulty of getting the ecosystem 
to adopt such changes.

Cheers,

--
Pieter

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

Re: [bitcoin-dev] An idea to block invalid addresses from reaching the peers.dat buckets

[Pieter Wuille via bitcoin-dev]

> This is an interesting read: https://bitcointalk.org/index.php?topic=5348856.0
>
> So according to this, somebody is spamming the bitcoin network with addr 
> message pointing to invalid addresses and ports, which bloats the peers.dat 
> and corresponding structure in memory.

The peers.dat file and the structure in memory have a fixed size, so those are 
not a problem.

> Since peers.dat uses a custom record type which I don't know how to parse, I 
> wasn't able to check specifics of IP addresses listed in there, but I believe 
> I have a workaround to prevent this kind of thing from happening. Exactly how 
> easy or difficult it will be to implement this change I don't know.

The "addrman" database is organized into 1024 buckets with "new" addresses 
(which we haven't tried to connect to), and 256 buckets with "tried" addresses 
(which we have connected to ourselves). Each bucket consists of 64 positions, 
and each of those can hold 1 address. Along with the addresses we remember 
where we originally heard about them (which IP).

Each group of source IPs (/16s etc) selects a subset of just 64 buckets (salted 
using a host-specific secret key), and inserts the newly received IPs in a 
position in a bucket in one of those, if certain criteria are met (the position 
was empty, or it held an IP address that also occurs elsewhere in the table 
already). This limits the impact an attacker can have, because they cannot 
under any circumstances affect IPs in buckets outside of the 64 their group 
maps to.

This database structure is a design from 2012, which was significantly improved 
following recommendations in the Eclipse Attacks paper 
(https://cs-people.bu.edu/heilman/eclipse/).

> - Change the AddrDb updating functionality so that it does not add nodes that 
> are unreachable. Not unreachable by timeout, but "connection refused" kind of 
> errors.

In a way we have that; there are separate tables in peers.dat for new and tried 
addresses. I don't think it's feasible to not add untried addresses at all, as 
our ability to create connections is far too low to try everything we receive. 
But I think the existing structure should reasonably protect against spam (in 
terms of database poisoning; there is certainly a processing cost to it).

Cheers,

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

Re: [bitcoin-dev] Proposal to stop processing of unrequested transactions in Bitcoin Core

[Pieter Wuille via bitcoin-dev]

> I'm not sure of the existing behavior is of when we issue a getdata request, 
> but noting that there could be a privacy implication of this sort of change. 
> Could you (or someone else) expand on why this is not a concern here?

What kind of privacy concern are you talking about? I'm not sure I see how this 
could matter.

Cheers,

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

Re: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity

[Pieter Wuille via bitcoin-dev]

‐‐‐ Original Message ‐‐‐
On Thursday, February 11, 2021 6:38 AM, Dr Maxim Orlovsky 
 wrote:

> Thank you very much for all the clarifications; it’s good to have them sorted 
> out and clearly structured. From what you wrote it follows that we still need 
> to reserve a dedicated purpose (with new BIP) for BIP340 signatures to avoid 
> key reuse, am I right?

Maybe, but it would be for a particular way of using keys (presumably: 
single-key pay-to-taproot), not just the signature scheme itself. If you go 
down this path you'll also want dedicated branches for multisig participation, 
and presumably several interesting new policies that become possible with 
Taproot.

The only thing ECDSA/Schnorr specific about this is that - if you want to 
maintain provable security - the keys used for ECDSA and BIP340 should be 
separated by a hardened step. It seems however that all approaches people 
actually use to prevent reuse do that already.

And as I said, dedicated branches only help for the simple case. For example, 
it doesn't address the more general problem of preventing reuse of keys in 
multiple distinct groups of multisig sets you participate in. If you want to 
solve that you need to keep track of  index is for participating in what - and 
once you have something like that you don't need dedicated purpose based 
derivation at all anymore.

So I'm not sure I'd state it as us *needing* a dedicated purpose/branch for 
single-key P2TR (and probably many other useful ways of using taproot based 
spending policies...). But perhaps it's useful to have.

Greg Maxwell pointed out to me that there may be another reason to want 
non-reuse across ECDSA and BIP340 keys: if someone were to do all of these 
wrong:
* not follow BIP340 and re-use RFC6979 for BIP340 nonce generation
* reuse the same keys for both
* sign the same message with both
... you would actually leak your private key. This isn't a concern for Bitcoin 
transaction signing however, as the sighash (message) indirectly commits to 
BIP341 or not, and thus it'd be impossible to construct colliding messages. 
Still, it's a consideration to factor in.

Cheers,

--
Pieter

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

Re: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity

[Pieter Wuille via bitcoin-dev]

On Friday, February 5, 2021 9:51 AM, Dr Maxim Orlovsky via bitcoin-dev 
 wrote:

> Hi,
>
> Background
>
> 
>
> Had a discussion last night in Bitcoin Core IRC with Peter Wuille on 
> different topics regarding key derivations, security, key tweaks in context 
> of Schnorr signatures & Taproot. Would like to share some action points and 
> plans that emerged from there:
>
> 1.  There is a real need for BIP-43 based new BIP with a new purpose field 
> for keys used in Schnorr signatures. Peter will not do it (he is not very 
> much interested in spending his time on wallet-level stuff), so someone else 
> should.
> 2.  Keys used in Schnorr signatures MUST NEVER BE used in ECDSA signatures, 
> otherwise there is a risk of private key leak via correlation attack. This is 
> rationale behind N1.

Hi Maxim,

thanks for bringing up this discussion here. I'd like to clarify a few things 
though, as I think the above is formulated far too strongly.

There are two issues here: (1) reasons to avoid reusing the same key for 
privacy reasons, and (2) reasons to avoid using related keys for cryptographic 
reasons. And in practice, solutions to the first (which we already need, 
unrelated to Taproot/Schnorr) mean the second is largely moot.


# Don't reuse keys for privacy/organizational reasons.

Reusing the same key in Bitcoin scripts - for use in distinct signature schemes 
or not - should always be avoided. It has obvious privacy implications; I don't 
think this is controversial, and it's a problem that exists today, unrelated to 
Taproot. E.g. you don't want to reuse the same keys as both single-sig and 
participation in multisig.

My personal view here is that distinct standard derivation paths help with this 
in the simple cases, but they're not a full solution in the most general case. 
E.g. if you want to use one seed/root to participate in multiple sets of 
multisig policies, you'll need some kind of index to assign to each anyway. For 
this reason in general I prefer solutions that explicitly track what path is 
used for what.


# Don't use related keys for cryptographic reasons

There are some concerns to address here, but I want to make it clear there are 
no known attacks against usage of related keys across ECDSA and Schnorr, and I 
don't expect there will be. However, there is probably no proof for this, and 
creating one may be tricky. On the other hand, the ecosystem (Bitcoin, but also 
many other applications) has accepted ECDSA long ago, while it had no security 
proofs whatsoever (and even the ones that exist now rely on fairly unusual 
assumption; a proof for security of mixed Schnorr/ECDSA usage would inherently 
need equally unusual assumptions too).

Now, as soon as a hardened derivation separates different uses there is no 
concern at all. So any solution for avoiding key reuse (section above) that 
works by assigning (implicitly or explicitly) different hardened derivation 
paths (as BIP43 etc. do) to different uses implies there is never any concern 
about related keys across Schnorr/ECDSA.

If the keys are not separated by a hardened step, it's more complicated. 
Looking at the different cases:

(1) Signing with related ECDSA keys (e.g. two unhardened child keys from the 
same xpub)

- This is very common on BIP32 usage today, so hopefully it is secure! Tim 
Ruffing pointed me today to 
https://link.springer.com/chapter/10.1007/978-3-030-36938-5_8 whose abstract 
seems to indicate they prove this is actually secure, but I don't know under 
what assumptions. Note that the comment there about Schnorr not having this 
property does not apply to BIP340, because it uses key-prefixed Schnorr.

(2) Signing with related Schnorr keys.

- I believe this is secure simply because BIP340 challenges commit to the 
pubkey (key prefixing), and thus a signature on one shouldn't teach you 
anything about others. A formal proof is probably a bit longer, but still 
trivial to construct.

(3) The real question: signing with a Schnorr key that is related to an ECDSA 
key.

- I don't expect that this is easy to prove, but I have a very hard time 
imagining how it could be exploitable, given the use of domain-separated 
hashes. Aspects such as BIP340's key prefixing and the fact that Bitcoin 
sighashes indirectly commit to the (set of) signing pubkeys make it even harder.


# TL;DR

* For privacy reasons, you should use separate keys/derivation branches for 
different uses in all circumstances (duh).
* To stay within the realm of provably security it's advisable to make sure 
ECDSA key and Schnorr keys use distinct hardened derivation steps.
* Even if you don't, you're really just back to the level of assurance we had 
about unhardened BIP32 ECDSA keys before a proof was known (which I think most 
people aren't even aware of).

Cheers,

--
Pieter

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org

Re: [bitcoin-dev] Bech32m BIP: new checksum, and usage for segwit address

[Pieter Wuille via bitcoin-dev]

On Tuesday, January 19, 2021 4:23 PM, nakagat  wrote:

> Dear. Pieter,
>
> My idea is exactly what you wrote.
>
> However, I don't think it is the same as "checksum = hash (hrp, data)".

No, it is not the same. But it has the same error-detection properties as just 
a hash. Hash-based checksums aren't bad, but:
* The BCH based checksum that Bech32 uses is better at detecting certain 
subsets of errors than a hash can be. Once you add in a hash you irrevocably 
lose these properties.
* If we wanted a checksum with error detection properties that are equivalent 
to a hash, we should just use a hash like Base58Check did. However, that's not 
the goal of Bech32/Bech32m.

If this isn't clear, I'm afraid I don't know how to continue discussing this. 
We can take if off this list, if you want.

Cheers,

--
Pieter

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

Re: [bitcoin-dev] Bech32m BIP: new checksum, and usage for segwit address

[Pieter Wuille via bitcoin-dev]

On Sunday, January 17, 2021 9:59 PM, nakagat  wrote:

> I thought that BECH32M_CONST could be created from hrp and data
> instead of constants.
>
> I thought that the error position would be the same as bech32 by
> recalculating the value created from hrp and data.

So, bech32 can be written as:

* checksum = polymod(expand(hrp) + data) xor 1

Bech32m changes that to:

* checksum = polymod(expand(hrp) + data) xor 0x2bc830a3

I believe that your idea is:

* checksum = polymod(expand(hrp) + data) xor hash(hrp, data)

That has exactly the same error detecting capabilities as:

* checksum = hash(hrp, data)

The hashing makes all types of errors uniform, and it doesn't matter what other 
things are added to the checksum. Once you hash the data, the checksum is 
uniformly random, and you can't make it "less random" anymore.

In this case, we *want* non-uniformity. The polymod function as a checksum 
detects some kinds of errors much better than others, and this is what we want.

Does that clarify things?

Cheers,

--
Pieter


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

Re: [bitcoin-dev] Bech32m BIP: new checksum, and usage for segwit address

[Pieter Wuille via bitcoin-dev]

On Monday, January 4, 2021 4:14 PM, Pieter Wuille  
wrote:

> Hello all,
>
> here is a BIP draft for changing the checksum in native segwit addresses for 
> v1 and higher, following the discussion in 
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-December/018293.html
>
> Overall, the idea is:
> * Define a new encoding which is a tweaked variant of Bech32, called Bech32m. 
> It refers to the Bech32 section of BIP173, which remains in effect.
> * Define a new segwit address encoding which replaces the corresponding 
> section in BIP173. It prescribes using Bech32 for v0 witness addresses, and 
> Bech32m for other versions.

Of course I forgot the actual link: 
https://github.com/sipa/bips/blob/bip-bech32m/bip-bech32m.mediawiki

Cheers,

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

[bitcoin-dev] Bech32m BIP: new checksum, and usage for segwit address

[Pieter Wuille via bitcoin-dev]

Hello all,

here is a BIP draft for changing the checksum in native segwit addresses for v1 
and higher, following the discussion in 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-December/018293.html

Overall, the idea is:
* Define a new encoding which is a tweaked variant of Bech32, called Bech32m. 
It refers to the Bech32 section of BIP173, which remains in effect.
* Define a new segwit address encoding which replaces the corresponding section 
in BIP173. It prescribes using Bech32 for v0 witness addresses, and Bech32m for 
other versions.

Comments, suggestions, ideas?

Cheers,

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

[Pieter Wuille via bitcoin-dev]

On Monday, December 21, 2020 2:57 PM, Pieter Wuille via bitcoin-dev 
 wrote:

> On Sunday, December 20, 2020 9:37 PM, Karl-Johan Alm via bitcoin-dev 
> bitcoin-dev@lists.linuxfoundation.org wrote:
>
> > Thanks a lot for taking the time to brush up the BIP. For what it's
> > worth, I am all for these changes, and I see them as clear
> > improvements all around.
> > IIRC Pieter was the one who originally suggested the two-checks
> > approach (invalid, inconclusive, valid) which is being modified here,
> > so would be good if you chimed in (or not -- which I'll assume means
> > you don't mind).
>
> I agree with the idea of permitting incomplete validators to return 
> inconclusive as well. That doesn't really reduce the functionality (given 
> that "inconclusive" was already a potential result), and it obviously makes 
> it much more accessible to a variety of software.
>
> This suggestion breaks the original use of inconclusive though: the ability 
> to detect that future features are used in the signature. The idea was to use 
> divergence between "consensus valid" and "standardness valid" as a proxy for 
> future extensions to be detected (e.g. OP_NOPn, future witness versions, 
> ...). I think it's undesirable that these things now become unconditionally 
> invalid (until the BIP is updated, but once that happens old validators will 
> give a different result than new ones).
>
> Since the BIP no longer relies on a nebulous concept of standardness, and 
> instead specifically defines which standardness features are to be 
> considered, this seems easy to fix: whenever validation fails due to any of 
> those, require reporting inconclusive instead of invalid (unless of course 
> something actually invalid also happens). In practice I guess you'd implement 
> that (in capable validators) by still doing validation twice, once with all 
> features enabled that distinguish between valid/invalid, and if valid, again 
> but now with the features enabled that distinguish between valid and (invalid 
> or inconclusive).

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.

Cheers,

--
Pieter

___
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

[Pieter Wuille via bitcoin-dev]

On Sunday, December 20, 2020 9:37 PM, Karl-Johan Alm via bitcoin-dev 
 wrote:

> Thanks a lot for taking the time to brush up the BIP. For what it's
> worth, I am all for these changes, and I see them as clear
> improvements all around.
>
> IIRC Pieter was the one who originally suggested the two-checks
> approach (invalid, inconclusive, valid) which is being modified here,
> so would be good if you chimed in (or not -- which I'll assume means
> you don't mind).

I agree with the idea of permitting incomplete validators to return 
inconclusive as well. That doesn't really reduce the functionality (given that 
"inconclusive" was already a potential result), and it obviously makes it much 
more accessible to a variety of software.

This suggestion breaks the original use of inconclusive though: the ability to 
detect that future features are used in the signature. The idea was to use 
divergence between "consensus valid" and "standardness valid" as a proxy for 
future extensions to be detected (e.g. OP_NOPn, future witness versions, ...). 
I think it's undesirable that these things now become unconditionally invalid 
(until the BIP is updated, but once that happens old validators will give a 
different result than new ones).

Since the BIP no longer relies on a nebulous concept of standardness, and 
instead specifically defines which standardness features are to be considered, 
this seems easy to fix: whenever validation fails due to any of those, require 
reporting inconclusive instead of invalid (unless of course something actually 
invalid also happens). In practice I guess you'd implement that (in capable 
validators) by still doing validation twice, once with all features enabled 
that distinguish between valid/invalid, and if valid, again but now with the 
features enabled that distinguish between valid and (invalid or inconclusive).

Cheers,

--
Pieter

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

Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173)

[Pieter Wuille via bitcoin-dev]

On Tuesday, December 8, 2020 9:39 AM, Ryan Grant  wrote:

> It looks like a good strategy for a bech32 library that is external to
> Bitcoin Core would be:
>
> -   Default to the new M, under the same bech32 brand.
> -   Provide an interface to explicitly use both M=1 and M=0x2bc830a3.
> -   If decoding fails, throw an error; but in constructing that error
> inform whether the other M would have succeeded.
>
> -   Provide an interface for a BIP173 implementation to peek at the
> witness version byte of the data part, which may also involve
> sanity-checking that byte for errors using a BIP173-specific
> understanding of the appropriate checksum.

I think there are two possible interfaces that make sense:

- Have the caller explicitly specify whether they want bech32 or bech32m (which 
someone - I think Rusty? - started using in reference to this new code and I'm 
going to adopt now).

- Have the bech32 decoding function return a tristate (failed, valid as bech32, 
valid as bech32m). No string is ever valid as both, so there is no loss of 
information here.

The former is a bit cleaner, and also the only real choice if error location 
hinting is desired. The second is more efficient if decoding twice is a 
performance concern.

Cheers,

--
Pieter

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

Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173)

[Pieter Wuille via bitcoin-dev]

‐‐‐ Original Message ‐‐‐
On Sunday, December 6, 2020 5:04 AM, David A. Harding  wrote:

> On Sat, Dec 05, 2020 at 11:10:51PM +0000, Pieter Wuille via bitcoin-dev wrote:
>
> > I think these results really show there is no reason to try to
> > maintain the old-software-can-send-to-future-segwit-versions property,
> > given that more than one not just didn't support it, but actually sent
> > coins into a black hole.
>
> I don't think this is a good criteria to use for making a decision. We
> shouldn't deny users of working implementations the benefit of a feature
> because some other developers didn't implement it correctly.
>
> > Thus, I agree with Rusty that we should change the checksum for v1+
> > unconditionally.
>
> I disagreed with Rusty previously and he proposed we check to see how
> disruptive an address format change would be by seeing how many wallets
> already provide forward compatibility and how many would need to be
> updated for taproot no matter what address format is used. I think that
> instead is a good criteria for making a decision.
>
> I understand the results of that survey to be that only two wallets
> correctly handled v1+ BIP173 addresses. One of those wallets is Bitcoin
> Core, which I personally believe will unhesitatingly update to a new
> address format that's technically sound and which has widespread support
> (doubly so if it's just a tweak to an already-implemented checksum
> algorithm).

Hi Dave,

You're right to point out there is nuance I skipped over.

Let's look at the behavior of different classes of software/services that exist 
today when trying to send to v1+ addresses:

(A) Supports sending to v1+ today
  * Old proposal: works, but subject to bech32 insertion issue
  * New proposal: fails
(B) Fails to send to v1+ today
  * Old proposal: fails
  * New proposal: fails
(C) Incorrectly sends to v1+ today
  * Old proposal: lost funds
  * New proposal: fails

So the question is how the support for sending to v1+ in (a) software weighs up 
against protecting both (a) from the insertion issue, and (c) from lost funds. 
I do think (c) matters in this equation - people may choose to avoid adopting 
v1+ witnesses if it were to be known that some senders out there would 
misdirect funds. But the fact that (a) is small also means there is very little 
to gain from the old proposal.

So perhaps I should have formulated it as: the small number of v1+ compatible 
senders today (regardless of the reasons for that) shows how futile the attempt 
to have one address type for all witness versions was, and the fact that there 
are even some who misdirect(ed) funds is the final nail in the coffin. Changing 
the checksum unconditionally gives us a new attempt at that.

> Given that, I also now agree with changing the checksum for v1+.

Great.

Cheers,

--
Pieter

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

Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173)

[Pieter Wuille via bitcoin-dev]

> On Wednesday, October 7, 2020 5:21 PM, Rusty Russell via bitcoin-dev 
> bitcoin-dev@lists.linuxfoundation.org wrote:
>
> > I propose an alternative to length restrictions suggested by
> > Russell in https://github.com/bitcoin/bips/pull/945: use the
> > https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb variant,
> > unless the first byte is 0.
>
> Hi all,
>
> starting a slight side-thread here.

Another update, and a longer write-up.


Introduction


Bech32's checksum algorithm was designed to be strong against substitution
errors, but it also provides some protection against more general classes of
errors. The final constant M that is XOR'ed into the checksum influences that
protection. BIP173 today uses M=1, but it is now known that this has a
weakness: if the final character is a "p", any number of "q" characters can be
inserted or erased right before it, without invalidating the checksum.

As it was recognized that other constants do not have this issue, the obvious
question is whether this is the only possible type of weakness, and if not, if
there is an optimal constant to use that minimizes the largest number of
weaknesses.

Since my last mail I've realized that it is actually possible to analyse the
behavior of these final constants under a wide variety of error classes
(substitutions, deletions, insertions, swaps, duplications) programatically.
Greg Maxwell and I have used this to perform an exhaustive analysis of certain
error patterns for all 2^30 possible M values, selected a number of criteria
to optimize for, and conclude that we should use as constant:

  M = 0x2bc830a3

The code used to do this analysis, as well as the code used to verify some
expected properties of the final result, and more, can be found on
https://gist.github.com/sipa/14c248c288c3880a3b191f978a34508e

See results_final.txt to see how this constant compares with the previously
suggested constants 1, 0x3fff, and 0x3fef.

Properties
--

If we define an error as a deletion of one position, a swap of adjacent
positions, a substitution in a specific position with a random character, an
insertion of one random character in a specific position, or a duplication of
the character in a specific position, then this M constant above gives us the
following properties:

* For generic HRPs and errors that don't affect the first 6 data characters,
  or alternatively averaged over all HRPs (see details futher):
  * Always detected:
* (P) Up to 4 substitution errors (true for any constant).
* (Q) Any valid code with the new constant, fed without modification to
  software that uses the old constant 1 (true for any constant).
  * Any error pattern has failure to detect probability <= 2^-30:
* (L) Any number of errors restricted to a single window of up to 4
  characters.
* (B) Up to two errors restricted to a window of up to 68 characters.
* (D) Any one error made to a valid code with the new constant, and fed to
  software that uses the old constant 1
  * Most error patterns have probability <= 2^-30:
* (C) Up to two errors in general: out of 23926796 such error patterns,
  0.0040% have probability 2^-25.
* (N) Up to three errors restricted to a window of up to 69 characters:
  out of 284708444 such patterns, 0.033% have probability 2^-25.
* (O) Up to three errors in general: out of 29572 such error patterns,
  0.034% have probability 2^-25; 0.65% have probability 2^-20.
* (G) Up to two errors made to a valid code with the new constant, and fed
  to software that uses the old constant 1: out of 2831622 such error
  patterns, 0.048% have probability 2^-25.

* Specifically for the bc1 HRP, with the BIP173 length restrictions:
  * Always detected:
* (R) Up to 4 substitution errors (true for any constant).
* (A) Up to 3 substitution errors made to a valid code with the new
  constant, and fed to software that uses the old constant 1.
  * Any error pattern has failure to detect probability <= 2^-30:
* (E) Any one error.
* (F) Any one error made to a valid code with the new constant, and fed to
  software that uses the old constant 1.
* (H) Up to two errors restricted to a window of 28 characters.
  * Most error patterns have probability <= 2^-30:
* (J) Up to two errors in general: out of 455916 such error patterns,
  0.039% have probability 2^-25; 0.0053% have 2^-20.
* (K) Any number of errors restricted to a window of 4 characters: out of
  5813139 such error patterns, 0.0016% have probability 2^-25.
* (M) Up to three errors: out of 50713466 such error patterns, 0.078% have
  probability 2^-25; 0.00063% have 2^-20.
* (I) Up to two errors made to a valid code with the new constant, and fed
  to software that uses the old constant 1: out of 610683 such error
  patterns, 0.092% have probability 2^-25; 0.00049% 

Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173)

[Pieter Wuille via bitcoin-dev]

On Friday, November 6, 2020 11:49 AM, Mike Schmidt via bitcoin-dev 
 wrote:

> Well I sure picked a bad couple weeks to volunteer to send a bunch of Bitcoin 
> test transactions...
>
> While I tested less than I would have liked, there are some notable results:

I think these results really show there is no reason to try to maintain the 
old-software-can-send-to-future-segwit-versions property, given that more than 
one not just didn't support it, but actually sent coins into a black hole.

Thus, I agree with Rusty that we should change the checksum for v1+ 
unconditionally. That also means that old senders are protected from the 
insertion issue (by failing, as we can guarantee that new-checksum addresses, 
even after a few errors, are invalid to old software).

I've sent another mail in this thread with details, but the TL;DR is that we 
should use the constant M=0x2bc830a3 rather than 0x3fff as previous 
suggested. More information on 
https://gist.github.com/sipa/14c248c288c3880a3b191f978a34508e.

Absent objections, I'll write up a BIP soon.

Cheers,

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

Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173)

[Pieter Wuille via bitcoin-dev]

On Wednesday, October 7, 2020 5:21 PM, Rusty Russell via bitcoin-dev 
 wrote:

> I propose an alternative to length restrictions suggested by
> Russell in https://github.com/bitcoin/bips/pull/945: use the
> https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb variant,
> unless the first byte is 0.

Hi all,

starting a slight side-thread here.

The discussion here made me realize that as we're introducing (at some point) a 
new checksum scheme, we don't just care about the new scheme's own error 
detection capabilities, but also about the probability that a new style address 
+ errors is incorrectly accepted as an old style address.


Clearly these properties are less of a priority than just the new-style + error 
being misinterpreted as a new-style address, as problems will only occur when 
entering a new address with errors in old software that supports the old scheme 
(which this thread shows, is not very common). Still, all other things being 
equal, it can't hurt to see if some choices are better than others.

https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb suggested the use 
of constant M = 0x3FFF. It turns out this is slightly suboptimal in two 
ways:

* It's possible to take a new-style address with that constant, make 3 
substitution errors, and obtain an old-style address.
* If a new-style address ends with '7', inserting 'g78u' just before it will 
result in a valid old-style address (ignoring length constraints).

I don't think either of these is serious, but it's possible to improve upon 
them:

* Guaranteeing that 4 substitution errors are always detected while switching 
schemes seems impossible, but a constant can be picked that guarantees 3 errors 
always are.
* Insertion/deletion errors can be restricted to patterns that require 6 fixed 
characters (which, assuming uniformly random characters, implies a probability 
of 2^-30).

It seems M=0x3ffe has both these properties.

I'm going to do some more analysis (swapping, and insertion/erasure near the 
start), and then update my gist, but so far it seems this is a strictly (albeit 
only slightly) better choice.

Cheers,

--
Pieter

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

Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173)

[Pieter Wuille via bitcoin-dev]

On Tuesday, October 20, 2020 3:29 AM, David A. Harding  wrote:


> I would guess that some of the failures / stuck transactions might now be 
> successes if the backend infrastructure has upgraded to Bitcoin Core > = 0.19.

Yeah, it would be good to re-test them since a ~year has passed since the 
0.19.0 release.

Cheers,

--
Pieter



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

Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173)

[Pieter Wuille via bitcoin-dev]

On Sunday, October 18, 2020 5:49 PM, Rusty Russell  
wrote:

> Pieter Wuille bitcoin-...@wuille.net writes:
>
> > Today, no witness v1 receivers exist. So it seems to me the only question
> > is what software/infrastructure exist that supports sending to witness v1,
> > and whether they (and their userbase) are more or less likely to upgrade
> > before receivers appear than those that don't.
> > Clearly if only actively developed software currently supports sending to
> > v1 right now, then the question of forward compatibility is moot, and I'd
> > agree the cleanliness of option 2 is preferable.
>
> If software supports v1 today and doesn't get upgraded, and we persue
> option 1 then a trailing typo can make trouble. Not directly lose money
> (since the tx won't get propagated), but for most systems (e.g. hosted
> wallets) someone has to go in and figure out the error and fix it up.

It depends. As is, they'd be relayed even as sending to future witness versions
or lengths is standard. If option 1 is chosen there may be reasons to add
safeguards using relay policy, though.

> Option 2 means they're likely to fix their systems the first time
> someone tries a v1 send, not the first time someone makes a trailing
> typo (which might be years).

Possibly, but it's also possible that it won't get fixed at all, and instead
receiver software just has to wait a few years longer before being able to start
giving out v1 addresses and have a reasonable chance the sender supports it.

You're right though that protecting old sender software from being protected
against the insertion bug is a good argument in favor of Option 2.

Strictly speaking it also has an issue, as the error detection properties aren't
guaranteed for new-scheme-address + intended-detected-error interpreted as
old-scheme-address (in particular, you can make 4 substitution errors in
a new-scheme address and have it be a valid old-scheme address). This is much
less of an issue than the insertion bug that remains present with Option 1 in
old senders.

> > As for how long: new witness version/length combinations are only rarely 
> > needed,
> > and there are 14 length=32 ones left to pick. We'll likely want to use those
> > first anyway, as it's the cheapest option with 128-bit collision resistance.
> > Assuming future constructions have something like BIP341's leaf versioning, 
> > new
> > witness version/length combinations are only required for:
> >
> > -   Changes to the commitment structure of script execution (e.g. Graftroot,
> > different hash function for Merkle trees, ...)
> >
> > -   Upgrades to new signing cryptography (EC curve change, PQC, ...).
> > -   Changes to signatures outside of a commitment structure (e.g. new 
> > sighash
> > modes for the keypath in BIP341, or cross-input aggregation for them).
> >
> >
> > and in general, not for things like new script opcodes, or even for fairly
> > invasive redesigns of the script language itself.
>
> Hmm, good point. These can all be done with version bumps.
>
> The only use for extra bytes I can see is per-UTXO flags, but even then
> I can't see why you'd need to know them until their spent (in which case
> you stash the flag in the input, not the output).
>
> And fewer bytes seems bad for fungibility, since multisig would be
> dangerous.
>
> But the future keeps surprising me, so I'm still hesitant.

Of course, our thinking here may change significantly over time - still, I 
expect
it'll be years before something other than 32-byte addresses is desired.

> > TL;DR: what codebases/services/infrastructure exists today that supports
> > sending to witness v1 BIP173 addresses?
>
> OK, time to waste some money!
>
> Can you provide a mainnet v1 address, and I'll try to spam it from as
> many things as I can find. If we're really lucky, you can collect it
> post-fork and donate it to charity. Or a miner can steal it pre-fork :)

Here is a BIP341 witness v1 address, corresponding to just the generator as
inner public key (using TapTweak(pubkey) as tweak, as suggested by the BIP):

bc1pmfr3p9 YOU j00pfxjh WILL 0zmgp99y8zf LOSE tmd3s5pmedqhy MONEY 
ptwy6lm87hf5ss52r5n8


Cheers,

--
Pieter

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

Re: [bitcoin-dev] Is BIP32's chain code needed?

[Pieter Wuille via bitcoin-dev]

On Tuesday, September 29, 2020 10:34 AM, Leonardo Comandini via bitcoin-dev 
 wrote:

> Hi all,
>
> BIP32 [1] says: "In order to prevent these from depending solely on the key
> itself, we extend both private and public keys first with an extra 256 bits of
> entropy. This extension, called the chain code...".
>
> My argument is that the chain code is not needed.
> To support such claim, I'll show a schematic of BIP32 operations to be 
> compared
> with an alternative proposal and discuss the differences.
>
> I have two main questions:
> - Is this claim false?
> - Has anyone shared this idea before?

Hi Leonardo,

It's been a while but I can comment on the history of how the chaincode ended 
up being in there.

The most direct reason is that BIP32 was inspired by Alan Reiner's Armory 
software, which had
a different homomorphic key derivation scheme, but included something called a 
chaincode to
enable multiple "chains" of keys to be derived from the same keypair. More 
information about
that scheme is here: 
https://bitcointalk.org/index.php?topic=205999.msg2155696#msg2155696

BIP32 made two improvements to this:
* Allow efficient random access into the derived keys (Armory's scheme required 
iterating the
derivation function to get consecutive subkeys - which is probably where the 
name "chain"
in chaincode comes from)
* Permit hierarchical derivation, by also constructing a sub-"chaincode" along 
with every subkey.

If I recall correctly, there was at least one argument at the time about 
whether the chaincode was
necessary at all. My rationale for keeping it was:
* xpubs are not as secret as private keys, but they do demand more protection 
than just public keys
(for both privacy reasons, and due to the fact that revealing an xpub + child 
xprv is ReallyBad(tm)).
For that reason, it seems nice that an xpub consists of more than just a public 
key, as revealing
the public key in it means the protection above remains. I don't think there is 
anything fundamental
here; just a distinct encoding for xpubs and pubkeys might have accomplished 
the same, but this
felt safer.
* Repeated hashing "felt" dangerous, as it reduces entropy at every step, so 
it'd go below 256 bits.
With a chaincode to maintain extra entropy this is prevented. In retrospect, 
this is a bogus
argument, as it's only a relevant point for information-theoretical security 
(which means we wouldn't
be able to use ECC in the first place), and even then, it's only a minimal 
effect.

So in short, from a cryptographic point of view, I think that indeed, the 
chaincode is not needed. It
probably has some qualitative advantage in practice, but not very much.

Cheers,

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

Re: [bitcoin-dev] Suggestion: Solve year 2106 problem by taking timestamps mod 2^32

[Pieter Wuille via bitcoin-dev]

On Saturday, September 19, 2020 5:36 AM, yanmaani--- via bitcoin-dev 
 wrote:

> Currently, Bitcoin's timestamp rules are as follows:
>
> 1.  The block timestamp may not be lower than the median of the last 11
> blocks'
>
> 2.  The block timestamp may not be greater than the current time plus two
> hours
>
> 3.  The block timestamp may not be greater than 2^32 (Sun, 07 Feb 2106
> 06:28:16 +)
>
> Thus, Bitcoin will "die" on or about 2106-02-07, when there is no
> timestamp below 2^32 that exceeds the median of the last 11 blocks.
>
> If the rules were changed to the following, this problem would be
> solved:
>
> 4.  The block timestamp plus k*2^32 may not be lower than the median of
> the last 11 blocks'
>
> 5.  The block timestamp plus k*2^32 may not be greater than the current
> time plus two hours
>
> 6.  k is an integer, whose value must be the same for the calculations of
> Rule 1 and Rule 2

I believe that is equivalent to: we treat block headers (as abstract data
structure) as having a 64-bit timestamp, which have the requirement that
the difference between the timestamp and the median timestamp of the past 11
blocks is at least one and at most 2^32 (I don't think we need to support
less than 6 blocks per 136 years).

On serialization, only the lower 32 bit are encoded. On deserialization,
the higher 32 bits are set equal to that of the median of the past 11 blocks.
If that violates the rule above, set it one higher.

That's in line of how I'd expect this will eventually be addressed. There is
no rush, of course.

> What do you think of this idea? Is it worth a BIP?

Probably, at some point.

Cheers,

--
Pieter

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

Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173)

[Pieter Wuille via bitcoin-dev]

Hi Rusty,

thanks for starting this thread. We definitely should make a decision around
this soon.


On Wednesday, October 14, 2020 6:40 PM, Rusty Russell via bitcoin-dev 
 wrote:
> > > Here's a summary of each proposal:
> > > Length restrictions (future segwits must be 10, 13, 16, 20, 23, 26, 29,
> > > 32, 36, or 40 bytes)
> > >
> > > 1.  Backwards compatible for v1 etc; old code it still works.
> > > 2.  Restricts future segwit versions, may require new encoding if we
> > > want a diff length (or waste chainspace if we need to have a padded
> > > version for compat).
> > >
> > > Checksum change based on first byte:
> > >
> > > 1.  Backwards incompatible for v1 etc; only succeeds 1 in a billion.
> > > 2.  Weakens guarantees against typos in first two data-part letters to
> > > 1 in a billion.[1]
> > >

> If we go for option 2, v1 (generated from bitcoin core) will simply fail
> the first time you try test it. So it will force an upgrade. There
> are fewer places generating addresses than accepting them, so this
> seems the most likely scenario.
>
> OTOH, with option 1, anyone accepting v1 addresses today is going to
> become a liability once v1 addresses start being generated.

Today, no witness v1 receivers exist. So it seems to me the only question
is what software/infrastructure exist that supports sending to witness v1,
and whether they (and their userbase) are more or less likely to upgrade
before receivers appear than those that don't.

Clearly if only actively developed software currently supports sending to
v1 right now, then the question of forward compatibility is moot, and I'd
agree the cleanliness of option 2 is preferable.

Does anyone have an up-to-date overview of where to-future-witness sending
is supported? I know Bitcoin Core does.

> > It took a lot of community effort to get widespread support for bech32
> > addresses. Rather than go through that again, I'd prefer we use the
> > backwards compatible proposal from BIPs PR#945 and, if we want to
> > maximize safety, consensus restrict v1 witness program size, e.g. reject
> > transactions with scriptPubKeys paying v1 witness programs that aren't
> > exactly 32 bytes.
>
> Yes, I too wish we weren't here. :(
>
> Deferring a hard decision is not useful unless we expect things to be
> easier in future, and I only see it getting harder as time passes and
> userbases grow.

Possibly, but in the past I think there has existed a pattern where adoption
of new technology is at least partially based on certain infrastructure
and codebases going out of business and/or being replaced with newer ones,
rather than improvements to existing ones.

If that effect is significant, option 1 may be preferable: it means less
compatibility issues in the short term, and longer term all that may be
required is fixing the spec, and waiting long enough for old/unmaintained code
to be replaced.

As for how long: new witness version/length combinations are only rarely needed,
and there are 14 length=32 ones left to pick. We'll likely want to use those
first anyway, as it's the cheapest option with 128-bit collision resistance.
Assuming future constructions have something like BIP341's leaf versioning, new
witness version/length combinations are only required for:

* Changes to the commitment structure of script execution (e.g. Graftroot,
  different hash function for Merkle trees, ...)
* Upgrades to new signing cryptography (EC curve change, PQC, ...).
* Changes to signatures outside of a commitment structure (e.g. new sighash
  modes for the keypath in BIP341, or cross-input aggregation for them).

and in general, not for things like new script opcodes, or even for fairly
invasive redesigns of the script language itself.

> The good news it that the change is fairly simple and the reference
> implementations are widely used so change is not actually that hard
> once the decision is made.

Indeed. Whatever observations we had about adoption of base58 -> bech32 may not
apply because the change to a different checksum is fairly trivial compared to
that. Still, presence of production codebases that just don't update at all
may complicate this.

> > Hopefully by the time we want to use segwit v2, most software will have
> > implemented length limits and so we won't need any additional consensus
> > restrictions from then on forward.
>
> If we are prepared to commit to restrictions on future addresses.
>
> We don't know enough to do that, however, so I'm reluctant; I worry that
> a future scheme where we could save (e.g.) 2 bytes will impractical due
> to our encoding restrictions, resulting in unnecessary onchain bloat.

I'm opposed to consensus-invalidating certain length/version combinations, if
that's what you're suggesting, and I don't think there is a need for it.

TL;DR: what codebases/services/infrastructure exists today that supports
sending to witness v1 BIP173 addresses?

Cheers,

--
Pieter

___

Re: [bitcoin-dev] Progress on Miner Withholding - FPNC

[Pieter Wuille via bitcoin-dev]

On Wednesday, October 7, 2020 1:31 PM, Mike Brooks via bitcoin-dev 
 wrote:

> But first of all, I'd like to say that the idea for FPNC came out of a 
> conversation with ZmnSCPxj's in regards to re-org stability. When I had 
> proposed blockchain pointers with the PubRef opcode, he took the time to 
> explain to me concerns around re-orgs and why it is a bigger problem than I 
> initially had thought — and I greatly appreciate this detail. After touching 
> base with ZmnSCPxj and Greg Maxwell there is an overwhelming view that the 
> current problems that face the network outweigh any theoretical ones.

Greg Maxwell isn't on this list, but assuming this is about the conversion 
you've had on Bitcoin Core's security disclosure list, I believe this is a 
misrepresentation. The discussion has been mostly around a DoS attack report 
which turned out to be a mistake.

Cheers,

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

Re: [bitcoin-dev] Revisiting squaredness tiebreaker for R point in BIP340

[Pieter Wuille via bitcoin-dev]

On Friday, August 21, 2020 1:50 AM, John Newbery via bitcoin-dev 
 wrote:

> Summary: We should change the proposal and implementation to use even 
> tie-breakers everywhere.
>
> John #notoquadraticresiduetiebreakers Newbery

Thanks Nadav, Lloyd, John, and those who commented privately,

As the comments we've received have been unanimously in favor of changing, here 
is the PR for doing so: https://github.com/bitcoin/bips/pull/982

I'm very happy with this outcome, as it's indeed a significant reduction in the 
mental overhead needed for explaining the design decisions (the entire 
optimization section from the BIP can be removed, as those are no longer 
relevant to inform the decisions).

There is still some ongoing discussion about another change, namely permitting 
the use of messages that aren't exactly 32 bytes in length: 
https://github.com/sipa/bips/issues/207, but that would be a strict superset of 
what is permitted now, and have no impact on its use in BIP341/BIP342.

Cheers,

--
Pieter #thefinalfinalfinalbip340 Wuille___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Revisiting squaredness tiebreaker for R point in BIP340

[Pieter Wuille via bitcoin-dev]

On Wednesday, August 12, 2020 11:49 AM, Pieter Wuille  
wrote:

> It is late in the process, but I feel I owe this explanation so that at least 
> the possibility of changing can be discussed with all information.

As the responses have been pretty positive so far, we've gone ahead and made a 
patch to implement the change to the even tiebreaker: 
https://github.com/sipa/bips/pull/210

If there are no other arguments (against), I'll PR it to the BIPs repo in a 
week or so.

All comments/questions/... still welcome.

Cheers,

--
Pieter

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

[bitcoin-dev] Revisiting squaredness tiebreaker for R point in BIP340

[Pieter Wuille via bitcoin-dev]

Hello all,

The current BIP340 draft[1] uses two different tiebreakers for conveying the Y 
coordinate of points: for the R point inside signatures squaredness is used, 
while for public keys evenness is used. Originally both used squaredness, but 
it was changed[2] for public keys after observing this results in additional 
complexity for compatibility with existing systems.

The reason for choosing squaredness as tiebreaker was performance: in non-batch 
signature validation, the recomputed R point must be verified to have the 
correct sign, to guarantee consistency with batch validation. Whether the Y 
coordinate is square can be computed directly in Jacobian coordinates, while 
determining evenness requires a conversion to affine coordinates first.

This argument of course relies on the assumption that determining whether the Y 
coordinate is square can be done more efficiently than a conversion to affine 
coordinates. It appears now that this assumption is incorrect, and the 
justification for picking the squaredness tiebreaking doesn't really exist. As 
it comes with other trade-offs (it slows down signing, and is a less 
conventional choice), it would seem that we should reconsider the option of 
having the R point use the evenness tiebreaker (like public keys).

It is late in the process, but I feel I owe this explanation so that at least 
the possibility of changing can be discussed with all information. On the 
upside, this was discovered in the context of looking into a cool improvement 
to libsecp256k1[5], which makes things faster in general, but specifically 
benefits the evenness variant.


# 1. What happened?

Computing squaredness is done through the Jacobi symbol (same inventor, but 
unrelated to Jacobian coordinates). Computing evenness requires converting 
points to affine coordinates first, and that needs a modular inverse. The 
assumption that Jacobi symbols are faster to compute than inverses was based on:

* A (possibly) mistaken belief about the theory: fast algorithms for both 
Jacobi symbols and inverses are internally based on variants of the same 
extended GCD algorithm[3]. Since an inverse needs to extract a full big integer 
out of the transition steps made in the extgcd algorithm, while the Jacobi 
symbol just extracts a single bit, it had seemed that any advances applicable 
to one would be applicable to the other, but inverses would always need 
additional work on top. It appears however that a class of extgcd algorithms 
exists (LSB based ones) that cannot be used for Jacobi calculations without 
losing efficiency. Recent developments[4] and a proposed implementation in 
libsecp256k1[5] by Peter Dettman show that using this, inverses in some cases 
can in fact be faster than Jacobi symbols.

* A broken benchmark. This belief was incorrectly confirmed by a broken 
benchmark[6] in libsecp256k1 for the libgmp-based Jacobi symbol calculation and 
modular inverse. The benchmark was repeatedly testing the same constant input, 
which apparently was around 2.5x faster than the average speed. It is a 
variable-time algorithm, so a good variation of inputs matters. This mistake 
had me (and probably others) convinced for years that Jacobi symbols were 
amazingly fast, while in reality they were always very close in performance to 
inverses.


# 2. What is the actual impact of picking evenness instead?

It is hard to make very generic statements here, as BIP340 will hopefully be 
used for a long time, and hardware advancements and algorithmic improvements 
may change the balance. That said, performance on current hardware with 
optimized algorithms is the best approximation we have.

The numbers below give the expected performance change from squareness to 
evenness, for single BIP340 validation, and for signing. Positive numbers mean 
evenness is faster. Batch validation is not impacted at all.

In the short term, for block validation in Bitcoin Core, the numbers for 
master-nogmp are probably the most relevant (as Bitcoin Core uses libsecp256k1 
without libgmp, to reduce consensus-critical dependencies). If/when [5] gets 
merged, safegcd-nogmp will be what matters. On a longer time scale, the gmp 
numbers may be more relevant, as the Jacobi implementation there is certainly 
closer to the state of the art.

* i7-7820HQ: (verify) (sign)
  - master-nogmp: -0.3% +16.1%
  - safegcd-nogmp: +6.7% +17.1%
  - master-gmp: +0.6% +7.7%
  - safegcd-gmp: +1.6% +8.6%

* Cortex-A53: (verify) (sign)
  - master-nogmp: -0.3% +15.7%
  - safegcd-nogmp: +7.5% +16.9%
  - master-gmp: +0.3% +4.1%
  - safegcd-gmp: 0.0% +3.5%

* EPYC 7742: (verify) (sign)
  - master-nogmp: -0.3% +16.8%
  - safegcd-nogmp: +8.6% +18.4%
  - master-gmp: 0.0% +7.4%
  - safegcd-gmp: +2.3% +7.8%

In well optimized cryptographic code speedups as large as a couple percent are 
difficult to come by, so we would usually consider changes of this magnitude 
relevant. Note however that while the percentages for signing speed are 

Re: [bitcoin-dev] BIP-341: Committing to all scriptPubKeys in the signature message

[Pieter Wuille via bitcoin-dev]

Hi all,

On Tuesday, May 5, 2020 3:20 AM, Jonas Nick via bitcoin-dev 
 wrote:

> This is a reasonable suggestion. Committing to every spent scriptPubKey and
> therefore every element of the TxOut instead of just the amount makes sense
> conceptually. And it would be a small diff (~4 lines + rationale) compared to
> the current bip-taproot version.

I agree.

There have been several steps so far towards making it possible for signers to 
determine whether they can safely sign with just O(1) information per input. 
This was initially attempted in BIP141 (by committing to spent input, to thwart 
the ability to lie about fees to ofline signers), and is improved in the 
current BIP341.

I think the CoinJoin + offline signer model indeed shows that is still 
incomplete, as it is yet another example where a signer may need to be provided 
with the entire creating transaction, which would be very unfortunate.

It's also counter to the model proposed by BIP147 (PSBT) workflows: the 
assumption is effectively already that it is sufficient to provide signers with 
just amount + scriptPubKey of the spent outputs. It feels very natural that 
signatures then indeed also need to commit to all that data; otherwise there 
should be ways that this information can be undetectably wrong.

AJ's approach seems great. It means not increasing the per-signature hashing, 
while retaining the ability to cache information across BIP141/BIP341.

As for coinbaseness and height: these are indeed also things currently kept 
track of in the UTXO set, but I don't think any signer is using this 
information to determine whether to sign or not (which I think is the minimum 
requirement for it to be included in a signature hash, see above). Signing 
height would cripple the ability to spend unconfirmed outputs, or force signers 
to reveal they're doing so (if done through a separate sighash flag) - both of 
which would be undesirable. That leaves coinbaseness, but I think the utility 
is very low.

The only downside is that this potentially slows down review, but I agree with 
earlier comments that it's hard to see how this would hurt. I also think it's 
important to get these things right from the start. Many things inside 
BIP341/BIP342 are extensible with future softforks, but signature hashes for 
key-path spends is not one of them (the set of potential signature hash 
semantics must be committed to directly by the output, so changing them 
requires a new output type - which would be highly unfortunate for fungibility 
reasons).

Thus, unless there are objections, I'd like to go through with this and make 
the suggested changes.

Thoughts?

--
Pieter

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

Re: [bitcoin-dev] Mitigating Differential Power Analysis in BIP-340

[Pieter Wuille via bitcoin-dev]

On Tuesday, March 24, 2020 6:00 AM, Lloyd Fournier via bitcoin-dev 
 wrote:

> Hi List,
>
> I felt this topic deserved it's own thread but it follows on from the mailing 
> list post [2] announcing a new PR [1] to change BIP-340 in several ways, 
> including adding random auxiliary data into the nonce derivation function. 
> Rather than hashing the randomness with the secret key and message etc, the 
> randomness is hashed then XOR'd (^) with the secret key and the result is 
> hashed like so to determine the secret nonce k:
>
> (1) k = H_derive( sec_key ^ H_aux(rand) || pub_key_x || message)
>
> The claim made in the mailing list post is that this is more secure against 
> "differential power analysis" (DPA) attacks than just doing the simpler and 
> more efficient:
>
> (2) k = H_derive(sec_key || rand || pub_key_x || message)
>
> The TL;DR here is that I don't think this is the case.

Hi Lloyd,

Thank you for looking into this. I very much agree we haven't given nearly 
enough justification for the use of a non-standard scheme here.

I'll try to summarize the discussion we had that led to this choice, but most 
of it is on https://github.com/sipa/bips/issues/195 if you want the details.

Let me first try to address what I think you're overlooking: in a BIP32/Taproot 
like scenario, the private key that goes into the signing algorithm functions 
as *both* secret and known to the attacker. That is to say, there is a master 
secret s, and signing key x that goes into the hash is x=s+a (mod n) for some 
value a that the attacker knows, and can modify (he cannot control it directly, 
but he may be able to grind it to have a structure he likes). I believe that 
means that feeding x to a hash directly itself is already a problem, regardless 
of what else goes into the hash - interactions between bits inside the hash 
operation that all come from x itself can leak bit-level information of x.  
XORing (or any other simple mix operation that does not expose bit-level 
information) into the private key before giving it to a hash function seems 
like it would address this.

That said, all these DPA issues are very hard to reason about, as it's hard to 
find a realistic attack model that both (a) leaks some information but (b) 
doesn't obviously leak the entire key immediately. In the reasoning above I 
assumed an attacker who can observe word-level Hamming weight aggregates of all 
variables in the algorithm (which seems to match what one of the papers 
observed), but not bit level information. It also assumes that somehow the 
computation of x itself is immune from leaks (something you pointed out in a 
previous e-mail, I noticed).

So really, all of this is trying to choose one alternative among a set of (when 
ignoring DPA) nearly equally good constructions. Note that randomness is useful 
for protection against fault attacks, but for that purpose it doesn't matter 
where in the hash it goes, or even that it's particularly strong randomness (a 
counter would also work). There are a number of other concerns we discussed in 
the linked thread:
* Efficiency (how many SHA256 transformations, including the ability for some 
to be precomputed)
* The risk that the randomness added is correlated with the private key in a 
way that cancels things out when they're naively XORed together.
* The risk of having a midstate in the hash function leak (without leaking the 
actual private key, but enough to predict nonces).
* The issue with public keys that are input to the signing algorithm which come 
directly from an attacker (which is the reason why pubkey goes into the nonce 
function too).

The solution we came up with (H(priv XOR H(aux) || pub || msg)) is the only 
that ticks most of the boxes - but a different prioritization may certainly 
lead to a different conclusion.

I'm happy for any input you may have here. In particular, the recent 
discussions around the interactions between anti-covert channel protection, 
randomness, and the ability to spot check hardware devices may mean we should 
revise the advice to consider not adding randomness unless such a anti-covert 
channel scheme is used.

Cheers,

--
Pieter

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

[bitcoin-dev] Overview of anti-covert-channel signing techniques

[Pieter Wuille via bitcoin-dev]

Hi all,

Given the recent activity and attention [1,2] around anti-covert channel
signing schemes, I decided to create this overview of the various techniques
that I know of, their trade-offs, and the various issues they protect against.
Most of this is based on various schemes by a number of authors, and credit
goes to them. I'm putting this together into something hopefully more
comprehensive, but mistakes and omissions in this writeup are likely mine.

I don't believe we have security proofs for any of the schemes, or for any of
the claims I make about the mitigation techniques below. I hope that having
all properties written up in one place makes it easier to eventually get those.

1) Security model
-

When talking about signing with covert channels, we consider 3 parties:
* HW, the hardware wallet (or other offline signing device) with secret data
  (a private key, or a seed from which the private key is derived).
* SW, the software wallet (or whatever communicates with HW and the network).
* OO, the outside observer who is trying to learn information about HW's
  secret data.

We consider two distinct attack models:
* MSW, "malicious software wallet", but with honest HW. OO and SW are the
  same party here, so this models the usual scenarios hardware wallets are
  designed for, including side-channel attacks if those are considered to be
  part of the threat model.
* MHW, "malicious hardware wallet", but with honest SW and no malicious party
  being able to communicate with HW directly. OO and HW may have shared secret
  information that SW (or anyone else) is unaware of. SW's job is trying to
  prevent HW from using this to leak any information about its secret.

When both the HW and the SW are compromised, clearly no security is possible,
as all entities are controlled by the same party in that case.

In case HW uses a deterministic algorithm, it is possible to protect against
the MHW case by spot checking HW's behavior, by using an externally known
secret/seed. However, we'd like to have better than just spot checking
security, and for protection against side-channel attacks we may want
something that keeps working even when randomness is used by HW.

To keep the scope limited, we assume SW has no secret key of their own. This
rules out solutions like using 2-of-2 MuSig between HW and SW, which work, but
come with their own complications (like needing secure storage for that
secret).

2) Issues and solutions
---

In this section I will go over the various issues that exist in the MHW and MSW
models, the known mitigation techniques, and the resulting schemes.

I'm assuming a Schnorr-like signature protocol, though everything should apply
equally to ECDSA, and to a lesser extent probably also to multisignature
schemes. These variable names are used:
* H is a hash function.
* G is the curve generator.
* m is the message to be signed, known to and agreed upon by SW and HW.
* d is HW's secret key, with corresponding public key Q=dG.
* k is the secret nonce k, with corresponding public nonce R=kG.

The simplest protocol is naive Schnorr with deterministic nonce generation,
where SW only verifies that a signature created by HW is valid:

[Scheme 1: deterministic nonce, no tweak]
* SW requests a signature by sending (Q,m) to HW.
* HW computes k=H(d,m), R=kG, s=k+H(R,Q,m)d, and sends (R,s) to SW.
* SW verifies sG=R+H(R,Q,m)Q, and publishes sig (R,s) in case of success.

2.a) Predictable k value

There is a simple attack against Scheme 1 that will leak the entire private
key undetectably using a single signature, under MHW. Assume HW and OO both
have access to a shared secret a, unknown to anyone else. HW computes
k=H(a,Q,m) instead, which SW cannot distinguish from the honest k=H(d,m) as it
knows neither a or d. OO can compute k using the same formula, and thus
recover the private key as d=(s-k)/H(R,Q,m).

The general strategy to avoid this is by letting SW provide entropy that is
included into the nonce computation. A very naive (and ineffective) way of
doing that would be:
* SW generates random t, and requests a signature by sending (Q,m,t) to HW.
* HW computes k0=H(d,m,t), R0=k0G, k=k0+t, R=kG, s=k+H(R,Q,m)d, and sends
  (R0,R,s) to SW.
* SW verifies sG=R+H(R,Q,m)Q, R=R0+tG, and publishes sig (R,s) if all is good.

This does not help as HW can still choose k directly, and retroactively
compute R0 as R-tG, satsifying SW's requirements. To address that, there are
two options:
* Turning R into a binding commitment to R0 and t (see Scheme 2).
* Only revealing t after HW has revealed their R0 (see Scheme 3).

The first approach is based on making R a commitment to R0 and t using
R=R0+H(R0,t)G. When applied to public keys this is known as pay-to-contract
(and is the basis for Taproot); when applied to the R point in signatures it's
known as sign-to-contract [3]. These are generally useful approaches to make
public keys and signatures commit to/timestamp external data, but 

[bitcoin-dev] BIP 340 updates: even pubkeys, more secure nonce generation

[Pieter Wuille via bitcoin-dev]

Hello list,

Despite saying earlier that I expected no further semantical changes
to BIP 340-342, I've just opened
https://github.com/bitcoin/bips/pull/893 to make a number of small
changes that I believe are still worth making.

1. Even public keys

Only one change affects the validation rules: the Y coordinate of
32-byte public keys is changed from implicitly square to implicitly
even. This makes signing slightly faster (in the microsecond range),
though also verification negligibly slower (in the nanosecond range).
It also simplifies integration with existing key generation
infrastructure. For example BIP32 produces public keys with known
even/oddness, but squaredness would need to be computed separately.
Similar arguments hold for PSBT and probably many other things.

Note that the Y coordinate of the internal R point in the signature
remains implicitly square: for R the squaredness gives an actual
performance gain at validation time, but this is not true for public
keys. Conversely, for public keys integration with existing
infrastructure matters, but R points are purely internal.

This affects BIP 340 and 341.

2. Nonce generation

All other semantical changes are around more secure nonce generation
in BIP 340, dealing with various failure cases:

* Since the public key signed for is included in the signature
challenge hash, implementers will likely be eager to use precomputed
values for these (otherwise an additional EC multiplication is
necessary at signing time). If that public key data happens to be
gathered from untrusted sources, it can lead to trivial leakage of the
private key - something that Greg Maxwell started a discussion about
on the moderncrypto curves list:
https://moderncrypto.org/mail-archive/curves/2020/001012.html. We
believe it should therefore be best practice to include the public key
also in the nonce generation, which largely mitigates this problem.

* To protect against fault injection attacks it is recommended to
include actual signing-time randomness into the nonce generation
process. This was mentioned already, but the update elaborates much
more about this, and integrates this randomness into the standard
signing process.

* To protect against differential power analysis, a different way of
mixing in this randomness is used (masking the private key completely
with randomness before continuing, rather than hashing them together,
which is known in the literature to be vulnerable to DPA in some
scenarios).

3. New tagged hash tags

To make sure that any code written for the earlier BIP text fails
consistently, the tags used in the tagged hashes in BIP 340 are
changed as well.

What do people think?

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

Re: [bitcoin-dev] Analysis of Bech32 swap/insert/delete detection and next steps

[Pieter Wuille via bitcoin-dev]

> > So my suggestion for the next steps are:
> >
> > -   Update BIP173 to include the insertion weakness as an erratum, and
> > the results of this analysis.
> >
>
> To clarify, this step does not modify anything about the implementation of 
> BIP173, only adds this as an additional erratum section?

Correct - just documenting the issue.

> > -   Amend segwit addresses (either by amending BIP173, or by writing a
> > short updated BIP to modify it) to be restricted to only length 20 or
> > 32 (as fixed-length strings are unaffected by the insertion issue, and
> > I don't think inserting 20 characters is an interesting error class).
>
> To clarify, this refers to all SegWit address versions from 1 to 15, as this 
> restriction exists for SegWit address v0?

Right, for v0 there is an inherent restriction to size 20 or 32
already, so this would only semantically change anything for version 1
through 16 (not 15).

> > -   Define a variant of Bech32 with the modified constant, so that
> > non-BIP173 uses of Bech32 can choose a non-impacted version if they
> > worry about this class of errors.
> >
>
> Okay, this probably needs to be raised in lightning-dev as well, for invoice 
> formats, as well as planned offers feature.

It seems BOLT11 already doesn't care very much about the error
detection properties, as it's using Bech32 outside its design
parameters (max length 90 characters).

> By my understanding, best practice for readers of Bech32-based formats would 
> be something like the below:
>
> 1.  Define two variants of checksum, the current Bech32 checksum and the 
> modified Bech32 checksum.
> 2.  Support both variants (software tries one first, then tries the other if 
> it fails).
> 3.  Flag or signal some deprecation warning if current Bech32 checksum was 
> detected.
> 4.  At some undefined point in the future, drop support for the current 
> Bech32 checksum.

I think it depends on the application and their tolerance to this sort
of errors. In some cases, these insertions may be detected already
with high probability (e.g. because of length restrictions, or the
fact that it adds random unstructured symbols at the end of the data
part).

> > -   Later, if and when we expect a need for non-32-byte witness programs
> > in the medium term, define an updated segwit address scheme that uses
> > the modified Bech32 variant.
>
> Okay, so we will only use the modified Bech32 if and only if we expect to 
> need a non-32-byte witness program for a particular non-0 SegWit version.

Exactly.

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

[bitcoin-dev] Analysis of Bech32 swap/insert/delete detection and next steps

[Pieter Wuille via bitcoin-dev]

Hi all,

I've made a writeup on Bech32's detection abilities, analysing how it
behaves in the presence of not just substitution errors, but also
swapping of characters, and insertions and deletions:
https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb

It shows that the "insert or delete a 'q' right before a final 'p'" is
in fact the only deviation from the expected at-most-1-in-a-billion
failure to detect chance, at least when restricted to the classes of
errors analyzed with various uniformity assumptions. There is some
future work left, such as analyzing combinations of insertions and
substitutions, but I would be surprising if additional weaknesses
exist there.

It also shows that changing one constant in Bech32 would resolve this
issue, while not affecting the error detection properties for other
classes of errors.

So my suggestion for the next steps are:
* Update BIP173 to include the insertion weakness as an erratum, and
the results of this analysis.
* Amend segwit addresses (either by amending BIP173, or by writing a
short updated BIP to modify it) to be restricted to only length 20 or
32 (as fixed-length strings are unaffected by the insertion issue, and
I don't think inserting 20 characters is an interesting error class).
* Define a variant of Bech32 with the modified constant, so that
non-BIP173 uses of Bech32 can choose a non-impacted version if they
worry about this class of errors.
* Later, if and when we expect a need for non-32-byte witness programs
in the medium term, define an updated segwit address scheme that uses
the modified Bech32 variant.

I believe that the impact on production systems will be minimal using
the above, as many wallets already do not accept unknown witness
versions in outputs, and it gives us probably years to adapt.

What do people think?

Cheers,

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

Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses

[Pieter Wuille via bitcoin-dev]

On Tue, Nov 12, 2019, 21:33 ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning all,
>
> It seems to me that adding the length for checksumming purposes need not
> require the length to be *actually* added in the address format.
>

Indeed!

This has the following properties:
>
> * The bech32 address format is retained, and no explicit length is added.
> * There are now two checksum formats: one with just the witness program,
> the other which validates with the witness program length.
>   * Readers that do not understand the new checksum format will simply
> reject them without mis-sending to the wrong witness program.
>

That's very close to what I was suggesting: create an improved bech32
algorithm and use that for future addresses, rather than working around the
problem in the address encoding while keeping the existing bech32 checksum.
Sorry if that wasn't clear from my previous email.

In this case, there is no need to even implicitly include the length in the
checksum algorithm. Replacing the "xor 1" at the end of the algorithm to
"xor (2^30 - 1)" would reduce the occurrence of this weakness from 1/32 to
1/2^30, and have no downsides otherwise. I'd like to do some analysis to
ascertain it actually will catch any other kind of insertion/deletion
errors with high probability as well before actually proposing it, though.

There are other solutions which do include the length in some fashion
directly in the checksum calculation, which may be preferable (I need to
analyse things...). It's also possible to do this in such a way that for
33-symbol and 53-symbol data parts (corresponding to P2WPKH and P2WSH
lengths) the new algorithm is defined as identical to the old one. That
would simplify upstream users of a bech32 library (which would then
effectively need no changes at all, apart from updating the
checksum/decoder code).

That brings me to Matt's point: there is no need to do this right now. We
can simply amend BIP173 to only permit length 20 and length 32 (and only
length 20 for v0, if you like; but they're so far apart that permitting
both shouldn't hurt), for now. Introducing the "new" address format (the
one using an improved checksum algorithm) only needs to be there in time
for when a non-32-byte-witness-program would come in sight.

Of course, I should update BIP173 to indicate the issue, and have a
suggested improvement for other users of bech32, if they feel this issue is
significant enough.

Cheers,

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

Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses

[Pieter Wuille via bitcoin-dev]

On Thu, Nov 7, 2019, 18:16 David A. Harding  wrote:

> On Thu, Nov 07, 2019 at 02:35:42PM -0800, Pieter Wuille via bitcoin-dev
> wrote:
> > In the current draft, witness v1 outputs of length other
> > than 32 remain unencumbered, which means that for now such an
> > insertion or erasure would result in an output that can be spent by
> > anyone. If that is considered unacceptable, it could be prevented by
> > for example outlawing v1 witness outputs of length 31 and 33.
>
> Either a consensus rule or a standardness rule[1] would require anyone
> using a bech32 library supporting v1+ segwit to upgrade their library.
> Otherwise, users of old libraries will still attempt to pay v1 witness
> outputs of length 31 or 33, causing their transactions to get rejected
> by newer nodes or get stuck on older nodes.  This is basically the
> problem #15846[2] was meant to prevent.
>
> If we're going to need everyone to upgrade their bech32 libraries
> anyway, I think it's probably best that the problem is fixed in the
> bech32 algorithm rather than at the consensus/standardness layer.
>

Admittedly, this affecting development of consensus or standardness rules
would feel unnatural. In addition, it also has the potential downside of
breaking batched transactions in some settings (ask an exchange for a
withdrawal to a invalid/nonstandard version, which they batch with other
outputs that then get stuck because the transaction does not go through).

So, Ideally this is indeed solved entirely on the bech32/address encoding
side of things. I did not initially expect the discussion here to go in
that direction, as that could come with all problems that rolling out a new
address scheme in the first place has. However, there may be a way to
mostly avoid those problems for the time being, while also not having any
impact on consensus or standardness rules.

I believe that most new witness programs we'd want to introduce anyway will
be 32 bytes in the future, if the option exists. It's enough for a 256-bit
hash (which has up to 128-bit collision security, and more than 128 bits is
hard to achieve in Bitcoin anyway), or for X coordinates directly. Either
of those, plus a small version number to indicate the commitment structure
should be enough to encode any spendability condition we'd want with any
achievable security level.

With that observation, I propose the following. We amend BIP173 to be
restricted to witness programs of length 20 or 32 (but still support
versions other than 0). This seems like it may be sufficient for several
years, until version numbers run out. I believe that some wallet
implementations already restrict sending to known versions only, which
means effectively no change for them in addition to normal deployment.

In the mean time we develop a variant of bech32 with better
insertion/erasure detecting properties, which will be used for witness
programs of length different from 20 or 32. If we make sure that there are
never two distinct valid checksum algorithms for the same output, I don't
believe there is any need for a new address scheme or a different HRP. The
latter is something I'd strongly try to avoid anyway, as it would mean
additional cognitive load on users because of another visually distinct
address style, plus more logistical overhead (coordination and keeping
track of 2 HRPs per chain).

I believe improving bech32 itself is preferable over changing the way
segwit addresses use bech32, as that can be done without making addresses
even longer. Furthermore, the root of the issue is in bech32, and it is
simplest to fix things there. The easiest solution is to simply change the
constant 1 that is xor'ed into the checksum before encoding it to a 30-bit
number. This has the advantage that a single checksum is never valid for
both algoritgms simultaneously. Another approach is to implicitly including
the length into the checksummed data.

What do people think?

Cheers,

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

[bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses

[Pieter Wuille via bitcoin-dev]

Hello all,

A while ago it was discovered that bech32 has a mutation weakness (see
https://github.com/sipa/bech32/issues/51 for details). Specifically,
when a bech32 string ends with a "p", inserting or erasing "q"s right
before that "p" does not invalidate it. While insertion/erasure
robustness was not an explicit goal (BCH codes in general only have
guarantees about substitution errors), this is very much not by
design, and this specific issue could have been made much less
impactful with a slightly different approach. I'm sorry it wasn't
caught earlier.

This has little effect on the security of P2WPKH/P2WSH addresses, as
those are only valid (per BIP173) for specific lengths (42 and 62
characters respectively). Inserting 20 consecutive "p"s in a typo
seems highly improbable.

I'm making this post because this property may unfortunately influence
design decisions around bip-taproot, as was brought up in the review
session 
(https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-October/017427.html)
past tuesday. In the current draft, witness v1 outputs of length other
than 32 remain unencumbered, which means that for now such an
insertion or erasure would result in an output that can be spent by
anyone. If that is considered unacceptable, it could be prevented by
for example outlawing v1 witness outputs of length 31 and 33.

Thoughts?

Cheers,

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

[bitcoin-dev] Taproot updates

[Pieter Wuille via bitcoin-dev]

Hi all,

I wanted to give an update on some of the changes we've made to the
bip-schnorr/taproot/tapscript drafts following discussions on this
list:
* The original post:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016914.html
and follow-ups
* Using 2 or 4 byte indexes:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-June/017046.html
* 32-byte public keys:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-August/017247.html
* Resource limits:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-September/017306.html
* P2SH support or not:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-September/017297.html).

We've made the following semantical changes to the proposal:
* 32-byte public keys everywhere instead of 33-byte ones: dropping one
byte that provably does not contribute to security, while remaining
compatible with existing BIP32 and other key generation algorithms.
* No more P2SH support: more efficient chain usage, no gratuitous
fungibility loss from having 2 versions, no mode limited to 80-bit
security for non-interactive multiuser constructs; however senders
will need bech32 support to send to Taproot outputs.
* 32-bit txin position and codesep position indexes instead of 16-bits ones.
* Tagged hashes also in bip-schnorr: the signature and nonce
generation now also use tagged hashes, rather than direct SHA256
(previously tagged hashes were only used in bip-taproot and
bip-tapscript)
* Dropping the 1 byte script limit and 201 non-push opcode limit:
as no operations remain whose validation performance depends on the
size of scripts or number of executed opcodes, these limits serve no
purpose, but complicate creation of Scripts.
* Increased the limit on the depth of Merkle trees from 32 to 128: a
limit of 32 would necessitate suboptimal trees in some cases, but more
than 128 levels are only necessary when dealing with leaves that have
a chance of ~1/2^128 of being executed, which our security level
treats as impossible anyway.

See the updated documents:
* https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
* https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki
* https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki

In addition, a lot of clarifications and rationales were added. The
reference implementation on
https://github.com/sipa/bitcoin/commits/taproot was also updated to
reflect these changes, has a cleaner commit history now, and improved
tests (though those can still use a lot of work).

Cheers,

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

Re: [bitcoin-dev] Taproot proposal

[Pieter Wuille via bitcoin-dev]

On Mon, 16 Sep 2019 at 21:10, ZmnSCPxj via bitcoin-dev
 wrote:

> ‐‐‐ Original Message ‐‐‐
> > I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for 
> > segwit
> > v0 for compatibility reasons. Most wallets/exchanges/services now support 
> > sending
> > to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption) and 
> > that
> > will be even more true if Schnorr/Taproot activate in 12+ months time.
> >
> > Apologies for necroing an ancient thread, but I'm echoing my agreement with 
> > John here.
> > We still have plenty of time to have ecosystem upgrade by the time taproot 
> > is likely to activate.

> On the other hand, the major benefit of taproot is the better privacy and 
> homogeneity afforded by Taproot, and supporting both P2SH-wrapped and 
> non-wrapped SegWit v1 addresses simply increases the number of places that a 
> user may be characterized and potentially identified.

I'm starting to lean towards not allowing P2SH wrapped Taproot as well.

Given the progress bech32 adoption has made in the past year or so, I
don't think adding P2SH support would result in many more software
authors deciding to implement receive-to-taproot functionality. And
without that advantage, having the option of supporting P2SH wrapping
actually risks degrading the privacy goals it aims for (see ZmnSCPxj's
argument above).

My main intuition for keeping P2SH is that Segwit was really designed
to support both, and I expect that disallowing P2SH would actually
require (very slightly) more complex validation code. I don't think
this is a sufficiently strong reason, especially as keeping P2SH
support does increase the number of combinations software needs to
test (both in consensus code and wallets).

Cheers,

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

[bitcoin-dev] bip-tapscript resource limits

[Pieter Wuille via bitcoin-dev]

Hi all,

In the draft for bip-tapscript (see [1], current version [2]), we
propose removing the per-block sigops limit for tapscript scripts, and
replacing it with a "every script gets a budget of sigops based on its
witness size (one per 50 WU)". Since signatures (plus pubkeys) take
more WU than that, this is not a restriction for anything but
pathologically constructed scripts. Simultaneously, it removes the
multi-dimensional optimization problem that theoretically needs to be
solved to maximize revenue in block template construction.

With our recent work on Miniscript (see [3]), we discovered that the
variety of other script resource limits also introduce (weaker)
complex optimization requirements, but for script constructors instead
of miners. An overview:
1) Scripts are limited to 1 bytes (and 3600 by standardness currently)
2) The total number of non-push opcodes in a script + the number of
keys participating in executed OP_CHECKMULTISIG(VERIFY) opcodes must
not exceed 201.
3) The size of the stack + altstack combined cannot exceed 1000
elements during execution (and the initial stack is limited to 100
elements by standardness currently)
4) The maximum size of elements on the stack is 520 bytes (and 80
bytes in the initial stack by standardness)

In a discussion about this with Andrew Poelstra we wondered whether
all these limits are still necessary in bip-tapscript. I believe the
only relevant ones are those that reduce total memory usage, or
verification CPU usage per witness byte. Total script verification CPU
usage isn't relevant I believe, because the same effect can be
accomplished by having a transaction (or block) with multiple inputs.

So let's go over the above resource limits, and see how they help with
limiting memory usage or CPu usage per byte.

# Script size limit

Memory usage for validation can grow with larger scripts, but only
indirectly by constructing extra stack data. Since those are
independently limited by (3), we don't need to consider those here.

There used to be a way through which larger scripts would cause larger
per byte verification cost, but it no longer applies, I believe. Due
to the scriptCode being replaced with a pre-hashed tapleaf hash, the
per-sigop hashing cost is now easily made independent of the size of
the script in implementations.

My suggestion is to drop the script size limit in tapscript, and
instead have it only be implicitly limited by transaction size limits.

# The 201 non-push opcodes limit

Ignoring how more opcodes can grow the stack and altstack (which are
already restricted by 3), I believe there is only one way that
additional (executed) opcodes can increase per-opcode execution time
in the current Bitcoin Core implementation [4], namely the "vfExec"
stack that keeps track of what sides of IF/NOTIF/ELSE/ENDIF execution
is currently passing through. As pointed out by Sergio Demian Lerner
[5], an O(1) algorithm can do this just as well (a variant of which is
implemented in PR 16902 [6]).

Taking such a patch into account, I don't think there are any problems
with removing the 201 ops limit for bip-tapscript scripts. Especially
given its strange semantics around OP_CHECKMULTISIG(VERIFY) (the keys
participating in those are each counted as 1 towards the 201 limit,
but only when executed, while all non-push opcodes are counted as 1
even when not executed), I think this is a nice simplification.

# The 1000 element limit for stack + altstack

A limit for the number of elements on the stack/altstack directly
affects memory usage. In a naive implementation without deduplication
as is used in Bitcoin Core now, every OP_3DUP can add 120 bytes of
memory usage plus the size of the data in the created elements
themselves (which can be a multiple of that number), leading to
several GB of memory usage for executing a maximal 4 MB script
(multiplied by the number of parallel executions). Even when using
reference-counting techniques to reduce duplication, 100 MB memory
usage is not unreasonable. I don't think those are acceptable numbers.

The stack size can also directly affect per-opcode execution time for
OP_ROLL, again shown by [5]. A block full of the most tightly packed
OP_ROLLS (which I believe is a repetition of OP_3DUP OP_ROLL OP_ROLL
OP_ROLL) operating on a stack of 1000 elements for me takes around 4.3
s of CPU time to verify. That's significant, but it's surprisingly
close to what a block packed with OP_CHECKSIGs (taking the 1 sigop /
50 WU limit into account) takes to verify on the same machine (3.8 s).
Even more remarkably, that time is also very close to how long a block
full of most tightly packed OP_HASH256s on 520 byte inputs take to
verify when disabling SHA256 hardware acceleration (3.6 s).

I believe we should keep this 1000 element stack limit for these
reasons. The 100 limit on input stacks can be increased to 1000 for
uniformity with the during-execution limit.

# The 520 byte stack element size limit

Given that there are no 

Re: [bitcoin-dev] testing bitcoin nodes

[Pieter Wuille via bitcoin-dev]

On Tue, 6 Aug 2019 at 09:57, Niels Thijssen via bitcoin-dev
 wrote:
>
> Hi,
>
> I'm working as (software) test specialist and run private a full bitcoin node 
> (based upon Raspberry Pi 4).
> I've been trying to figure out the tests performed during 
> installation/upgrade/compilation of the software for the node.
> Is there any overview on what's the (common) test approach, or other stuff. 
> Because the tests on GitHub don't help me that much.
> I'd like to figure out what/how is tested, maybe refine test cases, and try 
> some manual test also, as part of learning.

Hi Niels,

You're probably not getting many answers because this isn't the right
place to ask. The mailinglist is about development of the Bitcoin
protocol and conventions about its usage across multiple applications.
If you want to learn about the Bitcoin Core software and its testing
infrastructure, see https://bitcoincore.org/en/contribute/

Cheers,

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

[bitcoin-dev] Miniscript

[Pieter Wuille via bitcoin-dev]

Hi all,

Miniscript is a project we've been working on for the past year or so,
and is now at a stage where I'd like to get it some more attention. It is joint
work with Andrew Poelstra and Sanket Sanjalkar.

It's a language for writing (a subset of) Bitcoin Scripts in a structured way,
enabling analysis, composition, generic signing and more.

For example the script

   OP_CHECKSIG OP_IFDUP OP_NOTIF OP_DUP OP_HASH160 
  OP_EQUALVERIFY OP_CHECKSIGVERIFY <144> OP_CSV OP_ENDIF

in Miniscript notation would be

  or_d(c:pk(A),and_v(vc:pk_h(B),older(144)))

making it human (engineer?) readable that this is a script that permits A to
take the coins at any time, and B after 1 day. A full description of the
language can be found on the project website http://bitcoin.sipa.be/miniscript

Using Miniscript it's possible to:
* Write descriptors for addresses for scripts that implement things more
  complicated than multisig.
* Make software that can deal with composition of policies (e.g. have funds
  in a 2-of-3 setup where one of the 3 "keys" is itself a policy that involves
  perhaps multiple devices and timeouts).
* Compile complex spending policies to efficient scripts.
* Figure out under what necessary and/or sufficient conditions a script can be
  satisfied.
* Given signatures for a sufficient set of keys (and hash preimages, if needed),
  generically construct a witness for arbitrary scripts, without metadata
  apart from the script itself and public keys appearing in it. This means
  generic PSBT signers are possible for this class of scripts.
* Compute the bounds on the size of a witness for arbitrary scripts.
* Perform static analysis to see if any of Script's resource limitations
  (ops limit, stack size, ...) might interfere with the ability to spend.
* Who knows what else...

We have two implementations:
* a C++ one (https://github.com/sipa/miniscript)
* a Rust library (https://github.com/apoelstra/rust-miniscript).

The implementations are a work in progress, but through large scale randomized
tests we have confidence that the language design and associated witnesses are
compatible with the existing consensus and standardness rules.

To be clear: Miniscript is designed for Bitcoin as it exists today (primarily
P2WSH), and does not need any consensus changes. That said, we plan to extend
the design to support future script changes Bitcoin may include.

Cheers,

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

Re: [bitcoin-dev] Taproot proposal

[Pieter Wuille via bitcoin-dev]

On Fri, 9 Aug 2019 at 08:02, Elichai Turkel via bitcoin-dev
 wrote:
>
> Hi,

Since the idea of implicitly even pubkeys has potentially more general
implications, I've started a separate thread [1] about that idea.

> I want to add to John Newbery's suggestion of using implicit even/odd only 
> public keys and tweaked public keys in taproot and suggest the following:
> If everything is implicit then the only reason for the first byte of the 
> control block(`c[0]`) is the tapscript leaf version.

That's unfortunately not correct. If we want to maintain
batch-verifiability of the taproot tweaking (the Q = P + H(P,m)G
relation), we still need a bit in the control block to convey whether
a negation was necessary to make P+H(P,m)G even, even if P and Q both
have implied-even Y coordinates. Not doing that would require
exploring 2^n combinations to batch verify n relations, obviously
destroying any performance savings the batch verification had in the
first place.

> I suggest that this is moved to be the first OP_CODE of the tapscript itself 
> (i.e. OP_0/OP_1 etc.)
> That way having the script *tells* you what does it mean without needing to 
> check the control block.
> That way there's a separation between the tapscript+leaf version and the 
> control block being the merkle path to the script.

If we keep the leaf version idea (it's possible to instead just rely
entirely on OP_SUCCESSx, and drop leaf versions), my preference is to
still keep it separate from script, though just for a fairly banal
reason: that way the script consists entirely of opcodes and can be
treated uniformly by debug tools, rather than needing to treat the
first byte special. I do understand your preference too, but I don't
know how it weighs up.

  [1] 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-August/017247.html

Cheers,

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

[bitcoin-dev] 32-byte public keys in Schnorr and Taproot

[Pieter Wuille via bitcoin-dev]

Hello all,

It has been suggested [1] to drop the Y oddness bit in the witness
program for Taproot outputs. This seems like a worthwhile change, as:
* The bit doesn't actually contribute to security.
* It avoids Taproot outputs from being more expensive to create than v0 P2WSH.
* It doesn't preclude future changes that would still need the
additional byte anyway.

In exploring that option, Jonas Nick found that it seems cleanest [2]
to actually introduce a type of 32-byte public keys (which implicitly
have an even Y coordinate) in bip-schnorr, with associated signing and
verification logic that are distinct from the 33-byte variant.

This makes me wonder if we need 33-byte public keys at all.

So I'd like to hear opinions about modifying bip-schnorr to only
define 32-byte public keys. The implications of that would be:
* bip-schnorr public keys wouldn't be exactly the same as ECDSA public
keys, however all derivation logic would still apply (BIP32,
mnemonics, xpubs, ... would still exist and be compatible - just the
first pubkey byte would be dropped at the end).
* The Q point in bip-taproot (the one going in the scriptPubKey) would
just follow the 32-byte pubkey encoding, rather than needing a 33rd
byte.
* The P point in bip-taproot (the internal key revealed during script
path) would become just a 32-byte public key (and we can drop the one
bit in the control block to transmit the oddness of the Y coordinate
of P).
* In order to permit batch verification of the P to Q tweaking for
script-path spending, another control block bit is now needed, namely
one that indicates whether a negation was needed to make P+H(P||m)*G's
Y coordinate even.
* All public keys inside bip-tapscript would also become 32-bytes. If
desired, the "upgradable public key" construction in bip-tapscript can
be kept, by triggering based on the length of public keys (rather than
based on their first byte).

One question is whether it's worth such a change to bip-schnorr at
this point. We've purposefully never progressed it past draft since
publishing [3], but it has been a while. If necessary, it's possible
to keep verification compatible by still hashing the implied "even"
byte inside the scheme (which commits to the pubkey), but if we're
going to change things, it's perhaps best to do it as cleanly as
possible and also drop that byte.

Opinions?

  [1] 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016943.html
  [2] https://github.com/sipa/bips/pull/52
  [3] 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html

Cheers,

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

Re: [bitcoin-dev] PubRef - Script OP Code For Public Data References

[Pieter Wuille via bitcoin-dev]

On Fri, Jul 19, 2019, 12:13 William Casarin via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
> Hello Mike,
>
> Mike Brooks via bitcoin-dev 
> writes:
>
> > Motivation
> >
> > Giving scripts the ability to refer to data on the blockchain will reduce
> > transaction sizes because key material does not have to be repeated in
> > every Script. Users of the network are rewarded with smaller transaction
> > sizes, and miners are able to fit more transactions into new blocks.
> > Pointers are a common feature and it felt like this was missing from
> > Bitcoin Script.
>
> This would incentivize address re-use which would be bad for
> fungibility. It appears you're trying to optimize a use case which is
> already discouraged :(
>

Furthermore, right now block validation does not require access to the
whole historical chain (only to the set of unspent outputs), so a change
like this would massively increase storage requirements for validation.

Cheers,

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

Re: [bitcoin-dev] Two questions about segwit implementation

[Pieter Wuille via bitcoin-dev]

On Sun, May 26, 2019, 07:07 Aymeric Vitte via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> I realized recently that my segwit implementation was not correct,
> basically some time ago, wrongly reading the specs (and misleaded by
> what follows), I thought that scriptsig would go into witness data as it
> was, but that's not the case, op_pushdata is replaced by varlen
>
> Now reading correctly the specs, they seem to be not totally correct,
> then the first question is: why OP_0 is 00 in witness data and not 0100?
> Does this apply to other op_codes? This does not look logical at all
>
> The second question is: why for non segwit inputs there is a 00 length
> in segwit data, what is the rational for that? It should just be nothing
> since you don't need this to reconciliate things
>

This is a question that belongs on https://bitcoin.stackexchange.com, not
this list.

Cheers,

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

Re: [bitcoin-dev] OP_DIFFICULTY to enable difficulty hedges (bets) without an oracle and 3rd party.

[Pieter Wuille via bitcoin-dev]

On Thu, 23 May 2019 at 11:33, Tamas Blummer via bitcoin-dev
 wrote:
>
> Difficulty change has profound impact on miner’s production thereby introduce 
> the biggest risk while considering an investment.
> Commodity markets offer futures and options to hedge risks on traditional 
> trading venues. Some might soon list difficulty futures.
>
> I think we could do much better than them natively within Bitcoin.
>
> A better solution could be a transaction that uses nLocktime denominated in 
> block height, such that it is valid after the difficulty adjusted block in 
> the future.
> A new OP_DIFFICULTY opcode would put onto stack the value of difficulty for 
> the block the transaction is included into.
> The output script may then decide comparing that value with a strike which 
> key can spend it.
> The input of the transaction would be a multi-sig escrow of those who entered 
> the bet.
> The winner would broadcast.

If the difficulty can be directly observed by the script language, you
would need to re-evaluate all scripts in unconfirmed transactions
whenever the difficulty changes. This complicates implementation of
mempools, but it also makes reasoning about validity of (chains of)
unconfirmed transactions harder, as an unconfirmed predecessor may
have conditions that change over time.

For things like block time/height, this is solved by not having the
script itself observe the context state directly, but instead having
an assertion on the state outside of script (nLockTime for absolute
time/height and nSequence for relative), and then having opcodes
inside script that observe the assertion (OP_CLTV and OP_CSV). By
doing so, script validity is a single context-free yes or not that can
be evaluated once, and the variable part is just transaction-level
reasoning that doesn't involve a full script interpreter.
Additionally, the supported assertions are restricted in such a way
that if they are true within a particular block, they're also true in
any descendant, removing the complexity of reasoning about validity
(apart from the inevitable reasoning about possible double-spend
before confirmation).

I feel a similar construction is needed for observing block
difficulty. This can be done by either having an opcode that as a side
effect of execution "posts" an assertion (e.g. "difficulty at block
height X is at least Y"), instead of putting the difficulty on the
stack. An alternative is having the assertion be part of the
transaction structure (for example in the annex we propose in
bip-taproot), and having an opcode that observes the difficulty
assertion inside script.

I don't have a strong opinion either way on the usefulness of having
difficulty-dependent transaction/scripts.

Cheers,

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

Re: [bitcoin-dev] Taproot proposal

[Pieter Wuille via bitcoin-dev]

On Tue, 21 May 2019 at 10:20, Russell O'Connor  wrote:
>
> Regarding Tapscript, the specification calls for the final value of the stack 
> being a single non-false value:
>
>> The tapscript is executed according to the rules in the following section, 
>> with the initial stack as input
>> II. If the execution results in anything but exactly one element on the 
>> stack which evaluates to true with CastToBool(), fail.
>
> Perhaps it is worth taking this opportunity here to remove a minor wart of 
> the Script language and instead require the stack to be exactly empty upon 
> completion.
>
> In addition to removing a potential malleability vector, I expect it would 
> simplify development of Bitcoin Script.  A rule requiring an empty stack 
> means that the conjunction (logical and) of two policies can be implemented 
> by the simple concatenation of Bitcoin Scripts.  This combined with the 
> taproot ability to form the disjunction (logical or) of policies by having 
> multiple Merkle branches, means that the translation of a policy written in 
> disjunctive normal form (the logical ors of logical ands of primitive 
> policies) can be straightforwardly translated to a taproot of tapscript.
>
> That said, I think the developers of miniscript 
>  are in a much better 
> position to comment on whether my above intuition is correct given that 
> they've had to implement a host of various calling conventions.  I understand 
> that at least some of this complexity is due to Bitcoin Script's one element 
> stack rule.

IIRC I looked into this a few months ago, and found that the spending
cost (script size + expected witness size) of the optimal script for
every Miniscript policy at most changes by 1 WU (in either direction)
by requiring an empty stack rather than a true value, though in a
(admittedly very arbitrarily biased) distribution, more policies were
improved by it than degraded. This is not taking Taproot into account
(as many of those policies in a Taproot-supporting world should
optimally make use of the internal key and Merkle tree, rather than
turning everything into a monolithic script). I expect that this may
make the impact somewhat larger, but still never more than a 1 WU
gain.

I don't think the spending cost changes justify this change, so the
remaining criteria are complexity ones. In my view, the main benefit
would be to authors of hand-written scripts where the consistency
benefits matter, but this needs to be weighed against the mental cost
of learning the new semantics. For Miniscript itself, this doesn't
make much difference - the top level calling convention would become
'V' instead of 'T', but 'T' would still exist as a calling convention
that may be used internally; it's a few lines change.

So overall this feels like something with marginal costs, but also at
most marginal benefits. Perhaps other people have stronger opinions.

> Even if we choose not to implement the empty stack rule, we should at least 
> require that the last element be 0x01 to remove a potential malleability 
> vector and bring it in line with MINIMAL_IF semantics.

This feels like the right thing to do; as we're making MINIMALIF part
of consensus for Tapscript it would make sense to apply the same rule
to the "return" value of the script. There is a downside though,
namely that in some places where you'd use "
OP_CHECKSEQUENCEVERIFY" or " OP_CHECKLOCKTIMEVERIFY" you now need
to add an additional OP_0NOTEQUAL to convert the left-over element n
into an exact 0x01. I also can't come up with any practical benefits
that this would have; if the top stack element in a particular code
path comes directly from the input, it's insecure regardless; if there
isn't, it'll generally be a a boolean (or an intentional non-boolean
true value) computed by the script.

On Tue, 21 May 2019 at 13:05, John Newbery  wrote:
>
> Hi,
>
> > A Taproot output is a SegWit output [...]  with
> > version number 1, and a 33-byte witness program whose first byte is 0 or 1.
>
> Given a secret key k and public key P=(x,y), a signer with the knowledge of k
> can sign for -P=(x,p-y) since -k is the secret key for that point. Encoding 
> the
> y value of the public key therefore adds no security.

That's a good point; without security benefit there's no reason to
make pay-to-taproots more expensive. Making them the same cost as
P2WSH is nice in any case.

> As an alternative to
> providing the y value of the taproot output key Q when constructing the 
> taproot
> output, the signer can provide it when signing. We can also restrict the y 
> value
> of the internal key P to be even (or high, or a quadratic residue). That gives
> us 4 options for how to set the y signs for P and Q.
>
> 1. Q sign is explictly set in the witness program, P sign is explicitly set 
> in the control block
> => witness program is 33 bytes, 32 possible leaf versions (one for each 
> pair of 0xc0..0xff)
> 2. Q sign is 

Re: [bitcoin-dev] Taproot proposal

[Pieter Wuille via bitcoin-dev]

Thanks for the comments so far!

I'm going to respond to some of the comments here. Things which I plan
to address with changes in the BIP I'll leave for later.

On Mon, 6 May 2019 at 13:17, Luke Dashjr  wrote:
> Tagged hashes put the tagging at the start of the hash input. This means
> implementations can pre-cache SHA2 states, but it also means they can't reuse
> states to produce data for different contexts. (I'm not sure if there is a
> use for doing so... but maybe as part of further hiding MAST branches?)

It's true you can't cache/precompute things across tags, but I also
think there is no need. The type of data hashed in a sighash vs a
merkle branch/leaf vs a tweak is fundamentally different. I think this
is perhaps a good guidance to include about when separate tags are
warranted vs. simply making sure the input does not collide: there
shouldn't be much or any shared data with things that are expected to
be inputs under other tags.

> Is there any way to use the Taproot construct here while retaining external
> script limitations that the involved party(ies) *cannot* agree to override?
> For example, it is conceivable that one might wish to have an unconditional
> CLTV enforced in all circumstances.

Yes, absolutely - you can use a point with unknown discrete logarithm
as internal key. This will result in only script path spends being
available. For the specific goal you're stating an alternative may be
using a valid known private key, using it to pre-sign a timelocked
transaction, and destroying the key.

> It may be useful to have a way to add a salt to tap branches.

If you don't reuse public keys, effectively every branch is
automatically salted (and the position in the tree gets randomized
automatically when doing so, providing a small additional privacy
benefit).

>> Some way to sign an additional script (not committed to by the witness
>> program) seems like it could be a trivial addition.
> This would be especially useful for things like OP_CHECKBLOCKATHEIGHT:
> https://github.com/bitcoin/bips/blob/master/bip-0115.mediawiki

If you're talking about the ability to sign over the ability to spend
to another script ("delegation"), there are lots of interesting
applications and ways to implement it. But it overlaps with Graftroot,
and doing it efficiently in general has some interesting and
non-obvious engineering challenges (for example, signing over to a
script that enforces "f(tx)=y" for some f can be done by only storing
f and then including y in the sighash).

For the specific example of BIP115's functionality, that seems like a
reasonable thing that could be dealt with using the annex construction
in the proposed BIP. A consensus rule could define a region inside the
annex that functions as a height-blockhash assertion. The annex is
included in all sighashes, so it can't be removed from the input;
later opcodes could include the ability to inspect that assertion
even.

On Tue, 7 May 2019 at 13:43, Sjors Provoost  wrote:
> One reason why someone would want to avoid a "everone agrees" branch, is 
> duress (or self-discipline, or limiting powers of a trustee). In particular 
> with respect to time-locks.>

Indeed, though as I suggested above, you can also use timelocked
transactions (but using only CLTV branches is more flexible
certainly).

> Can this "unknown discrete logarithm" be made provably unknown, so all 
> signers are assured of this property? Bonus points if the outside world can't 
> tell. The exact mechanism could be outside the scope of the BIP, but knowing 
> that it's possible is useful.

Yes, that's a TODO that's left in the draft, but this is absolutely
possible (using a hash-to-curve operation). As ZmnSCPxj already
suggested, there can even be a fixed known constant you can use for
this. However, you get better privacy by taking this fixed known
constant (call it C) and using as internal key a blinded version of it
(C+rG, for some random value r, and G the normal secp256k1 generator);
as long as the DL between G and C is unknown, this is safe (and does
not reveal to the world that in fact no key-path was permitted when
spending).

> Regarding usage of Schnorr: do I understand correctly that the "everyone 
> agrees" internal key MUST use Schnorr, and that individual branches MAY use 
> Schnorr, but only if they're marked as tapscript spend?
>
> Why is tapscript not mandatory?

Spending using the internal key always uses a single Schnorr signature
and nothing else. When you spend using a script path, you must reveal
both the script and its leaf version. If that leaf version is 0xc0,
the script is interpreted as a tapscript (in which only Schnorr
opcodes exist). If that leaf version is not 0xc0, the script is
undefined, and is unconditionally valid. This is one of the included
extension mechanisms, allowing replacing the whole script language
with something else, but without revealing it unless a branch using it
is actually used (different Merkle tree leaves can have a 

[bitcoin-dev] Taproot proposal

[Pieter Wuille via bitcoin-dev]

Hello everyone,

Here are two BIP drafts that specify a proposal for a Taproot
softfork. A number of ideas are included:

* Taproot to make all outputs and cooperative spends indistinguishable
from eachother.
* Merkle branches to hide the unexecuted branches in scripts.
* Schnorr signatures enable wallet software to use key
aggregation/thresholds within one input.
* Improvements to the signature hashing algorithm (including signing
all input amounts).
* Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support
batch validation.
* Tagged hashing for domain separation (avoiding issues like
CVE-2012-2459 in Merkle trees).
* Extensibility through leaf versions, OP_SUCCESS opcodes, and
upgradable pubkey types.

The BIP drafts can be found here:
* https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki
specifies the transaction input spending rules.
* https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki
specifies the changes to Script inside such spends.
* https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
is the Schnorr signature proposal that was discussed earlier on this
list (See 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html)

An initial reference implementation of the consensus changes, plus
preliminary construction/signing tests in the Python framework can be
found on https://github.com/sipa/bitcoin/commits/taproot. All
together, excluding the Schnorr signature module in libsecp256k1, the
consensus changes are around 520 LoC.

While many other ideas exist, not everything is incorporated. This
includes several ideas that can be implemented separately without loss
of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT,
which we're working on as an independent proposal.

The document explains basic wallet operations, such as constructing
outputs and signing. However, a wide variety of more complex
constructions exist. Standardizing these is useful, but out of scope
for now. It is likely also desirable to define extensions to PSBT
(BIP174) for interacting with Taproot. That too is not included here.

Cheers,

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

Re: [bitcoin-dev] IsStandard

[Pieter Wuille via bitcoin-dev]

On Thu, 2 May 2019 at 16:28, Aymeric Vitte via bitcoin-dev
 wrote:
>
> Thanks for the answer, indeed for the redeem script and someone
> attempting a 0/1 of 3, good example
>
> So to summarize everything is standard as long as it matches P2PKH,
> P2SH, P2WPKH or P2WSH , the redeem scripts for the sha bounties are in
> op_return

Generally, all spends of P2SH/P2WSH is standard, with the following exceptions:
* Non-push operations in the scriptSig
* Resource limitations (too large scripts or items on the stack)
* Protections against known attack vectors (low s rule, cleanstack
rule, minimally encoded numbers rule, codesep usage, ...)
* Usage of unconditionally spendable constructions intended for future
extensions, such as spending future segwit versions.

Cheers,

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

Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

[Pieter Wuille via bitcoin-dev]

On Wed, 19 Dec 2018 at 18:06, Rusty Russell via bitcoin-dev
 wrote:
>
> Meanwhile, both SIGHASH_NOINPUT and OP_MASK have the reuse-is-dangerous
> property; with OP_MASK the danger is limited to reuse-on-the-same-script
> (ie. if you use the same key for a non-lightning output and a lightning
> output, you're safe with OP_MASK.  However, this is far less likely in
> practice).

Having had some more time to consider this and seeing discussions
about alternatives, I agree. It doesn't seem that OP_MASK protects
against any likely failure modes. I do think that there are realistic
risks around NOINPUT, but output tagging (as suggested in another ML
thread) seems to match those much better than masking does.

Cheers,

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

Re: [bitcoin-dev] Interrogating a BIP157 server, BIP158 change proposal

[Pieter Wuille via bitcoin-dev]

On Thu, 7 Feb 2019 at 12:19, Tamas Blummer via bitcoin-dev
 wrote:
> I did restart the discussion which I read and participated in at its first 
> instance because implementing the current proposal taught me how problematic 
> as is until not committed and because I have not seen a sign to assume 
> commitment was imminent.

Hi Tamas,

I think you're confusing the lack of sign of imminent commitment for a
sign it isn't the end goal. Changes in consensus rules take a while,
and I think adoption of BIP157 in a limited setting where offered by
trusted nodes is necessary before we will see a big push for that.

In my personal view (and I respect other opinions in this regard),
BIP157 as a public network-facing service offered by untrusted full
nodes is fair uninteresting. If the goal wasn't to have it eventually
as a commitment, I don't think I would be interested in helping
improving it. There are certainly heuristics that reduce the risk of
using it without, but they come at the cost of software complexity,
extra bandwidth, and a number of assumptions on the types of scripts
involved in the transactions. I appreciate work in exploring more
possibilities, but for a BIP157-that-eventually-becomes-a-commitment,
I think they're a distraction. Unless you feel that changes actually
benefit that end goal, I think the current BIP157 filter definition
should be kept.

There is no problem however in optionally supporting other filters,
which make different trade-offs, which are intended to be offered by
(semi) trusted nodes. Still, for the reasons above I would very much
like to keep those discussions separate from the
to-be-committed-filter.

Cheers,

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

Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

[Pieter Wuille via bitcoin-dev]

On Mon, 19 Nov 2018 at 14:37, Pieter Wuille  wrote:
> Here is a combined proposal:
> * Three new sighash flags are added: SIGHASH_NOINPUT, SIGHASH_NOFEE, and 
> SIGHASH_SCRIPTMASK.
> * A new opcode OP_MASK is added, which acts as a NOP during execution.
> * The sighash is computed like in BIP143, but:
>   * If SIGHASH_SCRIPTMASK is present, for every OP_MASK in scriptCode the 
> subsequent opcode/push is removed.
>   * The scriptPubKey being spent is added to the sighash, unless 
> SIGHASH_SCRIPTMASK is set.
>   * The transaction fee is added to the sighash, unless SIGHASH_NOFEE is set.
>   * hashPrevouts, hashSequence, and outpoint are set to null when 
> SIGHASH_NOINPUT is set (like BIP118, but not for scriptCode).

Thanks for all the input so far. Going over the suggestions and other ideas:

* OP_MASK should be required to be followed by a push, as suggested by
Anthony Towns. The alternative would permit substituting arbitrary
opcodes for masked pushes, which is at least very hard to reason
about. This would effectively turn it into a multi-byte OP_MASKEDPUSH
opcode.

* It's probably better to sign the amounts of all inputs, as suggested
by Johnson Lau. As that would cause default sighashes to sign all
input and output amounts, is there still a need to sign the tx fee
explicitly? Or in other words, are there situations where changing the
set of inputs or outputs after signing is desired, but the net
difference between them cannot change? If not, that would remove the
need for NOFEE.

* Do we need to keep the rule that sequence values of other inputs are
only signed with default sighash? It feels cleaner to always sign the
sequence values of all inputs that are included in the sighash anyway
(so all of them, unless ANYONECANPAY or NOINPUT, which would make it
sign only the current input's sequence value). If NOINPUT also blanks
the sequence values (as currently specified by BIP118), and all input
amounts are signed, that would make amounts/sequence values always be
treated identically.

* If MASK implies NOINPUT, and NOINPUT implies ANYONECANPAY, the 3 of
them can be encoded in just 2 bits using the
PARTIALSCRIPT/KNOWNSCRIPT/KNOWNTX/ALL_INPUTS encoding Anthony Towns
suggested.

* Regarding the discussion about preventing signatures from being
rebound to a different script(path)/checksig:
  * With MAST there is indeed less need for this, but at least
single-tree MAST constructions cannot replace all script branches (a
script with 40 IF/THEN/ELSE constructions may have 2^40 different
execution paths, for which computing a Merkle tree is intractable).
  * Just signing the opcode position of the CHECKSIG operator isn't
enough for all cases either. For example, you could have a complex
nested set of branches that puts a number of pubkeys on the stack, and
then a CHECKMULTISIG after the last ENDIF to verify all of them. In
such a situation, if the same key can occur in multiple combinations,
you still may want to prevent a signature generated for one
combination from being rebindable to the same key in another
combination. I believe that signing the opcode position plus the
true/false condition of all previous(?) IF statements is probably
sufficient to achieve that, but it would also introduce unnecessary
complexity for signers in most cases (see next point).
  * Thinking about signing code, adding these sort of execution trace
commitments to the sighash means they need to know which checksig
operator etc. they are signing for. I believe that in practice for
example HW devices will just whatever position the wallet indicated,
rather than verifying it corresponds with a particular intended code
path. Preventing rebinding isn't very useful if an attacker can make
you bind to the wrong thing regardless, so I'm not convinced this is
even worth having by default.
  * An alternative (not sure who suggested it) is to simply make every
CHECKSIG sign the opcode position of the last executed CODESEPARATOR
(and remove the earlier cut-of-scriptCode effect of CODESEPARATOR).
This gives a simple (but somewhat limited) way for scripts that need
to prevent certain kinds of cross-execution-trace rebinding.

A few misc ideas:
* (Taken from 
https://github.com/jl2012/bips/blob/sighash2/bip-sighash2.mediawiki)
For a default sign-everything sighash, the sighash byte can be
dropped.
* For the commitments to the scriptPubKey and scriptCode, an
intermediary hash should be used (so the data included in the sighash
includes a hash of those, rather than the script directly). This
prevents a blow up in hashing time for large scripts with many
different sighash types in its signatures.
* When masking the scriptCode, the push opcode immediately following
OP_MASKEDPUSH can be replaced by OP_VERIF (which will never collide
with any real script, as OP_VERIF makes a script invalid even when
occurring in an unexecuted branch).
* Sighashes (and really all new hashes that are introduced) should be
prefixed with a fixed 64-byte array as "tag", 

[bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

[Pieter Wuille via bitcoin-dev]

Hello everyone,

For future segwit versions, I think it would be good add a few things
to the sighash by default that were overlooked in BIP143:
* Committing to the absolute transaction fee (in addition to just the
amount being spent in each input) would categorically remove concerns
about wallets lying about fees to HW devices or airgapped signers.
* Committing to the scriptPubKey (in addition to the scriptCode) would
prevent lying to devices about the type of output being spent, even
when the scriptCode is correct. As a reminder, the scriptCode is the
actually executed script (which is the redeemscript in non-segwit
P2SH, and the witnesscript in P2WSH/P2WPKH).

As this implies additional information that may not be desirable to
commit to in all circumstances, it makes sense to make these optional.
This obviously interacts with SIGHASH_NOINPUT, which really adds two
different ways of rebinding signatures to inputs:
* Changing the prevout (so that the txid doesn't need to be known when
the signature is created)
* Changing the script (so that the exact scriptPubKey/redeemScript/...
doesn't need to be known when the signature is created)

Of course, the second implies the first, but do all use cases require
both being able to change the prevout and (arbitrarily) changing the
scriptPubKey? While BIP118 correctly points out this is secure if the
same keys are only used in scripts with which binding is to be
permitted, I feel it would be preferable if signatures/scripts would
explicitly state what can change. One way to accomplish this is by
indicating exactly what in a script is subject to change.

Here is a combined proposal:
* Three new sighash flags are added: SIGHASH_NOINPUT, SIGHASH_NOFEE,
and SIGHASH_SCRIPTMASK.
* A new opcode OP_MASK is added, which acts as a NOP during execution.
* The sighash is computed like in BIP143, but:
  * If SIGHASH_SCRIPTMASK is present, for every OP_MASK in scriptCode
the subsequent opcode/push is removed.
  * The scriptPubKey being spent is added to the sighash, unless
SIGHASH_SCRIPTMASK is set.
  * The transaction fee is added to the sighash, unless SIGHASH_NOFEE is set.
  * hashPrevouts, hashSequence, and outpoint are set to null when
SIGHASH_NOINPUT is set (like BIP118, but not for scriptCode).

So my question is whether anyone can see ways in which this introduces
redundant flexibility, or misses obvious use cases?

Cheers,

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

Re: [bitcoin-dev] Generalised taproot

[Pieter Wuille via bitcoin-dev]

On Thu, Jul 12, 2018 at 6:52 PM Anthony Towns via bitcoin-dev
 wrote:
> On Fri, Jan 26, 2018 at 09:34:39PM +, Gregory Maxwell via bitcoin-dev 
> wrote:
> > [pubkey]
> >   \-[pubkey]&
> >  \-[fancy script]
>
> I think it's possible to do recursive taproot in this manner in a
> neat way, using Pedersen Commitments.
>
> (Background: A Pedersen commitment uses a second generator in the curve,
> and rather than constructing a point from a single secret, like A=a*G,
> it constructs a point from two secrets, like C=a*G+b*G2, and finding a
> different c,d such that C=c*G+d*G2 gives you the discrete log of G2)
>
> So combining this with the taproot structure gives an equation like:
>
>   P = a*G + s*G2 + H(a*G+s*G2, Q)*G
>
> If you take "a" to be a private key (so A=a*G is the corresponding
> pubkey), "s" to be (the hash of) a set of additional conditions for
> spending with the pubkey, and "Q" to be an alternative method of spending,
> you get a recursive taproot construction.

I think this is a very neat construction, and has advantages beyond
solving the recursive-taproot-without-revealing-intermediary-scripts problem
(which is useful, but I would consider a stretch goal at best).

To summarize, this is my understanding of g'root:
* A spending condition is a policy of the form "sign with public key A
  and additionally satsify script S". Such a condition is associated with
  the point P = A + s*G2 (where G2 is a second independent generator for the
  curve, and s=H(S)). To satisfy such a condition, you reveal S, provide
  inputs that satisfy S, together with a signature for public key (P - s*G2).
  We'll call A the companion key of spending condition P (as opposed to other
  public keys which may appear in the script S).
* A scriptPubKey (or redeemScript in case of P2SH) can either be a spending
  condition P directly, or a P2C derivation (using P + H(P,Q)G) of a spending
  condition and an alternative. That alternative can either be another P2C
  derivation ("recursive Taproot"), or a Merkle tree of disjunct spending
  conditions.

This is elegant in that it removes the distinction between pay-to-pubkey and
pay-to-script constructions; every point becomes the representation of both.
As long as every script(branch) requires at least one pubkey check, it
comes at no cost (neither witness size or computational).

However, I think it also offers an easy way to construct a softfork-safe
cross-input aggregation system (discussed here before:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015838.html).

Essentially what's done here is extracting one key out of every spending
condition, given it a special place (the companion key) in the execution
structure - rather than being part of freeform script opcodes - and made it
cheaper to satisfy (as no pubkey needs to be revealed for it). This makes sense,
as we can assume that every (secure) script contains at least one CHECKSIG or
semantically equivalent operation, and with Schnorr multisignatures, can often
expect that to be just one key representing the set of all those who have to
sign.

However, it also means we could simply restrict a future cross-input signature
aggregation system to only apply to the set of these companion keys (one per
input). They are not subject to potential changes to the scripting language, as
they're outside of that. Under the assumption that most spending policies can be
encoded s a tractably-sized set of disjunct conditions, each with just a single
fixed set of public keys, the companion keys actually embody all public keys
involved in a transaction.

> (As far as deployment goes, I think it makes sense to get an initial
> schnorr/taproot/mast deployment out first, and add graftroot/aggregation
> later. My feeling is there's no great urgency for generalised taproot, so
> it would make sense to keep doing schnorr/taproot/mast for now, take time
> analysing generalised taproot, and if it seems sane and useful, aim to
> enable it in a later phase, eg at the same time as graftroot/aggregation)

Agree.

> [0] My inital name for these was "MAST-ended sc'roots", since it
> combines "taproot" and "scripts" and something MAST-like but only
> at the very end, but I was warned that the Mimblewimble folks have
> vast teams monitoring for Harry Potter references and will DMCA me,
> which I assume stands for "Dementors, Ministry, Cruciatus and Avada
> kedavra"... So I'm abbreviating generalised taproot as "g'root"
> instead. After all, what's the worst the Marvel guys could do?

Sebastian Geisler, Glenn Willen, and I had an hour long discussion to come up
with a name for the privileged key in g'root, but unfortunately had to resort
to the Valve universe instead to find "companion key"...

Cheers,

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

[bitcoin-dev] Bitcoin Core update notice

[Pieter Wuille via bitcoin-dev]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA512

Hello all,

Bitcoin Core 0.16.3 was just released with a fix for
CVE-2018-17144:
https://bitcoincore.org/en/2018/09/18/release-0.16.3/

We urge all network participants to upgrade to 0.16.3[*] as soon
as possible.

[*] For those who build from source, the 0.14, 0.15, 0.16, 0.17,
and master branches on GitHub (https://github.com/bitcoin/bitcoin)
are fixed as well.

- --
Pieter
-BEGIN PGP SIGNATURE-

iQIzBAEBCgAdFiEErGYmFy4AqCz/rolypjbpdjH3Z+AFAluhkogACgkQpjbpdjH3
Z+AZFg//a1UzupFYJPwM8iFWycIk3iU6VijgvuoeWv4Bq+BHxw/UtVsyI5XA4X/M
27wm7RtHQvgP/5BcWOTyXtX3WorKAVs3y6Ha3Ib67DEWUQ7HmWex1H5iSShO3PS0
lle1mwfqRY0/vC/zjIqqXiGrTstvy7Et6evTqc2zrsJrsc5pxyKxehYb0dtaR+9e
CzoioYhUWcYxy0LCtMztVBUlts8OfMK1xhpCDCk/XIVoJEqJuW5/wmux9tR0sxoJ
elEVdRGPrNfQ4lPQXDin8oUuRQ/bdfjncOu+CEWS6LgIIUXdWbzehxLpG80jCvzM
Id7ALPsTgazfj0y8EUyBlkrwlgHHIxGpHfxUJyybWMvJmjbRCQpIMKSTNsuY4DxD
mi8p2ZTfM03k7nLZbiZZdI3sGw6eACrTIx38tS+MiC8Hr69lHClTww8Q4qsMqHHd
X/eOQXLTtPzLeN9m5SmoFGFlHyHFMs+hMrhzIpig9n+sZbrYvDBOJlw28t3tYGKR
Z/WfpIUot6HdWJjsNkf3BLZF12BB/iwe2AplYYqUE8N8b6mJvbA2PkcXNbgAGexR
ySGl/CTMrpDKE5/m7cjP3h/5CSQ5M4YBPI3HijCWJQ/fSoAq9VTz0x+9V3pJyiDf
fSSdJa7QhS3flBcQ3HlrXaLBaosHoT3PHf4d16iyR6fvcn4s4HQ=
=nubz
-END PGP SIGNATURE-
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Extending BIP174 for HTLCs

[Pieter Wuille via bitcoin-dev]

On Tue, Sep 4, 2018, 04:32 Alex Bosworth via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> I've been experimenting with a format tag for BIP 174 to help support
> HTLC scripts I've been working with.
>

I've been thinking about this as well.

A useful way to look at it IMHO is to see a hash as the analogue of a
public key, and the preimage as the analogue of a signature.

That would suggest adding two fields to PSBT:
* A request for the preimage of a given hash (similar to the pubkey/path
field currently)
* A revealed preimage for a given hash (similar to the partial signature
field currently).

The workflow would in this case would be:
* An updater recognizes an output/script as being one that requires a
preimage, and adds a preimage request field to the input (along with pubkey
fields for all involved keys).
* A "signer" who knows the preimage sees the request field, verifies he's
willing to divulge the secret, and adds a preimage field (along with any
signatures he may be able to create).
* A finalizer who is compatible with the type of hashlock script combines
all signatures and preimages into a final scriptSig/witness stack.

An obvious difficulty is having updaters and finalizers which are
compatible with all possible variations of hashlocks and other scripts.

Not sure on the best format for this, but what I have been thinking
> about is a new input type that defines elements that should be
> inserted in the final p2sh/p2wsh stack such as a preimage or a refund
> path flag.
>

That's one approach to reducing the complexity of the finalizer: adding
information about the composition of the scriptSig to the PSBT itself.
However, I don't think that approach scales very well (you'd need new
fields for all kinds of new script constructions). In particular, dealing
with multiple possible satisfactions may complicate things, especially when
the number of combinations is intractable.

I've been working on another approach that doesn't involve changes to PSBT,
but instead uses an easily-parsable subset of script (which includes
and/or/threshold/pubkey/locktimes/hashlocks). I hope to publish something
soon about it.

Cheers,

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

[bitcoin-dev] Witness serialization in PSBT non-witness UTXOs

[Pieter Wuille via bitcoin-dev]

Hello all,

BIP174 currently specifies that non-witness UTXOs (the transactions
being spent by non-witness inputs) should be serialized in network
format.

I believe there are two issues with this.

1. Even in case the transaction whose output being spent itself has a
witness, this witness is immaterial to PSBT. It's only there to be
able to verify the txid commits to the output/amount being spent,
which can be done without witness.

2. "Network format" is a bit ambiguous. We can imagine a future
softfork that introduces a new type of witness. Network format could
be interpreted as including that new witness type, which is clearly
unnecessary (by the above argument), and would gratuitously break
compatibility with existing signers if implemented pedantically.

So my suggestion is to update the specification to state that
non-witness UTXOs must be serialized without witness. If it's too late
for that, it should instead be updated to explicitly specify with or
witnout witness, but it's safe to drop the witness.

Opinions?

Cheers,

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

Re: [bitcoin-dev] Schnorr signatures BIP

[Pieter Wuille via bitcoin-dev]

On Sat, Jul 14, 2018 at 8:42 AM, Sjors Provoost  wrote:
> Questions:
>
> Regarding verification: why does bytes(P) use compressed key serialization 
> rather than the implicit Y coordinate used for signing? I understand space 
> savings don't matter since these values don't end up on the blockchain. Is it 
> just easier to implement or is it faster?

Following the design decision to use key-prefixed Schnorr, the
signature must commit to the entire public key, including its Y
coordinate.

It would be possible to only permit public keys whose Y coordinates
are even, or quadratic residues (like the signature internally uses
for the R point), but that would mean changing what public keys are
acceptable. Not doing so has significant practical advantages, like
not breaking existing key generation mechanisms (like BIP32 and
derivatives).

So if we're going to serialize the public key into the hash, in full,
the easiest choice seems to be to use the encoding everyone already
uses for public keys.

> Regarding rationale for choosing (e,s) vs. (R,s), you say that (e,s) "avoids 
> the difficulty of encoding a point R in the signature". But since e = H(sG - 
> eP || m) also involves converting a point to some byte encoding in order to 
> hash it, how much difficulty is actually avoided? Is that, like for previous 
> question, because you could get away with compressed keys rather than 
> implicit Y coordinates?

This is mostly a historical argument. When Schnorr is applied to an
integer multiplication group rather than an elliptic curve group,
serializing a group element is many times larger than serializing a
hash. For elliptic curve based Schnorr, there is hardly any benefit
for choosing the (e,s) form over (R,s).

> Regarding batch verification: "randomly generated independently for each 
> batch of verifications" - by whom? I assume randomly picked by the verifier?

Randomly picked by the verifier, yes. The randomization factors are
there so that an attacker cannot choose signatures which cancel out
other invalid signatures within the same batch.

> Regarding random number used for signing. The suggested (?) deterministic 
> algorithm to derive secret key ''k'' from the private key ''d''  seems 
> similar to RFC6979. Maybe it's useful to briefly explain the difference, as 
> well as your rationale for not making it mandatory (presumably the same as 
> why RFC6979 isn't mandatory although most (?) wallets use it).

What would "mandatory" mean? To follow the BIP, signers must sign
using nonces generated deterministically following the provided
method. That's as far as mandatory can go.

However, it is not possible to enforce (by a verifier) than nonces
were generated in a specific way. To do so, the verifier would need to
know the nonce, which implies learning the private key. So the nonce
choosing algorithm cannot be enforced by the verifier. This implies
that it is possible to generate valid (and secure) nonces in a way
that does not follow the BIP.

> * Motivation: "signatures ... These are standardized", but the "standardized" 
> link points to the secp256k1 curve parameters, not to anything signature 
> related afaik

There are two documents on the site linked to. One describes the ECDSA
signing algorithm and serializations, the other specifies the curve
parameter. I could link to both.

> * "message m: an array of 32 bytes", maybe add "typically the sha256 hash of 
> the transaction components commited to by SIGHASH_TYPE”

Ok.

> * I left a few even smaller nits as a PR: https://github.com/sipa/bips/pull/10

Thanks for your comments, will review.

Cheers,

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

Re: [bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

On Tue, Jul 10, 2018 at 5:10 AM, matejcik  wrote:
> On 6.7.2018 00:06, Pieter Wuille wrote:> The only case where "malicious"
> conflicting values can occur is when
>> one of the Signers produces an invalid signature, or modifies any of
>> the other fields already present in the PSBT for consumption by
>> others. If this were an issue, it would be an issue regardless of the
>> Combiner's operation, as in topology A no Combiner is even present.
>> This is generally true I think - Combiners can always be replaced with
>> just a different (and possibly less parallel) topology of data flow.
>
> This is an interesting thesis, and also an unspoken assumption ISTM. It
> seems worth adding something like this to the spec:
> """
> In general, the result of Combiner combining two PSBTs from independent
> participants A and B should be functionally equivalent to a result
> obtained from processing the original PSBT by A and then B in a sequence.
> or, for participants performing fA(psbt) and fB(psbt):
> Combine(fA(psbt), fB(psbt)) == fA(fB(psbt)) == fB(fA(psbt))
> """

Adding that sounds like a good idea, indeed.

>> The bottom line is that a Combiner which picks arbitrarily in case of
>> conflicts will never end up with something worse than what you already
>> need to deal with. If you disregard the case of invalid fields
>> (because the result will just be an invalid transaction), then any
>> choice the Combiner makes is fine, because all the values it can pick
>> from are valid.
>
> This sounds reasonable and IMHO it would be good to have a summary of
> this argument in the Rationale section.

Sounds good.

>> If you're worried about attack surface, I don't believe rejecting
>> invalid fields ever matters. An attacker can always drop the fields
>> you don't understand before giving you the PSBT, making your behavior
>> identical to one where you'd have ignore those fields in the first
>> place.
>
> I'm reluctant to sign an input with unknown data, on the premise that there 
> could be *anything* in that data

But the point is: you are not signing an input with unknown data. You
are signing your own interpretation (since you compute the sighash
yourself), which doesn't include what you don't understand. If that
interpretation doesn't match reality, the signature is at worst
useless. Who cares that someone added information about a transaction
that doesn't affect what you sign?

> We are most likely to implement the "do not sign with unknown fields"
> rule in any case (technically a whitelist of "known OK" field types),
> and resolve potential problems as they arise. I raised this point mainly
> because I think discussing this explicitly in the spec is beneficial: a
> distinction between mandatory and optional fields is one way, mentioning
> or prescribing possible signing strategies is another.

I don't think that's a particularly useful policy, but certainly
Signers are allowed to implement any policy they like about what they
accept in signing.

Cheers,

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

Re: [bitcoin-dev] Multiparty signatures

[Pieter Wuille via bitcoin-dev]

On Sun, Jul 8, 2018, 21:29 Erik Aronesty  wrote:

> Because it's non-interactive, this construction can produce multisig
> signatures offline.   Each device produces a signature using it's own
> k-share and x-share.   It's only necessary to interpolate M of n shares.
>
> There are no round trips.
>
> The security is Shamir + discrete log.
>
> it's just something I've been tinkering with and I can't see an obvious
> problem.
>
> It's basically the same as schnorr, but you use a threshold hash to fix
> the need to be online.
>
> Just seems more useful to me.
>

That sounds very useful if true, but I don't think we should include novel
cryptography in Bitcoin based on your not seeing an obvious problem with it.

I'm looking forward to seeing a more complete writeup though.

Cheers,

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

Re: [bitcoin-dev] Multiparty signatures

[Pieter Wuille via bitcoin-dev]

On Sun, Jul 8, 2018, 19:23 Erik Aronesty via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Pretty sure these non interactive sigs are more secure.
>

Schnorr signatures are provably secure in the random oracle model assuming
the discrete logarithm problem is hard in the used group.

What does "more secure" mean? Is your construction secure with weaker
assumptions?

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

Re: [bitcoin-dev] Multiparty signatures

[Pieter Wuille via bitcoin-dev]

On Sun, Jul 8, 2018, 07:26 Erik Aronesty via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> To save space, start with the wiki terminology on schnorr sigs.
>
> Consider changing the "e" term in the schnorr algorithm to hash of message
> (elligator style) to the power of r, rather than using concatenation.
>

This is a very vague description. Is there some paper you can reference, or
a more detailed explanation of the algorithm?

This would allow m of n devices to sign a transaction without any of them
> knowing a private key at all.
>
IE: each device can roll a random number as a share and the interpolation
> of that is the private key.
>
> The public shares can be broadcast and combines.  And signature shares can
> be broadcast and combined.
>
> The net result of this is it really possible for an arbitrary set of
> devices to create a perfectly secure public-private key pair set.
>
At no point was the private key anywhere.
>

All of this sounds like a threshold signature scheme, which as Tim pointed
out is already possible with Schnorr.

What are the advantages of what you're describing?

Cheers,

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

[bitcoin-dev] Schnorr signatures BIP

[Pieter Wuille via bitcoin-dev]

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,

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

Re: [bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

On Thu, Jul 5, 2018 at 4:52 AM, matejcik  wrote:
>> Allowing combiners to choose any value also allows for intelligent combiners 
>> to choose the
>> correct values in the case of conflicts. A smart combiner could, when 
>> combining redeem scripts
>> and witness scripts, check that the redeem scripts and witness scripts match 
>> the hash provided
>> in the UTXO (or in the redeem script) and choose the correct redeem script 
>> and witness script
>> accordingly if there were, for some reason, a conflict there.
>>
>> Can you explain why it would be unsafe for combiners to arbitrarily choose a 
>> value?
>
> We're worried that the "pick one of non-deterministic signatures" is a
> special case and that most fields don't have this property:
>
> * conflicts in UTXOs, sighash type, redeem/witness scripts, derivation
> paths, are at best a recoverable error, usually an unrecoverable error,
> at worst malicious activity.
>
> * conflict in finalized scripts, in case more than one valid
> finalization exists, might indicate that the Finalizers picked different
> ND signatures, or it might indicate two possible interpretations of the
> transaction (see next point). Picking arbitrarily in the latter case
> would be an error.
>
> * even for partial signatures: if two Signers with the same public key
> use different sighash types, the Combiner shouldn't pick the winning one
> arbitrarily.
>
> It seems generally safer to default to rejecting conflicts, and
> explicitly allowing the Combiner to process them intelligently if it
> understands the relevant fields.

So consider two possible topologies for a multiparty signing:

A) Creator and Updater produce a PSBT T. T is sent to signer 1 who
turns it into PSBT T1. T1 is then forwarded to Signer 2 who turns it
into T12. A Finalizer extracts the transaction.
B) Creator and Updater produce a PSBT T. T is sent to signer 1 and 2
simultaneously, who then produce T1 and T2 respectively. A Combiner
combines those into T12. A Finalizer extracts the transaction.

The only case where "malicious" conflicting values can occur is when
one of the Signers produces an invalid signature, or modifies any of
the other fields already present in the PSBT for consumption by
others. If this were an issue, it would be an issue regardless of the
Combiner's operation, as in topology A no Combiner is even present.
This is generally true I think - Combiners can always be replaced with
just a different (and possibly less parallel) topology of data flow.

So the question is independent of Combiners IMHO, and really about how
we deal with roles that intentionally or unintentionally produce
invalid values. I believe this is mostly not an issue. Let's go over
the cases:
* If a partial signature is invalid, the resulting transaction will be invalid.
* if a non-witness UTXO is incorrect, you'll fail to sign because the
txid mismatches the input's prevout (which you do have to check)
* If a witness UTXO is incorrect, the resulting signature will be invalid.
* If a derivation path is incorrect, the signer will fail to find the
key, or sign with the wrong key resulting in an invalid transaction.
* If a witnessscript or redeemscript is incorrect, the resulting
signature will be invalid (as those go into the scriptCode of the
sighash, and affect the type of sighashing)
* If a sighash type is incorrect, the resulting transaction may be
useless for its intended purpose (but still something every signer
agreed to sign).

So all of this boils down to dealing with the possibility that there
can be roles which intentionally or unintentionally create incorrect
fields in a PSBT, and the solution is (a) checking that prevout txids
match non-witness utxos (b) checking that the transaction you're
signing is one you want to sign (including sighash type) (c) worst
case accepting that the resulting transaction may be invalid.

Now, (c) can sometimes be caught early, by implementing additional
sanity checks for known fields. For example, rejecting PSBTs with
partial signatures that are invalid (feed them through a verifier).
This is something a Combiner can of course optionally do, but so can a
Signer or any other role.

The bottom line is that a Combiner which picks arbitrarily in case of
conflicts will never end up with something worse than what you already
need to deal with. If you disregard the case of invalid fields
(because the result will just be an invalid transaction), then any
choice the Combiner makes is fine, because all the values it can pick
from are valid.

> I agree with your response, and I also think that in technical sense,
> the worst that can happen is an invalid signature. Our concern is twofold:
>
> 1. the produced signature is most likely valid, _for a different
> transaction_ than the Creator intended. It is a transaction that the
> Signer must have authorized, so we could argue that they would not mind
> if that unintended transaction was published. Nevertheless, this opens
> an attack surface.

If 

Re: [bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

On Wed, Jul 4, 2018 at 6:19 AM, matejcik  wrote:
> hello,
>
> we still have some concerns about the BIP as currently proposed - not
> about the format or data contents, but more about strictness and
> security properties. I have raised some in the previous e-mails, but
> they might have been lost in the overall talk about format.
>
> * Choosing from duplicate keys when combining.
> We believe that "choose whichever value it wishes" is not a good
> resolution strategy. We propose to either change this to "in case of
> conflicts, software MUST reject the conflicting PSBTs", or explain in
> more detail why picking at random is a safe choice.

Outlawing conflicting values would imply forcing all Signers to
implement fixed deterministic nonce generation, which I don't think it
very desirable. Otherwise PSBTs that got copied and signed and
combined again may fail. So I think we should see it the other way: we
choose the keys in such a way that picking arbitrarily is safe. If
there really is a future extension for which it would not be the case
that picking arbitrarily is acceptable, more data can be moved to the
keys, and leave the actual resolution strategy to the Finalizer. That
way Combiners can remain dumb and not need script-specific logic in
every interaction.

An alternative would be to have a fixed resolution strategy (for
example, when combining multiple PSBTs, pick the value from the first
one that has a particular key set), but I don't think this adds very
much - if picking the first is fine, picking a arbitrary one should be
fine too.

> * Signing records with unknown keys.
> There's been some talk about this at start, but there should be a clear
> strategy for Signers when unknown fields are encountered. We intend to
> implement the rule: "will not sign an input with any unknown fields
> present".
> Maybe it is worth codifying this behavior in the standard, or maybe
> there should be a way to mark a field as "optional" so that strict
> Signers know they can _safely_ ignore the unknown field.

Can you envision a situation in which this is needed? In every
scenario I can come up with, the worst that can happen is that the
resulting signature is just invalid. For example, if PSBT existed
before segwit, and then was later extended to support it, a pre-segwit
signer would not recognize that BIP143 would need to be used for
segwit inputs, and produce signatures using the old sighashing
algorithm. The result is just an invalid signature.

I believe that what you're trying to accomplish is preventing signing
something you don't understand, but that's an independent issue.
Signers generally will want to inspect the transaction they're
signing, or ask for confirmation w.r.t. fees or payment destinations
involved. The case where unknown fields are present for a reason you'd
want to withhold signing for will generally also just be the situation
where you don't understand the transaction you're signing.

Here is (perhaps far fetched) example of why it may not be desirable
to reject unknown fields when signing. Imagine an extension is defined
which adds pay-to-contract derivation for keys (Q = P + H(Q||C)G);
this would be a field similar to the current BIP32 derivation one, but
instead give a base key P and a contract C. Now say there is a 2-of-2
multisig in which you're one signer, and the other signer is (unknown
to you) using P2C. After the other party Updating, the input would
contain a P2C field which you don't understand - but it also isn't
something you care about or affects you.

I would not be opposed to having fields with an explicit flag bit that
says "Don't sign if you don't understand this", but I expect that that
can also be left for future extensions.

> * Fields with empty keys.
> This might be inferred from the definition, but is probably worth
> spelling out explicitly: If a field definition states that the key data
> is empty, an implementation MUST enforce this and reject PSBTs that
> contain non-empty data.
> We suggest adding something to the effect of:
> "If a key or value data in a field doesn't match the specified format,
> the PSBT is invalid. In particular, if key data is specified as "none"
> but the key contains data beyond the type specifier, implementation MUST
> reject the PSBT."
> (not sure about the languge, this should of course allow processing
> unknown fields)

Completely agree here. Any implementation that understands a
particular field must enforce whatever structure the field is known to
have.

> * "Combiner can detect inconsistencies"
> Added in response to this comment [1], the current wording looks like
> it's describing what the Combiner is _capable of_, as opposed to
> prescribing what the combiner is _allowed to_ do.
> We suggest changing to something like:
> "For every field type that the Combiner understands, it MAY also refuse
> to combine PSBTs that have inconsistencies in that field, or cause a
> conflict when combined."

Agree, just because Combiners are 

Re: [bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

On Wed, Jun 27, 2018, 07:04 matejcik  wrote:

> hello,
>
> On 26.6.2018 22:30, Pieter Wuille wrote:
> >> (Moreover, as I wrote previously, the Combiner seems like a weirdly
> >> placed role. I still don't see its significance and why is it important
> >> to correctly combine PSBTs by agents that don't understand them. If you
> >> have a usecase in mind, please explain.
> >
> > Forward compatibility with new script types. A transaction may spend
> > inputs from different outputs, with different script types. Perhaps
> > some of these are highly specialized things only implemented by some
> > software (say HTLCs of a particular structure), in non-overlapping
> > ways where no piece of software can handle all scripts involved in a
> > single transaction. If Combiners cannot deal with unknown fields, they
> > won't be able to deal with unknown scripts.
>
> Record-based Combiners *can* deal with unknown fields. Either by
> including both versions, or by including one selected at random. This is
> the same in k-v model.
>

Yes, I wasn't claiming otherwise. This was just a response to your question
why it is important that Combiners can process unknown fields. It is not an
argument in favor of one model or the other.

> combining must be done independently by Combiner implementations for
> > each script type involved. As this is easily avoided by adding a
> > slight bit of structure (parts of the fields that need to be unique -
> > "keys"), this seems the preferable option.
>
> IIUC, you're proposing a "semi-smart Combiner" that understands and
> processes some fields but not others? That doesn't seem to change
> things. Either the "dumb" combiner throws data away before the "smart"
> one sees it, or it needs to include all of it anyway.
>

No, I'm exactly arguing against smartness in the Combiner. It should always
be possible to implement a Combiner without any script specific logic.

> No, a Combiner can pick any of the values in case different PSBTs have
> > different values for the same key. That's the point: by having a
> > key-value structure the choice of fields can be made such that
> > Combiners don't need to care about the contents. Finalizers do need to
> > understand the contents, but they only operate once at the end.
> > Combiners may be involved in any PSBT passing from one entity to
> > another.
>
> Yes. Combiners don't need to care about the contents.
> So why is it important that a Combiner properly de-duplicates the case
> where keys are the same but values are different? This is a job that,
> AFAICT so far, can be safely left to someone along the chain who
> understands that particular record.
>

That's because PSBTs can be copied, signed, and combined back together. A
Combiner which does not deduplicate (at all) would end up having every
original record present N times, one for each copy, a possibly large blowup.

For all fields I can think of right now, that type of deduplication can be
done through whole-record uniqueness.

The question whether you need whole-record uniqueness or specified-length
uniqueness (=what is offered by a key-value model) is a philosophical one
(as I mentioned before). I have a preference for stronger invariants on the
file format, so that it becomes illegal for a PSBT to contain multiple
signatures for the same key for example, and implementations do not need to
deal with the case where multiple are present.

It seems that you consider the latter PSBT "invalid". But it is well
> formed and doesn't contain duplicate records. A Finalizer, or a
> different Combiner that understands field F, can as well have the rule
> "throw away all but one" for this case.
>

It's not about considering. We're writing a specification. Either it is
made invalid, or not.

In a key-value model you can have dumb combiners that must pick one of the
keys in case of duplication, and remove the necessity of dealing with
duplication from all other implementations (which I consider to be a good
thing). In a record-based model you cannot guarantee deduplication of
records that permit repetition per type, because a dumb combiner cannot
understand what part is supposed to be unique. As a result, a record-based
model forces you to let all implementations deal with e.g. multiple partial
signatures for a single key. This is a minor issue, but in my view shows
how records are a less than perfect match for the problem at hand.

To repeat and restate my central question:
> Why is it important, that an agent which doesn't understand a particular
> field structure, can nevertheless make decisions about its inclusion or
> omission from the result (based on a repeated prefix)?
>

Again, because otherwise you may need a separate Combiner for each type of
script involved. That would be unfortunate, and is very easily avoided.

Actually, I can imagine the opposite: having fields with same "key"
> (identifying data), and wanting to combine their "values" intelligently
> without losing any of the data. Say, two 

Re: [bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

On Tue, Jun 26, 2018 at 8:33 AM, matejcik via bitcoin-dev
 wrote:
> I'm still going to argue against the key-value model though.
>
> It's true that this is not significant in terms of space. But I'm more
> concerned about human readability, i.e., confusing future implementers.
> At this point, the key-value model is there "for historical reasons",
> except these aren't valid even before finalizing the format. The
> original rationale for using key-values seems to be gone (no key-based
> lookups are necessary). As for combining and deduplication, whether key
> data is present or not is now purely a stand-in for a "repeatable" flag.
> We could just as easily say, e.g., that the high bit of "type" specifies
> whether this record can be repeated.

I understand this is a philosophical point, but to me it's the
opposite. The file conveys "the script is X", "the signature for key X
is Y", "the derivation for key X is Y" - all extra metadata added to
inputs of the form "the X is Y". In a typed record model, you still
have Xes, but they are restricted to a single number (the record
type). In cases where that is insufficient, your solution is adding a
repeatable flag to switch from "the first byte needs to be unique" to
"the entire record needs to be unique". Why just those two? It seems
much more natural to have a length that directly tells you how many of
the first bytes need to be unique (which brings you back to the
key-value model).

Since the redundant script hashes were removed by making the scripts
per-input, I think the most compelling reason (size advantages) for a
record based model is gone.

> (Moreover, as I wrote previously, the Combiner seems like a weirdly
> placed role. I still don't see its significance and why is it important
> to correctly combine PSBTs by agents that don't understand them. If you
> have a usecase in mind, please explain.

Forward compatibility with new script types. A transaction may spend
inputs from different outputs, with different script types. Perhaps
some of these are highly specialized things only implemented by some
software (say HTLCs of a particular structure), in non-overlapping
ways where no piece of software can handle all scripts involved in a
single transaction. If Combiners cannot deal with unknown fields, they
won't be able to deal with unknown scripts. That would mean that
combining must be done independently by Combiner implementations for
each script type involved. As this is easily avoided by adding a
slight bit of structure (parts of the fields that need to be unique -
"keys"), this seems the preferable option.

> ISTM a Combiner could just as well combine based on whole-record
> uniqueness, and leave the duplicate detection to the Finalizer. In case
> the incoming PSBTs have incompatible unique fields, the Combiner would
> have to fail anyway, so the Finalizer might as well do it. Perhaps it
> would be good to leave out the Combiner role entirely?)

No, a Combiner can pick any of the values in case different PSBTs have
different values for the same key. That's the point: by having a
key-value structure the choice of fields can be made such that
Combiners don't need to care about the contents. Finalizers do need to
understand the contents, but they only operate once at the end.
Combiners may be involved in any PSBT passing from one entity to
another.

> There's two remaining types where key data is used: BIP32 derivations
> and partial signatures. In case of BIP32 derivation, the key data is
> redundant ( pubkey = derive(value) ), so I'd argue we should leave that
> out and save space. In case of partial signatures, it's simple enough to
> make the pubkey part of the value.

In case of BIP32 derivation, computing the pubkeys is possibly
expensive. A simple signer can choose to just sign with whatever keys
are present, but they're not the only way to implement a signer, and
even less the only software interacting with this format. Others may
want to use a matching approach to find keys that are relevant;
without pubkeys in the format, they're forced to perform derivations
for all keys present.

And yes, it's simple enough to make the key part of the value
everywhere, but in that case it becomes legal for a PSBT to contain
multiple signatures for a key, for example, and all software needs to
deal with that possibility. With a stronger uniqueness constraint,
only Combiners need to deal with repetitions.

> Thing is: BIP174 *is basically protobuf* (v2) as it stands. If I'm
> succesful in convincing you to switch to a record set model, it's going
> to be "protobuf with different varint".

If you take the records model, and then additionally drop the
whole-record uniqueness constraint, yes, though that seems pushing it
a bit by moving even more guarantees from the file format to
application level code. I'd like to hear opinions of other people who
have worked on implementations about changing this.

Cheers,

-- 
Pieter

Re: [bitcoin-dev] New serialization/encoding format for key material

[Pieter Wuille via bitcoin-dev]

On Fri, Jun 15, 2018 at 8:54 AM, Russell O'Connor
 wrote:
>
>> For codes designed for length 341 (the first length enough to support
>> 512 bits of data):
>> * correct 1 error = 3 checksum characters
>> * correct 2 errors = 7 checksum characters
>> * correct 3 errors = 11 checksum characters
>> * correct 4 errors = 15 checksum characters
>> * correct 5 errors = 19 checksum characters
>> * ...
>> * correct 7 errors = 26 checksum characters (~ length * 1.25)
>> * correct 13 errors = 51 checksum characters (~ length * 1.5)
>> * correct 28 errors = 102 checksum characters (~ length * 2)
>>
>> So it really boils down to a trade-off between length of the code, and
>> recovery properties.
>
>
> At the risk of making the proposal more complex, I wonder if it might be
> better to support multiple checksum variants?  The trade-off between code
> length and recovery seems to be largely determined by the user's medium of
> storage, which is likely to vary from person to person.  I personally would
> probably be interested in the 51 or even 102 character checksums variants.

Here are some more numbers then. It's important to note that the
number of correctable errors includes errors inside the checksum
characters themselves. So if you want to aim for a certain percentage
of correctable characters, the numbers go up much more dramatically.

For codes restricted to 341 characters total (including the checksum
characters), and assuming 103 data characters (enough for 512 bits):
* With 26 checksum characters (adding 25%, 20% of overall string), 7
errors can be corrected (5% of overall string)
* With 62 checksum characters (adding 60%, 38% of overall string), 17
errors can be corrected (10% of overall string)
* With 116 checksum characters (adding 113%, 53% of overall string),
33 errors can be corrected (15% of overall string)
* With 195 checksum characters (adding 189%, 65% of overall string),
60 errors can be corrected (20% of overall string)

For codes restricted to 1023 characters total (including the checksum
characters), and assuming 103 data characters (enough for 512 bits):
* With 27 checksum characters (adding 26%, 21% of overall string), 7
errors can be corrected (5% of overall string)
* With 64 checksum characters (adding 62%, 38% of overall string), 17
errors can be corrected (10% of overall string)
* With 127 checksum characters (adding 123%, 57% of overall string),
36 errors can be corrected (15% of overall string)
* With 294 checksum characters (adding 285%, 74% of overall string),
80 errors can be corrected (20% of overall string)
* With 920 checksum characters (adding 893%, 90% of overall string),
255 errors can be corrected (25% of overall string)

I'll gladly construct reference source code for any of these.

Cheers,

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

Re: [bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

On Thu, Jun 21, 2018 at 12:56 PM, Peter D. Gray via bitcoin-dev
 wrote:
> I have personally implemented this spec on an embedded micro, as
> the signer and finalizer roles, and written multiple parsers for
> it as well. There is nothing wrong with it, and it perfectly meets
> my needs as a hardware wallet.

This is awesome to hear. We need to hear from people who have comments
or issues they encounter while implementing, but also cases where
things are fine as is.

> So, there is a good proposal already spec'ed and implemented by
> multiple parties. Andrew has been very patiently shepherding the PR
> for over six months already.
>
> PSBT is something we need, and has been missing from the ecosystem
> for a long time. Let's push this out and start talking about future
> versions after we learn from this one.

I understand you find the suggestions being brought up in this thread
to be bikeshedding over details, and I certainly agree that "changing
X will gratuitously cause us more work" is a good reason not to make
breaking changes to minutiae. However, at least abstractly speaking,
it would be highly unfortunate if the fact that someone implemented a
draft specification results in a vested interest against changes which
may materially improve the standard.

In practice, the process surrounding BIPs' production readiness is not
nearly as clear as it could be, and there are plenty of BIPs actually
deployed in production which are still marked as draft. So in reality,
truth is that this thread is "late", and also why I started the
discussion by asking what the state of implementations was. As a
result, the discussion should be "which changes are worth the hassle",
and not "what other ideas can we throw in" - and some of the things
brought up are certainly the latter.

So to get back to the question what changes are worth the hassle - I
believe the per-input derivation paths suggested by matejcik may be
one. As is written right now, I believe BIP174 requires Signers to
pretty much always parse or template match the scripts involved. This
means it is relatively hard to implement a Signer which is compatible
with many types of scripts - including ones that haven't been
considered yet. However, if derivation paths are per-input, a signer
can just produce partial signatures for all keys it has the master
for. As long as the Finalizer understands the script type, this would
mean that Signers will work with any script. My guess is that this
would be especially relevant to devices where the Signer
implementation is hard to change, like when it is implemented in a
hardware signer directly.

What do you think?

Cheers,

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

Re: [bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

On Thu, Jun 21, 2018 at 4:29 AM, matejcik  wrote:
> In the case of everything per-input, the naive Signer can do this:
> 1. (in the global section) pre-serialize the transaction
> 2. (in each input) find and fill out scriptPubKey from the provided UTXO
> 3. (for a given BIP32 path) check if the master fingerprint matches
> mine, if yes, derive secret key, output pubkey, signature
> 4. goto 3 (more keys per input), goto 2 (next input)
>
> Note that this flow works perfectly for multisig; it’s going to be the
> job of a Finalizer to build the final scriptSig, but each input can have
> multiple partial signatures -- and, interestingly, the naive Signer
> doesn’t even need to know about multisig.

Ah, you're thinking of an even simpler signer than I was imagining. I
don't think this works in general, because the hash being signed
depends on the structure of the script. For example, if it is P2SH, it
is the redeemscript that goes into the scriptCode serialization rather
than the scriptPubKey. If it is segwit, BIP143 serialization needs to
be used, etc. It may work if your signing is restricted to just one of
those structures, though.

> A less naive Signer will want to check things, maybe derive a scriptSig
> itself and check if it matches the given hash, etc., but it can do this
> all in place. You go linearly through the signing flow and place a
> couple strategic assertions along the way.

Right - but I think anything but the simplest signer must do this,
just to be able to distinguish between different kinds of signature
hashing.

But you're right, having per-input redeemscript/witnessscript
simplifies things still - instead of needing to look a script hash in
a map, you can just compare it with *the* redeemscript/witnessscript.

> However, if the data is global, as is now, it gets more complicated:
> 1. (in the global section) pre-serialize the transaction, prefill lookup
> tables
> 2. (for a given BIP32 path) check if mine, then derive public key and
> store in a dictionary
> 3. (for each input) find _and parse_ scriptPubKey, extract (PK or)
> script hash
> 4. lookup redeem script based on script-hash; if not found, goto 2; if
> found, parse out public key
> 5. lookup public key in the BIP32 dictionary; if not found, goto 2
> 6. output pubkey, signature

I understand your point now. I hadn't considered the possibility of
just signing with all BIP32 derivation paths given for which the
master matches, instead of extracting pubkeys/pkhs from the script.
That's a major simplification for signers indeed. I do think you need
some conditions before to determine the script structure (see above),
but this is a good point in favour of making the derivation paths
per-input.

> In general, you seem to focus a lot on the role of Combiners, esp.
> simple Combiners. To me, that doesn’t look like a significant role. As I
> envision it, a Combiner really doesn’t need to do anything more
> complicated than merge and deduplicate records, simply based on the
> uniqueness of the whole record.

It's more a side-effect of focusing on forward compatibility. I expect
that we will have transactions with inputs spending different kinds of
outputs, and some signers may not be able to understand all of them.
However, as long as the design goal of having Combiners function
correctly for things they don't understand, everything should be able
to work together fine.

> It’s the Finalizer’s job to reconstruct and validate the result. Also
> ISTM if something messes up the PSBT (such as including multiple
> conflicting fields anywhere), it’s OK to leave it to Finalizer to fail.

Agree.

> An aside to this in particular, I’ve been thinking about the requirement
> to share derivation paths and public keys with the Creator. The spec
> assumes that this will happen; you’re talking about providing full
> xpub+chaincode too. At least, the Creator must prefill BIP32 paths and
> master key fingerprints. Possibly also prefill public keys in the redeem
> scripts?
>
> This might not be an improvement proposal, but a point worth being
> raised and maybe explained in the spec. Perhaps the original Creator
> doesn’t have access to this data, and delegates this to some
> “sub-Creators”  - I imagine a coordinator sending a PSBT to signing
> parties, each of which acts as a sub-Creator (fills out derivation paths
> and public keys) and a Signer (forwarding to a HWW). Some of the
> discussion even suggests some sort of generic “key derivation field”
> with arbitrary contents - fingerprint + bip32 path? xpub + chain code?
> derivation points? encrypted xprv?

That makes sense - I think we've already touched this when discussing
the requirement for UTXOs to be added. Perhaps those aren't added by
the Creator, but by some index server. The same could be true for the
scripts or derivations paths.

And indeed, most of the information in the derivation paths is
effectively opaque to the Creator - it's just some data given out by
the Signer about its keys that 

Re: [bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

On Tue, Jun 19, 2018 at 7:20 AM, matejcik via bitcoin-dev
 wrote:

Thanks for your comments so far. I'm very happy to see people dig into
the details, and consider alternative approaches.

> 1) Why isn't the global type 0x03 (BIP-32 path) per-input? How do we
> know, which BIP-32 path goes to which input? The only idea that comes to
> my mind is that we should match the input's scriptPubKey's pubkey to
> this 0x03's key (the public key).

> If our understanding is correct, the BIP-32 path is global to save space
> in case two inputs share the same BIP-32 path? How often does that
> happen? And in case it does, doesn't it mean an address reuse which is
> discouraged?

Yes, the reason is address reuse. It may be discouraged, but it still
happens in practice (and unfortunately it's very hard to prevent
people from sending to the same address twice).

It's certainly possible to make them per-input (and even per-output as
suggested below), but I don't think it gains you much. At least when a
signer supports any kind of multisig, it needs to match up public keys
with derivation paths. If several can be provided, looking them up
from a global table or a per-input table shouldn't fundamentally
change anything.

However, perhaps it makes sense to get rid of the global section
entirely, and make the whole format a transaction plus per-input and
per-output extra fields. This would result in duplication in case of
key reuse, but perhaps that's worth the complexity reduction.

> 2) The global items 0x01 (redeem script) and 0x02 (witness script) are
> somewhat confusing. Let's consider only the redeem script (0x01) to make
> it simple. The value description says: "A redeem script that will be
> needed to sign a Pay-To-Script-Hash input or is spent to by an output.".
> Does this mean that the record includes both input's redeem script
> (because we need to sign it), but also a redeem script for the output
> (to verify we are sending to a correct P2SH)? To mix those two seems
> really confusing.
>
> Yet again, adding a new output section would make this more readable. We
> would include the input’s redeem script in the input section and the
> output’s redeem script again in the output section, because they’ll most
> likely differ anyway.

I think here it makes sense because there can actually only be (up to)
one redeemscript and (up to) one witnessscript. So if we made those
per-input and per-output, it may simplify signers as they don't need a
table lookup to find the correct one. That would also mean we can drop
their hashes, even if we keep a key-value model.

> 3) The sighash type 0x03 says the sighash is only a recommendation. That
> seems rather ambiguous. If the field is specified shouldn't it be binding?

Perhaps, yes.

> 4) Is it a good idea to skip records which types we are unaware of? We
> can't come up with a reasonable example, but intuitively this seems as a
> potential security issue. We think we should consider  introducing a
> flag, which would define if the record is "optional". In case the signer
> encounters a record it doesn't recognize and such flag is not set, it
> aborts the procedure. If we assume the set model we could change the
> structure to {data}. We are not keen on
> this, but we wanted to include this idea to see what you think.

Originally there was at least this intuition for why it shouldn't be
necessary: the resulting signature for an input is either valid or
invalid. Adding information to a PSBT (which is what signers do)
either helps with that or not. The worst case is that they simply
don't have enough information to produce a signature together. But an
ignored unknown field being present should never result in signing the
wrong thing (they can always see the transaction being signed), or
failing to sign if signing was possible in the first place. Another
way of looking at it, the operation of a signer is driven by queries:
it looks at the scriptPubKey of the output being spent, sees it is
P2SH, looks for the redeemscript, sees it is P2WSH, looks for the
witnessscript, sees it is multisig, looks for other signers'
signatures, finds enough for the threshold, and proceeds to sign and
create a full transaction. If at any point one of those things is
missing or not comprehensible to the signer, he simply fails and
doesn't modify the PSBT.

However, if the sighash request type becomes mandatory, perhaps this
is not the case anymore, as misinterpreting something like this could
indeed result in an incorrect signature.

If we go down this route, if a field is marked as mandatory, can you
still act as a combiner for it? Future extensions should always
maintain the invariant that a simple combiner which just merges all
the fields and deduplicates should always be correct, I think. So such
a mandatory field should only apply to signers?

> In general, the standard is trying to be very space-conservative,
> however is that really necessary? We would argue for clarity and ease of
> use over 

[bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

Hello all,

given some recent work and discussions around BIP 174 (Partially
Signed Bitcoin Transaction Format) I'd like to bring up a few ideas.

First of all, it's unclear to me to what extent projects have already
worked on implementations, and thus to what extent the specification
is still subject to change. A response of "this is way too late" is
perfectly fine.

So here goes:

* Key-value map model or set model.

This was suggested in this thread:
https://twitter.com/matejcik/status/1002618633472892929

The motivation behind using a key-value model rather than a simple
list of records was that PSBTs can be duplicated (given to multiple
people for signing, for example), and merged back together after
signing. With a generic key-value model, any implementation can remove
the duplication even if they don't understand fields that may have
been added in future extensions.

However, almost the same can be accomplished by using the simpler set
model (the file consists of a set of records, with no duplication
allowed). This would mean that it would technically be legal to have
two partial signatures with the same key for the same input, if a
non-deterministic signer is used.

On the other hand, this means that certain data currently encoded
inside keys can be dropped, reducing the PSBT size. This is
particularly true for redeemscripts and witnessscripts, as they can
just be computed by the client when deserializing. The two types could
even be merged into just "scripts" records - as they don't need to be
separated based on the way they're looked up (Hash160 for P2SH, SHA256
for P2WSH). The same could be done for the BIP32 derivation paths,
though this may be expensive, as the client would need to derive all
keys before being able to figure out which one(s) it needs.

One exception is the "transaction" record, which needs to be unique.
That can either be done by adding an exception ("there can only be one
transaction record"), or by encoding it separately outside the normal
records (that may also be useful to make it clear that it is always
required).

* Ability for Combiners to verify two PSBT are for the same transaction

Clearly two PSBTs for incompatible transactions cannot be combined,
and this should not be allowed.

It may be easier to enforce this if the "transaction" record inside a
PSBT was required to be in a canonical form, meaning with empty
scriptSigs and witnesses. In order to do so, there could be per-input
records for "finalized scriptSig" and "finalized witness". Actually
placing those inside the transaction itself would only be allowed when
all inputs are finalized.

* Optional signing

I think all operation for the Signer responsibility should be
optional. This will inevitably lead to incompatibilities, but with the
intent of being forward compatible with future developments, I don't
think it is possible to require every implementation to support the
same set of scripts or contracts. For example, some signers may only
implement single-key P2PKH, or may only support signing SegWit inputs.
It's the user's responsibility to find compatible signers (which is
generally not an issue, as the different participants in a setup
necessarily have this figured out before being able to create an
address). This does mean that there can't be an unconditional test
vector that specifies the produced signature in certain circumstances,
but there could be "For implementations that choose to implement
signing for P2PKH inputs using RFC6979, the expected output given
input X and access to key Y is Z".

On the other hand, the Combiner and Finalizer roles can probably be
specified much more accurately than they are now.

* Derivation from xpub or fingerprint

For BIP32 derivation paths, the spec currently only encodes the 32-bit
fingerprint of the parent or master xpub. When the Signer only has a
single xprv from which everything is derived, this is obviously
sufficient. When there are many xprv, or when they're not available
indexed by fingerprint, this may be less convenient for the signer.
Furthermore, it violates the "PSBT contains all information necessary
for signing, excluding private keys" idea - at least if we don't treat
the chaincode as part of the private key.

For that reason I would suggest that the derivation paths include the
full public key and chaincode of the parent or master things are
derived from. This does mean that the Creator needs to know the full
xpub which things are derived from, rather than just its fingerprint.

* Generic key offset derivation

Whenever a BIP32 derivation path does not include any hardened steps,
the entirety of the derivation can be conveyed as "The private key for
P is equal to the private key for Q plus x", with P and Q points and x
a scalar. This representation is more flexible (it also supports
pay-to-contract derivations), more efficient, and more compact. The
downside is that it requires the Signer to support such derivation,
which I don't believe any 

Re: [bitcoin-dev] New serialization/encoding format for key material

[Pieter Wuille via bitcoin-dev]

On Sun, Jun 3, 2018 at 2:30 PM, Jonas Schnelli  wrote:
>> If there is interest, I can construct a code + implementation for any
>> of these in a few days probably, once the requirements are clear.
>
> Yes. Please.

Here is an example BCH code for base32 data which adds 27 checksum
characters, and can correct up to 7 errors occurring in strings up to
length 1023 (including the checksum characters themselves):
https://gist.github.com/sipa/d62f94faa1dcfd9ee4012d4c88955ba6

It can encode sequences of integers (between 0 and 31):

ref.py encode 13 7 22 23 11 29 21 15 3 26 20 26 4 7 6 11 19 1 6 8 31 13 4 19

> d8khta40r656y8xtnpxgldyne96vsfr83uch908se82g98rmnaa

Decode it again:

ref.py decode d8khta40r656y8xtnpxgldyne96vsfr83uch908se82g98rmnaa

> Decoded: 13 7 22 23 11 29 21 15 3 26 20 26 4 7 6 11 19 1 6 8 31 13 4 19

Or correct errors:

ref.py decode d8khta50r656y8xtmpxhlcyne96vsfr84udh908se82g98rmnat

> Errors found: d8khta?0r656y8xt?px?l?yne96vsfr8?u?h908se82g98rmna?
> Correction:   d8khta40r656y8xtnpxgldyne96vsfr83uch908se82g98rmnaa
> Decoded: 13 7 22 23 11 29 21 15 3 26 20 26 4 7 6 11 19 1 6 8 31 13 4 19

The code above is just a randomly picked BCH code, and has no special
properties beyond the ones it is designed for.

I can easily generate similar code for BCH codes with different properties.

Cheers,

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

Re: [bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving Transaction Propagation

[Pieter Wuille via bitcoin-dev]

On Mon, Jun 11, 2018, 07:37 Bradley Denby via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Thanks for the comments Pieter!
>
> We can make descriptions for the intended node behaviors more clear in the
> BIP.
>
> Regarding interaction with BIPs 37 and 133, we have found that if
> Dandelion routing decisions are based on self-reported features, malicious
> nodes can often exploit that to launch serious deanonymization attacks. As
> a result, we recommend not allowing fee filters from peers to influence the
> choice of route. Your suggestion of automatically fluffing is a good
> solution. Another (similar) option would be to apply fee filters in the
> stempool. This would prevent the tx from propagating in stem phase, so
> eventually an embargo timer on the stem will expire and the transaction
> will fluff. This is slower than auto-fluffing, but requires (slightly) less
> code.
>

I understand the argument about not making routing decisions based on
self-reported features, but I would expect it to only matter if done
selectively? Allowing a node to opt out of Dandelion entirely should always
be possible regardless - as they can always indicate not supporting it.

The reason for my suggestion was that most full nodes on the network use
feefilter, while only (from the perspective of Dandelion uninteresting)
light nodes and blocksonly nodes generally use Bloom filters.

Just dropping stem transactions that would otherwise be sent to a Dandelion
peer which fails its filter, and relying on embargo seems fine. But perhaps
this option is something to describe in the BIP ("Nodes MAY choose to
either drop stem transactions or immediately start diffusion when a
transaction would otherwise be sent to a Dandelion node whose filter is not
satisfied for that transaction. A node SHOULD NOT make any routing
decisions based on the transaction itself, and thus SHOULD NOT try to find
an alternative Dandelion node to forward to" for example).

Regarding mempool-dependent transactions, the reference implementation adds
> any mempool transactions to the stempool but not vice-versa so that the
> stempool becomes a superset of the mempool. In other words, information is
> free to flow from the mempool to the stempool. Information does not flow
> from the stempool to the mempool except when a transaction fluffs. As a
> result, a node's stempool should accept and propagate Dandelion
> transactions that depend on other unconfirmed normal mempool transactions.
> The behavior you described is not intended; if you have any tests
> demonstrating this behavior, would you mind sharing them?
>

Oh, I see! I was just judging based on the spec code you published, but I
must have missed this. Yes, that makes perfect sense. There may be some
issues with this having a significant impact on stempool memory usage, but
let's discuss this later on implementation.

Orphans: stem orphans can occur when a node on the stem shuffles its route
> between sending dependent transactions. One way to deal with this issue
> would be to re-broadcast all previous Dandelion transactions that have not
> been fluffed after Dandelion route shuffling. This could add a fair amount
> of data and logic. This re-broadcast method also telegraphs the fact that a
> Dandelion shuffle has taken place and can result in bursts of transactions
> depending on traffic patterns. A second option (which we used in the
> reference implementation) is to wait for the fluff phase to begin, at which
> point the orphans will be resolved. This should happen within 15 seconds
> for most transactions. Do you have any thoughts on which option would be
> more palatable? Or if there are other options we have missed?
>

Another option (just brainstorming, I may be missing something here), is to
remember which peer each stempool transaction was forwarded to. When a
dependent stem transaction arrives, it is always sent to (one of?) the
peers its dependencies were sent to, even if a reshuffle happened in
between.

Thinking more about it, relying on embargo is probably fine - it'll just
result in slightly lowered average stem length, and perhaps multiple
simultaneous fluffs starting?

Regarding preferred connections, we have found that making Dandelion
> routing decisions based on claims made by peer nodes can cause problems and
> therefore would recommend against biasing the peer selection code.
>

Oh, I don't mean routing decisions, but connections in general.

On the implementation side:
>

Let's discuss these later.


> Based on the feedback we have received so far, we are planning to
> prioritize writing up a clearer spec for node behavior in the BIP. Does
> that seem reasonable, or are there other issues that are more pressing at
> this point?
>

I think that's the primary thing to focus on at this point, but perhaps
others on this list feel different.

Cheers,

-- 
Pieter
___
bitcoin-dev mailing list

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

[Pieter Wuille via bitcoin-dev]

On Wed, Jun 6, 2018 at 5:48 AM, Tim Ruffing via bitcoin-dev
 wrote:
> On Thu, 2018-05-31 at 17:25 -0700, Pieter Wuille via bitcoin-dev wrote:
>> The best argument for why Graftroot does not need to be optional I
>> think was how Greg put it: "since the signer(s) could have signed an
>> arbitrary transaction instead, being able to delegate is strictly
>> less
>> powerful.".

...

> So
> I think Graftroot delegation is not "strictly less powerful" than just
> using a normal transaction: Graftroot enables to delegate in a way such
> that the delegation itself cannot be fixed in the chain. I think this
> is not possible currently. (Okay, you can just pass around the secret
> keys but has other problems obviously).
>
> Does this have practical implications?
> I don't see any but maybe this helps someone to identify an undesirable
> implication.

Interesting point; I don't see any relevant implications to this
either, but it's indeed good to point out this as a distinction.

> One way to be on the safe side and probably make Greg's argument go
> through is to just define the semantics such that (*) is allowed, i.e.,
> call g-sig a "Graftroot transaction" and give it transaction semantics.
> This provides a new perspective on Graftroot: Then Graftroot does not
> introduce new semantics but (*) is just an optimized version of (**)
> that uses fewer bytes and may be better for privacy.

So you're saying: the Graftroot signature data could be made identical
to the signature hash of an implicit 1-input-1-output transaction
spending the coin and creating a new output with the delegated script
as sPK, and the same amount.

I like that idea, but I don't think it can be *exactly* that. If it's
possible to take a Graftroot signature and instead construct a
transaction with it, you have inherently introduced a malleability.
The created outpoint will be different in both cases (different txid),
meaning that a chain of dependent unconfirmed transactions may be
broken by giving one participant the ability to choose between
Graftroot delegation or actual spending.

Two points here: (1) the implicit transaction would be 0 fee (unless
we somehow assign a portion of the fee to the delegation itself for
purposes of sighash computing), and (2) this sounds very similar to
the issue SIGHASH_NOINPUT is intended to solve. About that...

> Interestingly Andrew's blind-sig example and Johnson's fix (g-sig signs
> the outpoint) are just a special case. If g-sig has transaction
> semantics, it must sign the outpoint (and other stuff).

You're right when you're comparing with existing transaction sighash
semantics, but not when SIGHASH_NOINPUT would exist. If that were the
case, the only real difference is your point above of not being able
to commit the implicit transaction separately. In other words, we're
back to something Johnson pointed out earlier: some of the perceived
problems with Graftroot are also issues with SIGHASH_NOINPUT.

I wonder if we can make this explicit: Graftroot spending becomes a
special sighash flag (which possibly is only allowed at the top level)
- it builds an implicit transaction which moves all the coins to a
newly provided script, computes the sighash of that transaction
(taking all of the Graftroot signature's sighash flags into account -
including potentially SIGHASH_NOINPUT), and requires a signature with
that. The delegated script is then evaluated in the context of that
implicit transaction.

However, in order to avoid the malleability issue I think the actual
signature should still be different - possibly by simply passing
through the Graftroot sighash flag into the sighash being computed.

Cheers,

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

Re: [bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving Transaction Propagation

[Pieter Wuille via bitcoin-dev]

On Thu, May 10, 2018 at 5:59 AM, Bradley Denby via bitcoin-dev
 wrote:
> Hi all,
>
> ...
>
> This iteration of Dandelion has been tested on our own small network, and we
> would like to get the implementation in front of a wider audience. An
> updated
> BIP document with further details on motivation, specification,
> compatibility,
> and implementation is located here:
> https://github.com/mablem8/bips/blob/master/bip-dandelion.mediawiki

Hi Bradley,

thank you for working on this and going as far as implementing the
entire protocol. It looks like a very well-worked out idea already,
and its semantics can probably be adopted pretty much as-is. It would
be very exciting to bring these kinds of privacy improvements to
Bitcoin's P2P protocol.

I do have a number of comments on the specification and suggested
implementation in Bitcoin Core. I'm dumping my thoughts here, though
at this stage the specification is probably more important. The
implementation can be discussed more thoroughly when there is a PR
open.

Specification

* Overall, I think it would be worthwhile to describe the intended
node behavior in the BIP, at a higher level than Bitcoin Core
patchsets, but more detailed than what is in the BIP now. The
patch-based descriptions are both hard to read for developers working
on different systems who are unfamiliar with the Core codebase, and
don't make it clear to what extent implementation decisions are local
policy (which can be changed without network coordination), and which
follow from security or privacy arguments for the protocol.

* Interaction with feefilter (BIP 133) and Bloom filter (BIP 37). When
peers have given us filters on what transactions they will accept,
should Dandelion transactions be subject to the same? Should it
influence the choice of route? One simple possibility is perhaps to
avoid choosing BIP37 peers as Dandelion routes, and treat transactions
that do not pass the feefilter for its
would-be-outgoing-Dandelion-route as an automatic fluff - justified by
noting that relaying a transaction close to what fee is acceptable to
the network's mempools is already less likely to get good privacy due
to reduced chances of propagation.

* Mempool dependant transactions. It looks like the current
implementation accepts Dandelion transactions which are dependant on
other Dandelion (stempool) transactions and on confirmed blockchain
transactions, but not ones that are dependant on other unconfirmed
normal mempool transactions. Is this intentional, or resulting from a
difficulty in implementing this? Should the correct behaviour be
specified, or left free for nodes to decide?

* Orphan transactions. It looks like the current implementation
assumes no orphan transactions, but in a dynamic network (especially
with occasionally shuffling of Dandelion routes), I expect that
sometimes a dependent transaction will go on a different route than
its parent. Do you have any thoughts about that (even if not addressed
in a very implementation). Could we have a Dandelion-orphan-pool of
transactions, similar to the normal mempool has a set of orphan
transactions?

* Preferred connections. Should we bias the outgoing connection peer
selection code to prefer Dandelion-capable peers when the number is
too low?

Implementation

* How do we control the size of the stempool? Should acceptance of a
transaction to the normal mempool and/or blockchain result in eviction
of it (and conflicts) from the stempool? The existing code
intentionally has an upper bound on the size of the mempool to assure
predictable resource usage - the introduction of the stempool
shouldn't change that.

* I don't think you need to fully materialize all the routes. Instead,
you can just maintain a vector of 2 selected Dandelion-supporting
peers (and if one disconnects, replace just that one with another
one). To map incoming peers to an index in that list of peers, you can
use deterministic randomness (see SipHasher in the source code) with
the incoming node_id as data and a single global secret nonce (chosen
at startup, and reset on reshuffle).

* setDandelionInventoryKnown looks like it can grow unboundedly. A
rolling Bloom filter (like used for filterInventoryKnown) is perhaps
easier to guarantee predictable memory usage for.

* Use a scheduler job instead of a separate thread for shuffling the
routes (extra threads use unnecessarily large amounts of memory).

* (nit) coding style: doc/developer-notes.md has a number of
guidelines on coding style you may want to check out.

Cheers,

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