FRAGMENTED TRANSACTION PROTOCOL
Tom Elvis Jedusor
17 October, 2018
\****/
Introduction
/****\
A protocol is presented, to obsfucate transaction amounts until the moment the coin is spent.
In general only the receivers know each other's amounts. They prove this by revealing hash
preimages, ownership of whose encodes the fragmented transaction amounts. The script in
fragmented transaction is hashed and opaque, not subject to validation by network nodes.
This makes this proposal well suited for future improvements in the area such as using zero
knowledge proofs or secure multiparty computation that could prove the equation input = sum
of outputs to each member of the anonymity group. These future improvements could cause it so
that the each others amounts would not be known even by the actual members of the anonymity group.
\****/
The protocol for 2 receivers
/****\
To create transactions sender and recipients do the following ritual:
1. Alice and Bob wishing to receive funds from Charlie exchange addresses.
2. Alice creates 3 anonymous true random 256bit numbers, hashes them and sends them
to Bob in specific order.
3. Bob creates 3 anonymous true random 256bit numbers, hashes them and sends them to
Alice in specific order.
4. Alice hashes the amount she receives into Alice's address.
5. Alice hashes the total amount minus the amount Bob receives into Bob's address.
6. Bob hashes the amount he receives into Bob's address.
7. Bob hashes the total amount minus the amount Alice receives into Alice's address.
8. Bobs and Alices hashes are shuffled by Bob according to amounts ratio coding.
9. Bobs and Alices hashes are shuffled by Alice according to amounts ratio coding.
10. The 10-tuple (Script hash, Incoming TX hash(es), Alice's hashed address, Bob's
hashed address, 6 Shuffled hashes) is a fragmented transaction.
- a fragmented transaction with one input and 2 outputs.
- a fragmented transaction with the incoming output must be multiply of 38
satoshi (checked by clients not by network nodes).
- a fragmented transaction with outputs that never exceed the (sum of) inputs
- this is verified at output spend time - first spender wins.
11. Alice signs the fragmented transaction
12. Bob signs the fragmented transaction
13. Charlie sees both Alice and Bob signed the same thing, he discards Alice and
Bob's signatures and attaches his signature.
14. fragmented transaction+funding transactions is included to blockchain (they
must be together in block) and fragmented transaction is now in a hash reveal phase.
15. Once transaction is buried 6 blocks deep, Alice and Bob reveal all their
preimages at random moments of time from random network points.
16. Miners start including the preimages to hashes into blocks into a special
coinbase merkle tree. There is a determined block space in every block for
preimages only. Miners should prioritize preimages whose images are in
transactions that paid more fee per byte.
17. Once LOCKHEIGHT expires caches are checked if they contain all the hashes.
If during LOCKHEIGHT blocks all preimages were revealed fragmented transaction
is committed.
18. If during LOCKHEIGHT blocks not all preimages were revealed fragmented
transaction is rolled back. Coins atomically return to prev output.
19. Once all hashes are buried 6 blocks deep and thus transaction will be
committed Alice and Bob may give out the goods (if any).
20. To spend, Alice signs using her address+reveals her amount. Note that from
this moment observers also know Bob's amount since total minus Alice's=Bob's
\****/
Amounts ratio coding
/****\
Let C = 20 be the fragmenting factor. In a simple scheme the transaction is
fragmented into 0.5/(C-1) = 1/38 of the previous output amount. This is not
always possible, the output amount must be whole multiply of 38 satoshis. This
means when Charlie is spending let's say 38000 satoshis, the recievers Alice,
Bob can recieve the following possibilities (X are the possibilities IDs,
numbers < C):
Alice Bob X Preimage owners
----- ----- -- ---------------
0 38000 0 AAABBB
1000 37000 1 AABABB
2000 36000 2 AABBAB
3000 35000 3 AABBBA
4000 34000 4 ABAABB
5000 33000 5 ABABAB
6000 32000 6 ABABBA
7000 31000 7 ABBAAB
8000 30000 8 ABBABA
9000 29000 9 ABBBAA
10000 28000 10 BAAABB
11000 27000 11 BAABAB
12000 26000 12 BAABBA
13000 25000 13 BABAAB
14000 24000 14 BABABA
15000 23000 15 BABBAA
16000 22000 16 BBAAAB
17000 21000 17 BBAABA
18000 20000 18 BBABAA
19000 19000 19 BBBAAA
Higher granularities can be obtained by using more than 6 hashes / tuning the scheme
for instance making it nonlinear and skewed towards non-dust amounts.
In the first case, using more hashes gives to two users
C=(2*n)!/(n!)^2 possibilities. (Central binomial coefficients)
In general for many users:
C=(U*n)!/(n!)^U
Example table for 3 recievers
"A" Bob "C" X Owners
--- --- --- - ------
0 100 200 0 ABC
0 200 100 1 ACB
100 0 200 2 BAC
200 0 100 3 BCA
100 200 0 4 CAB
200 100 0 5 CBA
Tables are computed by scripts that produce table cells values. Rows sum to T.
\****/
Script details
/****\
Each user agrees on some formula hashed into
the fragmented transaction that specifies how many
coins they get in the case of every possible combination occurs.
Variables are: X = combination, N = user's number we are calculating amount for,
U = total number of users,
T = total amount, R = remaining amount, C = total number of combinations
Example formulas that yield the table in Amounts ratio coding chapter for 2 users:
f(X) = 1000*X
f(X,T,C) = X*T/(2*C-2)
Size:
Depends on the clients, up to 1MB sized scripts on each transaction should be okay.
They are not stored on blockchain. They may be compressed, but hashed into the transaction uncompressed.
Validation:
The formula is repeatedly (for the desired X that is known to the peers) evaluated
starting from N = 0, R = T thru N=current user (user that is validating) towards N=U-2.
User checks whether the amount given to him by the formula is equal to the amount
promised by sender(s) or to the cost of goods or a withdrawal from an exchange.
But execution does not stop there, user also validates the other users amounts and hashes
their received amounts from the formula+user ID's to their addresses-obtains amount hashed addresses.
Stack consists of up to maximum of 100MB? of uint64_t's.
When the formula halts, the topmost stack item is the N-th user's satoshi amount clamped in range 0 to current R.
For an user where the formula would exceed the
remainder R, simply the remainder is given to the user and remainder is thus set to zero.
If the stack machine halts on negative satoshi amount, 0 satoshis are given to the user.
The formula is not evaluated for the last user, simply R satoshis is given to the last user.
Network Nodes + miners need not validate formulas, or scripts. It should be designed so that to a network node,
every formula is "valid" - there are no loops.
Compatibility:
The first byte is script format version equal to byte = 1 (this format). 1 byte is also a NOP instruction.
About specific instructions:
1. We must implement a well compatible script that is "good enough" for common use cases
2. Script must always halt and return some number. If the stack is empty that means zero satoshis.
3. All scripts should halt pretty fast on all inputs on slow smartphone clients (input is the set X, N, U, T, R, C) .
4. It should be easy to write complex (not slow, not large) but difficult to analyze by authorities scripts.
We need all the things that's in C++ basically except loops. Basically anyone should be able
to write in C++ a uint64_t[9] (the variables X,N,U,T,R,C) accepting function without goto,for,while and recursion and
compile it to this script. X is a 256bit number.
Next we need all the instrucions that arent in C++ but should be, like: popcount, base2 logarithm.
+,-,*,/ and bitwises on 256bit numbers (4 limbs,order: to be defined).
Factorial, gamma for 4 limbs. Loggamma. Logarithm of zero, div by zero shall be handled somehow.
could be useful: push the current program counter to stack.
For deterministic random number generation: little endian SHA256 returning 4 limbs?
Never allowed: jump by negative amount (it jumps by positive number of bytes smaller than
remaining number of instructions forward only!)
\****/
Pay to self protocol
/****\
1. Charlie hashes output id=0 and for example his full amount to his address.
2. Charlie hashes output id=1 and for example his zero amount to his other address.
3. Charlie generates the fragmented transaction, uses a legit looking yet
random script that says id=0 gets all coins and id=1 gets no coins.
4. Charlie signs normal transaction + fragmented transaction.
5. Once it's in hash reveal phase, he reveals the hashes from random network points.
6. Once transaction commits, nobody can prove if Charlie paid to other people or to self.
7. Even if authorities force him to reveal script+amounts, all they can think that he
has no coins and somebody else got all the coins.
\****/
Rollback trolling, shills
/****\
Rollback trolling is when group member signs but not commits the transaction.
The solution is to kick the member from the group and try again. Only problem is
much blockchain traffic.
Shills can reveal anonymity group member's amounts. The solution is zero knowledge proofs
or multiparty secure computation.
\****/
More than 2 receivers
/****\
They all know each other's amounts. So they know X. Script is evaluated as normal.
In the future they may use a network enabled script format that allows to express
zero knowledge proofs or multiparty secure computation to prove to each other
that the outputs are valid.