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
--
Mailing list: https://launchpad.net/~mimblewimble
Post to : mimblewimble@lists.launchpad.net
Unsubscribe : https://launchpad.net/~mimblewimble
More help : https://help.launchpad.net/ListHelp
