📅 Original date posted:2014-01-07
📝 Original message:Le 07/01/2014 01:21, Mark Friedenbach a écrit :
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 01/06/2014 10:13 AM, Peter Todd wrote:
>> On Sun, Jan 05, 2014 at 07:43:58PM +0100, Thomas Voegtlin wrote:
>>> I have written a Python-levelDB implementation of this UTXO
>>> hashtree, which is currently being tested, and will be added to
>>> Electrum servers.
>> Along the lines of my recent post on blockchain data:
>>
>> Is it going to be possible to do partial prefix queries on that
>> tree?
> There's really two tree structures being talked about here. Correct me
> if I'm wrong Thomas, but last time I looked at your code it was still
> implementing a 256-way PATRICIA trie, correct? This structure lends
> itself to indexing either scriptPubKey or H(scriptPubKey) with
> approximately the same performance characteristics, and in the
> "Ultimate blockchain compression" thread there is much debate about
> which to use.
You are right. The 256-way branching follows from the fact that
the tree was implemented using a key-value database operating
with byte strings (leveldb). With this implementation constraint,
a different branching would probably be possible but wasteful.
My recent code creates one leaf per unspent, and uses 56-byte
keys built as:
H(scriptPubKey) + txid + txpos
(This is not pushed yet, it needs cleanup. Previous code created one
leaf per address)
Partial prefix queries are possible with database iterators.
> In the process of experimentation I've since moved from a 256-way
> PATRICIA trie to a bitwise, non-level-compressed trie structure - what
> I call proof-updatable trees in the BIP. These have the advantage of
> allowing stateless application of one proof to another, and as
> consequence enable mining & mempool operations without access to the
> UTXO set, so long as proofs are initially provided in the transaction
> & block wire format.
I see the advantage of doing that, but this looks really far-fetched..
My understanding is that it would require a complete change in the
way clients and miners work. Could such a change be brought iteratively?
Thomas Voegtlin [ARCHIVE] /
npub10f…7ej47
2023-06-07 15:11:31
in reply to nevent1q…6tyy
Author Public Key
npub10f96gqrsu4qpygfgvuvzce47aavjvql703egfde0l2hua8dzpszs67ej47Published at
2023-06-07 15:11:31Event JSON
{
"id": "a052640f9bc46ecfcf92063a99001570cf3fe2c80b5408c781732650e058d6aa",
"pubkey": "7a4ba40070e54012212867182c66beef592603fe7c7284b72ffaafce9da20c05",
"created_at": 1686150691,
"kind": 1,
"tags": [
[
"e",
"83737b7085425ef39b74eda6741f7cc83d1a1767299a10c924d05e01209d8eea",
"",
"root"
],
[
"e",
"c3820eedcf718354342d28df7c3eedc24a80118eded89f9c11016e8f3f118681",
"",
"reply"
],
[
"p",
"1c61d995949cbfaf14f767784e166bde865c7b8783d7aa3bf0a1d014b70c0069"
]
],
"content": "📅 Original date posted:2014-01-07\n📝 Original message:Le 07/01/2014 01:21, Mark Friedenbach a écrit :\n\u003e -----BEGIN PGP SIGNED MESSAGE-----\n\u003e Hash: SHA1\n\u003e\n\u003e On 01/06/2014 10:13 AM, Peter Todd wrote:\n\u003e\u003e On Sun, Jan 05, 2014 at 07:43:58PM +0100, Thomas Voegtlin wrote:\n\u003e\u003e\u003e I have written a Python-levelDB implementation of this UTXO\n\u003e\u003e\u003e hashtree, which is currently being tested, and will be added to\n\u003e\u003e\u003e Electrum servers.\n\u003e\u003e Along the lines of my recent post on blockchain data:\n\u003e\u003e\n\u003e\u003e Is it going to be possible to do partial prefix queries on that\n\u003e\u003e tree?\n\u003e There's really two tree structures being talked about here. Correct me\n\u003e if I'm wrong Thomas, but last time I looked at your code it was still\n\u003e implementing a 256-way PATRICIA trie, correct? This structure lends\n\u003e itself to indexing either scriptPubKey or H(scriptPubKey) with\n\u003e approximately the same performance characteristics, and in the\n\u003e \"Ultimate blockchain compression\" thread there is much debate about\n\u003e which to use.\n\nYou are right. The 256-way branching follows from the fact that\nthe tree was implemented using a key-value database operating\nwith byte strings (leveldb). With this implementation constraint,\na different branching would probably be possible but wasteful.\n\nMy recent code creates one leaf per unspent, and uses 56-byte\nkeys built as:\n\n H(scriptPubKey) + txid + txpos\n\n(This is not pushed yet, it needs cleanup. Previous code created one \nleaf per address)\n\nPartial prefix queries are possible with database iterators.\n\n\u003e In the process of experimentation I've since moved from a 256-way\n\u003e PATRICIA trie to a bitwise, non-level-compressed trie structure - what\n\u003e I call proof-updatable trees in the BIP. These have the advantage of\n\u003e allowing stateless application of one proof to another, and as\n\u003e consequence enable mining \u0026 mempool operations without access to the\n\u003e UTXO set, so long as proofs are initially provided in the transaction\n\u003e \u0026 block wire format.\n\nI see the advantage of doing that, but this looks really far-fetched..\nMy understanding is that it would require a complete change in the\nway clients and miners work. Could such a change be brought iteratively?",
"sig": "3e036542a3029b82dd2643512f9fa608ba733050286384b9886c970d215c05829e3819fedb56c27f5f91df45b4c0a8d65062ea4b2875d8dc15e2ab07f04e3083"
}