Share Template Validation

[mcelrath]

Braidpool needs to validate the Bitcoin block associated with every bead in the DAG (share). We don't want people mining invalid blocks to steal hashrate that could never win blocks. Naively if Braidpool has a bead rate 1000x that of Bitcoin, we'd need to download 1000x more blocks, which is impractical. Compact block relay can help but let's assume that validating every share is impractical.

Instead we can spot-check templates by having compact blocks sent to at minimum 4 other random peers on the network (because of the 3f+1 requirement of Byzantine consensus). The choice of peers should be pseudo-random and decided by randomness in the DAG (a hash of ancestor shares for instance).

If any of these peers cannot validate the block because of a double spend, invalid transaction, or other consensus failure, they can compactly broadcast this fraud proof to all Braidpool nodes in order to invalidate the shares of that miner.

To deal with bit flips in memory and in communication, we need an error correcting p2p layer such as using Forward Error Correction (FEC) over UDP. Furthermore I suggest an exponential back off in share invalidation. Upon one share validation failure, only that share will be invalidated (this can be accidentally caused by single bit errors from the sender). Upon two, we'd invalidate two shares. After N failures we'd invalidate 2^N shares. So single bit flips accidentally would have a minor but noticable effect on payouts (use ECC RAM and high quality power supplies people - these are the biggest cause of this), but repeated failures would quickly result in invalidation of all the miner's shares in this epoch.

All miners on Braidpool already have the Bitcoin block header corresponding to a bead/share, which contains the Merkle root(s) (segwit) of transactions. An error in this will be quickly known by all, which leaves only an error in the tx tree(s) (standard+segwit). Therefore a fraud proof would consist of the share hash and a Merkle path identifying the bad transaction, plus the full data of that transaction.

It is impossible to submit fraudulent fraud proofs as long as the sha256d hash used in the tx tree is cryptographically secure.

[pool2win]

There's another solution documented in the mailing list proposal. The solution depends on dag nodes being simply shares.

1. Miners build block templates and broadcast them using compact block proposal.
2. Miners refer to the block templates they are working on.
3. If other miners haven't yet received the block template, they mark the shares referring to them as pending.
4. Once the template is received, the pending shares are marked confirmed.
5. If no template is received for some shares in an epoch, those shares are marked invalid. Miners are free to create new templates in the middle of an epoch.
6. When a bitcoin block is found to end epoch n, miners generate a new template and start mining shares using that template in epoch n+1. However, while the template is being generated, they continue to mine on the old template - these shares are considered valid in the n+1 epoch. The incentive here is that they want to generate a new template asap to get the tx fees. Further, these shares won't be valid in epoch n+2.

[mcelrath]

Because block templates are part of share consensus, we need to ensure that every miner has received every template. It can't be passed out of band.

[mcelrath]

"If no template is received for some shares in an epoch" really means that the entire template itself must be in a bead, since "received" by any individual miner is not consensus-validateable. This requires the share chain to carry many block templates for blocks that never get mined, so has a higher bandwidth, storage, and processing requirements than the spot-check fraud proofs idea.

[pool2win]

It' will be one block template per miner per epoch. O(n) in number of miners. Plus the usual block hash in the shares. The eventual consistency and message stability proprieties provided by the dag of messages allows each miner to know when the template has been received and acknowledged by other miners. It's building on the async non-bft consensus provided by dag. Nodes don't need to wait for these confirmations anyway.

…

On Wed, 27 Dec 2023, 07:29 Bob McElrath, ***@***.***> wrote: "If no template is received for some shares in an epoch" really means that the entire template itself must be in a bead, since "received" by any individual miner is not consensus-validateable. This requires the share chain to carry many block templates for blocks that never get mined, so has a higher bandwidth, storage, and processing requirements than the spot-check fraud proofs idea. — Reply to this email directly, view it on GitHub <#66 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ASU3SYL6HX5LL2QTQWXX5XLYLQIA3AVCNFSM6AAAAABBAIQBRCVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM3TSNJWGA2DI> . You are receiving this because you commented.Message ID: ***@***.***>

[mcelrath]

It will be one block template per miner per block. You can't keep the same template after a block is mined. So O(n_miners) (multiplicative) more resources than Bitcoin.

The DAG I proposed is over shares not messages. I think you're talking about a DAG-based messaging system, which could be added for the P2P layer, but would be a second DAG with different "eventually consistent" properties since messages aren't mined. (Possibly committed to in the share DAG?) I've seen some P2P literature that uses DAGs... If this is what you're after that could work but needs to be described in more detail.

P.S. probably overlaps with "slots" which I need to post about, to manage the list of sender/miner pubkeys...

[mcelrath]

Here's an example of DAG-based messaging and consensus on who has seen what. Here messages are not mined but reference other messages they've seen to define the DAG. It's a new consensus mechanism different from Nakamoto consensus, but interesting. I question its Sybil resistance since it's nearly costless to flood the system with messages. But anyway for a DAG over the P2P messaging layer see this paper, citations and references.

https://arxiv.org/abs/2102.08325

[plebhash]

Furthermore I suggest an exponential back off in share invalidation.

this is good because it acts as a practical incentive against dishonest braidpool-node instances trying to propagate invalid shares/beads.

perhaps, after some backoff threshold, honest braidpool-nodes could simply disconnect from the peer who keeps insisting on gossiping invalid shares/beads.

as a result, dishonest braidpool-nodes would be simply shunned off by honest nodes and the DoS attack vector would exponentially decay.

[mcelrath]

Good idea.

[pool2win]

On Wed, 27 Dec 2023, 08:26 Bob McElrath, ***@***.***> wrote: It will be one block template per miner per *block*.

Yes. Minimum one template per miner.

You can't keep the same template after a block is mined. So O(n_miners) (multiplicative) more resources than Bitcoin.

We do need all the templates that shares are mined for. This is because that's the only way to know the shares are PoW for valid blocks. However we can aggressively prune away the templates once the shares are validated and payouts made. We will also need to prune the shares too. How long we need to keep the shares around will depend on the futures protocol we develop. The DAG I proposed is over *shares* not messages. I think you're talking

about a DAG-based messaging system, which could be added for the P2P layer, but would be a second DAG with different "eventually consistent" properties since messages aren't mined. (Possibly committed to in the share DAG?) I've seen some P2P literature that uses DAGs... If this is what you're after that could work but needs to be described in more detail.

Yup, the dag in my world view is more than beads. It helps build the reliable broadcast by providing implicit acknowledgements. As you know I worked with DAG broadcast and consensus algorithms for a while back in the day. It's a great tool to build loads of useful things. By putting templates in the dag, we also get a temporal relationship between shares and templates from different miners as well price provide reliable broadcast of the templates too. P.S. probably overlaps with "slots" which I need to post about, to manage

…

the list of sender/miner pubkeys... — Reply to this email directly, view it on GitHub <#66 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ASU3SYNC3YDFVWKJEYOBQ2DYLQOZ5AVCNFSM6AAAAABBAIQBRCVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM3TSNJWGU2DE> . You are receiving this because you commented.Message ID: ***@***.***>

[s2dd]

On Wed, 27 Dec 2023, 08:26 Bob McElrath, @.***> wrote: It will be one block template per miner per block.
Yes. Minimum one template per miner.

a miner can hash on several templates per block ? . so for a verification should have batch [node][block][template-used][shares-weight][ts-start/stop] ?

[s2dd]

a verifier of a "node template with shares" would need have all tx in it's(the verifier) mempool as well ?

this suggest "node template-provider connected bitcoind" should be configured to have peer of node being verified ?

or maybe some extra request to network -fetch ev. missing tx ? in template being verified

[pool2win]

Yes. In decentralised mining setup, you can't really trust third party bitcoind. That's how I think of it at least. We can provide opt out options to use third party bitcoin nodes. In the mailing list proposal I pointed to the option that some miners can trust other miner templates that they receive over the network - it's totally their choice. Out of the box the miner will be required to run their own bitcoind.

…

On Fri, 29 Dec 2023, 08:25 s2dd, ***@***.***> wrote: a verifier of a "node template with shares" would need have all tx in it's(the verifier) mempool as well ? this suggest "node template-provider connected bitcoind" should be configured to have peer of node being verified ? — Reply to this email directly, view it on GitHub <#66 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ASU3SYKSAZA64JHUOZROWADYL3ADPAVCNFSM6AAAAABBAIQBRCVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM3TSNZSGE3DC> . You are receiving this because you commented.Message ID: ***@***.***>

[s2dd]

yes -but verifier's bitcoind need maybe peer with the verifiyed's bitcoind as mempools of each will not be synced ie. having same view at time ?

[pool2win]

Yes, a miner can generate new templates as higher fee paying transactions come in. This is what the pool operators do right now too.

…

On Fri, 29 Dec 2023, 08:13 s2dd, ***@***.***> wrote: On Wed, 27 Dec 2023, 08:26 Bob McElrath, *@*.***> wrote: It will be one block template per miner per *block*. Yes. Minimum one template per miner. a miner can hash on several templates per block ? . so for a verification should have batch [block][template-used][shares-weight][ts-start/stop] ? — Reply to this email directly, view it on GitHub <#66 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ASU3SYIGLV5L5PKIDPTOSPLYL26WJAVCNFSM6AAAAABBAIQBRCVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM3TSNZSGEYDA> . You are receiving this because you commented.Message ID: ***@***.***>

[pool2win]

That's a fair point. We will need to trigger share revalidations and dag-reorg in response to bitcoind recieving new transactions. However, share validations is not on the critical path. We need to validate shares for block n, when we are constructing payout transactions for block n + 100. 100 being the required coinbase spending maturity. If a miner produces invalid shares, they definitely won't be rewarded for it. This is getting interesting. I'll write a TLA+ spec for this before coding it up.

…

On Fri, 29 Dec 2023, 10:22 s2dd, ***@***.***> wrote: yes -but verifier's bitcoind need maybe peer with the verifiyed's bitcoind as mempools of each will not be synced ie. having same view at time ? — Reply to this email directly, view it on GitHub <#66 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ASU3SYOLIRQH2YE7CYS43CLYL3N4HAVCNFSM6AAAAABBAIQBRCVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM3TSNZTGQ3TQ> . You are receiving this because you commented.Message ID: ***@***.***>

[s2dd]

Do the beads in braid DAG need be "near real time" or can / would it be constructed after some time in that if a bead reach network difficulty, new tip commence, else beads data submitted with pool variance difficulty, is distributed and collected at node's for later DAG build at node's with verification of beads-weight per miner is done ?

[s2dd]

I can se a node in Braidpool as being several micro-services divided by purpose and when in time work is to be done, easier to version / build / measure and maintain ?