Re: [bitcoin-dev] Card Shuffle To Bitcoin Seed

[Devrandom via bitcoin-dev]

I would suggest 50+ 6-sided dice rolls, giving about 128 bits of entropy.
Compared to a shuffle, it's easier to be sure that you got the right amount
of entropy, even if the dice are somewhat biased.


On Mon, Feb 4, 2019 at 2:33 PM James MacWhyte via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
> James
>
>
> On Sun, Feb 3, 2019 at 10:27 AM Ryan Havar via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Conveniently a shuffled deck of cards also can serve as a physical backup
>> which is easy to hide in plain sight with great plausible deniability.
>>
>
> To make sure someone doesn't play with your cards and mix up the order,
> use a permanent marker to draw a diagonal line on the side of the deck from
> corner to corner. If the cards ever get mixed up, you can put them back in
> order by making sure the diagonal line matches up.
> ___
> 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] Interrogating a BIP157 server, BIP158 change proposal

[Olaoluwa Osuntokun via bitcoin-dev]

Hi Tamas,

This is how the filter worked before the switch over to optimize for a
filter containing the minimal items needed for a regular wallet to function.
When this was proposed, I had already implemented the entire proposal from
wallet to full-node. At that point, we all more or less decided that the
space savings (along with intra-block compression) were worthwhile, we
weren't cutting off any anticipated application level use cases (at that
point we had already comprehensively integrated both filters into lnd), and
that once committed the security loss would disappear.

I think it's too late into the current deployment of the BIPs to change
things around yet again. Instead, the BIP already has measures in place for
adding _new_ filter types in the future. This along with a few other filter
types may be worthwhile additions as new filter types.

-- Laolu

On Mon, Feb 4, 2019 at 12:59 PM Tamas Blummer 
wrote:

> I participated in that discussion in 2018, but have not had the insight
> gathered by now though writing both client and server implementation of
> BIP157/158
>
> Pieter Wuille considered the design choice I am now suggesting here as
> alternative (a) in:
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016064.html
> In his evaluation he recognized that a filter having spent output and
> output scripts would allow decision on filter correctness by knowing the
> block only.
> He did not evaluate the usefulness in the context of checkpoints, which I
> think are an important shortcut here.
>
> Yes, a filter that is collecting input and output scripts is shorter if
> script re-use is frequent, but I showed back in 2018 in the same thread
> that this saving is not that significant in recent history as address reuse
> is no longer that frequent.
>
> A filter on spent outpoint is just as useful for wallets as is one on
> spent script, since they naturally scan the blockchain forward and thereby
> learn about their coins by the output script before they need to check
> spends of those outpoints.
>
> It seems to me that implementing an interrogation by evtl. downloading
> blocks at checkpoints is much simpler than following multiple possible
> filter paths.
>
> A spent outpoint filter allows us to decide on coin availability based on
> immutable store, without updated and eventually rolled back UTXO store. The
> availability could be decided by following the filter path to current tip
> to genesis and
> check is the outpoint was spent earlier. False positives can be sorted out
> with a block download. Murmel implements this if running in server mode,
> where blocks are already there.
>
> Therefore I ask for a BIP change based on better insight gained through
> implementation.
>
> Tamas Blummer
>
> On Feb 4, 2019, at 21:18, Jim Posen  wrote:
>
> Please see the thread "BIP 158 Flexibility and Filter Size" from 2018
> regarding the decision to remove outpoints from the filter [1].
>
> Thanks for bringing this up though, because more discussion is needed on
> the client protocol given that clients cannot reliably determine the
> integrity of a block filter in a bandwidth-efficient manner (due to the
> inclusion of input scripts).
>
> I see three possibilities:
> 1) Introduce a new P2P message to retrieve all prev-outputs for a given
> block (essentially the undo data in Core), and verify the scripts against
> the block by executing them. While this permits some forms of input script
> malleability (and thus cannot discriminate between all valid and invalid
> filters), it restricts what an attacker can do. This was proposed by Laolu
> AFAIK, and I believe this is how btcd is proceeding.
> 2) Clients track multiple possible filter header chains and essentially
> consider the union of their matches. So if any filter received for a
> particular block header matches, the client downloads the block. The client
> can ban a peer if they 1) ever return a filter omitting some data that is
> observed in the downloaded block, 2) repeatedly serve filters that trigger
> false positive block downloads where such a number of false positives is
> statistically unlikely, or 3) repeatedly serves filters that are
> significantly larger than the expected size (essentially padding the actual
> filters with garbage to waste bandwidth). I have not done the analysis yet,
> but we should be able to come up with some fairly simple banning heuristics
> using Chernoff bounds. The main downside is that the client logic to track
> multiple possible filter chains and filters per block is more complex and
> bandwidth increases if connected to a malicious server. I first heard about
> this idea from David Harding.
> 3) Rush straight to committing the filters into the chain (via witness
> reserved value or coinbase OP_RETURN) and give up on the pre-softfork BIP
> 157 P2P mode.
>
> I'm in favor of option #2 despite the downsides since it requires the
> smallest number of changes and is supported by the BIP 157 P2P protocol 

Re: [bitcoin-dev] Card Shuffle To Bitcoin Seed

[James MacWhyte via bitcoin-dev]

James


On Sun, Feb 3, 2019 at 10:27 AM Ryan Havar via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Conveniently a shuffled deck of cards also can serve as a physical backup
> which is easy to hide in plain sight with great plausible deniability.
>

To make sure someone doesn't play with your cards and mix up the order, use
a permanent marker to draw a diagonal line on the side of the deck from
corner to corner. If the cards ever get mixed up, you can put them back in
order by making sure the diagonal line matches up.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Tamas Blummer via bitcoin-dev]

I participated in that discussion in 2018, but have not had the insight 
gathered by now though writing both client and server implementation of 
BIP157/158

Pieter Wuille considered the design choice I am now suggesting here as 
alternative (a) in: 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016064.html 

In his evaluation he recognized that a filter having spent output and output 
scripts would allow decision on filter correctness by knowing the block only.
He did not evaluate the usefulness in the context of checkpoints, which I think 
are an important shortcut here.

Yes, a filter that is collecting input and output scripts is shorter if script 
re-use is frequent, but I showed back in 2018 in the same thread that this 
saving is not that significant in recent history as address reuse is no longer 
that frequent.

A filter on spent outpoint is just as useful for wallets as is one on spent 
script, since they naturally scan the blockchain forward and thereby learn 
about their coins by the output script before they need to check spends of 
those outpoints.

It seems to me that implementing an interrogation by evtl. downloading blocks 
at checkpoints is much simpler than following multiple possible filter paths.

A spent outpoint filter allows us to decide on coin availability based on 
immutable store, without updated and eventually rolled back UTXO store. The 
availability could be decided by following the filter path to current tip to 
genesis and
check is the outpoint was spent earlier. False positives can be sorted out with 
a block download. Murmel implements this if running in server mode, where 
blocks are already there.

Therefore I ask for a BIP change based on better insight gained through 
implementation.

Tamas Blummer

> On Feb 4, 2019, at 21:18, Jim Posen  wrote:
> 
> Please see the thread "BIP 158 Flexibility and Filter Size" from 2018 
> regarding the decision to remove outpoints from the filter [1].
> 
> Thanks for bringing this up though, because more discussion is needed on the 
> client protocol given that clients cannot reliably determine the integrity of 
> a block filter in a bandwidth-efficient manner (due to the inclusion of input 
> scripts).
> 
> I see three possibilities:
> 1) Introduce a new P2P message to retrieve all prev-outputs for a given block 
> (essentially the undo data in Core), and verify the scripts against the block 
> by executing them. While this permits some forms of input script malleability 
> (and thus cannot discriminate between all valid and invalid filters), it 
> restricts what an attacker can do. This was proposed by Laolu AFAIK, and I 
> believe this is how btcd is proceeding.
> 2) Clients track multiple possible filter header chains and essentially 
> consider the union of their matches. So if any filter received for a 
> particular block header matches, the client downloads the block. The client 
> can ban a peer if they 1) ever return a filter omitting some data that is 
> observed in the downloaded block, 2) repeatedly serve filters that trigger 
> false positive block downloads where such a number of false positives is 
> statistically unlikely, or 3) repeatedly serves filters that are 
> significantly larger than the expected size (essentially padding the actual 
> filters with garbage to waste bandwidth). I have not done the analysis yet, 
> but we should be able to come up with some fairly simple banning heuristics 
> using Chernoff bounds. The main downside is that the client logic to track 
> multiple possible filter chains and filters per block is more complex and 
> bandwidth increases if connected to a malicious server. I first heard about 
> this idea from David Harding.
> 3) Rush straight to committing the filters into the chain (via witness 
> reserved value or coinbase OP_RETURN) and give up on the pre-softfork BIP 157 
> P2P mode.
> 
> I'm in favor of option #2 despite the downsides since it requires the 
> smallest number of changes and is supported by the BIP 157 P2P protocol as 
> currently written. (Though the recommended client protocol in the BIP needs 
> to be updated to account for this). Another benefit of it is that it removes 
> some synchronicity assumptions where a peer with the correct filters keeps 
> timing out and is assumed to be dishonest, while the dishonest peer is 
> assumed to be OK because it is responsive.
> 
> If anyone has other ideas, I'd love to hear them.
> 
> -jimpo
> 
> [1] 
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016057.html 
> 
> 
> 
> 
> On Mon, Feb 4, 2019 at 10:53 AM Tamas Blummer via bitcoin-dev 
>  > wrote:
> TLDR: a change to BIP158 would allow decision on which filter chain is 
> correct at lower bandwith use
> 
> Assume there is a BIP157 

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

[Jim Posen via bitcoin-dev]

Please see the thread "BIP 158 Flexibility and Filter Size" from 2018
regarding the decision to remove outpoints from the filter [1].

Thanks for bringing this up though, because more discussion is needed on
the client protocol given that clients cannot reliably determine the
integrity of a block filter in a bandwidth-efficient manner (due to the
inclusion of input scripts).

I see three possibilities:
1) Introduce a new P2P message to retrieve all prev-outputs for a given
block (essentially the undo data in Core), and verify the scripts against
the block by executing them. While this permits some forms of input script
malleability (and thus cannot discriminate between all valid and invalid
filters), it restricts what an attacker can do. This was proposed by Laolu
AFAIK, and I believe this is how btcd is proceeding.
2) Clients track multiple possible filter header chains and essentially
consider the union of their matches. So if any filter received for a
particular block header matches, the client downloads the block. The client
can ban a peer if they 1) ever return a filter omitting some data that is
observed in the downloaded block, 2) repeatedly serve filters that trigger
false positive block downloads where such a number of false positives is
statistically unlikely, or 3) repeatedly serves filters that are
significantly larger than the expected size (essentially padding the actual
filters with garbage to waste bandwidth). I have not done the analysis yet,
but we should be able to come up with some fairly simple banning heuristics
using Chernoff bounds. The main downside is that the client logic to track
multiple possible filter chains and filters per block is more complex and
bandwidth increases if connected to a malicious server. I first heard about
this idea from David Harding.
3) Rush straight to committing the filters into the chain (via witness
reserved value or coinbase OP_RETURN) and give up on the pre-softfork BIP
157 P2P mode.

I'm in favor of option #2 despite the downsides since it requires the
smallest number of changes and is supported by the BIP 157 P2P protocol as
currently written. (Though the recommended client protocol in the BIP needs
to be updated to account for this). Another benefit of it is that it
removes some synchronicity assumptions where a peer with the correct
filters keeps timing out and is assumed to be dishonest, while the
dishonest peer is assumed to be OK because it is responsive.

If anyone has other ideas, I'd love to hear them.

-jimpo

[1]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016057.html



On Mon, Feb 4, 2019 at 10:53 AM Tamas Blummer via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> TLDR: a change to BIP158 would allow decision on which filter chain is
> correct at lower bandwith use
>
> Assume there is a BIP157 client that learned a filter header chain earlier
> and is now offered an alternate reality by a newly connected BIP157 server.
>
> The client notices the alternate reality by routinely asking for filter
> chain checkpoints after connecting to a new BIP157 server. A divergence at
> a checkpoint means that the server disagrees the client's history at or
> before the first diverging checkpoint. The client would then request the
> filter headers between the last matching and first divergent checkpoint,
> and quickly figure which block’s filter is the first that does not match
> previous assumption, and request that filter from the server.
>
> The client downloads the corresponding block, checks that its header fits
> the PoW secured best header chain, re-calculates merkle root of its
> transaction list to know that it is complete and queries the filter to see
> if every output script of every transaction is contained in there, if not
> the server is lying, the case is closed, the server disconnected.
>
> Having all output scripts in the filter does not however guarantee that
> the filter is correct since it might omit input scripts. Inputs scripts are
> not part of the downloaded block, but are in some blocks before that.
> Checking those are out of reach for lightweight client with tools given by
> the current BIP.
>
> A remedy here would be an other filter chain on created and spent
> outpoints as is implemented currently by Murmel. The outpoint filter chain
> must offer a match for every spent output of the block with the divergent
> filter, otherwise the interrogated server is lying since a PoW secured
> block can not spend coins out of nowhere. Doing this check would already
> force the client to download the outpoint filter history up-to the point of
> divergence. Then the client would have to download and PoW check every
> block that shows a match in outpoints until it figures that one of the
> spent outputs has a script that was not in the server’s filter, in which
> case the server is lying. If everything checks out then the previous
> assumption on filter history was incorrect and should be replaced by 

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

[Tamas Blummer via bitcoin-dev]

TLDR: a change to BIP158 would allow decision on which filter chain is correct 
at lower bandwith use

Assume there is a BIP157 client that learned a filter header chain earlier and 
is now offered an alternate reality by a newly connected BIP157 server.

The client notices the alternate reality by routinely asking for filter chain 
checkpoints after connecting to a new BIP157 server. A divergence at a 
checkpoint means that the server disagrees the client's history at or before 
the first diverging checkpoint. The client would then request the filter 
headers between the last matching and first divergent checkpoint, and quickly 
figure which block’s filter is the first that does not match previous 
assumption, and request that filter from the server.

The client downloads the corresponding block, checks that its header fits the 
PoW secured best header chain, re-calculates merkle root of its transaction 
list to know that it is complete and queries the filter to see if every output 
script of every transaction is contained in there, if not the server is lying, 
the case is closed, the server disconnected.

Having all output scripts in the filter does not however guarantee that the 
filter is correct since it might omit input scripts. Inputs scripts are not 
part of the downloaded block, but are in some blocks before that. Checking 
those are out of reach for lightweight client with tools given by the current 
BIP.

A remedy here would be an other filter chain on created and spent outpoints as 
is implemented currently by Murmel. The outpoint filter chain must offer a 
match for every spent output of the block with the divergent filter, otherwise 
the interrogated server is lying since a PoW secured block can not spend coins 
out of nowhere. Doing this check would already force the client to download the 
outpoint filter history up-to the point of divergence. Then the client would 
have to download and PoW check every block that shows a match in outpoints 
until it figures that one of the spent outputs has a script that was not in the 
server’s filter, in which case the server is lying. If everything checks out 
then the previous assumption on filter history was incorrect and should be 
replaced by the history offered by the interrogated server. 

As you see the interrogation works with this added filter but is highly 
ineffective. A really light client should not be forced to download lots of 
blocks just to uncover a lying filter server. This would actually be an easy 
DoS on light BIP157 clients.

A better solution is a change to BIP158 such that the only filter contains 
created scripts and spent outpoints. It appears to me that this would serve 
well both wallets and interrogation of filter servers well:

Wallets would recognize payments to their addresses by the filter as output 
scripts are included, spends from the wallet would be recognized as a wallet 
already knows outpoints of its previously received coins, so it can query the 
filters for them.

Interrogation of a filter server also simplifies, since the filter of the block 
can be checked entirely against the contents of the same block. The decision on 
filter correctness does not require more bandwith then download of a block at 
the mismatching checkpoint. The client could only be forced at max. to download 
1/1000 th of the blockchain in addition to the filter header history.

Therefore I suggest to change BIP158 to have a base filter, defined as:

A basic filter MUST contain exactly the following items for each transaction in 
a block:
• Spent outpoints
• The scriptPubKey of each output, aside from all OP_RETURN output 
scripts.

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

Re: [bitcoin-dev] Card Shuffle To Bitcoin Seed

[Adam Ficsor via bitcoin-dev]

Unlike mouse movement it works in a CLI software, which is great. However,
isn't there something else you can use instead of cards? Something with
invariant culture and maybe more common.

On Sun, Feb 3, 2019 at 7:27 PM Ryan Havar via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> More of a shower-thought than a BIP, but it's something I've long wish
> (hardware) wallets supported:
>
> ---
>
> Abstract: Bitcoin Wallets generally ask us to trust their seed generation
> is both correct and honest. Especially for hardware and air gapped wallets,
> this is both a big ask and more or less impossible to practically verify.
> So we propose a bring-your-own-entropy approach in which the wallet can
> function completely deterministically. Our method is based on shuffling
> physical deck of cards. There are 52!  (2^219.88) different shuffle order,
> which is a big enough space to be secure against collision and brute force
> attacks. Conveniently a shuffled deck of cards also can serve as a physical
> backup which is easy to hide in plain sight with great plausible
> deniability.
>
>
> Representation:
>
> Each card has a suit which can be represented by one of SCHD (spades,
> clubs, hearts, diamonds) and a value of one of 23456789TJQKA where the
> numbers are obvious and (T=ten, J=jack, Q=queen, K=king, A=ace) so "7 of
> clubs" would be represented by "7C" and a "Ten of Hearts" would be
> represented with "TH".
>
> An deck of cards looks like:
>
>
> 2S,3S,4S,5S,6S,7S,8S,9S,TS,JS,QS,KS,AS,2C,3C,4C,5C,6C,7C,8C,9C,TC,JC,QC,KC,AC,2H,3H,4H,5H,6H,7H,8H,9H,TH,JH,QH,KH,AH,2D,3D,4D,5D,6D,7D,8D,9D,TD,JD,QD,KD,AD
>
> And can be verified by making sure that every one of the 52 cards appears
> exactly once.
>
>
> Step 1.  Shuffle your deck of cards
>
> This is a lot harder than you'd imagine, so do it quite a few times, with
> quite a few different techniques. It is advised to do at *least* 7 good
> quality shuffles to achieve a true cryptographically secure shuffle. Do not
> look at the cards while shuffling (to avoid biasing) and don't be afraid to
> also shuffle them face down on the table. Err on the side over
> over-shuffling.
> See also:
> https://en.wikipedia.org/wiki/Shuffling#Sufficient_number_of_shuffles
>
> Step 2. Write out the order (comma separated)
>
> And example shuffle is:
>
>
> 5C,7C,4C,AS,3C,KC,AD,QS,7S,2S,5H,4D,AC,9C,3H,6H,9D,4S,8D,TD,2H,7H,JD,QD,2D,JC,KH,9S,9H,4H,6C,7D,3D,6S,2C,AH,QC,TH,TC,JS,6D,8H,8C,JH,8S,KD,QH,5D,5S,KS,TS,3S
>
> Step 3.  Sha512 it to create a seed
>
> In the example above you should get:
>
> dc04e4c331b1bd347581d4361841335fe0b090d39dfe5e1c258c547255cd5cf1545e2387d8a7c4dc53e03cacca049a414a9269a2ac6954429955476c56038498
>
> Step 4. Interpret it
>
> e.g. For bip32 you would treat the first 32 bytes as the private key, and
> the second 32 bytes as as the extension code.
>
>
>
>
> -Ryan
>
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>


-- 
Best,
Ádám
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev