CHIP 2021-01 PMv3: Version 3 Transaction Format

Hashed Witnesses vs. MalFix, SIGHASH_NOINPUT, SegWit, etc.

The hashed witnesses half of this proposal could also be solved by any transaction malleability solution which removes witness data from the parent transaction’s outpoint transaction hash.

If there was any demand for a full transaction malleability solution, we might want to consider implementing that instead of hashed witnesses.

I personally don’t see the need for an additional “malleability fix”, so I prefer the hashed witnesses solution:

  • hashed witnesses avoid creating two different TXID formats (e.g. TXID and WTXID) – this keeps the system as simple as possible, ensuring the competing ID formats never confuse user experiences, and ensuring consistency between e.g. the TXID in SPV proofs and the TXID referenced in contracts.
  • hashed witnesses avoid the need for an additional TXID index – nodes don’t need to maintain an index to match the two TXID formats (with and without witness data) even at the P2P layer.
  • hashed witnesses don’t affect block merkle root construction or any system components other than v3 transactions (depending on the solution – malleability fixes can be more disruptive)

Unless someone can point out advantages in implementing a malleability solution instead, I prefer that this problem be solved with the hashed witnesses solution. I started a thread to collect discussion if anyone is interested:

Hashed Witnesses vs. TXID Merkle Trees

Just to document another possible alternative to hashed witnesses: a new transaction version could also use a new merkle tree construction for its TXID.

Instead of hashing the full, serialized transaction, each major component of the transaction could be hashed, allowing child transactions to only introspect e.g. a particular output during a proof. (So in a sense, this would be hashed witnesses + hashed everything else, in a tree.)

While this may save a few bytes for contracts which introspect a parent transaction, it would require significantly more hashing per transaction. And even for a relatively small type of tree, e.g. hash256([version][input merkle tree][output merkle tree][locktime]), the small additional savings would probably not be worth it. (Proofs would still require 32 bytes * node count; a minimal 330 byte proof could maybe be reduced to ~128 bytes, but at the cost of requiring possibly 10x as much hashing when computing TXIDs.)

I think hashed witnesses are a much better choice, only costing one additional hash for any inputs which use them (and users pay for the extra bytes, discouraging unnecessary use).

For users just seeing this thread: I’m hoping to get other commonly asked questions documented in an FAQ soon. I’m happy to answer any questions here or in the new CashToken Devs Telegram group.

Group is essentially having a new kind of cash bill with a 546 sats BCH anti-fraud strip attached to each bill (UTXO) which can later be reclaimed if the token becomes useless, even without melt authority - by consolidating all your tokens into one UTXO and reclaiming the anti-fraud strips from all other inputs. Since I realized this simple truth, I’m having trouble sleeping, I feel the need to write, to make noise, to let everyone know. Writing this had me up all night. Maybe you will cringe at me “selling” it like that, but I just want everyone to reach the “aha!” moment with this. We all need to want this. Maybe you will feel annoyed that I’m making noise. Well, that’s a small price to pay for what we could be getting. The missed opportunity cost of not having it due to ABC has already been huge. We could have owned USDT market.

It’s really a small protocol change. The consensus rules are simple and conceptually easy. Using those rules in a meaningful way from a wallet dev. perspective could be seen as large but they don’t have to support everything. Basic token transactions are as simple as any BCH transaction, it only needs to have the OP_GROUP quantity balance in addition to the BCH balance. Token mint/melt/authorize is as simple as including an extra UTXO in the inputs, which affects the balancing rule. Authority is just another balance to check. Token genesis is as simple as creating a single UTXO.

Building blocks are simple, that’s what Group is. What you build with them may or may not need to be complicated, but the blocks themselves aren’t complicated, they couldn’t be any simpler.

They aren’t, and that’s the great news! Since every Group UTXO is also a BCH UTXO you can do with those whatever you want from any smart contract platform we may roll out. I just disagree on the priorities when it comes to deployment. Ok, I’m a nobody, but please hear me out.

Group should come first, as soon as possible, and as a minimum viable (but future proof) product: mint/melt/baton/maybe subgroup because people also need time to work on wallet software once it’s out. We have time, but we have to work together. Have group first, and think about how you could use them from whatever smart contract platform you want ie work with the assumption that you will have Group tokens to use. That way we can get the synergy!

Everybody already has smart contracts that look like cash, nobody has actual hard cash that smart contracts can use, yet.

Cash is not just one currency.

Having them available before any smart contract platform will mean that anyone wanting tokens will prefer it for simple token usage, for which there’s lots of demand as we have seen. And later when you roll out smart contracts, you should be operate on those tokens exactly the same like you operate on BCH. Only exotic tokens should require being implemented by the contract. For a simple token, miner doesn’t need you to tell them that 1+1=2, they ought to know that already, and check for that in C++, the same place where they check the BCH “contract”.

Everyone is thinking in smart contracts, so they can’t see the simple truth: smart contracts need smartly designed electronic cash system. That’s what Group is.

@bitcoincashautist would you mind moving this comment to the Group Tokens topic? It would be valuable to keep that discussion in one place.

I don’t need further convincing: token support is valuable. :+1: I think that adding built-in support to the protocol could eventually make certain constructions slightly more efficient.

My concern remains that committing to a large protocol expansion like Group Tokens is a one-way change, and getting it correct in “one shot” is much less likely than if we allow the ecosystem to first experiment with tokens in “userland” before we lock ourselves to one particular token standard. I wrote more detail in that topic – if you’re interested, I would appreciate answers there.

For this topic:

Have you gotten to review CashTokens & PMv3 yet? Please don’t let the script stuff scare you, there’s no complex math: the “parent introspection” is just checking that two hashes are equal, and the “inductive proof” is just checking that two scripts are equal.

If contracts can efficiently inspect the contents of their parent transactions, wallet developers can design all kinds of new contracts without waiting for “permission” or BCH protocol changes – including token implementations like CashTokens.

2 Likes

Not only that, it would also require all parties that now can just hash a bytearray to introspect and understand the transaction.

Thanks for getting back on this and explaining a bit more about this on the dev-chat yesterday.

As we talked about here I’ll write my thoughts on the topic of the var ints.

Here the arguments for changing the transaction formats parts which encode numbers:

  • The current transaction format has 3 different ways to encode integers. You name 4 as you include the one inside of the script as well.
    The idea to replace all with one is attractive from a purely architectural point of view.
  • Bitcoin Script has severe problems with the var-width encoding when doing covenants.
  • Variable-width encoding gains in tx size are a couple of percent.
  • Variable width means that the ‘amount’ field can grow beyond the 64-bit limit it has today.
    Caveat is that the 21 million limit we have today only takes 6½ bytes. We could multiply it with 8196 without needing more bytes.

So, really the main reason you suggested this is because Bitcoin Script doesn’t understand one of the 3 used integer formats. The var-int. And your suggestion is for the rest of the transaction to use the integer encoding that the scritping VM already is familiar with.

So, I have a counter suggestion. Two actually.

Use a more common encoding scheme.

My thinking here is that interpreting transactions, at least at the basic level, is going to be something that a LOT of software libraries will do. On the other hand the amount of places that implement a VM will be much lower. Probably only the full nodes and some specialized software.

Based on this, I vastly prefer to solve your basic problem of Bitcoin Script not understanding the format by introducing two opcodes. One for each of the conversion directions and picking a format that is actually much more standardized. See Variable-width encoding - Wikipedia. Think UTF-8 as an example of this.

Now, if you are going to break 100% of all transaction parsing code-bases, I think it makes a lot of sense to include a little upgrade that makes future transaction format changes much easier. This is based on reseach I did some years ago in the project called “Flextrans”.

The basic idea is that each field becomes a “name / format / value” type. This allows inserting new data in the transaction at a later version without forcing everyone to AGAIN rewrite the entire transaction parsing. Just like adding a new html tag to the standard doesn’t require you to update the old parsers.

This thinking got me to suggestion two:

Use the current size-formats.

So, we can go fancy and require everyone to rewrite the format, while also requiring two new opcodes to do the conversion between tx-numbers and script-vm-numbers.
But, hang on. If you need those opcodes anyway, then why would we change the numbering format?

I liked (and still do) the FlexTrans approach. But the gains are small and the change intrusive.

I’d vastly prefer to not have a different numbering format and simply add two opcodes for the conversion.

2 Likes

In my deep dive into the protocol the disparity between the screams for restricting transaction sizes or growth of data and then how so many single digit numbers are expressed across multiple bytes has always confused me a bit. :slight_smile:

Your example of UTF-8’s encoding model is a good one. The Smalltalk community had something called State Replication Protocol (SRP) which was a way of streaming objects and entire networks of objects across different dialects of SmallTalk and even completely disparate hardware environments.

Similar to UTF-8, the high bit of a byte (octet as they called it - the single primitive in SRP) determines whether or not the value you’re dealing with continues on to the next octet or finishes there. Ultimately you get 7 bits of data for every octet. Any value under 128 is represented in a single byte. There’s also no limit to how large a number you can represent and no endian considerations to confuse.

Were I to make a new VM for a cryptoledger to execute on, I’d make SRP the native representation of all data. It naturally compresses the size of most data by eliminating wasteful fixed sizes above 8 bits. A type like this in BCH could be really helpful in eliminating wasteful padded bytes.

Thank you @tom for the detailed review! And thanks @proteusguy for digging into the spec too! I want to continue with some more research on the encoding options before I make changes to the spec and/or respond to specific points. (I’m going to be mostly offline from March 5-15, but I’m hoping to focus on this again at the end of March. Also posted in CashTokens Devs.)

For anyone interested in a high-level summary of this topic, I recently spoke with @GeorgeDonnelly about hashed witnesses, PMv3, CashTokens, prediction markets, synthetic assets, decentralized exchanges, BCH scaling considerations, comparisons with ETH, and more:

2 Likes

I think PMv3 is a great proposal. It’s minimal, powerful and backwards compatible. :clap:

It did take me several days to wrap my head around it, and I thought it might to useful to explain where I got confused along the way …

To start with it’s the first time I’ve seen the term witness used in context of Bitcoin Cash. We already have the terms input script, scriptSig, redeemScript and unlocking script, so I wasn’t sure why the new term. Then to make matters worse I read “hashed witness” to mean “the hash of the witness” as opposed to “the full witness which is referenced elsewhere by its hash”. I spent ages trying to understand why you’d optionally append a hash at the end of the transaction :man_facepalming:. This led me further astray as I progressed through the doc: “If the parent transaction chose to provide a hash”… my interpretation: oh that must be the optional hash at the end of the transaction.

The term Hashed Unlocking Script would still have confused me here. Perhaps Detached Input Script, Detached Unlocking Bytecode or just Detached Script / Detached Bytecode would have been clearer. Then you could replace “Optional Hashing of Witness Data” with “Optional Detachment of Input Scripts”.

In the rationale section I found it useful to think of this change as enabling provenance (restrictions on ancestors) as opposed to covenants (restriction on descendants). A simple example of provenance would be a proof that “my parent has the same redeem script as me”. This can be translated to “my grandparent pays the same P2SH address as my parent”. This can be proved as follows:

  1. include both the parent and the grandparent transaction in the input script (in front of the redeem script)
  2. in the redeem script, inspect them and verify they have the matching output scripts
  3. in the redeem script, verify the embedded parent by comparing its hash to an outpoint hash in the current transaction
  4. in the redeem script, verify the embedded grandparent by comparing its hash to an outpoint in the parent
  5. To avoid infinite growth, embed truncated transactions which are sufficient to inspect their output scripts (in step 2) and calculate their hashes (in step 3 and 4) .

Side note: I use the term redeem script because locking script is ambiguous. It could refer to the redeem script (as I think it does in Bitauth IDE) or it could refer to the scriptPubkey. I might be a bit confused here and would be happy to be corrected. Also while on terminology I would like to suggest that there is no such thing as parent introspection, only parent inspection.

In the scheme above, the wallet which constructs the transaction is responsible for obtaining the raw parent and grandparent transactions so that they can be embedded. Nothing in the virtual machine allows inspecting the parent or grandparent transactions. But that’s not what I thought at first. Why? The citation of CashTokens as an example in the Medium article is an example of “Proof by Induction” but is not referenced in that section, it’s referenced under “Fixed Size Inductive Proofs” so I was looking to find some of the answers about PMv3 there. What I found was new opcodes, so I thought that these were parent inspection opcodes, but no mention of opcodes in the PMv3 spec :thinking:. Eventually I realised they were introspection opcodes related to TxInt and were not part of PMv3, and that fixed size inductive proofs don’t need parent inspection opcodes (although they would certainly be one solution).

Basically I was completely confused due to lack of knowledge on the subject matter. Once I cleared up all of the above, the penny dropped and I had the eureka moment. All down to my lack background, and I’m only brain-dumping my confusion here in the hopes it will help others at my level get there faster. Because wow, it’s awesome! Well done on thinking this up.

2 Likes

I can’t see how Hashed Witnesses affect signing serialization, so I’m wondering if a transaction could be malleated by moving a witnesses from its usual location in the input to hashed witnesses section?

1 Like

Thanks for the detailed walkthrough @rnbrady, this is really helpful!

I’ll try to revise the spec to make those areas clearer. And that step-by-step summary probably needs to be included too.

Also agree the terminology needs work – “detached” could be a good option, I’ll explore that when I working on incorporating everything else. (And thanks for the catch on “parent introspection” → “parent inspection”, I can’t unsee it now. :man_facepalming:)

Ah, you’re right! As specified, there’s a third-party malleability vector. Not sure if I have a solid answer yet. It’s just one bit of data we need to commit to for each signature (either true or false), so it’s a good candidate for a sighash/type flag. That will definitely need to be in the spec, thanks.

1 Like

Just an update for those following this topic: I’m continuing to work on a large decentralized BCH application as a more full-featured example. It’s a “two-way-bridge” covenant for a prediction market with support for millions of shareholders, an on-chain continuous IPO, and a quarterly BCH withdrawal process (which uses a Hivemind-like voting/commitment system among shareholders).

If you’re curious, you can get a sense for the plan in the video above and in the BCH Prediction Markets working group on Telegram.

I think a large, real-world example will be valuable for evaluating PMv3 and several of the other VM-related proposals. There are several dependencies I’ll need to iron out, so I’ll also release that tooling over the next few months as I’m working on the larger goal.

3 Likes

You know, I think another discussion made this finally “click” with me just now!

While pondering this, I realized that CashTokens is exactly where you’d arrive at if you want to solve those problems I describe! Let me see if I got it right:

  1. You implement all CashToken interfaces in the actual contract, hash it, and it becomes the genesis. Nobody knows it’s a CashToken genesis because they only see the P2SH hash in the UTXO at this point and it could be any contract. Only those with whom the author shared the contract via a side-channel could know.
  2. You then make another TX spending it, where the full contract is written to the blockchain in the input script and revealed to the world.
  3. Through a covenant, you enforce the outputs to carry that same token contract, and it can be hash-compressed in the following TXes.
  4. The new P2SH hash hashes the previous hash+token contract, that’s why it’s always different but that only proves the input script == output script, right?
  5. The HashedWitness is then needed to prove that input script == previous TX output script
  6. By induction, any CashToken output can then prove its lineage back to genesis
  7. Anyone can verify that he’s got a token from just the receiving TX and the contract. I’m unsure where he obtains the contract, from the genesis TX? In all TXes that follow it’s compressed into a hash yeah?

Script stuff still scares me but the nice thing is: I don’t need to understand it to understand how CashTokens work!

One detail, where do you store the token state? It must live outside the part that’s enforced to be the same in this covenant chain. So I guess it’s somewhere in the input script and that part doesn’t need to satisfy the in==out but must satisfy CashToken semantics which are verified with the fixed part, something like that yeah?

Hey everyone, just wanted to share an update on PMv3:

I’ve spent a lot of time testing these ideas over the past few months, and I stumbled upon a modification to the PMv3 draft that both 1) fixes a malleability vector and 2) opens a path for signature aggregation.

Background

In the first draft of PMv3, I had originally discounted 3rd-party malleability as a significant problem. In the Bitcoin Cash world, we have both covenants and reasonably secure zero-confirmation transactions: malleability is at most an inconvenience. (We’re not trying to migrate most user activity onto chains of signature-less transactions.) However, when @rnbrady identified the arbitrary detaching/re-attaching above, I realized malleability needs to be directly addressed for detached proofs (formerly “Hashed Witness”), since 3rd parties could actually disrupt important activity (beyond just fiddling with the TXID before confirmation).

In working on solutions, I spent a lot of time thinking about optimizing contracts, covenants, and transactions in general. I realized there are several closely related problems that an ideal solution should cover:

  • Malleability makes contracts less efficient and harder to validate – most non-trivial contracts must carefully validate all unlocking bytecode data to prevent vulnerabilities introduced by malleation, and this validation both bloats the contract and makes it harder to review for security. (For example, most covenants which use OP_SPLIT are vulnerable to a sort of “padding” attack which is not intuitive to first-time contract authors.)

  • The primary blocker to deduplication in transactions is unlocking bytecode malleability – because unlocking bytecode typically contains signatures (and signatures can’t sign themselves), unlocking bytecode is excluded from transaction signing serialization (“sighash”) algorithms. This is also the reason why unlocking bytecode must contain only push operations – the result of any non-push-including unlocking bytecode is a “viable malleation” for that unlocking bytecode. But if unlocking bytecode is signed, transaction introspection operations offer an opportunity to further reduce transaction sizes via deduplication. In a sense, if non-push operations could be used in unlocking bytecode, transactions would effectively have safe, efficient, zero-cost decompression via introspection opcodes.

  • Signature aggregation could save >20% of network bandwidth/storage – we know signature aggregation could save a lot of space and possibly improve transaction validation performance, but there’s no good place to put signatures which are shared between inputs. While we don’t want to bloat PMv3 with signature aggregation, a good v3 transaction format should not ignore this problem.

There are several possible solutions for each of these, but there is one particular solution I think is very elegant – it’s now specified in the CHIP:

TL;DR:

  • “Hashed Witnesses” have been renamed to Detached Proofs.

  • Detached Signatures are now separated from Detached Proofs, and they both comprehensively solve third-party malleability and enable signature aggregation (some immediately, some via a future sighash upgrade like the one proposed by Chris Pacia).

  • The PMv3 specification is now a proper CHIP (CasH Improvement Proposal): CHIP-2021-01-PMv3, and includes a lot more supporting detail outside of just the technical specification.

I’ve incorporated the answers to many of the questions from this thread, so thank you again to everyone who has contributed here.

I’d appreciate any feedback, reviews, or questions you have, either in this thread or in the GitHub issues. Thanks!

2 Likes

Ah, sorry to keep you waiting for an answer here – your numbered steps are very close – maybe Richard’s summary will help to make 4 through 7 clearer:

In the latest CHIP revision, I’ve tried to make things a bit clearer too, but I may try to add an appendix of sorts to walk through this particular “cross-contract interface” in detail.

Yes! Each tokens’ “genesis” transaction hash It’s stored in the top-level “corporation” covenant, which holds the full set in a merkle tree. So CashTokens can be moved around independently, then eventually checked-back-in to the top-level covenant. If you haven’t read it yet, see the description in the CashTokens demo.

That may help to get a sense for why detached proofs are so useful – they allow contract designers to build interfaces between different contracts (without resorting to the “global state” model of systems like Ethereum).

In the case of CashTokens, I’ve written a simple top-level covenant to keep track of 4, homogenous child “token” covenants. But this same strategy is useful for breaking even very large contracts up into smaller subcontracts.

In general, with PMv3 we can implement new token schemes and other high-level contract protocols entirely at the wallet/application layer, without network-wide upgrades or other coordination.

1 Like

Wow, this addresses so many of my blocking questions that I will be able to give another go understanding what Jason created. Thanks so much Richard!

2 Likes

@bitjson looking at the chip fresh after talking yesterday, there is one thing I notice that I didn’t mention before - I think a contrast exercise would be helpful for both high level general understanding and high level technical understanding. What I mean is taking a contract or use case and then showing where the dividing line is: Currently we can only do X. With pmv3 then Y becomes possible. The CHIP as I read it now basically skips straight to Y so it is harder to understand the scope of the gain.

1 Like

Good idea, thanks! I’m just now realizing that this revision doesn’t even link to the CashToken demo anymore.

I’ll work on adding that appendix directly to the spec. Probably want 2 examples:

  • basic parent transaction inspection - the covenant checks that it’s been given an un-hashed copy of a parent transaction for one of its inputs (validated by comparing the hash with an outpoint TX hash), then inspects some simple parent property like transaction version.
  • inductive proof covenants - the covenant inspects two transactions back to confirm that its grandparent used the expected covenant and its parent spent that covenant successfully, proving that the grandparent either is or descends from an original “mint” transaction of the same covenant. (This one is what @rnbrady outlines above.)

As a followup and to make things more concrete I have the following suggestion for your proposal.

I would like to split the proposal into two parts with the aim to simplify activation and to make sure that we have a smaller change that I believe can reach consensus next May.
The actual changes in the transaction format would then become this;

  • 2022-05. Transaction v3 introduced, where needed the input-script is replaced with a 32-byte hash and appended to the transaction is the list of detached proofs.
    When it comes to the transaction format, this is the only change. This actually does unlock your many improvements and inductive proofs. It allows Script to look backwards in time. It enables tokens and it enables most of your cool examples scripts. Other scripting improvements are a separate CHIP.

  • 2023: Transaction v4 introduced for variable-int sizes and various other ideas (tbd).
    Variable int sizes is one of the ideas you separately came up with which was previously part of FlexTrans (BIP 134), there were some other neat ideas that would be useful to combine in such a transaction format change.

The direct result of seperating your one CHIP is that parsers that read current (v2) style transactions will very likely not need to be modified to accept v3 transactions. Afterall, you just add some more data to the end. Even TXID calculation is going to be unchanged.
This is going to make deployment much simpler and since the May 2022 upgrade already has a large number of proposals I think it makes sense to keep it simple.

Changing the integer-format (the var-int idea) in transactions is simply a much more invasive change, 100% of the existing transaction-parsing code will need to get support that and for that it really makes sense to wait until after Restrict Transaction Version has activated which is specifically meant to make this kind of deployments simpler. Hence the suggestion to push it forward.

So, the separation of those more invasive transaction changes out of the detached signature change would be nice to move to the upgrade of 2023 to give ourselves as well as the wider ecosystem plenty of time to get it right.