📅 Original date posted:2014-01-06
📝 Original message:-----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.
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.
The "disadvantage" is that performance is closely tied to key length,
making H(scriptPubKey) the much more desirable option. I'm sure you
see that as an advantage, however :)
> Also have you considered creating per-block indexes of all
> scriptPubKeys, spent or unspent, queryable via the same partial
> prefix method?
This would be quite easy to do, separate from the UTXO structure but
using the same trie format.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.14 (GNU/Linux)
Comment: GPGTools - http://gpgtools.org
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
iQIcBAEBAgAGBQJSy0iFAAoJEAdzVfsmodw434MQAIA/fDYT7SfMtfLEgDQKhXCn
slRqFEx/HXjvgHHSYnbr9V+8LrGzNvT2ImebbV9ge8VlziAFNGIUq2EYhFs4kHWu
GVm9aL8Jj/27SvM0tRwr9n2XIifKOh2sVINAjbv+UwPv/O+cULU95/b53DEF6aqI
OWxioOR50TPe4t9AevAGVypNLm1DsyDdymhO9xyBN92xGTNj5QKL5hHG3kcsLIl1
7KaxO0w4UC2sdSGj9FeyH1b0zYg8FlzjJHc1CUshHwUwyYo8LRJtRypL5lrayERg
Er/kIGEDovcenNBW8G79l+8VKPfB/lMTssT2pDiQL+1e1fg46CIQxHSyap2JSFTE
jgleRk/+1NK/ZjOQ8dEBPZK3TE1WY3qlm/ekjG/8W5kXqcxzFBoAkeBNXuJ/8UMi
mKe+DTmbp0xnvLO1p+hpugXKfrQSpcFL+ZvJHlFS1lz7O1N3WvuDCNP9El+L6ueM
nFzjr1NTnX0z4vYtscI7qBKVqUrB7Z84c3O/lSYpw4Jilxl4trzV4cn7+AF7KWGM
ktR9JJeIoNcJ2Zx4EpRp6OSwhtLkWZyLpPnidQ2p6ev2ytXpTpGsW/i5XS2w57UD
2IG5E0Q7Xzvd58lI/YollWQcagVOZdyzYXa+wVZoFQ6gLF47andpUmtUJOhI7gxv
T/rWhPhkTMUn8TdvUcV/
=N9zM
-----END PGP SIGNATURE-----
Mark Friedenbach [ARCHIVE] /
npub1r3…48d0u
2023-06-07 15:11:30
in reply to nevent1q…mp0c
Author Public Key
npub1r3san9v5njl6798hvauyu9ntm6r9c7u8s0t65wls58gpfdcvqp5sa48d0uPublished at
2023-06-07 15:11:30Event JSON
{
"id": "c3820eedcf718354342d28df7c3eedc24a80118eded89f9c11016e8f3f118681",
"pubkey": "1c61d995949cbfaf14f767784e166bde865c7b8783d7aa3bf0a1d014b70c0069",
"created_at": 1686150690,
"kind": 1,
"tags": [
[
"e",
"83737b7085425ef39b74eda6741f7cc83d1a1767299a10c924d05e01209d8eea",
"",
"root"
],
[
"e",
"302ed3e5e20ea212fd9e96ff73ec5cfc0469314a20723cbb4e6c638152868a8c",
"",
"reply"
],
[
"p",
"daa2fc676a25e3b5b45644540bcbd1e1168b111427cd0e3cf19c56194fb231aa"
]
],
"content": "📅 Original date posted:2014-01-06\n📝 Original message:-----BEGIN PGP SIGNED MESSAGE-----\nHash: SHA1\n\nOn 01/06/2014 10:13 AM, Peter Todd wrote:\n\u003e On Sun, Jan 05, 2014 at 07:43:58PM +0100, Thomas Voegtlin wrote:\n\u003e\u003e I have written a Python-levelDB implementation of this UTXO\n\u003e\u003e hashtree, which is currently being tested, and will be added to\n\u003e\u003e Electrum servers.\n\u003e \n\u003e Along the lines of my recent post on blockchain data:\n\u003e \n\u003e Is it going to be possible to do partial prefix queries on that\n\u003e tree?\n\nThere's really two tree structures being talked about here. Correct me\nif I'm wrong Thomas, but last time I looked at your code it was still\nimplementing a 256-way PATRICIA trie, correct? This structure lends\nitself to indexing either scriptPubKey or H(scriptPubKey) with\napproximately the same performance characteristics, and in the\n\"Ultimate blockchain compression\" thread there is much debate about\nwhich to use.\n\nIn the process of experimentation I've since moved from a 256-way\nPATRICIA trie to a bitwise, non-level-compressed trie structure - what\nI call proof-updatable trees in the BIP. These have the advantage of\nallowing stateless application of one proof to another, and as\nconsequence enable mining \u0026 mempool operations without access to the\nUTXO set, so long as proofs are initially provided in the transaction\n\u0026 block wire format.\n\nThe \"disadvantage\" is that performance is closely tied to key length,\nmaking H(scriptPubKey) the much more desirable option. I'm sure you\nsee that as an advantage, however :)\n\n\u003e Also have you considered creating per-block indexes of all \n\u003e scriptPubKeys, spent or unspent, queryable via the same partial\n\u003e prefix method?\n\nThis would be quite easy to do, separate from the UTXO structure but\nusing the same trie format.\n-----BEGIN PGP SIGNATURE-----\nVersion: GnuPG v1.4.14 (GNU/Linux)\nComment: GPGTools - http://gpgtools.org\nComment: Using GnuPG with Thunderbird - http://www.enigmail.net/\n\niQIcBAEBAgAGBQJSy0iFAAoJEAdzVfsmodw434MQAIA/fDYT7SfMtfLEgDQKhXCn\nslRqFEx/HXjvgHHSYnbr9V+8LrGzNvT2ImebbV9ge8VlziAFNGIUq2EYhFs4kHWu\nGVm9aL8Jj/27SvM0tRwr9n2XIifKOh2sVINAjbv+UwPv/O+cULU95/b53DEF6aqI\nOWxioOR50TPe4t9AevAGVypNLm1DsyDdymhO9xyBN92xGTNj5QKL5hHG3kcsLIl1\n7KaxO0w4UC2sdSGj9FeyH1b0zYg8FlzjJHc1CUshHwUwyYo8LRJtRypL5lrayERg\nEr/kIGEDovcenNBW8G79l+8VKPfB/lMTssT2pDiQL+1e1fg46CIQxHSyap2JSFTE\njgleRk/+1NK/ZjOQ8dEBPZK3TE1WY3qlm/ekjG/8W5kXqcxzFBoAkeBNXuJ/8UMi\nmKe+DTmbp0xnvLO1p+hpugXKfrQSpcFL+ZvJHlFS1lz7O1N3WvuDCNP9El+L6ueM\nnFzjr1NTnX0z4vYtscI7qBKVqUrB7Z84c3O/lSYpw4Jilxl4trzV4cn7+AF7KWGM\nktR9JJeIoNcJ2Zx4EpRp6OSwhtLkWZyLpPnidQ2p6ev2ytXpTpGsW/i5XS2w57UD\n2IG5E0Q7Xzvd58lI/YollWQcagVOZdyzYXa+wVZoFQ6gLF47andpUmtUJOhI7gxv\nT/rWhPhkTMUn8TdvUcV/\n=N9zM\n-----END PGP SIGNATURE-----",
"sig": "cbb136b3411d46013d35f3ddd34433f586318c04fe1401fd51b80b355678742dd77ac9ef08d86baeb8ab37320abf2cb4d98bf93b36bf564ffb65ce43965d63f7"
}