Re: [bitcoin-dev] A Better MMR Definition

gmaxwell told me that most nodes would keep a full copy of the top of the MMR tree. Here I am exploring how this could be policy-ized to solve two problems: - MMR proofs change over time - How to coordinate nodes to get them to keep different portions of the MMR, so that everyone can prune most

Re: [bitcoin-dev] A Better MMR Definition

Peter Todd, This MMR structure looks good to me. I really like how wallets keep their MMR proof and txo index instead of requiring the entire network to maintain an index on txids w/ plain old utxo snapshots. Re: "only left or right child of inner node be a fully spent node"... that sounds

Re: [bitcoin-dev] A Better MMR Definition

On Wed, Mar 1, 2017 at 2:31 PM, Peter Todd wrote: > > A better way to present your work would have been to at least explain that > at > the top of the file, and perhaps even better, split the reference > implementation and optimized implementation into two separate files. If

Re: [bitcoin-dev] A Better MMR Definition

On Fri, Feb 24, 2017 at 10:23:20PM -0800, Bram Cohen wrote: > > Your merkle-set implementation is 1500 lines of densely written Python > > > The reference implementation which is included in those 1500 lines is less > than 300 lines and fairly straightforward. The non-reference implementation >

Re: [bitcoin-dev] A Better MMR Definition

On Tue, Feb 28, 2017 at 05:47:30PM -0800, Bram Cohen via bitcoin-dev wrote: > On Tue, Feb 28, 2017 at 3:24 PM, Pieter Wuille > wrote: > > > > > Yes, someone needs to have a lookup table from prevouts to TXO tree > > positions. But because an insertion-ordered TXO tree

Re: [bitcoin-dev] A Better MMR Definition

On Tue, Feb 28, 2017 at 3:24 PM, Pieter Wuille wrote: > > Yes, someone needs to have a lookup table from prevouts to TXO tree > positions. But because an insertion-ordered TXO tree does not rebalance, > that table can be maintained by wallets or service providers for

Re: [bitcoin-dev] A Better MMR Definition

On Feb 28, 2017 15:10, "Bram Cohen via bitcoin-dev" < bitcoin-dev@lists.linuxfoundation.org> wrote: On Tue, Feb 28, 2017 at 8:43 AM, G. Andrew Stone wrote: > > But since transactions' prevouts are not specified by [block height, tx > index, output index] or by TXO

Re: [bitcoin-dev] A Better MMR Definition

I can understand how Bram's transaction double sha256 hashed UTXO set patricia trie allows a client to quickly validate inputs because the inputs of a transaction are specified in the same manner. So to verify that an input is unspent the client simply traverses the patricia trie. It also makes

Re: [bitcoin-dev] A Better MMR Definition

On Fri, Feb 24, 2017 at 02:20:19PM -0800, Bram Cohen wrote: > So your idea is to cluster entries by entry time because newer things are > more likely to leave and updating multiple things near each other is > cheaper? Yes, exactly. > That can be done with my tool. Instead of using hashes for the

Re: [bitcoin-dev] A Better MMR Definition

On Thu, Feb 23, 2017 at 07:32:43PM -0800, Bram Cohen wrote: > On Thu, Feb 23, 2017 at 7:15 PM, Peter Todd wrote: > > > > > Glad we're on the same page with regard to what's possible in TXO > > commitments. > > > > Secondly, am I correct in saying your UTXO commitments scheme

Re: [bitcoin-dev] A Better MMR Definition

On Thu, Feb 23, 2017 at 7:15 PM, Peter Todd wrote: > > Glad we're on the same page with regard to what's possible in TXO > commitments. > > Secondly, am I correct in saying your UTXO commitments scheme requires > random > access? While you describe it as a "merkle set",

Re: [bitcoin-dev] A Better MMR Definition

On Thu, Feb 23, 2017 at 07:02:36PM -0800, Bram Cohen wrote: > On Thu, Feb 23, 2017 at 6:58 PM, Peter Todd wrote: > > > > > So to be clear, do you agree or disagree with me that you *can* extract a > > compact proof from a MMR that a given output is unspent? > > > > After

Re: [bitcoin-dev] A Better MMR Definition

On Thu, Feb 23, 2017 at 6:58 PM, Peter Todd wrote: > > So to be clear, do you agree or disagree with me that you *can* extract a > compact proof from a MMR that a given output is unspent? > After wading through your logic on how updates are done, I agree that that can be

Re: [bitcoin-dev] A Better MMR Definition

On Thu, Feb 23, 2017 at 06:50:10PM -0800, Bram Cohen wrote: > On Thu, Feb 23, 2017 at 5:09 PM, Peter Todd wrote: > > > I think you've misunderstood what TXO commitments are. From my article: > > > > "A merkle tree committing to the state of all transaction outputs, both > >

Re: [bitcoin-dev] A Better MMR Definition

On Thu, Feb 23, 2017 at 5:09 PM, Peter Todd wrote: > I think you've misunderstood what TXO commitments are. From my article: > > "A merkle tree committing to the state of all transaction outputs, both > spent > and unspent, can provide a method of compactly proving the

Re: [bitcoin-dev] A Better MMR Definition

On Thu, Feb 23, 2017 at 04:49:01PM -0800, Bram Cohen wrote: > On Thu, Feb 23, 2017 at 3:51 PM, Peter Todd wrote: > > > On Thu, Feb 23, 2017 at 03:13:43PM -0800, Bram Cohen wrote: > > > > > > I can't speak to MMRs (they look a bit redundant with the actual > > blockchain > > >

Re: [bitcoin-dev] A Better MMR Definition

On Thu, Feb 23, 2017 at 3:51 PM, Peter Todd wrote: > On Thu, Feb 23, 2017 at 03:13:43PM -0800, Bram Cohen wrote: > > > > 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 >

Re: [bitcoin-dev] A Better MMR Definition

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@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

Re: [bitcoin-dev] A Better MMR Definition

On Thu, Feb 23, 2017 at 9:53 AM, Chris Priest via bitcoin-dev < bitcoin-dev@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

Re: [bitcoin-dev] A Better MMR Definition

On Thu, Feb 23, 2017 at 01:28:18PM -0500, G. Andrew Stone wrote: > Can an insertion ordered MMR allow an efficient nonexistence proof? Why do you want a non-existance proof? It supports an efficient *spentness* proof, which is sufficient for what we need in Bitcoin, and much more scalable. --

Re: [bitcoin-dev] A Better MMR Definition

Can an insertion ordered MMR allow an efficient nonexistence proof? On Feb 23, 2017 1:20 PM, "Peter Todd via bitcoin-dev" < bitcoin-dev@lists.linuxfoundation.org> wrote: > On Thu, Feb 23, 2017 at 09:53:58AM -0800, Chris Priest wrote: > > On 2/22/17, Peter Todd via bitcoin-dev > >

Re: [bitcoin-dev] A Better MMR Definition

On Thu, Feb 23, 2017 at 09:53:58AM -0800, Chris Priest wrote: > On 2/22/17, Peter Todd via bitcoin-dev > wrote: > > Reposting something that came up recently in a private discussion with some > > academics: > > > > Concretely, let's define a prunable MMR

Re: [bitcoin-dev] A Better MMR Definition

On Wed, Feb 22, 2017 at 5:15 PM, Peter Todd via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > > With that, notice how proving the soundness of the proofs becomes trivial: > if > validation is deterministic, it is obviously impossible to construct two > different proofs that prove

[bitcoin-dev] A Better MMR Definition

Reposting something that came up recently in a private discussion with some academics: Concretely, let's define a prunable MMR with the following grammar. This definition is an improvement on whats in the python-proofmarshal by committing to the number of items in the tree implicitly; an obvious