update: Since this was posted, on Jun 11, an issue was opened by one of the IOTA Foundation developers to look into how to make the storage of trits use less memory. Although moving to a byte[] is not ideal, it at least tries to solve a future memory use problem in IoT devices.
See Reduce the memory footprint by a factor of 4 using byte array
In the IOTA IRI software and related projects, the three ternary values (-1,0,+1) are individually mapped into 4-byte integer containers, i.e. 4 bytes are used to store individual trits in memory.
Furthermore, in many places in the IRI code, both a binary representation exists in byte[] containers (no loss of economy) and a trinary representation exists in int[] containers (4 bytes per trit entry).
Trit-to-byte conversion within the IRI software
There is a 20X loss of radix economy due to the fact that transactions and hashes have hard-coded container sizes and use 4 bytes for every trit.
To store a number between -128 <= x <= 127 requires one byte. In the IRI software, the same number range requires between 1 and 5 trits. That is between 4 bytes for 1 trit to 20 bytes for 5 trits. In the IRI, each trit array requires 20 times as much memory as just storing it in binary form.
Among alternatives, each byte could be used to represent 5 trits numerically, and 4 trits graphically - if two bits are used to represent each trit.
See Alternatives further down for an example of a visual packing and a sample function to sum a pack of 4 trits and negate a pack of 4 trits.
Example Class in the IRI that holds Trits
The ubiquitous Hash.java class within the IRI software stores identical data as binary in byte[49] byte internal arrays and trinary in int[243] integer internal arrays (972 cum. bytes) -- often simultaneously storing the data as both trinary and binary.
Within Hash.java, one of the binary or trinary arrays is lazily initialized depending on whether the object was instantiated with binary or trinary data. This is all moot due to the fact that as soon as hashcode() or equals() or compare() is called, the binary data is produced and kept alongside.
The trit content is initialized as soon as any hash comparisons or cyrptographic security are used on the hash, or the hash is used alongside Transaction objects. What this means is that the lazy initialization has no net benefit to memory consumption and it further adds to complexity within the code.
Other examples
Transaction
A Transaction contains 8019 trits. The number of bytes used to contain this with the current scheme is 32KB. In binary, this would only require approximately 1.6KB.
When Transaction.java is used, the data is stored simultaneously as bytes (in the class) and trits in the TransactionViewModel.java that accompanies every transaction. Additionally, every TransactionViewModel stores an additional Hash object that also contains yet more 4-byte int arrays.
This limits the number of transactions that can be cached in RAM memory. Furthermore, with the churning of the many embedded Hash objects in Transactions, the Java Virtual Machine also needs to perform additional garbage collection.
Node
In Node.java, where 15,000 Hash objects are stored (16MB of trinary data), it is also stored as binary data within the Hash objects. If this was just binary data or a different trit-to-byte mapping was used, the node could store up to 20 times as many objects in a RAM cache than it currently does. That would increase the cache size from 15,000 to somewhere below 300,000 with little to no effect on memory consumption and possibly a great effect on performance in a high throughput server node environment.
TipsViewModel
In the TipsViewModel.java, there are 5000 tips stored in each of the tips and solidTips. Online network statistics show that the full nodes are often filling this container to the maximum allowed entries. Each of the tips are Hash objects and have data simultaneously stored as byte[] and int[]. Without the duplicate storage in binary and trinary, the number of tips that could be cached would be up to 20X as many as currently allowed.
With binary only data or a different trit-byte mapping scheme, up to 100,000 of each tips and solidTips could be cached in ram, greatly increasing on-the-fly software analytics and even spam and attack prevention within the node.
SignedFiles
In SignedFiles.java, the snapshot is verified by reading a tryte stream, converting the characters to String trytes in Converter.asciiToTrytes, then converting again to trits (4 bytes per trit) in Converter.trits, then passing the data to Kerl.java where it is now converted to bytes in 2 separate stages bytesFromBigInt(bigIntFromTrits(trit_state)) and then operated on by Keccak (binary) hash function. Afterwards, the data from Keccak is converted to a BigInteger where it is then re-converted back into trits with tritsFromBigInt(bigIntFromBytes(byte_state)) and then subsequently used in the curl digest.
If the data was exclusively binary, the most time-consuming and laborious function of trytes-to-trinary-to-BigInteger-to-bytes would be eliminated by a straightforward passing of the data to Kerl for Keccak digesting.
UDPReceiver
In UDPReceiver.java, incoming transactions via the Gossip protocol, are received, passed to Node.java, where a TransactionViewModel is created that stores both the binary data TransactionViewModel(final byte[] bytes, Hash hash) and where the received Hash object is now also containing verified trits (4-byte ints) via the Hash calculate(bytes,tritsLength,curl) function in Hash.java. As such, the data is stored as binary data (as received) and also stored in trits with 20x radix loss ... and then cached in all the internal caching structures for future reference.
Milestone
In Milestone.java, the process of verifying milestones involves reading data persisted to disk and comparing it. Data is read into Hash objects in TransactionViewModels and then compared according to byte data (all Hash objects compare only on byte data) and then compared to trit data which involves also now marshalling the data to a 4-byte trit format with a loss of radix. This process would possibly be faster, more efficient, or less error-prone if only binary data were used.
Looking at other IOTA libraries such as the iota.lib.js library
asciiTotrytes.js
All Javascript Strings are 2-byte encoded (16 bits per character). That means that everywhere a tryte is used in the javascript libraries, two bytes are used for every 3 trits.
converter.js
As can be seen, trits are converted to integer arrays in the javascript identically to the Java version in the IRI.
What I am not referring to
This question regards the IRI software at https://github.com/iotaledger/iri as written and stated as:
The main IOTA Reference Implementation and the embodiment of the IOTA network specification.
I am not talking about or referring to how objects are persisted to disk/SSD such as in the PersistenceProvider.java. The database stores 7 types of objects: Transaction, Milestone, StateDiff, Address, Approvee, Bundle and Tag. All of those objects are collections of Hash.java objects and when they are written to disk, they are all marshalled to pure binary form with no loss of storage efficiency.
What I am talking about, and what matters to this question, is what happens internally in the program, in structures, in caches and collections and functions.
Alternatives
Pack 4 trits to a byte using two bits to represent each trit
For a visual and highly storage-space efficient solution, two bits could have been used to represent [0,1,2] or [-1,0,1] (balanced), resulting in 4 trits packed to each byte and 20 trits packed to each int:
10 = -1
00 = 0
01 = 1
01_00_01_10 = [1,0,1,-1]
10_00_10_00 = [-1,0,-1,0]
etc.
Calculating the sum is also quick and easy because an AND and/or bitwise shift can isolate any trit within the number:
01_00_01_10
& 00_00_00_11
= 00_00_00_10 = 10 (isolates first trit)
01_00_01_10
& 00_00_11_00
>>> 2
= 00_00_00_01 = 01 (isolates second trit)
01_00_01_10
& 00_11_00_00
>>> 4
= 00_00_00_00 = 00 (isolates third trit)
01_00_01_10
>>> 6
= 00_00_00_01 = 01 (isolates fourth trit)
Calculating the sum is also easy with a lookup or with powers of three.
This is one of a few schemes outlined in The Ternary Manifesto, by Douglas W. Jones at THE UNIVERSITY OF IOWA Department of Computer Science (c) 2012.
A Function to quickly sum a pack of 4 trits
A function could quickly convert this to binary. Using the above scheme, 4 trits can be added up with the following, highly machine-optimizable, function:
int tritsToValue(final byte n) {
return (n & 1) - ((n >>> 1) & 1)
+ ((n >>> 2) & 1) * 3 + ((n >>> 3) & 1) * -3
+ ((n >>> 4) & 1) * 9 + ((n >>> 5) & 1) * -9
+ ((n >>> 6) & 1) * 27 + ((n >>> 7) & 1) * -27;
}
This is much faster than the current IOTA scheme of loading 4 int values, converting them using powers of three, and then summing them.
A Function to quickly negate a pack of 4 trits
byte negate(final byte n) {
return (byte) ((n & 0b10_10_10_10) >> 1 | ((n & 0b01_01_01_01) << 1));
}
Rationale
If a different trit-to-byte mapping was used, there would be less memory consumption. Furthermore, the performance and flexibility of working with trit values would be greatly enhanced.
The code in some places could be much more highly performant if the size of the collections was increased or if additional optimizations were performed once the code was made strictly binary - or used a packed trit system.
Of course, all of the issues and examples mentioned above could be done in binary only with greater efficiency, less memory consumption, less complicated code and a leaner cleaner code-base.
Furthermore, all of the marshalling with various types of converting (ascii, trytes, trits, bytes) and all of the composite methods to perform those functions, offer areas of vulnerability and hidden bugs and exploits.
With that in mind ...
What is the reason that this mapping schema was chosen in the IRI software foundation?
What are the advantages to using this mapping?
What are the implications of this for memory management, processing speed and ease of use by developers?
