Re: [bitcoin-dev] SAS: Succinct Atomic Swap
Ruben, In my opinion, this protocol is theoretical breakthrough as well as a practical protocol. Well done! I want to try and distil the core abstract ideas here as they appear to me. From my view, the protocol is a combination of two existing ideas and one new one: 1. In atomic swaps you can make the refund transaction on one chain dependent on the refund on the other using secret revelation. Thus only one chain needs to have a timelock and the other refund can be conditioned on a secret that is revealed when that first refund goes through. (This idea is in the monero atomic swap [1]). 2. Secret revelations can be used to give unconstrained spending power to one party. With an adaptor signature, rather than reveal a decryption key for another signature, you can just make the decryption key your signing key in the multisig so when you reveal it with the adaptor signautre the other party gains full knowledge of the private key for the output and can spend it arbitrarily. (this is just folklore and already what happens in HTLCs -- though it looks like lightning people are about to get rid of the unconstrained spend I think). The combination of these two ideas is novel in itself. The problem with idea (2) is that your unconstrained spending power over an output doesn't matter much if there is a pre-signed refund transaction spending from it -- you still have to spend it before the refund becomes valid. But if you bring in idea (1) this problem goes away! However, you are left with a new problem: What if the party with the timelock never refunds? Then the funds are locked forever. Here's where the truly novel part comes in. Ruben solves this by extending the standard *TLC contract: 1. Bob redeem with secret 2. Alice refund after T1 3. Bob redeem without secret after T2 We might call this a "Forced Refund *TLC". Alice must claim the refund or lose her money. This forces the refund secret revelation through punishment. If Alice refuses to refund Bob gets the asset he wanted anyway! The resulting protocol you get from applying these ideas is three transactions. At the end, one party has their funds in a non HD key output but if they want that they can just transfer it to an HD output in which case you get four transactions again. Thus I consider this to be a strict improvement over the four transaction protocol. Furthermore, one of the chains does not need a timelock. This is remarkable as the four transaction atomic swap is one of the most basic and most studied protocols. I considered it to be kind of "perfect" in a way. It just goes to show that this field is still very new and there are still things to discover in what we think is the most well trodden ground. I don't want to ignore that Ruben presents us with a two transaction protocol. He made a nice video explaining it here: https://www.youtube.com/watch?v=TlCxpdNScCA. It is harder to see the elegance of the idea in the two tx protocol because it involves revocation and relative timelocks etc. Actually, it is straightforward to naively achieve a two tx atomic swap with payment channels: 1. Alice and Bob set up payment channels to each other on different chains 2. They atomic swap the balances of the channels off-chain using HTLCs using the standard protocol. 3. Since one party exclusively owns the funds in each channel the party with no funds simply reveals their key in the funding OP_CHECKMULTISIG to the other 4. Both parties now watch the chain to see if the other tries to post a commitment transactions. The advantages that Ruben's two tx protocol has over this is that timelocks and monitoring is only needed on one of the chains. This is nothing to scoff at but for me the three tx protocol is the most elegant expression of the idea and the two tx protocol is a more optimised version that might make sense in some circumstances. [1] https://github.com/h4sh3d/xmr-btc-atomic-swap/blob/master/README.md LL ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] SAS: Succinct Atomic Swap
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
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
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
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 vi
[bitcoin-dev] SAS: Succinct Atomic Swap
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 f
Re: [bitcoin-dev] Compressed block headers
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
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