[bitcoin-dev] Storing the Merkle Tree in a compact way

2021-09-11 Thread shymaa arafat via bitcoin-dev
Allow me to introduce this simple idea that could be useful ...

-The Intuition was some discussion on Utreexo project about storage saving
and some traversing issues in handling the UTXOS Merkle Tree/ forest; that
is  N internal nodes need to be stored along with 2N pointers (left),
+ maybe 1 more pointer in the leaves special nodes to handle different
traversing options (insert, delete, & differently proof fetch that traverse
aunt or niece node according to your implementation
https://github.com/mit-dci/utreexo/discussions/316)
.
Then, I thought of a simple idea that gets rid of all the pointers;
specially appealing when we have all trees are full (complete) in the
forest, but can work for any Merkle Tree:

- 2D array with variable row size; R[j] is of length (N/2^j)
-For example when N=8 nodes
R[0]=0,1,2,...,7
R[1]=8,9,10,11
R[2]=12,13
R[3]=14
.
-We can see that total storage is just 2N-1 nodes,
no need for pointers, and traversing could be neat in any direction with
the right formula:

-Pseudo code to fetch proof[i] ...

//direction to know + or -
If ((i mod 2)==0) drct=1;
else drct=-1;
// first, the sibling node
proof[i]=R[0,i+drct]

//add the rest thru loop
For(j=1; j≤logN; j++)
 { index= i/(2^j)+drct;
proof[i]=Add(R[j,index]);
 }

-In fact it's just the simple primitive approach of transforming a
recursion to an iteration, and even if Utreexo team solved their problem
differently I thought it is worth telling as it can work for any Merkle Tree
.
Thanks for your time,
Shymaa M Arafat
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Braidpool: Proposal for a decentralised mining pool

2021-09-11 Thread Filippo Merli via bitcoin-dev
>From my understanding of the posted proposal, a share to get rewarded must
"prove" to be created before the rewarded share. (between L and R)
If GOOD3 refers to BAD2 the only thing that I can prove is that BAD2 has
been mined before GOOD2.

So if  BAD3 is a valid block (I call it R like in the pdf) the only thing
that I can certainly know is that between L and R there is BAD1 and BAD2
and they should be the ones that get the rewards.
Btw rereading the proposal I'm not sure about how the rewards are
calculated, what let me think that is the way that I illustrate above is
the figure 2: c3 is referring to a3 but is not included in the first reward.

To clarify I'm talking about two things in my previous email, the first one
is: what if a bad miner does not refer to good miners' shares?
The second thing is: what if a bad miner publishes two (or more)
conflicting versions of the DAG?


On Sat, Sep 11, 2021 at 3:09 AM ZmnSCPxj  wrote:

> Good morning Filippo,
>
> > Hi!
> >
> > From the proposal it is not clear why a miner must reference other
> miners' shares in his shares.
> > What I mean is that there is a huge incentive for a rogue miner to not
> reference any share from
> > other miner so he won't share the reward with anyone, but it will be
> paid for the share that he
> > create because good miners will reference his shares.
> > The pool will probably become unprofitable for good miners.
> >
> > Another thing that I do not understand is how to resolve conflicts. For
> example, using figure 1 at
> > page 1, a node could be receive this 2 valid states:
> >
> > 1. L -> a1 -> a2 -> a3 -> R
> > 2. L -> a1* -> a2* -> R
> >
> > To resolve the above fork the only two method that comes to my mind are:
> >
> > 1. use the one that has more work
> > 2. use the longest one
> > Btw both methods present an issue IMHO.
> >
> > If the longest chain is used:
> > When a block (L) is find, a miner (a) could easily create a lot of share
> with low difficulty
> > (L -> a1* -> a2* -> ... -> an*), then start to mine shares with his real
> hashrate (L -> a1 -> a2)
> > and publish them so they get referenced. If someone else finds a block
> he gets the reward cause he
> > has been referenced. If he finds the block he just attaches the funded
> block to the longest chain
> > (that reference no one) and publishes it without sharing the reward
> > (L -> a1* -> a2* -> ... -> an* -> R).
> >
> > If is used the one with more work:
> > A miner that has published the shares (L -> a1 -> a2 -> a3) when find a
> block R that alone has more
> > work than a1 + a2 + a3 it just publish (L -> R) and he do not share the
> reward with anyone.
>
>
> My understanding from the "Braid" in braidpool is that every share can
> reference more than one previous share.
>
> In your proposed attack, a single hasher refers only to shares that the
> hasher itself makes.
>
> However, a good hasher will refer not only to its own shares, but also to
> shares of the "bad" hasher.
>
> And all honest hashers will be based, not on a single chain, but on the
> share that refers to the most total work.
>
> So consider these shares from a bad hasher:
>
>  BAD1 <- BAD2 <- BAD3
>
> A good hasher will refer to those, and also to its own shares:
>
>  BAD1 <- BAD2 <- BAD3
>^   ^   ^
>|   |   |
>|   |   +--+
>|   +-+|
>| ||
>+--- GOOD1 <- GOOD2 <- GOOD3
>
> `GOOD3` refers to 5 other shares, whereas `BAD3` refers to only 2 shares,
> so `GOOD3` will be considered weightier, thus removing this avenue of
> attack and resolving the issue.
> Even if measured in terms of total work, `GOOD3` also contains the work
> that `BAD3` does, so it would still win.
>
> Regards,
> ZmnSCPxj
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev