Re: [bitcoin-dev] Taproot Fields for PSBT

2021-11-24 Thread 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

2021-11-17 Thread 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

2021-11-01 Thread 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

2021-10-26 Thread 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

2021-10-20 Thread 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

2021-10-09 Thread 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

2021-10-01 Thread 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

2021-09-16 Thread 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

2021-08-29 Thread 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

2021-08-29 Thread 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

2021-08-29 Thread 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

2021-07-12 Thread 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

2021-02-11 Thread 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

2021-02-11 Thread 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

2021-02-05 Thread 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

2021-01-19 Thread 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

2021-01-19 Thread 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

2021-01-17 Thread Pieter Wuille via bitcoin-dev
Hi all,

A few updates, in response to comments here and in a few other places:

- Updated several reference implementations (C, C++, Python, Javascript) to 
support Bech32m: https://github.com/sipa/bech32/tree/bech32m (but contributions 
to update other languages are welcome!)

- Updated website, including error-locating JS decoder, and demo: 
http://bitcoin.sipa.be/bech32/demo/demo.html

- Opened a Bitcoin Core PR: https://github.com/bitcoin/bitcoin/pull/20861

- Updates to the BIP draft 
(https://github.com/sipa/bips/blob/bip-bech32m/bip-bech32m.mediawiki):
  * Made the title clearer (so it doesn't imply Bech32m is used for v0)
  * Added rationale for not permitting both Bech32 and Bech32m for v0
  * Added a section on error location
  * Added links for more reference implementations

On Friday, January 15, 2021 12:01 AM, nakagat  wrote:

> I read the BIP draft of Bech32m and implemented it in Go.

Cool! Do feel like contributing it to 
https://github.com/sipa/bech32/tree/bech32m?

> Let me ask you one question.
> Does Checksum have to be fixed?
> The 'bech32_verify_checksum' function has hrp and data as parameters,
> so how about committing Checksum with these two values?
>
> For example, calculate Checksum from hrp and data using hash, chacha20, etc.

I'm not entirely sure what you mean. Do you mean:

1) Can we use a hash function to compute the checksum instead of Bech32's 
algorithm?

If you compute the checksum using the HRP and the data using a hash function, 
you just 2^-30 failure probability for any error. The idea behind Bech32 was 
doing better than that for common errors: any error that consists of up to 4 
substitutions are a failure probability of 0 - far better than a hash can do.

2) Can we keep using Bech32's algorithm, but compute the final xorred-in 
constant from the HRP and the data using a hash function?

That would be functionally equivalent to (1).

3) Can we keep using Bech32's algorithm, but compute the final xorred-in 
constant from the HRP (but not the data) using a hash function?

It would mean that some (very) small set of potential HRPs would exhibit much 
worse behavior than others - including the 'q'-before-'p' that the original 
Bech32 has.

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

2021-01-04 Thread 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

2021-01-04 Thread 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

2020-12-21 Thread 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

2020-12-21 Thread 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)

2020-12-17 Thread 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)

2020-12-06 Thread 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)

2020-12-05 Thread 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)

2020-12-05 Thread 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)

2020-10-27 Thread 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)

2020-10-20 Thread 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)

2020-10-19 Thread 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?

2020-10-16 Thread 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

2020-10-16 Thread 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)

2020-10-16 Thread 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

2020-10-07 Thread 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

2020-08-26 Thread 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

2020-08-19 Thread 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

2020-08-12 Thread 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

2020-05-11 Thread 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

2020-03-24 Thread 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

2020-03-03 Thread 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

2020-02-23 Thread 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] Taproot (and graftroot) complexity (reflowed)

2020-02-18 Thread Pieter Wuille via bitcoin-dev
On Fri, 14 Feb 2020 at 14:37, David A. Harding via bitcoin-dev
 wrote:
>
> On Fri, Feb 14, 2020 at 12:07:15PM -0800, Jeremy via bitcoin-dev wrote:
> > Is the same if Schnorr + Merkle Branch without Taproot optimization, unless
> > I'm missing something in one of the cases?
>
> That's fair.  However, it's only true if everyone constructs their
> merkle tree in the same way, with a single ` OP_CHECKSIG` as
> one of the top leaves.   Taproot effectively standardizes the position
> of the all-parties-agree condition and so its anonymity set may contain
> spends from scripts whose creators buried or excluded the the all-agree
> option because they didn't think it was likely to be used.
>
> More importantly, there's no incentive for pure single-sig users to use a
> merkle tree, since that would make both the scriptPubKey and the witness
> data are larger for them than just continuing to use v0 segwit P2WPKH.
> Given that single-sig users represent a majority of transactions at
> present (see AJ Towns's previous email in this thread), I think we
> really want to make it as convenient as possible for them to participate
> in the anonymity set.

Right, I think we shouldn't just see Taproot as adding a possibility
of a cheap single-key branch to Merkle tree. It is actively choosing
to incentivize protocols and implementations that can use the key
path, making sure that the cheapest way spending of spending is also
the most private one - as we can assume that it indeed will be the
most frequent one. I don't believe having a separate MAST-no-Taproot
spending type (through whatever mechanism) is beneficial to that.
Taproot effectively gives everyone a "key path spend is included in
the price", making it maximally appealing even to those who don't care
about privacy.

I don't think this is an unreasonable angle. There are plenty of other
options that exists if we just want to make verification constructions
cheap but disregard incentives for privacy. For example, why don't we
research account-based state/payments? Being able to avoid change
would make simple payments significantly cheaper (both in terms of
block space and computation). Of course, the reason (or at least one
of them) is that it would result in a discount for those willing to
reduce their privacy (use accounts = reuse address = don't pay for
change), and this hurts everyone (and indirectly the fungibility of
the system as a whole). This is true even when there are use cases
that would legitimately benefit from having this option.

This is of course a much weaker case, but I think it is similar.
Having no-Taproot available would reduce the incentives for those who
don't care about spending policy privacy to put the engineering effort
into building key-path-spendable protocols and implementations - and I
think such protocols, wherever possible, should be the goal. There
probably are some use cases where key path spending is truly not an
option, but I suspect they're rare, or sufficiently high value that 8
vbyte differences don't matter to them. If that turns out to be wrong,
it remains possible to add a new output type/witness version that does
support them. This does mean distinguishable outputs, but only for
things that would be distinguishable at spending time anyway, and
that's a cost we'll have to pay anyway for future structural script
improvements (like cross-input aggregation or graftroot).

Cheers,

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

2019-12-09 Thread 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

2019-12-09 Thread 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

2019-11-12 Thread 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

2019-11-10 Thread 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

2019-11-07 Thread 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

2019-10-09 Thread 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

2019-09-18 Thread 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

2019-09-18 Thread 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

2019-08-21 Thread 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

2019-08-19 Thread 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

2019-08-09 Thread 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

2019-08-09 Thread 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

2019-07-19 Thread 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

2019-05-27 Thread 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.

2019-05-23 Thread 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

2019-05-23 Thread 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

2019-05-09 Thread 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

2019-05-06 Thread 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

2019-05-03 Thread 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

2019-02-09 Thread 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

2019-02-08 Thread 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

2018-11-27 Thread 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

2018-11-19 Thread 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

2018-10-24 Thread 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

2018-09-19 Thread 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

2018-09-04 Thread 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

2018-08-13 Thread 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

2018-07-14 Thread 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

2018-07-11 Thread 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

2018-07-08 Thread 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

2018-07-08 Thread 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

2018-07-08 Thread 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

2018-07-06 Thread 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

2018-07-05 Thread 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

2018-07-04 Thread 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

2018-06-27 Thread 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

2018-06-26 Thread 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

2018-06-23 Thread 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

2018-06-22 Thread 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

2018-06-21 Thread 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

2018-06-19 Thread 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

2018-06-15 Thread 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

2018-06-12 Thread 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

2018-06-11 Thread 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?

2018-06-06 Thread 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

2018-06-05 Thread 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


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

2018-06-03 Thread Pieter Wuille via bitcoin-dev
On Sun, Jun 3, 2018 at 9:51 AM, Jonas Schnelli via bitcoin-dev
 wrote:
> Hi
>
> The BIP proposal is now available here:
> https://gist.github.com/jonasschnelli/68a2a5a5a5b796dc9992f432e794d719
>
> Reference C code is available here:
> https://github.com/jonasschnelli/bech32_keys
>
> Feedback, criticism, etc. welcome!

First of all, thanks for working on this.

I have some concerns about the use of Bech32. It is designed for
detecting 3 errors up to length 1023 (but is then picked specifically
to support 4 errors up to length 89). However, for error correction
this translates to just being able to efficiently correct 1 error
(3/2, rounded down) up to length 1023. You can of course always try
all combinations of up to N changes to the input (for any N), testing
the checksum, and comparing the results against the UTXO set or other
wallet information that may have been recovered. However, the checksum
at best gives you a small constant speedup here, not a fundamentally
improved way for recovery.

However, we can design other base32 BCH codes easily with different
properties. As we mostly care about efficient algorithms for recovery
(and not just error detection properties), it seems more important to
have good design strength (as opposed to picking a code from a large
set which happens to have better properties, but without efficient
algorithm, like Bech32).

This is what I find for codes designed for length 93 (the first length
for which efficient codes exist with length long enough to support 256
bits of data):
* correct 1 error = 3 checksum characters
* correct 2 errors = 6 checksum characters
* correct 3 errors = 10 checksum characters
* correct 4 errors = 13 checksum characters
* correct 5 errors = 16 checksum characters
* ...
* correct 8 errors = 26 checksum characters (~ length * 1.5)
* correct 11 errors = 36 checksum characters (~ maximum length without
pushing checksum + data over 93 characters)

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.

These two sets of codes are distinct (a code designed for length 93
has zero error correction properties when going above 93), so either
we can pick a separate code for the two purposes, or be limited to the
second set.

If there is interest, I can construct a code + implementation for any
of these in a few days probably, once the requirements are clear.

Cheers,

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


Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

2018-06-03 Thread Pieter Wuille via bitcoin-dev
On Sat, Jun 2, 2018, 22:56 Tamas Blummer via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Lighter but SPV secure nodes (filter committed) would help the network
> (esp. Layer 2) to grow mesh like, but add more user that blindly follow POW.
>
> On longer term most users' security will be determined by either trusted
> hubs or POW.
> I do not know which is worse, but we should at least offer the choice to
> the user, therefore commit filters.
>

I don't think that's the point of discussion here. Of course, in order to
have filters that verifiably don't lie by omission, the filters need to be
committed to by blocks.

The question is what data that filter should contain.

There are two suggestions:
(a) The scriptPubKeys of the block's outputs, and prevouts of the block's
inputs.
(b) The scriptPubKeys of the block's outputs, and scriptPubKeys of outputs
being spent by the block's inputs.

The advantage of (a) is that it can be verified against a full block
without access to the outputs being spent by it. This allows light clients
to ban nodes that give them incorrect filters, but they do need to actually
see the blocks (partially defeating the purpose of having filters in the
first place).

The advantage of (b) is that it is more compact (scriot reuse, and outputs
spent within the same block as they are created). It also had the advantage
of being more easily usable for scanning of a wallet's transactions. Using
(a) for that in some cases may need to restart and refetch when an output
is discovered, to go test for its spending (whose outpoint is not known
ahead of time). Especially when fetching multiple filters at a time this
may be an issue.

I think both of these potentially good arguments. However, once a committed
filter exists, the advantage of (a) goes away completely - validation of
committed filters is trivial and can be done without needing the full
blocks in the first place.

So I think the question is do we aim for an uncommitted (a) first and a
committed (b) later, or go for (b) immediately?

Cheers,

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


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

2018-05-31 Thread Pieter Wuille via bitcoin-dev
On Fri, May 25, 2018 at 3:14 AM, Johnson Lau  wrote:
> A graftroot design like this is a strict subset of existing signature 
> checking rules. If this is dangerous, the existing signature checking rules 
> must be dangerous.

While you may be right in this situation, I'm not sure that conclusion
follows from your argument. Whether or not a construction is safe does
not just depend on the consensus rules, but also on how it is used.
Otherwise you could as well argue that since OP_TRUE is possible right
now which is obviously insecure, nothing more dangerous can be
accomplished through any soft fork.

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.".

Cheers,

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


[bitcoin-dev] Minimizing the redundancy in Golomb Coded Sets

2018-05-25 Thread Pieter Wuille via bitcoin-dev
Hi all,

I spent some time working out the optimal parameter selection for the
Golomb Coded Sets that are proposed in BIP158:
https://gist.github.com/sipa/576d5f09c3b86c3b1b75598d799fc845

TL;DR: if we really want an FP rate of exactly 1 in 2^20, the Rice
parameter should be 19, not 20. If we don't, we should pick an FP rate
of 1 in a 1.4971*2^B. So for example M=784931 B=19 or M=1569861 B=20.

Cheers,

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


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

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

Thanks everyone who commented so far, but let me clarify the context
of this question first a bit more to avoid getting into the weeds too
much.

If it turns out to be necessary to explicitly commit to permitting
Graftroot spending, there are a number of approaches:
* Use a different witness version (or other marker directly in the
scriptPubKey) to enable Graftroot.
* Signal the permission to spend through Graftroot inside the Taproot
script as suggested by ZmnSCPxj.
* Make "Spend through Graftroot" a special script (possibly indirectly
with a Merkle tree in Taproot).
* Implement Graftroot as an opcode/feature inside the scripting
language (which may be more generically useful as a delegation
mechanism).
* Postpone Graftroot.

All of these are worse in either efficiency or privacy than always
permitting Graftroot spends directly. Because of that, I think we
should first focus on reasons why a lack of commitment to enabling
Graftroot may result in it being incompatible with certain use cases,
or other reasons why it could interfere with applications adopting
such outputs.

@Natanael: all of these concerns only apply to a new hypothetical
Taproot/Graftroot output type, which combines pay-to-pubkey and
pay-to-script in a single scriptPubKey that just contains a public
key. It doesn't apply to existing P2SH like constructions.

Also, the concern of making Graftroot optional does not apply to
Taproot, as the Taproot spending path's script is committed to (using
scriptPubKey = P + H(P,script)*G), allowing the script to be
explicitly chosen to be a non-spendable script, which the author could
prove is the case (without revealing it to the entire world).

It is also always possible to create a "script only" Taproot output
(without key that can unconditionally spend), by picking a pubkey that
is provably unspendable (hashing onto a curve point, in particular),
or through pubkey recovery.

Cheers,

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


[bitcoin-dev] Should Graftroot be optional?

2018-05-22 Thread Pieter Wuille via bitcoin-dev
Hello all,

Given the recent discussions about Taproot [1] and Graftroot [2], I
was wondering if a practical deployment needs a way to explicitly
enable or disable the Graftroot spending path. I have no strong
reasons why this would be necessary, but I'd like to hear other
people's thoughts.

As a refresher, the idea is that a script type could exists which
looks like a pubkey Q, but can be spent either:
* By signing the spending transaction directly using Q (key spending)
* By proving Q was derived as Q = P + H(P,S)*G, with a script S and
its inputs (Taproot script spending).
* By signing a script S using Q, and providing S's inputs (Graftroot
script spending).

Overall, these constructions let us create combined
pay-to-pubkey-or-script outputs that are indistinguishable, and don't
even reveal a script spending path existed in the first place when the
key spending path is used. The two approaches ((T)aproot and
(G)raftroot) for the script spending path have different trade-offs:
* T outputs can be derived noninteractively from key and scripts; G
outputs need an interaction phase where the key owner(s) sign off on
the potential script spending paths.
* T lets you prove what all the different spending paths are.
* T without any other technology only needs to reveal an additional
point when spending a single script; G needs half-aggregated
signatures [3] to achieve the same, which complicates design (see
[4]).
* G is more compact when dealing with many spending paths (O(1) in the
number of spending paths), while T spends need to be combined with
Merkle branches to deal with large number of spends (and even then is
still O(log n)).
* G spending paths can be added after the output is created; T
requires them be fixed at output creation time.

My question is whether it is safe to always permit both types of
script spending paths, or an explicit commitment to whether Graftroot
is permitted is necessary. In theory, it seems that this shouldn't be
needed: the key owners are always capable of spending the funds
anyway, so them choosing to delegate to others shouldn't enable
anything that isn't
possible by the key owners already.

There are a few concerns, however:

* Accidentally (participating in) signing a script may have more broad
consequences. Without Graftroot, that effect is limited to a single
transaction with specific inputs and outputs, and only as long as all
those inputs are unspent. A similar but weaker concern exists for
SIGHASH_NOINPUT.

* In a multisignature setting (where the top level key is an aggregate
of multiple participants), the above translates to the ability for a
(threshold satsisfying) subset of participants being able to (possibly
permanently) remove others from the set of signers (rather than for a
single output).

* In a situation where private keys are stored in an HSM, without
Graftroot an attacker needs access to the device and convince it to
sign for every output he wants to steal (assuming the HSM prevents
leaking private keys). With Graftroot, the HSM may be tricked into
signing a script that does not include itself. Arguably, in a
Graftroot setting such an HSM would need a degree of protection
similar to not leaking private keys applied to not signing scripts,
but this may be less obvious.

Overall, none of these are convincing points, but they do make me
uncomfortable about the effect the Graftroot spending path may have on
some use cases. Given that Taproot/Graftroot's primary advantage is
increasing fungibility by making all outputs look identical, it seems
good to discuss potential reasons such outputs couldn't or wouldn't be
adopted in certain applications.

  [1] 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015614.html
  [2] 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015700.html
  [3] 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014308.html
  [4] 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015838.html

Cheers,

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


Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

2018-05-18 Thread Pieter Wuille via bitcoin-dev
On Fri, May 18, 2018, 19:57 Olaoluwa Osuntokun via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Greg wrote:
> > What about also making input prevouts filter based on the scriptpubkey
> being
> > _spent_?  Layering wise in the processing it's a bit ugly, but if you
> > validated the block you have the data needed.
>
> AFAICT, this would mean that in order for a new node to catch up the filter
> index (index all historical blocks), they'd either need to: build up a
> utxo-set in memory during indexing, or would require a txindex in order to
> look up the prev out's script. The first option increases the memory load
> during indexing, and the second requires nodes to have a transaction index
> (and would also add considerable I/O load). When proceeding from tip, this
> doesn't add any additional load assuming that your synchronously index the
> block as you validate it, otherwise the utxo set will already have been
> updated (the spent scripts removed).
>

I was wondering about that too, but it turns out that isn't necessary. At
least in Bitcoin Core, all the data needed for such a filter is in the
block + undo files (the latter contain the scriptPubKeys of the outputs
being spent).

I have a script running to compare the filter sizes assuming the regular
> filter switches to include the prev out's script rather than the prev
> outpoint itself. The script hasn't yet finished (due to the increased I/O
> load to look up the scripts when indexing), but I'll report back once it's
> finished.
>

That's very helpful, thank you.

Cheers,

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


Re: [bitcoin-dev] {sign|verify}message replacement

2018-03-26 Thread Pieter Wuille via bitcoin-dev
Hello,

Thanks for starting a discussion about this idea.

A few comments inline:

On Wed, Mar 14, 2018 at 1:09 AM, Karl Johan Alm via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello,
>
> I am considering writing a replacement for the message signing tools
> that are currently broken for all but the legacy 1xx addresses. The
> approach (suggested by Pieter Wuille) is to do a script based
> approach. This does not seem to require a lot of effort for
> implementing in Bitcoin Core*. Below is my proposal for this system:
>
> A new structure SignatureProof is added, which is a simple scriptSig &
> witnessProgram container that can be serialized. This is passed out
> from/into the signer/verifier.
>

You need a bit more logic to deal with softforks and compatibility. The
question is which script validation flags you verify with:
* If you make them fixed, it means signatures can't evolve with new address
types being introduced that rely on new features.
* If you make it just consensus flags (following mainnet), it means that
people with old software will see future invalid signatures as always
valid; this is probably not acceptable.
* If you make it standardness flags, you will get future valid signatures
that fail to verify.

One solution is to include a version number in the signature, which
explicitly corresponds to a set of validation flags. When the version
number is something a verifier doesn't know, it can be reported as
inconclusive (it's relying on features you don't know about).

An solution is to verify twice; once with all consensus rules you know
about, and once with standardness rules. If they're both valid, the
signature is valid. If they're both invalid, the signature is invalid. If
they're different (consensus valid but standardness invalid), you report
the signature validation as inconclusive (it's relying on features you
don't know about). This approach works as long as new features only use
previous standardness-invalid scripts, but perhaps a version number is
still needed to indicate the standardness flags.

RPC commands:
>
> sign   [=false]
>

Why not extend the existing signmessage/verifymessage RPC? For legacy
addresses it can fall back to the existing signature algorithm, while using
the script-based approach for all others.


>
> Generates a signature proof for  using the same method that
> would be used to spend coins sent to .**
>
> verify[=false]
>
> Deserializes and executes the proof using a custom signature checker
> whose sighash is derived from . Returns true if the check
> succeeds, and false otherwise. The scriptPubKey is derived directly
> from .**
>
> Feedback welcome.
>
> -Kalle.
>
>
(**) If  is true,  is the sighash, otherwise
> sighash=sha256d(message).
>

That's very dangerous I'm afraid. It could be used to trick someone into
signing off on an actual transaction, if you get them to sign a "random
looking" prehashed message. Even if you have a prehashed message, there is
no problem with treating it as hex input to a second hashing step, so I
think the prehashed option isn't needed. It's why the existing message
signing functionality always forcibly prefixes "Bitcoin signed message:",
to avoid signing something that unintentionally corresponds to a message
intended for another goal.

Cheers,

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


Re: [bitcoin-dev] BIP 117 Feedback

2018-01-09 Thread Pieter Wuille via bitcoin-dev
On Jan 9, 2018 13:41, "Mark Friedenbach via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:

The use of the alt stack is a hack for segwit script version 0 which has
the clean stack rule. Anticipated future improvements here are to switch to
a witness script version, and a new segwit output version which supports
native MAST to save an additional 40 or so witness bytes. Either approach
would allow getting rid of the alt stack hack. They are not part of the
proposal now because it is better to do things incrementally, and because
we anticipate usage of MAST to better inform these less generic changes.


If the goal is to introduce a native MAST output type later, what is gained
by first having the tailcall semantics?

As far as I can see, this proposal does not have any benefits over Johnson
Lau's MAST idea [1]:
* It is more compact, already giving us the space savings a native MAST
version of the tail call semantics would bring.
* It does not need to work around limitations of push size limits or
cleanstack rules.
* The implementation (of code I've seen) is easier to reason about, as it's
just another case in VerifyScript (which you'd need for a native MAST
output later too) without introducing jumps or loops inside EvalScript.
* It can express the same, as even though the MBV opcode supports proving
multiple elements simultaneously, I don't see a way to use that in the tail
call. Every scenario that consists of some logic before deciding what the
tail call is going to be can be rewritten to have that logic inside each of
the branches, I believe.
* It does not interfere with static analysis (see further).
* Tail call semantics may be easier to extend in the future to enable
semantics that are not compactly representable in either proposal right
now, by allowing a single top-level script may invoke multiple subscripts,
or recursion. However, those sound even riskier and harder to analyse to
me, and I don't think there is sufficient evidence they're needed.

Native MAST outputs would need a new witness script version, which your
current proposal does indeed not need. However, I believe a new script
version will be desirable for other reasons regardless (returning invalid
opcodes to the pool of NOPs available for softforks, for example).

I will make a strong assertion: static analyzing the number of opcodes and
sigops gets us absolutely nothing. It is cargo cult safety engineering. No
need to perpetuate it when it is now in the way.


I'm not sure I agree here. While I'd like to see the separate execution
limits go away, removing them entirely and complicating future ability to
introduce unified costing towards weight of execution cost seems the wrong
way to go.

My reasoning is this: perhaps you can currently make an argument that the
current weight limit is sufficient in preventing overly expensive block
validation costs, due to a minimal ratio between script sizes and their
execution cost. But such an argument needs to rely on assumptions about
sighash caching and low per-opcode CPU time, which may change in the
future. In my view, tail call semantics gratuitously remove or complicate
the ability to reason about the executed code.

One suggestion to reduce the impact of this is limiting the per-script
execution to something proportional to the script size. However, I don't
think that addresses all potential concerns about static analysis (for
example, it doesn't easily let you prove all possible execution paths to a
participant in a smart contract).

Another idea that has been suggested on this list is to mark pushes of
potentially executable code on the stack/witness explicitly. This would
retain all ability to analyse, while still leaving the flexibility of
future extensions to tail call execution. If tail call semantics are
adopted, I strongly prefer an approach like that to blindly throwing out
all limits and analysis.

  [1] https://github.com/jl2012/bips/blob/mast/bip-mast.mediawiki

Cheers,

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


Re: [bitcoin-dev] BIP - Dead Man's Switch

2017-12-11 Thread Pieter Wuille via bitcoin-dev
On Dec 11, 2017 10:23, "Nick Pudar via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:

This topic has come up several times in recent years. While it is well
intentioned, it can have devastating outcomes for people that want to save
long term. If such a system were implemented, it would force people to move
funds around in order to not get nullified. In that process, it introduces
multiple opportunities for errors. Cold storage should be able to stay
cold. I personally would be apprehensive about implementing this kind of a
system.


Furthermore, if it rewards miners with funds that are expired, it creates
terrible incentives. Miners in their best interest could choose to censor
transactions that move funds close to their expiration time, to increase
their own future rewards.

Cheers,

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


Re: [bitcoin-dev] Visually Differentiable - Bitcoin Addresses

2017-10-30 Thread Pieter Wuille via bitcoin-dev
On Oct 30, 2017 15:21, "shiva sitamraju via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:

For example bc1qeklep85ntjz4605drds6aww9u0qr46qzrv5xswd35uhjuj8ahfcqgf6hak
in 461e8a4aa0a0e75c06602c505bd7aa06e7116ba5cd98fd6e046e8cbeb00379d6 is 62
bytes !


...

While I get the error/checksum capabilities Bech32 brings, any user would
prefer a 20 byte address with a checksum  over an address that would wrap
several lines !!


That's an unfair comparison. You're pasting a P2WSH address which contains
a 256-bit hash.

A P2WPKH address (which only contains a 160-bit hash, just like P2PKH and
P2SH) in Bech32 is only 42 characters, not 62.

Cheers,

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


Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST)

2017-09-22 Thread Pieter Wuille via bitcoin-dev
On Fri, Sep 22, 2017 at 2:54 PM, Sergio Demian Lerner via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> If the variable size increase is only a few bytes, then three
> possibilities arise:
>
> - one should allow signatures to be zero padded (to reach the maximum
> size) and abandon strict DER encoding
>
> - one should allow spare witness stack elements (to pad the size to match
> the maximum size) and remove the cleanstack rule. But this is tricky
> because empty stack elements must be counted as 1 byte.
>
> - signers must loop the generation of signatures until the signature
> generated is of its maximum size.
>

Or (my preference);

- Get rid of DER encoding alltogether and switch to fixed size signatures.

Cheers,

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


Re: [bitcoin-dev] proposal: extend WIF format for segwit

2017-09-16 Thread Pieter Wuille via bitcoin-dev
On Sep 15, 2017 01:56, "Thomas Voegtlin via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:

Note 3: we could also use a bech32 format for the private key, if it is
going to be used with a bech32 address. I am not sure if such a format
has been proposed already.


I've been working on an "extended bech32" format with 12 character checksum
rather than 6, for private keys and other things that need stronger
protection. It would guarantee correcting 4 errors, where normal bech32 can
only detect (but not correct) 4.

The rationale is that in the case of an address, if an error is detected,
you can ask the receiver for a corrected version. As that option doesn't
exist for private keys you want something stronger.

This has been a low-priority thing for me, though, and the computation work
to find a good checksum is significant.

Cheers,

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


  1   2   >