Cell & Bag of Cells(BoC)
Cell
A cell represents a data structure on TOS Blockchain. Cells are able to store up to 1023 bits and possess up to 4 references to other cells.
Bag of Cells
Bag of Cells (BoC) is a format for serializing cells into byte arrays, which is further described in the TL-B schema.
On TOS, everything consists of cells, including contract code, stored data, blocks, achieving streamline and robust flexibility in the process.
Cell serialization
Let's analyze our first example of a Bag of Cells :
1[8_] -> {
24[0AAAAA],
7[FE] -> {
24[0AAAAA]
}
}
In this example we have a 1-bit size root cell that has 2 links: the first to a 24-bit cell and the second to a 7-bit cell which possesses 1 link to a 24-bit cell.
For this framework to work as intended, it’s necessary to turn the cells into a single sequence of bytes. To accomplish this, first, we leverage only unique cell types, below 3 out of 4 are presented as follows:
1[8_]
24[0AAAAA]
7[FE]
Now let's arrange them in such an order that the parent cells do not point backwards. The cell pointed to by the rest must be in the list after the ones that point to it. We get:
1[8_] -> index 0 (root cell)
7[FE] -> index 1
24[0AAAAA] -> index 2
Now, let's calculate descriptions for each of the 3 cells touched on above. These descriptions are made up of 2 bytes that store flags composed of information about the length of the data and the number of data linkages.
The flags are omitted in the current parse and almost always possess a value of 0. The first byte contains 5 flag bits and 3 link count bits. The second byte is the length of the full 4-bit groups (but at least 1 if it isn’t empty). The result is:
1[8_] -> 0201 -> 2 links, length 1
7[FE] -> 0101 -> 1 link, length 1
24[0AAAAA] -> 0006 -> 0 links, length 6
For data with incomplete 4-bit groups, 1 bit is added to the end of the sequence. This means it denotes the end bit of the group and is used to determine the true size of incomplete groups. Let's add the bits below:
1[8_] -> C0 -> 0b10000000->0b11000000
7[FE] -> FF -> 0b11111110->0b11111111
24[0AAAAA] -> 0AAAAA -> do not change (full groups)
Now let's add the link indexes:
0 1[8_] -> 0201 -> refers to 2 cells with such indexes
1 7[FE] -> 02 -> refers to cells with index 2
2 24[0AAAAA] -> no links
And put it all together:
0201 C0 0201
0101 AA 02
0006 0AAAAA
And concat it by joining the corresponding strings into a single array of bytes:
0201c002010101ff0200060aaaaa, size 14 bytes.
Show example
func (c *Cell) descriptors() []byte {
ceilBytes := c.bitsSz / 8
if c.bitsSz%8 ! = 0 {
ceilBytes++
}
// calc size
ln := ceilBytes + c.bitsSz/8
specBit := byte(0)
if c.special {
specBit = 8
}
return []byte{byte(len(c.refs)) + specBit + c.level*32, byte(ln)}
}
Packing a Bag of Cells
Let's pack the cell from the section directly above. We have already serialized it into a flat 14 byte array.
Therefore, we build the header according to its schema.
b5ee9c72 -> id tl-b of the BoC structure
01 -> flags and size:(## 3), in our case the flags are all 0,
and the number of bytes needed to store the number of cells is 1.
we get - 0b0_0_0_00_001
01 -> number of bytes to store the size of the serialized cells
03 -> number of cells, 1 byte (defined by 3 bits size:(## 3), equal to 3.
01 -> number of root cells - 1
00 -> absent, always 0 (in current implementations)
0e -> size of serialized cells, 1 byte (size defined above), equal to 14
00 -> root cell index, size 1 (determined by 3 size:(## 3) bits from header),
always 0
0201c002010101ff0200060aaaaa -> serialized cells
Next, we concat everything above into an array of bytes into our final BoC:
b5ee9c7201010301000e000201c002010101ff0200060aaaaa
Bag of Cells Implementation Examples: Serialization, Deserialization
Special cells
Generally, cells operating on TOS are divided into two main types: ordinary cells and special cells. Most of the cells that the users work with are ordinary cells responsible for carrying information.
Nevertheless, to realize internal functionality of the network, special cells are sometimes needed and are used for a diverse range of purposes, depending on their subtype.
Special cell subtypes are determined by the first 8 bits that form their data structures. The main subtype variations include:
0x01: PrunnedBranch
0x02: Library
0x03: MerkleProof
0x04: MerkleUpdate
Merkle Proof
Merkle Proof cells are actually a hash tree that is used to cryptographically verify (via the merkle proof) that a portion of the cell tree data belongs to the full tree. This design often prevents the verifier from knowing the full contents of the tree, while only revealing its root hash.
Within itself, a cell carries the root hash of an object (for example, a block) and a hash tree of its branches as a child cell. The internal tree itself repeats the structure of the original object (by cryptographically proving its integrity), but at the same time, all branches that are not part of the data and don’t need verification and don’t lead to it are replaced by special PrunnedBranch cells, which instead of storing data, store the cell’s individualized hash.
Therefore, having calculated the root hash of the entire tree, the same hash should be derived from the root cell data of the merkle proof, which should match the hash known to us in advance (e.g., the hash of a block). This approach allows us to prove, for example, the existence of a transaction in a block, provided that the party knows the hash of the block in the first place.
Proof example for getAccountState
The getAccountState is a proof used to verify the integrity of the ShardStateUnsplit structure. But instead of the whole block, the getAccountState proof contains only the requested account: EQCVRJ-RqeZWcDqgTzzcxUIrChFYs0SyKGUvye9kGOuEWndQ.
All branches that are not related to or leading to the getAccountState are replaced with a PrunnedBranch, and those leading to it are Ordinary cells and contain the actual block data.
The symbol * denotes a special cell, the root which uses the 0x03 denotes a MerkleProof, while the 0x01 denotes a PrunedBranch.
Show example
280[03E42E9D59FE3B0900D185EA76AA5F64C6FA0F0C723FFD3CCA5F22B21354064C540219]* -> {
362[9023AFE2FFFFFF110000000000000000000000000001E9AA7F0000000163C1322C00001F522060E3C10194CD420_] -> {
288[0101CA91D55F8B903536211B4FB74EA37FD7930C3774D76FE64B45BCB1FE0E1E26380002]*,
75[8209C398C55C7BDDF32_] -> {
76[0104E1CC62AE3DEEF99_] -> {
288[01011D8C7CB5BFB085D47FB85883C71A7A1DC5B4856A2B9C27DE05F63E994D4A557A0216]*,
76[0101A1AB8F37E15D045_] -> {
76[01010A762B5E3DB9BB3_] -> {
76[01007896888C1BF9AFF_] -> {
288[0101658DA3EABE6B20FA399239F51BF78EB7DB0D8AAE0572E682B986268E041F71590036]*,
68[00F45169A7CA17BB3_] -> {
68[00E1E486CCD6F2D24_] -> {
288[0101F2B70E32B323C3E1817C1780D7A2A49D08BA63B9B9D024B3C713AB936ECA3FD40028]*,
68[00E17E05DDDEF5882_] -> {
68[00E0EEBE3D59F5624_] -> {
288[0101447569C499386266F623BB34E72EF718158ACC2E76ED42F88C6D842D503CDF900020]*,
68[00E0B73C712EA7A3C_] -> {
68[00E026EB80E87B804_] -> {
288[01015DB34588AAB7AF2A5034E0C26168E51FAED17544C56405B0F80CD967A4EE5BD9001B]*,
68[00E023322BD069152_] -> {
68[00E0220B791895CE8_] -> {
68[00E0208438C7659B4_] -> {
68[00E0201CBDC2FA57E_] -> {
288[010132D3C686F68E1E93D14D3DB79EE7D88FB582C87B35BB5B553D82AA25D09196130014]*,
60[00C047CA5AA50C4_] -> {
52[00BD53FE01932_] -> {
52[00A0AC70E85E2_] -> {
288[010178A421C00E63D315BAEB8086668F7D45632ACD4EF17B8A33884C1499856572E2000F]*,
44[00894655318_] -> {
44[0087FCFA2A6_] -> {
44[00805E35524_] -> {
288[010147E47997E4E71FC094644C589682DE513FB731A6B8E841EB2AB68DF4EF1BD92B0002]*,
53[E0A04027728E60] -> {
570[B991A9E656703AA04F3CDCC5422B0A1158B344B228652FC9EF6418EB845A001C09B2869397E6EAB3E5EC55401625FB84ED36424BB6EB0F344BC13953F74CC340000716D4326F30C_] -> {
288[0101BC95189D8B489591E527DFE6FC8787A3A2D382C1DCB6AA9153D7A538F9FFA3B90007]*
},
288[0101D3016CE07C229433613139886E3B2578C61C374FB3AB0C1889666D8588B5B0090008]*
}
},
288[0101641854A854E746372DB4110640D8AA4AFFDCA2CE5F110980D7EB7CF4159652A7000B]*
},
288[01014C4C14F8F5E62FE6145EFBB10255D3F82082E492D8A8E6F17AC610C70A5B06A8000C]*
}
},
288[0101DBC646BFEA5C4D04E6D76C3DCD521BECDD2062F493B9727D3466E0F5272F2FC90010]*
},
288[01017B7679129CCE779E8ADA70B51D8FD2A5B1FD8180E98FE35944399D3E583E49140013]*
}
},
288[0101853D4CD469D08FBE03DA3DDA48568763B19BC5A711BB7887E9D7700D24314275001C]*
},
288[010156C1849FDD43EFEAD3B9FCFB246A5FC40D0D9AA4F4B0C877A9AEB5C4AFFF84850018]*
},
288[010157B0C46BA1C3726890924C2D7F3F4B755BF7B24363CC325B37C9F956DF569AD4001A]*
}
},
288[01014FD09DCDD654FD4C3758B75C755893092B5D7845356647C3CB5028AE4CF75E26001C]*
}
},
288[0101D3E6EF78A7FB3E14C066534F5172078FCC4382D2AD1512470C25E1504CB3BFE50025]*
}
},
288[0101CDF101C69F77450BAC9532A70318AB7F0DD902A4A3EE2CE8CDF5262547B5CB68002A]*,
288[0101AAED7CCC3904836F362AE06EB234B71D64E02EB4BA6D6B7869197A9ED5C4B0B80001]*
},
288[0101AAED7CCC3904836F362AE06EB234B71D64E02EB4BA6D6B7869197A9ED5C4B0B80001]*
},
288[0101EE15491F5B3FFB71A0C759A476F99A84D7A1B5CF8A47B1DE5D1039882CD723710065]*,
288[0101EC90A44EEE02BED840C10E88351163EE9E3613EB9DBE8DA760783DA449714E280001]*
},
288[01011AAC6151A41BCC89EEE855D29D087ACDD30BC4F2069B246BE0C69E3C228C55110067]*,
288[0101BB06F3506745C5F6A6239D132A70B38439CB60FF95F62E45261BA12E844E889B0001]*
},
288[0101B3E9649D10CCB379368E81A3A7E8E49C8EB53F6ACC69B0BA2FFA80082F70EE390001]*
},
288[0101B3E9649D10CCB379368E81A3A7E8E49C8EB53F6ACC69B0BA2FFA80082F70EE390001]*
},
868[0000000000000000FFFFFFFFFFFFFFFF8270E631571EF77CCBBA0EF6D39D6343100001F5220425F440194CD434074F1CF0713270443B84FEA5C35142771F8C6895A2B36117743862354F4EBE767D25641E7D9D005816619EB807E1C18C943B86598038ADD33B65980DCB14EF2_] -> {
288[0101B3E9649D10CCB379368E81A3A7E8E49C8EB53F6ACC69B0BA2FFA80082F70EE390001]*
}
}
}
References
Here a link to the original article by Oleg Baranov.