Re: [bitcoin-dev] Updating the Scaling Roadmap

[Pieter Wuille via bitcoin-dev]

On Jul 11, 2017 09:18, "Chris Stewart via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:

Concept ACK.

If drivechains are successful they should be viewed as the way we scale


I strongly disagree with that statement.

Drivechains, and several earlier sidechains ideas, are not a scalability
improvement, but merely enabling users to opt-in for another security model.

While obviously any future with wider adoption will need different
technologies that have different trade-offs, and anyone is free to choose
their security model, I don't think this particular one is interesting. In
terms of validation cost to auditors, it is as bad as just a capacity
increase on chain, while simultaneously adding the extra risk of miners
being able to vote to steal your money.

Cheers,

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

Re: [bitcoin-dev] Updating the Scaling Roadmap

[Pieter Wuille via bitcoin-dev]

On Tue, Jul 11, 2017 at 1:36 PM, Paul Sztorc  wrote:
> Pieter,
>
> I think that you have misrepresented Chris' view by taking it out of
> context. His complete quote reads "If drivechains are successful they should
> be viewed as the way we scale -- not hard forking the protocol." Chris is
> comparing Drivechains/sidechains to a hard fork.

I apologize here; I didn't mean to misrepresent his viewpoint.

> You went on to "disagree", but every point of contention you introduced was
> something that would apply to both drivechain-sourced capacity and
> hardfork-sourced capacity. Neither improves scalability, and both allow
> users only the opportunity to select a different security model. If I
> understand you, the point at which a security model does not become
> "interesting" to you, would be the exact same point in the drivechain and
> hardfork worlds. Both, at any rate, have the same effect on "validation cost
> to auditors".

If you're talking about the extreme case where every full node in the
increased capacity single chain model corresponds to a node that
validates both chains and all transfers between them in the
drivechains, I agree. At that point they become nearly equivalent in
terms of ease of adoption, resource costs, and capacity.

However, I don't think that is a realistic expectation. When
considering drivechains as a capacity increase, I believe most people
think about a situation where there are many chains that give an
increased capacity combined, but not everyone verifies all of them.
This is what I meant with uninteresting security model, as it requires
increased miner trust for preventing the other chains' coins from
being illegally transferred to the chain you're operating on.

Regardless, people are free experiment and adopt such an approach. The
nice thing about it not being a hardfork is that it does not require
network-wide consensus to deploy. However, I don't think they offer a
security model that should be encouraged, and thus doesn't have a
place on a roadmap.

> Since their sidechain coins cannot appreciate in value relative
> to the mainchain coins, users would only opt-in if they felt that they were
> sufficiently compensated for any and all risks. Hence, it is difficult to
> list this item as a drawback when, to the user, it is a strict improvement
> (at least, by any epistemological standard that I can think of). If you have
> new objections to these claims, I'm sure we would all benefit from hearing
> them, myself most of all.

Am I right in summarizing your point here as "This approach cannot
hurt, because if it were insecure, people can choose to not use it."?
I'm not sure I agree with that, as network effects or misinformation
may push users beyond what is reasonable.

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

[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

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

[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] Visually Differentiable - Bitcoin Addresses

[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] BIP - Dead Man's Switch

[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] BIP 117 Feedback

[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] {sign|verify}message replacement

[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 158 Flexibility and Filter Size

[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

[bitcoin-dev] Should Graftroot be optional?

[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] Should Graftroot be optional?

[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] Minimizing the redundancy in Golomb Coded Sets

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

[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

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

[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] New serialization/encoding format for key material

[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 proposal - Dandelion: Privacy Preserving Transaction Propagation

[Pieter Wuille via bitcoin-dev]

On Thu, May 10, 2018 at 5:59 AM, Bradley Denby via bitcoin-dev
 wrote:
> Hi all,
>
> ...
>
> This iteration of Dandelion has been tested on our own small network, and we
> would like to get the implementation in front of a wider audience. An
> updated
> BIP document with further details on motivation, specification,
> compatibility,
> and implementation is located here:
> https://github.com/mablem8/bips/blob/master/bip-dandelion.mediawiki

Hi Bradley,

thank you for working on this and going as far as implementing the
entire protocol. It looks like a very well-worked out idea already,
and its semantics can probably be adopted pretty much as-is. It would
be very exciting to bring these kinds of privacy improvements to
Bitcoin's P2P protocol.

I do have a number of comments on the specification and suggested
implementation in Bitcoin Core. I'm dumping my thoughts here, though
at this stage the specification is probably more important. The
implementation can be discussed more thoroughly when there is a PR
open.

Specification

* Overall, I think it would be worthwhile to describe the intended
node behavior in the BIP, at a higher level than Bitcoin Core
patchsets, but more detailed than what is in the BIP now. The
patch-based descriptions are both hard to read for developers working
on different systems who are unfamiliar with the Core codebase, and
don't make it clear to what extent implementation decisions are local
policy (which can be changed without network coordination), and which
follow from security or privacy arguments for the protocol.

* Interaction with feefilter (BIP 133) and Bloom filter (BIP 37). When
peers have given us filters on what transactions they will accept,
should Dandelion transactions be subject to the same? Should it
influence the choice of route? One simple possibility is perhaps to
avoid choosing BIP37 peers as Dandelion routes, and treat transactions
that do not pass the feefilter for its
would-be-outgoing-Dandelion-route as an automatic fluff - justified by
noting that relaying a transaction close to what fee is acceptable to
the network's mempools is already less likely to get good privacy due
to reduced chances of propagation.

* Mempool dependant transactions. It looks like the current
implementation accepts Dandelion transactions which are dependant on
other Dandelion (stempool) transactions and on confirmed blockchain
transactions, but not ones that are dependant on other unconfirmed
normal mempool transactions. Is this intentional, or resulting from a
difficulty in implementing this? Should the correct behaviour be
specified, or left free for nodes to decide?

* Orphan transactions. It looks like the current implementation
assumes no orphan transactions, but in a dynamic network (especially
with occasionally shuffling of Dandelion routes), I expect that
sometimes a dependent transaction will go on a different route than
its parent. Do you have any thoughts about that (even if not addressed
in a very implementation). Could we have a Dandelion-orphan-pool of
transactions, similar to the normal mempool has a set of orphan
transactions?

* Preferred connections. Should we bias the outgoing connection peer
selection code to prefer Dandelion-capable peers when the number is
too low?

Implementation

* How do we control the size of the stempool? Should acceptance of a
transaction to the normal mempool and/or blockchain result in eviction
of it (and conflicts) from the stempool? The existing code
intentionally has an upper bound on the size of the mempool to assure
predictable resource usage - the introduction of the stempool
shouldn't change that.

* I don't think you need to fully materialize all the routes. Instead,
you can just maintain a vector of 2 selected Dandelion-supporting
peers (and if one disconnects, replace just that one with another
one). To map incoming peers to an index in that list of peers, you can
use deterministic randomness (see SipHasher in the source code) with
the incoming node_id as data and a single global secret nonce (chosen
at startup, and reset on reshuffle).

* setDandelionInventoryKnown looks like it can grow unboundedly. A
rolling Bloom filter (like used for filterInventoryKnown) is perhaps
easier to guarantee predictable memory usage for.

* Use a scheduler job instead of a separate thread for shuffling the
routes (extra threads use unnecessarily large amounts of memory).

* (nit) coding style: doc/developer-notes.md has a number of
guidelines on coding style you may want to check out.

Cheers,

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

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

[Pieter Wuille via bitcoin-dev]

On Wed, Jun 6, 2018 at 5:48 AM, Tim Ruffing via bitcoin-dev
 wrote:
> On Thu, 2018-05-31 at 17:25 -0700, Pieter Wuille via bitcoin-dev wrote:
>> The best argument for why Graftroot does not need to be optional I
>> think was how Greg put it: "since the signer(s) could have signed an
>> arbitrary transaction instead, being able to delegate is strictly
>> less
>> powerful.".

...

> So
> I think Graftroot delegation is not "strictly less powerful" than just
> using a normal transaction: Graftroot enables to delegate in a way such
> that the delegation itself cannot be fixed in the chain. I think this
> is not possible currently. (Okay, you can just pass around the secret
> keys but has other problems obviously).
>
> Does this have practical implications?
> I don't see any but maybe this helps someone to identify an undesirable
> implication.

Interesting point; I don't see any relevant implications to this
either, but it's indeed good to point out this as a distinction.

> One way to be on the safe side and probably make Greg's argument go
> through is to just define the semantics such that (*) is allowed, i.e.,
> call g-sig a "Graftroot transaction" and give it transaction semantics.
> This provides a new perspective on Graftroot: Then Graftroot does not
> introduce new semantics but (*) is just an optimized version of (**)
> that uses fewer bytes and may be better for privacy.

So you're saying: the Graftroot signature data could be made identical
to the signature hash of an implicit 1-input-1-output transaction
spending the coin and creating a new output with the delegated script
as sPK, and the same amount.

I like that idea, but I don't think it can be *exactly* that. If it's
possible to take a Graftroot signature and instead construct a
transaction with it, you have inherently introduced a malleability.
The created outpoint will be different in both cases (different txid),
meaning that a chain of dependent unconfirmed transactions may be
broken by giving one participant the ability to choose between
Graftroot delegation or actual spending.

Two points here: (1) the implicit transaction would be 0 fee (unless
we somehow assign a portion of the fee to the delegation itself for
purposes of sighash computing), and (2) this sounds very similar to
the issue SIGHASH_NOINPUT is intended to solve. About that...

> Interestingly Andrew's blind-sig example and Johnson's fix (g-sig signs
> the outpoint) are just a special case. If g-sig has transaction
> semantics, it must sign the outpoint (and other stuff).

You're right when you're comparing with existing transaction sighash
semantics, but not when SIGHASH_NOINPUT would exist. If that were the
case, the only real difference is your point above of not being able
to commit the implicit transaction separately. In other words, we're
back to something Johnson pointed out earlier: some of the perceived
problems with Graftroot are also issues with SIGHASH_NOINPUT.

I wonder if we can make this explicit: Graftroot spending becomes a
special sighash flag (which possibly is only allowed at the top level)
- it builds an implicit transaction which moves all the coins to a
newly provided script, computes the sighash of that transaction
(taking all of the Graftroot signature's sighash flags into account -
including potentially SIGHASH_NOINPUT), and requires a signature with
that. The delegated script is then evaluated in the context of that
implicit transaction.

However, in order to avoid the malleability issue I think the actual
signature should still be different - possibly by simply passing
through the Graftroot sighash flag into the sighash being computed.

Cheers,

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

Re: [bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving Transaction Propagation

[Pieter Wuille via bitcoin-dev]

On 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
bitcoin-dev@lists.linuxfoundation.

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

[Pieter Wuille via bitcoin-dev]

On Sun, Jun 3, 2018 at 2:30 PM, Jonas Schnelli  wrote:
>> If there is interest, I can construct a code + implementation for any
>> of these in a few days probably, once the requirements are clear.
>
> Yes. Please.

Here is an example BCH code for base32 data which adds 27 checksum
characters, and can correct up to 7 errors occurring in strings up to
length 1023 (including the checksum characters themselves):
https://gist.github.com/sipa/d62f94faa1dcfd9ee4012d4c88955ba6

It can encode sequences of integers (between 0 and 31):

ref.py encode 13 7 22 23 11 29 21 15 3 26 20 26 4 7 6 11 19 1 6 8 31 13 4 19

> d8khta40r656y8xtnpxgldyne96vsfr83uch908se82g98rmnaa

Decode it again:

ref.py decode d8khta40r656y8xtnpxgldyne96vsfr83uch908se82g98rmnaa

> Decoded: 13 7 22 23 11 29 21 15 3 26 20 26 4 7 6 11 19 1 6 8 31 13 4 19

Or correct errors:

ref.py decode d8khta50r656y8xtmpxhlcyne96vsfr84udh908se82g98rmnat

> Errors found: d8khta?0r656y8xt?px?l?yne96vsfr8?u?h908se82g98rmna?
> Correction:   d8khta40r656y8xtnpxgldyne96vsfr83uch908se82g98rmnaa
> Decoded: 13 7 22 23 11 29 21 15 3 26 20 26 4 7 6 11 19 1 6 8 31 13 4 19

The code above is just a randomly picked BCH code, and has no special
properties beyond the ones it is designed for.

I can easily generate similar code for BCH codes with different properties.

Cheers,

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

[bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

Hello all,

given some recent work and discussions around BIP 174 (Partially
Signed Bitcoin Transaction Format) I'd like to bring up a few ideas.

First of all, it's unclear to me to what extent projects have already
worked on implementations, and thus to what extent the specification
is still subject to change. A response of "this is way too late" is
perfectly fine.

So here goes:

* Key-value map model or set model.

This was suggested in this thread:
https://twitter.com/matejcik/status/1002618633472892929

The motivation behind using a key-value model rather than a simple
list of records was that PSBTs can be duplicated (given to multiple
people for signing, for example), and merged back together after
signing. With a generic key-value model, any implementation can remove
the duplication even if they don't understand fields that may have
been added in future extensions.

However, almost the same can be accomplished by using the simpler set
model (the file consists of a set of records, with no duplication
allowed). This would mean that it would technically be legal to have
two partial signatures with the same key for the same input, if a
non-deterministic signer is used.

On the other hand, this means that certain data currently encoded
inside keys can be dropped, reducing the PSBT size. This is
particularly true for redeemscripts and witnessscripts, as they can
just be computed by the client when deserializing. The two types could
even be merged into just "scripts" records - as they don't need to be
separated based on the way they're looked up (Hash160 for P2SH, SHA256
for P2WSH). The same could be done for the BIP32 derivation paths,
though this may be expensive, as the client would need to derive all
keys before being able to figure out which one(s) it needs.

One exception is the "transaction" record, which needs to be unique.
That can either be done by adding an exception ("there can only be one
transaction record"), or by encoding it separately outside the normal
records (that may also be useful to make it clear that it is always
required).

* Ability for Combiners to verify two PSBT are for the same transaction

Clearly two PSBTs for incompatible transactions cannot be combined,
and this should not be allowed.

It may be easier to enforce this if the "transaction" record inside a
PSBT was required to be in a canonical form, meaning with empty
scriptSigs and witnesses. In order to do so, there could be per-input
records for "finalized scriptSig" and "finalized witness". Actually
placing those inside the transaction itself would only be allowed when
all inputs are finalized.

* Optional signing

I think all operation for the Signer responsibility should be
optional. This will inevitably lead to incompatibilities, but with the
intent of being forward compatible with future developments, I don't
think it is possible to require every implementation to support the
same set of scripts or contracts. For example, some signers may only
implement single-key P2PKH, or may only support signing SegWit inputs.
It's the user's responsibility to find compatible signers (which is
generally not an issue, as the different participants in a setup
necessarily have this figured out before being able to create an
address). This does mean that there can't be an unconditional test
vector that specifies the produced signature in certain circumstances,
but there could be "For implementations that choose to implement
signing for P2PKH inputs using RFC6979, the expected output given
input X and access to key Y is Z".

On the other hand, the Combiner and Finalizer roles can probably be
specified much more accurately than they are now.

* Derivation from xpub or fingerprint

For BIP32 derivation paths, the spec currently only encodes the 32-bit
fingerprint of the parent or master xpub. When the Signer only has a
single xprv from which everything is derived, this is obviously
sufficient. When there are many xprv, or when they're not available
indexed by fingerprint, this may be less convenient for the signer.
Furthermore, it violates the "PSBT contains all information necessary
for signing, excluding private keys" idea - at least if we don't treat
the chaincode as part of the private key.

For that reason I would suggest that the derivation paths include the
full public key and chaincode of the parent or master things are
derived from. This does mean that the Creator needs to know the full
xpub which things are derived from, rather than just its fingerprint.

* Generic key offset derivation

Whenever a BIP32 derivation path does not include any hardened steps,
the entirety of the derivation can be conveyed as "The private key for
P is equal to the private key for Q plus x", with P and Q points and x
a scalar. This representation is more flexible (it also supports
pay-to-contract derivations), more efficient, and more compact. The
downside is that it requires the Signer to support such derivation,
which I don't believe any current

Re: [bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

On Tue, Jun 19, 2018 at 7:20 AM, matejcik via bitcoin-dev
 wrote:

Thanks for your comments so far. I'm very happy to see people dig into
the details, and consider alternative approaches.

> 1) Why isn't the global type 0x03 (BIP-32 path) per-input? How do we
> know, which BIP-32 path goes to which input? The only idea that comes to
> my mind is that we should match the input's scriptPubKey's pubkey to
> this 0x03's key (the public key).

> If our understanding is correct, the BIP-32 path is global to save space
> in case two inputs share the same BIP-32 path? How often does that
> happen? And in case it does, doesn't it mean an address reuse which is
> discouraged?

Yes, the reason is address reuse. It may be discouraged, but it still
happens in practice (and unfortunately it's very hard to prevent
people from sending to the same address twice).

It's certainly possible to make them per-input (and even per-output as
suggested below), but I don't think it gains you much. At least when a
signer supports any kind of multisig, it needs to match up public keys
with derivation paths. If several can be provided, looking them up
from a global table or a per-input table shouldn't fundamentally
change anything.

However, perhaps it makes sense to get rid of the global section
entirely, and make the whole format a transaction plus per-input and
per-output extra fields. This would result in duplication in case of
key reuse, but perhaps that's worth the complexity reduction.

> 2) The global items 0x01 (redeem script) and 0x02 (witness script) are
> somewhat confusing. Let's consider only the redeem script (0x01) to make
> it simple. The value description says: "A redeem script that will be
> needed to sign a Pay-To-Script-Hash input or is spent to by an output.".
> Does this mean that the record includes both input's redeem script
> (because we need to sign it), but also a redeem script for the output
> (to verify we are sending to a correct P2SH)? To mix those two seems
> really confusing.
>
> Yet again, adding a new output section would make this more readable. We
> would include the input’s redeem script in the input section and the
> output’s redeem script again in the output section, because they’ll most
> likely differ anyway.

I think here it makes sense because there can actually only be (up to)
one redeemscript and (up to) one witnessscript. So if we made those
per-input and per-output, it may simplify signers as they don't need a
table lookup to find the correct one. That would also mean we can drop
their hashes, even if we keep a key-value model.

> 3) The sighash type 0x03 says the sighash is only a recommendation. That
> seems rather ambiguous. If the field is specified shouldn't it be binding?

Perhaps, yes.

> 4) Is it a good idea to skip records which types we are unaware of? We
> can't come up with a reasonable example, but intuitively this seems as a
> potential security issue. We think we should consider  introducing a
> flag, which would define if the record is "optional". In case the signer
> encounters a record it doesn't recognize and such flag is not set, it
> aborts the procedure. If we assume the set model we could change the
> structure to {data}. We are not keen on
> this, but we wanted to include this idea to see what you think.

Originally there was at least this intuition for why it shouldn't be
necessary: the resulting signature for an input is either valid or
invalid. Adding information to a PSBT (which is what signers do)
either helps with that or not. The worst case is that they simply
don't have enough information to produce a signature together. But an
ignored unknown field being present should never result in signing the
wrong thing (they can always see the transaction being signed), or
failing to sign if signing was possible in the first place. Another
way of looking at it, the operation of a signer is driven by queries:
it looks at the scriptPubKey of the output being spent, sees it is
P2SH, looks for the redeemscript, sees it is P2WSH, looks for the
witnessscript, sees it is multisig, looks for other signers'
signatures, finds enough for the threshold, and proceeds to sign and
create a full transaction. If at any point one of those things is
missing or not comprehensible to the signer, he simply fails and
doesn't modify the PSBT.

However, if the sighash request type becomes mandatory, perhaps this
is not the case anymore, as misinterpreting something like this could
indeed result in an incorrect signature.

If we go down this route, if a field is marked as mandatory, can you
still act as a combiner for it? Future extensions should always
maintain the invariant that a simple combiner which just merges all
the fields and deduplicates should always be correct, I think. So such
a mandatory field should only apply to signers?

> In general, the standard is trying to be very space-conservative,
> however is that really necessary? We would argue for clarity and ease of
> use over sp

Re: [bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

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

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

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

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

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

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

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

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

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

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

Agree.

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

That makes sense - I think we've already touched this when discussing
the requirement for UTXOs to be added. Perhaps those aren't added by
the Creator, but by some index server. The same could be true for the
scripts or derivations paths.

And indeed, most of the information in the derivation paths is
effectively opaque to the Creator - it's just some data given out by
the Signer about its keys that g

Re: [bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

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

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

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

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

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

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

What do you think?

Cheers,

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

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

[Pieter Wuille via bitcoin-dev]

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

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

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

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

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

Cheers,

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

Re: [bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

On 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] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Re: [bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

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

Re: [bitcoin-dev] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

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

So consider two possible topologies for a multiparty signing:

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

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

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

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

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

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

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

If you

[bitcoin-dev] Schnorr signatures BIP

[Pieter Wuille via bitcoin-dev]

Hello everyone,

Here is a proposed BIP for 64-byte elliptic curve Schnorr signatures,
over the same curve as is currently used in ECDSA:
https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki

It is simply a draft specification of the signature scheme itself. It
does not concern consensus rules, aggregation, or any other
integration into Bitcoin - those things are left for other proposals,
which can refer to this scheme if desirable. Standardizing the
signature scheme is a first step towards that, and as it may be useful
in other contexts to have a common Schnorr scheme available, it is its
own informational BIP.

If accepted, we'll work on more production-ready reference
implementations and tests.

This is joint work with several people listed in the document.

Cheers,

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

Re: [bitcoin-dev] Multiparty signatures

[Pieter Wuille via bitcoin-dev]

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

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

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

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

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

What are the advantages of what you're describing?

Cheers,

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

Re: [bitcoin-dev] Multiparty signatures

[Pieter Wuille via bitcoin-dev]

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

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

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

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

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

Re: [bitcoin-dev] Multiparty signatures

[Pieter Wuille via bitcoin-dev]

On Sun, Jul 8, 2018, 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] BIP 174 thoughts

[Pieter Wuille via bitcoin-dev]

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

Adding that sounds like a good idea, indeed.

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

Sounds good.

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

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

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

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

Cheers,

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

Re: [bitcoin-dev] Schnorr signatures BIP

[Pieter Wuille via bitcoin-dev]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ok.

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

Thanks for your comments, will review.

Cheers,

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

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

[Pieter Wuille via bitcoin-dev]

Hello all,

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

I believe there are two issues with this.

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

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

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

Opinions?

Cheers,

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

Re: [bitcoin-dev] Extending BIP174 for HTLCs

[Pieter Wuille via bitcoin-dev]

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

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

I've been thinking about this as well.

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

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

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

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

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

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

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

Cheers,

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

[bitcoin-dev] Bitcoin Core update notice

[Pieter Wuille via bitcoin-dev]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA512

Hello all,

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

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

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

- --
Pieter
-BEGIN PGP SIGNATURE-

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

Re: [bitcoin-dev] Generalised taproot

[Pieter Wuille via bitcoin-dev]

On Thu, Jul 12, 2018 at 6:52 PM Anthony Towns via bitcoin-dev
 wrote:
> On Fri, Jan 26, 2018 at 09:34:39PM +, Gregory Maxwell via bitcoin-dev 
> wrote:
> > [pubkey]
> >   \-[pubkey]&&CSV
> >  \-[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] Safer sighashes and more granular SIGHASH_NOINPUT

[Pieter Wuille via bitcoin-dev]

Hello everyone,

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

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

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

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

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

Cheers,

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

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

[Pieter Wuille via bitcoin-dev]

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

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

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

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

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

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

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

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

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

[Pieter Wuille via bitcoin-dev]

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

Hi Tamas,

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

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

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

Cheers,

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

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

[Pieter Wuille via bitcoin-dev]

On 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] IsStandard

[Pieter Wuille via bitcoin-dev]

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

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

Cheers,

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

[bitcoin-dev] Taproot proposal

[Pieter Wuille via bitcoin-dev]

Hello everyone,

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

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

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

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

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

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

Cheers,

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

Re: [bitcoin-dev] Taproot proposal

[Pieter Wuille via bitcoin-dev]

Thanks for the comments so far!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Re: [bitcoin-dev] Taproot proposal

[Pieter Wuille via bitcoin-dev]

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

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

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

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

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

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

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

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

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

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

[Pieter Wuille via bitcoin-dev]

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

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

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

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

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

Cheers,

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

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

[Pieter Wuille via bitcoin-dev]

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

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

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

Cheers,

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

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

[Pieter Wuille via bitcoin-dev]

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

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

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

Cheers,

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

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

[Pieter Wuille via bitcoin-dev]

Hello all,

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

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

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

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

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

Opinions?

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

Cheers,

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

Re: [bitcoin-dev] Taproot proposal

[Pieter Wuille via bitcoin-dev]

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

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

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

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

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

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

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

Cheers,

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

[bitcoin-dev] Miniscript

[Pieter Wuille via bitcoin-dev]

Hi all,

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

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

For example the script

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

in Miniscript notation would be

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

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

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

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

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

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

Cheers,

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

Re: [bitcoin-dev] testing bitcoin nodes

[Pieter Wuille via bitcoin-dev]

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

Hi Niels,

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

Cheers,

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

[bitcoin-dev] bip-tapscript resource limits

[Pieter Wuille via bitcoin-dev]

Hi all,

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

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

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

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

# Script size limit

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

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

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

# The 201 non-push opcodes limit

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

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

# The 1000 element limit for stack + altstack

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

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

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

# The 520 byte stack element size limit

Given that there are no kno

Re: [bitcoin-dev] Taproot proposal

[Pieter Wuille via bitcoin-dev]

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

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

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

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

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

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

Cheers,

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

[bitcoin-dev] Taproot updates

[Pieter Wuille via bitcoin-dev]

Hi all,

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

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

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

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

Cheers,

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

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

[Pieter Wuille via bitcoin-dev]

Hello all,

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

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

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

Thoughts?

Cheers,

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

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

[Pieter Wuille via bitcoin-dev]

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

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

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

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

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

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

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

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

What do people think?

Cheers,

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

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

[Pieter Wuille via bitcoin-dev]

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

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

Indeed!

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

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

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

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

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

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

Cheers,

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

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

[Pieter Wuille via bitcoin-dev]

Hi all,

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

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

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

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

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

What do people think?

Cheers,

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

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

[Pieter Wuille via bitcoin-dev]

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

Correct - just documenting the issue.

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

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

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

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

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

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

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

Exactly.

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

Re: [bitcoin-dev] Taproot (and graftroot) complexity (reflowed)

[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

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

[Pieter Wuille via bitcoin-dev]

Hello list,

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

1. Even public keys

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

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

This affects BIP 340 and 341.

2. Nonce generation

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

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

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

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

3. New tagged hash tags

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

What do people think?

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

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

[Pieter Wuille via bitcoin-dev]

Hi all,

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

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

1) Security model
-

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

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

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

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

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

2) Issues and solutions
---

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

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

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

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

2.a) Predictable k value

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

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

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

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

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

[Pieter Wuille via bitcoin-dev]

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

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

Hi Lloyd,

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

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

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

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

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

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

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

Cheers,

--
Pieter

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

Re: [bitcoin-dev] "Subsidy fraud" ?

[Pieter Wuille via bitcoin-dev]

I meant a miner claiming more in the coinbase's output than subsidy + fees
allow.
On Dec 10, 2015 5:26 AM, "xor"  wrote:

> Pieter Wuille mentions "subsidy fraud" in his recent talk:
> https://youtu.be/fst1IK_mrng?t=57m2s
>
> I was unable to google what this is, and the Bitcoin Wiki also does not
> seem
> to explain it.
>
> If this is a well-known problem, perhaps it would be a good idea to
> explain it
> somewhere?
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Segregated Witness features wish list

[Pieter Wuille via bitcoin-dev]

On Sun, Dec 13, 2015 at 4:25 PM, jl2012--- via bitcoin-dev
 wrote:
> I'm trying to list the minimal consensus rule changes needed for segwit
> softfork. The list does not cover the changes in non-consensus critical
> behaviors, such as relay of witness data.
>
> 1. OP_NOP4 is renamed as OP_SEGWIT
> 2. A script with OP_SEGWIT must fail if the scriptSig is not completely
> empty
> 3. If OP_SEGWIT is used in the scriptPubKey, it must be the only and the
> last OP code in the scriptPubKey, or the script must fail
> 4. The OP_SEGWIT must be preceded by exactly one data push (the "serialized
> script") with at least one byte, or the script must fail

The use of a NOP opcode to indicate a witness script was something I
considered at first too, but it's not really needed. You wouldn't be
able to use that opcode in any place a normal opcode could occur, as
it needs to be able to inspect the full scriptSig (rather than just
its resulting stack) anyway. So both in practice and conceptually it
is only really working as a template that gets assigned a special
meaning (like P2SH did). We don't need an opcode for that, and instead
we could say that any scriptPubKey (or redeemscript) that consists of
a single push is a witness program.

> 5. The most significant byte of serialized script is the version byte, an
> unsigned number
> 6. If the version byte is 0x00, the script must fail

What is that good for?

> 7. If the version byte is 0x02 to 0xff, the rest of the serialized script is
> ignored and the output is spendable with any form of witness (even if the
> witness contains something invalid in the current script system, e.g.
> OP_RETURN)

Do you mean the scriptPubKey itself, or the script that follows after
the version byte?
* The scriptPubKey itself: that's in contradiction with your rule 4,
as segwit scripts are by definition only a push (+ opcode), so they
can't be an OP_RETURN.
* The script after the version byte: agree - though it doesn't
actually need to be a script at all even (see further).

> 8. If the version byte is 0x01,
> 8a. rest of the serialized script is deserialized, and be interpreted as the
> scriptPubKey.
> 8b. the witness is interpreted as the scriptSig.
> 8c. the script runs with existing rules (including P2SH)

I don't think it's very useful to allow P2SH inside segwit, as we can
actually do better and allow segwit scripts to push the (perhaps 256
bit) hash of the redeemscript in the scriptPubKey, and have the full
redeemscript in the witness. See further for details. The numbers I
showed in the presentation were created using a simulation that used
that model already.

It is useful however to allow segwit inside P2SH (so the witness
program including version byte goes into the redeemscript, inside the
scriptSig). This allows old clients to send to new wallets without any
modifications (at slightly lower efficiency). The rules in this case
must say that the scriptSig is exactly a push of the redeemscript
(which itself contains the witness program), to provide both
compatibility with old consensus rules and malleability protection.

So let me summarize by giving an equivalent to your list above,
reflecting how my current prototype works:
A) A scriptPubKey or P2SH redeemscript that consists of a single push
of 2 to 41 bytes gets a new special meaning, and the byte vector
pushed by it is called the witness program.
A.1) In case the scriptPubKey pushes a witness program directly, the
scriptSig must be exactly empty.
A.2) In case the redeemscript pushes a witness program, the scriptSig
must be exactly the single push of the redeemscript.
B) The first byte of a witness program is the version byte.
B.1) If the witness version byte is 0, the rest of the witness program
is the actual script, which is executed after normal script evaluation
but with data from the witness rather than the scriptSig. The program
must not fail and result in a single TRUE on the stack, and nothing
else (to prevent stuffing the witness with pointless data during relay
of transactions).
B.2) if the witness version byte is 1, the rest of the witness program
must be 32 bytes, and a SHA256 hash of the actual script. The witness
must consist of an input stack to feed to the program, followed by the
serialized program itself (whose hash must match the hash pushed in
the witness program). It is executed after normal script evluation,
and must not fail and result in a single TRUE on the stack, and
nothing else.
B.3) if the witness version byte is 2 or higher, no further
interpretation of the data happens, but can be softforked in.

I'll write a separate mail on the block commitment structure.

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

Re: [bitcoin-dev] Block size: It's economics & user preparation & moral hazard

[Pieter Wuille via bitcoin-dev]

On Wed, Dec 16, 2015 at 3:53 PM, Jeff Garzik via bitcoin-dev
 wrote:
> 2) If block size stays at 1M, the Bitcoin Core developer team should sign a
> collective note stating their desire to transition to a new economic policy,
> that of "healthy fee market" and strongly urge users to examine their fee
> policies, wallet software, transaction volumes and other possible User
> impacting outcomes.

You present this as if the Bitcoin Core development team is in charge
of deciding the network consensus rules, and is responsible for making
changes to it in order to satisfy economic demand. If that is the
case, Bitcoin has failed, in my opinion.

What the Bitcoin Core team should do, in my opinion, is merge any
consensus change that is uncontroversial. We can certainly -
individually or not - propose solutions, and express opinions, but as
far as maintainers of the software goes our responsibility is keeping
the system running, and risking either a fork or establishing
ourselves as the de-facto central bank that can make any change to the
system would greatly undermine the system's value.

Hard forking changes require that ultimately every participant in the
system adopts the new rules. I find it immoral and dangerous to merge
such a change without extremely widespread agreement. I am personally
fine with a short-term small block size bump to kick the can down the
road if that is what the ecosystem desires, but I can only agree with
merging it in Core if I'm convinced that there is no strong opposition
to it from others.

Soft forks on the other hand only require a majority of miners to
accept them, and everyone else can upgrade at their leisure or not at
all. Yes, old full nodes after a soft fork are not able to fully
validate the rules new miners enforce anymore, but they do still
verify the rules that their operators opted to enforce. Furthermore,
they can't be prevented. For that reason, I've proposed, and am
working hard, on an approach that includes Segregated Witness as a
first step. It shows the ecosystem that something is being done, it
kicks the can down the road, it solves/issues half a dozen other
issues at the same time, and it does not require the degree of
certainty needed for a hardfork.

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

Re: [bitcoin-dev] Segregated Witness in the context of Scaling Bitcoin

[Pieter Wuille via bitcoin-dev]

On Wed, Dec 16, 2015 at 9:38 PM, Jeff Garzik via bitcoin-dev
 wrote:
> 4.3.  Observations on new block economic model
>
> SW complicates block economics by creating two separate, supply limited
> resources.

Not correct. I propose defining the virtual_block_size as base_size +
witness_size * 0.25, and limiting virtual_block_size to 1M. This
creates a single variable to optimize for. If accepted, miners are
incentived to maximize fee per virtual_block_size instead of per size.

Wallet software can individually choose whether to upgrade or not.
Once they upgrade, they get to perform 1.75x as many transactions for
the same fee (assuming non-complex transactions), and this is
independent of whether anyone else upgrades.

> 5.1.  Problem:  Pace of roll-out will be slow - Whole Ecosystem must be
> considered.
>
> The current apparent proposal is to roll out Segregated Witness as a soft
> fork, and keep block size at 1M.
>
> The roll-out pace cannot simply be judged by soft fork speed - which is
> months at best.  Analysis must the layers above:  Updating bitcoin-core (JS)
> and bitcoinj (Java), and then the timelines to roll out those updates to
> apps, and then the timeline to update those apps to create extended
> transactions.

Agree, however everyone can upgrade whenever they want, and get the
reduced fees as soon as they do. This is contrary to a hard fork,
which forces every full node to upgrade at once (though indeed, light
clients are not necessarily forced to upgrade).

> 5.2.  Problem:   Hard fork to bigger block size Just Works(tm) with most
> software, unlike SW.
>
> A simple hard fork such as BIP 102 is automatically compatible with the vast
> range of today's ecosystem software.
>
> SW requires merchants to upgrade almost immediately, requires wallet and
> other peripheral software upgrades to make use of.  Other updates are opt-in
> and occur more slowly.  BIP 70 processors need some updates.
>
> The number of LOC that must change for BIP 102 is very small, and the
> problem domain well known, versus SW.

It multiplies all current DoS vectors by a factor equal to the
capacity increase factor. SW increases capacity while leaving several
worst-case effects constant.

> 5.4.  Problem:   More complex economic policy, new game theory, new bidding
> structure risks.
>
> Splitting blocks into two pieces, each with separate and distinct behaviors
> and resource values, creates two fee markets.

I believe you have misunderstood the proposal in that case.

> 5.5.  Problem:  Current SW mining algorithm needs improvement
>
> Current SW block template maker does a reasonable job, but makes some naive
> assumptions about the fee market across an entire extended block.  This is a
> mismatch with the economic reality (just described).

Again, I think you misunderstood. The proposal includes a single new
formula for block size, and optimizes for it. In case the proposal is
accepted, the mining code is automatically as optimal as it was
before.

> 6. Conclusions and recommendations
>
> A "short term bump" hard fork block size increase addresses economic and
> ecosystem risks that SW does not.
>
> Bump + SW should proceed in parallel, independent tracks, as orthogonal
> issues.

I agree here. SW is not a replacement for a scale increase. However, I
think it can be adopted much more easily, as it doesn't require the
massively pervasive consensus that a hardfork requires to perform
safely.

> 7. Appendix - Other SW comments
>
> Hard forks provide much stronger validation, and ensure the network operates
> at a fully trustless level.
>
> SW hard fork is preferred, versus soft fork.  Soft forking SW places a huge
> amount of trust on miners to validate transaction signatures, versus the
> rest of the network, as the network slowly upgrades to newer clients.

But old clients may not care about the new rules, and they still
validate the old ones they chose to enforce.

Furthermore, soft forks cannot be prevented: miners can always choose
to enforce stronger rules than the network demands from them.

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

Re: [bitcoin-dev] Block size: It's economics & user preparation & moral hazard

[Pieter Wuille via bitcoin-dev]

On Wed, Dec 16, 2015 at 10:08 PM, Jeff Garzik  wrote:
>> You present this as if the Bitcoin Core development team is in charge
>> of deciding the network consensus rules, and is responsible for making
>> changes to it in order to satisfy economic demand. If that is the
>> case, Bitcoin has failed, in my opinion.
>
>
> This circles back to Problem #1:   Avoidance of a choice is a still a choice
> - failing to ACK a MAX_BLOCK_SIZE increase still creates very real Economic
> Change Event risk.

We are not avoiding a choice. We don't have the authority to make a choice.

> And #3:  If the likely predicted course is that Bitcoin Core will not accept
> a protocol change changing MAX_BLOCK_SIZE via hard fork in the short term,
> the core dev team should communicate that position clearly to users and
> media.

I indeed think we can communicate much better that deciding consensus
rules is not within our power.

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

Re: [bitcoin-dev] Segregated Witness in the context of Scaling Bitcoin

[Pieter Wuille via bitcoin-dev]

On Wed, Dec 16, 2015 at 10:27 PM, Jeff Garzik  wrote:
>> Not correct. I propose defining the virtual_block_size as base_size +
>> witness_size * 0.25, and limiting virtual_block_size to 1M. This
>> creates a single variable to optimize for. If accepted, miners are
>> incentived to maximize fee per virtual_block_size instead of per size.
>
>
> It is correct.  There are two separate sets of economic actors and levels of
> contention for each set of space.
>
> That is true regardless of the proposed miner selection algorithm.

Maybe I haven't explained this properly, so consider this example:

A miner receives sets of 200 byte transactions with all identical
fees. Non-witness ones (whose virtual size is thus 200 bytes) and a
witness one (where 120 of the 200 bytes are witness data, so its
virtual size is 80 + 120*0.25 = 110 bytes).

The consensus rules would limit 1) the base size to 100 bytes 2)
the virtual size to 100 bytes. However, as the virtual size is
defined as the sum of the base size plus a non-negative number,
satisfying (2) always implies satisfying (1).

Thus, the miners' best strategy is to accept the witness transactions,
as it allows 100/110=9090 transactions rather than
100/200=5000.

In fact, the optimal fee maximizing strategy is always to maximize fee
per virtual size.

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

[bitcoin-dev] On the security of softforks

[Pieter Wuille via bitcoin-dev]

Hello all,

For a long time, I was personally of the opinion that soft forks
constituted a mild security reduction for old full nodes, albeit one
that was preferable to hard forks due to being far less risky, easier,
and less forceful to deploy.

After thinking more about this, I'm not convinced that it is even that anymore.

Let's analyze all failure modes (and feel free to let me know whether
I've missed any specific ones):

1) The risk of an old full node wallet accepting a transaction that is
invalid to the new rules.

The receiver wallet chooses what address/script to accept coins on.
They'll upgrade to the new softfork rules before creating an address
that depends on the softfork's features.

So, not a problem.

2) The risk of an old full node wallet accepting a transaction whose
coins passed through a script that depends on the softforked rules.

It is reasonable that the receiver of a transaction places some trust
in the sender, and on the basis of that, decides to reduce the number
of confirmations before acceptance. In case the transaction indirectly
depends on a low-confirmation transaction using softforked rules, it
may be treated as an anyone-can-spend transaction. Obviously, no trust
can be placed in such a transactions not being reorged out and
replaced with an incompatible one.

However, this problem is common for all anyonecanspend transactions,
which are perfectly legal today in the blockchain. So, if this is a
worry, we can solve it by marking incoming transactions as "uncertain
history" in the wallet if they have an anyonecanspend transaction with
less than 6 confirmations in its history. In fact, the same problem to
a lesser extent exists if coins pass through a 1-of-N multisig or so,
because you're not only trusting the (indirect) senders, but also
their potential cosigners.

3) The risk of an SPV node wallet accepting an unconfirmed transaction
which is invalid to new nodes.

Defrauding an SPV wallet with an invalid unconfirmed transaction
doesn't change with the introduction of new consensus rules, as they
don't validate them anyway.

In the case the client trusts the full node peer(s) it is connected to
to do validation before relay, nodes can either indicate (service bit
or new p2p message) which softforks are accepted (as it only matters
to SPV wallets that wish to accept transactions using new style script
anyway), or wallets can rely on the new rules being non-standard even
to old full nodes (which is typically aimed for in softforks).

4) The risk of an SPV node wallet accepting a confirmed transaction
which is invalid to new nodes

Miners can of course construct an invalid block purely for defrauding
SPV nodes, without intending to get that block accepted by full nodes.
That is expensive (no subsidy/fee income for those blocks) and more
importantly it isn't in any way affected by softforks.

So the only place where this matters is where miners create a block
chain that violates the new rules, and still get it accepted. This
requires a hash rate majority, and sufficiently few economically
important full nodes that forking them off is a viable approach.

It's interesting that even though it requires forking off full nodes
(who will notice, there will be an invalid majority hash rate chain to
them), the attack only allows defrauding SPV nodes. It can't be used
to bypass any of the economic properties of the system (as subsidy and
other resource limits are still enforced by old nodes, and invalid
scripts will either not be accepted by old full nodes wallets, or are
as vulnerable as unrelated anyonecanspends).

Furthermore, it's easily preventable by not using the feature in SPV
wallets until a sufficient amount of economically relevant full nodes
are known to have upgraded, or by just waiting for enough
confirmations.



So, we'd of course prefer to have all full nodes enforce all rules,
but the security reduction is not large. On the other hand, there are
also security advantages that softforks offer:

A) Softforks do not require the pervasive consensus that hardforks
need. Soft forks can be deployed without knowing when all full nodes
will adopt the rule, or even whether they will ever adopt it at all.

B) Keeping up with hard forking changes puts load on full node
operators, who may choose to instead switch to delegating full
validation to third parties, which is worse than just validating the
old rules.

C) Hardfork coordination has a centralizing effect on development. As
hardforks can only be deployed with sufficient node deployment, they
can't just be triggered by miner votes. This requires central
coordination to determine flag times, which is incompatible with
having multiple independent consensus changes being proposed. For
softforks, something like BIP9 supports having multiple independent
softforks in flight, that nodes can individually chose to accept or
not, only requiring coordination to not choose clashing bit numbers.
For hardforks, there is effectively no choice

Re: [bitcoin-dev] Block size: It's economics & user preparation & moral hazard

[Pieter Wuille via bitcoin-dev]

On Fri, Dec 18, 2015 at 6:11 AM, Jeff Garzik  wrote:
>> You present this as if the Bitcoin Core development team is in charge
>> of deciding the network consensus rules, and is responsible for making
>> changes to it in order to satisfy economic demand. If that is the
>> case, Bitcoin has failed, in my opinion.
>
> Diverging from the satoshi block size change plan[1] and current economics
> would seem to require a high level of months-ahead communication to users.

I don't see any plan, but will you say the same thing when the subsidy
dwindles, and mining income seems to become uncertain? It will equally
be an economic change, which equally well will have been predictable,
and it will equally well be treatable with a hardfork to increase the
subsidy.

Yes, I'm aware the argument above is a straw man, because there was
clear expectation that the subsidy would go down asymptotically, and
much less an expectation that the blocksize would remain fixed
forever.

But I am not against a block size increase hard fork. My talk on
segregated witness even included proposed pursuing a hard fork at a
slightly later stage.

But what you're arguing for is that - despite being completely
expected - blocks grew fuller, and people didn't adapt to block size
pressure and a fee market, so the Core committee now needs to kick the
can down the road, because we can't accept the risk of economic
change. That sounds very much like a bailout to me.

Again. I am not against growth, but increasing in response to fear of
economic change is the wrong approach. Economic change is inevitable.

> Segregated Witness does not kick the can, it solves none of the problems #1,
> #3 - #8 explicitly defined and listed in email #1.
>
> 1)  A plan of "SW + no hard fork" is gambling with ECE risk, gambling there
> will be no Fee Event, because the core block size is still heavily contended
> -- 100% contended at time out SW rollout.

That is an assumption. I expect demand for transactions at a given
feerate to stop growing at a certain contention level (and we've
reached some level of contention already, with mempools not being
cleared for significant amounts of time already).

> SW mitigates this
> - only after several months

That is assuming a hard fork consensus forming, deployment,
activation, ... goes faster than a softfork.

> - only assuming robust adoption rates by up-layer ecosystem software, and

That's not required. Everyone who individually switches to new
transactions gets to do 1.75x more transactions for the same price
(and at the same time gets safer contracts, better script
upgradability, and more security models at their disposal), completely
independent of whether anyone else in the ecosystem does the same.

> - only assuming transaction volume growth is flat or sub-linear

The only question is how many transactions for what price. Contention
always happens at a specific feerate level anyway.

> Those conditions must go as planned to fulfill "SW kicked the can" -- a lot
> of if's.
>
> As stated, SW is orthogonal to the drift-into-uncharted-waters problem
> outlined in email #1, which a short term bump does address.

Both SW and a short bump (which is apparently not what BIP102 does
anymore?) increase capacity available per price, and yes, they are
completely orthogonal.

My only disagreement is the motivation (avoiding economic change, as
opposed to aiming for safe growth) and the claim that a capacity
increase hardfork is easier and safe(r) to roll out quickly than
sortfork SW.

Apart from that, we clearly need to do both at some point.

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

Re: [bitcoin-dev] Block size: It's economics & user preparation & moral hazard

[Pieter Wuille via bitcoin-dev]

On Dec 18, 2015 2:13 AM, "sick...@gmail.com"  wrote:
> 1.75 x 0.5 + 1 x 0.5 = 1.375
>
> after six month.
>
> An hard-fork on the others side would bring 1.75 since the activation, am
I right?

Yes.

However, SW immediately gives a 1.75 capacity increase for anyone who
adopts it, after the softfork, instantly. They don't need to wait for
anyone else.

A hard fork is an orthogonal improvement, which is also needed if we don't
want to be stuck with a constant maximum ultimately.

Hardforks can however only be deployed at a time when all full node
software can reasonably have agreed to upgrade, while a softfork can be
deployed much earlier.

They are independent improvements, and we need both. I am however of the
opinion that hard forks need a much clearer consensus and much longer
rollout timeframes to be safe (see my thread on the security of softforks).

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

Re: [bitcoin-dev] Capacity increases for the Bitcoin system.

[Pieter Wuille via bitcoin-dev]

On Tue, Dec 8, 2015 at 6:07 AM, Wladimir J. van der Laan wrote:
> On Mon, Dec 07, 2015 at 10:02:17PM +, Gregory Maxwell via bitcoin-dev
wrote:
>> TL;DR: I propose we work immediately towards the segwit 4MB block
>> soft-fork which increases capacity and scalability, and recent speedups
>> and incoming relay improvements make segwit a reasonable risk. BIP9
>> and segwit will also make further improvements easier and faster to
>> deploy. We’ll continue to set the stage for non-bandwidth-increase-based
>> scaling, while building additional tools that would make bandwidth
>> increases safer long term. Further work will prepare Bitcoin for further
>> increases, which will become possible when justified, while also
providing
>> the groundwork to make them justifiable.
>
> Sounds good to me.

Better late than never, let me comment on why I believe pursuing this plan
is important.

For months, the block size debate, and the apparent need for agreement on a
hardfork has distracted from needed engineering work, fed the external
impression that nothing is being done, and generally created a toxic
environment to work in. It has affected my own productivity and health, and
I do not think I am alone.

I believe that soft-fork segwit can help us out of this deadlock and get us
going again. It does not require the pervasive assumption that the entire
world will simultaneously switch to new consensus rules like a hardfork
does, while at the same time:
* Give a short-term capacity bump
* Show the world that scalability is being worked on
* Actually improve scalability (as opposed to just scale) by reducing
bandwidth/storage and indirectly improving the effectiveness of systems
like Lightning.
* Solve several unrelated problems at the same time (fraud proofs, script
extensibility, malleability, ...).

So I'd like to ask the community that we work towards this plan, as it
allows to make progress without being forced to make a possibly divisive
choice for one hardfork or another yet.

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

Re: [bitcoin-dev] Block size: It's economics & user preparation & moral hazard

[Pieter Wuille via bitcoin-dev]

That's exactly the point: a hard fork does not just affect miners, and
cannot just get decided by miners. All full nodes must have accepted the
new rules, or they will be forked off when the hashrate percentage triggers.

Furthermore, 75% is pretty terrible as a switchover point, as it guarantees
that old nodes will still see a 25% forked off chain temporarily.

My opinion is that the role of Bitcoin Core maintainers is judging whether
consensus for a hard fork exists, and is technically necessary and safe. We
don't need a hashpower vote to decide whether a hardfork is accepted or
not, we need to be sure that full noded will accept it, and adopt it in
time. A hashpower vote can still be used to be sure that miners _also_
agree.

Currently, a large amount of developers and others believe that the
treshhold for a hardfork is not reached, especially given the fact that we
scale in the short term, as well as make many changes that long-term
benefit scalability, with just a softfork (which does not require forking
off nodes that don't adopt the new rules, for whatever reason).

-- 
Pieter
On Dec 26, 2015 17:25, "digitsu"  wrote:

> So it seems that everyone is in agreement then, since a hard fork to 2M is
> orthogonal to SW, and also that core should not be involved in dictating
> what the consensus rules should be, then why not put BIP102 into play with
> a 75% mining majority activation and let the market decide.
>
> As it’s activation only involves the miners, and its implementation
> doesn’t affect users or exchanges, then it poses no complication to SW
> which can do done in parallel.
>
>
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Block size: It's economics & user preparation & moral hazard

[Pieter Wuille via bitcoin-dev]

On Dec 26, 2015 23:55, "Jonathan Toomim"  wrote:
>
> On Dec 26, 2015, at 8:44 AM, Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>> Furthermore, 75% is pretty terrible as a switchover point, as it
guarantees that old nodes will still see a 25% forked off chain temporarily.
>
> Yes, 75% plus a grace period is better. I prefer a grace period of about
4000 to 8000 blocks (1 to 2 months).

I think that's extremely short, even assuming there is no controversy about
changing the rules at all. Things like BIP65 and BIP66 already took
significantly longer than that, were uncontroversial, and only need miner
adoption. Full node adoption is even slower.

I think the shortest reasonable timeframe for an uncontroversial hardfork
is somewhere in the range between 6 and 12 months.

For a controversial one, not at all.

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

Re: [bitcoin-dev] Block size: It's economics & user preparation & moral hazard

[Pieter Wuille via bitcoin-dev]

On Dec 27, 2015 00:06, "Jonathan Toomim"  wrote:

> Given that a supermajority of users and miners have been asking for a
hard fork to increase the blocksize for years, I do not think that
mobilizing people to upgrade their nodes is going to be hard.
>
> When we do the hard fork, we will need to encourage people to upgrade
their full nodes. We may want to request that miners not trigger the fork
until some percentage of visible full nodes have upgraded.

I am generally not interested in a system where we rely on miners to make
that judgement call to fork off nodes that don't pay attention and/or
disagree with the change. This is not because I don't trust them, but
because I believe one of the principle values of the system is that its
consensus system should be hard to change.

I can't tell you what code to run of course, but I can decide what system I
find interesting to build. And it seems many people have signed off on
working towards a plan that does not include a hard fork being scheduled
right now: https://bitcoin.org/en/bitcoin-core/capacity-increases

Cheers,

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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

[Pieter Wuille via bitcoin-dev]

> "The problem case is where someone in a contract setup shows you a
script, which you accept as being a payment to yourself. An attacker could
use a collision attack to construct scripts with identical hashes, only one
of which does have the property you want, and steal coins.
>
> So you really want collision security, and I don't think 80 bits is
something we should encourage for that. Normal pubkey hashes don't have
that problem, as they can't be constructed to pay to you."
>
> ... but I'm unconvinced:
>
> "But it is trivial for contract wallets to protect against collision
attacks-- if you give me a script that is "gavin_pubkey CHECKSIG
arbitrary_data OP_DROP" with "I promise I'm not trying to rip you off, just
ignore that arbitrary data" a wallet can just refuse. Even more likely, a
contract wallet won't even recognize that as a pay-to-gavin transaction.
>
> I suppose it could be looking for some form of "gavin_pubkey
somebody_else_pubkey CHECKMULTISIG ... with the attacker using
somebody_else_pubkey to force the collision, but, again, trivial contract
protocol tweaks ("send along a proof you have the private key corresponding
to the public key" or "everybody pre-commits pubkeys they'll use at
protocol start") would protect against that.

Yes, this is what I worry about. We're constructing a 2-of-2 multisig
escrow in a contract. I reveal my public key A, you do a 80-bit search for
B and C such that H(A and B) = H(B and C). You tell me your keys B, and I
happily send to H(A and B), which you steal with H(B and C).

Sending along a proof does not help, you can't prove that you do not know
of a collision. Pre-committing does help, but is a very non-obvious
security requirement, something I strongly believe is far riskier in
practice.

Bitcoin does have parts that rely on economic arguments for security or
privacy, but can we please stick to using cryptography that is up to par
for parts where we can? It's a small constant factor of data, and it
categorically removes the worry about security levels.

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

Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?

[Pieter Wuille via bitcoin-dev]

On Fri, Jan 8, 2016 at 2:54 AM, Gavin Andresen via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> I'm saying we can eliminate one somewhat unlikely attack (that there is a
> bug in the code or test cases, today or some future version, that has to
> decide what to do with "version 0" versus "version 1" witness programs) by
> accepting the risk of another insanely, extremely unlikely attack.

Ok, just having one witness program version now is a somewhat different
proposal. It would be simpler for sure. The reasoning was that you'd need
this to not add significant overhead to small scripts, but that may not be
the case anymore. I wouldn't mind seeing numbers.

> My proposal would be to just do a version 0 witness program now, that is
> RIPEMD160(SHA256(script)).

I don't think that is wise. Bitcoin has a 128-bit security target for
everything else. We did not know that P2SH and similar constructs were
vulnerable to a collision attack at the time, but now we do, so the obvious
choice is to pick a size that is sufficiently large to maintain the 128-bit
security target. This is a no brainer to me; we're not proposing switching
to a 160-bit EC curve either, right?

> I'm really disappointed with the "Here's the spec, take it or leave it"
> attitude. What's the point of having a BIP process if the discussion just
> comes down to "We think more is better. We don't care what you think."

It is a proposal and we are discussing it. You first brought up some
criticisms in private, and I agreed with several things you said.

But it remains the proposal of a few people including me, and I do not
agree with the specific suggestion of reducing the security target for
witness scripts to 80 bits.

We are not deciding what the system will be. We're making a proposal, and
hope that due to its technical merit, the ecosystem will adopt it. You're
free to participate in that discussion.

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

Re: [bitcoin-dev] Segwit Upgrade Procedures & Block Extension Data

[Pieter Wuille via bitcoin-dev]

On Thu, Jan 28, 2016 at 7:51 PM, Peter Todd via bitcoin-dev
 wrote:
> A few notes on upgrade procedures associated with segregated witnesses:

> While Pieter Wuille's segwit branch(1) doesn't yet implement a fix for
> the above problem, the obvious thing to do is to add a new service bit
> such as NODE_SEGWIT, and/or bump the protocol version, and for outgoing
> peers only connect to peers with segwit support.

Agree, I've merged the changes to switch to a service bit instead.
We'll need further changes to prefer connecting to segwit nodes.

> Segwit isn't going to be the last thing that adds new block data. For
> example, my own prev-block-proof proposal(3) requires that blocks commit
> to another tree, which itself is calculated using a nonce that must be
> passed along with the block data. (U)TXO commitments are another
> possible future example.

> Unfortunately, this means that the next soft-fork upgrade to add
> additional data will have the above relaying problem all over again!
> Even a minimal upgrade adding a new commitment - like my
> prev-block-proof proposal - needs to at least add another nonce for
> future upgrades. In addition to having to upgrade full nodes, this also
> requires systems like the relay network to upgrade, even though they may
> not themselves otherwise need to care about the contents of blocks.

Those are good arguments for making the witness data more extensible.
>
> A more subtle implication of this problem is how do you handle parallel
> upgrades, as proposed by BIP9? Splitting the P2P network into
> non-upgraded nodes, and a much smaller group of upgraded nodes, is bad
> enough when done every once in a awhile. How does this look with more
> frequent upgrades, not necessarily done by teams that are working
> closely with each other?

I don't expect that changes that add more data to be relayed with
blocks will be frequent, though I certainly agree there may be some.

> Proposal: Unvalidated Block Extension Data
> ==

(snip)

This will need a backward-incompatible change to the current segwit
change anyway, so at the risk of more bikeshedding, let me propose
going a bit further:

* The coinbase scriptSig gets a second number push (similar to the
current BIP34 height push), which pushes a number O. O is a byte
offset inside the coinbase transaction (excluding its witness data)
that points to a 32-byte hash H. This is more flexible and more
compact than what we have now (a suggestion by jl2012).
* H is the root of a Merkle tree, whose leaves are the hashes of the
coinbase witness's stack items.
* Item 0 of the coinbase witness stack must be 32 bytes, and must be
equal to the witness tree root.
* No further restrictions on the rest of the stack items; these can be
used for future commitments.

> A significant design consideration is that if arbitrary data can be
> added, it is very likely that miners will make use of that ability for
> non-Bitcoin purposes; we've already run into problems deploying segwit
> itself because of pools using the coinbase space for advertising and
> merge-mining. Avoiding this problem is easiest with a merkelized
> key:value mapping, with the ability to use collision-resistant ID's as
> keys (e.g. UUID).

I agree with the concern, but I don't really understand how this idea solves it.

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

Re: [bitcoin-dev] [BIP Draft] Allow zero value OP_RETURN in Payment Protocol

[Pieter Wuille via bitcoin-dev]

On Feb 2, 2016 18:04, "Peter Todd via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> On Tue, Jan 26, 2016 at 09:44:48AM -0800, Toby Padilla via bitcoin-dev
wrote:
> > I really don't like the idea of policing other people's use of the
> > protocol. If a transaction pays its fee and has a greater than dust
value,
> > it makes no sense to object to it.
>
> I'll point out that getting a BIP for a feature is *not* a hard
> requirement for deployment. I'd encourage you to go write up your BIP
> document, give it a non-numerical name for ease of reference, and lobby
> wallet vendors to implement it.
>
> While I'll refrain from commenting on whether or not I think the feature
> itself is a good idea, I really don't want people to get the impression
> that we're gatekeepers for how people choose use Bitcoin.

I'll go further: whatever people have commented here and elsewhere about
this feature (myself included) are personal opinions on the feature itself,
in the hope you take the concerns into account.

These comments are not a judgement on whether this should be accepted as a
BIP. Specifically, the BIP editor should accept a BIP even if he personally
dislikes the ideas in it, when the criteria are satisfied.

Beyond that, having a BIP accepted does not mean wallets have to implement
it. That's up to the individual wallet authors/maintainers.

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

Re: [bitcoin-dev] Compact Block Relay BIP

[Pieter Wuille via bitcoin-dev]

On 05/03/2016 12:13 AM, lf-lists at mattcorallo.com (Matt Corallo) wrote:
> Hi all,
> 
> The following is a BIP-formatted design spec for compact block relay
> designed to limit on wire bytes during block relay. You can find the
> latest version of this document at
> https://github.com/TheBlueMatt/bips/blob/master/bip-TODO.mediawiki.

Hi Matt,

thank you for working on this!

> ===New data structures===
> Several new data structures are added to the P2P network to relay
> compact blocks: PrefilledTransaction, HeaderAndShortIDs,
> BlockTransactionsRequest, and BlockTransactions. Additionally, we
> introduce a new variable-length integer encoding for use in these data
> structures.
> 
> For the purposes of this section, CompactSize refers to the
> variable-length integer encoding used across the existing P2P protocol
> to encode array lengths, among other things, in 1, 3, 5 or 9 bytes.

This is a not, but I think it's a bit strange to have two separate
variable length integers in the same specification. I understand is one
is already the default for variable-length integers currently, and there
are reasons to use the other one for efficiency reasons in some places,
but perhaps we should aim to get everything using the latter?

> New VarInt
> Variable-length integers: bytes are a MSB base-128 encoding of the number.
> The high bit in each byte signifies whether another digit follows. To make
> sure the encoding is one-to-one, one is subtracted from all but the last
> digit.

Maybe it's worth mentioning that it is based on ASN.1 BER's compressed
integer format (see
https://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf
section 8.1.3.5), though with a small modification to make every integer
have a single unique encoding.

> HeaderAndShortIDs
> A HeaderAndShortIDs structure is used to relay a block header, the short
> transactions IDs used for matching already-available transactions, and a
> select few transactions which we expect a peer may be missing.
> 
> |shortids||List of uint64_ts||8*shortids_length bytes||Little
> Endian||The short transaction IDs calculated from the transactions which
> were not provided explicitly in prefilledtxn

I tried to derive what length of short ids is actually necessary (some
write-up is on
https://gist.github.com/sipa/b2eb2e486156b5509ac711edd16153ed but it's
incomplete).

For any reasonable numbers I can come up with (in a very wide range),
the number of bits needed is very well approximated by:

  log2(#receiver_mempool_txn * #block_txn_not_in_receiver_mempool /
acceptable_per_block_failure_rate)

For example, with 2 mempool transactions, 2500 transactions in a
block, 95% hitrate, and a chance of 1 in 1 blocks to fail to
reconstruct, needed_bits = log2(2 * 2500 * (1 - 0.95) / 0.0001) =
34.54, or 5 byte txids would suffice.

Note that 1 in 1 failures may sound like a lot, but this is for each
individual connection, and since every transmission uses separately
salted identifiers, occasional failures should not affect global
propagation. Given that transmission failures due to timeouts, network
connectivity, ... already occur much more frequently than once every few
gigabytes (what 1 blocks corresponds to), that's probably already
more than enough.

In short: I believe 5 or 6 byte txids should be enough, but perhaps it
makes sense to allow the sender to choose (so he can weigh trying
multiple nonces against increasing the short txid length).

> Short transaction IDs
> Short transaction IDs are used to represent a transaction without
> sending a full 256-bit hash. They are calculated by:
> # single-SHA256 hashing the block header with the nonce appended (in
> little-endian)
> # XORing each 8-byte chunk of the double-SHA256 transaction hash with
> each corresponding 8-byte chunk of the hash from the previous step
> # Adding each of the XORed 8-byte chunks together (in little-endian)
> iteratively to find the short transaction ID

An alternative would be using SipHash-1-3 (a form of SipHash with
reduced iteration counts; the default is SipHash-2-4). SipHash was
designed as a Message Authentication Code, where the security
requirements are much stronger than in our case (in particular, we don't
care about observers being able to finding the key, as the key is just
public knowledge here). One of the designers of SipHash has commented
that SipHash-1-3 for collision resistance in hash tables may be enough:
https://github.com/rust-lang/rust/issues/29754#issuecomment-156073946

Using SipHash-1-3 on modern hardware would take ~32 CPU cycles per txid.

> ===Implementation Notes===

There are a few more heuristics that MAY be used to improve performance:

* Receivers should treat short txids in blocks that match multiple
mempool transactions as non-matches, and request the transactions. This
significantly reduces the failure to reconstruct.

* When constructing a compact block to send, the sender can verify it
against its own mempoo

Re: [bitcoin-dev] BIP141 segwit consensus rule update: extension of witness program definition

[Pieter Wuille via bitcoin-dev]

On Jun 8, 2016 18:46, "Luke Dashjr via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> On Wednesday, June 08, 2016 8:23:51 AM Johnson Lau wrote:
> > If someday 32 bytes hash is deemed to be unsafe, the txid would also be
> > unsafe and a hard fork might be needed. Therefore, I don’t see how a
> > witness program larger than 40 bytes would be useful in any case (as it
is
> > more expensive and takes more UTXO space). I think Pieter doesn’t want
to
> > make it unnecessarily lenient.
>
> There is no harm in being lenient, but it limits the ability to do
softfork
> upgrades in the future. I appreciate Pieter's concern that we'd need to do
> more development and testing to go to this extreme, which is why I am only
> asking the limit raised to 75 bytes.

No strong opinion, but I'd rather not change it anymore, as I don't see the
point. Any data you would want to encode there can be moved to the witness
at 1/4 the cost and replaced by a 256-bit hash. If the data is 43 bytes or
higher, that is even cheaper. The only thing that cannot be in the hash is
metadata to indicate what hashing/rule scheme itself is used. I think 68
bits (OP_n + 8 bytes) for that is plenty.

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

Re: [bitcoin-dev] RFC for BIP: Derivation scheme for P2WPKH-nested-in-P2SH based accounts

[Pieter Wuille via bitcoin-dev]

On Jun 15, 2016 12:53, "Daniel Weigl via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> That would be a big privacy leak, imo. As soon as both outputs are spent,
its visible
> which one was the P2WPKH-in-P2SH and which one the pure P2WPKH and as a
consequence
> you leak which output was the change and which one the actual sent output
>
> So, i'd suggest to even make it a requirement for "normal"
send-to-single-address transactions
> to always use the same output type for the change output (if the wallet
is able to recognize it)

Indeed, and you can go even further. When there are multiple "sending"
outputs, pick one at random, and mimic it for the change output. This means
that if you have a P2PKH and 3 P2SH sends, you'll have 25% chance for a
P2PKH change output, and 75% chance for a P2SH output.

You can go even further of course, if you want privacy that remains after
those sends get spent. In that case, you also need to match the template of
the redeemscript/witnessscript. For example, if the send you are mimicking
is a 2-of-3, the change output should also use 2-of-3.

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

Re: [bitcoin-dev] Even more proposed BIP extensions to BIP 0070

[Pieter Wuille via bitcoin-dev]

On Jun 23, 2016 12:56, "Peter Todd via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> In any case, I'd strongly argue that we remove BIP75 from the bips
repository,
> and boycott wallets that implement it. It's bad strategy for Bitcoin
developers
> to willingly participate in AML/KYC, just the same way as it's bad for
Tor to
> add wiretapping functionality, and W3C to support DRM tech. The minor
tactical
> wins you'll get our of this aren't worth it.

I hope you're not seriously suggesting to censor a BIP because you feel it
is a bad idea.

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

Re: [bitcoin-dev] Even more proposed BIP extensions to BIP 0070

[Pieter Wuille via bitcoin-dev]

On Thu, Jun 23, 2016 at 1:39 PM, Peter Todd  wrote:
> On Thu, Jun 23, 2016 at 01:30:45PM +0200, Pieter Wuille wrote:
>> On Jun 23, 2016 12:56, "Peter Todd via bitcoin-dev" <
>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>> > In any case, I'd strongly argue that we remove BIP75 from the bips
>> repository,
>> > and boycott wallets that implement it. It's bad strategy for Bitcoin
>> developers
>> > to willingly participate in AML/KYC, just the same way as it's bad for
>> Tor to
>> > add wiretapping functionality, and W3C to support DRM tech. The minor
>> tactical
>> > wins you'll get our of this aren't worth it.
>>
>> I hope you're not seriously suggesting to censor a BIP because you feel it
>> is a bad idea.
>
> For the record, I think the idea of the bips repo being a pure publication
> platform isn't a good one and doesn't match reality; like it or not by
> accepting bips we're putting a stamp of some kind of approval on them.

We? I don't feel like I have any authority to say what goes into that
repository, and neither do you. We just give technical opinion on
proposals. The fact that it's under the bitcoin organization on github
is a historical artifact.

> I have zero issues with us exercising editorial control over what's in the 
> bips
> repo; us doing so doesn't in any way prevent other's from publishing 
> elsewhere.

Editorial control is inevitable to some extent, but I think that's
more a matter of process than of opinion. Things like "Was there
community discussion?", "Is it relevant?", "Is there a reference
implementation?". I don't think that you objecting for moral reasons
to an otherwise technically sound idea is a reason for removal of a
BIP. You are of course free to propose alternatives, or recommend
against its usage.

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

Re: [bitcoin-dev] Even more proposed BIP extensions to BIP 0070

[Pieter Wuille via bitcoin-dev]

On Jun 23, 2016 14:10, "Peter Todd"  wrote:

> Right, so you accept that we'll exert some degree of editorial control;
the
> question now is what editorial policies should we exert?

No, I do not. I am saying that some degree of editorial control will
inevitably exist, simply because there is some human making the choice of
assigning a BIP number and merging. My opinion is that we should try to
restrict that editorial control to only be subject to objective process,
and not be dependent on personal opinions.

> My argument is that rejecting BIP75 is something we should do on
> ethical/strategic grounds. You may disagree with that, but please don't
troll
> and call that "advocating censorship"

I think that you are free to express dislike of BIP75. Suggesting to remove
it for that reason is utterly ridiculous to me, whatever you want to call
it.

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

Re: [bitcoin-dev] BIP 151 use of HMAC_SHA512

[Pieter Wuille via bitcoin-dev]

On Jun 29, 2016 07:05, "Ethan Heilman via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> >It's also not clear to me why the HMAC, vs just
SHA256(key|cipher-type|mesg).  But that's probably just my crypto
ignorance...
>
> SHA256(key|cipher-type|mesg) is an extremely insecure MAC because of
> the length extension property of SHA256.

This property does technically not apply here, as the output of the hash is
kept secret, and the possible messages are constants (which are presumably
chosen in such a way that one is never an extension of another).

However, this is a good example of why you can't generically use a hash
function in places where you want a MAC (aka "a hash with a shared
secret"). Furthermore, if you already have a hash function anyway, HMAC is
very easy construct on top of it.

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

Re: [bitcoin-dev] BIP 151

[Pieter Wuille via bitcoin-dev]

On Thu, Jun 30, 2016 at 11:57 AM, Eric Voskuil via bitcoin-dev
 wrote:
> The proliferation of node identity is my primary concern - this relates to 
> privacy and the security of the network.

I think this is a reasonable concern.

However, node identity is already being used widely, and in a very
inadvisable way:
* Since forever there have been lists of 'good nodes' to pass in
addnode= configuration options.
* Various people run multiple nodes in different geographic locations,
peering with each other.
* Various pieces of infrastructure exist that relies on connecting to
well-behaving nodes (miner relay networks, large players peering
directly with each other, ...)
* Several lightweight clients support configuring a trusted host to connect to.

Perhaps you deplore that fact, but I believe it is inevitable that
different pieces of the network will make different choices here. You
can'tg prevent people from create connections along preexisting trust
lines. That does not mean that the network as a whole relies on first
establishing trust everywhere.

And I do think there are advantages.

BIP 151 on its own gives you opportunistic encryption. You're very
right to point out that this does not give you protection from active
attackers, and that active attacking is relatively easy through sybil
attacks. I still prefer my attacker to actually do that over just
listening in on my connection. And yes, we should also work on
improving the privacy nodes and wallets have orthogonal to encryption,
but nothing will make everything perfectly private.

BIP 151 plus a simple optional pre-shared-secret authentication
extension can improve upon pure IP-based authentication, as well as
simplify things like SSL tunnels, and onion addresses purely used as
identity. This will still require explicit configuration, but not more
than now.

BIP 151 plus a non-leaking public key authentication scheme (where
peers can query "are you the peer with pubkey X?" but don't learn
anything if the answer is no) with keys specific to the IP addresses
can give a TOFU-like security. Nodes already remember IP addresses
they've succesfully interacted with in the past, and ban IP addresses
that misbehave. Being able to tell whether a node you connect to is
the same as one you've connected to before is a natural extension of
this, and does not require establishing any real-world identity beyond
what we're already implicitly relying on.

Perhaps these use cases and their security assumptions should be
spelled out more clearly in the BIP. If there is a misunderstanding,
it should be clearly stated that BIP 151 is only a building block for
further improvements

> Secondarily I am concerned about users operating under a false assumption 
> about the strength of privacy.

This is a widespread problem, but it exists far outside the scope of
this proposal. The privacy properties of Bitcoin are often
misrepresented and even used as advertizements. The solution is
education, not avoiding improvements because they may be
misunderstood.

> The complexity of the proposed construction is comparable to that of Bitcoin 
> itself.

I really think this is an exaggeration. It's a diffie-hellman
handshake and a stream cipher (both very common constructions), that
apply to individual connections. There are no consensus risks nor a
requirement for coordinated change through the network. The
cryptographic code can be directly reused from a well-known project
(OpenSSH), and is very small in size.

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

Re: [bitcoin-dev] BIP Number Request: Addresses over Audio

[Pieter Wuille via bitcoin-dev]

On Wed, Aug 10, 2016 at 7:28 PM, Erik Aronesty via bitcoin-dev
 wrote:
> By sending a public seed,  there's no way for someone to use the transmitted
> address and trace the total amount of payments to it.

Worse. By revealing a public seed, anyone who has seen it (= anyone
who ever pays you through it) can identity all payments to _any_
address derived from that seed.

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

Re: [bitcoin-dev] New BIP: Dealing with OP_IF and OP_NOTIF malleability in P2WSH

[Pieter Wuille via bitcoin-dev]

On Aug 17, 2016 00:23, "Russell O'Connor via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> If one's goal is to mess with an transaction to prevent it from being
mined, it is more effective to just not relay the transaction rather than
to mess with the witness.  Given two transactions with the same txid and
different witness data, miners and good nodes ought to mine/relay the
version with the lower cost (smaller?) witness data.

That implies that everyone will see both versions and be able to make that
choice. Unfortunately, those two versions will be definition be in conflict
with each other, and thus only one will end up paying a fee. We're can't
relay two transactions for the price of one, or we'd expose the p2p network
to a very cheap DDoS attack: just send increasingly small versions of the
same transaction.

Segwit's third party mallebility protection makes it not an issue for
dependent contracts if transactions are mauled (=apparently the verb
related to malleability), but there are still good reasons for senders not
to gratuitously make their transactions extensible in size or other
resources.

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

Re: [bitcoin-dev] New BIP: Dealing with OP_IF and OP_NOTIF malleability in P2WSH

[Pieter Wuille via bitcoin-dev]

On Aug 17, 2016 00:36, "Russell O'Connor"  wrote:

> Can I already do something similar with replace by fee, or are there
limits on that?

BIP125 and mempool eviction both require the replacing transaction to have
higher fee, to compensate for the cost of relaying the replaced
transaction(s).

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

Re: [bitcoin-dev] BIP Status updates (including to Active/Final Status) - BIP 39, BIP 43, BIP 44, BIP 67, BIP 111, BIP 125, BIP 130

[Pieter Wuille via bitcoin-dev]

This is not the place to discuss the merits and/or issues of these BIPs,
only whether they should be treated as final.

On Aug 25, 2016 10:51, "Marek Palatinus via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> As Luke pointed, BIP44 is already used by many wallets and to my knowledge
> people don't have any real world issues with that, including loading funds
> in another BIP44 wallet. I'm not saying that BIP44 is perfect from all
> points of view, but IMO it just works for most use cases. Let's set it as
> final, and propose competing standards which cover all your concerns.
>
> slush
>
> On Thu, Aug 25, 2016 at 10:12 AM, Jonas Schnelli via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>>
>> > The development paradigm of "maybe detect funds" is not something we
>> > should *not* encourage for Bitcoin IMO.
>>
>> Sorry. That was one "not" to many.
>>
>> 
>>
>>
>> ___
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>>
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP 151

[Pieter Wuille via bitcoin-dev]

Hello Eric,

I felt like I still owed you a response to the points below.

On Thu, Jun 30, 2016 at 5:10 PM, Eric Voskuil  wrote:
> Pieter, these are in my opinion very reasonable positions. I've made some 
> observations inline.
>
>> On Jun 30, 2016, at 3:03 PM, Pieter Wuille  wrote:
>>
>> On Thu, Jun 30, 2016 at 11:57 AM, Eric Voskuil via bitcoin-dev
>>  wrote:
>>> The proliferation of node identity is my primary concern - this relates to 
>>> privacy and the security of the network.
>>
>> I think this is a reasonable concern.
>>
>> However, node identity is already being used widely, and in a very
>> inadvisable way:
>> * Since forever there have been lists of 'good nodes' to pass in
>> addnode= configuration options.
>> * Various people run multiple nodes in different geographic locations,
>> peering with each other.
>> * Various pieces of infrastructure exist that relies on connecting to
>> well-behaving nodes (miner relay networks, large players peering
>> directly with each other, ...)
>
> Yes, libbitcoin also provides these options on an IP basis.
>
>> * Several lightweight clients support configuring a trusted host to connect 
>> to.
>
> I explicitly exclude client-server behavior as I believe the proper 
> resolution is to isolate clients from the P2P protocol. Libbitcoin does this 
> already.

I think that's a false dichotomy. There is no reason why the P2P
network consists of purely servers (full nodes) and clients
(lightweight nodes). Where does a client fit that is SPV at startup,
but upgrades in the background to a full node? It seems strange that
such a client would use a 'client protocol' for initial connections,
but the P2P protocol for syncing with history, when both come from the
same peers, and transmit the same kind of information.

What would make sense IMHO is a protocol split between the different
kinds of transmission:
1) Historical block download
2) Block synchronization at the tip
3) Transaction relay
...

(1) prefers high bandwidth, has no connectivity concerns, and does not
care about latency and has no privacy concerns. (2) needs
partition-resistance, low latency and has also no privacy concerns.
(3) needs moderate latency, reliability of propagation and privacy.

If there were to be separate protocols for these, I would argue that
(3) should use opportunistic encryption always to increase transaction
source privacy, and (2) and (3) need authentication when one of the
peers is not fully validating.

BIP 150/151 give the tools to construct these.

>> Perhaps you deplore that fact, but I believe it is inevitable that different 
>> pieces of the network will make different choices here. You can't prevent 
>> people from create connections along preexisting trust lines. That does not 
>> mean that the network as a whole relies on first establishing trust 
>> everywhere.
>
> Of course, the network operates just fine without universal trust. My concern 
> is not that it is required, but that it may grow significantly and will have 
> a tendency to gravitate towards more effective registration mechanisms for 
> what is a "good" peer. Even an informal but pervasive web of trust may make 
> it difficult for untrusted parties to connect.

Maybe, but I'm very unconvinced that that will happen more than how
today IP and DNS-based "authentication" is used already (in very
inadvisable ways).

>> And I do think there are advantages.
>>
>> BIP 151 on its own gives you opportunistic encryption. You're very right to 
>> point out that this does not give you protection from active attackers, and 
>> that active attacking is relatively easy through sybil attacks. I still 
>> prefer my attacker to actually do that over just listening in on my 
>> connection.

> I agree, and I doubt this proposal will have much impact on an advanced 
> persistent threat, or even lesser threats. People should understand that 
> there is both a risk and a limited benefit to this proposal.

I believe the risk is only in misunderstanding what it is good for,
and there significant benefits to a network that encrypts connections
by default, as it excludes purely passive attackers.

> I believe you have misinterpreted my comments on distributed anonymous 
> credentials (and the like) as commentary on the construction of BIP151 (and a 
> subsequent auth proposal). As such your observation that it is exaggerated 
> would make sense, but it is not what I intended. Encryption and auth are 
> straightforward. Preventing bad nodes from participating in an anonymous 
> distributed system is not.

Preventing bad nodes from participating is a very hard problem, if not
impossible. That doesn't mean we can't improve the current situation:
people are relying on node identity already, and doing so in ways that
have unclear attack vectors (IP spoofing, DNS poisoning, BGP routing
attacks). Adding optional and non-discoverable cryptographic
identities can improve this.

-- 
Pieter
___
bitcoin-d

[bitcoin-dev] Start time for BIP141 (segwit)

[Pieter Wuille via bitcoin-dev]

Hello all,

We're getting ready for Bitcoin Core's 0.13.1 release - the first one
to include segregated witness (BIP 141, 143, 144, 145) for Bitcoin
mainnet, after being extensively tested on testnet and in other
software. Following the BIP9 recommendation [1] to set the versionbits
start time a month in the future and discussion in the last IRC
meeting [2], I propose we set BIP 141's start time to November 15,
2016, 0:00 UTC (unix time 1479168000).

Note that this is just a lower bound on the time when the versionbits
signalling can begin. Activation on the network requires:
(1) This date to pass
(2) A full retarget window of 2016 blocks with 95% signalling the
version bit (bit 1 for BIP141)
(3) A fallow period consisting of another 2016 blocks.

  [1] https://github.com/bitcoin/bips/blob/master/bip-0009.mediawiki
  [2] 
http://www.erisian.com.au/meetbot/bitcoin-core-dev/2016/bitcoin-core-dev.2016-10-13-19.04.log.html

Cheers,

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

Re: [bitcoin-dev] [BIP Proposal] Buried Deployments

[Pieter Wuille via bitcoin-dev]

On Wed, Nov 16, 2016 at 5:58 AM, Eric Voskuil via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> This sort of statement represents one consequence of the aforementioned
> bad precedent.
>
> Are checkpoints good now?
>

So far in this discussion, and in a thread that has forked off, I think 3
cases of implementation aspects have been mentioned that under certain
circumstances result in the validity of chains changing:
* Buried softforks (by simplifying the activation rules for certain rules)
* Not verifying BIP30 after BIP34 is active (since only under a SHA256^2
collision a duplicate txid can occur)
* The existence (and/or removal) of checkpoints (in one form or another).

None of these will influence the accepted main chain, however. If they ever
do, Bitcoin has far worse things to worry about (years-deep reorgs, or
SHA256 collisions).

If you were trying to point out that buried softforks are similar to
checkpoints in this regard, I agree. So are checkpoints good now? I believe
we should get rid of checkpoints because they seem to be misunderstood as a
security feature rather than as an optimization. I don't think buried
softforks have that problem.

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

Re: [bitcoin-dev] [BIP Proposal] Buried Deployments

[Pieter Wuille via bitcoin-dev]

On Wed, Nov 16, 2016 at 6:16 PM, Eric Voskuil  wrote:

> On 11/16/2016 05:50 PM, Pieter Wuille wrote:
>


> > So are checkpoints good now?
> > I believe we should get rid of checkpoints because they seem to be
> misunderstood as a security feature rather than as an optimization.
>
> Or maybe because they place control of the "true chain" in the hands of
> those selecting the checkpoints? It's not a great leap for the parties
> distributing the checkpoints to become the central authority.
>

Yes, they can be used to control the "true chain", and this has happened
with various forks. But developers inevitably have this possibility, if you
ignore review. If review is good enough to catch unintended consensus
changes, it is certainly enough to catch the introduction of an invalid
checkpoint. The risk you point out is real, but the way to deal with it is
good review and release practices.

I wish we had never used checkpoints the way we did, but here we are.
Because of this, I want to get rid of them. However, It's not because I
think they offer an excessive power to developers - but because they're
often perceived this way (partially as a result of how they've been abused
in other systems).


> I recommend users of our node validate the full chain without
> checkpoints and from that chain select their own checkpoints and place
> them into config. From that point forward they can apply the
> optimization. Checkpoints should never be hardcoded into the source.
>

Having users with the discipline you suggest would be wonderful to have. I
don't think it's very realistic, though, and I fear that the result would
be that everyone copies their config from one or a few websites "because
that's what everyone uses".

> I don't think buried softforks have that problem.
>
> I find "buried softfork" a curious name as you are using it. You seem to
> be implying that this type of change is itself a softfork as opposed to
> a hardfork that changes the activation of a softfork. It was my
> understanding that the term referred to the 3 softforks that were being
> "buried", or the proposal, but not the burial itself.
>

I do not consider the practice of "buried softforks" to be a fork at all.
It is a change that modifies the validity of a theoretically construable
chain from invalid to valid. However, a reorganization to that theoretical
chain itself is likely already impossible due to the vast number of blocks
to rewind, and economic damage that is far greater than chain divergence
itself.


> Nevertheless, this proposal shouldn't have "that problem" because it is
> clearly neither a security feature nor an optimization. That is the
> first issue that needs to be addressed.


It is clearly not a security feature, agreed. But how would you propose to
avoid the ISM checks for BIP34 and BIP66 all the time? I feel this approach
is a perfectly reasonable choice for code that likely won't ever affect the
valid chain again.

Cheers,

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

Re: [bitcoin-dev] Managing block size the same way we do difficulty (aka Block75)

[Pieter Wuille via bitcoin-dev]

On Sat, Dec 10, 2016 at 4:23 AM, Daniele Pinna via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> We have models for estimating the probability that a block is orphaned
> given average network bandwidth and block size.
>
> The question is, do we have objective measures of these two quantities?
> Couldn't we target an orphan_rate < max_rate?
>

Models can predict orphan rate given block size and network/hashrate
topology, but you can't control the topology (and things like FIBRE hide
the effect of block size on this as well). The result is that if you're
purely optimizing for minimal orphan rate, you can end up with a single
(conglomerate of) pools producing all the blocks. Such a setup has no
propagation delay at all, and as a result can always achieve 0 orphans.

Cheers,

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

Re: [bitcoin-dev] BIP151 protocol incompatibility

[Pieter Wuille via bitcoin-dev]

On Feb 12, 2017 23:58, "Eric Voskuil via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:

The BIP151 proposal states:

> This proposal is backward compatible. Non-supporting peers will ignore
the encinit messages.

This statement is incorrect. Sending content that existing nodes do not
expect is clearly an incompatibility. An implementation that ignores
invalid content leaves itself wide open to DOS attacks. The version
handshake must be complete before the protocol level can be determined.
While it may be desirable for this change to precede the version
handshake it cannot be described as backward compatible.


The worst possible effect of ignoring unknown messages is a waste of
downstream bandwidth. The same is already possible by being sent addr
messages.

Using the protocol level requires a strict linear progression of (allowed)
network protocol features, which I expect to become harder and harder to
maintain.

Using otherwise ignored messages for determining optional features is
elegant, simple and opens no new attack vectors. I think it's very much
preferable over continued increments of the protocol version.

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