17

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?

  • It's premature optimisation, probably. IOTA doesn't run on processor/memory constrained devices for many reasons, and reducing the memory consumption won't enable it to do so. – Cybergibbons May 16 '18 at 9:10
  • 2
    Good analysis. Still sad to see that there is no good answer on this. Says a lot about IOTA, to be frankly. – ReneFroger May 19 '18 at 21:04
  • 1
    Keep it civil guys. If anyone has an objective disagreement with the question this should be detailed objectively in a comment when aiming to better the question or otherwise in an answer. SE does not advertise or condone discrediting anyone because you don't like their opinion. – Helmar May 20 '18 at 12:26
3

I will answer the three queries posted at the end of the original question.

What is the reason that this mapping schema was chosen in the IRI software foundation?

As a matter of typical practice, int (4 byte integer) containers are used in most Java software to represent just about anything that doesn't require a long precision integer.

I wasn't chosen as a matter of performance, or a matter of memory/bandwidth conservation, or a matter of representation.

It was chosen for Convenience.

For example, as an alternative to many packing schemes, a byte integer precision container could have been used since the range of -1,0,1 would also have been suitably represented. However if you bitwise AND two bytes, the result is an int and requires a cast back to byte:

byte a = 0;
byte b = 1;
byte result = (byte) (a & b);

Furthermore, if a packing scheme was chosen, then a utility library would need to be created.

That isn't convenient. How 'inconvenient' the other solutions would be is a matter of judgement and not the mandate of this answer. It might be even more convenient to use a packing scheme, as that allows composite operations to be performed more easily (such as operating on several values at once, etc.).

At face value, for speed of development and no additional solutions needed, it is more convenient to just use an int.

What are the advantages to using this mapping?

It allows bitwise math operations without casts. Java provides int results and converts most operands to int for binary operators.

The advantage is Clarity.

How 'unclear' the other solutions would be is a matter of judgement and not the mandate of this answer. It could be argued that byte byteResult = (byte) (a & b) is not unclear. However it is not as clear as int result = a & b.

What are the implications of this for memory management, processing speed and ease of use by developers?

Good

  • Ease of use

Bad

  • Storing trits in ints requires 20 times the required memory.
  • Storing data as both byte[] and int[] in various Objects also uses even more memory.
  • Using so much memory reduces the allowable sizes of non-persistent memory caches.
  • Small non-persistent memory caches may hinder responsiveness.

In developing a new idea, often it is more profitable to do the optimizations after the initial proof of concept is completed.

Some may say that using byte or a packing scheme are premature optimizations. I'd agree that is correct if it was being mocked up.

However, the current scheme is now in production software and therefore optimizations that would save 20 times the memory are not premature optimizations. I think that limiting the caches of internal collections very much limits and hinders the functioning of the product. Even moreso because the product is targeted towards IoT devices.

It can also be argued that IOTA's use of ternary over binary, with these sort of trade-offs, is actually a proof of 'what not to do'. Seeing the implications to using ternary in such a manner may forewarn other projects to avoid this sort of complication in their systems. I'm just being honest - don't down-vote brigade me for saying the honest truth.

In selecting these three answers, I used Occam's razor:

when presented with competing hypothetical answers to a problem, one should select the answer that makes the fewest assumptions. The idea is attributed to William of Ockham (c. 1287–1347), who was an English Franciscan friar, scholastic philosopher, and theologian.

I think that covers it all: Convenience, Clarity, Ease of Use.

1

I was in discord around the time this was originally posted. I figured someone would have provided the answer right after we discussed it...

@Come-from-Beyond brought it up himself, and he said that it was a good write-up, and question, but he was concerned that the answer was too simple.

Java (the language it was first implemented in) uses 4 bytes for an integer.

Abra soon.

  • Can you provide a bit more about that discussion? Or a history link? – Helmar Jun 10 '18 at 11:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.