AT2 discussion and questions

[mav]

Following on from this post with a video series on Asynchronous Trustworthy Transfers (AT2) I thought it would be good to have a place to discuss AT2. (Link to the AT2 paper for convenience).

Overall the fit seems very good for SAFE but I have some questions.

---

In video 2 at 6m14 they say “it turns out that the safe design of cryptocurrencies only require solving a problem with consensus number one. And this is very intuitive because if I have an account and I want to perform a transaction from the account I only need to agree with myself … I am the only one who is supposed to decide where the money from my account goes and for this I only need to agree with myself, and that’s why we have consensus number one.”

• What about multisig transactions? Does this definition of consensus number then mean it would be a higher consensus number? I think by this definition then yes it must be.
• It seems to conflate consensus of signing the transaction with consensus of the order of the transactions from that account as known by the system. Have I misunderstood something with this?
• They say elsewhere that bitcoin has consensus number infinity but that seems to refer to consensus of the order of transactions. To merely sign and broadcast a transaction in bitcoin is only consensus number one. So I’m a little unclear about consensus number; if there’s any good explanation of that concept I’d be keen to hear about it.

---

Regarding the gossip aspect for probabilistic AT2. My summary of this idea (please correct if wrong) seems to be that the sender of a transaction broadcasts their transaction to some nodes, then those nodes gossip it to others, and they gossip it further etc, spreading the transaction exactly the same way as bitcoin transaction relay happens. The recipient can then sample some random nodes in the network to see if they have a consistent agreement on that transaction. If they do, the transaction is very probably agreed. The more nodes the recipient samples the more likely it is the transaction is agreed and not in conflict or attempted at double spend.

• Why does bitcoin need blocks and not depend on transaction relay alone? Why does AT2 not need blocks and seem to only need transaction relay and sampling? I guess blocks are needed when there are conflicts in transaction order, the blocks resolve the order.
• There was previously a first-seen relay rule in bitcoin where nodes would not relay an apparently ‘double spend’ transaction. Does AT2 have something similar? What happens with AT2 to resolve conflicts for relayed/gossiped transactions? What happens with this race condition situation, which would be trivial for a sender to initiate?
  • From a recipient perspective: presumably sampling by the recipient would show two simultaneous transactions so the recipient would not accept the transaction. For example, if I’m a bad guy trying to buy my lunch and I send two transactions simultaneously (one to the cafe and another conflicting one to myself), what does that look like to the cashier and how long would it be until they can let them walk away with their lunch (or not)?
  • From a network perspective: are both transations rejected by the network? Or is one chosen and the other discarded, and how long would that choosing take?

I guess my general question here is how does AT2 deal with conflicts? I’m still not too clear on that aspect.

---

What is the flow of data for a transaction in SAFE? My guess is

• client signs and announces their transaction to a random node on the network
• the transaction is routed to the section responsible for the wallet of those funds via normal SAFE routing
• the section responsible for that wallet does AT2 to deduct the funds, gossiping only within that section
• when that section confirms there’s no conflict or error with deducting, the transaction is routed by that section to the recipient section using normal SAFE routing
• the section responsible for the recipient wallet does AT2 to credit the funds, gossiping only within that section
• the recipient polls their wallet for the change in balance applied in the step above (ie the recipient does not do AT2 sampling, only the section responsible for their wallet does the sampling)…?

Does that sound right? In a general sense, is AT2 only applied at the section level, not the global network level?

[jlpell]

Nice write-up mav. All really good questions.

[Nigel]

@mav

I guess my general question here is how does AT2 deal with conflicts? I’m still not too clear on that aspect.

What if the data type used for Safecoin is a CRDT (which I think is planned)? Then should be conflict free, no?

@mav

Why does bitcoin need blocks and not depend on transaction relay alone? Why does AT2 not need blocks and seem to only need transaction relay and sampling?

I’m sure I’m looking at this far too simplistically but the order of blocks seems like it’s meant to continually further cement the immutability of history and the consensus of a transaction whereas a lot of times so many confirmations is ‘good enough’ and what they are trying to get across in those videos is that blockchain is overkill for transfers. Maybe bitcoin is this way simply to prove it’s robustness and great computational power? I’m not able to answer your question so much as think aloud in hopes it sparks new ideas for you.

[dask]

It should be. From my reading/understanding (please jump in here if I’m wrong, this stuff is tricky) the design is good, but needs to be tested. One of the things that has impeded AT2 seems to be that it assumes that you already have access to (byzantine) consensus account state. In a way, it seems to me to resemble NANO’s scheme, where the latest validated account state can ‘sign a cheque’ the network will accept. Luckily SAFE provides this underpinning with it’s data consensus.

[dask]

@mav

Why does bitcoin need blocks and not depend on transaction relay alone? Why does AT2 not need blocks and seem to only need transaction relay and sampling? I guess blocks are needed when there are conflicts in transaction order, the blocks resolve the order.

Bitcoin needs blocks because its data model is unspent outputs, which represent final balances that a private key can spend. And so transactions can pull in dozens of them to ad up to what the output is, but you need to know the blocks to know that the network will accept your accounting. And nodes need the blocks to calculate if they will accept your accounting.

In SAFE proposal, the network already accepted your accounting; the balance is a consensus value for the sum of all these transactions stored tied to your account as confirmed data and handled by the section responsible for that chunk. If the section is queried, it can give the consensus and modify the data.

Both need methods for handling conflicting transactions both in the current mem/block pool.

[Nigel]

@dask

Bitcoin needs blocks because its data model is unspent outputs, which represent final balances that a private key can spend. And so transactions can pull in dozens of them to ad up to what the output is, but you need to know the blocks to know that the network will accept your accounting. And nodes need the blocks to calculate if they will accept your accounting.

In SAFE proposal, the network already accepted your accounting; the balance is a consensus value for the sum of all these transactions stored tied to your account as confirmed data and handled by the section responsible for that chunk. If the section is queried, it can give the consensus and modify the data.

Both need methods for handling conflicting transactions both in the current mem/block pool.

Awesome explanation!

[joshuef]

@mav

What about multisig transactions?

As I understand things, the consensus is for a given wallet, so with multisig, as long as you can generate a sig, you can start the process of a transaction, that transaction itself, still only needs to agree with itself. So I’d view this signing of multiple parties as a separate step to the transaction itself.

@mav

It seems to conflate consensus of signing the transaction with consensus of the order of the transactions from that account as known by the system . Have I misunderstood something with this?

It conflates it in so much as, once you have a signed transaction, valid for a wallet/address that is put to the network, and it has to be in order, or list other transactions that come before it. If it’s out of order, or missing a transaction, then it is invalid, so the order is enforced at that point.

@mav

So I’m a little unclear about consensus number; if there’s any good explanation of that concept I’d be keen to hear about it.

I don’t have any link to a better understanding. But I think it’s that, at the broadcast point, the transaction can be accepted, and that’s it, or it has to go through some proccess/proof of work etc to be considered valid.

At2 works, as all nodes can see all the state at all times. So, as long as order/deps are valid and there’s enough money in an account (which any node can check), then it is valid at that point.

(Note, that’s not to say on SAFE all nodes can see all balances, at the moment we’re considering a ‘node’ that you broadcast/communicate with to be your section elder)

---

Your probabilistic summary seems on point to me.

Why does bitcoin need blocks and not depend on transaction relay alone?

It comes down to the order of transaction and deps enforcement as far as I can see.

@mav

There was previously a first-seen relay rule in bitcoin where nodes would not relay an apparently ‘double spend’ transaction. Does AT2 have something similar? What happens with AT2 to resolve conflicts for relayed/gossiped transactions? What happens with this race condition situation, which would be trivial for a sender to initiate?

You broadcast your transactions with a sequence number. If you broadcast two at the same number to quorum, then one of those will be rejected. If it’s a later number, it has to depend on the prior transaction, and so that must be applied at the node before this one can be considered.

@mav

what does that look like to the cashier and how long would it be until they can let them walk away with their lunch (or not)?

In the paper AT2 (as i understand), this would look like their node seeing two conflicting transactions, and converging on one or the other.

In SAFE, (as we’re currently working to POC, with each section being their own mini AT2-network), the cashier would only see the transaction if the valid transaction was agreed upon by quorum of the sender’s section. Otherwise they would see no payment.

@mav

From a network perspective: are both transactions rejected by the network? Or is one chosen and the other discarded, and how long would that choosing take?

I think one of them would be seen by quorum before the other, so would be accepted and the second rejected.

---

So right now, our at2 bank is intra-section only, with messaged passed (And signed) between sections in order to “deposit” money at that section (and a target account).

So:

• Client initiates a transaction and broadcasts to all section elders
• Section elders validate the transaction is a) signed, b) in order c) has correct deps and d) there is sufficient balance for this transaction at that point.
• Section elders use their SecretKeyShare (of the group key) to sign the transaction and return this to client.
• Client collects and aggregates these BLS keyshares to get a valid “transaction” that it can broadcast to the network (normally to its section elders, or it would otherwise be routed there).
• Section elders now apply this valid transaction to their bank.
• As required (assuming recipient is in a different section), section elders sign a message crediting this account and forward it, securely to that section’s elders.
• Receiving section elders get the message and can apply to recipients account.
• Recipient will likely poll wallet for updates.

@mav

is AT2 only applied at the section level, not the global network level?

For now yep. We’re not ruling anything out. Though we’re starting with the section level impl. The difference between section level and network level AT2 is, for the former, a two stage transaction, but definitive iter-section anonimity with an encrypted inter-section message, vs atomic transactions but (at the moment) no anonymity and a requirement for all sections to store all balances. (That would be a probabilistic implementation).

---

@Nigel

What if the data type used for Safecoin is a CRDT (which I think is planned)?

AT2 is kind of CRDT itself. If you make a transaction with a higher sequence number, it can be delayed if deps are known, or will simply be rejected.

[jlpell]

I miss safecoin classic.

[Nigel]

@joshuef

You broadcast your transactions with a sequence number

Maybe I’m assuming too much but is that why I see a coins section in the Sequenced Data Type?
I’m kind of guessing no since you say at2 is like a CRDT itself.

One thing I’m completely lost on is dependencies. What are the dependencies for at2 and what is their role and importance?

[joshuef]

Heh, we’ve been discussing this just today actually @Nigel.

As far as I understand, the deps are more useful in the probabilistic case, where its not 100% guaranteed that a node will have seen a pending credit transaction yet, so you can specify in the deps, that X must be seen before applying this Y.

[Nigel]

@joshuef

so you can specify in the deps, that X must be seen before applying this Y.

Okay I understand in which context dependency is being used now. Thank you!

[mav]

@joshuef

once you have a signed transaction, valid for a wallet/address that is put to the network, and it has to be in order, or list other transactions that come before it. If it’s out of order, or missing a transaction, then it is invalid, so the order is enforced at that point.

@joshuef

At2 works, as all nodes can see all the state at all times. So, as long as order/deps are valid and there’s enough money in an account (which any node can check), then it is valid at that point.

@joshuef

You broadcast your transactions with a sequence number. If you broadcast two at the same number to quorum, then one of those will be rejected

@joshuef

each [SAFE network] section being their own mini AT2-network

Incredibly helpful post thanks @joshuef.

These points clarified something for me: in bitcoin the network is responsible for deciding the order, but in at2 the client is responsible for determining the order. If the client tries to deliberately mess with the order in bitcoin then the conflicting order will be sorted by the miners (via the blocks, and to a lesser degree even the transaction relay rules) but with at2 the conflicting order is … resolved by chance depending how the two transactions propagate to the elders?

@joshuef

• Client initiates a transaction and broadcasts to all section elders
• Section elders validate the transaction is a) signed, b) in order c) has correct deps and d) there is sufficient balance for this transaction at that point.
  …

If the client wallet is in section 000000 and the client doesn’t have a direct connection to that section, how do the elders do the validation? Do the elders use routing to get that info from the section holding the wallet?

Also for the step ‘has the correct deps’, (deps being dependencies). Is ‘dependencies’ a different thing to bitcoin unspent transaction outputs (utxos)? As in, a SAFE wallet is just a balance, not a collection of transactions, so the dependencies are probably different, right? In the case of SAFE wallet the dependencies would be … what?

[Nigel]

@mav

resolved by chance depending how the two transactions propagate to the elders?

That’s what I’m picking up. On the surface it almost sounds clunky doesn’t it? But it really isn’t. The only instance it is an issue is if you’re trying to spend the same coins twice (double spend) in which you still spend the coin once, on either thing and we shouldn’t really care because it’s most likely an act of malice anyhow.

[joshuef]

Happy to help! Also good for me to be writing these thins down as it helps clarify them for myself

@mav

but with at2 the conflicting order is … resolved by chance depending how the two transactions propagate to the elders?

Yup. Which (in safe) also essentially boils down to the client as it’s on the client to be sending it to each elder (at the mo). And all else being equal, it’d ocme down to their send order. (But natch, it’s a distributed network so all else may not be equal)

@mav

If the client wallet is in section 000000 and the client doesn’t have a direct connection to that section, how do the elders do the validation? Do the elders use routing to get that info from the section holding the wallet?

Yeh, the messages would just be routed to that section, as with any network messages. (I am not 100% familiar with the ins and out of this)

@mav

Also for the step ‘has the correct deps’, (deps being dependencies). Is ‘dependencies’ a different thing to bitcoin unspent transaction outputs (utxos)? As in, a SAFE wallet is just a balance, not a collection of transactions, so the dependencies are probably different, right? In the case of SAFE wallet the dependencies would be … what?

Probably better to term it “balance” as opposed to wallet. And a given balance will is a set of inputs and outputs in the at2 bank setup (each signed by the section group key on credit/debit).

A dependency might be a valid (signed) transaction that a given elder may not yet have seen (for some reason: dropped msg etc). So there could be a credit that’s been applied to 5/7 elders, is considered quorum, but X has not received. But they receive a tx req Y that depends upon it for $$. So they would know to hold on to this for Z time to wait and see if the Y comes in (via gossip) before running validation checks.

(I think it could even be that the dependency is the whole signed transaction, effectively providing it for the node, which could verify it via sig… that just occured to me, so don’t consider that canon yet! )

[digipl]

As I understand it, dependencies on Safe will always be zero.

This scenario is not possible in SAFE because are the Elders of the group that manage any transfer and inform the node of its approval so no node will ever know, before quorum elders, of the existence of any incoming transfer.

The possibility that one elder may not yet have seen a previous transaction is another case that must always be considered, regardless of any dependency.
One solution could be that any elder broadcast any transfer to the rest of the elders even if they consider it invalid due to insufficient funds.
Other solution could be that the outgoing transfers node broadcast the request to enough elders to always find one who knows the updated balance.

[Southside]

@joshuef

Also good for me to be writing these thins down as it helps clarify them for myself

Keep writing them down!!! And the rest of you keep questioning, please.

I am learning so much from this thread. Thank you to all of you.

[digipl]

@mav

at2 the conflicting order is … resolved by chance depending how the two transactions propagate to the elders?

Or not. Could be that neither of the two transfers will be completed.
If there are not enough funds, half of the Elders can sign one transfer and the other half can sign a different one.
In this case neither transfer has the necessary quorum to be approved.
For the consistency of the network there must be some milestone at some point that corrects these discrepancies.

[dirvine]

@digipl

If there are not enough funds, half of the Elders can sign one transfer and the other half can sign a different one.

Nice catch It’s cool though.

Here, what happens is the initiator (the client) sends a “please approve” message to quorum at least nodes. He has to wait then on receipt of these approvals. Then when he has the required set he can send the “approved transfer” again to the network. The transfer currently has a unique ID an causal relationship to a previous transfer (the crdt dot). Part of the validation is that this dot is incremented by exactly 1.

This means that the initiator requires to prove the total order of his transactions. It makes the process quite a bit simpler to understand I recon. Progress in code is looking good and we will fuzz test and use proptest to try and break this one. It should be good as less code is easier to debug for sure. We are also looking at kaos/chaos testing principles as we move closer to … you know what

I hope that helps. (I would think in future the causal order can be relaxed, but in the meantime, if we force that to the client then it reduces network load considerably)

[Southside]

Simplify, then add lightness.

Colin Chapman

Feynmann was the thinker, Chapman was the engineer.

[dirvine]

I don’t think so, if it means running bitcoin/eth nodes then it would not fly for us.

@KafkaLee

Also I think this side-peg is essential to make a coin exchange on network.

I think there are many ways that don’t require any pegging tech. Messages and burn/xfer to secure wallet etc.