0041 XLS-41d: XRPL Proof of Payment Standard (XPOP) #107

RichardAH · 2023-05-04T09:46:58Z

RichardAH
May 4, 2023
Maintainer

XLS-41d

Title: XRPL Proof of Payment Standard (XPOP)
Revison: 1 (2023-05-04)

Author: Richard Holland
Affiliation: XRPL-Labs, XRPLF

Abstract

An XRPL Proof of Payment (XPOP) is an offline non-interactive cryptographic proof that a transaction was successfully submitted to the XRP Ledger and what its impact (metadata) was.

Background

The XRPL is comprised of a chain of blocks (Ledgers) co-operatively and deterministically computed, shared and subsequently signed (validated) by a quorum of rippled nodes (validators) operating in a socially trusted group known as a Unique Node List (UNL). The UNL is typically published by a trusted third party in a format known as a Validator List (VL). (Examples: https://vl.xrplf.com, https://vl.ripple.com). Each VL is cryptographically signed by a master publishing key. Users of the network ultimately trust this publisher (key) to choose appropriate validators for the UNL that will co-operate to make forward progress and not conspire to defraud them.

Proof

Each VL contains a list of validators signed for by the VL publisher key.

Each validator is a key that signs validation messages over each Ledger header.

Each Ledger header contains the root hash of two patricia merkle tries:

the current (”account”) state for the ledger, and
the transactions and their metadata in that Ledger.

A quorum (from a given VL) of signed validation messages proves a Ledger was correctly closed and became part of the block chain.

Thus if one trusts the VL publisher key, then one can form a complete chain of validation from the VL key down to a transaction and its meta data without connectivity to the internet. This is an XPOP.

Format

XPOPs are a JSON object with the following schema:

{
	"ledger": {
		"acroot": merkle root of account state map | hex string,
		"txroot": merkle root of transaction map | hex string ,
		"close": close time | int,
		"coins": total drops | int or string,
		"cres": close time resolution | int,
		"flags": ledger flags | int,
		"pclose": parent close time | int,
		"phash": parent hash | hex string,
	},
	"transaction": {
		"blob": serialized transaction | hex string,
		"meta": serialized metadata | hex string,
		"proof": <see below>
	},
	"validation": {
		"data": {
			validator pub key or master key | base58 string : serialized validation message | hex string
			... for each validation message
		},
		"unl": {
			"blob": base64 encoded VL blob as appearing on vl site | base64 string,
			... remaining fields from vl site
		}
	}
}

The proof key inside transaction section has one of two possible forms:

List form:

In this form the merkle proof is a list of lists (and strings) containing the minimum number of entries to form the merkle proof. Each list contains 16 entries (branches 0 through F). For each branch either the the root hash of that branch is provided as a 64 hex nibble string, or a further list of 16 entries is provided, until the transaction that the proof proves is reached. If a list contains fewer than 16 entries then the verifier should infer that the remaining entries are all null entries (hash strings that are sequences of 0s).

# list form
"proof": [
	hex string for branch '0',
	...
        hex string for branch 'A',
	# branch 'B' is a list
	[ 
			hex string for branch 'B0',
			... ,
			hex string for branch 'BE',
			# branch 'BF' is a list
			[
				hex string for branch 'BF0',
				...
			]
	],
	hex string for branch 'C',
	...
]

Tree form:

In this form the merkle proof is an object of objects containing the entire transaction map for the ledger. This form is useful if many XPOPs must be generated for the same ledger and the size of each individual XPOP is less relevant than the amount of work to make and store the XPOPs. Each object contains three keys: children, hash, key.
- The children key is always either an empty object or is keyed with only the branches which actually exist there, each as a single hex nibble 0 - F.
- The hash key is always a 64 nibble hex string: either the hash over the children (with appropriate namespace) or, if a leaf node, the hash over the node (with appropriate namespace).
- The key key is always a 64 nibble hex string: the keylet (index) of the object at this location.
```
# tree form
"proof": {
  "hash" : hex string,
  "key" : hex string,
	"children" : {
		"0":
		{
			"children": {},
			"hash": hex string,
			"key": hex string
		},
		...
		"F":
		{ ...}
	}
}
```

Verifying

See reference implementation at: xpop-verifier-py

tequdev · 2023-06-19T06:24:12Z

tequdev
Jun 19, 2023

It may be easier to understand if there is JSON data from XPOP that can prove actual transactions on the mainnet.

1 reply

wojake Jul 7, 2023

This XPOP blob was generated from a validated transaction on Ripple's testnet.

Tx: https://testnet.xrpl.org/transactions/F300B5885B54CBA2F72ACE9B8299969F12203E167CA623F0CF23D22C9E9C0FFC/raw
XPOP blob:

{
        "ledger" : 
        {
                "acroot" : "F360C7E8A141575B03E386BFA5F6C988F2948F4B9F66A39724345A63D903A39E",
                "close" : 742038471,
                "coins" : "99166066808667104",
                "cres" : 10,
                "flags" : 0,
                "index" : 39280547,
                "pclose" : 742038470,
                "phash" : "E0DD7C02F9DADE5EE6028DBFD1CEEA9FE5809FB7D54FC4B33606A8572390641F",
                "txroot" : "35DDF481D97D15D4F03E0B180C8B7A1AC59C39B20E6116172035D723CC273943"
        },
        "transaction" : 
        {
                "blob" : "1200032200000000240255CCD0201B02575FB5201D0000535A684000092605294D007321ED49150677E641A3231ED04028D0FC5C08FBB564BCADEA933D59542EF4CB4689AC74408DD8C7769A142A00A500E9063827D39DE91C7AE6F8AB22C12737F0BA9C0CC7A2EB493AD317DDBEDD900F1C23CEC8E007F134E1A6B3043C6686FA5FD640A4E1098114AA27A467219814EB0B73F3A99C8610848C20F75C",
                "meta" : "201C00000000F8E51100612502575F835589BB7CEF87F7510EDABD1C75FD9B0E449BBF11059412C10E59C7FC950E9EB0D856383F26DEC23EE8EB0549CDCE5608BF72EE789469F28C11750E714FCEE5AF011EE6240255CCD0624001F852234D83F5E1E72200000000240255CCD12D00000000624001EF2C1E2436F58114AA27A467219814EB0B73F3A99C8610848C20F75CE1E1F1031000",
                "proof" : 
                {
                        "children" : 
                        {
                                "F" : 
                                {
                                        "children" : {},
                                        "hash" : "825707D738FBD15D3BF01C21304595264A393762121982106AD30BDBD98F50C9",
                                        "key" : "F300B5885B54CBA2F72ACE9B8299969F12203E167CA623F0CF23D22C9E9C0FFC"
                                }
                        },
                        "hash" : "35DDF481D97D15D4F03E0B180C8B7A1AC59C39B20E6116172035D723CC273943",
                        "key" : "0000000000000000000000000000000000000000000000000000000000000000"
                }
        },
        "validation" : 
        {
                "data" : 
                {
                        "n944nVL4GHUBpZWUn2XaQXYT92b42BYHpwAisiCqvL159tEmWY46" : "22800000012602575FA3292C3A9BC83A385F12D6319DDB9A512907439C379EBE328C5CB65A9F11FC0F1C434B1B625E48D5980411A77C11BAAA50174BF968B6D5F7CFD4F982A870BF36D5B6904ECC519B20BE15CF34FA3DF2EDE2B65019E0DD7C02F9DADE5EE6028DBFD1CEEA9FE5809FB7D54FC4B33606A8572390641F732103F71FA3C31F84FC0FC481E307C0DCF3F450EA5F5857EC8E5EBC21C6C08E3906A47646304402203CF3F26E2AC74ABAD50F74B18D9EE2F125243E34A1D7B62FADB9280F781869100220128242C5869DF40967DD5844834F319ACCD609351AC66FE569E02395AF6814CC",
                        "n9K7fyu8uvmCoWvW4ZQVCWgW2zrz7sh33Ao7ceNkL7iQGDYtuwTU" : "22800000012602575FA3292C3A9BC83A124E519EEDA8BF10512907439C379EBE328C5CB65A9F11FC0F1C434B1B625E48D5980411A77C11BAAA50174BF968B6D5F7CFD4F982A870BF36D5B6904ECC519B20BE15CF34FA3DF2EDE2B65019E0DD7C02F9DADE5EE6028DBFD1CEEA9FE5809FB7D54FC4B33606A8572390641F73210279C1B242658DD78514A5A60A206FA30C18A3EE370592A058A80FAA3E5C44F0977646304402200C417A593A6FD4495D75CF660010598B0CF002EF3EF4D9F93510E1EA86C654B10220165F51CB540C78A2056C1B2032187AD686EE9280A2FC4047641DFD1803363E2F",
                        "n9KWVA64rMeqkAvcQ4DNCa2eDXTzprCtK1HLC8H5PEyUVwSSyL5X" : "22800000012602575FA3292C3A9BC83A0AE7729763F67407512907439C379EBE328C5CB65A9F11FC0F1C434B1B625E48D5980411A77C11BAAA50174BF968B6D5F7CFD4F982A870BF36D5B6904ECC519B20BE15CF34FA3DF2EDE2B65019E0DD7C02F9DADE5EE6028DBFD1CEEA9FE5809FB7D54FC4B33606A8572390641F7321027F285B8BB33F0E8B025BF955C29A7CFA8A0995831EE4AD93A9BD572A7C8EEDCD7646304402202F166163547EB42BF55908C412B062A6653B423E2281C07D45E49D4E23AA604502202A4F6FE44C84012EA5C7570C1BC55E17C0D4EE6E7F52E9D8626DCC215A74AF17",
                        "n9KcRZYHLU9rhGVwB9e4wEMYsxXvUfgFxtmX25pc1QPNgweqzQf5" : "22800000012602575FA3292C3A9BC93A8BC16D1445BD05A1512907439C379EBE328C5CB65A9F11FC0F1C434B1B625E48D5980411A77C11BAAA50174BF968B6D5F7CFD4F982A870BF36D5B6904ECC519B20BE15CF34FA3DF2EDE2B65019E0DD7C02F9DADE5EE6028DBFD1CEEA9FE5809FB7D54FC4B33606A8572390641F7321028C9C1DE3789DA22316D789E31099D10F0FE5977DAFD45459B1311FFB65F46FC97646304402203A67F45C4F1B8AE86A92D3176EBD27F045EC9BE8D565DA86C778D27F5CCE2924022000B281CF9CCDC5735852E08384C9F456852F7BA8119CE73A2D16413A0D4FC69F",
                        "n9Kv3RbsBNbp1NkV3oP7UjHb3zEAz2KwtK3uQG7UxjQ8Mi3PaXiw" : "22800000012602575FA3292C3A9BC93A33E3CBEBC7F73D20512907439C379EBE328C5CB65A9F11FC0F1C434B1B625E48D5980411A77C11BAAA50174BF968B6D5F7CFD4F982A870BF36D5B6904ECC519B20BE15CF34FA3DF2EDE2B65019E0DD7C02F9DADE5EE6028DBFD1CEEA9FE5809FB7D54FC4B33606A8572390641F732102B4CF65358D43B21C6D720FD5211E4F6AD3C2C27BF2DB5960242E49A5E06A36D076463044022037CF060D9145D7BF6E79E43D7522058BE944ADAAEA30E8ADAF80FD4BF7F02A8802200CF3C3E7D928395B7BE213593B9AB92FE73331A9B4AC1B0BACF75FDC840A4D9F",
                        "n9MGR6mE5oQGbNSf2ZbQUnAQmZeN8uim5pcVdfqgdtQscXJutZHW" : "22800000012602575FA3292C3A9BC83AACF393EBA1E5C8D9512907439C379EBE328C5CB65A9F11FC0F1C434B1B625E48D5980411A77C11BAAA50174BF968B6D5F7CFD4F982A870BF36D5B6904ECC519B20BE15CF34FA3DF2EDE2B65019E0DD7C02F9DADE5EE6028DBFD1CEEA9FE5809FB7D54FC4B33606A8572390641F73210366985A2A58FCDD64004A0A1B0FE5C7550891436775AD50562DA6DFACE13AE62F76473045022100B09A8E1133CC9E3F70ED55D6A2F3A54B83191EDC0A946C45630C41126D42E77F02205CF757E7F5914C2345850D0ADC2083AF0C9CE97B5D885DAA70C51228D60184D0"
                },
                "unl" : 
                {
                        "blob" : "eyJzZXF1ZW5jZSI6NTUsImV4cGlyYXRpb24iOjc1MjcxNjgwMCwidmFsaWRhdG9ycyI6W3sidmFsaWRhdGlvbl9wdWJsaWNfa2V5IjoiRUQwNjFFQ0I1MUI1QkQ2MjY2NUY1RDFBNURCMUE2MkFGODQ0NjRCRUQ3N0U3NzI4MjM1QTdBNTUxRDQ1MzVFNzE3IiwibWFuaWZlc3QiOiJKQUFBQUFKeEllMEdIc3RSdGIxaVpsOWRHbDJ4cGlyNFJHUysxMzUzS0NOYWVsVWRSVFhuRjNNaEFubkJza0psamRlRkZLV21DaUJ2b3d3WW8rNDNCWktnV0tnUHFqNWNSUENYZGtjd1JRSWhBS1JpTFhldko2MXVraFp0aWt2Q3VLZ0dSblY4SDA4ZU0vUEV2Sk5FZGwwNEFpQmkvQms2OFZWZWZSMUd0Z0k0WWV6UlFWc3huRWlOL0xtV1NObVFZS1FSSUhBU1FBdDhoS2Z4a3FQTWVCT1RoMngyaGpya0FhN2xlVGVuQnRmOUR4dWh3bGdzQjlOL3h4VGZwek1Ra2pVWW9ZaXlYa1haeWgxTlZzTkxES1VtT2RXWkxBTT0ifSx7InZhbGlkYXRpb25fcHVibGljX2tleSI6IkVEQURCNkU2RjcyMjlGOTI5MDlFNUE2REJBRjgxQUQxRUM3MjNEMzFCNjc2Q0Q4RjVGM0U5MjZBRDA0M0QxODdDMCIsIm1hbmlmZXN0IjoiSkFBQUFBSnhJZTJ0dHViM0lwK1NrSjVhYmJyNEd0SHNjajB4dG5iTmoxOCtrbXJRUTlHSHdITWhBbjhvVzR1elB3NkxBbHY1VmNLYWZQcUtDWldESHVTdGs2bTlWeXA4anUzTmRrY3dSUUloQU5RbEZiaUROZmEvTEpJcitlYVoyS0tjMDRHbGRaTXJBRzRiRFdGTUx5VVJBaUFsd0FmTkl1dmVJMEhtaE0wSStGdzR5Z0FzSEZXdXdWcmNXS2FiWkxIdGdIQVNRQkJFVFRSRHhDc1FvNHdJSyt6NUNkOU9ta3UweUR4Qk9NVEE3MFJTcUVvcFY5REhCZ1ZWOWc4MmoxbW4wb0pYRHowcE5YcnJDbjNEcU1id0EwdkMrUUE9In0seyJ2YWxpZGF0aW9uX3B1YmxpY19rZXkiOiJFREY1QjY2MUVDQzYxNUM1Qzc3RDU1RjFCNTcyRkFDNkZFNkM3QjExNkVCMEEwRTNGMURDRUI5RjQ4OTMyNTQ4RDAiLCJtYW5pZmVzdCI6IkpBQUFBQUZ4SWUzMXRtSHN4aFhGeDMxVjhiVnkrc2IrYkhzUmJyQ2c0L0hjNjU5SWt5VkkwSE1oQS9jZm84TWZoUHdQeElIakI4RGM4L1JRNmw5WVYreU9YcndoeHNDT09RYWtka2N3UlFJaEFMVWRubHVoaHE4eWZMN2RkZ3o3MXRVUFdBNGUyZWRKMmE2OWNRa3d5TkNCQWlBNmQ5Rk5lS0FqTGhPampLUjUyTDRjSWZ2L0FRdGdVQWxiOUgwbjJ1eW82WEFTUUQ3TThMU0dMS29uZHoxRU9tckF3ekQ0MDdHdk14RmhhRWEyYnBJUHpObFZIRStQbU92SndabnhoTG9HK05ZVlVmbWFVcmVTKzdreHYrZ3lvSHR1bXdZPSJ9LHsidmFsaWRhdGlvbl9wdWJsaWNfa2V5IjoiRURGNjI5MDc3NjNBQUQ4RUQyMUY3RUFGM0YzNkI1MjY0ODU2QTM3NUZCQjQ3Q0U2NDM4M0VFRDc0ODQ3QzhEQTZBIiwibWFuaWZlc3QiOiJKQUFBQUFGeEllMzJLUWQyT3EyTzBoOStyejgydFNaSVZxTjErN1I4NWtPRDd0ZElSOGphYW5NaEEyYVlXaXBZL04xa0FFb0tHdy9seDFVSWtVTm5kYTFRVmkybTM2emhPdVl2ZGtjd1JRSWhBTXZWUXFEVjNQK3BKcE0vNENYN3hLV2RkZlhqZTFka0I3cXlQWW9Ua2F4eEFpQkhDRGNEVXJ5WDRGck13bEtRblB2cmN6dDFwUFVzNHMvTUFXRVQ1T1k4dW5BU1FQbCs5dndpTXhPTk9kR09VZ0NabzBJRWk5cXJmVFA2Q1RROEx5VlRLa0k1VE9VZURNSVlPNmlGT3JtWGpkY3NtZjBwaDU1VC9UcEtVdVA3dWlBMnN3MD0ifSx7InZhbGlkYXRpb25fcHVibGljX2tleSI6IkVEQTlCRUFCOTg3RENGRkVEQ0YyMDY3QjI0Q0M3QjhDRjBDMjEwQjM1OEE4OTFGRTBFRDc4RUMzMjRGQkI0MEFEQiIsIm1hbmlmZXN0IjoiSkFBQUFBSnhJZTJwdnF1WWZjLyszUElHZXlUTWU0end3aEN6V0tpUi9nN1hqc01rKzdRSzIzTWhBb3ljSGVONG5hSWpGdGVKNHhDWjBROFA1WmQ5cjlSVVdiRXhIL3RsOUcvSmRrY3dSUUloQU9EQWV0NTZ5Mm9hMEtVRE55ZkVVNnVJZjhsdTBRUnRaUkE0NVFzY3lTL05BaUIydzZTcFJoM3VTUXdjNVFOOHhsWEVpY3dReUM1SFBOZCtieU5Wb29sREtuQVNRRkpkRjl6ZHVVRW83UjVTZDdEUHVLOEdqVXczdGtXcGZSd0x6Ym01NU5mdHhDMi9RVEdmRzRtcWJvbitSYTRNQW95UEZKV216bUpuWWY5ZWNJZEMrZ2c9In0seyJ2YWxpZGF0aW9uX3B1YmxpY19rZXkiOiJFRDIwQkIxMzREMDNCNTRFM0QyRTY3NDU3NzVCRjQxRkFERjNDMjc2Mzk5QjFGMzYyMzA4MUQ3QjY2RDA3MTRFMzMiLCJtYW5pZmVzdCI6IkpBQUFBQUp4SWUwZ3V4Tk5BN1ZPUFM1blJYZGI5Qit0ODhKMk9ac2ZOaU1JSFh0bTBIRk9NM01oQXJUUFpUV05RN0ljYlhJUDFTRWVUMnJUd3NKNzh0dFpZQ1F1U2FYZ2FqYlFka2N3UlFJaEFQODJGeFZJdFJnMVdQUEN2Qit5dzBwUEhsNS9iQTB4RC9LV2NTZFdHRDJTQWlBVlE4YlhPbnRjYmw4TU0yanMrbVpPWWN0S2tKekZjRTl4RWY5MVdSb3czbkFTUUdQOXgxb3hSR2QyZkl5eUpweDYrSENnYXIyKy9Ocy9PcmQ1aFVsVFhhSUN6S0dmRzUvY1VsRXpjZ04yQm9SQmp4Q3BpNXdNaDg0aEphTCtoSVZINUFjPSJ9XX0=",
                        "manifest" : "JAAAAAFxIe0mSAcQKAUiDaDzEucfwsaeFVLJxXkPbCXjcp3rVz1YYHMh7Rt08vn4Maojg0vgNNcPuxVrJhyFy5tnQMSHfgCvuHjWdkCg/oL0GUq0QOgrdHw1Tw3BtA4lrLzDVQrSTFu+tMz+Dkdshs5gtbbfHQ2qFgYzGwaA9o3Z5Wwjv0iqXtxwH18PcBJAWCjvE1dMKgjMWu88GKgYDOaYJrOfOmN9CpxwnOObamY5gL2iENqTuo8bllpK4Hor3ewYwRCHWPTMpirBsDe4Aw==",
                        "public_key" : "ED264807102805220DA0F312E71FC2C69E1552C9C5790F6C25E3729DEB573D5860",
                        "signature" : "75DE050E6AD07EA5D8CD031C387CF00987389D8DDC0A1E018ABFE368EE881C4A68CFD7856BDBF7B87B53EEECCCB40CC8144E64E2D55FC833764DECD5EFE41E02",
                        "version" : 1
                }
        }
}

sublimator · 2023-09-25T05:33:27Z

sublimator
Sep 25, 2023

In this form the merkle proof is a list of lists (and strings) containing the minimum number of entries to form the merkle proof.

So basically all shamap inner nodes down to a given leaf + the leaf itself ?
In order to provide a minimal per TX proof?

If a list contains fewer than 16 entries then the verifier should infer that the remaining entries are all null entries (hash strings that are sequences of 0s).

Why not just use an empty string (or null) given empty nodes will be essentially randomly distributed? So any child can be set as empty?

In this form the merkle proof is an object of objects containing the ///ENTIRE TRANSACTION MAP/// for the ledger.

Why not just a flat list then?

                "proof" : 
                {
                        "children" : 
                        {
                                "F" : 
                                {
                                        "children" : {},
                                        "hash" : "825707D738FBD15D3BF01C21304595264A393762121982106AD30BDBD98F50C9",
                                        "key" : "F300B5885B54CBA2F72ACE9B8299969F12203E167CA623F0CF23D22C9E9C0FFC"
                                }
                        },
                        "hash" : "35DDF481D97D15D4F03E0B180C8B7A1AC59C39B20E6116172035D723CC273943",
                        "key" : "0000000000000000000000000000000000000000000000000000000000000000"
                }

You can easily derive 35DDF481D97D15D4F03E0B180C8B7A1AC59C39B20E6116172035D723CC273943 from just:

[{"hash" : "825707D738FBD15D3BF01C21304595264A393762121982106AD30BDBD98F50C9",
  "key" : "F300B5885B54CBA2F72ACE9B8299969F12203E167CA623F0CF23D22C9E9C0FFC"}]

EDIT:

Actually, you could probably use a trie for ShaMap hashes serialization, with only non empty branches serialized, ala (new, unrelated example):

    const json = rebuildFromSerialized.toHashTrieJSON();
    expect(json).toMatchInlineSnapshot(`
      {
        "0": "76F1C3FF38A714698F08C5975381C6535C6E4FA301A23E64BCFBF1E67E314CFC",
        "1": "6A609D46DEBF7E45387052017776B77180B37314E9F7CC56027C5EA4CFF7E833",
        "2": "A33493A006A7131F6050513E2A47143768363BC852E16087666B7D44443C316D",
        "3": "3237B99730D300B349FAC468B3D24EC2DA0B2BDA1DA0CF319219414F72088127",
        "4": "29FD2F34869B2E46EA2FC996FE7CB94AF4C3B40CD9859232D682F8AE1C17DAD5",
        "5": "F6CDB77D30E19B255FE830E8F78284183A6A268B69FF01933909A1EA89D580E6",
        "6": "7DCBA89FB67254F49F38CACC86038430A559AC63AF3F419925B33E33DE404300",
        "7": "5BF0F8F0301846B5DE57AC09C0E271B610519CE90BD45EA76DE47FAE1696A78C",
        "8": "A6ABF75B4DA7C37ADDC2EE7D7B05B2B8D2EF645182139E1694698164903628AD",
        "9": "388913E4628AF2AD3CEA0734E5E8D1DBCB04F89A1105F9B19173D883B4C1E0B2",
        "A": "C6E3D6EA5801B91BA37E1DD64D07205726C9D3362FF9DE67457C582F62A14CB8",
        "B": "8DE55E527AAE1557AA14AD1AA3130108A5F13B3A41E48DDCBF4DA5E88223CAA0",
        "C": "729E02B88D238663C46916904CFAE207C2CD8D45A4BE42D666B4DE4AA96C0C09",
        "D": "D46F861F9C0F0860392FF66DE7760CDD1F8896B92F2B94B53099C96049C22F2F",
        "E": "110D7FC2D0F0EE72257C4F2F35C834C705DCEA4F452D12F184A535C727DAA652",
        "F": {
          "0": "577F9BC59FF644CA79F1A54C701D7A2B9F6A94124EE3E858CADF2F1BA394934F",
          "2": "587DFD9CA7D3B6E1589270D84630020415E062F3E0309BD561C998FA18CAC653",
          "3": "241190127E9689D05E394FB47E0C0F52DFDC11F107121CD6646F177BCE27C064",
          "5": "05D7C9632E1D376260D9F1CC7B1CECD85E691D791200648ECDCE8BCE0AC57703",
          "7": "C0E2145F5DDDBB0DEE05B02F5053C3EC6AD438783442FE3CD9F98B91B4BDE9F9",
          "8": "0D9A13858FD4090E3DD388DF39E4A859ED17D400F3FE5735EF0E784F3D269424",
          "9": "176416363DF65DEDBC8F8F98E7B3E3204B9DDFA620129D58515DF0BBD7106D84",
          "D": "2C78CDA63B6E00C2415B40D661455DBA8245282AC9CFBD306CB1737E9E8C48EA",
          "E": "0F276EA0494A9E6F956776906FFD607D980B21A8056912A7AE5AF9F3FBDD77F4",
          "F": "09F3695445162CA5ED5AAEC271FF3E545F09B0D439003FC5A6009D205CA40981",
        },
      }
    `)
    const fromJSON = ShaMap.fromHashTrieJSON(json)
    expect(fromJSON.hash().toHex()).toBe(fullMap.hash().toHex())

Then with that format you could support both abbreviated or the full trees?

0 replies

sublimator · 2023-10-02T03:46:59Z

sublimator
Oct 2, 2023

Somewhat related, for QR encoding:
https://datatracker.ietf.org/doc/rfc9285/

0 replies

sublimator · 2023-10-17T05:33:09Z

sublimator
Oct 17, 2023

edit: see https://github.com/sublimator/xrplf-shamap

I experimented with abbreviated trees (just hashes for inner nodes that aren't of interest) and a binary trie format. Basically emitting a header for each inner node which defines its branch structure. 32 bits, with 2 bits each branch:

export const BRANCH = {
  empty: 0,
  inner: 1,
  preHashed: 2, // simply hash of leaf or inner
  item: 3 // full item R.F.U for run length encoding
} as const

Can be parsed as so:

  *trieHeader(): Generator<[number, BranchType]> {
    const header = this.uint32()
    for (let i = 0; i < 16; i++) {
      const type = header & (0b11 << (i * 2))
      yield [i, (type >>> (i * 2)) as BranchType]
    }
  }

Around 500 bytes for trie data to recompute the transaction tree hash for a ledger with 40 transactions.

Maybe some public key recovery can be done for the validation fields to shave bytes?

edit: this seems possible, also there's a lot of redundancy in the validation data fields

3 replies

wojake Oct 19, 2023

Good points, I think the redundancy in the validation data fields could be cut down as well. However, it may make the XPOP format less "standardized"? No?

sublimator Oct 19, 2023

Maybe some public key recovery can be done for the validation fields to shave bytes?

Btw, to recover a public key, at least with secp256k1 you need the message hash, which includes the public key itself as signing data, so that's somewhat of a non starter. You would save one byte (pub key 33 bytes vs 32 byte hash), and have to burn a lot of cpu cycles.

I think the redundancy in the validation data fields could be cut down as well.

Yep, it would definitely have to be an optional compressed format. But as long as you can stitch things back together and the signatures actually match?

I looked at some of the validations from the example and noticed these common fields:

        "Flags",
        "LedgerSequence",
        "LedgerHash",
        "ConsensusHash",
        "ValidatedHash",

I'm sure it would differ from ledger to ledger, and simply applying compression could help almost as much as something hand crafted and complicated, but there's a lot you could do, >>>if<<< you decided you needed to really create a minimally sized proof.

sublimator Oct 19, 2023

File Format	Original Size (bytes)	Zipped Size (bytes)	Gzipped Size (bytes)	Comments
blob.json	14432	9654	9523	b64 decoded "blob"
blob.hex	28864	12343	12213	"blob" field b64 decoded, and re-encoded as hex
blob.b64	19244	12209	12080	the "blob" field as is
blob.parsed.json	21722	9318	9197	same as blob.json, but with the manifests all decoded into json, rather than base64

Speaking of "low hanging fruit" compression: the unl 'blob' in different formats, compressed.

sublimator · 2023-10-21T04:07:48Z

sublimator
Oct 21, 2023

After some discussion with @wojake lamenting the ephemeral nature of validations, and pondering "why can't we just ask for validators to sign again?" (tonnes of extra work, contentious relitigation of ledgers, poor incentives etc) @mDuo13 suggested the use of LedgerHashes.

LedgerHashes/skip lists seem to be quite literally the "missing link" here. As long as the ledger is live, at some point you'll be able to gather validations for a ledger. You can work your way back from there.

It //would// complicate things, but it would mean you don't need to store tonnes of validations. In most cases you'll be able to gather the validations you need to submit a more compact proof, but if required, cause you couldn't get the required validations, you could create a chain with abbreviated maps containing the LedgerHashes entries.

Edit: I need to check this when I'm more awake, but I think:

Worst-Case Scenario for Ledger Validation

In the most challenging situation to validate a distant ledger, the required components would be:

1. Validated Ledger Components

To start, you'll need various elements from your validated_ledger_index:

LedgerHeader: The header information for the validated ledger, including hashes of txn and account trees, ledger index, and parent hash
Validations: These are the attestations by nodes confirming that the given ledger index matches the given hash.
Validator List (vl): This is a signed list of validator manifests, which essentially contains their keys. The list is signed by an ephemeral key, which itself is signed by the master key.

2. Additional Ledger Information

LedgerHeader: You'll need one more LedgerHeader for the closest flag ledger to your ledger of interest.
LedgerHashes: Per the closest flag ledger. This entry, with a static "index" contains up to 256 previous ancestor hashes, enabling you to track back through the blockchain.

3. Abbreviated Account State Trees

For both ledgers, you'll need an abbreviated account state tree. This tree will only include the hashes of the nodes down to the LedgerHashes entry. For top-most nodes that aren't descended into a single hash is sufficient, as it is a function of the child hashes.
This is needed to validate the LedgerHashes data by hashing the abbreviated tree and comparing it against the LedgerHeader#account_hash
This can be quite compact due to the shallowness of trees with 16 children

0 replies

RichardAH · 2023-10-25T19:42:23Z

RichardAH
Oct 25, 2023
Maintainer Author

@sublimator I wonder if it wouldn't be easier to extend the xpop standard (xpop 2) to allow ledger chaining. So you still provide the same proof but the validation messages are for a different ledger further along in the chain. You provide the ledger headers of each entry back from the current (signed ledger) to the ledger the txn occurred in. Then you don't need artificial secondary signing of old ledgers. A real "chain of blocks" solution.

0 replies

sublimator · 2023-10-25T21:39:10Z

sublimator
Oct 25, 2023

Yeah, I was thinking ledger header chains are perfect for small gaps in connectivity. But for big gaps "for some reason" you would want to use LedgerHashes. Depends use case eh? edit: I got an abbreviated LedgerHashes trie from a 28th October 2023 ledger, and it's pretty big (debug form): ``` { "A": "[A]:4B701E4BFAC38A0285E7468C290ECE9B2E2792C85B54537C4C5311308215B0CE", "B": { "A": "B:[A]:79F62478FECC175880F7F00BC8D2665733FCFE7408F84CE18BD7BB32E8441DC4", "B": "B:[B]:CE258923C068B68A4E09E29E83322277E56F052A39084D06F584DB54D07A28B4", "C": "B:[C]:7F85851E93E2566D35BA3589DFFB85A989DF0D36AFC3AE0F73C38711EB3FF1A2", "D": "B:[D]:B5963A050C12EF4F76D99AE60DDDBE622C5F6C4969D9A37F61F48741E548555E", "E": "B:[E]:48EC2512AF1E0B8482897396C4930A8BE23C267DC09017CB2118A08CED11371B", "F": "B:[F]:90AB8E4FA3E1F4AF811F5D1EA4A5B0F260BF4083CABE98A50F5E8CE261EFFD39", "0": "B:[0]:71269F348FF21B0DD22F933E1639205B37CA9BDEC18D9503449EBA49E077D88D", "1": "B:[1]:C662AD97DF0DC3A24843D1A5716AC5E1417C3B7C3D5A106E22D138BD59EA0BF4", "2": "B:[2]:BE803BB6BF2A44E6AB6ED3294D1A21592165575D2732BA473B0260C1435039E0", "3": "B:[3]:95D4AEBDEE5CC7FB6A166AE875E42C8BC9D28F96B9907ACBA4D75F6E33EE9059", "4": { "A": "B4:[A]:496656EEF74F6CC69E4A094348A14F9A0E308E7DB77392F8FCE01ECA897D42E0", "B": "B4:[B]:43401DAC8CEA94165345BEDD146608FBB691F5B75A146E9F3BD7AA51E44C830F", "C": "B4:[C]:071CE62735032A2C5F3B6E364A1690F3244A9477CFB7147F10DF6CA5602A6F58", "D": "B4:[D]:8BE590D3B697C4F6D4FF7FE9CF26DC32818D21192A95CE27218677CE14FF7701", "E": "B4:[E]:E02B462E00825E821875C96F02062C330A24A3AA0246D2682F68535571F9AD7B", "F": "B4:[F]:8430F8A114938A48311BF825F4B858994851B6F4A13D1FB74A572531818A4B60", "0": "B4:[0]:55F48EF8DFE1E4DCF21F7C1364DFAD3386B2EA2577F23B615B7962122028CE78", "1": "B4:[1]:CB8D24EFF5CB04803A570AC477B59AFE9BADEB840A15ECFBBC85AABDEDADF91B", "2": "B4:[2]:01C6AC647F4DC35EE550BE20108EA58B20EED6311896740FB1E75361B300EC96", "3": "B4:[3]:D151CAD5833891AA0C691290E065577C96D81E56D7340A2212E7680E471D92C9", "4": "B4:[4]:C56334648E78CCA63F41ADD08047A540D89B87C2CF9208C66A7ECE4B5A7620AF", "5": "B4:[5]:3377879BC45CF459ABB8CC0459084062DF7AF9434ACBE388793C19B04178BA7A", "6": "B4:[6]:020EB223F688D8EC68FBDEF0482A7532C5DA5E5C853971CD7C87522B8E47198A", "7": "B4:[7]:CE6947F410F5E37C1D082F3B03AFE61484E0F189C42C0AEE33D0B315756FCE87", "8": "B4:[8]:E817D44A59F52B849E6A0E45D805215C3C399165463DAED067DED99973F994F1", "9": { "A": "B49:[A]:FB764F47E99AC18CFC1483DD7A2C96F2ADA2947CBEEF056379889701A38A9E8A", "B": "B49:[B]:D92AE70C5BFBFF4C339CC2380D78975B370FD03403ACEED08BE751C24BE033E1", "C": "B49:[C]:FD4EE1931837B39D69F4F52A8C107C0DF172A869907A5B2DC60E3DEBB16FA04D", "D": "B49:[D]:5CD6F38CA9265B67068C010D1EB3BED5E6060B7FB8F974F321D445F344347234", "E": "B49:[E]:68955EE615988C52FE8F22495DFE5B4F89B0FE077E88FFB1336D27A2B5C206E9", "F": "B49:[F]:EDE05B18D0CBB9CAD5047C94F8D5FC1E4B9A42E617001D18BAFFFACDCFE22196", "0": "B49:[0]:DEC049E3D39A62410C1FE40522B98E2A26C4FC4398499DE02920A4E4BBD6310F", "1": "B49:[1]:80B2D03DFBEF3C93A0CB1E16BE4476CAFD9055D0ACA9CD3D35A64C85A3E41276", "2": "B49:[2]:6E48F5592F80F859D88F938F18D3833417441025FDAE5B78610103F16D5CB079", "3": "B49:[3]:5A19738F551EECBAAC414B3822D35E12C6048257C7133BEB02797E251B9CA498", "4": "B49:[4]:AABBD08A156F400E82C7FC0DD62F495346ADE7C779F264B045DADB30F3D5446A", "5": "B49:[5]:0B5802E1ED95887AB4E2902FA74946CF5C4C925751425D15AADFD2B765FDBA65", "6": "B49:[6]:32285804941329895799B7B90F278733355707311FDE8F568C5234BC0FB2668A", "7": { "A": "B497:[A]:EE8672511E69034BE0C532B197F2481A73FB1FD9EB325F7C52DBA25B4121E29D", "B": "B497:[B]:FF9EA66C97A4F0CA46F80E0EA99100B723FB5B91869796BC3D7D2F2CFB31473E", "C": "B497:[C]:4A532616414FBF25644D8583968003C70FD81A1C17F94030B0EF1876DED82852", "D": "B497:[D]:324070B37766558F754B5E7B1754B9DA953C680292F237CC76A46BB036F12A76", "E": "B497:[E]:2FD03A5F2116DAB43F3CC17BD3D9B071435572C8EE85FD9D698C2AAE4C67E976", "F": "B497:[F]:76D86D33FEE1CFA6A8106888232B0B3C69391A18A6DB4F6338753CEC57141839", "0": "B497:[0]:B0C791EB62162ED8B8A04D2418ADD208F5E89DC819092A9CDE2892AD641489C6", "1": "B497:[1]:A829BB3E1883F398C28D08B86B80DED8832524F082216B0CB4F6919A2E9D7875", "2": "B497:[2]:257BC250B6BC99BDB25D189C2F8D9CC02B5A9A0BF8FCDB1CB763E97E7CA24160", "3": "B497:[3]:D15222C51C0FB14FE37CCD0BC925A9EA188420534BC5E5C859819B7410C01BCF", "4": "B497:[4]:C24FDBA15C613B6846C1E9D352F2AD6229C13D5500FAC26170744F3518F48AA9", "5": "B497:[5]:E69602E1EE48F97B4940D0751B7F1CDEA8216E2579EC4D0BC803986029F08A01", "6": "B497:[6]:CD205E0496ADCB044272D6CF6B04F7038E7172AEBDBAE4498600912917C95371", "7": "B497:[7]:FF7754043AE72092765217B362257B49B5A89E21CC1B84D970991FD629A6C2F1", "8": "B497:[8]:D31289FB6D22A386C4571C67C23FD09D0C04C669AA44BE59A301C29619A5798D", "9": { "0": "B4979:[0]:E443B260B087E61CCF81F546491A57A7A5DEBC91BBECA36FA51240F3F5887654", "1": "B4979:[1]:47CD5F658C7906C0E49D488D7B4E7007FDBD78AA76413E134D7D5574B0F520EC", "A": "B4979:[A]:0BCBCE5C48B64397877CB9C3307E1B428E1223E534DDE529243E3ABFAFC269F3", "B": "B4979:[B]:2ECE26DCBB5835C88890739308E7A83CE356AE892DF31D49418C872ACF75B27E", "3": "B4979:[3]:847FB6F72D62A1E850A2D6A3C62722996B5B6E23B685E7293488C313D30CCA2A", "D": "B4979:[D]:E0581B897F71795510191ADFBC13FF379B186A14AE188FBAC8719BBB95DCEBB9", "5": "B4979:[5]:1622291E9F82DDB7A446E13E74A26656E2DA7C5DD19215D09CFDB1797188D593", "F": "B4979:[F]:B9FCE66B23F1C30E653FF05527925EEECAC08C96F5604AD27A408F71729BDBBC", "7": "B4979:[7]:2F5B7DF2CFE215D5099BF38B131700600EB22DBBEC4677A09116BC70E8B3D5C2", "8": "B4979:[8]:1BAAB51079DF064D194B50268E7415ED3907C9C26D1A1FCD3E5D0C6BCBEDDF8B" } }, "8": "B49:[8]:ED664A0457677B05C5422ECC481018302C41D0EA88985FBD27F9C8DCFBCA1DE3", "9": "B49:[9]:0F0D8ED0C666265B87A01D7CAB0108C0A07206EC6615F66E02394A8FC4F43280" } }, "5": "B:[5]:4493E61EB2287E9715DB7D530AE34DB2524AF53A3284410F03F0E7550FADCC7E", "6": "B:[6]:CC62BF8D278D2735D25B25C56F9A4DB242B727679DD6D35255BC4CA62E3805BC", "7": "B:[7]:B3243F6C36ECFB4E0B02FDB7C1103F5A2C1F895446940764273CBF772B2DD0D5", "8": "B:[8]:047EE3EF648F4AEFABD64CC524147EB45E84EA2C9538A830EE82F4277A469570", "9": "B:[9]:E48AFD7C8F74EBD0BB2C6A9FA984F8F878F8C4D30E9C9481BB1FA5AF933E1C39" }, "C": "[C]:161DCAAB6F2D7744D100DF03B577F5D5A674CDF3F53B4DFE3DDB746DDCB01649", "D": "[D]:32F18914492F4D5ECCC8FF79114161F964423122874D83A4B8501DFD2E6E10FC", "E": "[E]:FDEA9F06C1A96E707C7D8D56354FFAA2AFFBB8C91A0AA611081C35AB5135F9D3", "F": "[F]:8153C4E9F3B549AB670371DD369D7960DA80BD6FCEEC903A476E194BBECA1DBC", "0": "[0]:194D9DC1EEAFB92EA37DD24F94913E55D72FED960628A4BA3440A2436C371A01", "1": "[1]:1949034BC4BA6CD9CC83080A93CC065897AF068FDDC225569717B88F26E8BF2D", "2": "[2]:DAABD7276F5A021C3E32A6A60346045815836D49EEA76CF03AE7E3632897B741", "3": "[3]:E7E791571DE8A97C32BFD46C257305DB4CB4DE83CA599175339AE65F7D663F26", "4": "[4]:31AC7CEE5D5C9F47DAB3F44DBE589FB2B2356CEC091E086E6F2DA3770A5DB42D", "5": "[5]:B99E0A22D5B05D8EAFDEB028367AD9C13C6FF44FC45161A91532DC38D61C0438", "6": "[6]:223E036509E9335799A2E101D0C0F7A1581F22B800FA52516FC0B73594C4F025", "7": "[7]:CF0C45AF31303A193B0688E357D018CA40491A166FE627457B1ABACC0F25B8DB", "8": "[8]:5AC7C782A604FD1EDA3F96B191E2041EF5F7CB1E1AED19790E4B8EB2E4698866", "9": "[9]:C756D649FC378010BCAB9B9706C51CF586780DAE462A8C16DA83D8326FCD0E33" } ```

0 replies

sublimator · 2023-10-25T22:31:41Z

sublimator
Oct 25, 2023

I am not sure I am following you exactly but certainly "just" ledger headers (rather than LedgerHashes or combo ) would be a simple/logical bolt-on to xpop as it stands. Even for a v1.1? As for subsequent versions it might be nice to separate the ledger validations part so you could validate account state related data. xpox? 360?

1 reply

wojake Oct 26, 2023

here for the next xbox 360 😃

sublimator · 2023-10-26T06:46:42Z

sublimator
Oct 26, 2023

padame: you mean xpov right? anakin: xpox ...

0 replies

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

0041 XLS-41d: XRPL Proof of Payment Standard (XPOP) #107

{{title}}

{{editor}}'s edit

{{editor}}'s edit

Replies: 9 comments 5 replies

{{title}}

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{title}}

Select a reply

0041 XLS-41d: XRPL Proof of Payment Standard (XPOP) #107

RichardAH May 4, 2023 Maintainer

XLS-41d

Abstract

Background

Proof

Format

Verifying

Replies: 9 comments · 5 replies

Worst-Case Scenario for Ledger Validation

1. Validated Ledger Components

2. Additional Ledger Information

3. Abbreviated Account State Trees

RichardAH Oct 25, 2023 Maintainer Author

RichardAH
May 4, 2023
Maintainer

Replies: 9 comments 5 replies

RichardAH
Oct 25, 2023
Maintainer Author