Designing Fair and Efficient Blockchain Games: System Development

TABLE OF LINKS

Abstract and Introduction

Background

Randomness Practice in Blockchain

System Development

Transaction Fee Comparison

Discussion

Conclusion and References

4. SYSTEM DEVELOPMENT

In this section, we will begin by describing the implementation of the most basic raffle system, explaining its limitations, and introducing solutions. Then, we will gradually iterate our design to an advanced and production-ready raffle system. Source codes of different designs are at https://github.com/Bucket-Protocol/raffle-paper.

4.1 Basic Raffle System with DRAND

The goal of Basic Raffle is to enable the host to randomly select a winner from a group of participants and send the prize to that winner. The design of the Basic Raffle is intuitive and straightforward.

As shown in Figure 1, to initiate the random raffle, the host calls the Move smart contract’s create_coin_raffle, which includes three key parameters: Clock, Participants and Prize. Clock is an object on the Sui platform that allows smart contracts to obtain the current time. Participants is an array containing all participants’ addresses. Prize is an object about the reward for the raffle winner

The create_coin_raffle function then performs the following:

(1) Calculate the DRAND round: The function calculates the current DRAND round according to the current time.

(2) Initiate: The function creates a Raffle Object. Raffle Object includes an array of participants, “current DRAND round

+ N” as the target DRAND round and the prize. N can be set to any number greater than 2, depending on when the creator wants to know the results.

(3) Lock the prize: If the prize is a fungible coin, the function converts the prize object to balance and saves it in a field of the Raffle. If the prize is not fungible, the function saves the prize as a sub-object.

Then, when the signature of the current DRAND round + N is revealed, anyone can settle the raffle by calling settle_coin_raffle, which perform the following steps:

(1) Verify: The function checks the input DRAND signature is valid.

(2) Execute: The function first computes a random value based on the DRAND signature and subsequently uses this random value to pick a winner from the participants’ array. It then proceeds to transfer the prize to the selected winner.

(3) Settle: The function emits events about the raffle result. Then, clear the participants’ array to release space.

The creation and settlement process is illustrated at the first and second Transaction Block in Figure 1.

4.1.1 Advantages. The Basic Raffle has three advantages. Firstly, it fully utilizes DRAND’s capabilities, ensuring that the Raffle’s outcome remains unknown initially while allowing anyone to settle and verify the results. Additionally, the rewards are securely locked within the contract once the Raffle is created, preventing organizers from running multiple Raffles and picking the favorable result, thereby guaranteeing fairness in the process. Lastly, the settlement process involves data clearance and offers a Storage Rebate, creating a strong incentive for anyone to settle the raffle.

4.1.2 Limitations. However, there are several limitations when considering Basic Raffle for production use. First, Sui limits the size of transaction blocks, permitting an array size input of approximately 400 addresses. Consequently, the creation process will encounter errors if the host intends to include more than 400 participants in the Raffle. Furthermore, there is a size restriction of 250 KB for Sui Objects. Even if the host manages to input a sufficient number of addresses, the Raffle object cannot accommodate more than 7500 addresses. Therefore, it becomes necessary to leverage other features of Sui to accommodate more addresses.

4.2 Raffle with Object Table

The Object Table feature within Sui enables a parent object to own other objects. functioning in a manner akin to Mapping in Solidity or a Dictionary in Python. As depicted in Figure 2, Object Table empowers a Raffle Object to possess multiple sub-objects, such as several Prize Objects and Participant Address Objects.

Under these circumstances, we can establish a mechanism that automatically splits participants and prize addresses into separate sub-objects according to size. When the size surpasses 7,500, a fresh sub-object can be created and put under the Object Table, with its corresponding key added to the Object Table key list. In the case of using a single-tier Object Table, this strategic setup allows a Raffle to accommodate an impressive 7, 500 2 , which equals 56, 250, 000 addresses, a capacity more than sufficient for most practical scenarios. Additionally, it is possible to implement multiple levels of Object Table if even larger quantities are needed.

4.2.1 Advantages. Through the use of Object Table, we have addressed the issue of the number of addresses that an Object can accommodate. This type of Raffle is suitable for situations where users actively join by paying for themselves, such as a lottery. An example scenario is as follows:

(1) Initiate: The host initiates the raffle by locking the prizes within the contract, setting the entry fee, and establishing a deadline using DRAND’s Round.

(2) Participants Join: Participants submit their entry fees to the contract. The smart contract verifies that the deadline has not been exceeded and the fees are valid. Then, it adds the users’ address to the Address Object within the Object Table fields of the Raffle Object. If the Address Object is full, a new Address Object is created under the Object Table.

(3) Settle: When the designated time arrives, anyone can settle using DRAND Signatures, and the prizes are sent to the winner’s wallet while the entry fees are transferred to the host’s wallet.

4.2.2 Limitations. In the above case of the raffle, the block size won’t be an issue as users enter one address at a time. However, if we wish to input many addresses at once, we still have to deal with the block size limitation of only being able to enter 400 addresses in a single attempt. This limitation becomes particularly cumbersome when, for example, users who want to create a raffle with 2000 addresses must go through the signing process five times. This problem can be resolved using the Delegate Object Creation or Zero-Knowledge Proof approach.

4.3 Raffle with Delegate Object Creation

Delegate Object Creation aims to streamline the process for users with the help of a Delegate Host, enabling them to efficiently input numerous addresses into Raffle Object at the Sui Network with just one wallet operation. The steps of Delegate Object Creation are depicted in Figure 3 and described in the following:

(1) When a user wants to create a Raffle, he first sends all addresses to the backend of the Delegate Host.

(2) The Delegate Host then batches these addresses and writes them into an Delegated Object using its backend’s Private Key while paying the storage fee. The fee will reflected as a usage fee in the field of Delegated Object.

(3) Then, the user can initiate the raffle with the address table in Delegated Object in a single transaction. Moreover, when using the Address Object, the user pays the storage fee and transaction fees to the Delegate Host.

When users settle a raffle, they can rebate the storage fee by clearing their data to reclaim most usage fees. Additionally, if users do not use the Delegated Object for certain times, the Delegate Host can proactively remove data from the Delegated Object to rebate the storage fee.

4.3.1 Advantages. The advantage of Delegate Object Creation is that users only need to open their wallet and perform the signature once to create a Raffle with lots of participant addresses. By doing so, all participants’ addresses are stored on the transaction history of Sui Network, allowing every participant to verify their inclusion in the Raffle.

4.3.2 Limitations. The limitation of Delegate Object Creation is the waiting time. At the backend, it typically takes 1 second per transaction to upload 400 addresses. If there are 20,000 addresses, users will experience approximately a 50-second waiting time. Moreover, if users only need to select a few winners from many addresses, this method of writing and clearing addresses is inefficient. Consequently, we have developed another approach using Zero-Knowledge Proofs to quickly create a raffle with many addresses.

4.4 Raffle with Zero-Knowledge Proof

Zero-knowledge proof (ZKP) is a cryptography and mathematical technique [13] employed within the realm of blockchain to verify the authenticity of a statement while preserving the confidentiality of the statement’s details. The uses of ZKP in blockchain now extend beyond safeguarding privacy [24] but also encompass optimization in on-chain data storage to enhance efficiency [11]. The most renowned use of ZKP for storage optimization is Ethereum’s Zero-Knowledge rollups (ZK-rollups) [11] with Merkle Tree.

Merkle Tree is a cryptography binary tree structure used for data validation [15]. Merkle Tree ensures data integrity and facilitates efficient verification, making it particularly advantageous when handling extensive data while optimizing bandwidth and computational resources. Illustrated in the right side of Figure 4, in Merkle Tree, each leaf node corresponds to a data block within this structure, whereas each non-leaf node stores the hash of its child nodes. The uppermost node above all the leaves is called the Merkle Root. The number of data blocks that a Merkle Tree can accommodate is related to its number of layers. A Merkle Tree with 𝑁 layers can accommodate 2 𝑁 data blocks.

To confirm the authenticity of a target data leaf, one only needs to calculate the hash of the target leaf and hash it with the hashes of intermediate Merkle nodes (referred to as the Merkle Proof), then compare the outcome with the Merkle Root to ensure they match.

With the implementation of Merkle Tree, ZK-rollups can handle many transactions with a low transaction fee as it only publishes the Merkle Root of these transactions to the Mainnet. A similar mechanism, as illustrated in Figure 4, can also be applied to optimize data storage for the raffle system. The steps for using Merkle Tree to handle participants’ addresses in a ZK-raffle include the following:

(1) Prepare: Collect and organize the addresses of all participants.

(2) Generate: Generate the Merkle Tree and store it in the backend database.

(3) Initiate: Create the ZK-raffle by incorporating the Merkle root, prizes, and the count of Merkle leaves. The smart contract then calculates the DRAND round based on the current time.

(4) Settle Raffle: Employ the DRAND Signature to determine the raffle’s outcome and identify the list of IDs for winners.

(5) Claim Reward: Anyone can use the ID, participant’s address, and Merkle Proofs to claim the prize. The smart contract will check the ID is in the winner list and that the hash of the ID and address with Merkle Proofs is aligned with the Merkle root. After claiming, the ID will be removed from the winner array to avoid double-claiming.

4.4.1 Advantages. The ZK-raffle offers four notable advantages. Firstly, thanks to the lightweight nature of ZKP, the host can launch a ZK-raffle with lots of participants with low transaction fees since the host only needs to store the Merkle Root on the smart contract to represent numerous addresses. Additionally, because the Merkle Tree generation takes place in the backend, the ZK-raffle can be computed and prepared in an extremely short amount of time. Furthermore, this method eliminates the need for Storage Rebates, reducing the financial burden for the raffle creation and the load on the network

4.4.2 Limitations. ZK-raffle has two limitations. First is its complicated prize distribution process. Each prize distribution involves multiple rounds of hashing calculations with Merkle Proofs, which can be costly when there are many winners. Second, the Merkle Tree’s storage tends to be centralized with a database containing all Merkle Tree and Proofs data. This database is essential for users to confirm and claim their rewards or verify their raffle participation. If the database encounters data custody issues resulting in the loss of Merkle Proofs, all rewards may become locked within the smart contract.

4.5 ZK-raffle with single-key VRF

In addition to DRAND Randomness, employing a ZK-raffle with the host’s VRF outputs is a wise choice because they share common limitations, necessitating a centralized host to provide Merkle Proof or single-key VRF to settle the raffle. Moreover, since the Merkle root won’t be cleared after the raffle is settled, it is possible to use the same raffle multiple times. Therefore, they can be integrated to create a fair web3 raffle system, allowing users to draw random prizes fairly

Illustrated in Figure 5, implementing a ZK-raffle with Signature Randomness includes the following steps:

(1) The host initiates the ZK-raffle smart contract, providing essential parameters such as the Merkle Root, prize count, and public key, while setting the entrance fee at 10 Sui.

(2) A user enters the raffle by paying the 10 Sui entrance fee. Subsequently, the raffle smart contract generates a raffle ticket that includes the fee and forwards it to the host.

(3) The host settles the raffle ticket by verifying the VRF output (i.e., BLS signature) and computing a random result through the signature. Afterward, by validating the Merkle Proof to confirm that the random result indeed corresponds to the Prize NFT provided by the host, the host received the 10 Sui Entrance Fee while the user received the Prize NFT.

4.5.1 Advantages. A ZK-raffle with host’s VRF offers three significant advantages. Firstly, it is highly lightweight, avoiding data storage issues commonly associated with other versions of raffles. Secondly, it ensures that the host cannot manipulate the probabilities, as anyone can calculate the Merkle Proof to determine their chances of winning the overall prize, making it ideal for prize raffles such as gaming loot-box. Thirdly, it strikes a good balance between centralization and decentralization. While both Merkle Proofs and Signatures require centralized resources, the host must provide these resources to claim the entrance fees from users. Consequently, the host is strongly incentivized to settle the raffle.

4.5.2 Limitations. On the other hand, there exist two limitations. Firstly, since the randomness is generated from a single private key, the owner of that key (typically the host) can produce beacons at their discretion, granting them the ability to manipulate the raffle result in their favor. In the hands of a malicious host or a host

compromised by hackers, this private key can be used to exploit this vulnerability, resulting in the drawing of numerous grand prizes and undermining the distribution of prizes. Secondly, if the host refuses to settle the raffle, the users’ entrance fee remains locked within the contract. Nevertheless, this limitation can be mitigated by leveraging the transparent nature of blockchain. We can ensure that the host acts fairly by monitoring the number of unsettled raffle tickets and even giving penalties accordingly. For instance, if the host deliberately avoids settling a particular raffle ticket, it may indicate dishonest behavior, and users can claim their winning once a predetermined time period has passed.