[bitcoin-dev] Announcing B'SST: Bitcoin-like Script Symbolic Tracer

[Dmitry Petukhov via bitcoin-dev]

Hello list,

I have released B'SST: Bitcoin-like Script Symbolic Tracer

It can be found at https://github.com/dgpv/bsst

B'SST analyses Bitcoin and Elements scripts by symbolically executing
all possible execution paths, and tracking constraints that opcodes
impose on values they operate on. It then outputs a report based on
this analysis.

It can do analysis with the help of Z3 theorem prover [1]. With Z3
enabled, analysis will take more time, but all the features that depend
on SMT solver can be employed. By default, the analysis does not use
Z3, so it is fast, but not nearly as thorough.

Regarding the analysis performed, there are limitations and caveats.
Please refer to README.md in the repo at [0] for details.

I am aware of only one project that has aimed to do this type of
analysis before - the "SCRIPT Analyser" [2], but it had no updates in
its github repo for 5 years. Compared to [2], B'SST is more thorough in
its effort to match the reference interpreter closely, and it also uses
SMT solver, while [2] has used prolog for constraints solving.

Elements script interpreter [3], which is an extension of Bitcoin
script interpreter, was used as reference.

As an illustration of what information the analysis can provide, for
this rather contrieved example script:

7 ADD DUP 3 5 WITHIN
IF 0x00 ELSE 0 ENDIF
EQUALVERIFY 2DUP EQUALVERIFY SUB 0 EQUAL

The analysis report will show that:

- The first branch of IF will always fail
- Witness 0 must be -7 for script to succeed,
- Possible values for witness 1 and 2 are -1
- Result of last EQUAL is always true (because this condition was
  already checked by second EQUALVERIFY)

For more extensive example, please look at the report [5] for a rather
complex Elements script [4]

Plugins to implement custom opcodes are supported, please see "Custom
opcodes" section in README.md

B'SST is released under Prosperity Public License 3.0.0, which is a
"Free for non-commercial use" license, with a trial period for
commercial use and exemptions for educational institutions, public
research organizations, etc. Please refer to LICENSE.md file in the
repo at [0] for details.

[0] https://github.com/dgpv/bsst
[1] https://github.com/Z3Prover/z3
[2] https://github.com/RKlompUU/SCRIPTAnalyser
[3] 
https://github.com/ElementsProject/elements/blob/master/src/script/interpreter.cpp
[4] 
https://github.com/fuji-money/tapscripts/blob/with-annotations-for-bsst/beta/mint-mint.tapscript
[5] https://gist.github.com/dgpv/b57ecf4d9e3d0bfdcc2eb9147c9b9abf
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP Proposal: Receiving and Change Derivation Paths in a Single Descriptor

[Dmitry Petukhov via bitcoin-dev]

В Wed, 3 Aug 2022 20:16:52 -0500
Billy Tetrud  wrote:

> A descriptor format is simply defining a space of address
> derivation paths. It is not describing in any way what each path is
> intended for - those are conventions outside the scope of this BIP
> IMO. Defining the conventions of derivation path indexes should be a
> separate BIP. Single responsibility principle.

I see, you're right. I misread the BIP proposal text and missed that it
describes 'receive' and 'change' only as 'common usecase', not as
definitive designations for indexes. Considering this, I too see no need
to include such conventions in this BIP.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP Proposal: Receiving and Change Derivation Paths in a Single Descriptor

[Dmitry Petukhov via bitcoin-dev]

The issue with tuples of lenth more than two is that the purpose for
indexes beyond 'receive' and 'change' are not established, and
therefore various software might start to use extra indexes in a tuple
for their own non-standard purposes. This is bound to create
incompatibilities where different wallet software that import the same
descriptor would use those addresses for different purposes.

Even if some auxiliary standard emerges for the meanings of extra
indexes, since the indexes in the tuple are listed without omissions (no
"<0;1;;;3>" allowed), all software will need to be aware of the
existence of these purposes and define indexes for them: if one wishes
to utilize position 3 in such a tuple, they will need to define an index
for position 2 as well.

I'd expect that emergence of new widely-used purposes for indexes would
be a very rare event, and a separate BIP for each purpose wouldn't be
excessive.

I'd say that bip-multipath-descs should say that extra indexes are OK
for address discovery (for scanning of the addresses of a wallet), but
it should say that any interpretation of the purpose of such indexes
and deriving new addresses at these indexes are strongly discouraged.

Wallet software that wishes to utilize non-standard extra indexes beyond
'receive' and 'change' should use separate descriptors instead for
these extra indexes.

And when a new established purpose emerges for the next position in the
index tuple, a new BIP should be made that defines such position.

The BIP for position 3 would naturally come after the BIP for position
2, and thus software that implemnents BIP for position 3 would be aware
of the previous BIP and will at least know to choose some index for
position 2.

В Wed, 27 Jul 2022 14:58:28 +
Andrew Chow via bitcoin-dev 
wrote:

> I've updated the BIP text to allow arbitrary length tuples.
> 
> On 07/27/2022 04:44 AM, Pavol Rusnak wrote:
> 
> > On Wed, 27 Jul 2022 at 00:28, Andrew Chow
> >  wrote: 
> >> However I don't see why this couldn't generalize to any sized
> >> tuples. As long as the tuples are all the same length, and the
> >> limit is one tuple per key expression, then we don't get any
> >> combinatorial blowup issues.  
> >
> > I think it's worthwhile to generalize for any sized tuples. I don't
> > have any existing particular use case in mind, because BIP-44,
> > BIP-84, etc. are fine with just using <0;1>, but there might be
> > some upcoming standards in the future that will want to introduce
> > more sub-paths.
> >
> > --
> >
> > Best Regards / S pozdravom,
> >
> > Pavol "stick" Rusnak
> > Co-Founder, SatoshiLab  

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

Re: [bitcoin-dev] Proposal: Bitcoin Secure Multisig Setup

[Dmitry Petukhov via bitcoin-dev]

 > > >
> > > > HUMAN_READABLE_TITLE is in ASCII format, minimum length = 8,
> > > > maximum length = 20.
> > > > NONCE is a 64-bit number.
> > > >
> > > > Reason for going with SHA512 is due to legacy support on some
> > > > hardware. c=2048 also mimics BIP39. It takes about ~3 seconds to
> > > > derive the encryption key on a 80Mhz MCU. We feel like this is a
> > > > good enough tradeoff for this use case. The assumption here is
> > > > that the secure session is only needed temporarily for a few
> > > > hours, maybe up to one day.
> > > >
> > > > The Coordinator and Signers agree and exchange these 2 secrets
> > > > prior to the setup. The NONCE can be converted to either:
> > > > (a) a 6-word phrase using BIP39 wordlist
> > > > (b) a 20-digit decimal number
> > > > (c) a QR code
> > > >
> > > > Depending on the vendor. This flexibility in the data format
> > > > allows each vendor to customize the UX based on their respective
> > > > device capabilities.
> > > >
> > > > Best,
> > > > Hugo
> > > >
> > > > On Thu, Feb 11, 2021 at 8:25 AM Dmitry Petukhov via bitcoin-dev
> > > > < bitcoin-dev@lists.linuxfoundation.org> wrote:
> > > >
> > > > > В Thu, 11 Feb 2021 05:45:33 -0800
> > > > > Hugo Nguyen via bitcoin-dev
> > > > >  wrote:
> > > > >
> > > > > > > > ENCRYPTION_KEY = SHA256(SHA256(TOKEN))
> > > > > > >
> > > > > > > This scheme might be vulnerable to rainbow table attack.
> > > > > > >
> > > > > >
> > > > > > Thank you for pointing this out! Incidentally, Dmitry
> > > > > > Petukhov also told me the same privately.
> > > > >
> > > > > My thought was that if TOKEN has the characteristics of a
> > > > > password (short ASCII string), then it would be better to use
> > > > > key derivation function designed for passwords, like PBKDF2.
> > > > >
> > > > > The counter-argument to this is that this adds another code
> > > > > dependency for vendors, if the device firmware does not
> > > > > already have the required key derivation function.
> > > > >
> > > > > Maybe this could be solved by going into opposite direction -
> > > > > make the "token" even longer, use the mnemoic.
> > > > >
> > > > > The issue is that entering long data of the shared key into
> > > > > the device manually is difficult UX-wise.
> > > > >
> > > > > Hww vendors that allow to enter custom keys into their device
> > > > > already have to face this issue, and those who allow to enter
> > > > > custom keys via mnemonic probably tackled this somehow.
> > > > >
> > > > > Maybe the shared key for multisig setup can be entered in the
> > > > > same way ? (with maybe additional visual check via some
> > > > > fingerprint).
> > > > >
> > > > > Although we would then have another issue of potential
> > > > > confusion between two procedures (entering the main key and
> > > > > entering the shared key for multisig setup), and the measures
> > > > > has to be taken to prevent such confusion.
> > > > >
> > > > > The approaches can be combined - specify a key derivation
> > > > > function suitable for passwords; via secure channel, share a
> > > > > password and/or the derived key. If hww supports derivation
> > > > > function, it can derive the key from password. If hww supports
> > > > > only keys, the key can be entered raw or via mnemonic.
> > > > > ___
> > > > > 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] Proposal: Bitcoin Secure Multisig Setup

[Dmitry Petukhov via bitcoin-dev]

I think that it is better to issue individual TOKEN for each
participant. Otherwise it will be possible for one participant to
attack another (intercept and replace their xpub sent to the
coordinator).

It will also be convenient to have a public 'participant id', derived
from the token. It can be derived from the same token, but with
different (but fixed) `Pwd`. With unique token per participant, such
derivation will uniquely identify each participant, so the coordinator
won't need to try all the tokens to decrypt the data.

It will also be easier to deal with more elaborate setups where the
position of the xpub in the descriptor does matter - for example, with
miniscript-extended descriptors. With a descriptor template such as

`wsh(or(multi(2, , , ), older(1000, ))`

The coordinator will be able to store the map between the participant
labels (Alice, Bob, Carol, Dylan) and their participant ids (and the
TOKENs). When the data from Alice comes with participant id attached,
the coordinator will immediately know which TOKEN to use, and which
place in the descriptor the xpub should be put in.

Of course this is all possible without 'participant id' derived from
token, as long as there's unique TOKEN per participant - the coordinator
can always try all the tokens to decrypt the data from participant. But
implementors will likely invent their own ways to introduce
'participant id' anyway, as this is more convenient, and it might make
sense to have this standardized, for interoperability. 

В Fri, 12 Feb 2021 09:54:57 -0800
Hugo Nguyen  wrote:

> On Fri, Feb 12, 2021 at 9:36 AM Dmitry Petukhov 
> wrote:
> 
> > If HUMAN_READABLE_TITLE is the additional secret, the user would
> > need to enter it on the device in addition to the nonce, wouldn't
> > it defeat the advantage in UX that was gained by using (relatively)
> > short nonce ?
> >
> > Is 64 bit nonce not enough ?
> >
> >  
> Good question. If we don't need the extra entropy, we can fix
> the HUMAN_READABLE_TITLE string.
> 
> Something like "No SPOF". (No Single Point Of Failure).
> 
> 
> 
> > It seems that to crack this with fixed Pwd and 64 bit nonce, the
> > attacker will need to be about 10^15 more powerful than 80Mhz MCU:
> > (2^64)/(0.3*10^15)/3600 = 17 hours. I don't know if 10^15 is
> > realistic scale. Average desktop cpu seems to be about 10^3 more
> > powerful than the mentioned MCU for this task.
> >
> > Maybe for the UX it would be better to choose the number of rounds
> > to use in PBKDF2, instead of using variable Pwd. Number of rounds
> > will be easier to enter on the device (or just choose it from a set
> > of pre-defined values). The more money is at stake, the higher
> > number of rounds could the coordinator choose (taking into account
> > the characteristics of the participant devices)
> >  
> 
> > Or simply allow bigger entropy (more than 6 mnemonic words), if
> > the coordinator feels that 64 bit of entropy is not enough.  
> 
> 
> That could work. Allowing variable iteration count is probably better
> UX-wise.
> 
> Best,
> Hugo
> 
> 
> >
> > В Fri, 12 Feb 2021 08:55:55 -0800
> > Hugo Nguyen  wrote:
> >  
> > > Thanks everyone who has provided inputs so far!
> > >
> > > This is the new proposal for the encryption aspect of the scheme,
> > > based on all the feedback.
> > >
> > > The key derivation function would be PBKDF2, with PRF = SHA512.
> > > This should be readily available on today's hardware already, as
> > > they are used for BIP39.
> > >
> > > DK = PBKDF2(PRF, Password, Salt, c, dkLen)
> > > PRF = SHA512
> > > Pwd = HUMAN_READABLE_TITLE
> > > Salt = NONCE
> > > c = 2048
> > > dkLen = 256
> > >
> > > HUMAN_READABLE_TITLE is in ASCII format, minimum length = 8,
> > > maximum length = 20.
> > > NONCE is a 64-bit number.
> > >
> > > Reason for going with SHA512 is due to legacy support on some
> > > hardware. c=2048 also mimics BIP39. It takes about ~3 seconds to
> > > derive the encryption key on a 80Mhz MCU. We feel like this is a
> > > good enough tradeoff for this use case. The assumption here is
> > > that the secure session is only needed temporarily for a few
> > > hours, maybe up to one day.
> > >
> > > The Coordinator and Signers agree and exchange these 2 secrets
> > > prior to the setup. The NONCE can be converted to either:
> > > (a) a 6-word phrase using BIP39 wordlist
> > > (b) a 20-digit decimal number
> > > (c) a QR code
> > >
> > > Depending on the vendor. T

Re: [bitcoin-dev] Proposal: Bitcoin Secure Multisig Setup

[Dmitry Petukhov via bitcoin-dev]

If HUMAN_READABLE_TITLE is the additional secret, the user would need
to enter it on the device in addition to the nonce, wouldn't it defeat
the advantage in UX that was gained by using (relatively) short nonce ?

Is 64 bit nonce not enough ?

It seems that to crack this with fixed Pwd and 64 bit nonce, the
attacker will need to be about 10^15 more powerful than 80Mhz MCU:
(2^64)/(0.3*10^15)/3600 = 17 hours. I don't know if 10^15 is realistic
scale. Average desktop cpu seems to be about 10^3 more powerful than
the mentioned MCU for this task.

Maybe for the UX it would be better to choose the number of rounds to
use in PBKDF2, instead of using variable Pwd. Number of rounds will be
easier to enter on the device (or just choose it from a set of
pre-defined values). The more money is at stake, the higher number of
rounds could the coordinator choose (taking into account the
characteristics of the participant devices)

В Fri, 12 Feb 2021 08:55:55 -0800
Hugo Nguyen  wrote:

> Thanks everyone who has provided inputs so far!
> 
> This is the new proposal for the encryption aspect of the scheme,
> based on all the feedback.
> 
> The key derivation function would be PBKDF2, with PRF = SHA512. This
> should be readily available on today's hardware already, as they are
> used for BIP39.
> 
> DK = PBKDF2(PRF, Password, Salt, c, dkLen)
> PRF = SHA512
> Pwd = HUMAN_READABLE_TITLE
> Salt = NONCE
> c = 2048
> dkLen = 256
> 
> HUMAN_READABLE_TITLE is in ASCII format, minimum length = 8, maximum
> length = 20.
> NONCE is a 64-bit number.
> 
> Reason for going with SHA512 is due to legacy support on some
> hardware. c=2048 also mimics BIP39. It takes about ~3 seconds to
> derive the encryption key on a 80Mhz MCU. We feel like this is a good
> enough tradeoff for this use case. The assumption here is that the
> secure session is only needed temporarily for a few hours, maybe up
> to one day.
> 
> The Coordinator and Signers agree and exchange these 2 secrets prior
> to the setup. The NONCE can be converted to either:
> (a) a 6-word phrase using BIP39 wordlist
> (b) a 20-digit decimal number
> (c) a QR code
> 
> Depending on the vendor. This flexibility in the data format allows
> each vendor to customize the UX based on their respective device
> capabilities.
> 
> Best,
> Hugo
> 
> On Thu, Feb 11, 2021 at 8:25 AM Dmitry Petukhov via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> > В Thu, 11 Feb 2021 05:45:33 -0800
> > Hugo Nguyen via bitcoin-dev 
> > wrote:
> >  
> > > > > ENCRYPTION_KEY = SHA256(SHA256(TOKEN))  
> > > >
> > > > This scheme might be vulnerable to rainbow table attack.
> > > >  
> > >
> > > Thank you for pointing this out! Incidentally, Dmitry Petukhov
> > > also told me the same privately.  
> >
> > My thought was that if TOKEN has the characteristics of a password
> > (short ASCII string), then it would be better to use key derivation
> > function designed for passwords, like PBKDF2.
> >
> > The counter-argument to this is that this adds another code
> > dependency for vendors, if the device firmware does not already
> > have the required key derivation function.
> >
> > Maybe this could be solved by going into opposite direction - make
> > the "token" even longer, use the mnemoic.
> >
> > The issue is that entering long data of the shared key into the
> > device manually is difficult UX-wise.
> >
> > Hww vendors that allow to enter custom keys into their device
> > already have to face this issue, and those who allow to enter
> > custom keys via mnemonic probably tackled this somehow.
> >
> > Maybe the shared key for multisig setup can be entered in the same
> > way ? (with maybe additional visual check via some fingerprint).
> >
> > Although we would then have another issue of potential confusion
> > between two procedures (entering the main key and entering the
> > shared key for multisig setup), and the measures has to be taken to
> > prevent such confusion.
> >
> > The approaches can be combined - specify a key derivation function
> > suitable for passwords; via secure channel, share a password and/or
> > the derived key. If hww supports derivation function, it can derive
> > the key from password. If hww supports only keys, the key can be
> > entered raw or via mnemonic.
> > ___
> > 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] Proposal: Bitcoin Secure Multisig Setup

[Dmitry Petukhov via bitcoin-dev]

В Fri, 12 Feb 2021 18:42:31 +0100
Dmitry Petukhov  wrote:

> Maybe for the UX it would be better to choose the number of rounds to
> use in PBKDF2, instead of using variable Pwd. Number of rounds will be
> easier to enter on the device (or just choose it from a set of
> pre-defined values). The more money is at stake, the higher number of
> rounds could the coordinator choose (taking into account the
> characteristics of the participant devices)

Or simply allow bigger entropy (more than 6 mnemonic words), if
the coordinator feels that 64 bit of entropy is not enough.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Proposal: Bitcoin Secure Multisig Setup

[Dmitry Petukhov via bitcoin-dev]

В Thu, 11 Feb 2021 05:45:33 -0800
Hugo Nguyen via bitcoin-dev 
wrote:

> > > ENCRYPTION_KEY = SHA256(SHA256(TOKEN))  
> >
> > This scheme might be vulnerable to rainbow table attack.
> >  
> 
> Thank you for pointing this out! Incidentally, Dmitry Petukhov also
> told me the same privately.

My thought was that if TOKEN has the characteristics of a password
(short ASCII string), then it would be better to use key derivation
function designed for passwords, like PBKDF2.

The counter-argument to this is that this adds another code dependency
for vendors, if the device firmware does not already have the required
key derivation function.

Maybe this could be solved by going into opposite direction - make the
"token" even longer, use the mnemoic.

The issue is that entering long data of the shared key into the device
manually is difficult UX-wise.

Hww vendors that allow to enter custom keys into their device already
have to face this issue, and those who allow to enter custom keys via
mnemonic probably tackled this somehow.

Maybe the shared key for multisig setup can be entered in the same way
? (with maybe additional visual check via some fingerprint).

Although we would then have another issue of potential confusion
between two procedures (entering the main key and entering the shared
key for multisig setup), and the measures has to be taken to prevent
such confusion.

The approaches can be combined - specify a key derivation function
suitable for passwords; via secure channel, share a password and/or the
derived key. If hww supports derivation function, it can derive the key
from password. If hww supports only keys, the key can be entered raw or
via mnemonic.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Dmitry Petukhov via bitcoin-dev]

В Fri, 05 Feb 2021 17:51:27 +
Dr Maxim Orlovsky via bitcoin-dev
 wrote:

> Testnet path is unhardened from this point & till the end of the
> derivation path: no need to prevent private key leak there,
> simplifies test software (hardened paths require private key access
> for derivation).

I believe this will reduce robustness and will add complexity to the
test software instead. If the derivation path is hardened in 'production
code' and is unhardened in 'test code', then: code paths that depend on
hardened derivation may not be tested; there will be unnecessary
code that will need to deal with 'un-hardening' the paths for test code.

It is much more robust to just change the 'purpose' part of the path,
and leave the rest unchanged.

It is OK to require privkey access to hardened paths in test
software, because the same behaviour is expected in 'production'.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Formal specification of Miniscript in Alloy

[Dmitry Petukhov via bitcoin-dev]

В Wed, 25 Nov 2020 09:43:10 -0600
Clark Moody  wrote:

> Thanks for this! I can't comment on the correctness of your
> implementation, but I really appreciate the idea and effort.
> 
> By chance, did you come across any other spec definitions in alternate
> formal grammars?

As far as I know, this is the first formal spec for Miniscript.

I also considered using the K framework [1] for the task (it would
also give the parser out of the box), but at the time it did not have
the reference documentation, only tutorials on their site. It seems that
they have published the new site, with more documentation.

I am satisfied with how Alloy spec turned out, though - in my opinion,
the node definitions in the spec are very readable.

[1] https://kframework.org/


> On Wed, Nov 25, 2020 at 5:35 AM Dmitry Petukhov via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> > I have created a formal specification of Miniscript [1] using
> > the specification language of Alloy analyzer [2]
> >
> > Link: https://github.com/dgpv/miniscript-alloy-spec
> >
> > Possible uses for the spec:
> >
> > - Implementing Miniscript libraries, as additional reference that
> > might be easier to navigate than prose spec
> >
> > - Generating test cases for implementations, although currently this
> >   will be a manual process due to the tools limitation (can be
> > overcome with GUI automation)
> >
> > - Checking the implementation against the spec, by writing a program
> >   that would generate Alloy .als files from the data structures of
> > the implementation, and then checking these files in Alloy
> >
> > - Extending or amending Miniscript, if the need arise. Having
> >   extenstions and changes checked (with bounds) against a spec
> > should help catch inconsistencies
> >
> > - Exploring the properties of Miniscript
> >
> > If you have an interest in Miniscript, please consider looking at
> > the spec and share your ideas.
> >
> > The spec may contain mistakes, as it was not yet checked against any
> > implementation, it was only checked for consistency using its own
> > predicates, with the scope of up to 8 nodes.
> >
> > If you notice a mistake or inconsistency, please submit an issue on
> > github (or communicate this in other ways)
> >
> > [1] http://bitcoin.sipa.be/miniscript/
> > [2] https://alloytools.org/
> > ___
> > 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] Formal specification of Miniscript in Alloy

[Dmitry Petukhov via bitcoin-dev]

I have created a formal specification of Miniscript [1] using
the specification language of Alloy analyzer [2]

Link: https://github.com/dgpv/miniscript-alloy-spec

Possible uses for the spec:

- Implementing Miniscript libraries, as additional reference that might
  be easier to navigate than prose spec

- Generating test cases for implementations, although currently this
  will be a manual process due to the tools limitation (can be overcome
  with GUI automation)

- Checking the implementation against the spec, by writing a program
  that would generate Alloy .als files from the data structures of the
  implementation, and then checking these files in Alloy

- Extending or amending Miniscript, if the need arise. Having
  extenstions and changes checked (with bounds) against a spec should
  help catch inconsistencies

- Exploring the properties of Miniscript

If you have an interest in Miniscript, please consider looking at the
spec and share your ideas.

The spec may contain mistakes, as it was not yet checked against any
implementation, it was only checked for consistency using its own
predicates, with the scope of up to 8 nodes.

If you notice a mistake or inconsistency, please submit an issue on
github (or communicate this in other ways)

[1] http://bitcoin.sipa.be/miniscript/
[2] https://alloytools.org/
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP draft: BIP32 Path Templates

[Dmitry Petukhov via bitcoin-dev]

I have added a Python reference implementation of BIP32 path templates,
that is also compatible with micropython:

https://github.com/dgpv/bip32_template_python_implementation

The FSM formal spec has received a small corrections since the
announcement, and the reference implementations (C and this new python
implementation) are tested even more thoroughly now.

I submitted a PR to the bips repo:
https://github.com/bitcoin/bips/pull/1025, any comments welcome.


pgp7cddtKZGF0.pgp
Description: Цифровая подпись OpenPGP
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[Dmitry Petukhov via bitcoin-dev]

В Wed, 23 Sep 2020 15:10:22 -0700
Jeremy via bitcoin-dev  wrote:

> It's not particularly important that a transaction be in the same
> block once sponsored, it could also be in the last 100 blocks (the
> opposite of proposed change 3).

This will in effect enable "inverse timelock" mechanism for up to 100
blocks for sponsor transactions: broadcast a transaction A, and
then make a pre-signed sponsor transaction B that sponsors A.

Transaction B will become invalid after 100 blocks due to this rule.

If you put a timelock on B to make it valid after 50 blocks,
then it will be valid between block 50 and 100 after A is confirmed.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY

[Dmitry Petukhov via bitcoin-dev]

Just had an idea that an an "inverse timelock" can be made
almost-certainly automatic: a revocation UTXO shall become
anyone-can-spend after a timeout, and bear some non-dust amount.

Before the timelock expiration, it shall be spendable only along with
the covenant-locked 'main' UTXO (via a signature or mutual covenant)

This way, after a timeout expires, a multitude of entities will be
incentivized to spend this UTXO, because this would be free money for
them. It will probably be spend by a miner, as they can always replace
the spending transaction with their own and claim the amount.

After the revocation UTXO is spent, the covenant path that commits to
having it in the inputs will be unspendable, and this would effectively
constitute an "inverse timelock".

В Fri, 14 Feb 2020 11:16:26 -0800
Jeremy  wrote:

> Hi Dmitry,
> 
> I don't think that this is fundamentally introducing new behavior, but
> let's take a closer look.
> 
> We can talk about the issue you bring up purely in terms of a
> hypothetical "OP_CHECKINPUTOUTPOINTVERIFY" and
> "OP_CHECKINPUTSCRIPTVERIFY" (CIOV, CISV) with obvious implied by name
> semantics, as a separate construct from CTV itself. Such opcodes
> would be strictly more powerful/flexible than what CTV is enabling.
> 
> Using these opcodes I can make an output that can *only* be spent with
> another output -- e.g.,
> 
>   OP_CISV OP_DROP  OP_CHECKSIGVERIFY
>   OP_CIOV OP_DROP  OP_CHECKSIGVERIFY
> 
> Let's look at CISV first:
> 
> 1) Assume that  is from the same owner as PK
> 2) Assume that  is from a different owner than PK
> 
> In case 1, the wallet can create or recreate the appropriate output as
> needed if it gets spent/stuck
> 
> In case 2, the wallet can get "frozen" in a reorg until a signer on
>  re-spends.
> 
> 
> For CIOV:
> 
> 1) Assume that  exists in the chain somewhere
> 2) Assume that  exists in the mempool somewhere
> 3) Assume that  does not exist (or, is provably non-creatable
> -- h = txid(x) | x.IsValid() == false)
> 
> In case 2, this is just a fancy op-return.
> 
> Case 1 degrades into case 2 in the event of a reorg.
> 
> In Case 2, if the output  is spent in another transaction, our
> script becomes provably unspendable (unless a second reorg).
> 
> Otherwise, it is possible to mine a block with our transaction.
> 
> 
> Compare the above to normal transactions:
> 
> 1) If a reorg occurs, and someone double-spends, your transaction gets
> cancelled.
> 2) You can re-sign your UTXO onto a different transaction
> 
> However, if you have deleted your key (e.g. using a pre-signing HSM),
> or your transaction was using a multi-sig with an uncooperating
> party, you will have an output that may be effectively burned.
> 
> These issues are -- as with CTV -- not present in the single input
> use case.
> 
> Thus I argue that CTV -- whose semantics are less powerful/flexible
> than CISV/CIOV -- aren't introducing something that's not already
> present when doing protocols involving more than one input.
> 
> Further, on CTV "monotonic authorization":
> 
> Generally we want Bitcoin Scripts to have the property that once a
> condition is reached, it is 'permanently' a true case. E.g., showing
> a hash preimage to C x, H(x) == C. This can't change with the weather
> or anything else. Even things like timelocks -- although not obvious
> at first glance -- have this property. They express logic that says
> "given the chain is at this height, ...". This means that on any
> chain at such a height the txn is valid. CISV/CIOV semantics also
> fall in line with this description. It says, "given such an input U,
> ...". If that input is realizable one time, it is provably realizable
> across reorgs. However, that doesn't mean someone couldn't interrupt
> U from being created. But generally, with Reorg + Double spend, or
> Reorg > 100 blocks (potentially destroying CB reward), all bets are
> off as to the replay-ability of transactions.
> 
> I want to also point out that this "revocation" property -- to the
> extent it is something new that can't already be emulated with
> pre-signeds or RBF -- is entirely opt-in as far as CTV is concerned.
> You have to specify that an output can only be spent with another,
> most wallets shouldn't do that, and it can't "infect" other wallets
> to an extent more than spending from any recently confirmed output
> exposes you to more reorg risk.
> 
> *In sum, we do not need to worry about this for CTV.*
> 
> 
> Lastly, I want to note that revocation is part of what CTV is
> designed to do (absent reorgs). It allows us to prune spending
> conditions by playing a transaction forward.
> 
> E.g., spending conditions {Alice & Bob, Preimage(H(X)) + Eve,
> CTV({Alice & Bob}, 1 day)}
> 
> Expresses that Eve has 1 day to reveal the preimage to H(X), otherwise
> Alice and Bob can take the coin back by removing Eve's HTLC path.
> What's cool about this revocation v.s. just {Alice & Bob,
> Preimage(H(X)) + Eve} is that Alice and Bob don't need to coordinate

Re: [bitcoin-dev] BIP draft: BIP32 Path Templates

[Dmitry Petukhov via bitcoin-dev]

В Fri, 3 Jul 2020 21:53:44 +0500
Dmitry Petukhov via bitcoin-dev 
wrote:

> My hope is that having a clear specification and (possibly, in the
> future) permissibly licensed quality implementations would make
> adopting such format easier for vendors.

I have added a C implementation (MIT-licensed):
https://github.com/dgpv/bip32_template_c_implementation


pgpfozKsIww_E.pgp
Description: Цифровая подпись OpenPGP
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP draft: BIP32 Path Templates

[Dmitry Petukhov via bitcoin-dev]

В Fri, 3 Jul 2020 21:53:44 +0500
Dmitry Petukhov via bitcoin-dev 
wrote:

> The format for the path templates described in the presented BIP draft
> aims to provide a building block for interoperability between various
> hardware and software vendors in regard to this particular task of
> specifying derivation path restrictions.

One example of an interoperability workflow might be:

A software vendor that utilizes custom derivation paths in their
schemes create a "profile" that contains the constraints on the paths
(and possibly other parameters, but this is out of scope of the
proposal) for their particular scheme. In a simple case it might just
be a path template string provided in the documentation.

A user of a software solution from that vendor takes a hardware wallet
that supports path templates (or richer "profiles") and installs the
profile for that solution into hardware wallet. In a simple case, the
user just pastes a path template string into some configuration utility
program and then confirms the setting on-device.

The device statrts to enforce the constraints specified in the template
(or "profile"), and the software solution works as intended by the
software vendor.





pgp0EDjFTpNgy.pgp
Description: Цифровая подпись OpenPGP
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP draft: BIP32 Path Templates

[Dmitry Petukhov via bitcoin-dev]

IIUC, key origin identification specify chains of addresses, with
relation to specific keys. As the name suggests, they are for
identidication.

Path templates specify application-specific constraints for the
derivation paths. They are for imposing restrictions.

You could use path templates for identification, too, and in fact the
"path" part of the key origin identification would be a valid path
template. Path templates have potential to identify multiple chains
of addresses though, and I cannot say how useful it can be, if at all.

When a hardware wallet or some other type of autonomous signer signs a
transaction, there are two points where HD derivation can occur: 1) when
signing an input 2) when checking if the output is the change output

The second case is occurs more often, I think (determining actual
amount sent), but the first case can have uses, too -- when an
autonomous signer can impose restrictions on derivation path based on
the identity of the user that request the signing, for example. 

In both of these points an application-specific or usecase-specific
signing scheme might require that only certain whitelisted derivation
paths are used (sending change to the known key, but using derivation
path unknown to the sender allows an attacker to hold the change amount
for ransom, for example)

An autonomous signer might not be aware of the restrictions used in
particular scheme, because it might be developed by different vendor
than the implementor of the particular scheme. Or it might be difficult
to update the firmware of autonomous signer when the checks of the
path constraints are hard-coded in the program code. Having constraints
specified as data would allow to place them in configuration of the
signer.

One particular example of this being a problem is how hardware wallet
vendors seem to be inclined to decide to just restrict the derivation
paths allowed for the change addresses to the set of "well-known"
paths.

Such restrictions, on one hand, break custom schemes used by
various software solutions that rely on the ability of hardware wallet
to sign custom paths, and on the other hand, such hardcoded restrictions
might happen to be too relaxed, if the set of "well-known" path grows,
or the user or software vendor knows for sure that they won't use
addresses past index 1000, for example.

The format for the path templates described in the presented BIP draft
aims to provide a building block for interoperability between various
hardware and software vendors in regard to this particular task of
specifying derivation path restrictions.

Adopting a common format for specifying restictions is a flexible
alternative to everyone adopting a rigid set of "well-known" paths.
Such a set will inevitably grow, and those who really need custom
paths and do not have resources to push for standardization of their
custom paths will be at a disadvantage.

My hope is that having a clear specification and (possibly, in the
future) permissibly licensed quality implementations would make
adopting such format easier for vendors.

В Fri, 3 Jul 2020 10:39:45 -0400
"David A. Harding"  wrote:

> On Thu, Jul 02, 2020 at 09:28:39PM +0500, Dmitry Petukhov via
> bitcoin-dev wrote:
> > I think there should be standard format to describe constraints for
> > BIP32 paths.
> > 
> > I present a BIP draft that specifies "path templates" for BIP32
> > paths:
> > 
> > https://github.com/dgpv/bip32_template_parse_tplaplus_spec/blob/master/bip-path-templates.mediawiki
> >  
> 
> Hi Dmitry,
> 
> How do path templates compare to key origin identification[1] in
> output script descriptors?
> 
> Could you maybe give a specfic example of how path templates might be
> used?  Are they for backups?  Multisig wallet coordination?  Managing
> data between software transaction construction and hardware device
> signing?
> 
> Thanks,
> 
> -Dave
> 
> [1]
> https://github.com/bitcoin/bitcoin/blob/master/doc/descriptors.md#key-origin-identification
> (See earlier in the doc for examples)



pgpApkPHbWTwY.pgp
Description: Цифровая подпись OpenPGP
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[bitcoin-dev] BIP draft: BIP32 Path Templates

[Dmitry Petukhov via bitcoin-dev]

I think there should be standard format to describe constraints for
BIP32 paths.

I present a BIP draft that specifies "path templates" for BIP32 paths:

https://github.com/dgpv/bip32_template_parse_tplaplus_spec/blob/master/bip-path-templates.mediawiki

Matching against these templates allow to easily discern 'valid'
paths, that match the constraints, and 'invalid' paths, that exceed the
constraints. Extended motivation is given at the end of this message,
and in the text of the BIP draft.

A formal spec in TLA+ of a finite state machine implementing the parser
for the described format (and the matching operation) accompanies this
BIP draft: https://github.com/dgpv/bip32_template_parse_tplaplus_spec

This formal spec can be used with TLC model checker and a helper script
to generate thorough test data for implementations.

One (python) implementation of template parsing and matching already
exists (linked in the BIP draft).

Examples of the templates:

"m/[44,49,84]'/0'/0'/[0-1]/[0-5]" specifies a full template that
matches both external and internal chains of BIP44, BIP49 and BIP84
paths, with a constraint that the address index cannot be larger than
5

"[0-2,33,123]/*" specifies a partial template that matches non-hardened
values 0, 1, 2, 33, 123 as first index, and any non-hardened value at
second index

"*h/0" specifies a partial template that matches any hardened index
followed by any non-hardened index


Motivation:

BIP32 derivation path format is universal, and a number of schemes for
derivation were proposed in BIP43 and other documents, such as BIPs
44,45,49,84. The flexibility of the format allowed industry
participants to implement custom derivation shemes that fit particular
purposes, but not necessarily useful in general.

Unrestricted derivation path usage might be unsafe in certain contexts.
In particular, when "change" outputs of a transaction are sent to the
addresses derived via paths unknown to the sender, the sender might
loose access to the whole change amount.

A simplistic approach of hard-coding the checks for well-known paths
into software and firmware leads to reduced interoperability. Vendors
cannot choose custom paths that are appropriate for their particular,
non-general-purpose applications, and are forced to shoehorn their
solutions into using well-known paths, or convince other vendors to
support their custom paths. This approach scales poorly.

A flexible approach proposed is to define a standard notation for
"BIP32 path templates" that succintly describes the constraints to
impose on the derivation path.

Wide support for these path templates will increase interoperability
and flexibility of solutions, and will allow vendors and individual
developers to easily define their own custom restrictions. This way,
they will be able to deal with the risks of accidental or malicious use
of unrestricted derivation paths in a more flexible and precise manner.

Well-known path templates can be pre-configured by default on devices
and applications, but users can have an option to turn off the
templates that are not relevant to their uses.

Having standardized format for custom path templates will enable a
common approach to be developed to the enforcement of
application-specific path restrictions in devices and applications. One
example of such approach might be for devices to allow to install
application-specific profiles with path templates and possibly other
custom parameters. Care must be taken to prevent accidental
installation of malicious or incorrect profile, though. 
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] [was BIP OP_CHECKTEMPLATEVERIFY] Fee Bumping Operation

[Dmitry Petukhov via bitcoin-dev]

В Sun, 7 Jun 2020 23:43:39 -0700
Jeremy via bitcoin-dev  wrote:

> > PFN transaction would still be valid if some of 'ghost parents' are
> >  
> already confirmed, so the miners could have more fees than strictly
> necessary. But this is the same as with CPFP.
> 
> This is problematic and can't be done as it requires a new index of
> all past txns for consensus.

If the logic would match CPFP, then PFN would be valid if some of the
'ghost parents' are confirmed, but would be invalid if some of them are
spent. I believe in this case txindex won't be required.

> My thinking is that a Fee Bump transaction can name a list of TXIDs
> (Or one TXID which implies all ancestors of) that it wishes to be
> included in a block with. It must be included in that block. A Fee
> Bump transaction may have no unconfirmed ancestors nor any children.
> Potentially, it also may not be RBF'd. You treat the Fee Bump
> Transactions as the lowest descendant of whatever it targets and then
> set it's feerate/total fee based on the package that would have to
> co-confirm for it to be worth mining. This makes it sort like normal
> transactions for inclusion. You can require some minimums for mempool
> inclusion at all.
> 
> If it's target is confirmed or replaced, it should drop from the
> mempool.

Re "may not be RBF'd": What if the sender of PFN tx wants to increase
the fee it offers for the 'ghost parents'? RBF-ing PFN tx itself seems
like less wasteful way than RBF-ing some of the parents/'ghost parents'
just for this purpose. Sometimes I think the sender of PFN will not be
even able to replace any other transactions beside their own PFN tx
(like when they offer 'fee bumping' service for others)
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY

[Dmitry Petukhov via bitcoin-dev]

В Sun, 7 Jun 2020 15:45:16 -0700
Jeremy via bitcoin-dev  wrote:

> What I think we'll eventually land on is a way of doing a tx
> that contributes fee to another tx chain as a passive observer to
> them. While this breaks one abstraction around how dependencies
> between transactions are processed, it also could help resolve some
> really difficult challenges we face with application-DoS (pinning and
> other attacks) in the mempool beyond CTV. I have a napkin design for
> how this could work, but nothing quite ready to share yet.

I had an idea of 'Pay for neighbor' transaction where a transaction
that is not directly a child of some other transaction can specify that
it wants to pay the fee for that other transaction(s). It can become
like 'ghost child' transaction for them, in what it cannot be mined
unless its 'ghost parents' are confirmed, too. It will be like CPFP,
but without direct dependency via inputs. Such 'PFN' transaction would
not spend any coins beside what it specifies in its own inputs, of
course.

The idea required a hardfork at first, but Anthony Towns suggested
a way to make it into a soft fork (past-taproot) by putting the txids of
'ghost parents' into taproot annex.

PFN transaction would still be valid if some of 'ghost parents' are
already confirmed, so the miners could have more fees than strictly
necessary. But this is the same as with CPFP.

Looking at the mempool code, it seems that only a way how parent/child
transactions relationships are established will need to be adjusted to
account for this 'ghost relationships', and once established, other
logic will work as with CPFP. There could be complications regarding
transaction package size. But I cannot claim that I understand that
code enough to say something about this with certainty.

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

Re: [bitcoin-dev] SAS: Succinct Atomic Swap

[Dmitry Petukhov via bitcoin-dev]

I made a version of the TLA+ spec according to the suggested variant,
as I understood it from your description. This version is in
the separate branch in the SASwap repo, 'variant_ZmnSCPxj' [1]

If I understood and specified your variant correctly, there is a
deadlock possible after step 9, if Bob fails to publish success tx in
time. After refund tx becomes spendable, Alice cannot publish it via
mempool, because Bob can learn her secret and has a chance invalidate
her refund tx by giving his success tx to friendly miner, while taking
back the locked LTC because both secrets are known. At the same time,
Bob cannot publish success tx via mempool, because then Alice can do
the same thing, invalidating his success tx with refund tx via friednly
miner.

There is a possibility that this deadlock can be resolved if one
participant indeed has possibility to confirm their tx directly,
bypassing the mempool, so the counterparty won't learn the secret until
transaction is in the block. But then this just raises the cost of the
attack because the counterparty will need to invalidate (orphan) the
whole block instead of just a transaction in the mempool, after
learning the other secret from the recent block.

[1] https://github.com/dgpv/SASwap_TLAplus_spec/tree/variant_ZmnSCPxj

В Tue, 12 May 2020 04:41:43 +
ZmnSCPxj via bitcoin-dev  wrote:

> Good morning Ruben,
> 
> > Hi ZmnSCPxj,
> >
> > Thanks for your feedback :)
> >  
> > > CoinSwap for privacy is practically a "cross" chain atomic swap
> > > with the same chain and token for both sides of the swap  
> >
> > I agree, I didn't mean to imply that was new, only that this
> > protocol makes it more efficient.
> >  
> 
> Indeed; basically, any innovations in cross-chain swaps can be
> adapted to a CoinSwap (though not necessarily vice-versa, if a
> CoinSwap innovation requires certain specific blockchain features).
> 
> > > "Instead, Bob simply hands secretBob to Alice" is basically the
> > > same as private key turnover  
> >
> > Thanks for the link. I will add it to the links at the bottom of the
> > write-up, as I agree it's related. Do note there are a few key
> > differences:
> >
> > -   The swap is set up in an "asymmetric" way with only timelocks
> > on one side, so on the other side the swap never expires
> >  
> 
> An interesting setup.
> 
> So I was wondering why something like this would not work instead:
> 
> 0.  Alice has BTC, Bob has LTC, they agree on exchange rates and two
> future timelock L1 and L2 such that L1 < L2. 1.  Alice creates
> keypairs Alice[0] Alice[1] Alice[2], Bob creates Bob[0] Bob[1]
> Bob[2], and share the pubkeys. 2.  Alice creates, but does not sign,
> a funding tx on BTC whose output requires Alice[0] && Bob[0]. 3.  Bob
> creates a backout transaction spending the BTC funding txo, with an
> absolute timelock L1, whose output goes to Alice[2], then provides to
> Alice a signature for Bob[0] and requires an adaptor such that
> completing the signature with Alice[0] reveals Alice[1].
> 
>  nLockTime L1
> BTC funding txo ---> Alice[0] && Bob[0]--->  Alice[2]
>  reveals Alice[1]
> 
> 4.  Alice creates a timeout transaction spending the BTC funding txo,
> with an absolute timelock L2, whose output goes to Bob[2], then
> provides to Bob a signature for Alice[0] and requires an adaptor such
> that completing the signature with Bob[0] reveals Bob[1].
> 
>  nLockTime L2
> BTC funding txo ---> Alice[0] && Bob[0]--->  Bob[2]
>  reveals Bob[1]
> 
> 5.  Alice signs the BTC funding tx and broadcasts it.
> 6.  Alice and Bob wait for the BTC funding tx to be confirmed.
> 7.  Bob creates an LTC funding tx whose output requires Alice[1] &&
> Bob[1]. 8.  Alice and Bob wait for the LTC funding tx to be confirmed.
> 9.  Alice creates a success transaction spending the BTC funding txo,
> with no practical absolute timelock (current blockheight + 1), whose
> output goes to Bob[2], then provides to Bob a signature for Alice[0]
> and requires an adaptor such that completing the signature with
> Bob[0] reveals Bob[1].
> 
>  nLockTime now
> BTC funding txo ---> Alice[0] && Bob[0]--->  Bob[2]
>  reveals Bob[1]
> 
> 10.  Bob gives the secret key of Bob[1] to Alice.
> 11.  Alice gives the secret key of Alice[0] to Bob.
> 12.  Bob claims the BTC funding txo before L1.
> 
> Aborts and stalls:
> 
> * Aborts before step 5 are safe: no money is ever committed yet.
>   Stalls before step 5 can be promoted to aborts.
> * If aborted between step 5 and step 8, Alice reclaims her BTC via
> the backout transaction. Since Bob did not confirm any locked funds
> in LTC, revealing Alice[1] does not give Bob any extra funds it did
> not already have. If Bob stalls before step 8 Alice can abort at L1
> using the backout transaction.
> * If Alice stalls at step 9, Bob can force the completion using 

Re: [bitcoin-dev] TLA+ specification for Succint Atomic Swap

[Dmitry Petukhov via bitcoin-dev]

I've finished specifying the full Succint Atomic Swap contract in TLA+.

I believe the specification [1] now covers all relevant behaviors of
the participants. It even has an option to enable 'non-rational'
behavior, so that it can be shown that the transactions that are there
to punish bad behavior can actually be used. If you examine the spec
and find that I failed to specify some relevant behavior, please tell.

The specification can be used to exhaustively check safety properties
of the model (such as no participant can take both coins, unless in
explicitly specified circumstances), and temporal properties (such as
contract always end up in an explicitly specified 'finished' state).

The specification can also be used to *show* (but not automatically
check at the moment) the hyperproperties of the model, such as what
transactions can ever be confirmed in at least one the execution path,
max/min/avg values for various stats, etc. The information on these
hyperproperties can be printed out during model checking, and can be
examined manually or with help of additional scripts (if one willing to
write some).

The model has some limitations, like only having one miner, and not
modelling fees and mempool priorities. More than one miner needed to
introduce reorgs in the model, but I believe that reorgs are relevant
only if we cannot say that "one block in the model means 6 bitcoin
blocks" (or whatever reorg safety limit is acceptable). I also believe
that the fees and mempool priorities are a lower-level concern, because
the task to confirm the transaction in time is the same for different
stages of the contract and for different transactions, and therefore
this can be modelled separately.

The goal of creating this specification was to evaluate the suitability
of TLA+ for modelling of the smart contracts in UTXO-based
blockchain systems. I believe that the presented spec shows that it is
indeed feasible to do such modelling and TLA+ is a suitable tool for
specifying and for checking such specifications (Although having ability
to automatically check hyperproperties using TLA+ expressions would be
nice).

I hope that this spec can be used as a basis for specs for other
contracts, and that using TLA+ can make designing safe contracts for
UTXO-based systems easier. I also hope that this will help to increase
interest in using formal methods in this area.

I tried to make the parts of the spec that deal with things like mining
and mempool to not depend on the concrete contract logic, in
expectation that this logic can be reused afterwards for the specs of
other contracts. I did not make specific effort to factor out this
generic logic into separate module though, because I think that more
various contract specifications need to be designed and analyzed to
understand what is really generic and what should lay with concrete
contract logic. When more knowledge is created regarding this, there
could be a module that contract specifications can use to avoid
explicitly specifying the generic blockchain-related logic.

Thanks to Ruben Somsen for designing this contract and
providing helpful description and diagram that made it possible to
create this formal specification.

[1] https://github.com/dgpv/SASwap_TLAplus_spec
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] TLA+ specification for Succint Atomic Swap

[Dmitry Petukhov via bitcoin-dev]

В Thu, 14 May 2020 07:31:13 +0200
Ruben Somsen  wrote:

> Hi Dmitry,
> 
> >While refund_tx_1 is in the mempool, Bob gives success_tx to the
> >friendly miner
> 
> I see, so you're talking about prior to protocol completion, right
> after Alice sends Bob the success_tx. The reason this is not an issue
> is because Alice and Bob both had to misbehave in order for this to
> happen. Bob is misbehaving here because he should have published the
> success_tx before refund_tx_1 became valid, and Alice is misbehaving
> here because she should have sent the revoke_tx (which invalidates
> the success_tx) followed by refund_tx_2 (revealing her secret only
> AFTER Bob can no longer claim the BTC). In other words: yes, the
> protocol can fail if Alice and Bob together work towards that goal. A
> feature, not a bug. This won't happen if either of them doesn't want
> it to. I imagine this is difficult to model.

Right. But it should be noted that it is not enough that Bob publishes
success_tx before refund_tx_1 became valid. The success_tx needs to be
confirmed before refund_tx_1 became valid.

Only Bob can spend success_tx so this is unlikely to be the practical
problem, unless the original fee of success_tx is too small and Bob
epically screws up CPFP-ing it.

> >Bob will receive BTC, and the LTC can be locked forever, but Bob
> >doesn't  
> care, he got his BTC.
> 
> No, because diagram step 5 comes before step 6 -- Alice won't give
> her key until she learns secretBob.

I somehow missed it, and steps 5 and 6 in the diagram was not modelled
at all (on the other hand, it made the model simpler and I had
something working relatively quick). I now made the `signers_map` into
variable that can be changed to give Bob the ability to sign for Alice.

With that change, step 6 can be modelled, but this will add a bunch of
new txs to the model (each Alice spend will have 'Bob unilateral
override' case)
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] TLA+ specification for Succint Atomic Swap

[Dmitry Petukhov via bitcoin-dev]

В Wed, 13 May 2020 21:03:17 +0200
Ruben Somsen  wrote:

> Or perhaps you're referring to the issue ZmnSCPxj pointed out after
> that, where refund transaction #1 and the success transaction could
> both become valid at the same time. It would make sense for the test
> to pick up on that, but I believe that is ultimately also not an
> issue (see my last reply in the thread).

This one.

The issue as I see it: Bob can not broadcast success_tx and wait until
Alice has broadcasted refund_tx_1. While refund_tx_1 is in the mempool,
Bob gives success_tx to the friendly miner to have a chance to
invalidate success_tx. Bob already learned secretAlice, so he grabs
his LTC back. If the Bob-friendly miner has luck, success_tx is
confirmed while refund_tx_1 is invalidated, and Bob now have both LTC
and BTC, while Alice is out of her BTC.

> >I did not understand what the destination of Alice cooperative
> >spend  
> of refund_tx#1 will be
> 
> This transaction can be spent by Alice & Bob right away or by Alice a
> day later (in relative time, so the tx has to confirm first). The
> Alice & Bob condition is there purely to ensure that Bob can spend
> the money before Alice once he receives her key at the end of the
> protocol.

Ah, so this is possible because of the step 5 in the diagram: ``Alice
gives Bob her key ("Alice")'' -- As I understand, this is a way to deny
Alice to use refund_tx_1.

Then if Alice gives her _key_ to Bob before Bob has to share secretBob
via success_tx, could Bob just spend the Alice output of the
very first, "commitment" transaction that locks BTC ? Bob will receive
BTC, and the LTC can be locked forever, but Bob doesn't care, he got
his BTC.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[bitcoin-dev] TLA+ specification for Succint Atomic Swap

[Dmitry Petukhov via bitcoin-dev]

The Succint Atomic Swap contract presented by Ruben Somsen recently has
drawn much interest.

I personally am interested in the smart contracts realizeable in the
UTXO model, and also interested in applying formal methods to the
design and implementation of such contracts.

I think that having formal specifications for the contracts and to be
able to machine-check the properties of these specifications is very
valuable, as it can uncover the corner cases that might be difficult to
uncover otherwise.

The SAS contract is complex enough that it may benefit from formal
specification and machine checking.

I created a specification in TLA+ [1] specification language based on
the explanation and the diagram given by Ruben.

The checking of the model encoded in the specification can successfully
detect the violation of 'no mutual secret knowledge' invariant when one
of the participant can bypass mempool and give the transaction directly
to the miner (this problem was pointed out by ZmnSCPxj in the original
SAS thread [2])

There's one transition that was unclear how to model, though: I did not
understand what the destination of Alice cooperative spend of
refund_tx#1 will be, so this transition is not modelled.

I believe there can be more invariants and temporal properties of the
model that can be checked. At the moment the temporal properties
checking does not work, as I didn't master TLA+ enough yet. The safety
invariants checking should work fine, though, but more work needed to
devise and add the invariants.

In the future, it would be great to have an established framework for
modelling of the behavior in Bitcoin-like blockchain networks.
In particular, having a model of mempool-related behavior would help to
reason about difficult RBF/CPFP issues. The specification I present
models the mempool, but in a simple way, without regards to the fees.

The specification can be found in this github repository:
https://github.com/dgpv/SASwap_TLAplus_spec

There could be mistakes or omissions in the specified model, I hope
that public review can help find these.

It would be great to receive comments, suggestions and corrections,
especially from people experienced in formal methods and TLA+, as this
is only my second finished TLA+ spec and only my third project using
formal methods (I created bitcoin transaction deserialization code in
Ada/SPARK before that [3]). Please use the github issues or off-list
mail to discuss if the matter is not interesting to the general
bitcoin-dev list audience.

[1] https://lamport.azurewebsites.net/tla/tla.html

[2]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-May/017846.html

[3] https://github.com/dgpv/spark-bitcoin-transaction-example
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY

[Dmitry Petukhov via bitcoin-dev]

I decided to take this thread back on-list because I beleive that the
'revocation utxo' feature enabled by OP_CTV commiting to scriptSig may
have wider implications that can slightly change the behavior of Bitcoin
as a system, and some might not expect such changes or might not find
them desireable (although there is already a case for such behaviour
with RBF).

There is a principle that some find valuable: "During reorgs of depth
less than 100, it is always possible to eventually replay transactions
from the old branch into the new branch as long as no double spends are
attempted" (quoted from Russel O'Connor from the discussion about
'revocation utxo' on Elements Slack channel).

As far as I can tell, this principle can be violated with the use of
RBF: "(tx) that was included in branch A and then RBF-ed (tx') in branch
B and then branch A wins -> children of (tx') can't be replayed"

Some may hold an opinion that introducing new rules that violate that
principle should be done with caution.

The 'revocation utxo' feature enabled by OP_CTV essentially introduces
a manually triggered 'inverse timelock' -  normal timelocks make tx
invalid until certain point in time, and inverse timelock make tx
invalid _after_ certain point in time, in this case by spending an
unrelated UTXO.

In a reorg, one branch can have that UTXO spent before the OP_CTV
transaction that depends on it is included in the block, and the OP_CTV
transaction and its children can't be replayed.

This is the same issue as an 'automatic inverse timelock' that could
be enforced by the structure of the transaction itself, if there was
appropriate mechanism, with the difference that 'revocation utxo' is
manually triggered.

The absense of 'automatic inverse timelock' mechanism in Bitcoin hints
that it was not seen as desireable historically. I was not able to find
the relevant discussions, though.

I would like to add that the behaviour enabled by inverse timelocks
could be useable in various schemes with covenants, like the vaults
with access revocable by spending the 'revocation utxo', or in the
trustless lending schemes where the covenant scripts can enforce
different amounts of interest paid to lender based on the point in time
when the loan is returned - the obsolete script paths (with smaller
interest paid) can be disabled by inverse timelock.

В Fri, 13 Dec 2019 23:37:19 -0800
Jeremy  wrote:

> That's a cool use case. I've thought previously about an
> OP_CHECKINPUT, as a separate extension. Will need to think about if
> your construction introduces a hash cycle (unless
> SIGHASH_ALL|SIGHASH_ANYONECANPAY is used it seems likely).
> 
> Also re signatures I think it's definitely possible to pick a
> (signature, message) pair and generate a pk from it, but in general
> the Bitcoin message commits to the pk so forging isn't possible.
> 
> On Fri, Dec 13, 2019, 11:25 PM Dmitry Petukhov 
> wrote:
> 
> > Another idea for smart vaults:
> >
> > The ability to commit to scriptSig of a non-segwit input could be
> > used for on-chain control of spending authorization (revoking the
> > spending authorization), where CTV ensures that certain input is
> > present in the transaction.
> >
> > scriptSig of that input can contain a signature that commits to
> > certain prevout. Unless it is possible to forge an identical
> > signature (and I don't know how strong are guarantees of that),
> > such an input can only be valid if that prevout was not spent.
> >
> > Thus spending such prevout makes it impossible to spend the input
> > with CTV that commits to such scriptSig, in effect revoking an
> > ability to spend this input via CTV path, and alternate spending
> > paths should be used (like, another taproot branch)
> >
> >
> > В Fri, 13 Dec 2019 15:06:59 -0800
> > Jeremy via bitcoin-dev 
> > пишет: 
> > > I've prepared a draft of the changes noted above (some small
> > > additional modifications on the StandardTemplateHash described in
> > > the BIP), but have not yet updated the main branches for the BIP
> > > to leave time for any further feedback.
> > >
> > > See below:
> > >
> > > BIP:
> > > https://github.com/JeremyRubin/bips/blob/ctv-v2/bip-ctv.mediawiki
> > > Implementation:
> > > https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-v2
> > >
> > > Thank you for your feedback,
> > >
> > > Jeremy
> > > --
> > > @JeremyRubin 
> > >   
> >
> >  

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

Re: [bitcoin-dev] PSBT Addition (BIP 174) for authenticating source/output PSBT files

[Dmitry Petukhov via bitcoin-dev]

I am not sure that this particular task should be done with data
embedded in PSBT itself, and not with some sort of container that
includes PSBT and the authentication information.

The benefit seems to be in reusing PSBT structure for compatibilty, and
this might be a valid way, although I do not agree with some of your
points. I elaborate below:

> 1) In the PSBT globals section, a signature over the "source" PSBT
> file. It would cover all the bytes of the original PSBT file, as
> it was received by the Signer.

The problem of authenticating the contents of PSBT is independent of
the signing action. PSBT might be altered on the path from Creator to
Signer. Therefore you cannot always say that Signer will be an
authority over 'correctness' of PSBT.

> - At the end of the signing process, the Finalizer should check all
> the Signers have worked from the same PSBT file (assuming that's
> the flow expected)

If there is MitM, checking something at Finalizer is likely too
late - the party that can intercept PSBTs can finalize before the
legitimate Finalizer and broadcast the transaction.

Participants can work from the same PSBT file if they all receive the
same PSBT, and not working in chain where next particpant receives
updated PSBT from the previous participant. Otherwise they will need to
either pass two files (original and updated), or work out which fields
(key-value blobs) to remove to get the 'source' PSBT (which might not be
trivial with presense of proprietary and unknown fields). Even if you
know which key-value pairs to remove, there is no requirement for
ordering of the fields, and some signer can serialize them in different
order after dserialize/sign/add-signatures/re-serialize operation.

Introducing additional ordering or other structure requirements over
simple key-value structure will add complexity to PSBT processing, and
adding complexity on such a basic level should have really serious
reasons, because that increases effort required for even basic
implementations and increases chance of bugs.

If there is some authority on the 'correctness' of 'original' PSBT
(all particpants receive same PSBT at the start), particpants should
check the signature by that authority. That authority might use
the key used only for authentication, and not in the tx signing.

If particpants send PSBT in chain after adding their signatures, then
each participant can add their signature to say 'the contents
of PSBT after my updates should match this hash'.

The signatures of previous participants in the chain most likely do not
matter because of difficulty of restoring the contents of PSBT as it
was before the previous particpant, if you do not pass _all_ the PSBTs
(which is excessive). 
 
> 2) In the output section, specifically, the last key/value pair of
> the last output of the transaction, I want to add a similar signature,
> again signed by one of the keys used in the signing process. This
> signature will cover all the bytes of the resulting (signed) PSBT
> up to that point. Because it is the last output of the output
> section, that signature will be the last few bytes of the PSBT file.
> By "appending" the signature in this way, it's easier to validate
> and create the signature, without blanking the signature area during
> digest step.

This will introduce unnecessary higher-level structure to PSBT for the
reasons that I do not find strong enough for the amount of complexity
added.

Also, as I said above, you likely do not need more than one
signature - if this is 'fan-out' scheme, then participants need do
check the sig of authority that created PSBT; if this is piggy-back
chain, then only previous particpant's signature is easily verifiable.

> ## Next Steps
> 
> I'd like to get two officially-assigned BIP-174 key numbers assigned
> for these two signatures, and then I will see that it gets added
> into Coldcard's firmware immediately. In time, other tools are
> welcome to take advantage of these checks. I will also write a BIP
> for this, and/or make an addition to BIP-174.

I think you do not need to wait for officially-assigned key numbers,
and can just implement the scheme you envision with proprietary keys,
document and promote it. Then if it shows its usefulness, it will
either become de-facto standard with your proprietary keys (and
everyone will want to support 'Coldard PSBT auth' or whatever the name),
or the scheme will have serious grounds to be converted to standard and
have non-proprietary keys assigned.

// Dmitry.


pgpJQNtMxYpnT.pgp
Description: Цифровая подпись OpenPGP
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

[Dmitry Petukhov via bitcoin-dev]

В Wed, 7 Aug 2019 20:10:17 +0500
Dmitry Petukhov via bitcoin-dev 
wrote:

> In shared ownership rent scheme that ZmnSCPxj described in [1],
> the 'TXO rentier' has a signed timelocked 'backout' transaction that
> spends the locked TXO, and assigns the reward to rentier.
> 
> If we say that any transaction that spends any TXO in the bond
> (ignoring the timelock), invalidates the bond when presented to
> takers, then TXO rentier can revoke the bond by simply
> publishing this transaction (not to the blockchain, but by some other
> means so that takers can receive it).
> 
> The transaction validity can be verified, with the relaxed rules that
> ignores the timelock. After it is verified, takers mark the whole
> bond as revoked and will not consider it when chosing makers.

The backout transaction might not be timelocked itself, but can depend
on another timelocked transaction (made specifically to avoid the
backout transaction be timelocked). That extra transaction will need to
be broadcast before the backout transaction.

To account for that possibility, takers would need to either use more
relaxed verification rules (do not check if the inputs of the 'snitch
transaction' exist), or would need to check the whole package of
dependent transactions in which the last one spends the bond. 
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

[Dmitry Petukhov via bitcoin-dev]

В Thu, 08 Aug 2019 09:35:24 +
ZmnSCPxj  wrote:

>  OP_CHECKSIGVERIFY
>  OP_CHECKSIG

This anti-snitch protection won't work if there are two snitches, which
is concievable in the case of a large-scale consolidated bonds (one
entity can pretend to be two independent entities with two different
TXO). The snitch co-conspirator will refuse to sign the punishment
transaction.

If you change the MuSig(all_except_snitch) to 1-of-n multisig
construction so that anyone other than the actual 'snitch' can
confiscate the snitch-bond, then there's possibility that that a
co-conspirator can get that bond before others - even before
the sntich transaction is distributed to takers.

It seems that to reasonably protect from more than one snitch with this
punishment scheme, you want to make a multitude of taproot leaves where
each leaf can be spent by cooperation of N entities, where N is the
size of expected non-snitch participant set.

> Finally, aggregation is still possible to insure by off-blockchain
> agreements, possibly with legal consequences, and thus entities like
> exchanges might still be able to aggregate funds and acquire an
> undeservedly large weight in the fidelity bond system.

This seems to me like the most immediate problem for the discussed
system.

Since the centralized exchanges or other custodial services already
control TXOs of their customers who sent their funds there, they can
use them to make extra profit with joinmarket, and create fidelity
bonds out of these TXO with (or without) consent of the customers, and
pay them (or not) the amount according to their UTXO, while getting the
consolidation benefit of V^2 for themselves. It is also more probable
that such centralized custodial services would be willing to
participate in a deanonymization efforts, so that they can explain
their participation in coinjoins to regulators.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

[Dmitry Petukhov via bitcoin-dev]

Unfortunately, both described schemes fail the same way as
'require TXOs to be consolidated by the owner', by the fact that with
muSig, shared ownership of TXO is possible, as explained by ZmnSCPxj in
[1]. 2P-ECDSA is also possible, just more complex, so just saying 'ban
musig for the bonds' is not the answer, I believe.

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

В Wed, 7 Aug 2019 01:55:41 +0500
Dmitry Petukhov  wrote:

> В Mon, 5 Aug 2019 20:04:26 +0100
> Chris Belcher  wrote:
> 
> > So what's needed is a way to make renting out TXOs impossible or
> > very difficult.  
> 
> You can make renting the TXOs risky for the attacker. Make it so that
> the entity that rented out the TXO can revoke the participation of
> said TXO in the market, by publishing some special signature. That
> act of revocation can also mean revocation of all other TXOs that
> were used in a bond alongside it. This way, any entity that wants to
> spoil an attacker's consolidation via rent, can rent out its TXO to
> the attacker, and then revoke it, spoiling the whole package the
> attacker have consolidated.
> 
> There may be other way to impose penalties.
> 
> For example, all locked TXO may be required to be spendable by *any*
> key that controls any TXO in the 'bond TXO package'. I think this
> should be possible with taproot - you will have to publish a taproot
> trees for your locked TXOs (say, N of them), and the tree for each TXO
> will have N leaves, each leaf will specify a condition "spendable by
> the key N". This way, if I give you my TXO to include it in a bond by
> locking it, you also need to make your other TXOs in a bond spendable
> by me.
> 
> For both scenarios to work for the attacker, there's need to be an
> off-chain contractual relationship between the parties. Otherwise the
> entity that rents out the TXOs can spoil or just confiscate the bond
> of the entity that rented them, without reprecussions.

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

Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

[Dmitry Petukhov via bitcoin-dev]

В Mon, 5 Aug 2019 20:04:26 +0100
Chris Belcher  wrote:

> So what's needed is a way to make renting out TXOs impossible or very
> difficult.

You can make renting the TXOs risky for the attacker. Make it so that
the entity that rented out the TXO can revoke the participation of said
TXO in the market, by publishing some special signature. That act of
revocation can also mean revocation of all other TXOs that were used in
a bond alongside it. This way, any entity that wants to spoil an
attacker's consolidation via rent, can rent out its TXO to the
attacker, and then revoke it, spoiling the whole package the attacker
have consolidated.

There may be other way to impose penalties.

For example, all locked TXO may be required to be spendable by *any*
key that controls any TXO in the 'bond TXO package'. I think this
should be possible with taproot - you will have to publish a taproot
trees for your locked TXOs (say, N of them), and the tree for each TXO
will have N leaves, each leaf will specify a condition "spendable by
the key N". This way, if I give you my TXO to include it in a bond by
locking it, you also need to make your other TXOs in a bond spendable
by me.

For both scenarios to work for the attacker, there's need to be an
off-chain contractual relationship between the parties. Otherwise the
entity that rents out the TXOs can spoil or just confiscate the bond of
the entity that rented them, without reprecussions.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Proposed Extensions to BIP 174 for Future Extensibility

[Dmitry Petukhov via bitcoin-dev]

В Thu, 01 Aug 2019 19:01:06 +
Andrew Chow  wrote:

> I spoke to some people OOB and they said that they didn't really like
> the idea of having a prefix string (partially because they've already
> implemented some proprietary types by simply squatting on unused
> types). Matching the prefix string adds additional complexity to the
> parser code.

I do not oppose the idea of "{0xFC}|{private_type}" strongly, but I
would like to note that for those who do not want to deal with
additional complexity of handling a prefixed string, they can simply
not use it at all. Since this is a private construction, and their
private format specifies 'no prefix', they can just ignore everything
that does not start with "{0xFC}|{0x00}", thus any further complexity
regarding the prefix is also ignored. The only added complexity is one
condition check: second_byte_of_the_key != 0 

My other argument for conflict-avoidance prefix as a first thing after
0xFC is that the set of future users of PSBT and private types is
most likely much larger than the current set of those who already
implemented proprietary types on their own, and thus the overall benefit
for the whole industry will likely be bigger when 'i do not want
conflict avoidance' decision have to be explicit, by setting the prefix
to 0x00, and the set of possible conflicting types are limited only to
those entities that made this explicit decision.

Regarding the 'squatted' types, it seems to me that this only matters
in the discussed context if they squatted on 0xFC type in particular.
In other cases, they will need to implement changes anyway, to be
compatible with the BIP. Maybe they could consider that one additional
condition check is a small burden, and maybe they can tolerate that,
for the benefit of reducing possibility of interoperability problems
between other future PSBT/private types implementors.

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

Re: [bitcoin-dev] Proposed Extensions to BIP 174 for Future Extensibility

[Dmitry Petukhov via bitcoin-dev]

В Wed, 31 Jul 2019 01:13:46 +
Andrew Chow via bitcoin-dev 
wrote:

> Firstly, I would like to propose that some types be reserved for
> proprietary use. These proprietary use types are, in general, for
> private use by individuals and organizations who want to use PSBT in
> their processes. These are usefule when there are additional data that
> they need attached to a PSBT but such data are not useful (or
> available) for the general public.

I think private formats should have at least a basic format: they
should start with a prefix. This way different prviate formats can be
distinguished by this prefix, and there will be no risk of
unintentional confusion.

Private types can start with the size of the prefix, and then
organization can choose any prefix they like, or no prefix, if
the size is of the prefix is 0 (means they are fine with possible
conflicts with other empty-prefix private types)

> Lastly, I would like to propose the canonical method for mult-byte
> types. We designate a specific type to indicate that the type is
> multiple bytes. When such types are observed, parsers should move onto
> the next byte and interpret that as the type, keeping in mind the
> number of bytes that were read in for the type.
> 
> I propose that we use 0xFF as this designated type. When a parser sees
> an 0xFF value as the type, it reads the next byte as being part of the
> type. So two byte types will be of the form 0xFFXX. This method allows
> us to do a prefix match in order to quickly identify the type being
> used. For types with more bytes, simply use another 0xFF byte. So
> three byte types would be of the form 0xXX, four byte,
> 0xFFXX, and so on. When multi-byte types are specified in the
> BIP, they should be specified in this full length form, i.e. two byte
> types as 0xFFXX.

Why not just say that the types should be encoded as 'compact size
unsigned integer' ? This format for variable length integer encoding is
already used in the BIP for other fields, and thus will not add any
additional complexity to the parsing.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

[Dmitry Petukhov via bitcoin-dev]

В Tue, 30 Jul 2019 22:39:14 +0100
Chris Belcher via bitcoin-dev 
wrote:

> This is where a sacrifice of V bitcoins creates a
> bond of value V^2. The formula provides a strong incentive for
> profit-motivated makers to use all their fidelity bond coins with just
> one maker, not spread them out over many makers.

The attacker derives additional value from the use of
locked utxo - the deanonimyzation capabilities.

An entity M can use all of its locked coins to run a maker, and then
earn value X. It will also incur some operational expenses in the course
of running the maker, so the profit will be less than X.

If these locked coins are given to the attacker A as a package, an
attacker can derive a value of X+D where D is a value of increased
deanonymization capabilities for an attacker. Operational expenses
for an attacker are the same as before (without timelocked bonds),
because they need to operate a lot of makers either way.

If M is profit-driven and non-ideological, it can rent out all of its
coins to A as a package, for the price X, and get the same value without
running a maker and dedicating any resources and time to it, not
incurring any operatinal expenses (thus having a bigger profit in the
end).

Attacker A will run a maker with M's coins, get profit X, pay X to M,
get increased deanonymization capabilities. 

If renting out of utxo is done in a way that the owner always gets X
after the lock expires, the operation will be riskless for the owner.
The attacker will need to lock amount X along with owner's coins, but
hopefully makes X back by running a maker operation. 

The price for renting out the coins will be determined on the size of
the 'coin package', so it will not be feasible for the owners of the
coins to rent them out separately.

An attacker can even rent coins from several entities and combine them
to create a more 'powerful' maker. If I understand correctly, such
'powerful' maker can have bigger profit than two less 'powerful'
makers. It seems like a centralization risk to me.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Improving JoinMarket's resistance to sybil attacks using fidelity bonds

[Dmitry Petukhov via bitcoin-dev]

В Fri, 26 Jul 2019 10:10:15 +0200
Tamas Blummer via bitcoin-dev 
wrote:

> Imposing opportunity costs however requires larger time locked
> amounts than burning and the user might not have sufficient funds to
> do so. This is however not a restriction but an opportunity that can
> give rise to an additional market of locking UTXOs in exchange of a
> payment.
> 
> This would give rise to a transparent interest rate market for
> Bitcoin an additional huge benefit.

Wouldn't that 'locked utxo rent' market just drive the cost of attack
down to manageable levels for the attacker ?

The owner of the locked utxo can derive potential profit from it by
being a maker, and then the profit will be reduced by operational
expenses of running a maker operation.

The owner of utxo can just 'outsource' that task to someone, and pay
some fee for the convenience.

In effect, the owner would be renting out that utxo for the price of

 -  - 

If the attacker is the entity who provides this 'maker outsourcing',
and it captures significant portion of that maker-outsourcing/utxo-rent
market, it can even receive some profit from the convenience fee, while
deanonymizing the joins.

And with pseudonymous entities, you cannot be sure how much of that
market the attacker controls.


pgpqFGuSZ85N_.pgp
Description: Цифровая подпись OpenPGP
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] OP_SECURETHEBAG (supersedes OP_CHECKOUTPUTSVERIFY)

[Dmitry Petukhov via bitcoin-dev]

If you make ANYPREVOUTANYSCRIPT signature not the only signature that
controls this UTXO, but use it solely for restricting the spending
conditions such as the set of outputs, and require another signature
that would commit to the whole transaction, you can eliminate
malleability, for the price of additional signature, of course.

  CHECKSIG  CHECKSIG

(CHECKMULTISIG/CHECKSIGADD might be used instead)

where control-P can even be a pubkey of a key that is publicly known,
and the whole purpose of control-sig would be to restrict the outputs
(control-sig would be created with flags meaning ANYPREVOUTANYSCRIPT).
Because control-sig does not depend on the script and on the current
input, there should be no circular dependency, and it can be part of
the redeem script.

P would be the pubkey of the actual key that is needed to spend this
UTXO, and the signature of P can commit to all the inputs and outputs,
preventing malleability.

I would like to add that it may make sense to just have 2 additional
flags for sighash: NOPREVOUT and NOSCRIPT.

NOPREVOUT would mean that previous output is not committed to, and when
combined with ANYONECANPAY, this will mean ANYPREVOUT/NOINPUT:
ANYONECANPAY means exclude all inputs except the current, and NOPREVOUT
means exclude the current input. Thus NOPREVOUT|ANYONECANPAY = NOINPUT

With NOPREVOUT|ANYONECANPAY|NOSCRIPT you would have ANYPREVOUTANYSCRIPT

with NOPREVOUT|NOSCRIPT you can commit to "all the inputs beside the
current one", which would allow to create a spending restriction like
"this UTXO, and also one (or more) other UTXO", which might be useful
to retroactively revoke or transfer the rights to spend certain UTXO
without actually moving it:

think 'vault' UTXO that is controlled by Alice, but requires additional
'control' UTXO to spend. Alice have keys for both 'vault' UTXO, and
'control' UTXO, but Bob have only key for 'control' UTXO.

If Bob learnsthat Alice's vault UTXO key is at risk of compromize,
he spends the control UTXO, and then Alice's ability to spend vault
UTXO vanishes.

You can use this mechanism to transfer this right to spend if you
prepare a number of taproot branches with different pairs of (vault,
control) keys and a chain of transactions that each spend the previous
control UTXO such that the newly created UTXO becomes controlled by the
control key of the next pair, together with vault key in that pair.

В Sat, 22 Jun 2019 23:43:22 -0700
Jeremy via bitcoin-dev  wrote:

> This is insufficient: sequences must be committed to because they
> affect TXID. As with scriptsigs (witness data fine to ignore). NUM_IN
> too.
> 
> Any malleability makes this much less useful.
> --
> @JeremyRubin 
> 
> 
> 
> On Fri, Jun 21, 2019 at 10:31 AM Anthony Towns via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> > On Tue, Jun 18, 2019 at 04:57:34PM -0400, Russell O'Connor wrote:  
> > > So with regards to OP_SECURETHEBAG, I am also "not really seeing
> > > any  
> > reason to  
> > > complicate the spec to ensure the digest is precommitted as part
> > > of the opcode."  
> >
> > Also, I think you can simulate OP_SECURETHEBAG with an ANYPREVOUT
> > (NOINPUT) sighash (Johnson Lau's mentioned this before, but not
> > sure if it's been spelled out anywhere); ie instead of constructing
> >
> >   X = Hash_BagHash( version, locktime, [outputs], [sequences],
> > num_in )
> >
> > and having the script be " OP_SECURETHEBAG" you calculate an
> > ANYPREVOUT sighash for SIGHASH_ANYPREVOUTANYSCRIPT | SIGHASH_ALL:
> >
> >   Y = Hash_TapSighash( 0, 0xc1, version, locktime, [outputs], 0,
> >amount, sequence)
> >
> > and calculate a signature sig = Schnorr(P,m) for some pubkey P, and
> > make your script be "  CHECKSIG".
> >
> > That loses the ability to commit to the number of inputs or restrict
> > the nsequence of other inputs, and requires a bigger script (sig
> > and P are ~96 bytes instead of X's 32 bytes), but is otherwise
> > pretty much the same as far as I can tell. Both scripts are
> > automatically satisfied when revealed (with the correct set of
> > outputs), and don't need any additional witness data.
> >
> > If you wanted to construct "X" via script instead of hardcoding a
> > value because it got you generalised covenants or whatever; I think
> > you could get the same effect with CAT,LEFT, and RIGHT: you'd
> > construct Y in much the same way you construct X, but you'd then
> > need to turn that into a signature. You could do so by using pubkey
> > P=G and nonce R=G, which means you need to calculate
> > s=1+hash(G,G,Y)*1 -- calculating the hash part is easy, multiplying
> > it by 1 is easy, and to add 1 you can probably do something along
> > the lines of:
> >
> > OP_DUP 4 OP_RIGHT 1 OP_ADD OP_SWAP 28 OP_LEFT OP_SWAP OP_CAT
> >
> > (ie, take the last 4 bytes, increment it using 4-byte arithmetic,
> > then cat the first 28 bytes and the result. There's 

Re: [bitcoin-dev] BIP174 extension proposal (Global Type: PSBT_GLOBAL_XPUB_SIGNATURE)

[Dmitry Petukhov via bitcoin-dev]

В Sat, 29 Jun 2019 09:19:41 +0900
Jonathan Underwood  wrote:

> > Other note: you have 'unused' value of 1 for `m` in your scheme, why
> > not require m=1 for single-sig case, and use 0 as indicator that
> > there are a serlal number following it?
> >  
> 
> 0x00 is single sig, aka, OP_CHECKSIG
> 
> 0x01 is multisig, aka, 1-of-3, 1-of-2 OP_CHECKMULTISIG

This informatin is available in per-output redeem/witness script,
signer will be able to distinguish between multisig/single-sig by
looking at this script. I think it only need to know the total number
of keys participating in the signing, and check that this number
matches the particulars of redeem/witness script.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP174 extension proposal (Global Type: PSBT_GLOBAL_XPUB_SIGNATURE)

[Dmitry Petukhov via bitcoin-dev]

В Sat, 29 Jun 2019 09:19:41 +0900
Jonathan Underwood  wrote:

> Though outside the scope of this BIP, one difficulty of a whitelist
> feature would be revocation of signatures. If we pre-sign a
> revocation cert and somehow make the wallet blacklist if seen... then
> the question is "if your signer has a trustworthy store of state, why
> not store the whitelist pubkeys?"

In principle, if the hardware wallet can permanently store at least one
counter, it can have rich state, stored externally. It would sign a
state stored in RAM, and give out the state + signature to the
supporting app. The state will include a serial number, corresponding to
the internal counter stored in the hardware wallet. Next time, the app
will give the signed state to the hardware wallet along with
transaction data. Hardware wallet checks its signature over the state,
checks that serial matches its internal counter, uses and modifies the
state, then updates the internal counter and the serial number of the
state, and gives out the signed new state to the app. If the app
loses the state blob, though, there should be some mechanism to securely
override the hw wallet internal state.

This approach might have other limitations, as processing and storing
big enough state in the RAM of a resource-constrained device might
present a problem in itself.

The 'add serial to xpub-package' idea is in the same vein: you can
store this xpub-package serial inside the hw wallet directly, or inside
its 'external rich state blob', but it can take only one byte (unlikely
to need more than 255 xpub-package 'revocations', at that point you
are probably OK to change your cold keys already)
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP174 extension proposal (Global Type: PSBT_GLOBAL_XPUB_SIGNATURE)

[Dmitry Petukhov via bitcoin-dev]

In your proposed field key format,

{0x02}|{signing_pubkey}|{m}|{xpub}|...|{xpub}

I think you can replace the signing pubkey with just a fingerprint of
the master key, that would save 29 bytes per 0x02 field.

If the only entity that is concerned about the validity of the
signature is those that possess the signing_privkey, it will check the
signature when it sees the 0x02 field starting with its own key
fingerprint, and will ignore the field if the signature does not match.

If someone other than the signer needs to check that this xpub-package
was signed by certain cold key, it will need to know signing_pubkey
anyway, before it parses PSBT, as it won't have the means to check if
certain pubkey found in 0x02 field in PSBT is related to certain
signer, without knowing anything about the pubkey beforehand.

I'm not sure if the ability of unrelated parties to verify that
xpub-package matches its signature is useful in practice. 29 bytes per
0x02 field is not a big saving of space, and if this ability is actually
useful, the saving may not be worh loosing this ability.

Other note: you have 'unused' value of 1 for `m` in your scheme, why
not require m=1 for single-sig case, and use 0 as indicator that there
are a serlal number following it?

The key for the field would be encoded as

{0x02}|{signing_pubkey}|{m}|{xpub}|...|{xpub}

for usual case, and

{0x02}|{signing_pubkey}|0x00|{serial}|{m}|{xpub}|...|{xpub}

for the case when the signing scheme actually cares about different
versions of xpub packages signed by certain cold key

Going back to the idea of moving 'complex' usecases outside of BIP174:
maybe we could have a 'BIP-specific' field, that would have the key as

{0x0?}|{BIP-number}|{bip-specific-suffix-data}

so that the different usecases that are not general enough to be
included in BIP174 itself, may have their own BIPs. Vendor-specific
fields may also be done as a separate BIP.

В Thu, 27 Jun 2019 20:29:32 +0500
Dmitry Petukhov  wrote:

> Oh, I saw that you covered it in another mail:
> 
> > The expire / revoke problem is a larger problem than this feature
> > can handle.  
> 
> > In general, if one of the cold keys is stolen, there is rarely a
> > situation where you are completely sure the other cold keys haven't
> > been compromised... so the best practice would be all signers
> > generate new keys and all funds are moved to a completely new
> > multisig wallet (no common xpubs).  
> 
> The setup might not be 'all cold keys', but the keys with different
> levels of exposure to possible theft. In this config, compromise of
> one of the 'warm' keys might not necessary require changing the
> 'cold' key.
> 
> I'm not sure whether this usecase warrants adding extra 'serial'
> field, but on the other hand it is rather simple change, and those who
> does not care can always set 0. 
> 
> В Thu, 27 Jun 2019 18:14:29 +0500
> Dmitry Petukhov  wrote:
> 
> > What do you think about adding serial number to the xpub package ?
> > 
> > The key would be 
> > 
> > {0x02}|{signing_pubkey}|{serial}|{m}|{xpub}|...|{xpub}
> > 
> > and if the signer have the ability to store a counter, it can reject
> > 'outdated' xpub packages, and only accept those that was signed
> > using the serial number that it deems recent. This would allow a
> > limited mechanism to 'revoke' previously signed packages that have
> > compromized keys in them.
> > 
> > В Thu, 27 Jun 2019 17:16:14 +0900
> > Jonathan Underwood  wrote:
> >   
> > > I see what you mean.
> > > 
> > > What about this?
> > > https://github.com/junderw/bips/commit/57a57b4fae1ae14b77a2eebd99cd719148e3027e?short_path=82656c8#diff-82656c833e31e6751a412ce5e5c70920
> > > 
> > > Plus side: for single sig case, the key only increases by one byte
> > > (0x00 for the {m} value)
> > > 
> > > This way if it was 2 of 3 like before, you sign the whole "packet"
> > > so each key only signs the packet once. Way better than n!
> > > 
> > > Anywho. Please send your feedback. Thanks.
> > > Jonathan
> > > 
> > > 2019年6月27日(木) 16:27 Dmitry Petukhov :
> > > 
> > > > How would signer know that there _should_ be at least 3
> > > > signatures signed by the key owned by this signer ?
> > > >
> > > > If it does not know that it should enforce 2of3 multisig, for
> > > > example, the attacker that control only one key A can fool
> > > > signer B by sending to 1of1 single-sig that is derived from A's
> > > > xpub, and providing only sBxA in PSBT.
> > > >
> > > > If the signer does not have a hardcoded configuration that
> > > > will mandate a particular multisig scheme, it will allow sending
> > > > to any scheme.
> > > >
> > > > If the signer has a rich enough state to store updatable
> > > > configuration, it can just store the trusted xpubs directly.
> > > >
> > > > Alternatively, signer can sign not individual xpubs, but whole
> > > > xpub packages that correspond to particular multisig
> > > > configuration, and enforce that destination addresses correspond
> > > > to this 

Re: [bitcoin-dev] BIP174 extension proposal (Global Type: PSBT_GLOBAL_XPUB_SIGNATURE)

[Dmitry Petukhov via bitcoin-dev]

Oh, I saw that you covered it in another mail:

> The expire / revoke problem is a larger problem than this feature can
> handle.

> In general, if one of the cold keys is stolen, there is rarely a
> situation where you are completely sure the other cold keys haven't
> been compromised... so the best practice would be all signers
> generate new keys and all funds are moved to a completely new
> multisig wallet (no common xpubs).

The setup might not be 'all cold keys', but the keys with different
levels of exposure to possible theft. In this config, compromise of one
of the 'warm' keys might not necessary require changing the 'cold' key.

I'm not sure whether this usecase warrants adding extra 'serial'
field, but on the other hand it is rather simple change, and those who
does not care can always set 0. 

В Thu, 27 Jun 2019 18:14:29 +0500
Dmitry Petukhov  wrote:

> What do you think about adding serial number to the xpub package ?
> 
> The key would be 
> 
> {0x02}|{signing_pubkey}|{serial}|{m}|{xpub}|...|{xpub}
> 
> and if the signer have the ability to store a counter, it can reject
> 'outdated' xpub packages, and only accept those that was signed using
> the serial number that it deems recent. This would allow a limited
> mechanism to 'revoke' previously signed packages that have compromized
> keys in them.
> 
> В Thu, 27 Jun 2019 17:16:14 +0900
> Jonathan Underwood  wrote:
> 
> > I see what you mean.
> > 
> > What about this?
> > https://github.com/junderw/bips/commit/57a57b4fae1ae14b77a2eebd99cd719148e3027e?short_path=82656c8#diff-82656c833e31e6751a412ce5e5c70920
> > 
> > Plus side: for single sig case, the key only increases by one byte
> > (0x00 for the {m} value)
> > 
> > This way if it was 2 of 3 like before, you sign the whole "packet"
> > so each key only signs the packet once. Way better than n!
> > 
> > Anywho. Please send your feedback. Thanks.
> > Jonathan
> > 
> > 2019年6月27日(木) 16:27 Dmitry Petukhov :
> >   
> > > How would signer know that there _should_ be at least 3 signatures
> > > signed by the key owned by this signer ?
> > >
> > > If it does not know that it should enforce 2of3 multisig, for
> > > example, the attacker that control only one key A can fool signer
> > > B by sending to 1of1 single-sig that is derived from A's xpub, and
> > > providing only sBxA in PSBT.
> > >
> > > If the signer does not have a hardcoded configuration that
> > > will mandate a particular multisig scheme, it will allow sending
> > > to any scheme.
> > >
> > > If the signer has a rich enough state to store updatable
> > > configuration, it can just store the trusted xpubs directly.
> > >
> > > Alternatively, signer can sign not individual xpubs, but whole
> > > xpub packages that correspond to particular multisig
> > > configuration, and enforce that destination addresses correspond
> > > to this configuration.
> > >
> > > But this would not be possible with your PSBT scheme that uses
> > > individual key-xpub pairs.
> > >
> > > В Thu, 27 Jun 2019 14:07:47 +0900
> > > Jonathan Underwood  wrote:
> > >
> > > > Thanks for the reply.
> > > >
> > > > The way we would do it is:
> > > >
> > > > Let's say we have 3 cold keys for multisig: A B and C
> > > >
> > > > Whose xpubs are: xA xB and xC
> > > >
> > > > We all sign each other's xpubs, whose signatures are:
> > > > sAxB
> > > > sAxC
> > > > sBxA
> > > > sBxC
> > > > sCxA
> > > > sCxB
> > > >
> > > > We can then create a wallet that says "when verifying change
> > > > with 0x01 global type proposed by Andrew Chow, if the change is
> > > > multisig, we MUST require the other pubkeys to have signatures
> > > > via my 0x02 proposal"
> > > >
> > > > This way, all my PSBTs for my cold will have:
> > > > 1. an 0x01 entry to tell me how to get my change.
> > > > 2. All 6 of the signatures above.
> > > >
> > > > And the signer will then look at the change, check my pubkey by
> > > > deriving the xpub and checking equality to the BIP_DERIVATION of
> > > > the output... it will then check the OTHER pubkeys via
> > > > BIP32_DERIVATION to master fingerprint, then link that
> > > > fingerprint to a 0x02 sig from MY key, verifying all pubkeys.
> > > >
> > > > So this proposal of mine would not only fix the "send to address
> > > > verification" problem for HD, but also the multisig change
> > > > problem with 0x01.
> > > >
> > > > Cool.
> > > >
> > > > Only thing that is kind of sad is having to include n! (of
> > > > m-of-n) signatures in every PSBT... but tbh, the PSBT size is
> > > > not of much concern.
> > > >
> > > > Thanks for the reply.
> > > > - Jonathan
> > > >
> > > >
> > > > 2019年6月27日(木) 13:49 Dmitry Petukhov :
> > > >
> > > > > Hi!
> > > > >
> > > > > I wonder how your scheme handles multisig ?
> > > > >
> > > > > As I understand, you sign individual xpubs with cold keys, so
> > > > > that cold keys can check destination addresses are trusted.
> > > > >
> > > > > I seems to me that if you sign individual xpubs of a multisig
> > > > > warm wallet, 

Re: [bitcoin-dev] Adding xpub field to PSBT to make multisig more secure

[Dmitry Petukhov via bitcoin-dev]

> Therefore, the input==output check is sufficient: if I use the same
> set of signers for an input and an output, I can be sure that the
> change goes to the same multisig wallet.

This is sufficient, in a simple case.

I consider cases where spending from different wallets ('wallet
compartments') can be aggregated into one transaction, for efficiency
and convenience in certain circumstances. (ex: legacy addresses that
cannot be abandoned due to users still sending to them, but managing
them separately is inconvenient; wallet 'compartments' that each have
different multisig policies and spending priorities, and change would
go to most secure compartment used, etc.)

This is most likely a 'borader problem', as you said, but this is just
what my code already does, although with stateful signers that
store trusted xpubs. I had an idea how to apply this to stateless hw
wallets, and shared it.

> > This would allow to distinguish the trusted output even if the
> > inputs are not all derived from the same set of xpubs, that could
> > happen in more complex scenarios (batching, key rotation, etc.),
> > and can possibly be used to have several different types of
> > 'trusted' outputs.
> 
> This seems to be an attempt at a different, much broader problem. And
> it won't help if the attacker can replay a different trusted-xpub
> package (e.g., one that contains a revoked previously compromised
> key).

The auxiliary text can be constructed to include some code word that
would mark 'epoch' of the package, and will be displayed prominently.
Upon compromise, new trusted-xpub packages would use different 'epoch'
code word. This is one method to make it stateless (stateful way would
be to just have a counter inside hw wallet and check package version
against it).
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Adding xpub field to PSBT to make multisig more secure

[Dmitry Petukhov via bitcoin-dev]

> > Even with this additions to the PSBT format, I think PSBT-signing
> > devices still need to store the xpubs of their co-signers. It's not
> > possible to safely show an incoming address to the user without a
> > full understanding of the other keys in a "multisig wallet". Also,
> > it represents data that should not change between PSBT instances
> > (ie. tomorrow's co-signers should match today's).
> 
> I would like to keep hardware wallets state-less, otherwise wiping and
> recovering them would be problematic.
> At the setup phase the user can verify a multisignature address (or
> xpub) on the screens of all devices,
> after that we just need to verify that xpubs in the inputs and in the
> change output are the same.

At the setup phase, hardware wallet can sign a message that consists of
xpubs of participants, and some auxiliary text. It can use the key
derived from the master key, with path chosen specifically for this
purpose.

Hardware wallet then gives out this signature to the software.

The software will store the message and the signature (or maybe it can
take xpubs from PSBT), and will send this 'trusted-xpub-package' to
hardware wallet along with the transaction.

Hardware wallet can then verify that the message is indeed signed by
the key for that purpose, and then can mark the ouputs that use the
pubkeys derived from 'verified' xpubs as 'trusted' outputs. It can also
display the auxiliary text along with the information about the
'trusted' output.

This way, hardware wallet does not need to store anything extra besides
the master key.

This would allow to distinguish the trusted output even if the inputs
are not all derived from the same set of xpubs, that could happen in
more complex scenarios (batching, key rotation, etc.), and can possibly
be used to have several different types of 'trusted' outputs.

If the user loses the signature for trusted-xpub-package, the signature
can be re-created again - but maybe the procedure should be more
involved than ordinary signing, because creating creating such
'trusted-xpub-package' with malicious keys can enable attackers to
bypass these checks.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP Proposal - Address Paste Improvement

[Dmitry Petukhov via bitcoin-dev]

> > Do you know any reasonably convenient mechanism for end user to
> > transfer an address from, say, a web page to the wallet address
> > input field ?  
> 
> - QR code scanning of a Bitcoin URI
> - On Android: A "bitcoin:" URI intent or a BIP70 payment message
> intent
> - On desktop OSes there are similar mechanisms to launch Apps from the
> browser (e.g. for mailto: links)

This works if the author of the web page thought about this, and
created appropriate liks/qr codes. In many cases, addresses are
just presented for users as text, to copy.

People also send addresses in message apps and emails. Maybe if
applications start to autodetect bitcoin addresses and convert them to
bitcoin: links, there will be less need to copy-paste. But I suspect
that this feature will not be quickly adopted by applications.

> For cases where the payee is a well-known entity the BIP70 payment
> protocol has authentication via certificates. That doesn't work for
> the "the person in front of you is the only trust anchor you have"
> usecase though.

There are also BIP75 and BIP47 that may help, but the number of wallets
that support these protocols is small (I think in part because of
relative complexity of these protocols).
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP Proposal - Address Paste Improvement

[Dmitry Petukhov via bitcoin-dev]

> Copying addresses to the clipboard should be discouraged, rather than
> supported.

Do you know any reasonably convenient mechanism for end user to
transfer an address from, say, a web page to the wallet address
input field ?

The clipboard is just a low-hanging fruit for malware, anyway. It just
the most easy point to replace an address. If the computer is
compromized, malware can edit the web page in the memory of the browser
process, for example. If it shown as QR code, malware can decode,
detect that it is an address, and replace the image of QR code.

I think that the only way to protect from this is to add some form of
authentication for an address - 2fa (transfer checksum via second
channel), visual fingerprints for addresses, that will are hard to
detect (and hence, replace) for malware, signing the destination address
with the key of an address that is already known and checking the
signature, etc.

The problem will be to come up with an address authentication procedure
that will be convenient for users and widely supported, as a result.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev