Topic: 1000x throughput on transaction batching + privacy boost using Script Bitfields. - page 2. (Read 407 times)

Hello spartacus, excellent job.  

although I need a bit more time to fully digest your idea, it may be helpful to put your proposal this way:

1- Payer generates a txn which pays to a single Merkle root.

2- The Merkle hash tree has leafs each hashes of outputs mentioning amounts and addresses of receivers (or an output script?)

3- Each receiver, privately is handed a proof that is consisted of exact traversal path from its own leaf to the root and siblings necessary to prove a     leaf as a member.

4- Full nodes maintain an additional bitfield data structure for such txn types to keep track of spent/unspent status of leafs.

5- Recipients can spend by disclosing the path to the root including the hash of their respected leaf, the actual output and required information/signature(s) depending on the output script.

All good but a single issue (for now):
How full nodes could ever verify that the payer has not over spent the input(s)?

And I got (premature) solutions for this problem as well

1- You may consider including the list of amounts in the txn body. It adds like 1024*8 bytes  (max) to txn size and reduces the effect you wish from 1000x to like 5x-10x . Not a smart solution.

2- Another and ways better solution would be including just sha256 hash of the amounts list in the txn and not the list itself,  full nodes do not verify this hash at all, instead each receiver will be given the original list (same) along with the hash proof of the main tree for their respected leaf (exclusive) and we are done! It would be each receiver's job to verify the amounts, all of them. A collusion between payer and the receivers have no incentives as the first overspend attempt will be rejected  by full nodes as they are always able to check the remained balance of the original utsxo.

Still there is another issue: This idea implies a kind of interaction and  wallet liveness which is acceptable as the cos t of the great performance boost, imo.

Edit:
It is also important to note that proofs and signatures can be safely pruned after a while and don't have to be maintained forever but spend txn should reveal the index permanently.

This trick requires upgrades to the current Bitcoin scripting language. I'm pretty sure it can all be done right now on Liquid.

You need CHECKOUPUTVERIFY and some covenant logic.
The ability to check Merkle Proofs - the branches of the tree pointing to some root.
And bit-wise operations for checking and setting bits. We'll be using Bram Cohen's bitfields, and indicate spent output with a single bit.

When we get that..
 
Here's how :

You're an exchange and you need to pay 1024 people as they want to withdraw. You have each of their addresses.

Instead of creating a transaction that sends the right amount to each participant..

Create a hash tree that has Hash ( Index Amount Address ) as the leaf nodes. Get the root of the tree. This will create proofs per leaf of 10 hashes + 10 boolean left/right values (to descend the tree - to it's root). The Index value goes from 0-1023. It's a perfect binary tree. 2^10=1024.

Give each leaf node proof to each user. This does not reveal the other outputs.

Now create a covenant script.

Send the complete funds for all 1024 participants to this one address.

Anyone of the 1024 can present their proof as an input, and the correct signature, when trying to spend their exact allotted amount. The covenant script ensures there is an output of the new correct lower amount to the same address in the outputs.

How do we know the user has not spent before ? We store it in a bitfield. 1024 Bits is 128Bytes. So there is a 128 byte value passed from covenant to covenant, similar to the way eltoo does it, and you check the bit value from INDEX in the proof to see if you can spend. Once you do spend that bit is set to 1, the 128 byte value updated and passed on, and the next check will fail. This is nice as the address for the script does not change, even though it's functioning does.

This way 1024 separate users have access to the same transaction output. Saving quite a bit of space.

Once we get SIGHASH_NOINPUT we should be able to spend outputs from one transaction as inputs to another transaction in the same block and multiple users can call the script simultaneously (they won't specify a coinid just the script).

Lots of other use cases.. (Off-ramping from a sidechain)