Transactions,Andrew Stone,Technology | 29th September 2022 | Andrew Stone

Nexa’s Transaction Idem

One major difference between the Nexa blockchain and the Satoshi code (BTC, BCH, Litecoin, and others) it built upon is its use of two methods to identify transactions: the Id and the Idem.

The transaction Id is analogous to the Satoshi code transaction Id so this article will mostly focus on the Idem. In Latin, the word “Idem” means “the same”, and is pronounced E-dem. And that is the core of what the Idem is about. All transactions with the same Idem are in essence the same, even though they may contain different bits.

What do I mean by “in essence the same”? Well, the blockchain is a very carefully defined database in which a transaction has a specific role. It deletes (spends) some database entries (UTXOs in blockchain terminology) and creates new database entries. This is the only way that a transaction can affect the blockchain state. Therefore, all transactions that delete and create the same set of entries are exactly the same (from the perspective of the blockchain)!

Specifically, the transaction Idem is the double SHA256 of the serialized transaction without signature scripts. And the transaction Id includes the both Idem and the signature scripts – its the double SHA256 of the Idem concatenated to the double SHA256 of the serialized signature scripts.

The transaction Id is used in the block merkle tree and in networking code, while the Idem is used by transactions to identify which UTXOs are being spent.

This offers the following properties:

  1. Preservation of the chain of signatures
  2. Ability to sign child transactions before the parent
  3. Malleability Attack resistance
  4. Merkle proofs-of-inclusion for the transaction either by Id or Idem

Preservation of the chain of signatures

Since transaction inputs now contain the idem, they do not commit to the exact parent transaction. They skip the signatures. But the blocks do commit to signatures. This means that the chain of signatures can still be validated all the way back to the coinbase (currency creation) transactions.

And that entity can provide merkle proofs-of-inclusion for all ancestor transactions to an entity that is not storing the entire blockchain, including and proving the exact signatures used.

To provide a full proof of a transaction’s validity, Satoshi-style transactions have the same data requirements. Yes, one can verify the chain of signatures without the full merkle proofs-of-inclusion (which one cannot do with Nexa’s Idem-style transactions). But doing that is not enough – actually it’s such a glaring security problem it's arguably better that this mistake is impossible in Nexa. The problem is that any attacker could easily (without significant compute resources) create a separate (not included in the blockchain) history for a fake transaction. If a verifier does not validate that these transactions are actually committed in the blockchain, the verifier will accept these non-existent parent transactions.

Ability to Sign Child Transactions First

Since the transaction Id covers the signatures, participants in Satoshi-style blockchains cannot sign child transactions before signing parent transactions. However the Idem does not cover signatures, and a child transaction refers to its parent by Idem. This allows the child transaction to be fully constructed and signed before the parent is signed.

Malleability Attack Resistance: A Bit Of History

In 2012 the first major Bitcoin exchange failed (MtGox), citing “transaction malleability” as the reason funds were lost. Although this reason may not be the full story behind the failure of MtGox, transaction malleability is undeniably a problem. In essence, the transaction malleability attack proceeds as follows:

  1. Withdraw some funds in BTC. A transaction is created by the exchange.
  2. Change some bits in the withdrawal transaction, without affecting its validity or its effect on the blockchain state. This will change the transaction id.
  3. Get your “malleated” transaction confirmed rather than the original transaction.
  4. Go back to the exchange and claim that the original transaction never confirmed, asking that your account be credited.
  5. If the exchange is unaware of transaction malleability, it might look up the transaction by id, discover that it in fact has not confirmed, and credit your account. At this point you can repeat the attack to steal more money.

Note that steps 4 and 5 might even happen automatically in the code, depending on how the exchange is programmed.

Insanity?

You might ask “how is this even POSSIBLE?” Why are there bits in a transaction that don’t affect blockchain state, aren’t those just waste? And why isn’t the entire transaction signed, so if someone modifies the transaction the signature and therefore the modified transaction is invalid?

Well, first of all, recognise that the bytes in the signatures themselves can’t be signed… that would be an impossible recursion. And that those bytes all evaluate to produce one bit of essential information – whether the transaction is valid or invalid. But what if there exist different signature bytes that when evaluated produce the same single “valid” bit? Any of these signature bytes could therefore be used, producing different versions (“malleations”) of the same transaction.

One unfortunate property of ECDSA signatures is that anyone can create another valid signature (over the same data) from an existing one. Oops, an attacker can use this property to malleate the transaction!

And remember that the “signature” in Satoshi-derived blockchains is actually a script, not a raw ECDSA signature. It would be very hard to figure out which part of that “satisfier” script (it “satisfies” the spending constraints put on the UTXO by the “constraint” script) is the ECDSA signature, verses other data. So when a transaction is signed, the entire “satisfier” script is ignored.

This means that a simple malleability attack can be executed if the script is (say) pushing a number onto the stack. Push the same number, with a preceding 0 (because, for example 1 and 01 and 001 are all the same number).

There are a large variety of such “malleability attacks”, and in the aftermath of MtGox, the Bitcoin community identified most if not all of them and added rules to the system (for example, all numbers must be encoded in a certain way – no preceding zeros allowed) to prevent them. They were aided in this effort by a parallel effort to “lock down” the scripts in the protocol to just a few options, effectively removing scripts from Bitcoin.

This was necessary because, even with all of their efforts, it is simple to craft a transaction that can be malleated: create a constraint script that pops a number off of the stack but does not actually use it (and then presumably executes other constraints). The satisfier script can then push any value in that position. Note that the exchange attack is prevented even with this issue, because the exchange is using its own addresses. But as we move to more and more complex smart contracts, it will be easy for developers to accidentally add malleability opportunities into their code.

However, there’s a simple solution – use a transaction identifier that does not include satisfier script bits. This is the Nexa Transaction Idem

Merkle Proofs-Of-Inclusion

A Merkle Proof underlies the “Simplified Payment Verification” (SPV) and “Block pruning” technology described in the Bitcoin white paper. Since the transaction id is stored in the block Merkle Tree, creating Merkle Proofs for transactions referenced by Id happens just like in Bitcoin/Bitcoin Cash.

But the transaction Id is generated differently in Nexa, as I described above. Rather than being the hash of the transaction bytes, it’s the hash of the Idem and the hash of the signatures. Visually, then, you can think of the Idem as a “basement” level below the normal Merkle Proof. This means that a Merkle Proof of Idem is just the Id’s Merkle Proof plus the signatures hash.

Fin

Although this strategy is unique to Nexa, it’s not a reach to say that there is a general agreement that the properties described above are desirable. For example, this is the main purpose of Bitcoin’s controversial-as-a-scaling-solution “segregated witness” feature. Segregated Witness (or “segwit” for short) is a cryptographer’s way of saying “separate signatures”, and segwit accomplishes this by basically putting a special “no-op” in the normal script slot and enforcing the rule that when miners see this special no-op they look in a separate extension block for the actual signature script. But carrying this “cruft” around is inefficient on the blockchain and does not actually fully solve many of the above problems because using segwit is optional. But that is the price of perfect backwards compatibility. Since Nexa is not a fork – it starts its own genesis block – it was a pretty easy decision to go with a clean solution to these problems.