mimblewimble team mailing list archive

[A Nargle <nargle@xxxxxxxxxxxxxx>]

Here are two related ideas for enforcing per-output lock times that perfectly hide what lock time value was chosen. The first is simpler, but scales linearly in the number of different lock times we allow. The second requires signature validation operations, but it scales logarithmically and the signature operations can be batched. In combination, they seem quite practical.

Suppose that the only locktimes we allow are 0, 1, 2, ..., n. This isn't strictly necessary, but simplifies the presentation. Suppose we want to validate a transaction that is m blocks farther in the chain than the output it spends. We'll assume that m < n, since if m ≥ n, the locktime condition is necessarily satisfied, so the transaction needs no further validation. In both approaches, we require that the spender reveal the preimage of the hashed switch commitment. For extensibility, it should have multiple fields, but one of them is what determines the locktime. Call this field Y.

In the first approach, we require that the spender reveal a (n-m) times iterated preimage of Y under some hash function. That is, they must reveal an X such that

Y = H(H(H(...H(X)...)))

where the hash function is called (n-m) times. To give a concerete example, if we allow locktimes up to 4 and someone wants to spend a value in the block immediately following where it was created, they must reveal X such that Y = H(H(H(X))). If they choose to wait another block, they reveal X' such that Y = H(H(X')). If they wait yet another block, they reveal X'' such that Y = H(X'').

Note that these transactions are still monotonic. If a transaction is sitting in the mempool and doesn't make it into the block, the miners can easily update them to be spendable in the next block. Note that if Y = H(H(H(X))), then we can define X' = H(X) and X'' = H(X') and the equations for the later blocks Y = H(H(X')) and Y = H(X'') are satisfied.

To create one of these transactions, pick a random string X. Then, hash it repeatedly. If you want a locktime of m, then hash it (n-m) times. Put the result into the hashed switch commitment and reveal X and m to the owner of the output.

This approach requires up to n hash function evaluations for every input in a block, which may be prohibitively expensive for large n.

In the second approach, we use a Goldreich-style tree of one-time signatures (though in a stateful way, and the one-time signature scheme could just be to use Schnorr signatures). We fix a standard tree structure over n leaves, labeled with the possible locktimes.

To spend an output at distance m, the transaction must reaveal, for every node q along the path from the root of the tree to m:
- A signature, signed by a public key associated with q, of the public keys associated with all of q's children.
- A public key of each sibling of q to the left of q.
- The public key of q.
- A private key of each sibling of q to the right of q.
The public key at the root is Y, the value revealed in the hashed switch commitment.

To give a concrete example, suppose we allow locktimes up to n=8, organized in a balanced binary tree, and we want to spend an output m=2 blocks after it was created. The Rs are public keys, the rs are private keys corresponding to them, || is concatenation. Since Y is a public key, we say R_{0-7} = Y. We release:
- Signature of (R_{0-3} || R_{4-7}) with R_{0-7}
- R_{0-3}, r_{4-7}
- Signature of (R_{0-1} || R_{2-3}) with R_{0-3}
- R_{0-1}, R_{2-3}
- Signature of (R_{2-2} || R_{3-3}) with R_{2-3}
- R_{2-3}, r_{3-3}


Note that these transactions are still monotonic. If a transaction is sitting in the mempool and doesn't make it into the block, the miners can easily update them to be spendable in the next block. The miner finds the next private key in line and converts it into a public key for release. If this new private key is at a node with children, then the miner randomly chooses new private keys for the children, then signs the resultant public keys, and recurses into the first branch and hitting a leaf. It may be more profitable for the miner to wait with this process until it knows the transaction will be included in a block, however, since it takes roughly the same amount of work to move this timelock proof several steps forward as it does to move a single step.

To create one of these transactions, pick a random private key r. Place the public key corresponding to r in the hashed switch commitment. If a you want no locktime requirement, give r to the owner of the output. Otherwise, pick random private keys in a path leading to leaf m, where m is the locktime. Sign all the intermediate public keys, and give the resultant locktime proof to the owner of the output.

This approach requires log_d(n) signature validations and up to (d-1)log_d(n) private to public key conversions for every input in a block for a balanced tree of branching factor d. The tree could be unbalanced or have several different degrees, however. By unbalancing the tree, it can have infinitely many leaves, where leaf m has depth approximately log(m).

The two approaches can be combined with each other, using a small number iterated hashes at the leaves of a signature tree. If the public keys are hashed as H(H(H(R_0 || R_1) || R_2) || R_3)... before signing, then all the public keys released at a level can be collapsed into a single value.

As a tradeoff, instead of allowing all locktimes in the range 0-n for some n (or all locktimes period), we could choose an arbitrary set of allowed locktimes. When releasing a transaction that is in between two allowed locktimes, we use a proof for previous locktime. Since the desired granularity of locktimes is likely lower for longer locktimes, an exponential schedule (e.g. 1, 2, 3, 4, 6, 8, 10, 12, 16, 20, 24, 28, 36, 44, 52, 60, etc.) or some otherwise accelerating schedule might make sense. If combined with an infinite unbalanced tree, the locktime proof for a transaction spending an output created m blocks ago would scale as log(log(m)).

A Nargle
4c503e3d099187fab4240b771511a0104f4a496501b3cee0a26ffcf65f7630a1
5895404bb5a01d5c757edb1c7c350cbbada11786e1187e44d2bbf4308bfe3179