lib.nr

// Ethereum trie proof implementation

mod rlp; // Module for required RLP encoding/decoding

global KEY_LENGTH: comptime Field = 32; // key length in bytes; <= 55 for simplicity

global MAX_COMPACT_ENCODE_LENGTH: Field = 33; // = KEY_LENGTH + 1

global NIBBLE_LENGTH: comptime Field = 64; // = 2*KEY_LENGTH

global MAX_NODE_LENGTH: comptime Field = 532; // = MAX_RLP_LIST_HEADER_LENGTH (= 1 + MAX_LENGTH_BYTES)
//   + 16*MAX_RLP_ELEMENT_LENGTH (= 16*(1 + KEY_LENGTH))
// + LENGTH_OF_NULL_ELEMENT (= 1)

global MAX_NUM_FIELDS: Field = 17;

// Ethereum trie proof verifier
fn verify_proof_fixed<N>( // N *must* be a multiple of MAX_NODE_LENGTH!
    root_hash: [u8; KEY_LENGTH], // Hash of root, i.e. first, node.
    path: [u8; N], // RLP encoded proof path; assumed to be obtained by right-padding each node (e.g. with zeros) to form a list of length MAX_NODE_LENGTH and concatenated in order.
    depth: Field, // Depth of path. Necessary for technical reasons.
    key: [u8; KEY_LENGTH], // Key to look up along path
    value: [u8; KEY_LENGTH], // Value to verify
    mut value_length: Field) -> bool // Length of value to verify
{
    assert((N as u32) % (MAX_NODE_LENGTH as u32) == 0); // Check that N is a multiple of MAX_NODE_LENGTH
    
    let _r = root_hash; // TODO: Delete once keccak256 is ready
    // let mut prev_hash = root_hash; // TODO: Uncomment when keccak256 is ready

    let key_nibbles = key_as_nibbles(key);
    
    let mut key_offset = 0;

    let mut cur_value = [0; KEY_LENGTH];

    let mut cur_value_length = 0;
    
    let mut cur_node = [0; MAX_NODE_LENGTH];

    for i in 0..path.len()/MAX_NODE_LENGTH
    {
	    if i as u8 < depth as u8
	    {
	        for j in 0..MAX_NODE_LENGTH
	        {
		        cur_node[j] = path[j + i*MAX_NODE_LENGTH];
	        }

	        // First compute current node hash
	        // let node_length = { let rlp_header = rlp::decode_length(cur_node); rlp_header.offset + rlp_header.length }; // Determine length of node
	        // let cur_hash = ... ; // TODO: Compute keccak256 hash
	        // assert(cur_hash == prev_hash); // Make sure hashes are consistent
 	        let lookup = get_fixed(key_nibbles, key_offset, cur_node); // Follow node
 	        cur_value = lookup.0;
	        cur_value_length = lookup.1;
 	        key_offset = lookup.2;

	        // let prev_hash = cur_hash;
	    }
    }
    

    assert(key_offset == 2*key.len()); // All of the key has been exhausted.

    // Need to encode value

    let (enc_value, enc_value_length) = encode_value(value, value_length);

    assert(cur_value_length == enc_value_length); // Value length equality

    for i in 0..KEY_LENGTH
    {
	    if i as u8 < value_length as u8
	    {
	        assert(cur_value[i] == enc_value[i]); // Value equality
	    }
    }
    
    true
}

// Encode value according to 'node cap function' (see Appendix D of Ethereum Yellow Paper)
fn encode_value<N>(value: [u8; N], value_length: Field) -> ([u8; KEY_LENGTH], Field)
{
    assert(value.len() as u32 >= value_length as u32);

    let mut out_value = [0; KEY_LENGTH];
    
    if value_length == 0 // Check for empty string
    {
    	let out = (out_value, value_length);
 	    
	    out
    }
    else if value_length as u32 < 31 // Check for sufficiently short string
    {
	    out_value[0] = 0x80 + value_length as u8;
	    
 	    for i in 1..value.len()
 	    {
 	        out_value[i] = value[i-1];
 	    }
	    
	    let out = (out_value, value_length + 1);

	    out
    }
    else // String too long, so hash it.
    {
	    // Run Keccak256 on [value[0], ... , value[value_length - 1]]
	    let out = (out_value, 32);
	    out
    }
}




// Key-to-nibble conversion
fn key_as_nibbles(key: [u8; KEY_LENGTH]) -> [u4; NIBBLE_LENGTH]
{
    let mut nibkey = [0; NIBBLE_LENGTH];
    
    for i in 0..KEY_LENGTH
    {
	    nibkey[2*i + 1] = (key[i] & 0x0f) as u4;
	    nibkey[2*i] = ((key[i] - nibkey[2*i + 1] as u8) >> 4) as u4;
    }
    
    nibkey
}

// Decode leaf/extension node's first slot into nibbles
// Assume this slot is a 33-byte right-padded array
// Returns nibbles in a right-padded array together with the number of nibbles.
fn compact_decode(input: [u8; MAX_COMPACT_ENCODE_LENGTH], length: Field) -> ([u4; NIBBLE_LENGTH], Field)
{
    let mut nibble = [0 as u4; NIBBLE_LENGTH];
    let mut out_length = 0;

	let mut prev_nibbles = ((input[0] >> 4) as u4, (input[0] & 0x0f) as u4);
    let mut cur_nibbles = (0,0);
    
    let first_nibble = prev_nibbles.0;
	let parity = first_nibble as u1;

    // Consistency checks
    // The first nibble should always be less than 4.
    assert(first_nibble < 4);
    // Parity consistency: If we are dealing with an even number of nibbles, then the second nibble should be 0.
    assert(((1-parity) as u4)*prev_nibbles.1 == 0);

    for i in 0..KEY_LENGTH
    {
        let x = input[i + 1];
        cur_nibbles = ((x >> 4) as u4, (x & 0x0f) as u4);

        nibble[2*i] = (parity as u4)*prev_nibbles.1 + (1 - (parity as u4))*cur_nibbles.0;
        nibble[2*i + 1] = (parity as u4)*cur_nibbles.0 + (1 - (parity as u4))*cur_nibbles.1;

        prev_nibbles = cur_nibbles;
    }

	out_length = 2*length + (parity as Field) - 2;


    assert((out_length as u32) <= (NIBBLE_LENGTH as u32)); // Sanity check
    let out = (nibble, out_length);
    out
}

// Check whether RLP-decoded list represents a valid trie node
fn valid_node_shape_p<M,N>(
    fixed_key_length_p: comptime bool, // Predicate indicating whether key length is fixed or variable
    rlp_list: rlp::RLP_List<N>
) -> bool
{
    let num_fields = rlp_list.num_fields;
    let slot_len = rlp_list.length;
    
    // First check the number of fields
    if num_fields == 2
    {
        // The first slot's length should be <= 1 (compact encoding header) + 32
        assert((slot_len[0] as u32) <= ((KEY_LENGTH + 1) as u32));
        
        // The second slot's length should be <= 32
        assert((slot_len[1] as u32) <= (KEY_LENGTH as u32));

        true
    }
    else if num_fields == 17
    {
        // The first 16 slots should be of length 32 or 0.
        for i in 0..16
        {
            assert(slot_len[i]*(slot_len[i] - KEY_LENGTH) == 0);
        }

        // If we are dealing with a fixed key length, the last slot should be of length 0.
        // Else it should be of length <= 32
        assert((fixed_key_length_p & (slot_len[16] == 0))
               | (!fixed_key_length_p & ((slot_len[16] as u32) <= (KEY_LENGTH as u32))));

        true
    }
    else
    {
        false
    }
}

// Look up nibble (or sequence of nibbles) in RLP-encoded node
fn get_fixed<N>(
    key: [u4; NIBBLE_LENGTH],
    mut key_offset: Field,
    node: [u8; N]) ->
    ([u8; KEY_LENGTH], // Value obtained from node
    Field, // Length of value obtained from node (between 0 and KEY_LENGTH)
    Field) // New key offset
{
    let rlp_list: rlp::RLP_List<MAX_NUM_FIELDS> = rlp::decode1(node);
    let num_fields = rlp_list.num_fields;

    // Make sure node has the right shape, i.e. that it has the right number
    // of slots and that its slots have the right lengths.
    assert(valid_node_shape_p(true, rlp_list));
    
    let mut value = [0; KEY_LENGTH];
    let mut value_length = 0;

    if num_fields == 2 // If we are dealing with a leaf/extension node
    {
        let first_slot: [u8; KEY_LENGTH + 1] = rlp::take_with_offset(node,rlp_list.offset[0]);
	    let (nib, niblen) = compact_decode(first_slot, rlp_list.length[0]);

        // Length check. Should not go past 64 nibbles.
	    assert(NIBBLE_LENGTH as u32 - key_offset as u32 >= niblen as u32);

        // Check that the `niblen` nibbles in the first slot match up with the `niblen` nibbles
        // in `key` starting from offset `key_offset`.

        // TODO: Fix this problematic code!
        // for i in 0..NIBBLE_LENGTH
        // {
        //     if (i as u32) < (niblen as u32)
        //     {
        //         assert(nib[key_offset + i] == key[i]);
        //     }
        // }

        // Slightly more complicated working code
        let mut nib_ptr = 0;
        for i in 0..NIBBLE_LENGTH
        {
            if ((i as u32) >= (key_offset as u32)) & ((i as u32) <= ((key_offset + niblen) as u32))
            {
                assert(nib[nib_ptr] == key[i]);
                nib_ptr += 1;
            }
        }

        // Store length of value obtained
	    value_length = rlp_list.length[1];

        // Increment offset
        key_offset += niblen;

	    // Store value
		for i in 0..KEY_LENGTH
		{
		    value[i] = node[rlp_list.offset[1] + i];
		}

        // Ensure we've followed the right kind of node, i.e. if we're not at the end of the key,
        // we should have followed an extension node, and if we are, then we should have followed a leaf node.
        let node_type = first_slot[0] >> 4;
        assert(((key_offset == NIBBLE_LENGTH) & (node_type > 1))
               | (key_offset != NIBBLE_LENGTH) & (node_type < 2));
        
    }
    else
    {
	    let cur_nibble = key[key_offset * (((key_offset as u32) < (NIBBLE_LENGTH as u32)) as Field)]; // TODO: Avoid this.
	    value_length = rlp_list.length[cur_nibble as Field];

	    key_offset += 1;

	    let nibble_offset = rlp_list.offset[cur_nibble as Field];
		for j in 0..KEY_LENGTH
		{
		    value[j] = node[nibble_offset + j];
		}
	}
    
    let out = (value, value_length, key_offset);

    out
}

// Trie proof test
#[test]
fn cryptopunk1() // Who owns the first cryptopunk? cf. https://www.youtube.com/watch?v=2-yYtEJdrFY&t=266s
{
    // Block 14194126
    // Address: 0xb47e3cd837dDF8e4c57f05d70ab865de6e193bbb
    // Value: 0xb88f61e6fbda83fbfffabe364112137480398018
    // Key: 0xbbc70db1b6c7afd11e79c0fb0051300458f1a3acb8ee9789d9b6b26c61ad9bc7
    // Fetch proof using e.g.
    // curl https://eth-mainnet.g.alchemy.com/v2/your-api-key \
    // -X POST \
    // -H "Content-Type: application/json" \
    // -d '{"jsonrpc":"2.0","method":"eth_getProof","params":["0xb47e3cd837dDF8e4c57f05d70ab865de6e193bbb",["0xbbc70db1b6c7afd11e79c0fb0051300458f1a3acb8ee9789d9b6b26c61ad9bc7"],"latest"],"id":1}'

    let path = [249,2,17,160,251,89,247,143,226,191,198,83,149,72,1,45,104,20,219,154,238,66,4,191,200,203,254,105,20,1,23,0,248,161,225,108,160,148,246,5,114,77,164,105,60,73,249,243,5,239,223,48,172,56,52,129,202,210,19,37,187,136,161,35,155,79,37,98,106,160,225,101,143,149,19,184,165,84,95,17,82,203,202,197,74,175,216,214,160,49,194,89,172,219,63,36,94,248,198,85,0,74,160,12,92,91,61,216,69,183,3,50,98,154,181,50,29,198,141,126,47,224,57,67,159,191,139,180,222,55,116,155,102,72,217,160,133,143,252,202,185,113,114,31,177,187,82,219,19,87,121,64,205,241,145,199,128,51,127,248,153,60,141,180,123,199,234,190,160,101,134,57,72,179,96,2,122,3,152,117,150,193,247,255,185,101,222,164,33,216,164,70,86,81,175,213,185,31,1,49,230,160,165,5,210,150,55,251,238,31,214,113,136,45,204,69,219,241,154,32,22,43,244,153,118,160,209,102,92,91,235,14,38,121,160,97,190,92,162,193,211,46,43,241,111,108,144,21,130,10,42,11,187,196,16,45,53,22,19,107,205,175,64,59,82,220,55,160,19,178,130,134,15,94,184,158,145,77,246,154,68,2,239,243,114,86,239,86,81,162,144,169,138,8,219,139,186,85,104,58,160,28,152,157,133,223,35,68,105,142,14,225,245,216,41,207,242,205,114,140,25,194,240,158,248,227,46,255,168,242,227,10,13,160,235,101,48,90,110,124,194,146,172,103,180,94,125,35,222,180,114,201,214,112,192,139,221,73,225,185,30,88,225,96,143,84,160,129,5,29,59,216,86,200,79,195,167,7,252,120,103,15,114,101,53,71,127,67,41,226,212,215,101,167,120,138,81,123,143,160,162,145,113,7,201,40,201,154,28,47,211,16,108,95,34,215,207,38,248,185,242,193,12,246,75,205,214,10,38,80,16,43,160,22,149,20,80,124,170,89,5,52,93,33,23,85,160,29,247,187,129,57,126,1,173,97,28,11,63,216,217,98,133,232,220,160,69,152,156,6,71,251,156,239,81,86,57,56,152,161,103,170,163,233,140,160,193,48,212,50,236,3,48,8,231,217,68,214,160,214,34,129,230,87,246,176,74,131,217,6,108,228,176,174,68,138,170,37,84,76,189,44,130,112,213,237,224,242,100,95,143,128,249,2,17,160,204,94,208,184,72,67,71,121,107,229,250,174,232,39,63,204,86,132,175,174,92,119,2,32,234,175,244,98,35,72,133,42,160,48,153,188,131,53,240,136,188,205,189,128,236,161,52,171,32,123,59,161,29,65,29,220,144,150,0,129,229,45,163,134,40,160,211,190,127,163,207,47,137,2,234,49,166,141,241,17,66,222,110,12,46,123,249,75,67,32,151,207,206,93,253,192,54,39,160,149,251,160,109,220,200,246,169,105,99,96,228,68,73,249,229,174,244,183,211,76,147,147,144,224,12,148,106,233,167,76,116,160,82,253,0,29,135,176,127,164,195,188,249,231,6,183,227,224,22,196,50,213,54,203,72,68,137,209,196,248,4,253,133,54,160,76,149,1,215,238,36,83,180,202,11,178,89,230,216,69,139,104,159,184,93,164,18,46,137,45,186,115,65,145,205,119,188,160,115,237,80,197,56,62,161,136,160,172,15,143,232,47,155,110,186,0,196,57,168,121,105,77,246,43,31,149,117,75,117,150,160,130,119,126,67,189,31,238,98,52,233,159,47,30,96,195,171,19,56,157,35,25,21,235,142,68,153,78,101,100,2,57,151,160,144,93,8,218,18,133,113,96,84,88,165,34,180,171,68,209,64,19,191,19,168,191,232,167,179,212,151,38,109,144,245,180,160,235,252,249,81,250,184,119,124,213,125,87,240,122,210,13,107,140,192,34,57,240,139,240,230,218,214,120,168,18,101,115,63,160,7,251,140,87,174,78,191,170,235,159,200,87,40,4,22,133,90,207,151,30,3,147,54,66,45,108,65,42,213,96,115,156,160,143,58,160,75,37,72,79,217,197,211,233,237,109,226,248,213,162,76,123,106,34,216,64,234,221,162,227,114,130,89,110,242,160,186,72,181,250,245,89,139,195,54,156,83,4,163,113,200,8,178,105,65,177,223,200,71,198,204,16,63,128,54,149,182,186,160,250,118,41,214,208,33,247,152,127,124,203,251,161,183,127,235,117,167,160,216,254,24,138,76,184,48,250,23,71,85,212,35,160,134,108,64,163,249,62,132,234,185,162,242,228,44,82,68,116,99,237,90,184,29,35,27,54,195,3,116,222,226,0,229,106,160,52,90,156,62,34,246,166,97,199,80,253,32,127,173,198,129,159,95,204,82,136,8,211,44,92,49,41,65,251,235,216,20,128,249,2,17,160,16,52,41,4,106,244,122,158,97,103,58,96,78,119,13,196,29,192,7,197,93,185,91,104,65,10,213,80,25,253,201,119,160,99,226,242,52,224,55,169,26,189,91,193,28,1,253,59,247,26,198,178,4,80,107,174,135,251,108,230,33,245,12,165,172,160,218,28,101,226,68,72,17,19,202,134,101,145,114,94,158,190,60,185,199,247,7,40,3,57,34,16,129,91,160,73,7,206,160,132,34,66,56,9,30,179,208,219,136,153,157,160,236,250,226,95,153,24,38,1,240,228,41,117,28,247,195,63,113,26,157,160,112,170,58,234,216,89,42,126,139,21,43,44,98,187,38,21,212,185,80,48,249,131,72,251,155,197,167,34,223,180,154,37,160,253,218,130,199,68,153,141,19,216,149,99,99,54,201,171,223,216,171,18,55,15,120,74,175,68,139,14,189,190,63,239,59,160,94,199,190,215,147,134,100,152,161,160,185,168,247,212,4,251,50,232,217,119,113,181,209,74,197,20,73,107,31,77,59,174,160,22,221,195,230,159,173,214,181,69,99,38,245,153,142,206,148,70,218,59,18,180,47,69,82,252,52,3,69,206,224,203,56,160,115,1,212,195,105,160,165,238,3,255,203,154,173,204,200,57,55,180,123,15,248,252,75,41,52,105,31,14,193,105,81,114,160,116,95,232,43,89,83,196,203,4,225,246,152,56,41,102,200,245,170,93,63,47,200,9,14,155,202,82,53,171,161,114,240,160,76,121,242,107,106,6,5,54,174,132,114,165,21,175,174,15,43,239,28,25,91,101,150,231,68,5,149,23,170,155,165,208,160,209,166,45,131,155,154,139,188,146,138,128,171,125,95,170,4,255,248,54,97,157,173,85,243,0,182,186,151,29,211,49,46,160,215,233,123,209,95,254,3,211,130,155,102,147,195,1,36,117,91,101,21,132,128,227,100,46,25,219,109,94,68,99,173,45,160,81,121,242,103,174,208,230,76,220,90,237,138,17,38,100,96,7,172,79,100,236,33,60,19,179,223,227,216,154,212,4,149,160,18,90,118,20,167,150,50,13,211,230,184,27,165,84,167,110,4,205,149,83,174,208,43,122,14,58,249,30,101,194,41,76,160,74,237,218,87,155,244,168,177,208,213,70,251,69,136,69,249,52,41,122,105,254,194,143,31,47,31,235,100,46,76,57,47,128,248,177,128,128,128,128,128,160,28,249,182,132,51,145,111,142,211,178,180,147,92,161,244,19,73,10,187,240,227,19,159,57,142,9,254,81,139,248,67,175,128,128,160,73,97,138,225,4,245,30,87,189,138,110,63,153,2,254,23,33,35,77,206,160,31,55,142,20,57,31,122,160,140,79,188,128,160,15,143,44,113,58,7,157,9,191,167,58,140,221,27,221,62,79,240,181,31,177,121,148,175,107,82,237,215,126,250,137,75,128,160,41,222,166,27,179,177,3,173,193,241,7,231,155,19,232,201,100,152,160,60,219,21,187,170,229,4,97,78,229,104,217,14,160,0,188,57,48,132,60,195,69,115,33,11,219,146,191,236,195,45,181,187,210,167,19,203,73,127,26,141,27,147,110,109,204,128,128,128,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
		        ,246,159,32,176,50,213,165,250,58,91,101,68,86,110,228,106,15,107,143,232,177,55,94,200,120,220,59,230,88,11,7,132,149,149,148,184,143,97,230,251,218,131,251,255,250,190,54,65,18,19,116,128,57,128,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
		        ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 // depth 6
		        ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 // depth 7
		        ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 // depth 8
    ];
    let depth = 5; // Actual depth

    let key = [0xed,0x65,0xb0,0x32,0xd5,0xa5,0xfa,0x3a,0x5b,0x65,0x44,0x56,0x6e,0xe4,0x6a,0x0f,0x6b,0x8f,0xe8,0xb1,0x37,0x5e,0xc8,0x78,0xdc,0x3b,0xe6,0x58,0x0b,0x07,0x84,0x95]; // keccak256([0xbb,0xc7,0x0d,0xb1,0xb6,0xc7,0xaf,0xd1,0x1e,0x79,0xc0,0xfb,0x00,0x51,0x30,0x04,0x58,0xf1,0xa3,0xac,0xb8,0xee,0x97,0x89,0xd9,0xb6,0xb2,0x6c,0x61,0xad,0x9b,0xc7]
    let value = [0xb8,0x8f,0x61,0xe6,0xfb,0xda,0x83,0xfb,0xff,0xfa,0xbe,0x36,0x41,0x12,0x13,0x74,0x80,0x39,0x80,0x18,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00];
    let value_length = 20;
    assert(verify_proof_fixed
           ([0; KEY_LENGTH], path, depth, key, value, value_length));

}

// Auxiliary function tests
#[test]
fn fixed_key_lookup_test()
{
    let x3 = [246,159,32,176,50,213,165,250,58,91,101,68,86,110,228,106,15,107,143,232,177,55,94,200,120,220,59,230,88,11,7,132,149,149,148,184,143,97,230,251,218,131,251,255,250,190,54,65,18,19,116,128,57,128,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
    let rlp_list3: rlp::RLP_List<MAX_NUM_FIELDS> = rlp::decode1(x3);
    assert(rlp_list3.num_fields == 2);
    assert(rlp_list3.length[0] == 31);
    assert(rlp_list3.length[1] == 21);
    let (value3, value_length3, _key_offset3) = get_fixed(
	    key_as_nibbles([0xed,0x65,0xb0,0x32,0xd5,0xa5,0xfa,0x3a,0x5b,0x65,0x44,0x56,0x6e,0xe4,0x6a,0x0f,0x6b,0x8f,0xe8,0xb1,0x37,0x5e,0xc8,0x78,0xdc,0x3b,0xe6,0x58,0x0b,0x07,0x84,0x95]),
	    4,
	    x3);
    assert(value_length3 == 21);
    assert(value3[0] == 0x94);
    assert(value3[20] == 0x18);
    
}

#[test]
fn nibble_check()
{
    assert(key_as_nibbles([0x56,0xe8,0x1f,0x17,0x1b,0xcc,0x55,0xa6,0xff,0x83,0x45,0xe6,0x92,0xc0,0xf8,0x6e,0x5b,0x48,0xe0,0x1b,0x99,0x6c,0xad,0xc0,0x01,0x62,0x2f,0xb5,0xe3,0x63,0xb4,0x21]) == [0x05,0x06,0x0e,0x08,0x01,0x0f,0x01,0x07,0x01,0x0b,0x0c,0x0c,0x05,0x05,0x0a,0x06,0x0f,0x0f,0x08,0x03,0x04,0x05,0x0e,0x06,0x09,0x02,0x0c,0x00,0x0f,0x08,0x06,0x0e,0x05,0x0b,0x04,0x08,0x0e,0x00,0x01,0x0b,0x09,0x09,0x06,0x0c,0x0a,0x0d,0x0c,0x00,0x00,0x01,0x06,0x02,0x02,0x0f,0x0b,0x05,0x0e,0x03,0x06,0x03,0x0b,0x04,0x02,0x01]);
}

#[test]
fn compact_decode_test()
{
    let (nibble0, len0) = compact_decode([0x11, 0x23, 0x45,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 3); // TODO: Legit header!
    assert(len0 == 5);
    assert([nibble0[0], nibble0[1], nibble0[2], nibble0[3], nibble0[4]] == [1,2,3,4,5]);

    let (nibble1, len1) = compact_decode([0x20, 0x0f, 0x1c, 0xb8, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 4); // TODO
    assert(len1 == 6);
    assert([nibble1[0], nibble1[1], nibble1[2], nibble1[3], nibble1[4], nibble1[5]] == [0,15,1,12,11,8]);

    let (nibble2, len2) = compact_decode([0x3f, 0x1c, 0xb8, 0x99, 0xab, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 3);
    assert(len2 == 5);
    assert([nibble2[0], nibble2[1], nibble2[2], nibble2[3], nibble2[4]] == [15,1,12,11,8]);
    
}

// Omit the following test due to compiler panic

#[test]
fn encode_value_test()
{
    let val1 = [0xb8,0x8f,0x61,0xe6,0xfb,0xda,0x83,0xfb,0xff,0xfa,0xbe,0x36,0x41,0x12,0x13,0x74,0x80,0x39,0x80,0x18,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00];
    let val1_length = 20;

    let encoded_val1 = encode_value(val1,val1_length);

    assert(encoded_val1.0 == [0x94,0xb8,0x8f,0x61,0xe6,0xfb,0xda,0x83,0xfb,0xff,0xfa,0xbe,0x36,0x41,0x12,0x13,0x74,0x80,0x39,0x80,0x18,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00]);
    assert(encoded_val1.1 == 21);
}