search

algorand / go-algorand

Algorand's official implementation in Go.
https://developer.algorand.org/
Other
1.35k stars 471 forks source link

circular transfers failing #1575

Open jeapostrophe opened 4 years ago

jeapostrophe commented 4 years ago

I have the following transaction group:

0: type: appl, from: A, amt: 0, fee: 1000,
1: type: pay, from: B, to: A, amt: 0, fee: 1000
2: type: pay, from: A, to: B, amt: 1000, fee: 1000
3: type: pay, from: A, to: C, amt: 0, fee: 1000

where A's balance is very large, but B and C have zero balances.

My expectation is that this succeeds, because txn 2 gives the B the funds it needs to pay its fee. But, when I run this I get an error:

{"message":"TransactionPool.Remember: transaction ODBLSF6JJZYAEVMDP7O2ON4BNMJLXGIZZW536O5SBTSGJ4WKFRHA: overspend (account 7RR22O4SJSENA2F6WYYMJIRM4RSSK2OKCECIKGDNTET66XZOPSXUZ6T2TQ, data {_struct:{} Status:Offline MicroAlgos:{Raw:0} Rewa
rdsBase:0 RewardedMicroAlgos:{Raw:0} VoteID:[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] SelectionID:[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] VoteFirstValid:0 VoteLastValid:0 VoteKeyDilution:0
 AssetParams:map[] Assets:map[] AuthAddr:AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAY5HFKQ AppLocalStates:map[] AppParams:map[] TotalAppSchema:{_struct:{} NumUint:0 NumByteSlice:0}}, tried to spend {1000})"}

The documentation on atomic transfers claims it supports circular transfers --- https://developer.algorand.org/docs/features/atomic_transfers/ --- but this appears to not be the case.

I did some looking around in the code and I don't see anything that evaluate the fixed point of the transaction group and allow circular transfers like this. But maybe I'm missing something in the code.

My guess is that my group could be re-ordered to pay B first, but that just happens to work in this case. But the general feature of circular transfers needs to be able to solve any ordering.

My txns in base64:

gqNzaWfEQJRr8JuWIAp2sLhn1Q/eZZLXX0DTl31OEu0VYCpZrQucPtMjY8r9UVSUV0agyoHFFOXnWdwpF4G3h+PhcNnoPgijdHhuiaRhcGlkNaNmZWXNA+iiZnbNEC6jZ2VuqWRldm5ldC12MaJnaMQgVTBRy6LxQAy6OhrpOlFuNubh/E8MkOKgNpWtpT8fpwCjZ3JwxCABClFrQcdJRMBDxXijVXCCS4GPGNtuAgidzQJt34lkoKJsds0UFqNzbmTEIOjYBqx+8xsECneuVypovdQ4EOPrTv3noIne++0AKqoKpHR5cGWkYXBwbIKkbHNpZ4KjYXJnlcQgARtNA92MAfEEkUPPnEyBfksWfx0bg+XG8PENiboee87EILaAla3gUo/yLE9gSXeQ7pwdnPddboCBLR00HWeZPWenxAgAAAAAAAAAAMQIAAAAAAAAEC7ECAAAAAAATEtAoWzEygIgBQYBAAUEJgIIAAAAAAAAADUguJKvRAjx+j1K7K+bmHi84o9GT/pInMAMfmJ0vDAHA+0zABAiEkEAijMAGCgXEkEAgTMCECMSQQB5MwIHMQASQQBwMwIIMwEBEkEAZjMDECMSQQBeMwMHKRJBAFYxFiMSQQBPMRAjEkEASDEIJBJBAEExBzMCABJBADgxMSUSQQAxJBYCLRJBACkkMwMIEkEAISMWMwMAUCwEUAIuEkEAEi8XJBJBAAtCAAoyBCEEEkEAACRDI0OjdHhuiaNmZWXNA+iiZnbNEC6jZ2VuqWRldm5ldC12MaJnaMQgVTBRy6LxQAy6OhrpOlFuNubh/E8MkOKgNpWtpT8fpwCjZ3JwxCABClFrQcdJRMBDxXijVXCCS4GPGNtuAgidzQJt34lkoKJsds0UFqNyY3bEIOjYBqx+8xsECneuVypovdQ4EOPrTv3noIne++0AKqoKo3NuZMQg/GOtO5JMiNBovrYwxKIs5GUlacoRBIUYbZkn718ufK+kdHlwZaNwYXmCo3NpZ8RAwv/J8BLUsXeHMT9QL9uRWphYXM7vkEk2H6DQBvW9Lc5W58PsS1ptnBAE0qUZXjyUXcLEutkmieeCEfE6v3eWBaN0eG6Ko2FtdM0D6KNmZWXNA+iiZnbNEC6jZ2VuqWRldm5ldC12MaJnaMQgVTBRy6LxQAy6OhrpOlFuNubh/E8MkOKgNpWtpT8fpwCjZ3JwxCABClFrQcdJRMBDxXijVXCCS4GPGNtuAgidzQJt34lkoKJsds0UFqNyY3bEIPxjrTuSTIjQaL62MMSiLORlJWnKEQSFGG2ZJ+9fLnyvo3NuZMQg6NgGrH7zGwQKd65XKmi91DgQ4+tO/eegid777QAqqgqkdHlwZaNwYXmCo3NpZ8RANdDWIVG57C210s+jXbgrv529EQC52tjCMlZi4GoCeDb5q3dVo6oK4EIGRv77bf+ENdrMN19+ZkhgxZ4rQBb5D6N0eG6Jo2ZlZc0D6KJmds0QLqNnZW6pZGV2bmV0LXYxomdoxCBVMFHLovFADLo6Guk6UW425uH8TwyQ4qA2la2lPx+nAKNncnDEIAEKUWtBx0lEwEPFeKNVcIJLgY8Y224CCJ3NAm3fiWSgomx2zRQWo3JjdsQguJKvRAjx+j1K7K+bmHi84o9GT/pInMAMfmJ0vDAHA+2jc25kxCDo2AasfvMbBAp3rlcqaL3UOBDj607956CJ3vvtACqqCqR0eXBlo3BheQ==
brianolson commented 4 years ago

this is probably an issue for developer forums https://forum.algorand.org/

jeapostrophe commented 4 years ago

Hi @brianolson , I don't understand what you mean.

Do you mean that the software is working as expected and there is a documentation error and they want those reported on the forum? The documentation --- https://developer.algorand.org/docs/features/atomic_transfers/ --- says, "Atomic transfers enable use cases such as: Circular trades - Alice pays Bob if and only if Bob pays Claire if and only if Claire pays Alice." Is that right or wrong?

My read is that the software should support use cases where if before

And the transaction group says

Then the should be successful and at the end

Isn't that what "circular transfer" means? Notice that this transaction group has no linearizable solution, because everyone starts off transferring things they don't have.

I'm coming from the perspective that the documentation is an authoritative specification of what the code is supposed to do.

As for how to support this, I think it just a simple mistake in the code,

This check in roundCowState.Move:

https://github.com/algorand/go-algorand/blob/79e639de1b9a2a36c7f399fac1ca5c1049f13c3f/ledger/eval.go#L143

and these checks in BlockEvaluator.transaction:

https://github.com/algorand/go-algorand/blob/79e639de1b9a2a36c7f399fac1ca5c1049f13c3f/ledger/eval.go#L696

should be moved to after all of the transactions have been inspected in BlockEvaluator.transactionGroup:

https://github.com/algorand/go-algorand/blob/79e639de1b9a2a36c7f399fac1ca5c1049f13c3f/ledger/eval.go#L606

That way, you check to make sure at the end of the entire group the rules are satisfied, rather than in the middle, so that later txns in the same group will be allowed to provide input to earlier ones. I don't know if the ledger data structure needs to be changed to allow signed integers, but that might be an annoying wrinkle.

tsachiherman commented 4 years ago

@jeapostrophe, what you want here is more then just a circular funds transfer ( which allows the same account to be used as both the source and the destination on a single transaction group). The order in which the transactions are evaluated within the transaction group has to remain the same, since these might be inspected by a TEAL code. That takes out the ability to reorder transactions. As for allowing account to "temporarily" remain with a zero or negative amount during the transaction group evaluation - this is something we would need to research further, as I'm not sure if it's safe to do with our existing implementation. One place which I think would be problematic is that when executing TEAL code, it might want to refer to the accounts data, and find that it has a (temporary) negative value. At this point, all TEAL code would need to know how to handle negative balance correctly..

Priegle commented 4 years ago

hey @jeapostrophe - just want to make sure i'm super clear on where you're coming from.

I think the core question here is, A) does each tx in a group need to succeed, in order, for the entire group to succeed or B) as long as the net result of a group is successful, the group will succeed.

The current behavior reflects our explicit design. It requires A - each tx in a group need to succeed, in order, for the entire group to succeed.

A secondary question seems to be how does one define a "circular trade" with the same core question. It sounds like your perspective is that a "circular trade" should ignore the order of transactions in a group and should instead focus on the net result. Our perspective is that circular trades are possible with the current implementation - with the exception of a circular trade which has individual transaction inside of it that would fail on their own, when executed in order. We will update the documentation to clearly reflect that.

The behavior you're looking for here is definitely not unreasonable though - we can take a look at potentially changing the behavior in the future. Could you help me understand the scenario in which the txs can't be ordered correctly or its better/more efficient not to?

Does this cover the issue at hand or did I misinterpret?

jeapostrophe commented 4 years ago

I agree with your read of A vs B.

One could imagine a version of Algorand where each transaction only saw the "before" state so that a later txn might fail even though an early txn gave it the necessary funds. You didn't do that.

I'd say that you have "left-to-right" transfers within an atomic group and not circularity, because in my mind, circularity is not about the direction of funds, but about the idea of unbreakable dependency in the transfers.

As far use cases, I spontaneously discovered this, based on dApp's transfer patterns, but in my particular use case, I was able to re-order things.

My example, in the reply to Brian, has a situation where the circularity is necessary. How might this arise is practice? I'm not sure; I believe that we have precedent in the real world for X borrowing money from Y which lends to Z which lends to X again. If such an obligation were to be discharged atomically, then you could get a situation like this.

My expectation is that we should think of this as necessary for compositionality of transactions and transaction groups. Think of it like deadlock... you don't plan for their to be a cycle in your dependency graph, but you have an operation F that involves two resources X & Y and an operation G that involves two resources A & B, then some extra use sets X = B, so now you have a cycle that the individual components didn't know about. With the current Algo design, you'll fail in this composition, but you don't have to, because you could only look at the final state rather than the intermediate states.