Skip to content

Latest commit

 

History

History
177 lines (151 loc) · 18.4 KB

specification.md

File metadata and controls

177 lines (151 loc) · 18.4 KB
Raw

Proveth proof-blob format specification

Table of Contents

Throughout this document, we will use zero-based indexing and refer to the initial element of a sequence as the zeroth element.

We also assume that you're somewhat familiar with Ethereum's RLP encoding and Merkle-Patricia-Tries.

Proof kind

Every proveth proof-blob is an RLP-encoded list. The zeroth element of the list is a uint that specifies the kind of proof the proof-blob represents:

[kind, actual proof...]

Currently we support two types of proofs:

  • Type 1 proofs of inclusion/exclusion for the transaction requests aka transactions.
  • Type 2 proofs of inclusion/exclusion for the transaction outcomes aka transactions receipts.

Proof of transaction (receipt) inclusion/exclusion

A proof of inclusion proves a statement of the form "the given transaction is present at the given index in the given block". A proof of exclusion proves a statement of the form "there is no transaction at the given index in the given block". Replace "transaction" with "transaction receipt" in the previous sentence in case of a proof of type 2.

A proof consists of 4 elements:

  • 0: kind equals 1 for transactions and equals 2 for transaction receipts.
  • 1: consensus block header, consisting of 
    [<hash of previous block>,
 <uncles hash>,
 <miner address>,
 <state root hash>,
 <transactions root hash>,
 <receipts root hash>,
 <logs bloom filter>,
 <difficulty>,
 <number>,
 <gas limit>,
 <gas used>,
 <timestamp>,
 <extra data>,
 <mix hash>,
 <nonce>]
  • 2: transaction index (zero-based, i.e. the initial transaction in the block has index 0)
  • 3: Merkle-Patricia-Trie nodes on the path to the transaction. Each node is a list of length 2 (for extension and leaf nodes) or a list of length 17 (for branch nodes).

Examples

For better readability, we hex-encode all bytestrings in the examples below.

You can use the following python functions to decode and encode the proof-blobs in the examples:

import rlp

def decode_proof_blob(hex_blob):
    blob = bytes.fromhex(hex_blob)
    return rec_hex(rlp.decode(blob))

def encode_proof_blob(list):
    blob = rlp.encode(rec_bin(list))
    return blob.hex()

def rec_hex(x):
    if isinstance(x, list):
        return [rec_hex(elem) for elem in x]
    else:
        return x.hex()

def rec_bin(x):
    if isinstance(x, list):
        return [rec_bin(elem) for elem in x]
    elif isinstance(x, int):
        return x
    elif isinstance(x, str):
        if x.startswith("0x"):
            return bytes.fromhex(x[2:])
        else:
            return bytes.fromhex(x)

Transaction 0 of block 5000000 (mainnet)

This is proof-blob for transaction 0 of block 5000000 on the mainnet:

'f9039601f90204a0cae4df80f5862e4321690857eded0d8a40136dafb8155453920bade5bd0c46c0a01dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d4934794b2930b35844a230f00e51431acae96fe543a0347a06092dfd6bcdd375764d8718c365ce0e8323034da3d3b0c6d72cf7304996b86ada091dfce7cc2174482b5ebcf6f4beedce854641982eadb1a8cf538e3206abf7836a06db67db55d5d972c59646a3bda26a39422e71fe400e4cdf9eb7f5c09b0efa7d0b901008584009c4dd8101162295d8604b1850200788d4c81f39044821155049d2c036a8a00d07f2a10383180984400b0290ba00293400c1d414a5018104a010220101909b918c601251215109755b90003c6a2c23490829e319a506281d9641ac39a840d3aa03e4a287900e0c09641594409a2010543016e966382c02040754030430e2d708316ec64008f0c0100c713b51f8004005bd48980143e08b22bf2262365b8b2658804a560f1028207666d10288144a5a14609a5bcb221280b13da2f4c8800d8422cc27126a46a04f08c00ca9004081d65cc75d10c62862256118481d2e881a993780808e0a00086e321a4602cb214c0044215281c2ccbca824aca00824a8087090c21c56929b2834c4b40837a121d8379fac5845a70760d83743132a094cd4e844619ee20989578276a0a9046877d569d37ba076bf2e8e34f76189dea884617a20003ba3f2580f9018af90111a0915214954ddbb2b08a9d9de48b2bc31289d3bda55b8f017242f376ff8df56b93a00106fad9e6c0d6c92e84893ba3c26aba93b4e2a1ab3fa52587a6946b7eedebada074fd2bf3665a2576317a74c0215cd4ac19ee0305191df1ae5f5eaa6788c2a9a9a04157e0398ade02f9acf5e4183d5c554af0e39387b7f5c4da6990b3df177ddd32a013e1c573e8e8f09e3d23d30ccfccbafd4ef9666f7df578999bdc5b9c65bdcc80a041a8eb6c4616c8e12c56a6fafbe9013478e14bce6afad04f9b28f47bdcb5373aa09c08f2a7050bdd3e0d6922ff9c8ce801436afcd078a79df6ffae267a2a755b0b80a012e7ff44f271d1f5968b23a258b21f703cacfe3061e0fafe9ea04b810537a6068080808080808080f87430b871f86f820fef851f3305bc008301d8a89488a690553913a795c3c668275297635b903a29e5882c250d42400204008025a05df5034c46551b630553201581bd690e021c13b3134f37d14eb19ea971292a39a04f263a9ef7b6e6d18d1b6c120f051e51aa737e12aabcf9466377779eb60656a9'

When we decode it, we get the following:

[
  # kind
  1,
  # consensus block header
  # '91dfce7cc2174482b5ebcf6f4beedce854641982eadb1a8cf538e3206abf7836' is the hash of the transaction Merkle-Patricia-Trie
  ['cae4df80f5862e4321690857eded0d8a40136dafb8155453920bade5bd0c46c0', '1dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d49347', 'b2930b35844a230f00e51431acae96fe543a0347', '6092dfd6bcdd375764d8718c365ce0e8323034da3d3b0c6d72cf7304996b86ad', '91dfce7cc2174482b5ebcf6f4beedce854641982eadb1a8cf538e3206abf7836', '6db67db55d5d972c59646a3bda26a39422e71fe400e4cdf9eb7f5c09b0efa7d0', '8584009c4dd8101162295d8604b1850200788d4c81f39044821155049d2c036a8a00d07f2a10383180984400b0290ba00293400c1d414a5018104a010220101909b918c601251215109755b90003c6a2c23490829e319a506281d9641ac39a840d3aa03e4a287900e0c09641594409a2010543016e966382c02040754030430e2d708316ec64008f0c0100c713b51f8004005bd48980143e08b22bf2262365b8b2658804a560f1028207666d10288144a5a14609a5bcb221280b13da2f4c8800d8422cc27126a46a04f08c00ca9004081d65cc75d10c62862256118481d2e881a993780808e0a00086e321a4602cb214c0044215281c2ccbca824aca00824a80', '090c21c56929b2', '4c4b40', '7a121d', '79fac5', '5a70760d', '743132', '94cd4e844619ee20989578276a0a9046877d569d37ba076bf2e8e34f76189dea', '4617a20003ba3f25'],
  # transaction index
  0,
  # Merkle-Patricia-Trie nodes on path to transaction
  # the 8t element of the zeroth node is '12e7ff44f271d1f5968b23a258b21f703cacfe3061e0fafe9ea04b810537a606', which is the hash of the first node
  # the 1st element of the first node is 'f86f820fef851f3305...6377779eb60656a9', which is the rlp-encoded transaction
  [
    # Root node in the transaction Merkle-Patricia-Trie (this is a "branch node")
    ['915214954ddbb2b08a9d9de48b2bc31289d3bda55b8f017242f376ff8df56b93', '0106fad9e6c0d6c92e84893ba3c26aba93b4e2a1ab3fa52587a6946b7eedebad', '74fd2bf3665a2576317a74c0215cd4ac19ee0305191df1ae5f5eaa6788c2a9a9', '4157e0398ade02f9acf5e4183d5c554af0e39387b7f5c4da6990b3df177ddd32', '13e1c573e8e8f09e3d23d30ccfccbafd4ef9666f7df578999bdc5b9c65bdcc80', '41a8eb6c4616c8e12c56a6fafbe9013478e14bce6afad04f9b28f47bdcb5373a', '9c08f2a7050bdd3e0d6922ff9c8ce801436afcd078a79df6ffae267a2a755b0b', '', '12e7ff44f271d1f5968b23a258b21f703cacfe3061e0fafe9ea04b810537a606', '', '', '', '', '', '', '', ''],
    # 1st child of root node in the transaction Merkle-Patricia-Trie (this is a "leaf node")
    ['30', 'f86f820fef851f3305bc008301d8a89488a690553913a795c3c668275297635b903a29e5882c250d42400204008025a05df5034c46551b630553201581bd690e021c13b3134f37d14eb19ea971292a39a04f263a9ef7b6e6d18d1b6c120f051e51aa737e12aabcf9466377779eb60656a9']
  ]
]

Transaction 109 of block 5000000 (mainnet)

This is a proof of exclusion since no transaction with index 109 exists in block 5000000. Proof-blob:

f904d401f90204a0cae4df80f5862e4321690857eded0d8a40136dafb8155453920bade5bd0c46c0a01dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d4934794b2930b35844a230f00e51431acae96fe543a0347a06092dfd6bcdd375764d8718c365ce0e8323034da3d3b0c6d72cf7304996b86ada091dfce7cc2174482b5ebcf6f4beedce854641982eadb1a8cf538e3206abf7836a06db67db55d5d972c59646a3bda26a39422e71fe400e4cdf9eb7f5c09b0efa7d0b901008584009c4dd8101162295d8604b1850200788d4c81f39044821155049d2c036a8a00d07f2a10383180984400b0290ba00293400c1d414a5018104a010220101909b918c601251215109755b90003c6a2c23490829e319a506281d9641ac39a840d3aa03e4a287900e0c09641594409a2010543016e966382c02040754030430e2d708316ec64008f0c0100c713b51f8004005bd48980143e08b22bf2262365b8b2658804a560f1028207666d10288144a5a14609a5bcb221280b13da2f4c8800d8422cc27126a46a04f08c00ca9004081d65cc75d10c62862256118481d2e881a993780808e0a00086e321a4602cb214c0044215281c2ccbca824aca00824a8087090c21c56929b2834c4b40837a121d8379fac5845a70760d83743132a094cd4e844619ee20989578276a0a9046877d569d37ba076bf2e8e34f76189dea884617a20003ba3f256df902c8f90111a0915214954ddbb2b08a9d9de48b2bc31289d3bda55b8f017242f376ff8df56b93a00106fad9e6c0d6c92e84893ba3c26aba93b4e2a1ab3fa52587a6946b7eedebada074fd2bf3665a2576317a74c0215cd4ac19ee0305191df1ae5f5eaa6788c2a9a9a04157e0398ade02f9acf5e4183d5c554af0e39387b7f5c4da6990b3df177ddd32a013e1c573e8e8f09e3d23d30ccfccbafd4ef9666f7df578999bdc5b9c65bdcc80a041a8eb6c4616c8e12c56a6fafbe9013478e14bce6afad04f9b28f47bdcb5373aa09c08f2a7050bdd3e0d6922ff9c8ce801436afcd078a79df6ffae267a2a755b0b80a012e7ff44f271d1f5968b23a258b21f703cacfe3061e0fafe9ea04b810537a6068080808080808080f901b1a0926c9592f6e3f3fdb9510de57fb60b0413fa0e8c9bc9b3ae25536487354a136ca078df5aef8d73d86c9c875323a90584e70638b590bb9314ebb91a010a7f3b0874a0e86be9fc7f24962a2a5872b4aac6fbe62149b11e787982b3b89f3f59ba6e68d9a0277156f773f0db978ce9a8248447188868ac05a13fb5d3fb595bf58ab715c58da0fbb50c6c762e920d12b36be8e6cf3f62fc15bed2b3826a9295dde31e0eaca92aa0d252a56cb1f2ff5d8beb51cd7e38d8e9bbf113e6719628e8cab574fba68a33cda03d6db3090e80411df76c76aabed90a36ecbb7ca78d4dcbdbd45787ebac96adeba04ce247a831382c25b3cecf5824077af5d8340d2f531343da143a8f24b5623c91a008b5b9bad14b02c79370f9b741b7051a195301773aac7ff7fbf626c95e9fa89ca0cfeb46c773370ca40ccba0066d4685bb8ffa58a8b471748f22fc1f04c07f20fda03905a9d97fccfb9e5d2a0b9030dc32da7e461bd90eb66179368ac5ac5f913e80a02c042434f04cfcca5f418778fe9fcb05e753a1437a1a636000d021a90c6e2643a06ff3f067699fdcf7d7a76c61988dc152ba52984eb5230d15db058c7f04447cf980808080

Decoded proof-blob:

[
  # kind
  '01',
  # consensus block header
  # '91dfce7cc2174482b5ebcf6f4beedce854641982eadb1a8cf538e3206abf7836' is the hash of the transaction Merkle-Patricia-Trie
  ['cae4df80f5862e4321690857eded0d8a40136dafb8155453920bade5bd0c46c0', '1dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d49347', 'b2930b35844a230f00e51431acae96fe543a0347', '6092dfd6bcdd375764d8718c365ce0e8323034da3d3b0c6d72cf7304996b86ad', '91dfce7cc2174482b5ebcf6f4beedce854641982eadb1a8cf538e3206abf7836', '6db67db55d5d972c59646a3bda26a39422e71fe400e4cdf9eb7f5c09b0efa7d0', '8584009c4dd8101162295d8604b1850200788d4c81f39044821155049d2c036a8a00d07f2a10383180984400b0290ba00293400c1d414a5018104a010220101909b918c601251215109755b90003c6a2c23490829e319a506281d9641ac39a840d3aa03e4a287900e0c09641594409a2010543016e966382c02040754030430e2d708316ec64008f0c0100c713b51f8004005bd48980143e08b22bf2262365b8b2658804a560f1028207666d10288144a5a14609a5bcb221280b13da2f4c8800d8422cc27126a46a04f08c00ca9004081d65cc75d10c62862256118481d2e881a993780808e0a00086e321a4602cb214c0044215281c2ccbca824aca00824a80', '090c21c56929b2', '4c4b40', '7a121d', '79fac5', '5a70760d', '743132', '94cd4e844619ee20989578276a0a9046877d569d37ba076bf2e8e34f76189dea', '4617a20003ba3f25'],
  # transaction index (0x6d == 119)
  '6d',
  # Merkle-Patricia-Trie nodes on path to transaction
  # the 6th element of the zeroth node is '12e7ff44f271d1f5968b23a258b21f703cacfe3061e0fafe9ea04b810537a606', which is the hash of the first node
  # the 13th element of the first node is '', which indicates that the node has no child in this position.
  # Hence there is no transaction with index 0x6d.
  [
    ['915214954ddbb2b08a9d9de48b2bc31289d3bda55b8f017242f376ff8df56b93', '0106fad9e6c0d6c92e84893ba3c26aba93b4e2a1ab3fa52587a6946b7eedebad', '74fd2bf3665a2576317a74c0215cd4ac19ee0305191df1ae5f5eaa6788c2a9a9', '4157e0398ade02f9acf5e4183d5c554af0e39387b7f5c4da6990b3df177ddd32', '13e1c573e8e8f09e3d23d30ccfccbafd4ef9666f7df578999bdc5b9c65bdcc80', '41a8eb6c4616c8e12c56a6fafbe9013478e14bce6afad04f9b28f47bdcb5373a', '9c08f2a7050bdd3e0d6922ff9c8ce801436afcd078a79df6ffae267a2a755b0b', '', '12e7ff44f271d1f5968b23a258b21f703cacfe3061e0fafe9ea04b810537a606', '', '', '', '', '', '', '', ''],
    # Note that the 0xd-th element of this Merkle-Patricia branch node is empty, indicating that no transaction exists
    ['926c9592f6e3f3fdb9510de57fb60b0413fa0e8c9bc9b3ae25536487354a136c', '78df5aef8d73d86c9c875323a90584e70638b590bb9314ebb91a010a7f3b0874', 'e86be9fc7f24962a2a5872b4aac6fbe62149b11e787982b3b89f3f59ba6e68d9', '277156f773f0db978ce9a8248447188868ac05a13fb5d3fb595bf58ab715c58d', 'fbb50c6c762e920d12b36be8e6cf3f62fc15bed2b3826a9295dde31e0eaca92a', 'd252a56cb1f2ff5d8beb51cd7e38d8e9bbf113e6719628e8cab574fba68a33cd', '3d6db3090e80411df76c76aabed90a36ecbb7ca78d4dcbdbd45787ebac96adeb', '4ce247a831382c25b3cecf5824077af5d8340d2f531343da143a8f24b5623c91', '08b5b9bad14b02c79370f9b741b7051a195301773aac7ff7fbf626c95e9fa89c', 'cfeb46c773370ca40ccba0066d4685bb8ffa58a8b471748f22fc1f04c07f20fd', '3905a9d97fccfb9e5d2a0b9030dc32da7e461bd90eb66179368ac5ac5f913e80', '2c042434f04cfcca5f418778fe9fcb05e753a1437a1a636000d021a90c6e2643', '6ff3f067699fdcf7d7a76c61988dc152ba52984eb5230d15db058c7f04447cf9', '', '', '', '']
  ]
]

Transaction 6000 of block 6027762 (mainnet)

This is a proof of exclusion since no transaction with index 6000 exists in block 6027762. Proof-blob:

f903ec01f90216a00947e6d3e6884ef3b6d54251200719e10c71d93b822be696afea9a1a2d93ae0ca01dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d4934794ea674fdde714fd979de3edf0f56aa9716b898ec8a093f095892d0c46d3f7c73989f29e910979c396dee9d0fc885f3407861eb96bf9a0758cb2c904e1229497d8d610a23ee5a4bc0d4968811d366029eb65c9d73d75dca0164b57685b6c40430979391aab93eb4945c782145f78b44ad7dbd3ef4ee33bebb9010002000000000200000000000000008002000000000000000004100010100000000000000000000000008000000001000000020000004000000000804000000000100000000000000000000000002000200000000400000000000200002002000004000000000000001100014000000000000000000000000000000400000000000000020000080000000000200090004000000000000000400020100000000100000010000000000080200200000005000000000800000000000000000000000000000004000000000000008000800200008040000000080120000008024000000000001000000000000004000000008000000000400008000000000040000010870c76cdc3636820835bf9f28379f3798379c749845b587d739565746865726d696e652d6177732d61736961312d32a0199d055cf2a0283e8362d40c538970d1c25b843cf284c70d134b69cd46636c2e88c2ae5ff80e4b9873821770f901ccf90131a0ba8ac26a1ecca80036646825fe83c23819b2826d21db47a8c4345fec9247366fa017d86d5d4ada9c618a533c4f396a653b230fb00aee249e4b408218d44e6ce519a02d49848c73d037a07e77379965b6197b42c90c15978c0959cd5c6a72397bf666a02bc76e23c38782cc0072173b7f1e985f6256c84d721747489a6e2390aa222462a00222513b6138798cf398dd32d1d7127da0a8d9caad87218b1927b7228aff3519a01a795302578a2619aee9f1c30c2417a6ae992d3563133093683bf9037971a7fba09d9221fd4ef863d040d9f724ad84e3268141a1caba51254f078fa53c3122276da07dbbb758386cd6410ca616d0c01294d53e741a088c71f7a0254db2633ea565a7a01acb734cb4301016fd8bd7e19cecf0ef6fd30d7f001404e690c847c0872b3f9e8080808080808080f871a0fb98cd012e9c6cd332d6c2895e39dbd2dbc376005950963fff1209e691b1a856a094af3f83b301d9e07550ed4c9c327d0ae3780de51899eb9e7d3adb2f7dab026ba0c0658d28f3e6f71e6d59b14cde67919cff0ed7908b3af848bec2eaaeb76ae29a8080808080808080808080808080e4820001a0b8433f2f0b1efd01978a094160436af2f1228050103ed93b64ea952f68eae807

Decoded proof-blob:

[
  # kind
  '01',
  # consensus block header
  # '758cb2c904e1229497d8d610a23ee5a4bc0d4968811d366029eb65c9d73d75dc' is the hash of the transaction Merkle-Patricia-Trie
  ['0947e6d3e6884ef3b6d54251200719e10c71d93b822be696afea9a1a2d93ae0c', '1dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d49347', 'ea674fdde714fd979de3edf0f56aa9716b898ec8', '93f095892d0c46d3f7c73989f29e910979c396dee9d0fc885f3407861eb96bf9', '758cb2c904e1229497d8d610a23ee5a4bc0d4968811d366029eb65c9d73d75dc', '164b57685b6c40430979391aab93eb4945c782145f78b44ad7dbd3ef4ee33beb', '02000000000200000000000000008002000000000000000004100010100000000000000000000000008000000001000000020000004000000000804000000000100000000000000000000000002000200000000400000000000200002002000004000000000000001100014000000000000000000000000000000400000000000000020000080000000000200090004000000000000000400020100000000100000010000000000080200200000005000000000800000000000000000000000000000004000000000000008000800200008040000000080120000008024000000000001000000000000004000000008000000000400008000000000040000010', '0c76cdc3636820', '5bf9f2', '79f379', '79c749', '5b587d73', '65746865726d696e652d6177732d61736961312d32', '199d055cf2a0283e8362d40c538970d1c25b843cf284c70d134b69cd46636c2e', 'c2ae5ff80e4b9873'],
  # transaction index (0x1770 == 6000)
  '1770',
  # Nodes on path:
  # the 8th element of the zeroth node is '1acb734cb4301016fd8bd7e19cecf0ef6fd30d7f001404e690c847c0872b3f9e', which is the hash of the first node
  # the 2nd element of the first node is 'c0658d28f3e6f71e6d59b14cde67919cff0ed7908b3af848bec2eaaeb76ae29a', which is the hash of the second node
  # the second node is an extension node with path [0,1], proving that no transaction exists at 080201070700.
  # the special index 'ff' indicates that this extension node diverges from the desired path 080201070700.
  [
    ['ba8ac26a1ecca80036646825fe83c23819b2826d21db47a8c4345fec9247366f', '17d86d5d4ada9c618a533c4f396a653b230fb00aee249e4b408218d44e6ce519', '2d49848c73d037a07e77379965b6197b42c90c15978c0959cd5c6a72397bf666', '2bc76e23c38782cc0072173b7f1e985f6256c84d721747489a6e2390aa222462', '0222513b6138798cf398dd32d1d7127da0a8d9caad87218b1927b7228aff3519', '1a795302578a2619aee9f1c30c2417a6ae992d3563133093683bf9037971a7fb', '9d9221fd4ef863d040d9f724ad84e3268141a1caba51254f078fa53c3122276d', '7dbbb758386cd6410ca616d0c01294d53e741a088c71f7a0254db2633ea565a7', '1acb734cb4301016fd8bd7e19cecf0ef6fd30d7f001404e690c847c0872b3f9e', '', '', '', '', '', '', '', ''],
    ['fb98cd012e9c6cd332d6c2895e39dbd2dbc376005950963fff1209e691b1a856', '94af3f83b301d9e07550ed4c9c327d0ae3780de51899eb9e7d3adb2f7dab026b', 'c0658d28f3e6f71e6d59b14cde67919cff0ed7908b3af848bec2eaaeb76ae29a', '', '', '', '', '', '', '', '', '', '', '', '', '', ''],
    ['0001', 'b8433f2f0b1efd01978a094160436af2f1228050103ed93b64ea952f68eae807']
  ]
]