Re: [bitcoin-dev] Compressed Bitcoin Transactions
Hi, After reviewing all the feedback and writing a reference implementation, I have linked the updated schema and a Draft PR for a reference Implementation to Bitcoin Core. Some of the major changes consist of: - Removing the grinding of the nLocktime in favor of a relative block height, which all of the Compressed Inputs use. - And the use of a second kind of Variable Integer. Compressed Transaction Schema: [compressed_transactions.md](https://github.com/TomBriar/bitcoin/blob/2023-05--tx-compression/doc/compressed_transactions.md) Reference Impl/Draft PR: https://github.com/bitcoin/bitcoin/pull/29134 Thanks-Tom. Text of Compressed_Transactions.md: Compressed Transaction Schema By (Tom Briar) and (Andrew Poelstra) https://github.com/TomBriar/bitcoin/blob/2023-05--tx-compression/doc/compressed_transactions.md#1-abstract1. Abstract With this Transaction Compression Schema we use several methods to compress transactions, including dropping data and recovering it on decompression by grinding until we obtain valid signatures. The bulk of our size savings come from replacing the prevout of each input by a block height and index. This requires the decompression to have access to the blockchain, and also means that compression is ineffective for transactions that spend unconfirmed or insufficiently confirmed outputs. Even without compression, Taproot keyspends are very small: as witness data they include only a single 64/65-byte signature and do not repeat the public key or any other metadata. By using pubkey recovery, we obtain Taproot-like compression for legacy and Segwit transactions. The main applications for this schema are for steganography, satellite/radio broadcast, and other low bandwidth channels with a high CPU availability on decompression. We assume users have some ability to shape their transactions to improve their compressibility, and therefore give special treatment to certain transaction forms. This schema is easily reversible except when compressing the Txid/Vout input pairs(Method 4). Compressing the input Txid/Vout is optional, and without it still gleans 50% of the total compression. This allows for the additional use case of P2P communication. https://github.com/TomBriar/bitcoin/blob/2023-05--tx-compression/doc/compressed_transactions.md#2-methods2. Methods The four main methods to achieve a lower transactions size are: - packing transaction metadata before the transaction and each of its inputs and outputs to determine the structure of the following data. - replacing 32-bit numeric values with either variable-length integers (VarInts) or compact-integers (CompactSizes). - using compressed signatures and public key recovery upon decompression. - replacing the 36-byte txid/vout pair with a blockheight and output index. Method 4 will cause the compressed transaction to be undecompressable if a block reorg occurs at or before the block it's included in. Therefore, we'll only compress the Txid if the transaction input is at least one hundred blocks old. https://github.com/TomBriar/bitcoin/blob/2023-05--tx-compression/doc/compressed_transactions.md#3-schema3 Schema https://github.com/TomBriar/bitcoin/blob/2023-05--tx-compression/doc/compressed_transactions.md#31-primitives3.1 Primitives NameWidth Description CompactSize 1-5 Bytes For 0-253, encode the value directly in one byte. For 254-65535, encode 254 followed by 2 little-endian bytes. For 65536-(2^32-1), encode 255 followed by 4 little-endian bytes. CompactSize flag2 Bits 1, 2 or 3 indicate literal values. 0 indicates that the value will be encoded in a later CompactInt. VarInt 1+ Bytes7-bit little-endian encoding, with each 7-bit word encoded in a byte. The highest bit of each byte is 1 if more bytes follow, and 0 for the last byte. VLP-Bytestream 2+ BytesA VarInt Length Prefixed Bytestream. Has a VarInt prefixed to determine the length. https://github.com/TomBriar/bitcoin/blob/2023-05--tx-compression/doc/compressed_transactions.md#32-general-schema3.2 General Schema NameWidth Description Transaction Metadata1 Byte Information on the structure of the transaction. See Section 3.3. Version 0-5 Bytes An optional CompactSize containing the transactions version. Input Count 0-5 Bytes An optional CompactSize containing the transactions input count. Output Count0-5 Bytes An optional CompactSize containing the transactions output count. LockTime0-5 Bytes An optional CompactSize containing the transaction LockTime if its non zero. Minimum Blockheight 1-5 Bytes A VarInt containing the Minimum Blockheight of which the transaction locktime and input blockheights are given as offsets. Input Metadata+Output Metadata 1+ BytesA Encoding containing metadata on all the inputs and then all the outputs of the transaction. For each input see Section 3.4, for each output see Section
Re: [bitcoin-dev] Compressed Bitcoin Transactions
Thanks Tom. It looks like you posted a text-scrape of the rendered markdown, which is hard to read. For posterity here is the full text. Best Andrew === begin compressed_transactions.md === # Compressed Transaction Schema By (Tom Briar) and (Andrew Poelstra) ## 1. Abstract With this Transaction Compression Schema we use several methods to compress transactions, including dropping data and recovering it on decompression by grinding until we obtain valid signatures. The bulk of our size savings come from replacing the prevout of each input by a block height and index. This requires the decompression to have access to the blockchain, and also means that compression is ineffective for transactions that spend unconfirmed or insufficiently confirmed outputs. Even without compression, Taproot keyspends are very small: as witness data they include only a single 64/65-byte signature and do not repeat the public key or any other metadata. By using pubkey recovery, we obtain Taproot-like compression for legacy and Segwit transactions. The main applications for this schema are for steganography, satellite/radio broadcast, and other low bandwidth channels with a high CPU availability on decompression. We assume users have some ability to shape their transactions to improve their compressibility, and therefore give special treatment to certain transaction forms. This schema is easily reversible except for compressing the Txid/Vout input pairs(Method 4). Compressing the input Txid/Vout is optional, and without it still gleans 50% of the total compression. This allows for the additional use case of P2P communication. ## 2. Methods The four main methods to achieve a lower transactions size are: 1. packing transaction metadata before the transaction and each of its inputs and outputs to determine the structure of the following data. 2. replacing 32-bit numeric values with either variable-length integers (VarInts) or compact-integers (CompactSizes). 3. using compressed signatures and public key recovery upon decompression. 4. replacing the 36-byte txid/vout pair with a blockheight and output index. Method 4 will cause the compressed transaction to be undecompressable if a block reorg occurs at or before the block it's included in. Therefore, we'll only compress the Txid if the transaction input is at least one hundred blocks old. ## 3 Schema ### 3.1 Primitives | Name | Width | Description | |--|---|-| | CompactSize | 1-5 Bytes | For 0-253, encode the value directly in one byte. For 254-65535, encode 254 followed by 2 little-endian bytes. For 65536-(2^32-1), encode 255 followed by 4 little-endian bytes. | | CompactSize flag | 2 Bits| 1, 2 or 3 indicate literal values. 0 indicates that the value will be encoded in a later CompactInt. | | VarInt | 1+ Bytes | 7-bit little-endian encoding, with each 7-bit word encoded in a byte. The highest bit of each byte is 1 if more bytes follow, and 0 for the last byte. | | VLP-Bytestream | 2+ Bytes | A VarInt Length Prefixed Bytestream. Has a VarInt prefixed to determine the length. | ### 3.2 General Schema | Name | Width | Description | ||-|-| | Transaction Metadata | 1 Byte| Information on the structure of the transaction. See Section 3.3. | | Version| 0-5 Bytes | An optional CompactSize containing the transactions version. | | Input Count| 0-5 Bytes | An optional CompactSize containing the transactions input count. | | Output Count | 0-5 Bytes | An optional CompactSize containing the transactions output count. | | LockTime | 0-5 Bytes | An optional CompactSize containing the transaction LockTime if its non zero. | | Minimum Blockheight| 1-5 Bytes | A VarInt containing the Minimum Blockheight of which the transaction locktime and input blockheights are given as offsets. | | Input Metadata+Output Metadata | 1+ Bytes | A Encoding containing metadata on all the inputs and then all the outputs of the transaction. For each input see Section 3.4, for each output see Section 3.5. | | Input Data | 66+ Bytes | See Section 3.6 for each input. | | Output Data| 3+ Bytes | See Section 3.7 for each output. | For the four CompactSize listed above we could use a more compact bit encoding for these but they are already a fall back for the bit encoding of the Transaction Metadata. ### 3.3 Transaction Metadata | Name | Width | Description | |--||-| | Version | 2 Bits | A CompactSize flag for the transaction version. | | Input Count | 2 Bits | A CompactSize flag for the transaction input count. | | Output Count | 2 Bits | A CompactSize flag for the transaction output count. | | LockTime
Re: [bitcoin-dev] Future of the bitcoin-dev mailing list
Hi all, It looks like there are only a few mailing lists left on https://lists.linuxfoundation.org/mailman/listinfo and all of the remaining ones are using Mailman version 2.1.15, which is not the current version - https://www.gnu.org/software/mailman/ Was there any decision made on where to move the bitcoin-dev mailing list to? Thanks, Brad On 2023-11-11 02:54, vjudeu via bitcoin-dev wrote: > What about using Signet, or some separate P2P network, to handle all of that? > > 1. All e-mails could be sent in a pure P2P way, just each "mailing list node" > would receive it, and include to its mempool. > 2. The inclusion of some message would be decided by signing a block. > Moderators would pick the proper messages, and publish them by broadcasting a > new block to all nodes. > 3. Each message will be signed by some public key. It could be changed each > time, or even derived from some HD wallet. Only those owning "master public > keys" would know, which messages were sent by the same person. > 4. The time of the block could be much longer than 10 minutes. It could be > for example one hour, one day, or even longer. Or, the commitment to all of > that could be just included "every sometimes" to the existing Signet chain, > because it would take no additional on-chain bytes, and can be easily done in > the coinbase transaction. > 5. If there will be too much spam in the mempool, then hashcash-based Proof > of Work can be used to filter messages. Instead of fee-based filtering, it > could be Proof-of-Work-based filtering. Even better: because of "master > public keys", the regular participants could be allowed anyway, without > providing additional Proof of Work. Their signature would be sufficient in > that case. > 6. The code is almost there. Maybe there are even altcoins, designed > specifically for storing data, and we could just use them? > 7. This kind of decision would push things like Silent Payments forward. > Because then, you could develop scanners, to know, who wrote which message. > You could enter some "master public key", scan the whole chain, and find out > all messages written by that particular participant. > 8. It would push commitments forward. Because then, it would be possible to > send some message to the "P2P mailing list network", and reveal it later. Of > course, it is not mandatory to accept commitments at all, which means, they > could be easily disabled, if they would be misused. Or we could start with no > commitments, and introduce them later if needed. > 9. Because Signet challenge can contain some multisig, or even some Taproot > address, there will be no issue with using the same password to access the > moderation panel. Also, in that case, it is possible to prove later, which > moderator accepted which message. And also, it is still possible to use some > shared key, if revealing that is not desirable, or even it is possible to > easily reach "approved by all moderators" messages, because their Schnorr > signatures could be combined. Also, any K-of-N multisig can be battle-tested > in that way. > > So, I can see two options: reusing some existing P2P network, or making a new > one, designed specifically for handling mailing list messages in a pure P2P > way. I guess we can try some existing chains first, and if there is no > promising altcoin, or if we don't want to be associated with any altcoin, > then our own Signet-like network could solve it. > ___ > 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] Lamport scheme (not signature) to economize on L1
Dear friends and colleagues, I believe this current version of the protocol and its documentation, now including a diagram answers the questions raised so far: https://github.com/Yuri-SVB/LVBsig/blob/main/docs/white_paper.md All in all, in addition to the plain transaction TXi, only 36 bytes are needed to authenticate it. The number falls to 16 in case of address (address chain) is reused, because change address coincides with Lamport-scheme pre-image. YSVB. Sent with Proton Mail secure email. On Monday, January 1st, 2024 at 11:17 AM, yuri...@pm.me wrote: > Hello, Dave, > > I'm afraid I didn't understand your objection. It would be great to have a > direct, real-time conversation with you, if you have the availability. Be my > guest to DM me for that. > > Though this is to be confirmed, I suspect my proposed scheme can be > implemented with available, existing Bitcoin infrastructure. As far as my > limited knowledge goes, the trickiest part would be to have miners agree that > pre-image of hash of a transaction, in a subsequent block is acceptable > authentication. As for the commitment, it could be implemented as ordinary > smart contracts are, and its size doesn't matter because in the normal use > case, it is not mined. > > To be clear: The only component that is mined other than addresses and the > plaintext transactions would be one hash, between 16 and 20 bytes. From the > No-Free-Lunch Principle, the cost for it is that transaction takes a few > blocks, instead of just one to be validated. > > YSVB > > Sent with Proton Mail secure email. > > > On Sunday, December 31st, 2023 at 8:33 PM, David A. Harding d...@dtrt.org > wrote: > > > > > Hi Yuri, > > > > I think it's worth noting that for transactions with an equal number of > > P2TR keypath spends (inputs) and P2TR outputs, the amount of space used > > in a transaction by the serialization of the signature itself (16 vbytes > > per input) ranges from a bit over 14% of transaction size (1-input, > > 1-output) to a bit less than 16% (10,000-in, 10,000-out; a ~1 MvB tx). > > I infer that to mean that the absolute best a signature replacement > > scheme can do is free up 16% of block space. > > > > An extra 16% of block space is significant, but the advantage of that > > savings needs to be compared to the challenge of creating a highly peer > > reviewed implementation of the new signature scheme and then convincing > > a very large number of Bitcoin users to accept it. A soft fork proposal > > that introduces new-to-Bitcoin cryptography (such as a different hash > > function) will likely need to be studied for a prolonged period by many > > experts before Bitcoin users become confident enough in it to trust > > their bitcoins to it. A hard fork proposal has the same challenges as a > > soft fork, plus likely a large delay before it can go into effect, and > > it also needs to be weighed against the much easier process it would be > > for experts and users to review a hard fork that increased block > > capacity by 16% directly. > > > > I haven't fully studied your proposal (as I understand you're working on > > an improved version), but I wanted to put my gut feeling about it into > > words to offer feedback (hopefully of the constructive kind): I think > > the savings in block space might not be worth the cost in expert review > > and user consensus building. > > > > That said, I love innovative ideas about Bitcoin and this is one I will > > remember. If you continue working on it, I very much look forward to > > seeing what you come up with. If you don't continue working on it, I > > believe you're likely to think of something else that will be just as > > exciting, if not more so. > > > > Thanks for innovating!, > > > > -Dave publickey - yurisvb@pm.me - 0x535F445D.asc Description: application/pgp-keys signature.asc Description: OpenPGP digital signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Lamport scheme (not signature) to economize on L1
Addendum: Tomorrow I'll host a Twitter Spaces on this topic: https://twitter.com/yurivillasboas/status/1743305920937963696 You are all welcome to join! YSVB Sent with Proton Mail secure email. On Friday, January 5th, 2024 at 7:02 PM, yuri...@pm.me wrote: > Dear friends and colleagues, > > I believe this current version of the protocol and its documentation, now > including a diagram answers the questions raised so far: > > https://github.com/Yuri-SVB/LVBsig/blob/main/docs/white_paper.md > > All in all, in addition to the plain transaction TXi, only 36 bytes are > needed to authenticate it. The number falls to 16 in case of address (address > chain) is reused, because change address coincides with Lamport-scheme > pre-image. > > YSVB. > > Sent with Proton Mail secure email. > > > On Monday, January 1st, 2024 at 11:17 AM, yuri...@pm.me yuri...@pm.me wrote: > > > > > Hello, Dave, > > > > I'm afraid I didn't understand your objection. It would be great to have a > > direct, real-time conversation with you, if you have the availability. Be > > my guest to DM me for that. > > > > Though this is to be confirmed, I suspect my proposed scheme can be > > implemented with available, existing Bitcoin infrastructure. As far as my > > limited knowledge goes, the trickiest part would be to have miners agree > > that pre-image of hash of a transaction, in a subsequent block is > > acceptable authentication. As for the commitment, it could be implemented > > as ordinary smart contracts are, and its size doesn't matter because in the > > normal use case, it is not mined. > > > > To be clear: The only component that is mined other than addresses and the > > plaintext transactions would be one hash, between 16 and 20 bytes. From the > > No-Free-Lunch Principle, the cost for it is that transaction takes a few > > blocks, instead of just one to be validated. > > > > YSVB > > > > Sent with Proton Mail secure email. > > > > On Sunday, December 31st, 2023 at 8:33 PM, David A. Harding d...@dtrt.org > > wrote: > > > > > Hi Yuri, > > > > > > I think it's worth noting that for transactions with an equal number of > > > P2TR keypath spends (inputs) and P2TR outputs, the amount of space used > > > in a transaction by the serialization of the signature itself (16 vbytes > > > per input) ranges from a bit over 14% of transaction size (1-input, > > > 1-output) to a bit less than 16% (10,000-in, 10,000-out; a ~1 MvB tx). > > > I infer that to mean that the absolute best a signature replacement > > > scheme can do is free up 16% of block space. > > > > > > An extra 16% of block space is significant, but the advantage of that > > > savings needs to be compared to the challenge of creating a highly peer > > > reviewed implementation of the new signature scheme and then convincing > > > a very large number of Bitcoin users to accept it. A soft fork proposal > > > that introduces new-to-Bitcoin cryptography (such as a different hash > > > function) will likely need to be studied for a prolonged period by many > > > experts before Bitcoin users become confident enough in it to trust > > > their bitcoins to it. A hard fork proposal has the same challenges as a > > > soft fork, plus likely a large delay before it can go into effect, and > > > it also needs to be weighed against the much easier process it would be > > > for experts and users to review a hard fork that increased block > > > capacity by 16% directly. > > > > > > I haven't fully studied your proposal (as I understand you're working on > > > an improved version), but I wanted to put my gut feeling about it into > > > words to offer feedback (hopefully of the constructive kind): I think > > > the savings in block space might not be worth the cost in expert review > > > and user consensus building. > > > > > > That said, I love innovative ideas about Bitcoin and this is one I will > > > remember. If you continue working on it, I very much look forward to > > > seeing what you come up with. If you don't continue working on it, I > > > believe you're likely to think of something else that will be just as > > > exciting, if not more so. > > > > > > Thanks for innovating!, > > > > > > -Dave publickey - yurisvb@pm.me - 0x535F445D.asc Description: application/pgp-keys signature.asc Description: OpenPGP digital signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
