/*
	It's multi-sig wallet that isn't storing public keys on chain, but rather
	computes merkle tree root hash out of them. It attempts to minimize
	storage that is used, in expense of storage to store the code and
	gas required to check proofs. At the moment it lacks admin features
	such as adding new keys or removing pending orders.

	Initially public keys are set in stateinit as numbered list. The first thing
	that is done is converting them into roothash. To build proof client may pull
	keys that went into building the tree from stateinit.

	When order with attached list of signatures (along with proofs) arrives
	key numbers are used to flip bits in confirmations bitset. Once required
	number of bits is collected order's tx is sent.

	Sequence numbers are attached to new orders, rather than individual
	transactions. Order body is not stored on chain and required to be sent
	with each message. There is no 'expiration' dict for garbage collection,
	but rather a mechanism to point contract to expired order so related
	data can be removed.

	It currently supports up to 253 keys, but can be extended further.

	The file below contains contract code, followed by fift primitives to
	serialize messages and construct proofs, then there are tests that
	describe order lifecycle and state transitions, and simple testnet example.
*/

"Asm.fif" include

0  constant OK
34 constant ERR_SIGNATURE_INVALID
35 constant ERR_SIGNATURE_KEY_INVALID
36 constant ERR_SIGNATURE_PROOF_ERR
37 constant ERR_SIGNATURE_MISSING
38 constant ERR_SIGNATURE_REPLAY
40 constant ERR_ORDER_NOT_FOUND
41 constant ERR_ORDER_EXPIRED
50 constant ERR_NUMKEYS_COUNT
60 constant ERR_OP_UNKNOWN
61 constant ERR_MSG_TYPE_UNKNOWN
70 constant ERR_UNREACHABLE

-1     constant MSG_TYPE_EXTERNAL
0      constant MSG_TYPE_INTERNAL
85143  constant MSG_TYPE_SEQNO
101736 constant MSG_TYPE_N
116780 constant MSG_TYPE_ROOTHASH
72782  constant MSG_TYPE_CONFIRMS_FOR

100001 constant OP_SET_NEW_NUMKEYS
100002 constant OP_DELETE_CONFIRMS_FOR

x{8_} constant EMPTY_SLICE


// MERKLE
{
	DUP TLEN EXPLODEVAR
	<{ DUP 1 INT GREATER }> PUSHCONT <{
		ROTREV
		MINMAX NEWC 256 STU 256 STU ENDC HASHCU
		OVER DEC ROLLREVX
		DEC
	}> PUSHCONT WHILE
	DROP
} : MERKLE:GET_ROOTHASH


// ITER
{                                                                                // s
	LDREFRTOS SWAP                                                                 // iter, s'
} : ITER:LD

{                                                                                // s
	1 LDU SWAP <{                                                                  // s'
		ITER:LD                                                                      // iter, s'
	}> PUSHCONT <{
		EMPTY_SLICE PUSHSLICE SWAP
	}> PUSHCONT IFELSE
} : ITER:LD_NULLREF

{
	DUP SBITS ISZERO SWAP SREFS ISZERO AND
} : ITER:CHKEMPTY

{                                                                                // iter
	DUP SBITS <{                                                                   // iter
		TRUE                                                                         // iter, true
	}> PUSHCONT <{                                                                 // iter
		DUP SREFS 1 INT EQUAL <{                                                     // iter
			LDREF ENDS CTOS TRUE                                                       // list_next, true
		}> PUSHCONT <{                                                               // iter
			ENDS FALSE                                                                 // false
		}> PUSHCONT IFELSE
	}> PUSHCONT IFELSE
} : ITER:LDNEXTRQ


// HHASH_ITER
{
	ITER:LD_NULLREF
} : HHASH_ITER:LD

{                                                                                // hhash_iter, hash
	SWAP                                                                           // hash, hhash_iter
	<{ ITER:LDNEXTRQ }> PUSHCONT <{                                                // hash, hhash_iter'
		1 LDU LDREF 3 ROLLREV                                                        // hhash_iter', hash, hash_pos, hhash_cell
		DUP HASHCU                                                                   // hhash_iter', hash, hash_pos, hhash_cell, hash_next
		4 ROLLREV                                                                    // hash_next, hhash_iter', hash, hash_pos, hhash_cell
		CTOS 256 LDU 256 LDU ENDS CONDSEL                                            // hash_next, hhash_iter', hash, hash_expected
		EQUAL NOT ERR_SIGNATURE_PROOF_ERR THROWIFNOT                                 // hash', hhash_iter
	}> PUSHCONT WHILE
} : HHASH_ITER:HASH_WITH


// SIG
{ 0 INDEX } : SIG:GET_SIGNATURE
{ 1 INDEX } : SIG:GET_KEY
{ 2 INDEX } : SIG:GET_KEY_NO
{ 3 INDEX } : SIG:GET_ROOTHASH

{                                                                                // s
	512 INT LDSLICEX                                                               // s_sig, s'
	DUP 264 INT PLDSLICEX HASHSU ROTREV                                            // hash, signature, s
	256 LDU 8 LDU HHASH_ITER:LD                                                    // hash, signature, key, no, hhash_iter, s'
	s0 s5 XCHG                                                                     // s', signature, key, no, hhash_iter, hash
	HHASH_ITER:HASH_WITH                                                           // s', signature, key, no, roothash
	4 TUPLE SWAP                                                                   // sig, s
} : SIG:LD

{                                                                                // sig, order_hash
	OVER SIG:GET_SIGNATURE                                                         // sig, order_hash, signature
	ROT SIG:GET_KEY                                                                // order_hash, signature, key
	CHKSIGNU
} : SIG:CHK_SIGNATURE

{                                                                                // sig, roothash
	SWAP SIG:GET_ROOTHASH EQUAL
} : SIG:CHK_ROOTHASH


// SIG_ITER
{                                                                                // s
	ITER:LD_NULLREF
} : SIG_ITER:LD

{
	ITER:LDNEXTRQ <{                                                                   // s
		SIG:LD SWAP TRUE                                                             // s, sig, true
	}> PUSHCONT <{                                                                 //
		FALSE                                                                        // false
	}> PUSHCONT IFELSE
} : SIG_ITER:LDNEXTRQ

{
	ITER:CHKEMPTY
} : SIG_ITER:CHKEMPTY


// NUMKEY
{ 0 INDEX } : NUMKEY:GET_KEY
{ 1 INDEX } : NUMKEY:GET_NO
{ 2 INDEX } : NUMKEY:GET_HASH

{                                                                                // s
	264 INT LDSLICEX SWAP HASHSU SWAP                                              // hash, s
} : NUMKEY:LD_HASH

{                                                                                // s
	264 INT LDSLICEX SWAP                                                          // s', s_numkey
	DUP HASHSU SWAP 256 LDU 8 LDU ENDS                                             // s, hash, key, no
	ROT 3 TUPLE SWAP                                                               // numkey, s
} : NUMKEY:LD


// NUMKEY_ITER
{
	ITER:LD
} : NUMKEY_ITER:LD

{                                                                                // numkey_iter
	NIL SWAP                                                                       // hashes[], numkey_iter
	<{ ITER:LDNEXTRQ }> PUSHCONT <{                                                // hashes[], numkey_iter'
		NUMKEY:LD_HASH                                                               // hashes[], hash, numkey_iter'
		ROTREV TPUSH SWAP                                                            // hashes[]', numkey_iter
	}> PUSHCONT WHILE                                                              // hashes[]
} : NUMKEY_ITER:GET_HASHES


// ORDER
{ 0 INDEX } : ORDER:GET_SEQNO
{ 1 INDEX } : ORDER:GET_EXP
{ 2 INDEX } : ORDER:GET_MODE
{ 3 INDEX } : ORDER:GET_TX
{ 4 INDEX } : ORDER:GET_HASH

{                                                                                // s
	72 INT 1 INT SPLIT SWAP                                                        // s', s_order
	DUP HASHSU SWAP                                                                // s, hash, s_order
	32 LDU 32 LDU 8 LDU LDREF ENDS                                                 // s, hash, seqno, exp, mode, tx
	4 ROLL 5 TUPLE SWAP                                                            // order, s
} : ORDER:LD

{
	ORDER:GET_EXP NOW LEQ
} : ORDER:CHKEXP


// CONFIRMS
{ 0 INT }   : CONFIRMS:NONE
{ OR }      : CONFIRMS:MERGE_WITH
{ POW2 OR } : CONFIRMS:SET_FOR
{ ISZERO }  : CONFIRMS:IS_NONE

{                                                                                // confirms
	0 INT 0 INT                                                                    // confirms, exp, count
	s2 PUSH UBITSIZE <{                                                            // confirms, exp, count
		OVER POW2 s3 PUSH                                                            // confirms, exp, count, 2^exp, confirms
		AND SGN                                                                      // confirms, exp, count, 0/1
		ADD                                                                          // confirms, exp, count'
		SWAP INC SWAP                                                                // confirms, exp', count
	}> PUSHCONT REPEAT
	ROTREV 2DROP                                                                   // count
} : CONFIRMS:GET_COUNT

{                                                                                // confirms, b
	OVER UBITSIZE 8 STUR OVER UBITSIZE STUX                                        // b'
} : CONFIRMS:ST

{                                                                                // s
	8 LDU SWAP LDUX                                                                // confirms, s'
} : CONFIRMS:LD


// STATE
{ 0 INDEX } : STATE:GET_SEQNO          { 0 SETINDEX } : STATE:SET_SEQNO
{ 1 INDEX } : STATE:GET_N              { 1 SETINDEX } : STATE:SET_N
{ 2 INDEX } : STATE:GET_ROOTHASH       { 2 SETINDEX } : STATE:SET_ROOTHASH
{ 3 INDEX } : STATE:GET_CONFIRMS_DICT  { 3 SETINDEX } : STATE:SET_CONFIRMS_DICT

{
	DUP STATE:GET_SEQNO INC STATE:SET_SEQNO
} : STATE:INC_SEQNO

{                                                                                // state, order_hash
	SWAP STATE:GET_CONFIRMS_DICT                                                   // order_hash, confirms_dict
	256 INT DICTUGET ERR_ORDER_NOT_FOUND THROWIFNOT                                // s_confirms
	CONFIRMS:LD ENDS                                                               // confirms
} : STATE:GET_CONFIRMS_FOR

{                                                                                // state, order_hash, confirms
	NEWC CONFIRMS:ST SWAP                                                          // state, b, order_hash
	s2 PUSH STATE:GET_CONFIRMS_DICT                                                // state, order_hash, b, confirms_dict
	256 INT DICTUADDB ERR_UNREACHABLE THROWIFNOT                                   // state, confirms_dict'
	STATE:SET_CONFIRMS_DICT                                                        // state'
} : STATE:STORE_CONFIRMS_FOR

{                                                                                // state, order_hash
	OVER STATE:GET_CONFIRMS_DICT                                                   // state, order_hash, confirms_dict
	256 INT DICTUDELGET ERR_ORDER_NOT_FOUND THROWIFNOT                             // state, confirms_dict', s_confirms
	CONFIRMS:LD ENDS                                                               // state, confirms_dict, confirms
	ROTREV STATE:SET_CONFIRMS_DICT                                                 // confirms, state'
} : STATE:DELGET_CONFIRMS_FOR

{                                                                                // state, order_hash
	OVER STATE:GET_CONFIRMS_DICT                                                   // state, order_hash, confirms_dict
	256 INT DICTUDEL ERR_ORDER_NOT_FOUND THROWIFNOT                                // state, confirms_dict'
	STATE:SET_CONFIRMS_DICT                                                        // state'
} : STATE:DELETE_CONFIRMS_FOR

{                                                                                // state, n, numkey_iter
	NUMKEY_ITER:GET_HASHES                                                         // state, n, numkey_hashes[]
	OVER OVER TLEN GREATER ERR_NUMKEYS_COUNT THROWIF                               // state, n, numkey_hashes[]
	MERKLE:GET_ROOTHASH                                                            // state, n, roothash
	ROTREV STATE:SET_N                                                             // roothash, state'
	SWAP STATE:SET_ROOTHASH                                                        // state'
	NEWDICT STATE:SET_CONFIRMS_DICT                                                // state'
} : STATE:SET_NEW_NUMKEYS

{
	SWAP 4 UNPACKFIRST 5 0 REVERSE
	32 STU 8 STU 256 STU STDICT
} : STATE:ST


// STATE_INIT
{ 1 INDEX } : STATE_INIT:GET_N
{ 2 INDEX } : STATE_INIT:GET_NUMKEY_ITER

{
	1 INT
	SWAP DUP STATE_INIT:GET_N
	SWAP STATE_INIT:GET_NUMKEY_ITER NUMKEY_ITER:GET_HASHES MERKLE:GET_ROOTHASH
	NEWDICT
	4 TUPLE
} : STATE_INIT:GET_STATE_1


// C4
{ 0 INDEX } : C4:GET_SEQNO

{
	C4:GET_SEQNO ISZERO
} : C4:IS_STATE_INIT

{
	32 LDU
	OVER ISZERO <{
		8 LDU NUMKEY_ITER:LD
		3 ROLLREV 3 TUPLE SWAP
	}> PUSHCONT <{
		8 LDU 256 LDU LDDICT
		4 ROLLREV 4 TUPLE SWAP
	}> PUSHCONT IFELSE
} : C4:LD

<{
	SETCP0

	DUP MSG_TYPE_EXTERNAL INT EQUAL <{                                             // msg, msg_type_external
		DROP c4 PUSHCTR CTOS C4:LD ENDS                                              // msg, c4

		DUP C4:IS_STATE_INIT <{                                                      // msg, state_init
			// init state transition
			NIP                                                                        // state_init
			ACCEPT
			STATE_INIT:GET_STATE_1                                                     // state
			NEWC STATE:ST ENDC c4 POP
		}> PUSHCONT IFJMP

		SWAP ORDER:LD SIG_ITER:LD ENDS                                               // state, order, sig_iter

		OVER ORDER:CHKEXP <{
			// new already expired order
			s2 PUSH STATE:GET_SEQNO
			s2 PUSH ORDER:GET_SEQNO
			EQUAL ERR_ORDER_EXPIRED THROWIF

			// removing expired order require message with 0 signatures
			// so not to confuse with successfully sent transaction
			SIG_ITER:CHKEMPTY ERR_ORDER_EXPIRED THROWIFNOT

			// another requirement is that it actually exists                          // state, order
			ORDER:GET_HASH STATE:DELETE_CONFIRMS_FOR
			ACCEPT NEWC STATE:ST ENDC c4 POP
		}> PUSHCONT IFJMP                                                            // state, order, sig_iter

		s2 PUSH STATE:GET_SEQNO s2 PUSH ORDER:GET_SEQNO EQUAL <{
			ROT STATE:INC_SEQNO ROTREV                                                 // state', order, sig_iter
			CONFIRMS:NONE                                                              // state, order, sig_iter, confirms_bfr
		}> PUSHCONT <{                                                               // state, order, sig_iter
			ROT s2 PUSH ORDER:GET_HASH STATE:DELGET_CONFIRMS_FOR 3 ROLLREV             // state', order, sig_iter, confirms_bfr
		}> PUSHCONT IFELSE

		DUP 3 2 BLKSWAP                                                              // confirms_bfr, confirms_aft, state', order, sig_iter
		DUP SIG_ITER:CHKEMPTY ERR_SIGNATURE_MISSING THROWIF

		<{ SIG_ITER:LDNEXTRQ }> PUSHCONT <{                                          // ... , state, order, sig_iter', sig
			// I could not throw signature check exception,
			// because i might have already accepted the message
			DUP s3 PUSH ORDER:GET_HASH SIG:CHK_SIGNATURE <{                            // ... , state, order, sig_iter, sig
				DUP s4 PUSH STATE:GET_ROOTHASH SIG:CHK_ROOTHASH <{
					// s4 PUSH ISZERO 1 THROWIFNOT // uncomment for gas usage test
					4 ROLL SWAP SIG:GET_KEY_NO CONFIRMS:SET_FOR                            // confirms_bfr, state, order, sig_iter, confirms_aft'
					DUP s5 PUSH NEQ <{ ACCEPT }> PUSHCONT IF
					3 ROLLREV                                                              // confirms_bfr, confirms_aft, state, order, sig_iter
				}> PUSHCONT IFJMP
			}> PUSHCONT IFJMP

			DROP
		}> PUSHCONT WHILE                                                            // confirms_bfr, confirms_aft, state, order

		2 2 BLKSWAP                                                                  // state, order, confirms_bfr, confirms_aft
		2DUP EQUAL ERR_SIGNATURE_REPLAY THROWIF
		NIP

		DUP CONFIRMS:GET_COUNT s3 PUSH STATE:GET_N LESS <{                           // state, order, confirms
			SWAP ORDER:GET_HASH SWAP                                                   // state, order_hash, confirms
			STATE:STORE_CONFIRMS_FOR                                                   // state'
		}> PUSHCONT <{                                                               // state, order, confirms
			DROP                                                                       // state, order
			DUP ORDER:GET_TX SWAP ORDER:GET_MODE SENDRAWMSG                            // state
		}> PUSHCONT IFELSE

		NEWC STATE:ST ENDC c4 POP
	}> PUSHCONT IFJMP

//	DUP MSG_TYPE_INTERNAL INT EQUAL <{                                           // msg, msg_type_internal
//		DROP                                                                       // msg
//
//		c4 PUSHCTR CTOS C4:LD ENDS SWAP                                            // state, msg
//		32 LDU                                                                     // state, op_code, msg
//
//		OVER OP_SET_NEW_NUMKEYS INT EQUAL <{
//			NIP 8 LDU NUMKEYS:LD ENDS                                                // state, n, numkeys
//			STATE:SET_NEW_NUMKEYS                                                    // state'
//			NEWC STATE:ST ENDC c4 POP
//		}> PUSHCONT IFJMP
//
//		OVER OP_DELETE_CONFIRMS_FOR INT EQUAL <{
//			NIP 256 LDU ENDS                                                         // state, order_hash
//			STATE:DELETE_CONFIRMS_FOR                                                // state'
//			NEWC STATE:ST ENDC c4 POP
//		}> PUSHCONT IFJMP
//
//		ERR_OP_UNKNOWN THROW
//	}> PUSHCONT IFJMP

	DUP MSG_TYPE_SEQNO INT EQUAL <{
		DROP c4 PUSHCTR CTOS C4:LD ENDS
		STATE:GET_SEQNO
	}> PUSHCONT IFJMP

	DUP MSG_TYPE_N INT EQUAL <{
		DROP c4 PUSHCTR CTOS C4:LD ENDS
		STATE:GET_N
	}> PUSHCONT IFJMP

	DUP MSG_TYPE_ROOTHASH INT EQUAL <{
		DROP c4 PUSHCTR CTOS C4:LD ENDS
		STATE:GET_ROOTHASH
	}> PUSHCONT IFJMP

	DUP MSG_TYPE_CONFIRMS_FOR INT EQUAL <{                                         // order_hash, msg_type_confirms_for
		DROP c4 PUSHCTR CTOS C4:LD ENDS
		STATE:GET_CONFIRMS_FOR
	}> PUSHCONT IFJMP

	ERR_MSG_TYPE_UNKNOWN THROW
}>c constant contract-code

{                                                                                // leafs, hash
	explode                                                                        // h1, [], ... hn, l
	{ dup 1 > } {
		-rot
		over tuple? { , } {
			dup tuple? { swap , } {
				minmax <b swap 256 u, swap 256 u, b> hashu
			} cond
		} cond
		over 1 - -roll
		1 -
	} while
	drop
} : merkle-hhash

{                                                                                // b, null|cell
	dup null? {
		drop 0 1 u,
	} {
		swap 1 1 u, swap ref,
	} cond                                                                         // b'
} : nullref,

{
	dup sbits 0= {                                                                 // s
		dup srefs 0= { false } {
			ref@+ swap s> <s true
		} cond
	} { true } cond
} : iter-next@+

{                                                                                // keys[]
	dup count 0= abort"empty list of keys"

	0 swap {                                                                       // i, keys[]
		over 3 mod 0= { <b -rot } if                                                 // b_prev, b, i, keys[]
		over over over []                                                            // ..., b, i, keys[], no, key
		4 roll                                                                       // ..., i, keys[], no, key, b
		swap B, swap 8 u, -rot                                                       // ..., b', i, keys[]
		swap 1 + swap                                                                // ..., b, i', keys[]
	} over count times                                                             // b1, ... bn, i, keys[]

	drop { b> ref, } swap 3 /c 1 - times
	b>                                                                             // numkeys
} : numkeys

{                                                                                // hhash[], agg_hash
	over count 0= {
		2drop null
	} {
		swap                                                                         // agg_hash, hhash[]
		0 swap {                                                                     // agg_hash, i, hhash[]
			over 3 mod 0= { <b 3 -roll } if                                            // b_prev, b, agg_hash, i, hhash[]
			2dup swap []                                                               // ..., b, agg_hash, i, hhash[], hhash
			3 roll                                                                     // ..., b, i, hhash[], hhash, agg_hash
			2dup > abs -rot                                                            // ..., b, i, hhash[], agg_hash_pos, hhash, agg_hash
			minmax <b swap 256 u, swap 256 u, b>                                       // ..., b, i, hhash[], agg_hash_pos, hhash_item
			dup hashu                                                                  // ..., b, i, hhash[], agg_hash_pos, hhash_item, agg_hash
			4 -roll                                                                    // ..., b, agg_hash, i, hhash[], agg_hash_pos, hhash_item
			5 roll                                                                     // ..., agg_hash, i, hhash[], agg_hash_pos, hhash_item, b
			swap ref, swap 1 u,                                                        // ..., agg_hash, i, hhash[], b'
			3 -roll                                                                    // ..., b, agg_hash, i, hhash[]
			swap 1 + swap                                                              // ..., b, agg_hash, i', hhash[]
		} over count times                                                           // b1, ... bn, agg_hash, i, hhash[]
		drop nip { b> ref, } swap 3 /c 1 - times
		b>                                                                           // hhash_list
	} cond
} : hhash-list

{                                                                                // numbered_keys, key
	256 B>u@ swap                                                                  // key', numbered_keys
	| swap <s { iter-next@+ } {                                                    // key, leafs[], s
		256 u@+ swap                                                                 // key, leafs[], s', key_n
		dup 4 pick = {
			drop swap | , swap                                                         // key, leafs[]', s
			8 u@+ swap 3 -roll                                                         // no, key, leafs[], s'
		} {                                                                          // ..., key, leafs[], s, numbered_key
			swap 8 u@+                                                                 // ..., key, leafs[], key_n, no, s'
			3 0 reverse                                                                // ..., key, leafs[], s, no, key_n
			<b swap 256 u, swap 8 u, b> hashu                                          // ..., key, leafs[], s, merkle_leaf
			1 2 exch2 , swap                                                           // ..., key, leafs[]', s
		} cond
	} while                                                                        // no, key, leafs[], s

	s> merkle-hhash                                                                // no, key, hhash[]
	-rot 2dup <b swap 256 u, swap 8 u, b> hashu                                    // hhash[], no, key, hash
	3 roll swap                                                                    // no, key, hhash[], hash
	hhash-list -rot                                                                // hhash_list, no, key
	<b swap 256 u, swap 8 u, swap nullref, b>                                      // proof
} : numkeys-proof-for

{                                                                                // signature, proof
  swap <b swap B, swap <s s, b>
} : sig

{                                                                                // sig[]
	dup count 0= {
		drop null
	} {
		0 swap {                                                                     // i, sig[]
			<b -rot                                                                    // b_prev, b, i, sig[]
			2dup swap []                                                               // ..., b, i, sig[], sig
			3 roll                                                                     // ..., i, sig[], sig, b
			swap <s s, -rot                                                            // ..., b', i, sig[]
			swap 1 + swap                                                              // ..., b, i', sig[]
		} over count times                                                           // b1, ... bn, i, sig[]

		drop { b> ref, } swap 1 - times
		b>                                                                           // sig_list
	} cond
} : sig-list

{                                                                                // seqno, exp, mode, tx<>
	4 0 reverse
	<b swap 32 u, swap 32 u, swap 8 u, swap ref, b>
} : order

{                                                                                // order, pvtkey, proof
	rot hashu rot                                                                  // proof, order_hash, pvtkey
	ed25519_sign_uint swap                                                         // signature, proof
	sig
} : order-sign

// comment next line to run tests // /*
// /*

"TonUtil.fif" include

{                                                                                // n
	| swap { newkeypair drop , } swap times                                        // pvtkeys[]
} : test-pvtkeys

{                                                                                // prefix, n
	| swap {
		over "_key" $+ over count 1 + (.) $+ +".pk" load-generate-keypair nip ,
	} swap times nip                                                               // pvtkeys[]
} : test-pvtkeys-saved

{                                                                                // pvtkeys[]
	explode {
		swap priv>pub
		over -roll
	} over times tuple                                                             // keys[]
} : priv[]>pub[]

{                                                                                // pvtkeys[], n
	over explode {
		swap
		priv>pub
		over -roll
	} over times tuple numkeys -rot                                                // numkeys, pvtkeys[], n
	[] priv>pub                                                                    // numkeys, key_n
	numkeys-proof-for                                                              // proof_n
} : test-proof-n

{                                                                                // order, pvtkeys[], n
	2dup test-proof-n -rot                                                         // order, proof_n, pvtkeys[], n
	[] swap                                                                        // order, pvtkey_n, proof_n
	order-sign                                                                     // sig
} : test-sign-n

{                                                                                // order, pvtkeys[], n[]
	explode {
    dup 2 + pick over 2 + pick                                                   // order, pvtkeys[], n1, ... n, l, order, pvtkeys[]
		3 roll                                                                       // order, pvtkeys[], n1, ... l, order, pvtkeys[], n
		test-sign-n                                                                  // order, pvtkeys[], n1, ... l, sig_n
		over -roll
	} over times tuple nip                                                         // order, sig[]

	sig-list swap                                                                  // order, sig-list
	<b swap <s s, swap nullref, b>
} : test-message

{
	<b 0 32 u, b>
} : test-init-message

{                                                                                // pvtkeys[]
	priv[]>pub[]
	dup count 2 / 1 + swap                                                         // n, keys[]
	numkeys swap                                                                   // keys, n
	<b 0 32 u, swap 8 u, swap ref, b>
} : test-init-c4

{                                                                                // state, msg, t_delta
	| 0 , 1 , 2 ,	swap now + , 1 tuple                                             // state, msg, c7
	-rot <s -1 rot                                                                 // c7, msg{}, -1, state<>
	contract-code <s swap 4 roll                                                   // c7, msg{}, -1, code{}, state<>
	runvmctx                                                                       // 0 (, error_code) state'
	over 0 = { swap } { 3 0 reverse drop } cond                                    // state, exit_code
} : test-run-external

// gas usage test, should be below 10k gas

250 test-pvtkeys constant users15
users15 test-init-c4
	test-init-message
0 test-run-external 0<> abort"init"
1 now 60 + 0 <b b{001100} s, b> order constant order1
	order1 users15 | 0 , test-message
0 test-run-external OK <> abort"order1()+0"
	order1 users15 | 1 , test-message
0 test-run-external OK <> abort"order1(0)+1,2,3"


// state transition tests

7 test-pvtkeys constant users7
users7 test-init-c4

	test-init-message
0 test-run-external 0<> abort"init"

1 now 60 + 0 <b b{001100} s, b> order constant order1

	// order1 collected 1 signature
	order1 users7 | 0 , test-message
0 test-run-external OK <> abort"order1()+0"

	// order1 collected 4 signatures and is sent
	order1 users7 | 1 , 2 , 3 , test-message
0 test-run-external OK <> abort"order1(0)+1,2,3"


	// order1 5th signature is rejected
	order1 users7 | 4 , test-message
0 test-run-external ERR_ORDER_NOT_FOUND <> abort"order1(0,1,2,3)+4 ERR_ORDER_NOT_FOUND"


2 now 60 + 0 <b b> order constant order2
3 now 60 + 0 <b b> order constant order3

	// order2 collected 3 signatures
	order2 users7 | 1 , 2 , 3 , test-message
0 test-run-external OK <> abort"order2()+1,2,3"

	// order3 has 4 signatures and is sent
	order3 users7 | 1 , 2 , 3 , 4 , test-message
0 test-run-external OK <> abort"order3()+1,2,3,4"

	// order2 collected 4th signature and is sent
	order2 users7 | 4 , test-message
0 test-run-external OK <> abort"order2(1,2,3)+4"

	// order2 is already sent
	order2 users7 | 0 , test-message
0 test-run-external ERR_ORDER_NOT_FOUND <> abort"order2(1,2,3,4)+0 ERR_ORDER_NOT_FOUND"

	// order3 is already sent
	order3 users7 | 0 , test-message
0 test-run-external ERR_ORDER_NOT_FOUND <> abort"order3(1,2,3,4)+0 ERR_ORDER_NOT_FOUND"


4 now 60 + 0 <b b> order constant order4
4 now 60 + 0 <b b{00} s, b> order constant order4-alt

	// order4 collected 1 signature
	order4 users7 | 1 , test-message
0 test-run-external OK <> abort"order4()+1"

	// alternative order4 is now rejected, but throws a bit confusing error
	order4-alt users7 | 2 , test-message
0 test-run-external ERR_ORDER_NOT_FOUND <> abort"order4-alt()+2 ERR_ORDER_NOT_FOUND"


5 now 60 - 0 <b b> order constant order5-exp
5 now 60 + 0 <b b> order constant order5

	// order5-exp is expired to begin with
	order5-exp users7 | 1 , test-message
0 test-run-external ERR_ORDER_EXPIRED <> abort"order5-exp()+1 ERR_ORDER_EXPIRED"

	// order5 collected 1 signature
	order5 users7 | 1 , test-message
0 test-run-external OK <> abort"order5()+1"

	// 90s later order5 additional signature is rejected
	order5 users7 | 2 , test-message
90 test-run-external ERR_ORDER_EXPIRED <> abort"order5(1)+2 +90s ERR_ORDER_EXPIRED"

	// but it's removed by empty message containing no signatures
	order5 users7 | test-message
90 test-run-external OK <> abort"order5(1) +90s"


6 now 60 + 0 <b b> order constant order6

	// message without signatures is accepted for expired order only
	order6 users7 | test-message
0 test-run-external ERR_SIGNATURE_MISSING <> abort"order6() ERR_SIGNATURE_MISSING"

	// that wasn't already sent
	order1 users7 | test-message
90 test-run-external ERR_ORDER_NOT_FOUND <> abort"order1(0,1,2,3) +90s ERR_ORDER_NOT_FOUND"

	// after order6 is signed by user1
	order6 users7 | 1 , test-message
0 test-run-external OK <> abort"order6()+1"

	// user1's signature cannot be replayed on it's own
	order6 users7 | 1 , test-message
0 test-run-external ERR_SIGNATURE_REPLAY <> abort"order6(1)+1 ERR_SIGNATURE_REPLAY"

	// but can be replayed as part of another list of signatures
	order6 users7 | 1 , 2 , 3 , test-message
0 test-run-external OK <> abort"order6(1)+1,2"

	// because that message changed confirmations count
	order6 users7 | 2 , 3 , test-message
0 test-run-external ERR_SIGNATURE_REPLAY <> abort"order6(1,2,3)+2,3 ERR_SIGNATURE_REPLAY"


drop

// comment next line to get testnet example
/*

{                                                                                // name, count
	over swap test-pvtkeys-saved                                                   // name, pvtkeys[]
	dup priv[]>pub[]                                                               // name, pvtkeys[], keys
	dup count 2 / 1 + swap                                                         // name, pvtkeys[], keys, n
	numkeys swap
	<b 0 32 u, swap 8 u, swap ref, b>                                              // name, pvtkeys[], state
	<b b{0011} s, contract-code ref, swap ref, dictnew dict, b>                    // name, pvtkeys[], state_init
	| 0 , over hashu , swap                                                        // name, pvtkeys[], state_init, address
	-rot pair swap                                                                 // name, testnet_wallet, state_init

	<b
		b{1000100} s,
		2 pick second unpair addr,
		b{000010} s,
		swap <s s,
		b{0} s,
	b> 2 boc+>B                                                                    // name, testnet_wallet, boc
	rot +".boc" B>file                                                             // testnet_wallet
} : testnet-wallet

{                                                                                // wallet_dest, amount
	swap second                                                                    // amount, dest
	<b
		b{01} s,
		false 1 i,                          // bounce
		b{000100} s,
		swap unpair addr,                   // dest addr
		swap Gram,                          // amount
		0 9 64 32 + + 1+ 1+ u,
		0 32 u,
		"TX" $,
	b>
} : testnet-tx

{                                                                                // tx, seqno
	<b swap 32 u, now 7200 + 32 u, 3 8 u, swap ref, b>
} : testnet-order

{                                                                                // order, src_wallet, user_n[]
	over first                                                                     // order, src_wallet, user_n[], pvtkeys[]
	3 roll 3 0 reverse                                                             // src_wallet, order, pvtkeys[], user_n[]
	test-message                                                                   // src_wallet, msg_tail
	swap second                                                                    // msg_tail. src
	<b b{1000100} s, swap unpair addr, 0 Gram, b{00} s, swap <s s, b>              // msg
} : testnet-message


"wallet1" 3 testnet-wallet constant wallet1
"wallet2" 100 testnet-wallet constant wallet2

wallet1 second unpair 7 smca>$ constant wallet1-addr7
wallet2 second unpair 7 smca>$ constant wallet2-addr7

1 constant wallet1-seqno
1 constant wallet2-seqno

cr
"lite-client -c 'sendfile wallet1.boc'" type cr
"lite-client -c 'last' -c 'getaccount " type wallet1-addr7 type "'" type cr
"lite-client -c 'last' -c 'runmethod " type wallet1-addr7 type " seqno'" type cr
cr

"wallet1_" now (.) $+ constant wallet1-msg-filebase
wallet2 "2" $>GR testnet-tx wallet1-seqno testnet-order constant wallet1-msg
wallet1-msg wallet1 | 0 , 1 , testnet-message 2 boc+>B wallet1-msg-filebase +"_u0u1.boc" B>file

"lite-client -c 'sendfile " type wallet1-msg-filebase +"_u0u1.boc'" type cr
" send 2 Gram from wallet1 to wallet2" type cr
cr

cr
"lite-client -c 'sendfile wallet2.boc'" type cr
"lite-client -c 'last' -c 'getaccount " type wallet2-addr7 type "'" type cr
"lite-client -c 'last' -c 'runmethod " type wallet2-addr7 type " seqno'" type cr
cr

"wallet2_" now (.) $+ constant wallet2-msg-filebase
wallet1 "1" $>GR testnet-tx wallet2-seqno testnet-order constant wallet2-msg
wallet2-msg wallet2 | 0 ,                          testnet-message 2 boc+>B wallet2-msg-filebase +"_u0.boc" B>file
wallet2-msg wallet2 | { dup count 1 + , } 50 times testnet-message 2 boc+>B wallet2-msg-filebase +"_u1-u50.boc" B>file

"lite-client -c 'sendfile " type wallet2-msg-filebase +"_u0.boc'" type cr
"lite-client -c 'sendfile " type wallet2-msg-filebase +"_u1-u50.boc'" type cr
" send 1 Gram from wallet2 to wallet1" type cr
cr


// comment next line to run heavier tests
/*

// wallet can support up to 253 keys (it should be 255, but due to some overflow...)
253 test-pvtkeys constant users253
users253 test-init-c4

	// and it takes 500k gas to compute merkle tree root hash
	test-init-message
0 test-run-external 0<> abort"init"

1 now 60 + 0 <b b> order constant order1_253
2 now 60 + 0 <b b> order constant order2_253

	// checking individual signature is 13k
	order1_253 users253 | 0 , test-message
0 test-run-external OK <> abort"order1_253()+0"

	// 1kk to check half of the signatures
	order1_253 users253 | { dup count 1 + , } users253 count 2 / times test-message
0 test-run-external OK <> abort"order1_253(0)+1...127"

	// or 1.8kk to check them all
	order2_253 users253 | { dup count , } users253 count times test-message
0 test-run-external OK <> abort"order2_253()+0...252"


drop

// */

contract-code