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

[ZmnSCPxj via bitcoin-dev]

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 the timeout 
transaction at L2, revealing Bob[1] and claiming the BTC.
* If Alice instead aborts at step 9 using the backout transaction at L1, Bob 
learns Alice[1] and can reclaim its LTC.
* Steps 10 and 11 are optional and "only" give Alice and Bob extra flexibility 
in what they can do with the funds (such as sweeping multiple swaps, RBFing, 
performing another swap, etc.), i.e. private key turnover.
  Bob can always claim the BTC funding txo before L1 by signing and 
broadcasting the success transaction.

Would this not work?
It requires that at least one chain involved supports witness segregation, in 
order to allow signing a dependent transaction before signing what it spends.

This has the advantage of using only absolute timelocks, which are better for 
privacy since ordinary wallets like Bitcoin Core and C-Lightning use absolute 
timelocks for ordinary spends onchain.


>
> Unfortunately this does not hold for the revoke transaction. It would
> be a bit awkward if Alice had a high fee copy after the protocol
> completes. She could send it to the blockchain and essentially Bob
> would be paying for it. I'm not as concerned about the other
> transactions, because those could all be bumped with CPFP if needed,
> but having different feerates would be nice.
>
> And a general comment about privacy: it seems inevitable that some
> information will be leaked if the protocol does not complete
> cooperatively. As long as the cooperative case is not traceable, that
> seems about 

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

[Pieter Wuille via bitcoin-dev]

Hi all,

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

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

I agree.

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

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

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

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

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

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

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

Thoughts?

--
Pieter

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

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

[Ruben Somsen via bitcoin-dev]

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.

>"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
- The timelocks are set up in such a way that the swap does not expire
unless Alice starts the relative timelock countdown (the revoke
transaction)
- This relative timelock setup comes practically for free, because the
asymmetry naturally requires that kind of setup

>The "OR Alice in +1 day" branch can be implemented, at least on Bitcoin and 
>similar blockchains, by signing a specific `nSequence`

"OR Alice in +1 day" is "refund transaction #1" from the diagram. If
I'm not mistaken, the change you are suggesting is exactly how "refund
transaction #2" is constructed. Note that #1 and #2 serve the same
purpose. Strictly speaking, #1 is not needed at all, but it's there to
give Alice the option to back out of the swap in two transactions as
opposed to three.

>It strikes me that the relative locktime is unnecessary on the output of this 
>refund tx

I believe I addressed this in the FAQ section (the question about
absolute timelocks). An absolute timelock is possible, but you then
need to make absolutely sure that the revoke transaction confirms in
time, otherwise the protocol can fail (namely after Bob has received a
copy of the success transaction and just waits and does nothing). You
also lose the ability to keep the channel open indefinitely.

>having a variety of different versions of the transactions with different 
>feerates could be used

That's a good point.

>As long as the one resolving a particular side of the swap is the one that 
>ocmpletes the signature (which I believe holds true for all branches?)

Unfortunately this does not hold for the revoke transaction. It would
be a bit awkward if Alice had a high fee copy after the protocol
completes. She could send it to the blockchain and essentially Bob
would be paying for it. I'm not as concerned about the other
transactions, because those could all be bumped with CPFP if needed,
but having different feerates would be nice.

And a general comment about privacy: it seems inevitable that some
information will be leaked if the protocol does not complete
cooperatively. As long as the cooperative case is not traceable, that
seems about as good as it can get. That's my view, at least. I'd be
curious to hear if you see that differently.

Cheers,
Ruben



On Mon, May 11, 2020 at 6:45 PM ZmnSCPxj  wrote:
>
> Good morning Ruben,
>
> CoinSwap for privacy is practically a "cross" chain atomic swap with the same 
> chain and token for both sides of the swap, see also this set of ideas: 
> https://github.com/AdamISZ/CoinSwapCS/issues/53
>
> "Instead, Bob simply hands secretBob to Alice" is basically the same as 
> private key turnover, as best as I can understand it, and gives significant 
> advantages, also described in passing here: 
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-May/017816.html
>
> Overall, this looks very much like a working CoinSwap as well.
>
> The Refund tx does not need anything more than a 2-of-2 script.
> The "OR Alice in +1 day" branch can be implemented, at least on Bitcoin and 
> similar blockchains, by signing a specific `nSequence`, or if the chain 
> forking predates BIP68, by using absolute locktimes and signing a specific 
> `nLockTime`, with the destination being just "Alice".
> This should help privacy, as now all `scriptPubKey`s will be 2-of-2 (or P2PKH 
> with 2p-ECDSA).
>
> (It strikes me that the relative locktime is unnecessary on the output of 
> this refund tx --- as long as both participants agree on either Alice or Bob 
> having a longer locktime, you can just use the locktime on the refund tx 
> directly as backout; see the topic "`nLockTime`-protected Backouts" on the 
> CoinSwapCS issue link)
>
> If you are willing to accept protocol complexity, having a variety of 
> different versions of the transactions with different feerates could be used 
> rather than the Decker-Russell-Osuntokun "eltoo" bring-your-own-fees method.
> In terms of privacy this is better as you would not be using anything other 
> than the most boring `SIGHASH_ALL` signing flag, whereas the 
> Decker-Russell-Osuntokun will be identifiable onchain (and thus possibly flag 
> the transaction as "of interest" to surveillors) due to use of 
> `SIGHASH_ANYPREVOUT`.
> As long as the one resolving a particular side of the swap is the one that 
> ocmpletes the signature (which I believe holds true for all branches?) 

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

[ZmnSCPxj via bitcoin-dev]

Good morning Ruben,

CoinSwap for privacy is practically a "cross" chain atomic swap with the same 
chain and token for both sides of the swap, see also this set of ideas: 
https://github.com/AdamISZ/CoinSwapCS/issues/53

"Instead, Bob simply hands secretBob to Alice" is basically the same as private 
key turnover, as best as I can understand it, and gives significant advantages, 
also described in passing here: 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-May/017816.html

Overall, this looks very much like a working CoinSwap as well.

The Refund tx does not need anything more than a 2-of-2 script.
The "OR Alice in +1 day" branch can be implemented, at least on Bitcoin and 
similar blockchains, by signing a specific `nSequence`, or if the chain forking 
predates BIP68, by using absolute locktimes and signing a specific `nLockTime`, 
with the destination being just "Alice".
This should help privacy, as now all `scriptPubKey`s will be 2-of-2 (or P2PKH 
with 2p-ECDSA).

(It strikes me that the relative locktime is unnecessary on the output of this 
refund tx --- as long as both participants agree on either Alice or Bob having 
a longer locktime, you can just use the locktime on the refund tx directly as 
backout; see the topic "`nLockTime`-protected Backouts" on the CoinSwapCS issue 
link)

If you are willing to accept protocol complexity, having a variety of different 
versions of the transactions with different feerates could be used rather than 
the Decker-Russell-Osuntokun "eltoo" bring-your-own-fees method.
In terms of privacy this is better as you would not be using anything other 
than the most boring `SIGHASH_ALL` signing flag, whereas the 
Decker-Russell-Osuntokun will be identifiable onchain (and thus possibly flag 
the transaction as "of interest" to surveillors) due to use of 
`SIGHASH_ANYPREVOUT`.
As long as the one resolving a particular side of the swap is the one that 
ocmpletes the signature (which I believe holds true for all branches?) then it 
would select the version of the transaction with the best feerate, which it 
effectively pays out to what it recovers.


Regards,
ZmnSCPxj


> Works today with single signer ECDSA adaptor signatures[0], or with
> Schnorr + MuSig.
>
> Diagram here:
> https://gist.github.com/RubenSomsen/8853a66a64825716f51b409be528355f#file-succinctatomicswap-svg
>
> Advantages:
>
> -   Requires merely two on-chain transactions for successful completion,
> as opposed to four
>
> -   Scriptless, and one of the chains doesn't need to support timelocks
> -   Can be used for efficient privacy swaps, e.g. Payswap[1]
>
> Disadvantages:
>
> -   Access to money is contingent on remembering secrets (backup complexity)
> -   Online/watchtower requirement for the timelock supporting chain (not
> needed with 3 tx protocol)
>
> Protocol steps:
>
> 0.) Alice & Bob pre-sign the following transactions, with exception of
> the signatures in [brackets]:
>
> -   success_tx (money to Bob): [sigSuccessAlice] + [sigSuccessBob]
> -   revoke_tx (timelock): sigRevokeAlice + sigRevokeBob, which must then
> be spent by:
> -- refund_tx (relative timelock, refund to Alice): [sigRefundAlice]
>
>
> -   {sigRefundBob}
> -- timeout_tx (longer relative timelock, money to Bob):
> sigTimeoutAlice + [sigTimeoutBob]
>
> {sigRefundBob} is an adaptor signature, which requires secretAlice to 
> complete
>
> 1.) Alice proceeds to lock up 1 BTC with Bob, using keyAlice & keyBob as 
> pubkeys
>
> If protocol is aborted after step 1:
>
>
> -   Alice publishes the revoke_tx, followed by the refund_tx &
> sigRefundBob, to get her BTC back
>
> -   If Alice neglects to publish the refund_tx in time, Bob will claim
> the BTC with the timeout_tx
>
> 2.) Bob locks up altcoins with Alice, using secretAlice & secretBob as 
> pubkeys
>
> If protocol is aborted after step 2:
>
> -   Once Alice publishes sigRefundBob, Bob learns secretAlice and
> regains control over the altcoins
>
> 3.) Protocol completion:
>
> -   Alice hands adaptor signature {sigSuccessAlice} to Bob, which
> requires secretBob to complete
>
> -   Bob could now claim the BTC via the success_tx, reveal secretBob,
> and thus give Alice control over the altcoins (= 3 tx protocol)
>
> -   Instead, Bob simply hands secretBob to Alice
> -   Likewise, Alice hands keyAlice to Bob to forego her claim on the refund_tx
> -   Bob continues to monitor the chain, because he'll have to respond if
> Alice ever publishes the revoke_tx
>
> More graceful protocol failure:
>
> If the protocol aborts after step 1, Alice would have been forced to
> make three transactions in total, while Bob has made none. We can
> reduce that to two by introducing a second refund_tx with timelock
> that can be published ahead of the revoke_tx and directly spends from
> the funding transaction. Publishing this transaction would also reveal
> secretAlice to Bob 

[bitcoin-dev] SAS: Succinct Atomic Swap

[Ruben Somsen via bitcoin-dev]

Works today with single signer ECDSA adaptor signatures[0], or with
Schnorr + MuSig.

Diagram here:
https://gist.github.com/RubenSomsen/8853a66a64825716f51b409be528355f#file-succinctatomicswap-svg


Advantages:

- Requires merely two on-chain transactions for successful completion,
as opposed to four
- Scriptless, and one of the chains doesn't need to support timelocks
- Can be used for efficient privacy swaps, e.g. Payswap[1]


Disadvantages:

- Access to money is contingent on remembering secrets (backup complexity)
- Online/watchtower requirement for the timelock supporting chain (not
needed with 3 tx protocol)


Protocol steps:


0.) Alice & Bob pre-sign the following transactions, with exception of
the signatures in [brackets]:

- success_tx (money to Bob): [sigSuccessAlice] + [sigSuccessBob]
- revoke_tx (timelock): sigRevokeAlice + sigRevokeBob, which must then
be spent by:
  -- refund_tx (relative timelock, refund to Alice): [sigRefundAlice]
+ {sigRefundBob}
  -- timeout_tx (longer relative timelock, money to Bob):
sigTimeoutAlice + [sigTimeoutBob]

{sigRefundBob} is an adaptor signature, which requires secretAlice to complete


1.) Alice proceeds to lock up 1 BTC with Bob, using keyAlice & keyBob as pubkeys

If protocol is aborted after step 1:

- Alice publishes the revoke_tx, followed by the refund_tx &
sigRefundBob, to get her BTC back
- If Alice neglects to publish the refund_tx in time, Bob will claim
the BTC with the timeout_tx


2.) Bob locks up altcoins with Alice, using secretAlice & secretBob as pubkeys

If protocol is aborted after step 2:

- Once Alice publishes sigRefundBob, Bob learns secretAlice and
regains control over the altcoins


3.) Protocol completion:

- Alice hands adaptor signature {sigSuccessAlice} to Bob, which
requires secretBob to complete
- Bob could now claim the BTC via the success_tx, reveal secretBob,
and thus give Alice control over the altcoins (= 3 tx protocol)
- Instead, Bob simply hands secretBob to Alice
- Likewise, Alice hands keyAlice to Bob to forego her claim on the refund_tx
- Bob continues to monitor the chain, because he'll have to respond if
Alice ever publishes the revoke_tx


More graceful protocol failure:

If the protocol aborts after step 1, Alice would have been forced to
make three transactions in total, while Bob has made none. We can
reduce that to two by introducing a second refund_tx with timelock
that can be published ahead of the revoke_tx and directly spends from
the funding transaction. Publishing this transaction would also reveal
secretAlice to Bob via an adaptor signature. In the 3 tx protocol,
this output can go directly to Alice. In the 2 tx protocol with
online/watchtower requirement, this output needs a script: spendable
by Alice + Bob right away OR by Alice after a relative timelock. It is
important to note that this transaction must NOT be published during
step 3. Once Bob can complete the success_tx, the revoke_tx is needed
to invalidate the success_tx prior to revealing secretAlice.


FAQ:

- Why not allow Alice to still claim the altcoins if she accidentally
lets Bob publish the timeout_tx?

Alice could send the revoke_tx at the same time, revealing both
secrets and causing likely losses. This can be solved by adding yet
another transaction, but it wouldn't be efficient and wouldn't
motivate Alice to behave.

- Is it possible to implement this protocol on chains which only
support absolute timelocks?

Yes, but then Bob must spend his swapped coins before the timelock
expires (or use the 3 tx protocol). Be aware that the revoke_tx MUST
confirm before the timeout_tx becomes valid, which may become a
problem if fees suddenly rise. The refund_tx can also not be allowed
to CPFP the timeout_tx, as they must confirm independently in order to
invalidate the success_tx first.

- Can't Alice just publish the revoke_tx after protocol completion?

Yes, she'd first have to move the altcoins (to invalidate
secretAlice), and could then try to claim the BTC by publishing the
revoke_tx, forcing Bob to react on-chain before the refund_tx becomes
valid. The eltoo[2] method of paying for fees (requires
sighash_anyprevout) or a second CPFP-able output may be an improvement
here (and also mitigates fee rising issues), but note that this also
increases the required amount of tx data if the protocol doesn't
complete successfully.

- Can this be made to work with hash locks?

Yes, by making the altcoins spendable via sigAlice + preimageBob OR
sigBob + preimageAlice, and ensuring the contracts on the BTC side
reveal either pre-image. Do note that this is not scriptless and will
thus increase the transaction size.


Open question:

Perhaps it's possible to perform an atomic swap in and out of
Lightning with only a single on-chain transaction. This would require
some kind of secondary set of HTLCs, allowing the sender to cancel a
Lightning payment by revealing a secret after a certain period of
time.


-- Ruben Somsen




Thanks to Lloyd Fournier for 

Re: [bitcoin-dev] Compressed block headers

[Robin Linus via bitcoin-dev]

Hi,

not sure if headergolf was mentioned yet. It's about very similar ideas: 
https://github.com/alecalve/headergolf









‐‐‐ Original Message ‐‐‐
On Friday, May 8, 2020 2:31 PM, Will Clark via bitcoin-dev 
 wrote:

> Hello list,
>
> I would like to propose a compressed block header scheme for IBD and block 
> announcements. This proposal is derivative of previous proposals found on 
> this list (see links in spec below) with some modifications and 
> clarifications.
>
> The below specification (also found at 
> https://github.com/willcl-ark/compressed-block-headers/blob/v1.0/compressed-block-headers.adoc
>  ) details the compression recommended along with the generated bandwidth 
> savings in the best-case scenario.
>
> I look forward to any feedback anyone has to offer on the specification 
> itself, as well as any additions or objections to the motivation.
>
> Cheers,
> Will
>
> = Compressed block headers
> Will Clark will8cl...@gmail.com
> v1.0, May 2020:
> :toc: preamble
> :toclevels: 4
>
> This work is a derivation of these mailing list posts:
>
> 1.  
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-August/014876.html[bitcoin-dev:
>  "Compressed" headers stream - 2017] (with resurrection 
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015385.html[here])
> 2.  
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015851.html[bitcoin-dev:
>  Optimized Header Sync]
>
> '''
>
> == Motivation
>
> Block headers as exchanged by nodes over the p2p network are currently 81 
> bytes each.
>
> For low bandwidth nodes who are doing a headers-only sync, reducing the 
> size of the headers can provide a significant bandwidth saving. Also, nodes 
> can support more header-only peers for IBD and protection against eclipse 
> attacks if header bandwidth is reduced.
>
> === Background
>
> Currently headers are sent over the p2p network as a vector of 
> `block_headers`, which are composed of the following sized fields:
>
> [cols="<,>"]
>
>
> |===
> |Field |Size
>
> |Version |4 bytes
> |Previous block hash |32 bytes
> |Merkle root hash |32 bytes
> |Time |4 bytes
> |nBits |4 bytes
> |nonce |4 bytes
> |txn_count |1 byte
> |Total |81 bytes
> |===
>
> Some fields can be removed completely, others can be compressed under certain 
> conditions.
>
> == Proposed specification
>
> === block_header2 data type
>
> The following table illustrates the proposed `block_header2` data type 
> specification.
>
> [cols="<,>,>"]
> |===
> |Field |Size |Compressed
>
> |Bitfield |1 byte | 1 byte
> |Version |4 bytes |0 \| 4 bytes
> |Previous block hash |32 bytes |0 \| 32 bytes
> |Merkle root hash |32 bytes |32 bytes
> |Time |4 bytes |2 \| 4 bytes
> |nBits |4 bytes |0 \| 4 bytes
> |nonce |4 bytes |4 bytes
> |Total |81 bytes |range: 39 - 81 bytes
> |===
>
> This compression results in a maximum reduction from an 81 byte header to 
> best-case 39 byte header. With 629,474 blocks in the current blockchain, a 
> continuous header sync from genesis (requiring a single full 81 byte header 
> followed by only compressed `block_header2`) has been tested to have its 
> required bandwidth reduced from 50.98MB down to 25.86MB, a saving of 49%.
>
>  Bitfield
>
> To make parsing of header messages easier and further increase header 
> compression, a single byte bitfield was suggested by gmaxwell 
> footnote:[https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015397.html].
>  We propose the following amended bitfield meanings (bits re-ordered to match 
> `headers2` field order):
>
> [cols="<,<"]
> |===
> |Bit |Meaning + field size to read
>
> |0 +
> 1 +
> 2 |version: same as the last distinct value 1st ... 7th (0 byte field) or a 
> new 32bit distinct value (4 byte field).
> |3 |prev_block_hash: is omitted (0 byte field) or included (32 byte field)
> |4 |timestamp: as small offset (2 byte field) or full (4 byte field).
> |5 |nbits: same as last header (0 byte field) or new (4 byte field).
> |6 |possibly to signal "more headers follow" to make the encoding 
> self-delimiting.
> |7 |currently undefined
> |===
>
> This bitfield adds 1 byte for every block in the chain, for a current total 
> increase of 629,474B.
>
>  Version
>
> In most cases the Version field will be identical to one referenced in one of 
> the previous 7 unique versions, as indicated by bits 0,1,2 of the Bitfield.
>
> To block 629,474 there were 616,137 blocks whose version was in the previous 
> 7 distinct versions, and only 13,338 blocks whose version was not, this 
> includes any version bit manipulation done via overt ASIC boost.
>
> [cols=">,>,>,>"]
> |===
> |Genesis to block |Current (B) |Compressed (B) |Saving (%)
>
> |629,474 |2,517,896 |53,352 |98
> |===
>
>  Previous block hash
>
> The previous block hash will always be the
> `SHA256(SHA256())` so is redundant, presuming you have the 
> previous header in the chain.
>
> [cols=">,>,>,>"]
> |===
> |Genesis 

Re: [bitcoin-dev] Compressed block headers

[Richard Myers via bitcoin-dev]

Thanks for resurrecting this idea for discussion Will.

I see three reasons for reducing block header bandwidth:

 1. support for long range block header broadcast via alternative
communication modalities like radio where every byte counts
 2. where repurposed mobile devices with SPV wallets are used because
metered bandwidth and hardware costs are high relative to income
 3. full nodes could potentially support twice as many header only peers
(is that a thing?) for better eclipse protection

Nodes could also run an additional daemon (eg. electrs) that serves
compressed block headers to light clients, but then it would be less likely
to see widespread use to reduce bandwidth between full nodes.

What are the negatives?
 - higher computation? probably minimal compared to serving the same
uncompressed headers.
 - memory for caching the last few versions? bounded to last seven, so not
too large.
 - complexity/bugs? minor and opt in for node operators, though you could
argue the gain isn't worth any kind of change for nodes with high bandwidth
connections.
 - use of low-bandwidth light clients should not be encouraged? that is a
separate discussion, but I do not currently see any proposals to remove
light client support.

I'm curious what other people think. Are the motivations enough to justify
a change to the protocol that produces a high percentage (but low absolute)
bandwidth reduction for transmitting block headers?

  -- Richard

On Fri, May 8, 2020 at 3:34 PM Will Clark via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello list,
>
> I would like to propose a compressed block header scheme for IBD and block
> announcements. This proposal is derivative of previous proposals found on
> this list (see links in spec below) with some modifications and
> clarifications.
>
> The below specification (also found at
> https://github.com/willcl-ark/compressed-block-headers/blob/v1.0/compressed-block-headers.adoc
> ) details the compression recommended along with the generated bandwidth
> savings in the best-case scenario.
>
> I look forward to any feedback anyone has to offer on the specification
> itself, as well as any additions or objections to the motivation.
>
> Cheers,
> Will
>
>
> = Compressed block headers
> Will Clark 
> v1.0, May 2020:
> :toc: preamble
> :toclevels: 4
>
>
> This work is a derivation of these mailing list posts:
>
> 1.
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-August/014876.html[bitcoin-dev:
> "Compressed" headers stream - 2017] (with resurrection
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015385.html[here]
> )
>
> 2.
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015851.html[bitcoin-dev:
> Optimized Header Sync]
>
> '''
>
> == Motivation
>
> Block headers as exchanged by nodes over the p2p network are currently 81
> bytes each.
>
> For low bandwidth nodes who are doing a headers-only sync, reducing the
> size of the headers can provide a significant bandwidth saving. Also, nodes
> can support more header-only peers for IBD and protection against eclipse
> attacks if header bandwidth is reduced.
>
> === Background
>
> Currently headers are sent over the p2p network as a vector of
> `block_headers`, which are composed of the following sized fields:
>
> [cols="<,>"]
> |===
> |Field   |Size
>
> |Version |4 bytes
> |Previous block hash |32 bytes
> |Merkle root hash|32 bytes
> |Time|4 bytes
> |nBits   |4 bytes
> |nonce   |4 bytes
> |txn_count   |1 byte
> |*Total* |81 bytes
> |===
>
> Some fields can be removed completely, others can be compressed under
> certain conditions.
>
> == Proposed specification
>
> === block_header2 data type
>
> The following table illustrates the proposed `block_header2` data type
> specification.
>
> [cols="<,>,>"]
> |===
> |Field   |Size |Compressed
>
> |Bitfield|1 byte   | 1 byte
> |Version |4 bytes  |0 \| 4 bytes
> |Previous block hash |32 bytes |0 \| 32 bytes
> |Merkle root hash|32 bytes |32 bytes
> |Time|4 bytes  |2 \| 4 bytes
> |nBits   |4 bytes  |0 \| 4 bytes
> |nonce   |4 bytes  |4 bytes
> |*Total* |81 bytes |range: 39 - 81 bytes
> |===
>
> This compression results in a maximum reduction from an 81 byte header to
> best-case 39 byte header. With 629,474 blocks in the current blockchain, a
> continuous header sync from genesis (requiring a single full 81 byte header
> followed by only compressed `block_header2`) has been tested to have its
> required bandwidth reduced from 50.98MB down to 25.86MB, a saving of 49%.
>
>  Bitfield
>
> To make parsing of header messages easier and further increase header
> compression, a single byte bitfield was suggested by gmaxwell footnote:[
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015397.html].
> We propose the following