Consider a compact PSBT based encoding for wallet descriptors

[seedhammer]

Prompted by discussions at wizardsardine/liana#539, this is a sketch for a BIP proposal for serializing wallet descriptors. I raise it here for comments and because Blockchain Commons is a recognized standards body for Bitcoin specifications. If there's enough interest, it should be fleshed out and proposed as a BIP.

A Go implementation written from scratch is here: https://github.com/seedhammer/bip-serialized-descriptors

At the high level, this is a binary and compact serialization specification for the [wallet-policies] BIP.

• Binary format, based on the [BIP174] PSBT format.
• Descriptor is in text, as described in BIPs 380-386 (+389). Like the wallet-policies BIP, keys are always by indexed reference.
• Key references uses the wallet-policies format @<key-index>.
• Miniscript is trivially supported, except pk(NAME) expressions are replaced with key indexes.

Borrowing from BIP174, the format would be

 <desc> := <magic> <global-map> <key-map>*
 <magic> := 0x64 0x65 0x73 0x63 0xFF
 <global-map> := <keypair>* 0x00
 <key-map> := <keypair>* 0x00
 <keypair> := <key> <value>
 <key> := <keylen> <keytype> <keydata>
 <value> := <valuelen> <valuedata>

Where <global-map> contains one or more of the fields:

• DESC_BIP38x_DESCRIPTOR: The descriptor itself, encoded in UTF-8 according to the BIP380 family, with the Miniscript extensions. Keys must be specified as @ according to the wallet-policies BIP. Inline keys are not allowed.
• DESC_NAME: The name of the wallet in UTF-8.
• DESC_BIRTHDATE: The wallet birthdate in blocks, encoded as a compact integer.

In future, other script formats (Simplicity?) can be added as separate field types.

The <key-map> is a list of keys, matching the indexed references from the descriptor. Each <key-map> contains one or more of the fields:

• PSBT_GLOBAL_XPUB: An extended key, encoded just like PSBTs would.
• DESC_KEY_NAME: The name of the key encoded in UTF-8.

FAQ

Why not use the Blockchain Commons [BCR-2020-010] format?

The format was recently deprecated, for good reasons: its binary format is compact but difficult to extend to support extensions to the descriptor format, such as Miniscript.

Why not use the Blockchain Commons Envelope format for descriptors?

• It relies on the CBOR encoding which is a significant complexity in a specification (more on CBOR later).
• CBOR is more compact than text, but descriptors are encoded in text and does not enjoy any of the advantages of CBOR.

The standard is being developed and as such does not have an advantage of existing use.

Why not use CBOR for encoding?

• CBOR is significantly more general, and therefore complex, than the PSBT encoding.
• CBOR is more complex and thus require more code space, which is scarce in embedded applications.
• Wallet software already include PSBT decoders for transaction processing. To be fair, most wallet software also includes some CBOR capability because of the Blockchain Commons UR standard (more on UR later).
• A specification (or BIP) should ideally be complete and self-contained, and referencing another standard (CBOR) makes implementing, debugging and ensuring interoperability harder. For an example of this complexity, CBOR is not deterministic (I believe the Blockchain Commons is working on a dCBOR proposal to fix that).
• The PSBT format is already a BIP and widely accepted. A self-contained specification based on an already widely accepted binary format increases our chances of widespread support. In particular, I'd like to see Bitcoin Core support this format.

What about QR code representation?

A straightforward encoding would be the use the Blockchain Commons [BCR-2020-005] standard for splitting the serialized descriptor into multiple QR code frames. I believe the general purpose bytes urtype is sufficient, because the magic header decreases the likelihood of misinterpretation.

Doesn't UR support rely on a CBOR implementation anyway?

It's true that the UR specification rely on CBOR for encoding data shards, but it's my understanding that the subset of CBOR required can practically be implemented ad-hoc without a full fledged CBOR library.

Some devices, such as the camera-less Coldcards, won't implement the UR encoding because they exchange serialized descriptors through higher bandwidth mediums such as SD cards, USB, or NFC.

Why not encode the descriptor itself in binary?

The BC envelope format made the same decision of encoding the descriptor in text, for good reasons:

• The descriptor language is complicated and expanding. Relying on existing standards for encoding saves a lot of complexity and duplicate specification efforts. In particular, any future descriptor extension BIPs such as Miniscript may be used immediately for this BIP, without deciding on a binary representation first.
• The major source of bloat, extended keys, are binary encoded for compactness and can be re-used multiple times in a single descriptor.

[wallet-policies] https://github.com/bitcoin/bips/blob/bb98f8017a883262e03127ab718514abf4a5e5f9/bip-wallet-policies.mediawiki
[BIP174] https://github.com/bitcoin/bips/blob/master/bip-0174.mediawiki
[BCR-2020-010] https://github.com/BlockchainCommons/Research/blob/master/papers/bcr-2020-010-output-desc.md
[BCR-2020-005] https://github.com/BlockchainCommons/Research/blob/master/papers/bcr-2020-005-ur.md

[seedhammer]

For everyone interested in joining the discussion, we'll be at the next Gordian Developer community meeting Nov. 1. to present this proposal.

[pythcoiner]

cc @bigspider

[wolfmcnally]

@seedhammer Quick note: we deprecate the use of the bytes UR type for any purpose other than testing and demonstration purposes. So we are unlikely to support any proposal that specifies it.

[wolfmcnally]

@seedhammer @ChristopherA See below for my initial response to some of the points raised above.

Why not use the Blockchain Commons Envelope format for descriptors?

• It relies on the CBOR encoding which is a significant complexity in a specification.
  • CBOR is a recognized standard for data encoding like JSON, but unlike JSON CBOR encoders are usually much smaller and therefore CBOR is better suited to embedded systems than JSON.
• CBOR is more compact than text, but descriptors are encoded in text and does not enjoy any of the advantages of CBOR.
  • This appears to also apply to the present proposal.
• The standard is being developed and as such does not have an advantage of existing use.
  • This appears to also apply to the present proposal, but dCBOR and Envelope already have IETF Internet Drafts that have been reviewed by the community and may eventually become RFCs. I would argue that this does give Envelope an advantage over the existing proposal.

Why not use CBOR for encoding?

• CBOR is significantly more general, and therefore complex, than the PSBT encoding.
  • Specific applications of CBOR do not require complex general codecs. Gordian dCBOR also requires and enforces deterministic encoding, further reducing variance in what a receiver must parse. Gordian envelopes may only add a couple bytes of overhead to any CBOR structure.
• CBOR is more complex and thus require more code space, which is scarce in embedded applications.
  • Addressed by previous point.
• Wallet software already include PSBT decoders for transaction processing. To be fair, most wallet software also includes some CBOR capability because of the Blockchain Commons UR standard (more on UR later).
  • PSBT, like the present proposal, is a bespoke format and not a common data container format. CBOR is a container format, and Envelope is a highly structured container format based on dCBOR, which adds very little overhead in size and parsing code for simple applications. Bespoke codecs for specific dCBOR/Envelope applications can be written with no more effort than the present proposal would require.
• A specification (or BIP) should ideally be complete and self-contained, and referencing another standard (CBOR) makes implementing, debugging and ensuring interoperability harder. For an example of this complexity, CBOR is not deterministic (I believe the Blockchain Commons is working on a dCBOR proposal to fix that).
  • It is rare, if not impossible, for a proposed standard to not reference other standards. PSBT is not a standard for anything but itself, and is not put forth as a platform with a future upon which further standards should be based.
• The PSBT format is already a BIP and widely accepted. A self-contained specification based on an already widely accepted binary format increases our chances of widespread support. In particular, I'd like to see Bitcoin Core support this format.
  • Addressed by previous point.

I think a major sticking point here is in thinking that representing output descriptors in dCBOR/Envelope would require highly general purpose parser/codecs. This is not true. Minimal specifications for output descriptors represented as Gordian Envelope will yield minimal, deterministic binary serializations that could be documented without any reference to CBOR or Envelope, and would be highly suitable for embedded environments. Unlike bespoke formats however, using Envelope provides a forward-looking platform that makes it easy to add support for future enhancements.

[wolfmcnally]

@seedhammer @ChristopherA I'd also like to add that our Rust implementation of Gordian Envelope also provides a lot of "feature gates" for many optional extensions like encryption, which makes it more suitable for use in resource-constrained environments. Users can turn off all the feature gates they don't use, and the Rust compiler will aggressively code strip all unneeded dependencies.

[wolfmcnally]

@seedhammer @ChristopherA
To demonstrate what I've been talking about, let's take an example of a minimal encoding for an output descriptor.

In Envelope notation, the subject is just the text of the output descriptor, and it has one assertion declaring its type:

"wpkh([55016b2f/84'/1'/2']xpub6BkiBzPzLUEo9F5n6N4CSKWzFeXdWaKGhYsVNXH8bqfbeAhdpvNeGhu2mP35cABAwDHNpHD5hmXfZcMSdpTUmAyCYnQggXkk9hwbTP9KRRB/<0;1>/*)#cf9l9nxt" [
    'isA': 'OutputDescriptor'
]

Now let's look at the envelope as a tagged CBOR structure:

d8 c8                                    # tag(200) envelope
   82                                    # array(2)
      d8 18                              # tag(24) leaf
         78 9a                           # text(154)
            77706b68... # "wpkh([55016b2f/84'/1'/2']xpub6BkiBzPzLUEo9F5n6N4CSKWzFeXdWaKGhYsVNXH8bqfbeAhdpvNeGhu2mP35cABAwDHNpHD5hmXfZcMSdpTUmAyCYnQggXkk9hwbTP9KRRB/<0;1>/*)#cf9l9nxt"
      a1                                 # map(1)
         01                              # unsigned(1) 'isA'
         1901fb                          # unsigned(507) 'outputDescriptor'

The first two bytes are CBOR tag 200, indicating this is a Gordian Envelope. This tag is now standardized, as it has been registered with IANA. This value is a constant, and can be expected by a minimal parser.

The next byte is 82 indicating a CBOR array of two elements. In this minimal encoding this value will be a constant, and can be expected by a minimal parser.

The next two bytes introduce the first element of the CBOR array, which is a CBOR tagged element tagged with (24). In this minimal encoding this value will be a constant, and can be expected by a minimal parser.

The next two bytes introduce a CBOR text string, and specify its length. The bytes that follow it are the textual representation of the output descriptor. No null terminator is needed.

The remaining bytes are the second element of the array, which is a CBOR map with one entry. The key is the integer 01 representing the known value isA (a type declaration) and the value is the 507 representing the known value OutputDescriptor. As such, this type declaration adds five bytes to the total length of the envelope, and is fixed and can be expected by a minimal parser.

So to a minimal parser, the "magic bytes" are at the beginning (envelope) and the end (output descriptor) and everything amounts to simple to parse, often invariate values.

Now to be fair: if support for hasName or note assertions is required, and the order of these assertions including the isA needs to be determined by doing SHA-256 hashes on each assertion and then sorting them. But the code to perform SHA-256 is small, and sorting an array of hashes is also quite easy in constrained environments.

[wolfmcnally]

So if output descriptors are so simple, why use Envelope to represent them?

Two reasons:

1. Adding hasName or note fields is just the tip of the iceberg about the sort of metadata that can easily be added using Gordian Envelope.
2. CBOR-encoded objects (including every envelope) play well with UR encoding and anything that can be UR-encoded can be transmitted via air gaps by QR codes using fountain codes.

[ChristopherA]

I’d like to see the keys externalized (remove xpubs and point to binary keys). I find that having notes possible on the different keys in a multisig useful, for instance maybe a nostr or signal address to contact the keyholder.

[wolfmcnally]

That's all easily doable using Envelope, but the more complex and variable the structure becomes, the more likely you'll want a full dCBOR/Envelope implementation, even if you need nothing more than the base Envelope specification with all the optional feature gates turned off.

[seedhammer]

I've implemented a strawman Go codec to keep the conversation concrete: https://github.com/seedhammer/bip-serialized-descriptors

Quick note: we deprecate the use of the bytes UR type for any purpose other than testing and demonstration purposes. So we are unlikely to support any proposal that specifies it.

Understood. Note that the the particular UR representation is outside the scope of this specification. I mentioned bytes because the format is self-identifying and as such doesn't require a UR type.

For that reason, I'm leaning towards a generic binary, file etc. UR type for the same reason that your envelopes all share the same UR type. I don't oppose a crypto-bipxxx or similar, though.

CBOR is more compact than text, but descriptors are encoded in text and does not enjoy any of the advantages of CBOR.

This appears to also apply to the present proposal.

Almost: this proposal binary encodes xpubs, as referred to in #135 (comment).

I think a major sticking point here is in thinking that representing output descriptors in dCBOR/Envelope would require highly general purpose parser/codecs. This is not true. Minimal specifications for output descriptors represented as Gordian Envelope will yield minimal, deterministic binary serializations that could be documented without any reference to CBOR or Envelope, and would be highly suitable for embedded environments.

It is not clear to me how the enveloped descriptor format is completely specified without referring to neither dCBOR/Envelope, nevermind the requirement that fields be sorted according to SHA256. Can you describe the format? You did offer a thorough example of one instance of an enveloped output descriptor, but that's not the same as specifying the format for every descriptor. The former is sufficient for encoders, but decoders need to cover every possible instance. One example where this matters: your specified minimal encoding for a two-element array (82 in dCBOR) doesn't say anything about the minimal encoding for other array sizes.

To reciprocate your efforts, I implemented most of this proposal: https://github.com/seedhammer/bip-serialized-descriptors. Note in particular how few lines the codec is, assuming you already have access to a PSBT codec. Total around 300 lines, including comments and no external dependencies.

Unlike bespoke formats however, using Envelope provides a forward-looking platform that makes it easy to add support for future enhancements.

This proposal is an existence proof that BIP-174 is extensible. Perhaps not as much as Envelopes, but enough to cover at least two important use cases (PSBTs and now descriptors) and I see no reason the BIP-174 cannot be used for most/all future binary encodings in BIPs.

A specification (or BIP) should ideally be complete and self-contained, and referencing another standard (CBOR) makes implementing, debugging and ensuring interoperability harder. For an example of this complexity, CBOR is not deterministic (I believe the Blockchain Commons is working on a dCBOR proposal to fix that).

It is rare, if not impossible, for a proposed standard to not reference other standards.

It may be rare, but that's besides the point. All things equal, wouldn't you agree that a self-contained specification is superior to a specification with external references?

PSBT is not a standard for anything but itself, and is not put forth as a platform with a future upon which further standards should be based.

This is another major sticking point. I claim that BIP-174 (PSBT) is very much a standard on at least equal footing to what other standards bodies produce.

I further claim that it is more important for widespread use to produce a BIP than to submit proposals to other standards bodies. Regardless of format, a proposal should not be declared complete until significant buy-in from the community has been attained (gauged through bitcoin mailing lists, wallet developers).

Finally, I claim that it's more important to have a simple specification than covering use cases outside of Bitcoin.

Of course, the above claims assume the Bitcoin perspective.

[jeandudey]

Hey!

I currently have been working with the PSBT format and I can't recommend it for other serialization purposes as it was designed with normal processors in mind where memory is freely available, it doesn't really suit embedded use cases as the the PSBT format is complex enough to parse and to keep in memory.

Why not use the Blockchain Commons [BCR-2020-010] format?

The format was recently deprecated, for good reasons: its binary format is compact but difficult to extend to support extensions to the descriptor format, such as Miniscript.

I think this point is not valid, CBOR was designed to be extensible and CDDL too, in fact, one can extend choices in a CBOR type by using the Socket/Plug mechanism which allows each one to extend choices, crypto-output can be adapted to that without issues IMO.

See:

• RFC 8610, Section 3.9 Socket/Plug
• draf-ietf-suit-manifest-24, Appendix A. for an example of how this is used to extend standards.

It relies on the CBOR encoding which is a significant complexity in a specification (more on CBOR later).

The CBOR format was made specifically to be small and for embedded devices, there are several implementations of CBOR out there that are very small, for example:

• NanoCBOR, it has like ~1300 lines of code for both the encoder and decoder, written in C and it is a zero copy parser, so there's no memory allocation overhead.
• TinyCBOR which is more complex than NanoCBOR yet small for microcontroller standards, also it's zero-copy and doesn't allocate.

For real world usage of NanoCBOR there is:

• https://github.com/RIOT-OS/RIOT/tree/2b9e82851b1bcf4f977cbca5bb604afde42a1385/sys/suit

Which decodes the standard mentioned before for MCU firmware upgrades.

CBOR is more compact than text, but descriptors are encoded in text and does not enjoy any of the advantages of CBOR.

I agree with this but using the CBOR representation avoids parsing the text which is more difficult to do and does not make it easy to do zero-copy parsing since one has to store decoded bytes into dynamically sized containers.

For instance, this data structure would be impossible to do if parsing from text as one has to additionally keep a separate location in memory to where to copy decoded stuff into, instead of a single one for the descriptor AST. That one reuses the buffer of the CBOR-encoded crypto-output, so basically zero-copy.

Even then I think that with CBOR it is complicated, but without it is even harder.

The PSBT format is already a BIP and widely accepted. A self-contained specification based on an already widely accepted binary format increases our chances of widespread support. In particular, I'd like to see Bitcoin Core support this format.

Yeah but PSBT is very application specific and I doubt that code that parses PSBT could be easily adapted to parse a format based on it since that code assumes PSBT is only for that purpose, it would require refactorings anyway in most code bases that handle the PSBT format.

As a side note, CBOR is also self-contained and self-describing so any application that does not speak the UR standards can decode it, this is a plus for languages like JavaScript or Python while also being small and compatible with embedded devices.

A specification (or BIP) should ideally be complete and self-contained, and referencing another standard (CBOR) makes implementing, debugging and ensuring interoperability harder. For an example of this complexity, CBOR is not deterministic (I believe the Blockchain Commons is working on a dCBOR proposal to fix that).

Nor is the PSBT format, in fact it is hard to serialize the same PSBT just after deserializing it without any modifications, there can exist N versions of a PSBT that represent the very same PSBT, and that's fine IMO since the format doesn't need it, same applies to CBOR.

Unless CBOR is used in a distributed system where all peers need to agree on how some stuff is serialized into CBOR, but that doesn't apply to descriptors.

As a side note, CBOR can be deterministic if you define your rules and the standard even recommends so:

https://www.rfc-editor.org/rfc/rfc8949.html#section-4.2

---

P.S.: I think defining custom serialization formats for trivial data structures does not help for adoption of Bitcoin and I hope that trend declines.

[seedhammer]

Why not use the Blockchain Commons [BCR-2020-010] format?
The format was recently deprecated, for good reasons: its binary format is compact but difficult to extend to support extensions to the descriptor format, such as Miniscript.

I think this point is not valid, CBOR was designed to be extensible and CDDL too, in fact, one can extend choices in a CBOR type by using the Socket/Plug mechanism which allows each one to extend choices, crypto-output can be adapted to that without issues IMO.

Maybe, but is it relevant? This proposal is an alternative to the Envelope output descriptor format that encodes the descriptor itself in text, not in CBOR. Extending the BCR-2020-010 format is another discussion.

It relies on the CBOR encoding which is a significant complexity in a specification (more on CBOR later).

The CBOR format was made specifically to be small and for embedded devices, there are several implementations of CBOR out there that are very small, for example:

* [NanoCBOR](https://github.com/bergzand/NanoCBOR), it has like ~1300 lines of code for both the encoder and decoder, written in C and it is a zero copy parser, so there's no memory allocation overhead.

* [TinyCBOR](https://github.com/intel/tinycbor) which is more complex than NanoCBOR yet small for microcontroller standards, also it's zero-copy and doesn't allocate.

For real world usage of NanoCBOR there is:

* https://github.com/RIOT-OS/RIOT/tree/2b9e82851b1bcf4f977cbca5bb604afde42a1385/sys/suit

Which decodes the standard mentioned before for MCU firmware upgrades.

Sure, but this proposal is even simpler. A codec is 300 lines from scratch, even less if your software already includes a PSBT parser.

In other words, this proposal is clearly an afternoon dependency, whereas I have yet to see specification for bcr-2023-007-envelope-output-desc that doesn't require a third party library, however small or memory light. I'd love to be proved wrong by someone specifying or implementing a parser for BCR-2023-007 from scratch in a reasonable amount of code.

This matters not only for development time and for resource constrained environments, but also for security. 300 lines are easier to review than a CBOR implementation. Don't forget that we're parsing potentially adversarial data!

CBOR is more compact than text, but descriptors are encoded in text and does not enjoy any of the advantages of CBOR.

I agree with this but using the CBOR representation avoids parsing the text which is more difficult to do and does not make it easy to do zero-copy parsing since one has to store decoded bytes into dynamically sized containers.

For instance, this data structure would be impossible to do if parsing from text as one has to additionally keep a separate location in memory to where to copy decoded stuff into, instead of a single one for the descriptor AST. That one reuses the buffer of the CBOR-encoded crypto-output, so basically zero-copy.

I believe this point is irrelevant because BCR-2023-007 is textual, see above.

The PSBT format is already a BIP and widely accepted. A self-contained specification based on an already widely accepted binary format increases our chances of widespread support. In particular, I'd like to see Bitcoin Core support this format.

Yeah but PSBT is very application specific and I doubt that code that parses PSBT could be easily adapted to parse a format based on it since that code assumes PSBT is only for that purpose, it would require refactorings anyway in most code bases that handle the PSBT format.

The strawman implementation is existence proof that the PSBT format is sufficiently general to cover output descriptors.

A specification (or BIP) should ideally be complete and self-contained, and referencing another standard (CBOR) makes implementing, debugging and ensuring interoperability harder. For an example of this complexity, CBOR is not deterministic (I believe the Blockchain Commons is working on a dCBOR proposal to fix that).

Nor is the PSBT format, in fact it is hard to serialize the same PSBT just after deserializing it without any modifications, there can exist N versions of a PSBT that represent the very same PSBT, and that's fine IMO since the format doesn't need it, same applies to CBOR.

I concede your point about determinism. I stand by my point that a self-contained specification is superior to one with references, all things being equal.

[jeandudey]

In other words, this proposal is clearly an afternoon dependency...

Software is made of dependencies of dependencies, I think this doesn't applies to today's world, creating another serialization means just verifying another implementation of something instead of using well-proven solutions.

If dependencies are an issue for you one could use GNU Guix which largely solves that issue, as a fact Bitcoin Core uses it for reproducible builds.

Would have to just review the particular CBOR implementation.

Fun fact, I doubt any true Bitcoiner has reviewed every one of the dependencies, here's how you can build a graph:

guix shell bash graphviz -- bash -c 'guix graph bitcoin-core --type=bag-emerged | dot -Tpdf -o dependencies.pdf'

I'm running it and it'll take a few hours to produce the graph from the very first dependencies, all of the compiler bootstrap chains, all of the GNU utilities, Qt, etc. up to bitcoin-core. I don't think it'll finish generating the graph this day or tomorrow.

We rely on other people's code and that's fine.

The strawman implementation is existence proof that the PSBT format is sufficiently general to cover output descriptors.

The code assumes the existence of an operating system with a malloc implementation like any modern OS, hardly reaches embedded code. I think it's best to show an example of reading the file format using C without a libc or Rust without std/alloc reading the bytes from memory directly.

These are the places where one might see the true limitations of a format like PSBT.

I believe this point is irrelevant because BCR-2023-007 is textual, see above.

I think a crypto-output-like approach is still valid though.

[seedhammer]

I believe this point is irrelevant because BCR-2023-007 is textual, see above.

I think a crypto-output-like approach is still valid though.

I don't think it's worth the decrease in size to have to invent binary representations for every (future) output descriptor feature. This is the reason I think Enveloped Descriptors chose wisely by encoding the descriptor in text.