0015 XLS-15d: Concise Transaction Identifier

[RichardAH]

Change Log

This standard was amended on 25th March 2021:

XLS15.1

• Add an optional 7 bit control byte to the most significant byte position.
• Control byte may be absent in which case assumed to be 0x00 for backwards compatibility.
• Credit for these changes to @nbougalis

Current Identifiers

Transactions in the XRPL ecosystem are identified using the namespace-biased SHA512-half of their canonical byte-wise serialisation [1] whether or not the transaction has been submitted to consensus.

Ledgers are also identified by hashes. [2] However provided there is a human consensus about validation (sufficient UNL overlap) ledgers may instead be identified by their 4 byte sequence number. [3]

Transactions are recorded in the protocol-defined canonical order within each ledger. [4] This ordering means each transaction has a sequence number within the ledger. This offset is present in the transaction metadata as TransactionIndex.[5]

It may be useful in a range of applications to be able to uniquely identify a transaction by the point at which it was validated rather than by its explicit contents. Thus for an unvalidated (unsubmitted or locally rejected) transaction this type of identifier would not apply.

New Identifier: Concise Transaction Identifier

At time of the publication we assume for the foreseeable future that there will not be more than 65535 transactions in a given ledger. Therefore we can uniquely identify a txn within a ledger with a 2 byte integer, and we can uniquely identify the ledger by its 4 byte sequence number. Thus a 6 byte number uniquely identifies a validated transaction.

To prevent transcription errors (and to provide some validation for the contents) the first hex nibble of the ledger's canonical hash and the first hex nibble of the transaction's canonical hash are included in byte position 0, bringing the total number of bytes to 7. This is referred to a the checksum byte.

To future-proof this format an additional, optional, 7 bit control byte may be prepended to these 7 bytes. If this control byte is absent then it is assumed to be 0x00 which is referred to as the simple case. This is a change introduced in XLS15.1, and is strictly backwards compatible with existing CTIs.

The control byte (if set) allows the CTI to identify a transaction in:

• A different network (other than XRPL mainnet)
• With a double-wide TransactionIndex
• With a double-wide LedgerSequence
• Or any combination of these

In the simple case the CTI fits neatly and unambiguously in a positive signed 64 bit integer. In the advanced case, depending on which options are selected a big number may be required to store and process the CTI.

CTI Format — Simple Case

Must be handled by all implementations.

Byte/s	Field
0	<first four bits of ledger hash> <first four bits of transaction hash>
1-3	<16 bit TransactionIndex>
3-7	<32 bit LedgerSequence>

CTI Format — Advanced Case

Required for implementations that need to handle non-mainnet transactions or for "fully future-proofed implementations", otherwise optional.

Byte/s	Field
0	<reserved 00> <T double-wide txn bit> <L double-wide lgr bit> <four bits of network id>
1	<first four bits of ledger hash> <first four bits of transaction hash>

• Byte 0 is the control byte and may be absent which gracefully degrades into the simple case above.
• Most significant bit of the control byte is always 0 such that most CTIs can be encoded as a positively signed int64.
• The next most significant bit is reserved for future use and must also be zero.
• The T double-wide txn bit, when 1, doubles the size of the TransactionIndex field.
• The L double-wide lgr bit, when 1, doubles the size of the LedgerSequence field.
• Network ID is an unsigned 4 bit integer corresponding to a network identified in the range 0-15. A table of assigned values appears below.

Taken together the two double-wide bits inform the parsing application how to proceed:

Case 1: Normal Field Sizes TL = 00

Byte/s	Field
2-4	<16 bit TransactionIndex>
4-8	<32 bit LedgerSequence>

Case 2: Double wide LedgerSequence TL = 01

Byte/s	Field
2-4	<16 bit TransactionIndex>
4-12	<64 bit LedgerSequence>

Case 3: Double-wide TransactionIndex TL = 10

Byte/s	Field
2-6	<32 bit TransactionIndex>
6-10	<32 bit LedgerSequence>

Case 4: Double-wide TransactionIndex and LedgerSequence TL = 11

Byte/s	Field
2-6	<32 bit TransactionIndex>
6-14	<64 bit LedgerSequence>

Network IDs

Number	Network
0	XRPL mainnet
1	XRPL testnet
2	XRPL devnet
3	XRPL-Labs Public Hooks Testnet
4..15	Reserved for future use

Canonical Presentation

To prevent copy-paste errors and non-canonical CTIs, presentation of CTIs to end users must be in decimal without leading zeros. The only allowable characters in a presented CTI are [0-9].

In the case of an advanced CTI the smallest possible way to describe the transaction is always the Canonical CTI. Thus if double-wide bits are set but the high bytes of those fields are 0x00 then this is a non-canonical and therefore an invalid CTI. Any implementation that handles advanced case CTIs must identify this.

Examples—Simple Case

This randomly selected transaction: 1C0FA22BBF5D0A8A7A105EB7D0AD7A2532863AA48584493D4BC45741AEDC4826

• Has a transaction index of 25
• Resides in ledger 62084722
• The transaction hash's first nibble is 1
• The ledger hash's first nibble is F
  Thus this transaction in CTI format encodes to
• CTI: 67835576823535218
• Hex: F1001903B35672
• URI: xrpl://cti/67835576823535218

Another randomly selected transaction AE1C4AD620251CA97C320052A5B9755CD002B5FBDBECC9A49F088FD58B71A44E

• Has a transaction index of 9
• Resides in ledger 62090589
• CTI: 43347185130237277
  You can resolve these CTIs right now: cti-resolver

CTI Reference Implementations—Simple Case

In C:

int64_t
cti_encode(
        uint8_t* txn_hash,
        uint16_t txn_index,
        uint8_t* ledger_hash,
        uint32_t ledger_index)
{
    uint64_t cti = (((ledger_hash[0]>>4U) & 0xFU)<<4U) + ((txn_hash[0]>>4U) & 0xFU); // these are the 8 check bits
    cti <<= 16; // shift left 2 bytes to make space for the transaction index
    cti += txn_index;
    cti <<= 32; // shift left 4 bytes to make space for the ledger sequence number
    cti += ledger_index;
    return (int64_t)cti;
}

uint8_t
cti_is_simple(
        int64_t cti)
{
    return (cti >>56U) == 0;
}

uint16_t
cti_transaction_index(
        int64_t cti)
{
    return (cti >> 32U) & 0xFFFFU;
}

uint32_t
cti_ledger_index(
        int64_t cti)
{
    return (cti & 0xFFFFFFFFUL);
}

uint8_t
cti_ledger_check(
        int64_t cti)
{
    return (cti >> 52) & 0xFU;
}

uint8_t
cti_transaction_check(
        int64_t cti)
{
    return (cti >> 48) & 0xFU;
}

In JS:

function
cti_encode(
    txn_hash /* hex string */,
    txn_index,
    ledger_hash /* hex string */, 
    ledger_index)
{
    let ledger_check = BigInt(parseInt(ledger_hash.slice(0,1), 16));
    let txn_check = BigInt(parseInt(txn_hash.slice(0,1), 16));
    let cti = (ledger_check << 4n) + txn_check;
    cti <<= 16n;
    cti += BigInt(txn_index);
    cti <<= 32n;
    cti += BigInt(ledger_index);
    return cti;
}

function
cti_is_simple(
    cti)
{
    return (cti >> 56n) == 0;
}

function
cti_transaction_index(
    cti)
{
    return (cti >> 32n) & 0xFFFFn;
}

function
cti_ledger_index(
    cti)
{
    return (cti & 0xFFFFFFFFn);
}

function
cti_ledger_check(
    cti)
{
    return (cti >> 52n) & 0xFn;
}

function
cti_transaction_check(
    cti)
{
    return (cti >> 48n) & 0xFn;
}

RH Note: Advanced case (XLS15.1) examples and reference implementations to be added shortly

[WietseWind]

Very useful to point eg. with a issued currency HEX code (#30) to a transaction containing memo with more information about the token (@RareData, @nixer89).

A change I'd like to propose is to switch from xrpl-cti://67835576823535218 to the xrpl:// protocol code, so apps don't have to register a whole list of protocols to handle, eg.:
xrpl://cti/67835576823535218

[nbougalis]

This format seems to conflate two different goals: a "compact" encoding for code purposes, and a "compact" encoding for human purposes. Why not use two?

Using your example, here's what it would look like for human consumption:

xrpl://cti/62090589-9
or
xrpl://cti/62090589/9

For the compact 64-bit encoding, useful to machines, I'd recommend 4 bytes for the ledger sequence followed by the 3 low bytes of the sequence number. The last byte can be a CRC8 over the previous 7 bytes, if you're so inclined.

[RichardAH]

Main issue with that encoding IMHO is that fails the double-click-copy test. That is: a user in a hurry double clicks (to select) and then copies, resulting in half copied code, whereas a singular code with no delimiter is always copied completely.

[nbougalis]

Makes sense, re: copy-paste test. I still think you should use hex: it makes the identifier shorter than pure decimal and more compact for users, which is a plus.

[RichardAH]

Makes sense, re: copy-paste test. I still think you should use hex: it makes the identifier shorter than pure decimal and more compact for users, which is a plus.

I agree hex is a nicer representation for compactness, however decimal is case-less (and therefore every CTI literal is trivially unique, there are no non-canonical CTIs, unlike for example xrpl://cti/F1001903B35672 and xrpl://cti/f1001903b35672 which would be two unique strings referring to the same CTI) and can be parsed and passed trivially between virtually any language, system or interface with no special logic. That said the spec leaves it up to the implementer to decide how to display or use a CTI, unless it's a URI, in which case presently decimal is used for the reasons above.

[Silkjaer]

Referring to transactions to store e.g. a token payload is great, however it will only live for as long as full history is available. Where “live” ledger objects persistent, the transaction history can be lost, hence invalidating the reference?

It’s not a major concern, as the standards discussed here and in the NFT thread is focusing on ways to implement NFTs without amending the XRPL – so the outcome will be an agreed upon standard of how to do it, and not a “real” XRPL feature.

[RichardAH]

It’s definitely true that if the thing you point to disappears the pointer is effectively useless.
But even if that does happen the pointer is still unique. So for example if you did point to a txn containing metadata for an NFT, you lose access to the metadata but you retain the uniqueness of the token. Ultimately the world of crypto currency is a cooperative game where we all agree to assign significance to arbitrary values decided through consensus. Why not the unique pointer being the value as opposed to the pointee?

[Silkjaer]

I agree, and a standard for a pointer is very helpful no matter what. Just as a hyperlink remains a hyperlink, even if the domain doesn’t resolve.

The main concern of mine was related to the NFT-specific use cases and I have addressed that in the proper thread (#30). In other words, the persistence-concern in relation to CTI can be ignored 🙂

[calvincs]

Question w/ "Why not the unique pointer being the value as opposed to the pointee?" If the pointer is failing to resolve to the meta, how does the end users application pull the meta that it requires in order to show the content, or validate they own the digital objects? This is one thing I really like about the XRP ledger, and I find as one of its strong suites as compared to other block chains, you don't require a full history of TXs. If we begin to use the meta in the memo of a TX, and then use a pointer which can roll off (unless you maintain full history), you create complexity. Over time the system will become fragile (NFTs).

However, if the pointer/meta is in the AccountRoot, no number of transactions is required for storage for later retrieval.
Are my assumptions of this limitation incorrect?

If not, I think we should really consider putting the meta/pointer data in the AccountRoot, like the Domain/Email/Msg Key hash, or create a new field (I dont think this is required tho).

Im writing a piece of software which may help with this by providing AccountRoot summary data in a p2p fashion for clients. And while some hosts would need to periodically query the ledger to compile said data, those hosts would not require the full processing power of a full history rippled node to do that, as we are only examining the latest state of the ledgers accounts. And clients as simple as phone web browsers should be able to acquire, parse, and locate whatever services or meta they require from the ledger, from a given address, in a reasonable time period.

[calvincs]

If you can use the strengths the XRP ledger gives you out of the box, and boot strap your apps that way instead of requiring heavy services like full history nodes, IMHO it makes the app and the use cases stronger. Small light weight apps should have as easy of a time locating services or pointers tied to assets on the ledger as possible w/o requiring resource intensive infrastructure.

I understand Xumm has a well maintained back end, full history nodes, beefy post processing w/ lookup tables, etc. But not all apps have that power, and if possible, if we can make that not a dependency for applications, XRP dependent apps and services would be better for it. This would also allow more agility for apps, less dependence on said heavy services like full history nodes do function normally.

This is why when I built the demo code I did, it used the accountRoot, the one thing that always carries forward.
Thoughts?

[RichardAH]

However, if the pointer/meta is in the AccountRoot, no number of transactions is required for storage for later retrieval.
Are my assumptions of this limitation incorrect?

XLS15d is just a definition for a type of pointer called CTI, it doesn't tell you how you should or shouldn't use it.
I think you probably want to move this NFT discussion to XLS16d which proposes using CTI as a pointer to NFT metadata.

[intelliot]

Since the first hex nibble is only affected by the first four bits of ledger hash and the first four bits of transaction hash, it seems there is a risk of a transcription error since it is not a checksum over the entire data. It may make sense to use something like the Luhn algorithm (which is used in credit card numbers) so that any single digit error is caught.

[RichardAH]

The first byte isn’t a checksum over the data so this doesn’t work the way you’re thinking. The address of the transaction is validated with some information about the destination that you can only validate by looking it up / going there.

If I give you street directions and tell you that the house you are looking for has a green dragon out front now I can make any number of transcription errors and you will still know you arrived at the wrong place in almost every iteration of this scenario.

In this case even if the ledger and transaction you ended up accidentally addressing are valid you have only a 1 in 256 chance of getting the check byte correct with respect to the destination. Thus for at least 255 out of 256 mistranscriptions this will catch any number of errors in the digits.

[intelliot]

Ah, my bad. I understand now -- thanks!

[intelliot]

Alternatively, Bech32 is a little more compact.

[ximinez]

We assume a ledger will never contain more than 65535 transactions.

I don't know if that's a very safe assumption. Sure, we're nowhere near that level today, but there's no telling how things may change in the future.

[RichardAH]

That’s true, however this would gracefully fail in the form of CTI-addressable vs not CTI addressable txns. The cost of using two extra bytes everywhere forever for the possibility of not being able to address some txns in the future seems unappealing to me. I suppose “zero compression” could be used but adds unwanted complexity to a currently straight forward standard

[ximinez]

Good points. This standard 1) is very clear that it has this restriction, and 2) leaves open the possibility of coming up with a new standard if and when ledgers ever get that big. Sort of a T65K problem, if you will. 😀

[nbougalis]

Having now read this spec and the several comments, I agree that the 64k limitation on transactions per ledger is likely a non-issue today but "feels" problematic nonetheless. Since we're still discussing this, let's weigh the positives of a slightly more complex format:

Proposed alternative

Part of my goal was to ensure that any tx which has a valid CTI under the original proposal (i.e. has a 64-bit encoding) the resulting encoding under this scheme would also be under 64 bits. In other words, we want to fit the resulting CTI in 64 bits for any currently representable ledger, where the transaction index is less than 65536.

In crude ASCII, the proposed format looks like this:

     +-------------------------------------+
     |                                     |
     | +-----------+                       |
     | |           |                       |
     | |           v                       v
1RRRRTTL CCCCCCCC [AAAAAAAA ... AAAAAAAA] [BBBBBBBB ... BBBBBBBB ]
     | | |
     | | |
     | | +---> Checksum, as described by you originally.
     | |
     | +---> Ledger Index Length: `1` if ledger index is 64-bits long, `0` otherwise.
     |
     +---> Transaction Index Length: number of bytes _minus one_ occupied by transaction index.

This will fit in 64 unsigned bits for any ledger where the transaction index is less than 65536. Considering that the existing format can't represent such transactions anyways, and we're comfortable with that, we should be fine. Bonus: 4 reserved bits (potentially 5 if we don't care for a leading 1). How to use them? There's options. For example, we could shave off two of the "reserved" bits to represent mainnet (0), testnet (1) and devnet (2) and use 3 to represent other.

Small caveat: we need a simple rule to ensure there is a canonical format (that is, the same tx can't be represented by two CTIs):

1. If the ledger index is 64-bits long but the encoded value is less than 2³²-1 the CTI is invalid.
2. If the transaction index has leading zero bytes (i.e. is not represented minimally) the CTI is invalid.

Example:

Your example was CTI resides in ledger 62084722, has a transaction index of 25, the transaction hash's first nibble is 1 and the ledger hash's first nibble is F.

Encoded with my scheme, would produce:

0x80 for the flag bits, 0 for the transaction index indicator (it's 25 which needs 1 byte) and 0 for the ledger length (it's 32 bits): the result is 0x80.
The checksum is, per your calculations, 0x1F.
The ledger index is, per your calculations, 0x03B35672.
The transaction index is, per your calculations, 0x19

Let's compare the CTIs produced by the two encodings:

Style	Hex	CTI
NB	0x801F03B3567219	36062897773113881
RH	0xF1001903B35672	67835576823535218

Downside

Once parsed into a 64-bit unsigned value, the location of the "header" is 'floating' (i.e. it's not always in the high byte, hence the need for the leading one in the header). This makes parsing a little more difficult; the cost for having ever so slightly more compact CTIs. This may or may not be a worthwhile tradeoff.

This downside can be addressed by ensuring that the transaction index is always represented as two bytes. Of course, this makes the "overlong" checker slightly more complex. Still, it may be worth the effort.

Representation

Decimal. I still think hex is, generally, more compact and (imo) easier to parse, but I think decimal is the way to go for the reasons @RichardAH highlights.

[nbougalis]

There's a couple of issues with endianess in my example that I'll need to work out.

[nbougalis]

@RichardAH liked the proposed extensions to the format, but he also noticed that with a mild massaging of the fields, my proposal could be backwards-compatible with existing CTIs. He's going to make those changes in the proposed standard.

A win, all-around!

[RichardAH]

XLS15.1 update has been mostly made

[interc0der]

Here is my shot at the advanced implementation... How does it look @RichardAH ?

Implementation

  encode: (opts: CtiAdvancedEncodeOpts) => {
    let ledger_check = BigInt(parseInt(opts.ledger_hash.slice(0, 1), 16));
    let txn_check = BigInt(parseInt(opts.txn_hash.slice(0, 1), 16));
    let txnBin = Number(opts.txn_index).toString(2);
    let lgrBin = Number(opts.ledger_index).toString(2);

    let padding = BigInt('00'); // Will be dropped from BigInt, placeholder
    let T = BigInt(txnBin.length < 16 ? 0 : 1);
    let L = BigInt(lgrBin.length < 32 ? 0 : 1);

    let cti = (padding << 1n) + T;
    cti <<= 1n;
    cti += L;
    cti <<= 4n;
    cti += BigInt(opts.networkId);
    cti <<= 4n;
    cti += ledger_check;
    cti <<= 4n;
    cti += txn_check;
    cti <<= T === 1n ? 32n : 16n;
    cti += BigInt(opts.txn_index);
    cti <<= L === 1n ? 64n : 32n;
    cti += BigInt(opts.ledger_index);
    return cti;
  },

Example

networkId	1
ledger_hash	F8A87917637D476E871D22A1376D7C129DAC9E25D45AD4B67D1E75EA4418654C
ledger_index	62084722
txn_hash	25

hex	0x1F1001903B35672
ctx	139893170861463154

Question

Since there are floating zeros at the front end of the bits, these will get chopped off when encoding. This is especially an issue when trying to determine the T & L bits when they are both 0 ( TL = 00 ).

Is there a simple way to decode the advanced CTI? I would imagine that the first step would be to determine the T & L bits and then move from there. However, in their current position, they could be lost and inaccessible.