š
Original date posted:2017-02-23
š Original message:On Thu, Feb 23, 2017 at 03:13:43PM -0800, Bram Cohen wrote:
> On Thu, Feb 23, 2017 at 9:53 AM, Chris Priest via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> >
> > What problem does this try to solve, and what does it have to do with
> > bitcoin?
> >
>
> I can't speak to MMRs (they look a bit redundant with the actual blockchain
> history to my eye) but circling back to utxo commitments, the benefits are
In what way do you see MMRs as redundant?
Remember that with UTXO commitments because access patterns are uniform, you'll
over time have a lot more "redundancy" in the form of lost-coins evenly spread
out across the whole keyspace.
> that it enables actual proofs of non-fraud: You can prove the validity of a
> block based on just the previous block (and maybe some previous headers
> because of mining rewards) and can prove to a light node that a utxo hasn't
> been spent yet.
>
> A major factor in the way of getting utxo commitments in blocks is
> performance. The txo set is of course vastly larger and more unwieldy. If
That statement is incorrect with pruning: you can maintain a commitment to the
TXO set, without actually storing the entire TXO set, because you don't need to
store anything for nodes that have already been spent.
Concretely, this can be done with nothing more than adding a FullySpent node
type to the MMR definition I published earlier, with the rule being that only a
left or right child of an inner node be a FullySpent node, not both; if both
sides are spent, the inner node itself becomes FullySpent. Equally, I think you
can re-use the Empty node for this, but I need to think a little about the
implications re: partial inner nodes.
Regardless, with a generalized commitment scheme, the serialization/commitment
to an Empty node is simply '0', the encoding of an unspent txout surrounded by
spent txouts will be similar in size to a position integer followed by the
txout...
A subtlety of this construction is that you can only prove that a specific
txout # is unspent, but that's actually sufficient, as you can also prove what
# a txout txid corresponds too with a previous version of the MMR.
> you make the utxo commitments trail by a small fixed number of blocks
> (between 2 and 5) their latency problems shouldn't be a big deal as long as
> the overall performance is good enough. My thesis is that with appropriate
> format and implementation tricks it's possible to get performance good
> enough to no longer be a gating factor to deployment.
>
> Disappointingly there hasn't been any feedback about my implementation,
> just discussion about merkle sets generally.
Well, I think at this point there's still discussion over whether or not a UTXO
set commitment is the right approach to begin with; if it's not your
implementation isn't relevant.
--
https://petertodd.org 'peter'[:-1]@petertodd.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: Digital signature
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170223/7dfb1ea7/attachment.sig>;
Peter Todd [ARCHIVE] /
npub1m2ā¦a2np2
2023-06-07 17:56:31
in reply to nevent1qā¦n3mj
Author Public Key
npub1m230cem2yh3mtdzkg32qhj73uytgkyg5ylxsu083n3tpjnajxx4qqa2np2Published at
2023-06-07 17:56:31Event JSON
{
"id": "496e9f356c9d1523c750131a6dea40ea7db041a3303dd21485d16a037226aa9a",
"pubkey": "daa2fc676a25e3b5b45644540bcbd1e1168b111427cd0e3cf19c56194fb231aa",
"created_at": 1686160591,
"kind": 1,
"tags": [
[
"e",
"7c1fe6216790fb2846f605436edee6db0e33feb9c670df2e38b3b46417cf9504",
"",
"root"
],
[
"e",
"15c49c41ae155e1cc900554b654bcb89e84ddce3f8322dba51048859e13cbb01",
"",
"reply"
],
[
"p",
"fb7007c42a06687e3cd3fbbb1a3b17972e2a949ae679445f6b96579114d05cd9"
]
],
"content": "š
Original date posted:2017-02-23\nš Original message:On Thu, Feb 23, 2017 at 03:13:43PM -0800, Bram Cohen wrote:\n\u003e On Thu, Feb 23, 2017 at 9:53 AM, Chris Priest via bitcoin-dev \u003c\n\u003e bitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e \n\u003e \u003e\n\u003e \u003e What problem does this try to solve, and what does it have to do with\n\u003e \u003e bitcoin?\n\u003e \u003e\n\u003e \n\u003e I can't speak to MMRs (they look a bit redundant with the actual blockchain\n\u003e history to my eye) but circling back to utxo commitments, the benefits are\n\nIn what way do you see MMRs as redundant?\n\nRemember that with UTXO commitments because access patterns are uniform, you'll\nover time have a lot more \"redundancy\" in the form of lost-coins evenly spread\nout across the whole keyspace.\n\n\u003e that it enables actual proofs of non-fraud: You can prove the validity of a\n\u003e block based on just the previous block (and maybe some previous headers\n\u003e because of mining rewards) and can prove to a light node that a utxo hasn't\n\u003e been spent yet.\n\u003e\n\u003e A major factor in the way of getting utxo commitments in blocks is\n\u003e performance. The txo set is of course vastly larger and more unwieldy. If\n\nThat statement is incorrect with pruning: you can maintain a commitment to the\nTXO set, without actually storing the entire TXO set, because you don't need to\nstore anything for nodes that have already been spent.\n\nConcretely, this can be done with nothing more than adding a FullySpent node\ntype to the MMR definition I published earlier, with the rule being that only a\nleft or right child of an inner node be a FullySpent node, not both; if both\nsides are spent, the inner node itself becomes FullySpent. Equally, I think you\ncan re-use the Empty node for this, but I need to think a little about the\nimplications re: partial inner nodes.\n\nRegardless, with a generalized commitment scheme, the serialization/commitment\nto an Empty node is simply '0', the encoding of an unspent txout surrounded by\nspent txouts will be similar in size to a position integer followed by the\ntxout...\n\n\nA subtlety of this construction is that you can only prove that a specific\ntxout # is unspent, but that's actually sufficient, as you can also prove what\n# a txout txid corresponds too with a previous version of the MMR.\n\n\u003e you make the utxo commitments trail by a small fixed number of blocks\n\u003e (between 2 and 5) their latency problems shouldn't be a big deal as long as\n\u003e the overall performance is good enough. My thesis is that with appropriate\n\u003e format and implementation tricks it's possible to get performance good\n\u003e enough to no longer be a gating factor to deployment.\n\u003e \n\u003e Disappointingly there hasn't been any feedback about my implementation,\n\u003e just discussion about merkle sets generally.\n\nWell, I think at this point there's still discussion over whether or not a UTXO\nset commitment is the right approach to begin with; if it's not your\nimplementation isn't relevant.\n\n-- \nhttps://petertodd.org 'peter'[:-1]@petertodd.org\n-------------- next part --------------\nA non-text attachment was scrubbed...\nName: signature.asc\nType: application/pgp-signature\nSize: 455 bytes\nDesc: Digital signature\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170223/7dfb1ea7/attachment.sig\u003e",
"sig": "74035b5a164d1c469b8f777b291d374aecb53866102be61cfcb1aa9b2ea6a0699e576cb4d92f873cd5ba9e9bd37d95c13b522ed79a43d46478e4ac54ccd2ec86"
}