[BIP-98 + BIP-116] MERKLEBRANCHVERIFY #12131

kallewoof commented at 9:17 AM on January 9, 2018: member

Implements BIPs 98 and 116 as policy rules for transaction relay, causing transactions which use NOP4 for things other than Merkle branch verification to be treated as non-standard. This is not the soft-fork activation logic needed to use MERKLEBRANCHVERIFY in production.

MERKLEBRANCHVERIFY is a soft-fork upgradeable opcode that allows script writers to commit to a set of data elements and have one or more of these elements be provided at redemption without having to reveal the entire set. As these data elements can be used to encode policy, such as public keys or validation subscripts, the MERKLEBRANCHVERIFY opcode can be used to overcome size limitation of existing bitcoin script, and combines with tail-call semantics to provide a minimal implementation of the Merkelized Abstract Syntax Tree concept.

TheBlueMatt commented at 9:42 PM on January 9, 2018: member

Are there demos of scripts based on this/BIP117 anywhere? eg has someone sat down and rewritten the Lightning scripts or TumbleBit scripts to use this stuff to compare the cost/privacy tradeoffs? What about example usage for hiding multisig?

maaku commented at 10:15 PM on January 9, 2018: contributor

There are some examples inside the BIPs:

https://github.com/bitcoin/bips/blob/master/bip-0116.mediawiki https://github.com/bitcoin/bips/blob/master/bip-0117.mediawiki

It is specifically anticipated that ALL instances of MAST would be of the following:

redeemScript: [TOALTSTACK]*N OVER HASH256 <root> 1 MERKLEBRANCHVERIFY 2DROP 2DROP witness: <policyScript> <proof> <arg1> ... <argN>

TheBlueMatt commented at 10:49 PM on January 9, 2018: member

Hmm, I was hoping for somewhat larger scripts. Specifically, do you have a list of scripts which are cheaper to do using a merkle-hidden tail call than normally outside of large-multisig examples?

maaku commented at 11:02 PM on January 9, 2018: contributor

Basically every script where you are eliding, at minimum, a hash or pubkey push. Sorry for the obtuseness, but it seems like that describes just about anything and it didn't seem appropriate to overload the BIP with examples of everything beyond what was necessary to illustrate the concept. I would certainly like a lightning developer to show how those scripts could be reformulated to use tail-call semantics, but I'm not up to speed on the latest lightning standards.

TheBlueMatt commented at 11:05 PM on January 9, 2018: member

Hmm, well my primary motivation for asking was to get a better sense of the cost of using MBV+tail-call in practice. Comparing the cost of LN + TumbleBit scripts seems like an obvious route to figure that out, as it seems to me the only obvious user of something like this would be small-n large-m multisig, which seems somewhat of a waste.

maaku commented at 11:06 PM on January 9, 2018: contributor

It seems rather to me that the obvious user of something like this is 'everybody' for the fungibility improvement.

TheBlueMatt commented at 11:08 PM on January 9, 2018: member

Hence my concern - ideally "everyone" would use something like this for fungibility reasons, but I'm highly skeptical anyone will pay a material difference in fees to do so. Obviously I'm not suggesting we go through all the fun of SegWit again to adjust the discount to make a MAST extra branch free, but getting a good idea of exactly what that cost is for common protocols would be useful.

maaku commented at 11:13 PM on January 9, 2018: contributor

I think your intuition for the cost savings is off. Right now even a 2-of-3 multisig ends up costing about the same as a MAST of 2-of-2 vs having an extra (unused) pubkey. Likewise the 2of2 -or- CSV 1of1. And when we switch to Schnorr signatures basically any multisig becomes cheaper in the MAST construct because they all reduce to a MAST of 1of1's.

ghost commented at 1:26 AM on January 10, 2018: none

Concept ACK

chiguireitor commented at 12:28 PM on January 11, 2018: none

Conceptual question here: am i reading the code right or is the branch size limited to 9997 branches? Imho, having arbitrarily long branching trees could allow for really interesting stuff

kallewoof commented at 1:56 PM on January 11, 2018: member

@chiguireitor I believe the 9997 cap is basically representing the maximum depth in the tree. I think that shrinks if you want to pick multiple entries, though. I could be wrong. @maaku?

kallewoof force-pushed on Jan 11, 2018

maaku commented at 2:33 PM on January 11, 2018: contributor

I had to grep the diff to figure out what @chiguireitor was referring to. I assume it is the comment about MAX_STACK_SIZE limiting the number of elements that can be proven from a Merkle tree at once. That number is actually an error, as it should be 997, not 9997 as MAX_STACK_SIZE is a constant limit of 1,000 elements and 3 of those elements are the count parameter, the root hash, and the proof. It's worth noting that a separate limit, the 520 byte push limitation, prevents pushing a proof for a fully expanded Merkle tree of more than about 1380 elements anyway, so even if the MAX_STACK_SIZE limit were avoided you'd hit another one soon enough.

However I think there is some confusion on @chiguireitor's part. Why would you want to prove 1,000+ items from a tree at once? This is the maximum number of elements that you can prove at one time, NOT the maximum number of elements that can be in a tree, for which there is no practical limit. The 520 byte push limitation prevents you from proving a hash more than 16 levels deep in a tree, but MERKLEBRANCHVERIFY calls can be chained allowing for verification of extremely deep trees, much larger than could be practically constructed. A single chained validation allows for trees consisting of billions of elements, that would take hours to construct on a reasonably powerful CPU.

chiguireitor commented at 3:05 PM on January 11, 2018: none

Yeah, my bad. Makes sense now, it's just limiting the "next" level of the tree, so in fact, it's not limiting the overall tree structure at all, excellent.

kallewoof force-pushed on Jan 12, 2018

laanwj added the label Consensus on Jan 15, 2018

martin-lizner commented at 8:49 AM on January 16, 2018: none

Code will go to 0.16 and softfork signalling will start 0.16.1?

kallewoof commented at 9:01 AM on January 16, 2018: member

@martin-lizner There is no consensus yet on whether this code will be merged or not. It's still being debated (e.g. on the mailing list and such).

in src/script/interpreter.cpp:1154 in 1af2099f6e outdated

1147 | +                            CHash256().Write(vchLeaf.data(), vchLeaf.size()).Finalize(branch.m_verify.back().begin());
1148 | +                        }
1149 | +                    }
1150 | +
1151 | +                    // Compute Merkle root hash
1152 | +                    uint256 result = branch.GetHash();

jl2012 commented at 6:56 PM on March 18, 2018:

should error be returned here for invalid MerkleTree structure?

kallewoof commented at 9:03 AM on March 19, 2018:

@maaku Is there a reason why you presumed !invalid on this one? If not I think we should check validity and return error on invalid=true.

in src/consensus/merkle.h:306 in 1af2099f6e outdated

 301 | +    inline MerkleLink GetLeft() const
 302 | +      { return MerkleNode::m_left_from_code[GetCode()]; }
 303 | +    inline MerkleNodeReference& SetLeft(MerkleLink left)
 304 | +      { return SetCode(MerkleNode::_get_code(left, GetRight())); }
 305 | +
 306 | +    MerkleLink GetRight() const

jl2012 commented at 3:39 PM on March 20, 2018:

inline?

kallewoof force-pushed on Mar 23, 2018

kallewoof commented at 5:17 AM on March 23, 2018: member

@jl2012 Thanks for feedback! I inlined GetRight/SetRight in d99522a and added check/error for invalid result in GetHash in 8191d01. Not sure if SCRIPT_ERR_BAD_DECODE_ARG is suitable but it looked close enough.

in src/consensus/merkle.cpp:516 in 8191d011f5 outdated

 511 | +            *invalid = false;
 512 | +        }
 513 | +        return CHashWriter(SER_GETHASH, PROTOCOL_VERSION).GetHash();
 514 | +    }
 515 | +
 516 | +    // Except for the special case of a 0-node, 0-verify, 0-skip tree,

maaku commented at 3:58 AM on March 24, 2018:

I think this is the reason for allowing invalid=true in MBV. Maybe it should be fixed by setting *invalid to the logical OR of the various sizes referenced.

kallewoof commented at 6:20 AM on March 27, 2018:

All tests passed, though. I'm pretty sure you are testing for that case, no?

Add midstate output to CSHA256. This allows the intermediate state of a SHA-256 run to be saved for future resumption, or in the case of fast Merkle trees to perform a non-padded hash. 51342eb8a1

Add custom initialization vector support to CSHA256. Using alternative initialization vectors allows SHA-256 to be reused as a different cryptographic hash function while sharing the same implementation, which is necessary to secure some hash tree protocols. 9705a4ece4

Add fast Merkle branch functions. A fast Merkle branch uses midstate to perform a single SHA-256 compression with a custom initialization vector per internal node of a binary Merkle tree, and is not vulnerable to CVE-2012-2459. It produces different hash values though, so can only be used for new hash trees going forward. 74d45be41f

Add MerkleProof and MerkleTree data structures, for efficiently transmitting and validating proofs of multiple elements from a fast Merkle tree. The MerkleProof contains the tree structure and skip hashes, while the MerkleTree contains a proof and associated verify hashes. 240c6af170

Replace NOP4 with MERKLEBRANCHVERIFY, presently disabled.

  [... leaf/H(leaf) ...] proof root {count,prehashed} MERKLEBRANCHVERIFY

This opcode takes a Merkle root, any number of leaf hashes of the tree, and a 'proof' object composed of an encoding of the path through the tree from root to leaves and the minimal set of hash values necessary to recompute the the root from the leaf. Script validation fails if the recomputed root does not match the hash provided (which, presumably, would be committed to in the scriptPubKey).

Only the logic and unit tests are implemented; this commit does not have any soft-fork activation logic in it.

See BIP116 for details.

19b7f05059

Enable MERKLEBRANCHVERIFY as a standard script verification flag. Transactions that fail MBV verification will be rejected from the mempool, making it easier to test and to later soft-fork activate this feature. Blocks which contain "invalid" MBV-using transactions will still be accepted; this is *not* the soft-fork required to use MBV in production. 7e3fdbeff6

f'src/consensus/merkle.h: inline Get/SetRight 108f4d1d67

f'src/script/interpreter.cpp: check invalid flag in branch.GetHash() and throw SCRIPT_ERR_BAD_DECODE_ARG if true e5e56bc8b4

kallewoof force-pushed on Apr 24, 2018

kallewoof commented at 6:38 AM on April 24, 2018: member

The failure is due to a recent rewrite causing READWRITE(REF(CFlatData(m_skip))); to fail in merkle.h.

Discussing right now whether it makes a difference to switch to varint over compactsize explicitly as is done right now (I argue it does not make a difference, as the size is only a small fraction of the content).

MarcoFalke added the label Needs rebase on Jun 6, 2018

kallewoof commented at 3:30 AM on September 19, 2018: member

I'm closing this for now. If a better suited champion appears I'll help out where I can. Ping @btcdrak @maaku.

kallewoof closed this on Sep 19, 2018

laanwj removed the label Needs rebase on Oct 24, 2019

kallewoof deleted the branch on Jan 4, 2020

DrahtBot locked this on Feb 15, 2022