Proposal: merkle tree account signers

[Leigh McCulloch]

I recently considered using pre-authorized transactions, but the minimum reserve cost for having each pre-authorized transaction be a signer was disincentivizing.

Example:

A user wishes to create an account and place funds in the account with a fixed set of outcomes for the funds in that account. A user could create an account, deposit the funds, set several pre-authorized transactions as signers of the account and remove any other signer. An additional 0.5XLM reserve is required in the account to pay for each additional pre-authorized transaction signer. Four pre-authorized transactions are approximately US$0.20 today. The cost becomes more prohibitive if the user wishes to retry transactions. Any pre-authorized transaction may fail consuming its sequence number. To retry a transaction the user would need to add additional transactions as signers, one for each retry. For 10 retries, this increases the minimum reserve cost to US$2.00.

Proposal:

I propose we make using pre-authorized transactions more economical by adding a new signer to accounts and a new signature payload to transactions. The new signer would use a merkle tree to reduce the data needed within ledger entries to a single root hash, and shift the weight of the data required to prove that a transaction is pre-authorized into the transaction signature payload.

A user when building a set of pre-authorized transactions would build a merkle tree where the data blocks are the transactions (or the transaction hashes).

The account signer would be the merkle tree root hash, 32 bytes using SHA256.

The transaction signature payload would be the hashes that make up a merkle branch from the root to the leaf node for the transaction and the transactions index in the tree. The payload size would vary depending on how many transactions were included. For example, 70 bytes if the tree contained a single pre-authorized transaction, 300 bytes for 100 transactions, 650 bytes for 100,000 transactions.

The transaction verification process verifies that the transaction hash lives under the root hash stored in the account, using the hashes stored in the signature payload.

This would make any number of pre-authorized transactions affordable.

There would be some limitations: a maximum depth, to ensure the cost of verification was understood but that depth could probably be sufficiently large. It may be difficult to implement in XDR because signature payloads on transactions do not have an extension point. However, this is not a new issue and we should probably consider how to make it easier to add new signature types in the future anyway.

Does anyone have any thoughts on this?

This is not pressing or blocking anything I'm working on immediately.

Leigh

[Nicolas Barry]

re: use case, retries in the context of sequence numbers getting consumed seems like that smart contract can be broken by a bad actor. Probably worth analyzing the root problem better before deciding that this is a viable solution to that problem.

As far as using merkle trees like that, this is something we discussed a while back in protocol meetings, and didn't move very far with it then because of the change to the envelope and the lack of use cases. I think that kind of change is a lot more doable now that we can swap out the entire transaction envelope.

I suspect the more complicated change in this will be related to fees: bandwidth utilization is probably the biggest factor here, and if we start to tack on potentially large payloads to transactions we may have to revisit the fee model and use a base fee per byte (what basically everybody else is doing) instead of a base fee per operation like we do now.

Nicolas

--
You received this message because you are subscribed to the Google Groups "Stellar Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to stellar-dev...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/stellar-dev/2381b3b3-fc43-4d92-bb0d-19b1078f1127n%40googlegroups.com.

[mister...@cosmic.plus]

I think that's a great idea: as I get it in opens the doors to new use cases that would require too many pre-signed TX, and make the use of those generally cheaper. Removing a tight limitation at a decent cost seems like a good idea.

About the particular example you gave, I'd agree with Nicolas that there must be a better solution. What you need to solve that case properly is an infinite number of retries.

I think that the best solution here is to add a type of transaction that doesn't increment sequence on failure - that could be a simple tx parameter.

Once done, it'll be possible to use any operation as a conditional. For example, having a contract that executes only once an account gathered 10 APPROVAL assets.

I think that's worth digging because here again, you can open many doors for a decent cost. Like, _many_ doors.

MisterTicot

To view this discussion on the web visit https://groups.google.com/d/msgid/stellar-dev/CABf4b3y8ZtBLrX3XVESgsxPmuGGZe640W9WzVGezkCe3F%3DoLDw%40mail.gmail.com.

[Johan Stén]

It's compact on the protocol side of things, since all you need is to add as a signer is the root of the Merkle tree, which is just 32 bytes, assuming SHA-256. However, in order to create the Merkle path the user needs to have access to the full tree, which adds some coordination overhead to the table.

Leigh: I'm not getting the same numbers as you. 2 * 32 bytes * number-of-levels for the Merkle path + 64 bytes for the signature, no?
You could add a one-bit flag to specify which leaf you're signing for, otherwise, just try verifying both.

BR,

Johan

To view this discussion on the web visit https://groups.google.com/d/msgid/stellar-dev/cd8ee90f-d20c-49e9-909e-d1ffb7a8075a%40email.android.com.

[Jonathan Jove]

@MisterTicot About 9 months ago while I was working on fee-bump transactions for protocol 13, I devised a mechanism by which I think it would be possible to allow infinite retries on failure safely. The general concept was similar to a fee-bump transaction:

- Add a new type of transaction and transaction envelope: RetryableTransaction and RetryableTransactionEnvelope. RetryableTransaction does not specify a fee, but is otherwise identical to Transaction.

- Add a new type of transaction and transaction envelope: TryRetryableTransaction and TryRetryableTransactionEnvelope. TryRetryableTransaction contains a source account, sequence number, a fee, and a RetryableTransaction.

- Because RetryableTransaction does not contain a fee it cannot be submitted on its own. But you can submit a RetryableTransaction by wrapping it in a TryRetryableTransaction. The source account of the TryRetryableTransaction pays a fee and has the sequence number consumed _unconditionally_. The sequence number of the RetryableTransaction is only consumed upon success.

Why so much indirection? It prevents two attacks: a denial-of-service attack and a replay attack. If the RetryableTransaction could fail repeatedly without consuming a fee, then it would be possible to deny service by submitting RetryableTransactions that are guaranteed to fail. If the RetryableTransaction could fail repeatedly while consuming a fee, then it would be possible to drain the source account of the RetryableTransaction by repeatedly submitting it when it is expected to fail. TryRetryableTransaction effectively provides a "sacrificial sequence number" that resolves both issues. The key insight is that the TryRetryableTransaction can be unilaterally crafted at the time that the pre-signed transaction needs to be submitted.

What do you think about an approach like this?

To view this discussion on the web visit https://groups.google.com/d/msgid/stellar-dev/CAD8nLm%3DSAvh6wvVqUpxRbd%3DF7ZzD%3D%2BOFwfLPw8FjNxcbLNdoTQ%40mail.gmail.com.

[Leigh McCulloch]

@Nicolas I think failed transactions are unavoidable because of things outside the control of the account. For example if a transaction contains a payment and the destination account can't receive the payment there's a good chance the contract writer would want an opportunity for the destination to be fixed and the transaction retried. If transient failure is possible we need retries, either by pre-authorizing additional transactions or by using some future mechanism such as what Jon suggests.

Also, this is just one example, and the main issue this proposal is addressing is general cost of using pre-authorized transactions. Planning for failed transactions is the example where cost explodes, but in general pre-authorized transactions have a cost limitation.

What signature payload size would be considered large? At what point in size would we need to consider fee impact?

@Johan You're correct my numbers are not accurate. The signature payload sizes were estimates based off a quick proof of concept I coded in Go where I serialized the merkle branch proof using some rudimentary serialization method of a Go type. In reality the numbers would be smaller. Each signature payload would be made up of an 8 byte index plus one 32 bytes for each level of the tree, which are the hashes that can't be computed in the branch. Assuming no overhead, 8 bytes for a single transaction (index+no hashes), 232 bytes for 100 transactions (index+7 hashes), 328 bytes for 1,000 transactions, 552 bytes for 100,000 transactions.

[Johan Stén]

Ah, gotcha... the main path is implicit.. But you'll need both leaves to start, so your numbers will have one more hash. The index is there to specify if you add in a hash on the left or right side of your current node, I assume. If we cap the depth, we could use a fixed-size bitfield instead.

Either way, both setting up a root and sending a transaction using a root requires knowledge of the full tree. It can be offloaded to an external service that keeps a tree and returns a path for you, but *someone* has to do it.

To view this discussion on the web visit https://groups.google.com/d/msgid/stellar-dev/5b3f5b86-d4b5-4baf-bb77-65c9666b5943n%40googlegroups.com.

[Leigh McCulloch]

@Johan Yup the main path can be computed, and actually even at the leaf we only need one hash. We don't need the hash of the transaction to be included in the signature because the party verifying the transaction has the transaction and can hash it to compute the value.

You either need to store the tree, or store a copy of the transaction with the proofs attached as signatures. There might be an opportunity for an external service to store the tree, but the contract creator may want to store it and keep it private. I can see myself storing the transactions prebuilt with the proofs attached rather than the tree.