Wallard, tx relay, and bridgeless

[adiabat]

From the jitsi discussion today (2022-03-21):

@dergoegge brought up some of the difficulties in wallet transaction broadcast for CSNs that don't have proofs for their own transactions. There are 2 ways to do wallets with utreexo: Wallets keep track of proofs for their utxos, or they don't.

While long term the goal would be to have all wallets track their utxos, it seems to present a privacy problem: nodes could leak information about their knowledge of the accumulator state from peer to peer messages, which could allow attackers to figure out which nodes own which utxos. This attack could be passive, where surrounding nodes track which proofs are requested, and by figuring out which portions of the accumulator state are requested and which are not (and presumably cached) one could observe "unlikely" caching.

So we initially figured, don't have wallets track utxos at all. When they are constructing a transaction to broadcast to the network, they send it over to a regular full node. Eventually the transaction will make it back through a bridge node to the node that issued the transaction.

The problem with this is that it's actually a whole bunch of new code. In bitcoin core, wallet transactions go through mempool validation before being sent out to peers. Basically the node treats the transactions from the wallet as if it were received from any other peer, and validates before inserting into its mempool and sending it out. Similarly with btcd rpc calls, we'd use sendrawtransaction. But any use of sendrawtransaction presents problems with utreexo.

Normally, calls like sendrawtransaction will take the transaction received and treat it as if it had come over the network from a peer. It doesn't actually "send" the transaction, it's more like "accept" raw transaction. If you run something like xxd -l 400 -c 400 -p /dev/urandom | bitcoin-cli sendrawtransaction, your bitcoin node won't actually try to send that out to peers. It will see that it's an invalid transaction and reject it. But with wallets giving transactions to CSNs, we can't have the CSN treat the transaction as if it had come in from a peer, since it's missing proof data.

It's totally possible to write some new code that broadcasts unverified transactions to full node peers. But it's a bit awkward. The wallet would send out a transaction, and wait for it to come back, and not really know what to do if it never came back. Maybe this isn't all that hard, but it doesn't seem that easy, and if you're going to write a bunch of new code anyway, we might as well get the CSN wallets to track their own proofs.

Tight integration between the wallet and the CSN would allow the wallet to flag leaves to keep in the pollard. This would be most efficient, but could present a privacy leak. Another way would be for the wallet to keep a separate proof for each of its utxos. But probably the best balance of efficiency and simplicity, and which has a silly name, would be for the wallet to maintain it's own pollard, separate from the CSN's mempool: the wallard.

wallard

The wallet will still need new rpc or hooks to the CSN; it needs to be able to get data that lets it change its proofs for the leaves it's tracking. It doesn't need the whole block proof, but since it's all local & there's no network traffic, it's easy to start with the CSN giving the wallet the whole block proof. The wallet doesn't need to validate anything though, just replace hashes and move them around.

If the wallet & wallard work properly, then the mempool & broadcast code shouldn't need to change at all. CSNs would treat transactions coming from wallets just the same as coming from a peer.

bridgeless network

Another fun thing wallarded CSNs would enable is a bridgeless test network. Since the wallets would provide their own proof, we could start a network with no bridge nodes. All the nodes would be CSNs, and any tx or block without a proof would be considered invalid. For full functionality, we would need some CSNs to be able to save and serve blocks & proofs. Currently bridge and archive functionality are linked together, but they don't have to be. Most of the work for bridge nodes now is building proofs given a non-utreexo history (like set of blocks). In a bridgeless, CSN-only network, building the archive set would be pretty easy as nodes already have the block proofs, and can just write them to disk. A bridgeless test network would be fun to try, and see how scalability works. Without needing to deal with bridge nodes, is it easy to scale out better?

Granted if you really wanted a bridgeless network, there are probably better accumulator designs. But we know bridge nodes can work, and have spent a while optimizing them, so it seems fun to see how far a network could go without the need for bridges.